Feynman’s Puzzle
June 12, 2009
Richard Feynman was an American physicist; he worked on the Manhattan Project that developed the atomic bomb, won the Nobel Prize in 1965 for his work in the development of quantum electrodynamics, and famously demonstrated the inelasticity of the rubber o-rings on the space shuttle Challenger using a clamp, a rubber band, and a glass of ice water. Feynman proposed this puzzle:
Your task is to solve Feynman’s Puzzle. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercises in the comments below.
Longest Common Subsequence
June 9, 2009
Finding the longest common subsequence of two sequences is a classic computer science problem with an equally classic solution that dates to the folklore of computing. The longest common subsequence is the longest set of elements that appear in order (not necessarily contiguous) in two sequences; for instance, the longest common subsequence of PROGRAMMING and PRAXIS is PRAI:
P R O G R A M M I N G
| | | |
P R A X I S
The classic solution uses dynamic programming. A matrix is prepared with one sequence in the rows and the other sequence in the columns, giving in each cell the minimum edit distance between the two, where the edit distance is the least number of adds, deletes and changes that can convert one sequence to the other. For instance:
P R O G R A M M I N G
0 0 0 0 0 0 0 0 0 0 0 0
P 0 1 1 1 1 1 1 1 1 1 1 1
R 0 1 2 2 2 2 2 2 2 2 2 2
A 0 1 2 2 2 2 3 3 3 3 3 3
X 0 1 2 2 2 2 3 3 3 3 3 3
I 0 1 2 2 2 2 3 3 3 4 4 4
S 0 1 2 2 2 2 3 3 3 4 4 4
If we represent the rows as Xi and the columns as Yj, the matrix can be filled top-to-bottom, left-to-right using the formula:
{ 0, if i=0 or j=0
{
LCS(i,j) = { LCS(i-1,j-1) + 1, if X(i) = Y(j)
{
{ max(LCS(i-1,j), LCS(i,j-1)), otherwise
Intuitively, the two sequences are scanned in parallel. If the current two cells are identical, the length of the longest common subsequence increases by one; otherwise, there are two possibilities to consider recursively, after deleting the current cell from either one input sequence or the other, and the length of the longest common subsequence is simply the greater of the two possibilities.
Once the matrix of longest common subsequence lengths has been calculated, the longest common subsequence itself can be recovered by noting each point where the length “bumps” to the next lower value along the diagonal, starting at the lower right-hand corner: from 4 to 3 when both sequences are at I, from 3 to 2 when both sequences are at A, from 2 to 1 when both sequences are at R, and from 1 to 0 when both sequences are at P.
Note that the longest common sequence is not necessarily unique. For instance, given the two sequences ABC and BAC, there are two longest common subsequences, AC and BC. Either answer is correct.
Your task is to write a function that takes two sequences and returns their longest common subsequence. 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.
Ternary Search Tries
June 5, 2009
Several of our exercises (Mark V. Shaney, Word Frequencies, Dodgson’s Doublets, Anagrams) have used hash tables based on string keys. When the keys are strings, a useful alternative to hash tables is a data structure called a ternary search trie, which can be faster than a hash table because it takes advantage of the fact that keys are strings, and also provides in-order access to the keys. Ternary search tries were introduced by Jon Bentley and Robert Sedgewick at the 1997 SODA conference.
As the name implies, ternary search tries are a cross between binary search trees and radix tries. Ternary search tries consist of recursive nodes and leaves, just like binary search trees and radix tries. As the name implies, a node of a ternary search trie has three children, one for lesser children, one for greater children, and a third for equal children. Searches proceed character-by-character, as with a trie. At each level of the trie, the search compares the current character of the search string with the character stored in the node. If the search character is less, the search continues at the less-than child, and if the search character is greater, the search continues at the greater-than child. However, when the two characters are equal, the search continues recursively at the equal-to child, proceeding to the next character in the search string.
The picture below, taken from the Bentley/Sedgewick SODA paper, shows a ternary search trie containing twelve two-character words:
Your task is to implement the lookup, insert, update, delete and enlist operations on ternary search tries. When you are finished, you are welcome to read or run a suggested solution, or post your solution or discuss the exercise in the comments below.
Pig Latin
June 2, 2009
Pig Latin is an English-language word game, usually played by children, in which words are mutated systematically. A word that begins with a vowel (a, e, i, o, or u) has the syllable “way” added to the end; for instance, art becomes art-way and eagle becomes eagle-way. A word that begins with one or more consonants has the initial consonants stripped, moved to the end of the word, then the syllable “ay” is added; for instance, start becomes art-stay and door becomes oor-day. A hyphen is added as shown above as an aid to prevent ambiguity; otherwise, a word like aspray could be the translation of spray (ay-spray) or prays (ays-pray). Even so, some words remain ambiguous; art-way could be translated as either art or wart.
Your task is to write functions that translate English to Pig Latin and Pig Latin to English. When you are finished, you may read or run a suggested solution, or post your solution or discuss the exercise in the comments below.
Double Transposition Cipher
May 29, 2009
Transposition ciphers work by rearranging the letters of a plaintext to form a ciphertext; both the length of the text and the frequency distribution of the letters are identical between plaintext and ciphertext. The rail-fence cipher is a well-known transposition cipher; another is the columnar transposition that is the subject of today’s exercise.
To illustrate columnar transposition, we will encipher the plaintext PROGRAMMINGPRAXIS with the keyword COACH. First, COACH is converted to the numeric key 25134 by noting the alphabetic ordering of its letters; the two Cs have the same rank, so they are ordered left to right. Then, the plaintext is written in rows under the key, each row the same length as the key:
C O A C H
2 5 1 3 4
P R O G R
A M M I N
G P R A X
I S
The ciphertext is read off by colums, taking the columns in numeric order; first OMR, then PAGI, and so on, ending with RMPS:
O M R P A G I G I A R N X R M P S
Decryption is the opposite operation. The shape of the grid is determined by the number of letters in the ciphertext and the number of letters in the key:
C O A C H
2 5 1 3 4
_ _ _ _ _
_ _ _ _ _
_ _ _ _ _
_ _
Then the letters of the ciphertext are filled in to the grid starting with the lowest-numbered column, then the second column, and so on, respecting the given column lengths; here is the grid with the first two columns filled
C O A C H
2 5 1 3 4
P _ O _ _
A _ M _ _
G _ R _ _
I _
Columnar transposition is fairly easy to break; guess a key length, write out the columns, then look for common letter-sequences like QU or THE or ING. Columnar transposition can be made much more secure by double-encrypting the input with two keys of differing length: encrypt the plaintext with the first key, then encrypt the intermediate ciphertext with the second key.
Double transposition ciphers were routinely used for military field-grade encryption through the Second World War, because they are reasonably secure but manageable by hand in less-than-ideal circumstances. It is said that the French could normally read German ciphers due to poor radio discipline by German cipher clerks; search for Übchi to learn more of this fascinating story. In recent times, double transposition ciphers have been cryptanalyzed and attacks are known.
Your task is to write functions to perform double-transposition encryption and decryption. 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.
Word Search Solver
May 26, 2009
Word search puzzles are a popular time-wasting pasttime. To redeem some of that lost time, we will write a program to search puzzles. For instance, given a problem like
F Y Y H N R D
R L J C I N U
A A W A A H R
N T K L P N E
C I L F S A P
E O G O T P N
H P O L A N D
and the list of words ITALY, HOLLAND, POLAND, SPAIN, FRANCE, JAPAN, TOGO, and PERU, you should find words at the following locations:
ITALY row 5 column 2 up
HOLLAND row 7 column 1 up right
POLAND row 7 column 2 right
SPAIN row 5 column 5 up
FRANCE row 1 column 1 down
JAPAN row 2 column 3 down right
TOGO row 6 column 5 left
PERU row 5 column 7 up
Your task is to write a word search 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.
The Next Palindrome
May 22, 2009
This exercise comes originally from the Sphere Online Judge; I read it on Proggit based on a blog posting by Chethan T. So many of the answers were wrong that I decided it would make a good exercise for Programming Praxis. Here is SPOJ’s statement of the exercise:
A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.
Your task is to write a function that calculates the next palindrome larger than its input. When you are finished, you are welcome to read or run a suggested solution, or post your own solution or discuss the exercise in the comments below.
Fermat’s Method
May 19, 2009
We have previously studied integer factorization by trial division and wheel factorization. In this exercise we will implement integer factorization by Fermat’s method. Pierre de Fermat was a French lawyer and amateur mathematician of the seventeenth century, a contemporary of René Descartes and Blaise Pascal, who did early work in calculus, number theory, analytic geometry and probability.
Fermat’s method works by noticing that if n, the odd number to be factored, can be written as the difference of two squares n = x2 – y2, then it can be factored as (x – y) × (x + y). Thus, to find the factors of n, we start with y = 0 and x as the smallest integer greater than or equal to the square root of n and increase y until x2 – y2 is equal to n, in which case x and y reveal the factors of n, or x2 – y2 is less than n, when we increase x by one and iterate. This process must terminate; if n is prime, it will stop with the factors 1 and n.
Though this method works, the repeated squarings are relatively expensive, so it is normal to work with u = 2x + 1 and v = 2y + 1 and to keep track of r = x2 – y2 – n; when r = 0, the algorithm terminates. The variable u keeps track of the amount r increases when x2 is replaced by (x + 1)2 and variable v keeps track of the amount r decreases when y is replaced by (y + 1)2; as x and y increase by 1, u and v increase by 2.
Your task is to implement integer factorization by Fermat’s method. When you are finished, you are welcome to read or run the suggested solution, or post your own solution or discuss the exercise in the comments below.
Cellular Automata
May 15, 2009
A cellular automaton is a collection of cells arranged in an infinite grid, controlled by a clock, with each cell coloring itself at each tick of the clock based on the state of its neighboring cells. A linear cellular automaton has all the cells of the grid arranged in a single line. A time-lapse picture of a linear cellular automaton shows a two-dimensional grid with the automaton as a horizontal line, the state of the automaton at each clock tick flowing down the page.
For the elementary cellular automata that we will study, each cell may be either of two colors, black or white, and a cell’s neighborhood consists of itself and the two cells on either side. With two colors and three neighbors, there are 23=8 states and 28=256 possible rules for advancing from one state to the next.
Rules are specified using a kind of binary notation; for each of the eight states 111, 110, 101, 100, 011, 010, 001, and 000, where 1 is black and 0 is white and the neighbors are arranged left-to-right on the line. Then the rule is specified by the binary number corresponding to the eight successor states of each of the eight neighbors, so for instance rule 30 = 000111102 maps 111 to 0, 110 to 0, 101 to 0, 100 to 1, 011 to 1, 010 to 1, 001 to 1, and 000 to 0.
For example, the first 12 rows of the rule 158 automaton applied to a row containing a single black cell are shown below:
X
X X X
X X X X
X X X X X
X X X X X X X
X X X X X X X
X X X X X X X X X X
X X X X X X X X X
X X X X X X X X X X X X X
X X X X X X X X X X X
X X X X X X X X X X X X X X X X
X X X X X X X X X X X X X
X X X X X X X X X X X X X X X X X X X
You can see more examples at http://mathworld.wolfram.com/ElementaryCellularAutomaton.html.
Your task is to write a function that draws the result of applying a given rule to a given number of rows, starting from a row with a single black cell. When you are finished, you are welcome to read or run a suggested solution, or post your own solution or discuss the exercise in the comments below.
Loan Amortization
May 12, 2009
My daughter, a freshman in high school, is just completing her first programming class, using Java. Her final assignment was to write a program to print a loan amortization table, given an initial balance, annual interest rate, term in months, and monthly payment.
Your task is to write that program (you are not restricted to Java), then print the amortization table for a three-year car loan of $10,000 at 7% (it’s an old textbook). When you are finished, you are welcome to read a suggested solution, or to post your solution or discuss the exercise in the comments below.
Programming Praxis 