Programming Praxis

A classic puzzle of recreational mathematics is the cryptarithm, where the solver is given a math problem in words and must systematically substitute digits for the letters of the puzzle to form a valid calculation. For instance, the famous cryptarithm SEND + MORE = MONEY is solved as M=1, Y=2, E=5, N=6, D=7, R=8, S=9 and O=0, giving 9567 + 1085 = 10652. Cryptarithms were invented by H. E. Dudeney in the July 1924 edition of Strand Magazine.

We are going to give four solutions to this puzzle, two slow ones today and two fast ones in the next exercise. Our first solution is simple brute force, using nested loops to generate all possible solutions and testing each to see if it forms a valid calculation. Our second solution is backtracking, which is similar to the generate-and-test solution.

Your task is to write the two solutions to the SEND + MORE = MONEY problem 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

Today’s exercise continues our occasional series of exercises based on interview questions:

Design a data structure that provides push and pop operations, like a stack, plus a third operation that finds the minimum element. All three operations must perform in constant time. You may assume that all elements are distinct.

Your task is to write the three indicated functions. 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 folks at /r/dailyprogrammer publish programming exercises on a regular basis; you might want to have a look. They frequently steal my exercises, so today I will steal one of theirs.

Any positive integer can be represented as the sum of one or more non-consecutive fibonacci numbers. For instance, 100 = 2 + 8 + 89. Note that 100 can also be written using fibonacci sums as 89 + 8 + 2 + 1 or 55 + 34 + 8 + 3, but those use consecutive fibonacci numbers (2 + 1 for the first representation, 55 + 34 for the second). Belgian mathematician Edouard Zeckendorf proved that such a representation is unique.

Zeckendorf representations can easily be found by a greedy strategy. Start with the largest fibonacci number less than the target number. Then choose the largest fibonacci number less than the remainder after subtracting the first number. And so on, stopping when the remainder is a fibonacci number itself.

Your task is to write a function that finds the Zeckendorf representation of a positive integer. 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 most fundamental operations in computing is to evaluate an arithmetic expression, observing the precedences and associativities of the operators. For instance, given the expression 3+4*5, the multiplication is performed first, then the addition, giving a result of 23. Parentheses may change the order of evaluation, so that (3+4)*5 is 35. Today’s task is to write a program that takes as input a string containing an arithmetic expression and returns as output the result of evaluating that expression.

The usual approach to this task is to write a parser that identifies each element of the expression, evaluates them, and combines them into a solution. The parser is driven by a grammar that enumerates the various elements; the usual grammar for arithmetic expressions is:

expr -> term | expr + term | expr - term
term -> factor | term * factor | term / factor
factor -> number | ( expr )

Here -> and | are metasymbols of the grammar, +, -, *, /, ( and ) are operator literals, and expr, term, factor and number are operands; it’s not shown above, but a number is and integer consisting of either 0 or a sequence of digits not starting with 0, with an optional leading - sign. Blanks anywhere in the expression, even between the digits of a number, are ignored.

The evaluator consists of a set of mutually recursive functions that each recognize one metastatement of the grammar, plus a driver that accepts an input string and returns the result, all organized as dictated by the grammar.

As an example, consider the input string (3+4)*5. The driver passes the input to a function that recognizes expressions. Since the metastatement for expressions expects a term, that function immediately passes the input to a function that recognizes terms. Then, since the metastatement for terms expects a factor, that function immediately passes the input to a function that recognizes factors. That functions recognizes the opening parenthesis and calls the function that recognizes expressions to evaluate what is inside the parenthesis. Again, the expression metastatement looks for a term, and the term metastatement looks for a factor, and the factor metastatement looks for a number, which it finds, so it returns 3 to the term metatstatment, which returns 3 to the expression metastatement. Then the expression metastatement recognizes the + sign and goes next to the 4. The expression metastatement calls the term metastatement, which calls the factor metastatement, which identifies the 4 and passes it back to the term metastatement, which passes it back to the expressions metastatement, which adds it to 3 giving a result of 7. Now the expression metastatement is satisfied because the next input character is not a +, - or expression, so it returns the 7 to the expression that was called within the parentheses of the factor metastatement. The next character is a closing parenthesis, so the factor metastatement is complete, and passes back the 7 to the term metastatement. Now the next character is *, which is recognized by the term metastatement, which passes the remainder of the input string, the 5 character, to the factor metastatement. Now the factor metastatement recognizes the number 5 and returns it to the term metastatement, which multiplies it by 7 producing a result of 35. The result is passed back to the expression metastatement, which recognizes that the expression is complete, so it passes the result 35 back to the driver function, which outputs the result. Whew! Aren’t you glad you have a computer to do all of that work for you?

Your task is to write a function that evaluates an infix arithmetic expression. 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 algorithm that raster graphics devices use to draw straight lines was invented by Jack Breshenham of IBM in 1962. The algorithm is favored because it uses only simple arithmetic, addition and subtraction and multiplication by 2, making it suitable both for software (graphics libraries, or languages such as PostScript) and for hardware (graphics cards, video displays, plotters).

Assume coordinates with point (0,0) at the top left, increasing down and right, where the first coordinate is the column and the second coordinate is the row, that all pixels have integer coordinates, and the task is to draw a line from (x₀, y₀) to (x₁, y₁). Assume for the moment a line that slopes downward from left to right (so both x and y are increasing) at less than a 45 degree angle (so y increases faster than x). For each x from x₀ to x₁, the algorithm chooses the y between y₀ and y₁ that is closest to the ideal y for the corresponding x. But instead of computing fractional y, the algorithm keeps track of the error between the current value of y and its idealized value. At each increase in x, the error is increased by the slope of the line, and if the error exceeds half a pixel, y increases by 1 and the error decreases by 1. Similar calculations can be made for other orientations of the line.

Your task is to write a function that implements Breshenham’s line-drawing 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

[ Today’s guest author, Sam Kennedy, is a hobbyist programmer just finishing his A-levels in Newcastle, England. ]

Genetic programming is a branch of artificial intelligence in which programmable machines are evolved to perform a specific task; among other tasks, genetic programming is used in the design of electrical circuits, development of chemical reactions, and solving instances of the travelling salesman problem. In today’s exercise we will look at artificial organisms called flibs (“finite living blobs”) invented by A. K Dewdney in his book The Armchair Universe (which we’ve seen in two previous exercises) which learn to recognize and predict the elements of a sequence.

The DNA of a flib is a finite state machine like that shown above right; the sample machine has three states A, B and C, and two input/output symbols 0 and 1, and can be written in its alternate form 1B1C0C0B1A0A, which we call a chromosome. A gene is a symbol in the chromosome: A, B, C, 0, or 1. An allele is a gene at a particular locus: The allele 0 at locus 7 of chromosome 1B1C0C0B1A0A controls the flib’s output symbol when it is in state B and receives an input symbol of 1. The task performed by a flib is to recognize and predict a sequence of input/output states; for instance, the sample flib responds to the input sequence 0111000010110 with the output sequence 100001100100. By shifting the output bits one place to the right, we see only 6 of the 12 predictions are correct, a score of 50% which is no better than random chance.

The purpose of genetic programming is to evolve a flib that perfectly predicts a random sequence. For instance, the sequence 010011010011010011… (an infinite sequence that repeats 010011 forever) can be predicted perfectly by the sample flib that failed on the earlier input sequence; the input sequence must cycle, as no flib can perfectly predict a random (non-repeating) sequence.

Genetic programming uses two operators. Mutation occurs when an allele is changed at random (think of a gene being struck by a cosmic ray); for instance, the chromosome 0D1C0D0B1A0C1B1A might be changed to 0D0C0D0B1A0C1B1A by mutation. Crossover occurs when two chromosomes breed by exchanging portions of their gene sequence. For instance, the chromosomes 0D1C0D0B1A0C1B1A and 1A1B0D1A0C1D1B0C might breed by replacing the fourth through eighth genes of the second chromosome with those of the first chromosome, forming the offspring chromosome 1A1C0D0B0C1D1B0C; the two crossover points are selected at random.

Given all that, the genetic algorithm takes a set of randomly-generated chromosomes (the gene pool), say a dozen of them, and runs the following loop:

1) calculate the score of each flib on identical input sequences
2) find the flibs with the highest and lowest scores
3) replace the lowest-scoring flib with its crossover with the highest-scoring flib, sometimes
4) mutate a single gene on a single flib

Each time a flib beats the current high score, its score and chromosome are printed; the loop continues until a flib reaches a perfect score or your patience is exhausted. In Step 3, the crossover is only performed sometimes, say 3 times out of 10, because if the flibs breed too often the gene pool becomes very similar to that of the highest-scoring flib and loses diversity; on the other hand, if they breed infrequently the simulation will take longer.

Your task is to write a genetic program that breeds perfect flibs. 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 totient of a number n is the count of the numbers less than n that are coprime to it; two numbers are coprime if they have no common factor other than 1. For instance, the totient of 30 is 8, since the numbers 1, 7, 11, 13, 17, 19, 23 and 29 are coprime to 30. The totient function was discovered by Leonhard Euler, and it pops up in all kinds of strange places in number theory; for instance, the totatives of 30 are the spokes on a 2,3,5 factorization wheel. We have seen the totient function in a previous exercise.

If you want to know the totient of a single number m, the best way to find it is to factor n and take the product of 1 less than each factor; for instance, 30 = 2 * 3 * 5, and subtracting 1 from each factor, then multiplying, gives the totient 1 * 2 * 4 = 8. But if you want to find the totients of all the numbers less than a given n, a better approach than factoring each of them is sieving. The idea is simple: Set up an array X from 0 to n, store i in each X_i, then run through the array starting from 0 and whenever X_i = i loop over the multiples of i, multiplying each by i − 1.

Your task is to write a function that computes all the totients less than n by sieving. 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 British mathematician John Horton Conway, famous for inventing the cellular automata Game of Life, also invented an esoteric programming language called fractran in which commands are represented as fractions; for instance, the primegame program generates prime numbers:

17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1

Fractran has two rules:

1. Find the first fraction f in the list for which nf is an integer, output nf, and set n ← nf.

2. Repeat the first rule, but halt if no product nf is integral.

For example, given an initial 2, the sequence of values produced by the above program begins 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, …. (A007542).

The program is called primegame because the exponents of each number in the sequence that is a power of 2 form the list of prime numbers. For instance, the number 4 in the sequence is 2², for which the exponent 2 is the first prime. Fifty steps later the sequence takes the value 8 = 2³. After another 211 steps the sequence takes the value 32 = 2⁵. And so on, generating all of the prime numbers in sequence.

Your task is to write a fractran interpreter and use it to generate prime numbers using primegame. 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 simple word game starts with a word and repeatedly removes a single letter from the word, forming a new word, until there are no letters left. The act of removing a letter is called chopping and the resulting list of words is a chopping chain. For instance:

planet → plane → plan → pan → an → a

Your task is to write a program that takes a word and returns a list of all possible chopping chains that can be formed from the word, given a suitable dictionary. 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