Puzzle Archive



 
 

Over the years, you may have seen some of our recruiting puzzles in advertising campaigns around Boston and Cambridge. While we no longer require puzzle solutions as part of our application process, solving programming puzzles, problems, and riddles is still a passion at ITA.

 

For those of you who enjoy the challenge of designing and implementing solutions to interesting computing problems, here are some of our favorite retired puzzles. Enjoy! 

Rebus Generator


A rebus is a phrase or sentence expressed all or in part through pictures. For this puzzle, you will use pictures from this archive (use the included file "images.txt" to map pictures to the associated words). Write a program that will take an English sentence (here’s a list of test cases for you to use) and generate a rebus from it. Here’s a simple example:
 


That is, each word becomes a parenthesized expression with up to three components: a word corresponding to a picture from the clipart library, a sequence of letters to be added to the name of the picture, and a sequence of letters to be deleted from the name. Distinguish words used as pictures from other sequences of letters by prepending a colon. The order of letters must match: the letters to be added must be in the order in which they would appear in the target word, and the letters to be deleted must be in the order in which they appear in the image name. Your program should produce plain text output.

But there’s more to the puzzle than that. Suppose we charge 5 points for every consonant you add or delete, and 1 point for every vowel. Now come up with a rebus that costs the fewest points. The example above costs 57 points, but this rebus of the same phrase:

costs only 31 points.

Finally, you can reduce the cost even further by adding or subtracting images (which cost nothing) instead of letters. If you use recursive encodings, you can get rid of letters altogether. For instance, a recursive rebus for “solve” is:
 

 
Write a program to generate recursive rebuses like the one above. Your program may use a mix of letters and pictures; balance performance against optimal scores as you see fit. Even for all-picture rebuses, a shorter rebus is better.

 

Optimal Ghost


In the game of Ghost, two players take turns building up an English word from left to right. Each player adds one letter per turn. The goal is to not complete the spelling of a word: if you add a letter that completes a word (of 4+ letters), or if you add a letter that produces a string that cannot be extended into a word, you lose. (Bluffing plays and "challenges" may be ignored for the purpose of this puzzle.)

Write a program that allows a user to play Ghost against the computer.

The computer should play optimally given the following dictionary: WORD.LST (1.66 MB). Allow the human to play first. If the computer thinks it will win, it should play randomly among all its winning moves; if the computer thinks it will lose, it should play so as to extend the game as long as possible (choosing randomly among choices that force the maximal game length).

Your program should be written as a Java web application that provides an html-based, rich GUI for a human to play against the optimal computer player from inside the Firefox browser. The web page should access a server using JavaScript's XMLHttpRequest object, and display the results using DOM manipulation. Your GUI does not have to be complicated, but should be polished and look good.

Please submit your source code, configuration instructions, and any comments on your approach. Please also include a WAR file that we can test against Tomcat 5.5.x on Sun's J2SE 6.0. Finally, in your submission email, answer this question: if the human starts the game with 'n', and the computer plays according to the strategy above, what unique word will complete the human's victory?  
 

BitVector Genealogy


The BitVectors are an ancient and immortal race of 10,000, each with a 10,000 bit genome. The race evolved from a single individual by the following process: 9,999 times a BitVector chosen at random from amongst the population was cloned using an error-prone process that considers each bit independently, and flips it with 20% probability.


Write a program to guess the reproductive history of BitVectors from their genetic material. The randomly-ordered file bitvectors-genes.data.gz contains a 10,000 bit line for each individual. Your program's output should be, for each input line, the 0-based line number of that individual's parent, or -1 if it is the progenitor. Balance performance against probability of mistakes as you see fit.


To help you test your program, here is a much smaller 500 x 500 input dataset:bitvectors-genes.data.small.gz, along with its solution file: bitvectors-parents.data.small.
 

Word Numbers


"If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?"
 
 

To be precise: if the integers from 1 to 999,999,999 are expressed in words (omitting spaces, 'and', and punctuation[1]), and sorted alphabetically so that the first six integers are
 

  • eight
  • eighteen
  • eighteenmillion
  • eighteenmillioneight
  • eighteenmillioneighteen
  • eighteenmillioneighteenthousand
  • twothousandtwohundredtwo

then reading top to bottom, left to right, the 28th letter completes the spelling of the integer "eighteenmillion".

 

The 51 billionth letter also completes the spelling of an integer. Which one, and what is the sum of all the integers to that point?
 

[1] For example, 911,610,034 is written "ninehundredelevenmillionsixhundredtenthousandthirtyfour"; 500,000,000 is written "fivehundredmillion"; 1,709 is written "onethousandsevenhundrednine".

This puzzle was created March 2007 and retired September 2008.

Sling Blade Runner


"How long a chain of overlapping movie titles, like Sling Blade Runner, can you find?"

Use the following listing of movie titles: MOVIES.LST. Multi-word overlaps, as in "License to Kill a Mockingbird," are allowed. The same title may not be used more than once in a solution. Heuristic solutions that may not always produce the greatest number of titles will be accepted: seek a reasonable tradeoff of efficiency and optimality.
 

Data provided by MovieLens at the University of Minnesota.

This puzzle was created March 2007 and retired September 2008.

Lucky Sevens


Write a program to compute the sum of all the integers between 1 and 10^11 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.

Decrypting the Two-Time Pad (hard!)


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.

Landmarks Web App


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 in April '05 and retired November '05.

 

ASCII A-maze-ment

 


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.

 

Queens & Knights


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 in April '02 and retired in June '04.

Add-A-Gram


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, what is the longest add-a-gram?


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

The Mystery M Function


(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 in December ‘01 and retired in April ’03.

Nine 9s


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 in December '01 and retired in August '03.

Instant Search


Write a Java web application which provides "instant search" over properties listed in the National Register of Historic Places. Rather than waiting for the user to press a submit button, your application will dynamically update search results as input is typed. We provide the file nrhp.xml.gz, which contains selected information from the register's database.

Database
The key component of your server-side application is an efficient, in-memory data structure for looking up properties (written in pure Java). A good solution may take several minutes to load, but can answer a query in well under 0.1 ms on a modern PC. (Note that a sequential search of all properties is probably too slow!) An input matches a property if it is found at any position within that property's names, address, or city+state. Matches are case-insensitive, and consider only the characters A-Z and 0-9, e.g. the input "mainst" matches "200 S Main St" and "red" matches "Lakeshore Dr." Note that the server's JVM will be configured with 1024M maximum heap space. Please conform to the interfaces specified in nrhp.jar when creating your database.

Servlet
Your servlet should accept an input string as the request parameter to a GET request. Results should include the information for a pre-configured number of properties (e.g. 10), the total number of matches which exist in the database, and the time taken by your search algorithm. Your servlet should be stateless, ie. not depend on any per-user session information. Paginate your additional results as a bonus!


Client
Your web page should access the servlet using JavaScript's XMLHttpRequest object. As the user types, your interface should repeatedly refine the list of search results without refreshing the page. Your GUI does not have to be complicated, but should be polished and look good.
 

Please submit a WAR file, configuration instructions, your source code, and any comments on your approach. Your application will be tested with Tomcat on Sun's 64-bit J2SE and a recent version of Firefox.
 

Resources XMLHttpRequest, StAX, Apache Tomcat, Mozilla Firefox, Eclipse
 


 

Roll Your Own Chat Server


Implement a simple standalone TCP-based chat server, using the following protocol:

The server responds to all commands with either:
            OK<CRLF>
  
or, when an error occurred, with:
            ERROR <reason><CRLF>    
<CRLF> indicates the bytes '\r\n'.

Upon connecting to the server, the client sends:
            LOGIN <username><CRLF>    
Clients can create new chatrooms or join existing chatrooms (chatrooms begin with the character '#') by doing:
            JOIN #<chatroom><CRLF>   
Clients can leave chatrooms by sending:
            PART #<chatroom><CRLF>   
Clients can be in multiple chatrooms at once.

Clients can send a message to a chatroom:

            MSG #<chatroom> <message-text><CRLF>    
Clients can send a message to another user:
            MSG <username> <message-text><CRLF>     
When a message is sent to a chatroom the user is in, the server sends to the appropriate client:
            GOTROOMMSG  <sender> #<chatroom> <message-text><CRLF>   
or if the message is sent directly from one user to another:
            GOTUSERMSG <sender> <message-text><CRLF>     
Finally, the client can log off by sending:
            LOGOUT<CRLF>

Here's a transcript of a sample session where a user named "alice" joins a chatroom called #news after connecting. C indicates the line was sent by the client, S indicates it was sent by the server (end of line indicates CRLF was sent):


C: LOGIN alice

S: OK

C: JOIN #news

S: OK

C: MSG #news hi everyone

S: GOTROOMMSG bob #news nothing much happened after that

S: OK

S: GOTROOMMSG alice #news hi everyone

S: GOTUSERMSG carol hi alice, where've you been?

C: MSG carol on vacation

S: OK

C: LOGOUT



When implementing the server, aim for scalability and robustness. (Many submissions fail due to lack of robustness!) Your submission should include a description of the steps you took towards those two goals. Keep in mind that the client may be buggy, or even malicious. For example, if a client connects to the server and sends an infinite stream of the byte 'X' with no line break, the server should deal with this case gracefully. Please do not use an existing networking framework (e.g., Twisted or asyncore for Python, ACE for C++, etc.) to implement the server. The server should support running on Linux. 
 

 

The O'Hare Affair


Objective
You want to meet a friend at O'Hare airport at noon and return home the same day. Given a date and an origin airport, find the pair of nonstop flights that gets you to Chicago and home again on that date, minimizing your total time away from home, subject to the constraint that you are at O'Hare at noon. 


Details
Your program, which must be written in Java, will work by scraping our http://matrix2.itasoftware.com website. Your program should accept two command-line inputs as follows: 

java -jar OHareAffair.jar YYYY-MM-DD airportCode


The program should navigate to matrix2.itasoftware.com and pose a round-trip query between the given airportCode and O'Hare (ORD), limited to nonstop flights only, using BOS as the sales city, with appropriate date and time constraints. The program should then scan the resulting solution set for solutions that meet the objective specified above. No more than 15 http requests should be made of matrix2.itasoftware.com per invocation. Finally, details of the three shortest solutions (breaking ties arbitrarily) should be written out in human-readable form to the console.


For example, for a traveler from Baltimore on July 4th, your program might be invoked as follows: 


java -jar OHareAffair.jar 2006-07-04 BWI


Sample output:


Travelling round-trip from BWI to ORD on 2006-07-04:
Trip length: 6:21
Outbound: American Airlines Flight AA3991 (10:03a-11:04a)
Return: United Airlines Flight UA1236 (1:30p-4:24p)
Trip length: 6:39
Outbound: United Airlines Flight UA641 (9:45a-10:47a)
Return: United Airlines Flight UA1236 (1:30p-4:24p)
Trip length: 6:54
Outbound: American Airlines Flight AA3991 (10:03a-11:04a)
Return: American Airlines Flight AA4009 (2:09p-4:57p)


Strive to make your code clean and robust, and to report errors cleanly. Be sure to include your source, any necessary libraries, and instructions on how to run it. 
 

Strawberry Fields


Strawberries are growing in a rectangular field of length and width at most 50. You want to build greenhouses to enclose the strawberries. Greenhouses are rectangular, axis-aligned with the field (i.e., not diagonal), and may not overlap. The cost of each greenhouse is $10 plus $1 per unit of area covered.

Write a program that chooses the best number of greenhouses to build, and their locations, so as to enclose all the strawberries as cheaply as possible. Heuristic solutions that may not always produce the lowest possible cost will be accepted: seek a reasonable tradeoff of efficiency and optimality.

Your program must read a small integer 1 ≤ N ≤ 10 representing the maximum number of greenhouses to consider, and a matrix representation of the field, in which the '@' symbol represents a strawberry. Output must be a copy of the original matrix with letters used to represent greenhouses, preceded by the covering's cost. Here is an example input-output pair:

Input   Output
4
..@@@@@...............
..@@@@@@........@@@...
.....@@@@@......@@@...
.......@@@@@@@@@@@@...
.........@@@@@........
.........@@@@@........
                  90
..AAAAAAAA............
..AAAAAAAA....CCCCC...
..AAAAAAAA....CCCCC...
.......BBBBBBBCCCCC...
.......BBBBBBB........
.......BBBBBBB........

In this example, the solution cost of $90 is computed as (10+8*3) + (10+7*3) + (10+5*3).

 

Run your program on the 9 sample inputs found in this file and report the total cost of the 9 solutions found by your program, as well as each individual solution.

 

Palindromic Pangram


A palindrome is a sequence of words like "lid off a daffodil" or "shallot ayatollahs" that uses the same letters reading backwards as forwards. The words need not form a meaningful or grammatical sentence.

A palindromic pangram is a multi-word palindrome that includes all 26 letters of the alphabet. Find the shortest sequence of words that is both a pangram and a palindrome. Use this dictionary: WORD.LST (1.66 MB).

 

This puzzle was created in 2004 and retired in January 2009.

Tour the T


Objective

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 in December ‘05 and retired in January ‘07.

 

Word Rectangle


Write a program to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom). Words should appear in this dictionary: WORD.LST (1.66MB). Heuristic solutions that may not always produce a provably optimal rectangle will be accepted: seek a reasonable tradeoff of efficiency and optimality. 

 

Setless SET®


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 in December '05 and retired in January '07.