Write a program to compute the sum of all the integers between 1 and 10¹¹ both divisible by seven and, when the decimal digits are reversed, are still divisible by seven.

This puzzle was created July '05 and retired October '05

You have intercepted two encrypted messages, ciphertext-1 and ciphertext-2, encoded in the following 46-character alphabet:

[space]ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.?,-:;'()

The messages were encrypted with a one-time pad - a sequence of randomly drawn characters of the same length and alphabet as the plaintexts. The encryption algorithm is to add the code of a plaintext character with the code of the corresponding pad character, modulo 46. To illustrate, if the plaintext is "ITA SOFTWARE" and the pad is "9KS;UENFN068" then the ciphertext is ")4T;-TTZ.1E-".

plaintext: ITA SOFTWARE = 9 20 1 0 19 15 6 20 23 1 18 5
pad: 9KS;UENFN068 = 36 11 19 42 21 5 14 6 14 27 33 35
ciphertext: )4T;-TTZ.1E- = 45 31 20 42 40 20 20 26 37 28 5 40

However, the sender made the critical mistake of using the same one-time pad for both messages, compromising their security. Write a program that takes the two ciphertexts and produces a guess at the two plaintexts. It should produce two plaintext messages of the same length as the ciphertexts, hopefully containing many of the correct words in the correct positions. It is unlikely your program will get all of the words correct, since there is not enough information in the ciphertexts to uniquely determine the plaintexts. Strive for a quality of decryption sufficient for a human reader--perhaps with the aid of a web search--to identify the original texts, which happen to be excerpts from classic works of English literature.

Your program may use English text or word lists or dictionaries of your choice to train on, for example to gather tables of letter or word frequencies, but you should not rely on any portion of the messages being in your training material.

This puzzle was created September '04 and retired December '06

The file landmarks.xml contains a list of landmarks near ITA Software, along with their latitude and longitude in degrees. Write a Java web application which allows users to choose a landmark and search for others that are nearby. Your application should use an XML parser and XPATH to parse the landmarks database on the server, and use JSTL 1.1 to help create your web interface. When searching for nearby landmarks, use JavaScript and the XMLHttpRequest object rather than a standard HTTP post. Submit a gzipped tar file containing your application, or an Eclipse 3.1.0 project for use with the Sysdeo Tomcat Plugin. Document your code, and make sure it works with the latest Firefox and Tomcat 5.

Resources:

J2SE 5.0

Jakarta Tomcat 5.5.7+

Xerces 2.6.2+

Xalan 2.6.0+

Jakarta Taglibs - JSTL 1.1

Firefox 1.0.2+

Eclipse 3.1.0+

Sysdeo Eclipse Tomcat Plugin 3.0.0+

This puzzle was created April '05 and retired November '05

Write a program that reads in a simple 2-D maze in a format like these examples:


Download the mazes above as ASCII text.

The input is guaranteed to be a well-formed maze and to have a unique solution path from the bottom left grid cell to the top right grid cell. Your program should re-output the maze with the solution path filled in, e.g.:


Download results above as ASCII text.

Additional sample input mazes may be found in sample-mazes.tar.

This puzzle was created April '04 and retired August '04

In 1850, Carl Friedrich Gauss and Franz Nauck showed that it is possible to place eight queens on a chessboard such that no queen attacks any other queen. The problem of enumerating the 92 different ways there are to place 8 queens in this manner has become a standard programming example, and people have shown that it can be solved using many different search techniques. Now consider a variant of this problem: you must place an equal number of knights and queens on a chessboard such that no piece attacks any other piece. What is the maximum number of pieces you can so place on the board, and how many different ways can you do it?

This puzzle was created April '02 and retired June '04

An "add-a-gram" is a sequence of words formed by starting with a 3-letter word, adding a letter and rearranging to form a 4-letter word, and so on. For example, here are add-a-grams of the words "CREDENTIALS" and "ANACHRONISM":

ail + s = sail + n = nails + e = aliens + t = salient + r = entrails + c = clarinets + e = interlaces + d = CREDENTIALS (length 11)

mar + c = cram + h = march + s = charms + o = chromas + n = monarchs + i = harmonics + a = maraschino + n = ANACHRONISM (length 11)

Test your own credentials: given the dictionary found here (1.66MB), what is the longest add-a-gram?

This puzzle was created December '01 and retired April '02

(defun m (i j k)
  (cond ((= i 0) (1+ k))
        ((and (= i 1) (= k 0)) j)
        ((and (= i 2) (= k 0)) 0)
        ((= k 0) 1)
        (t (m (1- i) j (m i j (1- k))))))

 

eval (m 4 4 4) => ?

Notes:

• i, j, and k should be nonnegative integers
• The 1- operator in Common LISP is the same as -1+ in Scheme, for example, (1- 10) => 9.

This puzzle was created December ‘01 and retired April ’03

Combining nine 9s with any number of the operators +, -, *, /, (, ), what is the smallest positive integer that cannot be expressed?

Hints:

1)The answer isn't zero. You can express zero like this:
      (9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9)
    Also, zero isn't a positive integer.

2) The answer isn't one. You can express one like this:
       9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9

3) It's not a trick question.

4) Be sure to handle parentheses correctly.

Notes:

• You cannot exponentiate.
• You cannot concatenate (for example, put two 9s together to make 99).
• The - operator can be used in either its binary or unary form.
• Assume base 10.

This puzzle was created December '01 and retired August '03

Given a T timetable, write a program to compute the quickest route that passes through every station on the Red, Blue, Green, and Orange Lines, ending at Kendall Square.

Details
Your program should compute a route that visits all T stations at least once. A station has been visited if you stop there (to change to a different line) or pass through on a train. You may start at any station.

The supplied T timetable contains the definitive list of all T stations and the travel time between them. All trains in the timetable should be assumed to run in both directions. Assume that the expected wait time for a train at a given station is fixed:

 

• Red Line - 5 minutes
• Blue Line - 4 minutes
• Green Line - 3 minutes
• Orange Line - 2 minutes

For example, if part of your route includes changing from the Green Line to the Red Line at Park Street, you should assume that you will wait 5 minutes for the Red Line train to show up. You should also assume that the wait time is the same for all trains (e.g. you will wait 5 minutes for the Red Line to Braintree, Ashmont, or Alewife).

At the end of the line, you must get off the train and wait the appropriate amount of time for a train going in the opposite direction.

Include in your answer the total time to visit all stations, plus enough information to verify your solution. Sample output for a (suboptimal) route starting at Kendall Square might look like:

 

0:00:00:  Arrive Kendall/MIT
                 0:05:00:  Board Red Line Braintree
                 0:07:00:  Arrive Charles/MGH
                 0:09:00:  Arrive Park St
                 0:12:00:  Board Green Line B
                 0:14:00:  Arrive Government Center
                 0:17:00:  Board Green Line B
                 ...
                 

Of course, your code should not be in any way specific to the Boston subway topology, but generalize easily to other data files, representing, say, the New York subway.

This puzzle was created December ‘05 and retired January ‘07

In the card game SET^®, how many collections of 20 cards are there that do not contain a Set?

[For those unfamiliar with SET^®: each card has a number (1, 2, or 3)  of shapes (squiggle, oval, or diamond) of the same color (red, purple, or green) and shading (full, empty, or striped). Thus, there are 4 properties with 3 possible values for each property, for a total of 81 cards. A Set is defined as a collection of three cards such that for each property, either all three cards have the same value for this property, or all three cards have a different value for this property.]

Submit an explanation of your counting technique and a program that implements that technique. SET^® is a trademark of SET Enterprises, Inc.

This puzzle was created December '05 and retired January '07