Sum of squares of two largest of three values
March 16, 2012
Today’s exercise comes to us from the book Structure and Interpretation of Computer Programs by Abelson and Sussman (exercise 1.3):
Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.
Your task is to write the indicated function. 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.
Perfect Power Predicate
March 13, 2012
A number n is a perfect power if there exists a b and e for which be = n. For instance 216 = 63 = 23 · 33 is a perfect power, but 72 = 23 · 32 is not. Testing for perfect powers is similar to other powering predicates we have seen, and is useful in some factoring algorithms.
The trick to determining if a number is a perfect power is to know that, if the number is a perfect power, then the exponent e must be less than log2 n, because if e is greater then 2e will be greater than n. Further, it is only necessary to test prime es, because if a number is a perfect power to a composite exponent it will also be a perfect power to the prime factors of the composite component; for instance, 215 = 32768 = 323 = 85 is a perfect cube root and also a perfect fifth root.
Your task is to write a function to determine if a number is a perfect power. 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.
Sparse Sets
March 9, 2012
We look today at a clever data structure for storing sparse sets of integers on the range 0 .. u−1 and performing initialization, lookup, and insertion is time O(1) and iteration in O(n), where n is the number of elements in the set. The data structure was studied in a 1993 article “An Efficient Representation for Sparse Sets” by Preston Briggs and Linda Torczon, in Exercise 1.9 (1.8 in the first edition) of Jon Bentley’s book Programming Pearls, and in exercise 2.12 of the 1974 book The Design and Analysis of Computer Algorithms by Al Aho, John Hopcroft and Jeffrey Ullman; the data structure itself dates to the folklore of computing.
The data structure considers a universe of integers from 0 to u−1; depending on the circumstances, the integers probably map to something else, but we don’t care about that. Any given set consists of n items chose from the universe; there are no duplicates. Note that n ≤ u, certainly, and likely n is much less than u — otherwise, you would probably use a bit vector to represent the set. Note also that we are optimizing for speed at the expense of space, as a bit vector takes u bits but our data structure takes 2u integers.
Think about a bit vector. Setting a bit is a constant-time operation, as is checking if a bit is set or unset. But initializing the bit vector and iterating over the set elements of the bit vector each take time proportional to the size of the bit vector. Our sparse sets reduce the iteration to time proportional to the size of the set (rather than the size of the universe) and reduce the initialization time to a constant.
The sparse set is represented by two vectors that we will call dense (abbreviated D) and sparse (abbreviated S). Initially n, the number of elements in the set, is zero; the two vectors are uninitialized and may contain anything. To add an element 0 ≤ k < u to a set that does not already contain k, we set D[n] to k, S[k] to n, and increase n by 1, an operation that takes constant time. After this, the two vectors point to each other, which gives a test of set membership that also works in constant time: an element k is in the set if and only if S[k] < n and D[S[k]] == k>. Note that if k is not a member of the set, the value of S[k] doesn’t matter; either it S[k] will be greater than n or it will point to an element of D that doesn’t point back to it. The diagram above right shows a set with the elements 5, 1 and 4; the blue boxes may contain any value. To iterate over the elements of the set, read D[0 .. n−1], which takes time O(n), and to clear the set make n = 0, which takes time O(1); note in particular that clearing the set doesn’t require reinitialization. Other operations, including size-of, delete, union, intersection, difference, and set-equality are possible, and equally time-efficient compared to bit vectors, but we won’t discuss them here, since they are seldom used with this representation of sets. A common use of these sparse sets is with register allocation algorithms in compilers, which have a fixed universe (the number of registers in the machine) and are updated and cleared frequently during a single processing run.
Your task is to implement the insert, lookup, iterate and clear operations for sparse sets as 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.
Union Route Cipher
March 6, 2012
One of the most successful military ciphers in history was fielded by the Union armies during the American Civil War. It is known that the Confederacy never cracked the cipher; in fact, they even took to publishing intercepted messages in their newspapers, in the hope that someone could read them. The cipher was devised by Anton Stager, the general superintendent of the Western Union Telegraph Company, at the request of the government of Ohio; later, General George McClellan, who was in charge of the armies of Ohio, introduced the cipher throughout the Union armies. You can read more about the cipher here and here.
The cipher works in two phases. First, some of the words with military significance are replaced by code words; for instance, attack could be replaced by tulip, and the phrase at dawn could be replaced by stripe, so the code tulip stripe means attack at dawn. The lexicon included names of people (Lincoln, various generals), places (Richmond, hilltop), times (Tuesday, 4:30pm, dawn), and actions (attack, reconnoiter); a single cleartext word could admit multiple code words, multiple cleartext words could be encoded as a single word, and even digits and punctuation had code words. The final version of the lexicon included 1608 codewords.
The second phase was a route transposition, and there were many variants. For instance, a route designated willow might call for six columns with words chosen in the order down column three, up column four, down column two, down column six, up column one, and down column five; nulls were added to pad out the last row, and an additional null was added in a seventh column.
Here’s an example: On June 1, 1863, President Lincoln sent the following telegram:
FOR COLONEL LUDLOW:
RICHARDSON AND BROWN, CORRESPONDENTS OF THE TRIBUNE,
CAPTURED AT VICKSBURG, ARE DETAINED AT RICHMOND.
PLEASE ASCERTAIN WHY THEY ARE DETAINED
AND GET THEM OFF IF YOU CAN.
LINCOLN.
The lexicon included certain codewords: VENUS for COLONEL, WAYLAND for CAPTURED, ODOR for VICKBURG, NEPTUNE for RICHMOND, and ADAM for LINCOLN. An additional codeword NELLY gives the time of dispatch as 4:30PM. Thus the message becomes:
FOR VENUS LUDLOW:
RICHARDSON AND BROWN, CORRESPONDENTS OF THE TRIBUNE,
WAYLAND AT ODOR, ARE DETAINED AT NEPTUNE.
PLEASE ASCERTAIN WHY THEY ARE DETAINED
AND GET THEM OFF IF YOU CAN.
ADAM NELLY
Now the cipher clerk picks a route GUARD that calls for five columns in the order up column one, down column two, up column five, down column four, and up column three. He writes the message in five columns, the last row padded with nulls:
FOR VENUS LUDLOW RICHARDSON AND
BROWN CORRESPONDENTS OF THE TRIBUNE
WAYLAND AT ODOR ARE DETAINED
AT NEPTUNE PLEASE ASCERTAIN WHY
THEY ARE DETAINED AND GET
THEM OFF IF YOU CAN
ADAM NELLY THIS FILLS UP
Now the message is pulled off in column route order and nulls are added after each column:
up column one ADAM THEM THEY AT WAYLAND BROWN FOR KISSING
down column two VENUS CORRESPONDENTS AT NEPTUNE ARE OFF NELLY TURNING
up column five UP CAN GET WHY DETAINED TRIBUNE AND TIMES
down column four RICHARDSON THE ARE ASCERTAIN AND YOU FILLS BELLY
up column three THIS IF DETAINED PLEASE ODOR OF LUDLOW COMMISSIONER
Then the final message is read off in order following the route indicator:
GUARD ADAM THEM THEY AT WAYLAND BROWN FOR KISSING VENUS CORRESPONDENTS AT NEPTUNE ARE OFF NELLY TURNING UP CAN GET WHY DETAINED TRIBUNE AND TIMES RICHARDSON THE ARE ASCERTAIN AND YOU FILLS BELLY THIS IF DETAINED PLEASE ODOR OF LUDLOW COMMISSIONER
Deciphering simply reverses the process. The recipient counts the words in the message, draws a grid of the proper size, fills in words in route order, converts codewords to their plaintext equivalents, and reads the message.
The Union route cipher had the strong advantage that it worked with words rather than individual letters, making errors in transcription and telegraphy much less common. The disadvantage, of course, was that codebooks had to be painstakingly controlled; loss of a single codebook would give the enemy access to all your communications. But that didn’t happen, and the cipher remained secure throughout the war.
Your task is to write a program that encrypts and decrypts messages according to the Union route cipher; make your own conventions for the lexicon and routes. 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.
Balanced Delimiters
March 2, 2012
These interview questions are addicting; I have to stop with them and get on something else. But one more won’t hurt:
Write a function that takes a string and determines if the delimiters in the string are balanced. The pairs of delimiters are (), [], {}, and <>, and delimiters may be nested. In addition, determine that string delimiters ‘ and ” are properly matched; other delimiters lose their magical delimiter-ness property within quoted strings. Any delimiter is escaped if it follows a backslash.
Your task is to write the function to determine if a string has balanced delimiters. 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.
Next Greater Permutation Of Digits
February 28, 2012
We have another interview question today:
Given a number, find the next higher number that uses the same set of digits. For instance, given the number 38276, the next higher number that uses the digits 2 3 6 7 8 is 38627.
Your task is to write a function to find the next greater permutation of digits. 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.
Remove characters from a string
February 24, 2012
The other day I needed a function to remove characters from a string, and was annoyed when neither R5RS nor the Standard Prelude provided one. Today’s exercise asks you to write that function:
Write a function that takes two strings and removes from the first string any character that appears in the second string. For instance, if the first string is “Programming Praxis” and the second string is “aeiou” the result is “Prgrmmng Prxs”.
Your task is to write the function 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.
Learn A New Language
February 21, 2012
We’ve done this before, and had some fun, so we’ll do it again.
There are hundreds, probably thousands, of programming language. Some are general-purpose, others are intended for a limited domain. Some are useful, most get in your way. Some are just weird. We programmers frequently have to learn a new language, or re-learn an old one, or adapt to improvements from the vendor.
A good way to learn a new language is to write in the new language a familiar program from an old language with which you are experienced. Many people have written that they use the exercises at Programming Praxis as a way to get started with a new language.
Your task is to write a program that solves the Programming Praxis exercise of your choice in a programming language in which you are not proficient. 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.
Hailstones
February 17, 2012
We have an easy exercise for a Friday afternoon.
Consider the sequence of positive integers for which xn+1 = xn / 2 when x is even and 3·xn + 1 when xn is odd; this is known colloquially as “half or triple plus one.” For instance, starting from x0 = 13 the sequence is 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, whence it loops through 4, 2, 1, …. This is called a hailstone sequence because it tends to go up and down and up and down much like hailstones in a thundercloud. Lothar Collatz conjectured in 1937 that every starting number eventually reaches 1; the conjecture is widely believed to be true, but has never been proven or disproven.
Your task is to write a function that computes hailstone sequences; you may wish to have some fun with your function by searching the internet for interesting tidbits about hailstone sequences and the Collatz conjecture. 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.
Divisors
February 14, 2012
We discussed divisors in a previous exercise. There, we factored a number and applied various loops to list the divisors of the number, their count, and their sum. That works fine for one or a few numbers. But if you have to find the divisors of a lot of numbers, it makes sense to compute the solutions all at once using a sieve. Start with an empty array d of the desired size n; then, for each i from 1 to n, mark i as a divisor of each multiple of i. For instance, with an array of 12:
1: 1
2: 1 2
3: 1 3
4: 1 2 4
5: 1 5
6: 1 2 3 6
7: 1 7
8: 1 2 4 8
9: 1 3 9
10: 1 2 5 10
11: 1 11
12: 1 2 3 4 6 12
Depending on your needs, you can make a list of the divisors, or count them, or compute their sum as you go along.
Your task is to write a function that builds a table of divisors as in the sample. Use it to find the perfect numbers and amicable pairs less than 10000, where perfect numbers are those whose divisors sum to twice the number and amicable pairs are those numbers whose sum of divisors (excluding the number itself) are the other number of the pair. 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.
Programming Praxis 