Programming Praxis

The Leonardo numbers A001595 are defined as L₀ = 1, L₁ = 1, L_n = L_n−2 + L_n−1 + 1; Dijkstra discusses Leonardo numbers in EWD797, and uses them in the analysis of smoothsort. Leonardo numbers are similar to Fibonacci numbers, and are related by the formula L_n = 2 F_n+1 − 1.

Your task is to write a function that computes Leonardo numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We have today an exercise inspired by those “programming challenge” websites where you upload code and an automated judge tells if you pass or fail and how your time compares to other programmers. I haven’t seen this particular problem at one of those sites, but it feels like something they would do; this would also make a good interview question:

You are given a list of people’s lifespans with birth and death years; for instance, a person lived from 1924 to 1991. Some people have only a birth year because they are still living. You are to find the year in which the most people of a set of people were alive.

Input: A number n on a line by itself indicating the number of input cases, followed by n sets of lines containing a number m indicatingthe number of people in this particular input case, followed by m lines indicating birth and, possibly, death years.

Output: For each input case, the year (or years) in which the most people were alive.

Example: For the input:

2
3
1910 1948
1948 2011
1927 1995
3
1910 1948
1927 1995
1945

You should produce the following output:

1948
1945 1946 1947 1948

Your task is to write the indicated program. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We’ve looked at algorithms to process a stream of data in previous exercises (streaming median, streaming knapsack, reservoir sampling), and we also looked at an algorithm that finds the most frequent items (the “heavy hitters”) in a file. Today’s exercise combines the two to find the most frequent items in a stream; it’s called the “Britney Spears” algorithm because it is the algorithm used to cull the most frequently-seen items in Twitter feeds and other social media, and the pop starlet always seems to be on that list.

There are two similar algorithms used to find the n most frequently-appearing items in a stream. The first, due to Jayadev Misra and David Gries, uses an initially-empty associative array of items and their associated counts and processes each item in the input stream according to the following algorithm:

    if the new item is already in the array
        increment the associated count
    else if there are less than n items in the array
        add the new item to the array with a count of 1
    else for each item in the array
             decrement the associated count and
             remove any items whose count becomes zero
    

The other algorithm, called the “space-saving” algorithm, is due to Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. The first to parts of the algorithm are the same as the Misra-Gries algorithm. But, when a new item is found and there is no space to store it, the item already in the array that has the smallest associated count is replaced by the new item, and its count is incremented; thus, the counts are never reset, only the item is replaced.

With either algorithm, the array can be queried at any time to see the current list of most-frequent items in the array.

Your task is to implement the two heavy hitter algorithms. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

The Perrin Numbers P_n are defined as P₀ = 3, P₁ = 0, P₂ = 2, and P_n+3 = P_n+1 + P_n for n > 2. If P_n (mod n) ≡ 0, then n is most likely prime. Perrin’s formula always reports that a prime number is prime, but sometimes reports a composite number is prime, though seldom: there are only two pseudoprimes, 271441 and 904631, less than a million.

The Perrin sequence A001608 is computed by sequential addition. An individual member of the Perrin sequence can be computed by matrix exponentiation followed by matrix multiplication:

The terms of the Perrin sequence grow exponentially at a rate of 1.32471795, which is known at the plastic number.

The Perrin pseudoprimality test can be implemented using matrix exponentiation followed by matrix multiplication with all operations performed modulo n. Sloane gives a list of Perrin pseudoprimes at A013998.

Your task is to write a function to determine if a number is a Perrin pseudoprime and to find all Perrin pseudoprimes less than a million. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Today’s task is to solve a current exercise in recreational mathematics.

The Guardian recently published a math puzzle that is apparently given to third-grade students (eight-year old children) in Vietnam. The puzzle is a graphic in the form of a snake, and the digits 1 through 9 are to be inserted in the nine empty boxes in such a way as to make the formula correct. Although it may not be clear, the colon symbol is used for division, and the normal order of operations is to be preserved, so the formula becomes A + ((13 * B) / C) + D + (12 * E) − F − 11 + ((G * H) / I) − 10 = 66.

Your task is to write a program that generates all possible solutions to the problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

In the previous exercise I needed a string-replace function, and was surprised not to find one in my code library. I quickly wrote a very simple function, noting that it was “awful” because it had quadratic performance.

Your task is to write a string-replace function that has linear time instead of quadratic. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

There is a lot of information available on the Internet, and a lot of APIs that make it readily accessible. Today’s exercise is intended to remind you of that, and to spur you to find out something interesting for yourself.

Your task is to write a program that fetches and displays information from the Internet; I chose to get baseball scores for my beloved Cardinals, but you are welcome to pick some other topic of interest to you. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Our exercise today is an interview question. Like all of our interview questions, it works better if you put some pressure on yourself to simulate the pressure of an interview; so, for today’s exercise you must complete your solution in fifteen minutes:

Given two positive integers, a numerator and a denominator, and a third positive integer, the number of digits, write the decimal ratio of numerator to denominator to the requested number of digits. For instance, given a numerator of 3227, a denominator of 557, and a number of digits of 30, the correct output is 5.793536804308797127468581687612.

Your task is to write a program to convert ratios to decimals. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

An interesting variant on binary search is Fibonacci search. Invented by Jack Kiefer in 1953 to find the zeros of a function, and first applied to searching in an array by David Ferguson in 1960, its initial appeal was to improve locality when searching for a record on magnetic tape. It was later applied to searching on paged memory when it was expensive to read a segment of an array from disk, and it is now used to improve locality of cache memory; a good idea never goes away! Here is a description of Fibonacci search, taken from Wikipedia:

Let Fk represent the k-th Fibonacci number where Fk+2=Fk+1 + Fk for k>=0 and F0 = 0, F1 = 1. To test whether an item is in a list of n ordered numbers, proceed as follows:

1) Set k = m, where Fm is the smallest Fibonacci number greater than or equal to n.
2) If k = 0, halt and report failure.
3) Test item against entry in position Fk-1.
4) If match, halt and report success.
5) If item is less than entry Fk-1, discard entries from positions Fk-1 + 1 to n. Set k = k – 1 and go to 2.
6) If item is greater than entry Fk-1, discard entries from positions 1 to Fk-1. Renumber remaining entries from 1 to Fk-2, set k = k – 2 and go to 2.

Your task is to implement Fibonacci search. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We have today a famous puzzle:

Five sailors are shipwrecked on a desert island. They quickly determine that the only other inhabitant of the island is a monkey and that the only food is coconuts. They set about collecting as many coconuts as they can and put them all in a pile. By nightfall they are too tired to divide the harvest; so they agree to go to sleep and divvy up the coconuts the next morning.

During the night one sailor awakens, suspicious that the others might try to cheat him, and desides to take his portion then and there and not wait until morning. He divides the coconuts into five piles and finds there is one coconut left over, which he gives to the monkey. He hides one of the five piles, then puts the rest of the nuts together and returns to sleep. About an hour later a second sailor awakens with the same suspicions and does the same thing: He divides the coconuts into five piles, leaving one extra, which he gives to the monkey. Then he hides what he thinks is his share and goes back to sleep.

One after another the rest of the sailors do the same: they each take one fifth of the coconuts in the pile (after giving the extra one to the monkey) and then return to sleep.

When the sailors awaken the next morning they all notice the coconut pile is much smaller than it was the night before, but since each man is as guilty as the others, no one says anything. They divide the coconuts (for the sixth time), but this time there is no coconut left for the monkey.

How many coconuts were in the original pile?

Your task is to determine how many coconuts were in the original pile; first solve the problem for 5 sailors, then again for 6 sailors, and finally for 30 sailors. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2