Look And Say, Revisited
March 28, 2011
We calculated the look and say sequence in a previous exercise, and mentioned there that the sequence has some fascinating mathematical properties. One of them is that, if Ln is the number of digits in the n-th element of the sequence, then
where λ is known as Conway’s constant, calculated by the British mathematician John Horton Conway as the unique positive real root of the following polynomial:
Conway analyzed the look and say sequence in his paper “The Weird and Wonderful Chemistry of Audioactive Decay” published in Eureka, Volume 46, Pages 5−18 in 1986. In his blog, Nathaniel Johnston gives a derivation of the polynomial.
Your task is to compute the value of λ. 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.
Sum
March 25, 2011
Today’s exercise implements the old Unix Sys V R4 sum command. The original sum calculated a checksum as the sum of the bytes in the file, modulo 216−1, as well as the number of 512-byte blocks the file occupied on disk. Called with no arguments, sum read standard input and wrote the checksum and file blocks to standard output; called with one or more filename arguments, sum read each file and wrote for each a line containing the checksum, file blocks, and filename. The GNU version of the program, which implements an additional version of the checksum that was part of BSD Unix, is available at ftp://alpha.gnu.org/gnu/coreutils/textutils-2.0.22.tar.gz in file sum.c; if you run it, be sure to give the −s argument to get the original Unix Sys V R4 version of the checksum.
Your task is to write a program that implements the original Unix Sys V R4 sum command. 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.
Two Kaprekar Exercises
March 22, 2011
For today’s exercise we return to the world of recreational mathematics with two exercises due to the Indian mathematician Dattaraya Ramchandra Kaprekar. First we compute Kaprekar chains:
1. Choose any four-digit number, with at least two different digits. Leading zeros are permitted.
2. Arrange the digits into two numbers, one with the digits sorted into ascending order, the other with the digits sorted into descending order.
3. Subtract the smaller number from the larger number.
4. Repeat until the number is 6174. At that point, the process will cycle with 7641 − 1467 = 6174.
For instance, starting with 2011, the chain is 2110 − 112 = 1998, 9981 − 1899 = 8082, 8820 − 288 = 8532, and 8532 − 2358 = 6174.
The second exercise determines if a number is a Kaprekar number, defined as an n-digit number such that, when it is squared, the sum of the first n or n−1 digits and the last n digits is the original number. For instance, 703 is a Kaprekar number because 7032 = 494209 and 494 + 209 = 703. Sloane gives the list of Kaprekar numbers at A053816.
Your task is twofold: first, write a program that computes the Kaprekar chain for a given starting number, and compute the longest possible Kaprekar chain; second, write a program to determine if a particular number is a Kaprekar number, and compute the list of all the Kaprekar numbers less than a thousand. 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.
Loopy Loops
March 18, 2011
I don’t like this silly question. But it has appeared recently on Hacker News and Stack Overflow (C/C++ and Java, and probably other languages but I quit searching), and generated lots of comments on both, and it’s apparently a popular interview question, so we may as well do it here, too:
Print the numbers from 1 to 1000 without using any loop or conditional statements. Don’t just write the printf() or cout statement 1000 times.
Your task is to write the program in your favorite language. Have fun — think of as many solutions as you can, or the wackiest, or the fewest characters in the source file, or some other best-in-category. 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.
Look And Say
March 15, 2011
The “Look and Say” sequence, Sloane number A005150, begins 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, …. Each term is constructed from its predecessor by stating the frequency and number of each group of like digits. For instance, the term after 1211 is “one 1, one 2, and two 1s”, or 111221. This sequence was studied by the British mathematician John Horton Conway, and has some fascinating properties; see MathWorld or follow the references at Sloane’s if you are interested.
Your task is to write a program to compute the look and say sequence. 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.
Lowest Common Ancestor
March 11, 2011
Today’s problem appears with some regularity at places like Proggit and Stack Overflow and in lists of programming interview questions:
Given a binary tree t and two elements of the tree, m and n, with m<n, find the lowest element of the tree (farthest from the root) that is an ancestor of both m and n.
For example, in the tree shown at right, the lowest common ancestor of 4 and 7 is 6, the lowest common ancestor of 4 and 10 is 8, and the lowest common ancestor of 1 and 4 is 3. It is possible for an element of the tree to be its own ancestor, so the lowest common ancestor of 1 and 3 is 3, and the lowest common ancestor of 3 and 6 is 3.
Your task is to write a function that finds the lowest common ancestor of two elements of a binary tree. 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.
Reverse Words
March 8, 2011
After we solved the reverse-words problem in an exercise a few weeks ago, a reader complained that the suggested solution was too simple because it used library functions to split the words and later to rejoin them; he also thought the exercise should include a restriction that the string had to be reversed in-place. I’m not sure about either of the objections, but we’ll take the opportunity to revisit a classic interview question. We’ll also eliminate the letters-only and single-space-between-words restrictions of the original exercise from Google. Thus, here are some sample inputs and their associated outputs; note especially the placements of leading and trailing spaces:
"" => ""
" " => " "
" " => " "
"hello" => "hello"
"hello " => " hello"
" hello" => "hello "
"the quick brown fox" => "fox brown quick the"
"the quick brown fox" => "fox brown quick the"
"the quick brown 42 fox!" => "fox! 42 brown quick the"
Your task is to write a reverse-words function given the definition and restrictions stated 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.
Chutes And Ladders
March 4, 2011
The children’s game Chutes and Ladders, pictured at right, is a chase game in which one or more players, moving alternately, move their tokens along the numbered spaces of a board according to the roll of a die; the tokens are initially off-the-board at what is effectively space zero. Tokens that land on the bottom end of a ladder are promoted to the space at the top end of the ladder, and tokens that land on the top end of a chute are demoted to the space at the bottom end of the chute. Space 100 must be reached by exact roll of the die; if the roll of the die would take the token past space 100, the token remains where it is and play passes to the next player. The winner of the game is the first token to reach space 100.
There are several interesting questions that can be asked about the game. First, what is the minimum number of rolls required to reach space 100. Second, for a single player, what is the average number of rolls required to reach space 100. And third, for k players, what is the average number of rolls until one of the players reaches space 100 and wins the game. S. C. Althoen, L. King and K. Schilling studied these and other questions in their paper “How Long Is a Game of Snakes and Ladders?” The Mathematical Gazette, Volume 77, Number 478, March 1993, pages 71-76.
Your task is to write programs that will answer those questions. 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.
An Early LISP Program
March 1, 2011
Today we have another exercise in our continuing theme of historical computing, celebrating the publication of the Lisp I Programmer’s Manual on this date fifty-one years ago. Over at his blog Abstract Heresies, LISP/Scheme expert and general curmudgeon Joe Marshall recalls this program from that manual, written by Phyllis Fox:
DEFINE
(((COLLAPSE,(LAMBDA,(L),(COND,
((ATOM,L), (CONS,L,NIL))
((NULL,(CDR,L)),
(COND,((ATOM,(CAR,L)),L),(T,(COLLAPSE,(CAR,L)))))
(T,(APPEND,(COLLAPSE,(CAR,L)),(COLLAPSE,(CDR,L))))))))) ()
COLLAPSE ((((A,B),((C))),((D,(E,F)),(G),((H))))) ()
COLLAPSE ((A,(B,(C,(D,(E))),F,(G,(H,J))))) ()
COLLAPSE ((((((A),B),C),D),E)) ()
STOP))))))))))STOP
The program collapses a nested list into an un-nested one. Here’s the same program in modern Lisp:
(defun collapse (l)
(cond ((atom l) (cons l nil))
((null (cdr l))
(cond ((atom (car l)) l)
(t (collapse (car l)))))
(t (append (collapse (car l))
(collapse (cdr l))))))
Your task is to write a function to un-nest a nested list. 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 