Programming Praxis

A mathematician purchased four items in a grocery store. He noticed that when he added the prices of the four items, the sum came to $7.11, and when he multiplied the prices of the four items, the product came to $7.11.

Your task is to determine the prices of the four items. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Pages: 1 2

Astronomy has fascinated mankind since its earliest days; science and math were developed first to study the heavens. Even today, your local newspaper tells you such astronomical information as the time of local sunrise and sunset and the phase of the moon.

Your task is to write functions that calculate the time of sunrise and sunset for any spot on earth for any day of the year; you will have to do your own research on the internet to find a suitable set of formulas. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Pages: 1 2

In the previous exercise we wrote a Master Mind setter. In today’s exercise we will write a solver, using an algorithm given by Donald E. Knuth in his article “The Computer As Master Mind” in Volume 9, Number 1, the 1976-1977 edition, of The Journal of Recreational Mathematics.

The central concept of Knuth’s algorithm is the pool of potential solutions. His algorithm chooses at each step a probe that minimizes the maximum number of remaining possibilities over all possible response of the codebreaker; in the event of a tie, any pattern that achieves the minimum may be used, subject to the condition that a probe that is a member of the current pool is preferred to one that is not.

For instance, consider the pool of 1296 possible code words at the start of a puzzle. There are essentially five possible starting probes: 1 1 1 1, 1 1 1 2, 1 1 2 2, 1 1 2 3, and 1 2 3 4 (rotations are excluded, as are variants that substitute one symbol consistently for another). The remaining pool sizes after each of the five probes is applied to all of the 1296 possible code words are given in the table below:

The minimax solution is 256, achieved when the probe is 1 1 2 2, so that should always be the first probe. Then the solution is determined by making the minimax probe, reducing the pool by applying the result of the probe, and repeating on the reduced pool until the puzzle is solved.

Your task is to write a Master Mind solver based on the rules set out in the previous exercise and Knuth’s algorithm given above. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Pages: 1 2

Master Mind is a two-player game of deductive logic. One player, the setter, selects a four-symbol code, and the other player, the solver, tries to identify the code by trying test patterns, probes, to which the setter responds with the number of black hits, indicating the number of positions where the code symbol and probe symbol are identical, and the number of white hits, where a probe has the right symbol in the wrong position. Setter and solver change roles after each puzzle is solved, for a pre-defined number of rounds, and the winner is the player who has solved the puzzles with the least number of probes. With six symbols and four pegs there are 6⁴ = 1296 possible codes. The physical game uses colored pegs for the symbols; we will use digits instead. Variants of the game increase the number of symbols and/or the length of the code; a variant with five pegs using eight colors is marketed under the name Super Master Mind. Here is a sample game:

1 1 2 2    B
1 3 4 4    W
3 5 2 6    BWW
1 4 6 2    BW
3 6 3 2    BBBB

The solver first probes with the pattern 1 1 2 2, which has a single black hit. The second probe, 1 3 4 4, receives a single white hit. The third probe, 3 5 2 6, earns a single black hit and two white hits. The fourth probe, 1 4 6 2, receives one black hit and one white hit. The fifth probe, 3 6 3 2, solves the puzzle with four black hits.

Your task is to write a program that performs the role of the setter, selecting a random code, prompting for probes, and scoring each probe until the human solver who is playing the game solves the puzzle. In the next exercise you will be asked to write a solver. 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

It is well known that any comparison-based sort, as we have been studying, has a lower time bound of O(n log n). But if all the keys are positive integers less than or equal to n, it is possible to sort in O(n) linear time by taking advantage of the structure of the keys themselves.

Count sort determines, for each input element x, the number of elements less than x, then places x directly in its position in the output; if there are k elements less than x, then x belongs in the k^th + 1 position (being careful to properly consider the case of equal elements). Count sort requires two temporary arrays, one to hold the counts of the various elements, which act as indexes into the array, and one to build up the output.

Radix sort extends count sort by making multiple passes based on the positional digits of the integers being sorted: first do a count sort on the digits in the ones column of the integers, then a count sort on the digits in the tens column, then the hundreds column, the thousands column, and so on until the input is sorted, taking advantage of the fact that count sort is stable. Radix sort works on other kinds of keys besides integers; for instance, dates can be sorted by doing count sort on day, month and year in succession.

Your task is to write functions that sort arrays using count sort and radix sort. 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 last O(n log n) sorting algorithm that we shall consider in our current series of exercises is merge sort. If you have two sorted sequences, they can be merged into a single sorted sequence in time linear to their combined length by running through them in order, at each step taking the smaller of the heads of the two sequences. Then mergesort works by recursively merging smaller sequences into larger ones, starting with trivially-sorted sequences of one element that are merged into two-element sequences, then merging pairs of two-element sequences into four-element sequences, and so on, until the entire sequence is sorted.

Your task is to write a function that sorts an array by the merge sort algorithm described above, according to the conventions of the prior exercise. 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

A priority queue is a data structure that permits insertion of a new element and retrieval of its smallest member; we have seen priority queues in two previous exercises. Priority queues permit sorting by inserting elements in random order and retrieving them in sorted order. Heapsort uses the heap data structure to maintain a priority queue. The heap is a tree embedded in an array, with the property that the item at each index i of the array is less than the children at indices 2i and 2i+1.

The key to understanding heapsort is a function we call heapify that gives the sub-array A[i .. n] the heap property if the sub-array A[i+1 .. n] already has the property. Heapify starts at the i^th element of the array and swaps each element with its smallest child, repeating the operation at that child, stopping at the end of the array or when the current element is smaller than either of its children. Then heapsort works in two phases; the first phase forms an initial heap by calling heapify on each element of the array from n/2 down to 1, then a second phase extracts the elements in order by repeatedly swapping the first element with the last, re-heaping the sub-array that excludes the last element, and recurring with the smaller sub-array that excludes the last element.

Your task is to write a function that sorts an array using the heapsort algorithm, using the conventions of the prior exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Pages: 1 2

Quick sort was invented by Sir Charles Antony Richard “Tony” Hoare, a British computer scientist and winner of the 1980 Turing Award, in 1960, while he was a visiting student at Moscow State University. Though it has an annoying quadratic worst-case performance, quick sort has expected O(n log n) performance and is significantly faster in practice than most other O(n log n) sorting algorithms, and it is possible to arrange that the worst-case performance almost never happens for real-world data.

Quick sort works as follows: First, an element, called the pivot, is chosen from the array. Then the array is partitioned around the pivot by reordering the array so that all elements less than the pivot come before it and all items greater than the pivot come after it; this puts the pivot element in its final position in the array. Finally, quick sort is called recursively on the less-than and greater-than partitions; the base of the recursion is arrays of zero or one element.

There are many ways to choose the pivot element. Some algorithms choose the first element of the array, or the last; others choose the median of three elements (first, middle, last). Our preference is to choose an element at random, since that virtually eliminates the possibility of quadratic performance (unless there is collusion between the random-number generator and the data).

Likewise, there are many ways to perform the partitioning. One approach, due to Nick Lomuto, uses a single pointer to run through the sub-array, swapping the current element for the last element of the sub-array, which is then decremented, if it is greater than the pivot. Another approach uses two pointers that approach each other, swapping elements when the two pointers cross over the pivot element. Lomuto’s partition is simpler; dual pointers is quicker, but the details are hard to get right.

Your task is to write a function that sorts an array using the quick sort algorithm, using the conventions of a previous exercise. 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