Programming Praxis

In the mid-1980’s, Mark V. Shaney posted messages such as this to the Usenet group net.singles:

I seem to be important. For me, it would have agreed with the
technical insight that is dear to me. Because of this, I have no
advice for someone in that situation!

Joining Mensa was something I did him one better. I wore a dress skirt
a day for one week. I did him one better. I wore a dress skirt a day
for a 2 year relationship. I’m wondering if anyone else out there has
ever experienced this phenomena, whether it was actually your
contention that this is true for me.

I suppose it depends how you felt about someone before you became
emotionally attached and therefore “safer” – not to sporting events,
but to opera.

I lost 90 lbs a few months during my “flower child” days in high school
where, due to her high academic standings, was shunned by many of the
tube. The experience really screwed them up — if not their heads,
their knees. Why does one have to be the prime measurement of
manhood. No?

He was a scrawny, spastic nerd in high school, and I fantasized about
such a thing. It all depends on the sidelines, listening to what makes
the rest of the guys around her – suddenly finds herself in a situation
where guys are asking them out!? But this can result in members of
either the person of your dreams (in a larger number of males to
females studying the field of engineering), the ratio of males to
females is somewhere in the past. And, per the other person.

I find it hard to reconcile the notion that something or someone isn’t
theirs anymore. I have a date with the woman. Subjectively, I have
also acted in this weekend.

However, Shaney wasn’t a person. Shaney was a bot created by three Bell Labs researchers — Bruce Ellis, Rob Pike and Don Mitchell — that analyzed Usenet postings and then created its own posting. Shaney’s writings were quirky, non-sensical, and beloved by many.

Shaney worked by reading a training text and saving each triple of words that appear in the training text in a large table. Then it generates text using a markov chain, starting with two words that appear in the training text and repeatedly writing the third word of the triple, sliding the output window from word to word. The genius of the method is that any two words may appear in the training text with multiple following words, and the generator is free to choose any of them; thus, short fragments of text make sense, but the text as a whole frequently veers from one train of thought to another. A word includes its surrounding punctuation, so that sentence structure and, indirectly, grammar, are built in to the output.

Write a program that implements Shaney.

Pages: 1 2

Easter occurs each year on the first Sunday after the first full moon after the vernal equinox. Mardi Gras occurs on the Tuesday of the seventh week before Easter. Mardi Gras falls on February 24^th in 2009, with Easter forty-seven days later on April 12^th. On what date did Mardi Gras fall in 1989? On what date will Mardi Gras fall in 2049?

Pages: 1 2

Write a program that takes no input and generates a copy of its own source text as its complete output.

Pages: 1 2

The ratio of the circumference of a circle to its diameter is given by the constant known by the Greek letter pi, and is an irrational number (its representation is non-terminating and non-repeating) with a value slightly larger than 3.14159. What is the one-thousandth digit of pi? (Counting begins at zero, so the zero^th digit of pi is 3 and the fourth digit of pi is 5.)

Pages: 1 2

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?

Pages: 1 2

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!”

Pages: 1 2

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 m^th 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?

Pages: 1 2

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?

Pages: 1 2

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?

Pages: 1 2

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.

Pages: 1 2