## Cracker Barrel

### August 19, 2014

While I was out of town last week, I ate dinner one evening at Cracker Barrel, which provides a triangle puzzle at each table so you can amuse yourself while you are waiting for your food. When my daughter challenged me to solve the problem, I failed, but I promised her that I would write a program to solve it.

As shown in the picture at right, the puzzle is a triangle with 15 holes and 14 pegs; one hole is initially vacant. The game is played by making 13 jumps; each jump removes one peg from the triangle, so at the end of 13 jumps there is one peg remaining. A jump takes a peg from a starting hole, over an occupied hole, to an empty finishing hole, removing the intermediate peg.

Your task is to write a program that solves the Cracker Barrel puzzle; find all possible solutions that start with a corner hole vacant and end with the remaining peg in the original vacant corner. 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.

## Big Modular Exponentiation

### August 8, 2014

Today’s exercise is a frequent source of questions at places like Stack Overflow and /r/learnprogramming; it must come from one of the competitive programming sites like SPOJ or UVA. The most common statement of the problem is something like this:

You are given two positive integers

PandQ, either of which can be quite large, up to a million digits. ComputeP, that is,^{Q}Praised to theQpower. For your convenience, give the result modulo 10^{9}+ 7. For instance, withP= 34534985349875439875439875349875 andQ= 93475349759384754395743975349573495, the expected result is 735851262.

The phrase “for your convenience” is a giveaway that the modulo computation is a trick; that kind of contest site never does anything for your convenience. In fact, due to a corollary of Fermat’s little theorem, *P ^{Q}* (mod

*m*) ≡

*p*(mod

^{q}*m*) where

*p*=

*P*(mod

*m*) and

*q*=

*Q*(mod

*m*− 1). That makes it easy. Compute

*p*and

*q*. Both will be less than 2

^{32}, so we can use the Montgomery multiplication algorithm of a previous exercise to make the computation.

Your task is to write a program to perform the big modular exponentiations 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.

## Minimal Palindromic Base

### August 5, 2014

We have a simple little problem today: Given an integer *n* > 2, find the minimum *b* > 1 for which *n* base *b* is a palindrome. For instance, *n* = 15 = 1111_{2} = 120_{3} = 33_{4} = 30_{5} = 23_{6} = 21_{7} = 17_{8} = 16_{9} = 15_{10} = 14_{11} = 13_{12} = 12_{13} = 11_{14}; of those, bases 2, 4 and 14 form palindromes, and the least of those is 2, so the correct answer is 2.

Your task is to write a program that calculates the smallest base for which a number *n* is a palindrome. 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.

## K’th Largest Item

### August 1, 2014

Today’s exercise is a common interview question, and also interesting in its own right:

Find the

kth largest integer in a file ofnintegers, wherenis large (defined as too large to fit into memory all at once) andkis small (defined as small enough to all fit in memory).

Your task is to write the program 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.

## Montgomery Multiplication

### July 29, 2014

[ Does anybody know the proper method for writing a-bar and b-bar in plain HTML? The LaTeX symbols are \={a} and \={b}, but WordPress renders LaTeX poorly, and I prefer plain HTML. FIXED! Thanks to Jussi, who suggests writing a amp hash x304 semicolon and b amp hash x304 semicolon. ]

Montgomery multiplication is a method of computing *ab* mod *m* for positive integers *a*, *b* and *m*, designed for situations where there are many multiplications to be performed mod *m* with a small number of multipliers; in particular, it is valuable for computing *x ^{y}* mod

*m*for large

*y*. Montgomery multiplication was invented by Peter Montgomery in a 1985 article. Our exercise today will implement modular multiplication and exponentiation using Montgomery’s method.

The basic idea of Montgomery multiplication is to eliminate the division inherent in the modulo operation by translating the modulus *m* to a larger modulus *r*, with gcd(*r*, *m*) = 1, where *r* is a power of 2; thus, the division is rendered as a bit mask. Since *r* is a power of 2, the modulus *m* must be odd to satisfy the gcd requirement; we also require the two multipliers *a* and *b* be less than *m*. Then the Montgomery algorithm is as follows:

- Find two integers
*r*^{−1}and*m*′ such that*r r*^{−1}*m**m*′ = 1 by the extended Euclidean algorithm. In particular, the algorithm used is a binary version of the algorithm that performs no divisions. - Translate the multipliers to “Montgomery space” by multiplying them by
*r*(using left shifts) and reducing the product modulo*m*. Thus, ā =*a r*mod*m*and b̄ =*b r*mod*m*. These operations are expensive, but they are performed only once for each multiplier in a chain of multiplications. - Perform the Montgomery multiplication: calculate
*u*=*a b r*mod*m*by the sequence of operations

*t*= ā * b̄

*u*= (*t*+ (*t***m*′ mod*r*) **m*) /*r*

if (*u*≥*m*) then subtract*m*from*u*The only division is a right-shift; the final result uses subtraction instead of division because it is known that the product is less than 2

*m*. - Translate the result back from Montgomery space to an ordinary integer by
*ab*=*u r*^{−1}mod*m*.

Montgomery exponentiation is similar. To compute *x ^{y}* mod

*m*, select

*r*, compute

*r*

^{−1}and

*m*′, translate

*x*to Montgomery space, use the square-and-multiply method with Montgomery multiplications to perform the exponentiation starting from 1 in Montgomery space, then translate the result back from Montgomery space. This is much faster than the calculation without Montgomery multiplication, because the cost of initializing the Montgomery space is amortized over several multiplications, each of which avoids the inherent division of the modulo operator.

Your task is to write functions that perform Montgomery multiplication and exponentiation. 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.

## Number Words

### July 25, 2014

Today’s exercise is an interview question from Career Cup. When I first saw the exercise, I thought it would be easy, but I had trouble writing a solution, so maybe it will a good exercise for all you readers, as well:

Given a positive integer, return all the ways that the integer can be represented by letters using the mapping 1 -> A, 2 -> B, …, 26 -> Z. For instance, the number 1234 can be represented by the words ABCD, AWD and LCD.

Your task is to write the program to generate words from 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.

## Maximum Sum Path

### July 22, 2014

Sometimes here at Programming Praxis we publish exercises taken from homework in computer science classes, sometimes we publish exercises that are based on or related to problems at Project Euler, and sometimes we publish exercises that based on common technical interview questions. Today we hit the trifecta: a common interview question that is frequently assigned as homework in computer science classes and that also appears at Project Euler (twice!):

Given a binary tree with integers stored in its nodes, find the maximum sum of any path from root to leaf.

For instance, in the binary tree represented by the triangle shown below, the maximum sum path goes from the 3 at the root, to its child 7, to its grandchild 4, to the leaf node 9, a sum of 23. Since there is no other path with a greater sum, the maximum sum is 23:

` 3`

7 4

2 4 6

8 5 9 3

Your task is to write a program to compute the maximum sum path through a binary tree; also write a variant of the program that returns the path. 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.

## How Fermat Factored Integers

### July 18, 2014

Living in the age of computers, I’ve always been fascinated by how much arithmetic it was possible to do before the advent of computers. The Egyptians knew the peasant method of multiplication when the built the pyramids. Archimedes knew the value of pi two centuries before Christ, with an approximation we still use today. Heron had an algorithm for calculating square roots two thousand years ago. And so on.

By the time of Fermat, Euler and Gauss, arithmetic was done with simple algorithms, rules of thumb, and large tables. Sadly, the tables were frequently wrong; Charles Babbage invented his Difference Engine for the purpose of automatically constructing accurate tables.

We studied Fermat’s algorithm for factoring integers in a previous exercise:

`function fermat(n)`

x := floor(sqrt(n))

r := x * x - n

t := 2 * x + 1

while r is not a square

r := r + t

t := t + 2

x := (t - 1) / 2

y := sqrt(r)

return x - y, x + y

But how did Fermat actually work his algorithm? In addition to the basic arithmetic, he used some simple rules for identifying squares and a table of the squares of numbers similar to that on the next page, with the largest square at least as large as *n*.

Let’s consider the factorization of *n* = 13290059 as an example. First, Fermat removed small factors by trial division, say for factors less than 30 or 50. Then, Fermat looked up *n* in the table. If *n* appeared in the body of the table, then it is a perfect square, and the square root is its factor. But in the general case, Fermat finds *x* as the square root of the next smaller entry in the table. For 13290059, *x* = 3645, because 3645^{2} < 13290059 < 3646^{2}. Then *t* = 7291 and *r* = -4034, which is not a perfect square (because it’s negative).

Now the iteration begins. Fermat calculated *r* and *t* in 45 steps as follows, first *r*, then *t* below it, then a sum line, then the sum *r* = *r* + *t*, then *t* incremented by 2 from the previous *t*, then a sum line, then a new sum *r*, at each step checking if *r* is a square:

0: r = -4034 = 3645 * 3645 - 13290059 t = 7291 = 2 * 3645 + 1 ------ 1: r = 3257 ends in 7; not a square t = 7293 = 7291 + 2 ------ 2: r = 10550 ends in 50; not a square t = 7295 = 7293 + 2 ------ 3: r = 17845 ends in 45; not a square ... 44: r = 318662 ends in 2; not a square t = 7381 = 7379 + 2 ------ 45: r = 326041 in table: 571 * 571

At that point, Fermat could calculate the factors of *n*: *x* = (7381 – 1) / 2 = 3690, *y* = 571, and the factors of *n* are *x* − *y* = 3690 − 571 = 3119 and *x* + *y* = 3690 + 571 = 4261.

The key to Fermat’s calculation was identifying the case where *r* is a square. Fermat used three rules: First, the last two digits of the number had to be 00, *e*1, *e*4, 25, *o*6 or *e*9, where *e* is any even digit and *o* is any odd digit. Second, the digital root of the number had to be 1, 4, 7 or 9: sum the digits of *n*; if the result is less than 10, then return the sum of the digits, otherwise return the digital root of the sum of the digits. In practice, this goes much more quickly than it appears by “casting out nines” wherever they appear in the digits of *n* or the result. Third, if he had not already determined that the number was not a square, he looked it up in his table of squares. The whole calculation goes much more quickly than I can describe it here.

And that’s how Fermat factored integers. Of course, sometimes he failed, when it took too many iterations to find a square, or when his table of squares was too small, or when he made an error in the arithmetic. Fortunately, it was easy enough for him to confirm that any factorization he found was correct by multiplying the factors.

Your task is to write a program that factors integers the same way Fermat factored integers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the program in the comments below.

## How Many Distinct Products In A Times Table?

### July 15, 2014

We all learned our times tables in elementary school. For instance, here is the standard 9 by 9 times table:

`1 2 3 4 5 6 7 8 9`

2 4 6 8 10 12 14 16 18

3 6 9 12 15 18 21 24 27

4 8 12 16 20 24 28 32 36

5 10 15 20 25 30 35 40 45

6 12 18 24 30 36 42 48 54

7 14 21 28 35 42 49 56 63

8 16 24 32 40 48 56 64 72

9 18 27 36 45 54 63 72 81

That table has 36 distinct products: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 54, 56, 63, 64, 72 and 81.

Your task is to write a program that computes the number of distinct products in an *n* by *n* times table. There is an obvious O(*n*^{2}) algorithm; can you do better? 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.

## FSM Generator

### July 11, 2014

A few weeks ago we had an exercise that solved the problem of removing singleton occurrences of a given character from a string while leaving multiple occurrences of the given character intact. Our solution used a finite state machine that iterated over the input string writing output as it went.

The finite state machine used in that solution was hand-crafted to solve the given problem. But it is possible to write a program that takes a definition of a finite state machine and creates a function that takes an input string and applies the finite state machine to it. Such a program isn’t hard to create and provides a useful utility for small parsing problems.

Your task is to write a program that generates a finite state machine from a simple description; the format and capabilities of the machine are up to you, but it should be at least powerful enough to solve the “remove singleton” 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.