Programming Praxis

In their 1973 paper “The Early Development of Programming Languages,” Luis Trabb Pardo and Donald Knuth give the following algorithm as a means of assessing programming languages:

ask for 11 numbers to be read into a sequence S
reverse sequence S
for each item in sequence S
    call a function to do an operation
    if result overflows
        alert user
    else
        print result

Though it is trivial, the algorithm involves arrays, indexing, mathematical functions, subroutines, I/O, conditionals and iteration, and thus exposes many basic operations of a programming language.

Your task is to write a program that implements the Trabb Pardo Knuth algorithm. 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

One of the sites that I visit regularly is Reddit, and one of my favorite forums there is learnprogramming, which is often a source of ideas for the exercises that I write here. A recent question on learnprogramming came from a poet who wanted a rhyming dictionary. The poet says the dictionary must be the OED (won’t accept the CMU dictionary), isn’t a programmer but has a little bit of experience with HTML but expects to be able to write a rhyming dictionary program in a couple of days, doesn’t know that Java and JavaScript are two different languages, has already decided to use Python or Ruby, expects to be able to copy all the pronunciations from the OED without license, and seems to not have a clue what he really wants (“Basically I want to have multiple inputs (somewhere around a dozen) in different categories that when pooled together can give you what you’re looking for.” — whatever that means). The poet also has a foul mouth. Still, building a rhyming dictionary is a good exercise, and we can have some fun with it.

First we need a pronunciation dictionary. CMU has one, which we will use even though the poet found it “too choppy.” You’ll want the c06d.gz file, which after a brief commentary provides one word per line in the form PROGRAMMING P R OW1 G R AE2 M IH0 NG. The dictionary uses 39 phonemes, 15 vowels and 24 consonants, with three possible stresses for each vowel, indicated by a trailing number, 1 for primary stress, 2 for secondary stress, and 0 for unstressed; thus, there are 69 unique pronunciation symbols. We’ll say that two words rhyme if their final vowel (including stress) and any trailing consonants are identical.

Your task is to write a function that determines if two words rhyme and a function that takes one word and returns all the words that rhyme with it. 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 3

We studied one-dimensional cellular automata in a previous exercise. In today’s exercise, we will implement the famous two-dimensional cellular automaton by the British mathematician John Horton Conway, the Game of Life. Life was introduced by Martin Gardner in the October 1970 issue of Scientific American; I can remember coming home from the library and tracing a glider as it moved across my checkerboard.

The automaton exists on an infinite two-dimensional grid of cells, each either alive or dead. Each cell has a neighborhood of the eight cells horizontally, vertically or diagonally adjacent to it. A cell that is alive in one generation dies if it has less than two live neighbors or more than three live neighbors, otherwise is survives to the next generation; a cell that is dead becomes alive at the next generation if it has exactly three living neighbors. All births and deaths occur simultaneously from one generation to the next.

Mathematicians have shown that these simple rules evoke immense variety, and have built general-purpose computing structures from particular configurations of living cells. Forty-two years on, there are articles in scholarly journals, doctoral dissertations, and jillions of web sites that serve Life enthusiasts.

Your task is to write a program that computes and displays the history of a Life population. 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

Pairs of prime numbers that differ by two are known as twin primes: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73), …. Sometimes the list is given by the lowest number in the pair (A001359: 3, 5, 11, 17, 29, 41, 59, 71, …), sometimes by the highest number in the pair (A006512: 5, 7, 13, 19, 31, 43, 61, 73, …), sometimes by the number in between (A014574: 4, 6, 12, 18, 30, 42, 60, 72, …), and sometimes just as a list of primes (A001097: 3, 5, 7, 11, 13, 17, 19, 29, 31, 41, 43, 59, 61, 71, 73, …). All twin primes have the form 6k±1.

It is simple and fast to compute the twin primes less than n by a variant of the Sieve of Eratosthenes. The sieving primes are the primes less than the square root of n, excluding 2 and 3 which are not of the form 6k±1. In the first step, the primes of the form 6k−1 are sieved; first make a bitarray for the numbers 5, 11, 17, 23, 29, …, then, for each sieving prime p, find the smallest multiple of the prime in the list, strike it off the list, and strike each pth number off the list as well. In the second step, the primes of the form 6k+1 are sieved; first make a bitarray for the numbers 7, 13, 19, 25, 31, …, then, for each sieving prime p, find the smallest multiple of the prime in the list, strike it off the list, and strike each pth number off the list as well. In the third step, sweep through the pair of bitarrays and collect twin primes for each remaining pair of corresponding bitarray elements.

The smallest multiple of a prime p of the form 6k−1 is the modular inverse of 6 mod p; the smallest multiple of a prime p of the form 6k+1 is the modular inverse of −6 mod p. Be sure not to strike the prime p. We discussed the modular inverse in a previous exercise.

An alternative method to compute twin primes is to use the normal Sieve of Eratosthenes to compute the primes less than n, then sweep through the list comparing each prime to its successor. But the algorithm given above is faster, about twice as fast, because the two bitarrays are shorter than the single bitarray of the normal Sieve of Eratosthenes.

Your task is to write a function that finds the twin primes less than a given input n. 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 studied McNugget Numbers in a previous exercise. You may recall that McDonald’s Restaurants sell Chicken McNuggets in meal sizes of 6, 9 or 20 nuggets, and a McNugget Number is a number that can be formed by some combination of 6, 9 and 20. For instance, 100 is a McNugget Number because 100 = 5 ·20.

The previous exercise asked you to find the list of numbers that cannot be formed by some combination of 6, 9 and 20; those numbers, which are the Non-McNugget Numbers, are 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 and 43. Today’s exercise asks you to count the ways in which a McNugget number can be formed; for instance, you can form the number 100 in 5 different ways: 100 = 0 · 6 + 0 · 9 + 5 · 20 = 1 · 6 + 6 · 9 + 2 · 20 = 4 · 6 + 4 · 9 + 2 · 20 = 7 · 6 + 2 · 9 + 2 · 20 = 10 · 6 + 0 · 9 + 2 · 20.

Your task is to write a program that calculates the number of ways a number can be expressed as a McNugget Number, and to use your program to calculate the number of ways to express one million as a McNugget Number. 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 we had one of the simulations from A. K. Dewdney’s Five Easy Pieces, and today we have another. You’ve all seen a Galton board, invented by the Victorian statistician Sir Francis Galton; a series of pegs is arranged in diagonal columns at the top, a marble is dropped into the center of the top row, and it falls through the rows, moving left or right at each peg, until it drops into a bin at the bottom of the board, one bin under each gap in the final row of pegs. Each individual marble can go left or right at each peg with equal probability, but the overall effect after several marbles are dropped is to form a bell-shaped curve in the bins at the bottom.

Your task is to write a program to simulate a Galton board, showing the bell-shaped distribution in a histogram. 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’s election year in the United States, and in today’s exercise we have an election simulation. It comes to us from chapter “Five Easy Pieces” in A. K. Dewdney’s book The Armchair Universe, which is a compilation of some of Dewdney’s “Computer Recreations” columns in Scientific American. Dewdney calls his simulation voters.

The simulation is simple. A rectangular x-by-y grid contains cells that represent voters. Each cell has eight horizontally, vertically or diagonally adjacent neighbors, with the grid wrapping around on all sides to form a torus. Each cell can contain one of two values, which we call 0 and 1, not necessarily in order, instead of Democrat or Republican. At each time step, one cell, chosen at random, changes its allegiance to that of one of its eight neighbors, chosen at random; in some cases that random choice leaves the allegiance unchanged.

The current state of the simulation is displayed on the screen, with easily distinguishable symbols for 0 and 1. The simulation continues until it reaches a steady state — totalitarianism — in which all cells have the same value. It is mesmerizing to watch the screen as voting blocks form and changing allegiances sweep across the grid.

Your task is to write a program that displays the simulation described above. 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 a fun little problem from number theory today. Take a minute and try to find x and y so that x² + 4 y² = 1733. If that’s too easy for you, try x² + 58 y² = 3031201.

Equations of the form x² + d y² = p, with p prime, can be solved by an algorithm developed by Giuseppe Cornacchia in 1908 (actually, a fellow named Smith developed the same algorithm in 1885, but his work seems to be forgotten). Here’s the algorithm, which assumes that p is prime and 0 < d < p:

1. If the jacobi symbol (−d/p) is negative, there is no solution; stop.

2. Compute x such that x² ≡ −d (mod p). If there are two such values, choose the larger. Then set a ← p and b ← x.

3. While b² > p, set a ← b and b = a mod b. The two assignments are done simultaneously, so the values on the right-hand sides of the two assignments are the old values of the variables. (You may notice that this is Euclid’s algorithm.)

4. After the loop of Step 3 is complete, if d does not evenly divide p − b² or if c = (p − b²) / d is not a perfect square, there is no solution; stop. Otherwise, x = b and y = √c.

We can use Cornacchia’s algorithm with d = 1 to verify Fermat’s Christmas Theorem (because it was announced in a letter to Marin Mersenne on December 25, 1640) that all primes of the form 4k+1 can be represented as the sum of two squares; as usual, Fermat didn’t give the proof, which was finally published by Leonhard Euler in a letter to Goldbach in 1749 after seven years of effort.

Your task is to implement Cornacchia’s algorithm and use it to demonstrate that all primes of the form 4k+1 and less than 1000 can be written as the sum of two squares. 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