Multiple Dwellings
February 20, 2009
Baker, Cooper, Fletcher, Miller and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher’s. Fletcher does not live on a floor adjacent to Cooper’s. Where does everyone live?
ROT13
February 20, 2009
From the Jargon File:
rot13 /rot ther’teen/ /n.,v./ [Usenet: from `rotate alphabet 13 places’] The simple Caesar-cypher encryption that replaces each English letter with the one 13 places forward or back along the alphabet, so that “The butler did it!” becomes “Gur ohgyre qvq vg!” Most Usenet news reading and posting programs include a rot13 feature. It is used to enclose the text in a sealed wrapper that the reader must choose to open — e.g., for posting things that might offend some readers, or spoilers. A major advantage of rot13 over rot(N) for other N is that it is self-inverse, so the same code can be used for encoding and decoding.
Write a function that takes a string and returns the ROT13 version of the string; you may assume that the character set is ascii. What is the meaning of “Cebtenzzvat Cenkvf vf sha!”
Flavius Josephus
February 19, 2009
Flavius Josephus was a famous Jewish historian of the first century, at the time of the destruction of the Second Temple. According to legend, during the Jewish-Roman war he was trapped in a cave with a group of forty soldiers surrounded by Romans. Preferring death to capture, the Jews decided to form a circle and, proceeding around it, to kill every third person remaining until no one was left. Josephus found the safe spot in the circle and thus stayed alive.
Write a function josephus(n,m) that returns a list of n people, numbered from 0 to n-1, in the order in which they are executed, every mth person in turn, with the sole survivor as the last person in the list. What is the value of josephus(41,3)? In what position did Josephus survive?
Sudoku
February 19, 2009
Sudoku puzzles are a simple and popular amusement given as a nine-by-nine grid of cells, some of them containing digits:
|
|
|
|||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
|
The challenge is to fill the empty cells with the digits 1 through 9 in such a way that no row, column, or three-by-three sub-grid contains the same digit two or more times.
Write a program to solve sudoku puzzles; your program may assume the puzzle is well-formed. What is the solution of the above puzzle?
Bingo
February 19, 2009
Bingo is a children’s game of chance, sometimes played by adults for fun or money. Each player has a card of numbers arranged in a five-by-five grid with five randomly-chosen numbers from 1 to 15 in the first column, from 16 to 30 in the second column, 31 to 45 in the third column, 46 to 60 in the fourth column, and 61 to 75 in the fifth column; the central space is “free” and is considered to be occupied. Then a caller randomly calls numbers from 1 to 75 without replacement, each player marking the corresponding number, if it is present on their card, as occupied. The first player to have five occupied numbers in a row horizontally, in a column vertically, or along either of the two major diagonals is the winner.
What is the average number of calls required before a single card achieves bingo? In a large game with five hundred cards in play, what is the average number of calls required before any card achieves bingo?
Sieve of Eratosthenes
February 19, 2009
Over two millenia ago, Eratosthenes, who calculated the circumference of the earth, the distance to the Sun and the tilt of the Earth’s axis, developed a system of latitude and longitude, and invented the leap day, created a systematic method to enumerate the prime numbers that is still in use today. Eratosthenes was born in Cyrene (present-day Libya), lived from 276 B.C. to 194 B.C., and spent most of his life in Alexandria, Egypt, where he was the second Chief Librarian of the Great Library, succeeding Apollonius of Rhodes; he was a good friend of Archimedes.
The Sieve of Eratosthenes starts by making a list of all the numbers up to a desired maximum; we’ll illustrate the method by calculating the prime numbers through thirty:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Now take the first number on the list, 2, and cross off every second number:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
(Although it may not be obvious, the number 4 is crossed off the list; in some fonts, the cross-bar of the 4 coincides with the strike-through bar.) Next, take the next number on the list that isn’t crossed off, 3, and cross off every third number; some of them have already been crossed off:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Repeat that last step for the next un-crossed number on the list, 5:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
And so on, each time crossing off all multiples of the next un-crossed number on the list. The list of prime numbers are all those that haven’t been crossed off:
2 3 5 7 11 13 17 19 23 29
This method is called a sieve because it sweeps through a range of numbers, with each prime number, as it is discovered, blocking all its multiples from falling through as prime numbers. The sieve admits several optimizations. First, only odd numbers are considered, since the initial sifting crosses off all the even numbers except 2, which is handled separately. Second, crossing off starts at the square of the number being sifted, since all smaller primes have already been crossed off by previous steps of the sieve; for instance, sifting by 3 starts at 9, since 6 was already crossed off when sifting by 2. Third, sifting stops at the square root of the maximum number in the sieve, since any non-primes larger than the square root must have already been crossed off at previous levels of the sieve; thus, in the above example there is no need to sieve on the prime number 7, or any larger prime number, since the square of 7 is greater than 30, which is the largest number in the list.
Write a function that takes a single argument n and returns a list of prime numbers less than or equal to n using the optimized sieving algorithm described above. Apply the function to the argument 15485863 and count the number of primes returned.
RPN Calculator
February 19, 2009
Implement an RPN calculator that takes an expression like 19 2.14 + 4.5 2 4.3 / - * which is usually expressed as (19 + 2.14) * (4.5 - 2 / 4.3) and responds with 85.2974. The program should read expressions from standard input and print the top of the stack to standard output when a newline is encountered. The program should retain the state of the operand stack between expressions.
Programming Praxis 