Programming Praxis

One of the first functions taught to programmers who are just learning about recursion is the function to compute the fibonacci numbers. The naive function takes exponential time, as each recursive call must compute the values of smaller fibonacci numbers, so programmers are next taught how to remove the recursion by explicitly storing state information, giving a linear-time iterative algorithm. The upshot is that programming students are left with the impression that recursion is bad and iteration is good.

It is actually possible to improve the performance with a logarithmic-time algorithm. Consider the matrices

Each time the matrix is multiplied by itself, the number in the lower left-hand corner is the next fibonacci number; for instance, F₄=3 (F₀=0 is a special case). Of course, powering can be done using a binary square-and-multiply algorithm, as in the ipow and expm functions of the Standard Prelude, giving a logarithmic algorithm for computing the nth fibonacci number.

Your task is to write the three fibonacci functions — exponential, linear, and logarithmic — 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

Back in the 1970s, David Ahl wrote a new game program each month for Creative Computing magazine. Those were the days of all-caps teletypes (if you were rich you could get a new-fangled “glass teletype”) and punched paper tapes (it was fun to play with the confetti they made). MS-BASIC permitted twenty-six single-letter variable names; later they also allowed a single letter followed by a single digit. There were no user-defined functions and no recursion. GOTO was common, resulting in a phenomenon called “spaghetti code.” There was good news, however: it was acceptable programming practice to GOTO the middle of a FOR loop and run the code there, as long as you jumped back out of the loop before the corresponding NEXT — try to do that in your favorite functional language!

One of Ahl’s most memorable games was Hamurabi, in which the player took the role of the administrator of the ancient city of Sumeria, managing the grain and land resources of the city and trying to keep the residents from starvation. It is typical of the genre, with simple numeric input and scrolling text output. Here is a description and sample game, and the original BASIC source code is reproduced on the next page. By my count, there are fourteen lines that are unreachable except by an IF…THEN, GOSUB or GOTO, forty-three lines that redirect control flow away from the line below, and four instances (line 555 to 215, bypassing line 210, 453 and 479 to 440, bypassing 430, 441 to 511, bypassing 510, and 880 and 885 to 565, bypassing 560) of jumping into the middle of a block of code; that’s a fine bowl of spaghetti, considering the entire program is only 120 lines. Variable P represents the current population, S is the number of bushels in stores, and A is the number of acres of farmland owned by the city, but other variables are used inconsistently — for instance D sometimes represents the number of deaths in the current year, but other times it represents the current input value, and other times Q is used to represent the current input value.

Your task is to reimplement HAMURABI.BAS in a more modern computer language. Don’t peek at the solution unless you want to deprive yourself of the sheer joy of working out the spaghetti code and figuring out what the variables really stand for. 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 4

Over at SteamCode, Scott LaBounty suggests that writing a program to compute the happy numbers less than n makes a good interview question. According to Wikipedia:

A happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers (or sad numbers).

For example, 7 is a happy number, as 7²=49, 4²+9²=16+81=97, 9²+7²=81+49=130, 1²+3²+0²=1+9+0=10, and 1²+0²=1+0=1. But 17 is not a happy number, as 1²+7²=1+49=50, 5²+0²=25+0=25, 2²+5²=4+25=29, 2²+9²=4+81=85, 8²+5²=64+25=89, 8²+9²=64+81=145, 1²+4²+5²=1+16+25=42, 4²+2²=16+4=20, 2²+0²=4+0=4, 4²=16, 1²+6²=1+36=37, 3²+7²=9+49=58, and 5²+8²=25+64=89, which forms a loop.

Your task is to write a function to identify the happy numbers less than a given limit; you should work at the level of a programming interview, taking no more than about fifteen minutes, and giving a short explanation of your work to the interviewer. 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 today’s exercise we continue the examination of matrix operations that we began previously. Our goal is to be able to solve a system of equations; along the way we will see two methods for decomposing matrices.

We begin with some terminology. All the matrices we will be looking at are square, meaning that they have the same number of rows and columns. A lower-triangular matrix L has all entries L_ij = 0 for i < j; thus, all entries above the main northwest-to-southeast diagonal are zero. An upper-triangular matrix U has all entries U_ij = 0 for i > j; thus, all entries below the main northwest-to-southeast diagonal are zero. A lower- or upper-triangular matrix is unit lower- or upper-triangular if all the entries along the main diagonal are 1. A permutation matrix P has exactly one 1 in each row and column and 0 elsewhere; it is called a permutation matrix because multiplying a vector X by a permutation matrix has the effect of permuting the elements of X. The identity matrix I has 1 in each entry along the main diagonal and 0 elsewhere. A matrix M is singular if it has no inverse, that is, there is no matrix M^-1 such that M M^-1 = I.

An LU decomposition of a matrix A finds two matrices L, which is unit lower-triangular, and U, which is upper-triangular, such that A = L U. The algorithm is called Gaussian elimination, and works from top to bottom. First, multiples of the first equation are subtracted from the other equations so that the first variable is removed from those equations. Then multiples of the second equation are subtracted from the remaining equations so that the second variable is removed from those equations. Then the third equation, and the fourth, and so on, until all the equations have been processed and the matrix is in upper-triangular form. Here is an example of the LU decomposition of matrix A into its factors L × U:

There are two problems with LU decomposition: First, the algorithm leads to a divide-by-zero error on singular matrices. Second, it is prone to numerical instability for small divisors. The solution is to rearrange, or permute, the equations so that the pivot element is always the largest remaining element, greatly reducing the likelihood of numerical instability.

An improved decomposition is the LUP decomposition, which finds for an input matrix A three matrices L, U, and a permutation matrix P such that P A = L U. Rather than actually moving equations, the permutation matrix records the rearrangements. For example, here is the LUP decomposition of the matrix A given by P × A = L × U:

Given the LUP decomposition, it is simple to solve a system of linear equations. Forward substitution solves the lower-triangular system by calculating the first variable, which is part of an equation with one unknown, then substitutes that into the second equation, reducing it from two unknowns to one unknown, and so on. Then back substitution runs backward, calculating the final values of the variables in the original matrix. Here’s an example, where we wish to solve for the vector X given A X = B:

The LUP decomposition P A = L U is

,

the result of forward substitution L Y = P B is

, giving ,

and the result of the back substitution U X = Y is

, giving ,

which is the solution.

Your task is to write functions that perform LU-decomposition and LUP-decomposition and solve systems of linear equations. 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 two previous exercises, we looked at the programs behind the tables of contents pages in chronological order and permuted by keywords. In today’s exercise, we complete this trio of exercises by writing the program that creates the themed table of contents page. Like the others, it is based on the praxis.info file, which was described previously. We won’t give the output format here, except to say that it is similar to the others, but with an additional header section for the list of themes.

Your task is to write a program that extracts needed data from the praxis.info file and writes the themed table of contents. 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

Word cube is game in which players form words from the nine letters in a cube. Words must have four or more letters and must use the central letter from the cube; at least one word will use all nine letters in the cube. The player who forms the most words wins. Many newspapers publish a word cube on their puzzle page, and Stealthcopter publishes a word cube on line daily. Wikipedia describes word cubes under the caption “word polygon.” There are twelve words formed from the word cube at right: bonnie, bunion, coin, concubine, conic, cubic, ennui, icon, nice, nine, nuncio, and union.

Your task is to write a program that finds all matching words for a given word cube. 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 examined in a previous exercise a program that extracts a chronological listing of the exercises on the Programming Praxis website from the praxis.info file. We also discussed in a previous exercise a program that creates a permuted index. In today’s exercise we will combine those two programs into the program that is used to create the Permuted Table of Contents page at Programming Praxis.

The format of the praxis.info file was given in a previous exercise. The output from today’s program should look like this:

<table cellpadding="10">
<tr><td>129</td><td>20 Apr 2010</td><td align="right">&nbsp;</td><td>145 Puzzle: Build and evaluate expressions using the digits one through nine and the simple arithmetic operators</td><td><a href="/2010/04/20/145-puzzle/">exercise</a> <a href="/2010/04/20/145-puzzle/2/">solution</a> <a href="http://programmingpraxis.codepad.org/SzbrJbjx">codepad</a></td></tr>
<tr><td>51</td><td>17 Jul 2009</td><td align="right">International Mathematical Olympiad: Three exercises from</td><td>1960s math competitions</td><td><a href="/2009/07/17/international-mathematical-olympiad/">exercise</a> <a href="/2009/07/17/international-mathematical-olympiad/2/">solution</a> <a href="http://programmingpraxis.codepad.org/JRGmt2wZ">codepad</a></td></tr>
...
</table>

Your task is to write a program that reads praxis.info and produces the permuted table of contents. 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 1918, John Byrne invented a two-disk cryptographic machine, which he called a chaocipher; he drew up blueprints, but was unsuccessful in his efforts to sell the machine to the US Signal Corps and Navy. He left several challenge messages in his 1954 autobiography, but no one successfully deciphered the messages. Recently, following the death of Byrne’s son, the son’s widow donated Byrne’s complete archives, including a mock-up of the machine, to the National Cryptologic Museum at Fort Meade, Maryland. Last Friday, Moshe Rubin published the first public description of the chaocipher algorithm.

The algorithm uses two key sequences, one for cipher-text and one for plain-text. Encryption and decryption look up the desired character on one sequence and report the corresponding character on the other sequence, working from plain-text to cipher-text for encryption and from cipher-text to plain-text for decryption.

After each character, both sequences are permuted, each by a different method. Thus, the chaocipher is similar to an autokey cipher, because the key is modified according to the plain-text.

The left disk, which normally represents the cipher-text, is permuted in two steps. First, the entire alphabet is shifted left as far as cipher-text of the current character (so the current cipher-text character becomes the first character in the sequence), with the shifted-off portion of the sequence reattached at the end. Second, the second through fourteenth characters are shifted left one character, and cycled; the third character becomes the second, the fourth character becomes the third, and so on, until the fourteenth character becomes the thirteenth and the second character becomes the fourteenth. For instance, given the sequence HXUCZVAMDSLKPEFJRIGTWOBNYQ and the current character P, the entire sequence is shifted to bring P to the front, giving PEFJRIGTWOBNYQHXUCZVAMDSLK, then the second through fourteenth characters are shifted to move E after Q, giving PFJRIGTWOBNYQEHXUCZVAMDSLK. Byrne invented the terms zenith and nadir to represent the first and fourteenth characters, Rubin refers to zenith and zenith+13, but we’ll just call them by their ordinal positions in the sequence.

The right disk, which normally represents the plain-text, is permuted in three steps. First, the entire alphabet is shifted left as far as the plain-text of the current character (so the current plain-text character becomes the first character in the sequence), with the shifted-off portion of the sequence reattached at the end. Second, the first character is shifted to the end (so the current plain-text character becomes the last character in the sequence). Third, the third through fourteenth characters are shifted left one character, and cycled, similar to the left disk except for the different starting position. For instance, given the sequence PTLNBQDEOYSFAVZKGJRIHWXUMC and the current character A, the final sequence is VZGJRIHWXUMCPKTLNBQDEOYSFA.

Thus, the encryption of WELLDONEISBETTERTHANWELLSAID, given the above cipher-text and plain-text sequences, is OAHQHCNYNXTSZJRRHJBYHQKSOUJY.

Your task is to write functions that perform encryption and decryption according to the algorithm given 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

You may have noticed that the Contents page changed recently. Previously the Contents page listed all the exercises in chronological order. Now, there are four listings of the exercises, in chronological order, reverse chronological order, permuted by the words in the title and summary, and organized manually by themes.

The four listings all derive from a single source. The file praxis.info consists of records separated by blank lines, fields on a single line with field name followed by a tab character followed by the data element. Here is an excerpt, which shows the header at the beginning of the file followed by the first two records:

praxis.info

number  2
file    sieve-of-eratosthenes
pubmon  2
pubday  19
pubyear 2009
title   Sieve of Eratosthenes
blurb   A Scheme implementation of an ancient algorithm
exer    1
soln    2
codepad wI14BJ8Q
theme   Prime Numbers

Four programs manipulate the data from the praxis.info file to produce the four listings. The output has elements of html, but WordPress adds the surrounding context; here is the corresponding excerpt from the listing in chronological order:

<table cellpadding="10">

</table>

Your task is to write programs that read praxis.info and write the two listing files for exercises in chronological order and reverse chronological order. 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