Project Euler, MIT Mystery Hunt Edition
The MIT Mystery Hunt starts this Friday at noon, and I’ll be participating seriously for about my 10th year. In the hunt, teams solve a collection of puzzles to discover the location of a gold coin hidden somewhere on campus. The puzzles may be numerous (sometimes over 100), are generally provided without instructions (except when they are provided with painfully explicit instructions), and the overall structure of the hunt is also unknown at the start. Hunt is nearly always finished before Monday, but during the 60 hours starting Friday at noon, many highly capable teams, some with several dozen members, will try their hardest to solve some very challenging puzzles.
Project Euler is a neat website that presents a series of computer science problems suitable for students and non-students to practice the skill of writing algorithms to solve numerical puzzles. It’s a great way to learn a new programming language, or just to kill time in a mentally engaging way.
Two of the peculiarities of the MIT Mystery Hunt are that the puzzles are drawn from a wide range of domains, and that there are no restrictions on what resources can be brought to bear on a puzzle. The result is both puzzles that are explicitly about software (e.g. perl program cryptograms) as well as puzzles that are best solved by writing some kind of program. Many of my favorite puzzles over the years have come from this category. Some hunts have few, some hunts have many, but every year there is a call to write some kind of software solution to a puzzle.
The programming skills required to write puzzle solving programs in high pressure situations are different from those normally required to write software, and so it can be useful to practice them. I have collected and categorized here all of the software puzzles since the 2000 hunt. In most cases, I recommend attempting to solve the puzzle, knowing that software is likely the best way. But because the solutions are available, if you are stumped it can still be interesting to read the solution and attempt to duplicate it in software. In most cases the solution is linked from the puzzle page; where it is not I have provided a link. The categories here are presented from least elegant to most elegant, in my opinion. Feel free to jump around and do puzzles which you find attractive.
Just Decompile It
A useful trick is to decompile any java applet or flash thing that you are given in a puzzle. The answer might just be in a string constant, though more likely it will just give you a different puzzle to solve.
- Maze (2005)
- String Theory (2003)
- Gnireenigne Lab (2003) This reverse engineering puzzle is pretty challenging. Only one team solved it during the longest hunt on record.
- Cubology (2002) Unfortunately decompiling this one doesn’t really help, but what the hey. (answer)
- Twisty Little Passages (2008) Not quite decompilation, but pulling the whole maze down to your local machine is the best way to handle this puzzle.
- Some Trolleys Named Lust (2006) The title clues Moira, the computer system that does configuration management for MIT Athena, which has command line utilities named after characters from A Streetcar Named Desire. This puzzle contains components which are no longer online, so you are limited to reading through the solution.
Mathematical Manipulation and Brute Force Enumeration
Many search problems can be solves on modern hardware with brute force enumeration, or maybe slightly smart enumeration.
- Bars of Soap (2005) Unfortunately the puzzle isn’t available, only the solution, though it still provides a useful programming exercise.
- Ginormous (2005) Prime factorization is always a fun thing to do with numbers.
- The Road Signs Of Unspeakable Chaos (2003)
- Mathophobia (2001) (answer)
Sometimes a program is the easiest way to do a bulk text manipulation. Particularly when you need to experiment with various transforms, or might need to do them repeatedly. This includes basically all cryptograms, which I am not including here, though software often comes in handy solving them.
- Blather (2007)
- Decode This (2006)
- Long Division (2006) Not so much text manipulation as diagram manipulation, but you can get the diagram as postscript, which makes it easy to extract the data. Doesn’t help you figuring out the algorithm, but it does make trying out variations easier.
- Shotgun Wedding (2005) Gene sequencing also comes up occasionally. There are some pretty simple text matching algorithms that turn out to be critical parts of that work.
- Lost (2004)
- Reminders World (2004)
- Whoa — I have a Migraine! (2003)
- Famous First Words (2002) (answer)
- Lions and Tigers and Bears (2000) My first attempt to solve a puzzle with software, this one wasn’t very successful, partly because of the challenge of getting the grid and the source data accurately input, and partly because of a slow algorithm. The fact that computers were notably slower in 2000 might have also been relevant. I think the most powerful machine available to me was an Ultra 10. In the end people doing it by hand finished first. (answer)
File Identification and Manipulation
Many puzzles require you to identify files, or to do interesting manipulations to entire files. Often both at the same time. Sometimes the files are programs written in other languages.
- Hyperextensions (2009)
- Surgical Files (2009) This puzzle triggered a programming language race, between Perl and Haskell. The race ended in a tie, but I learned some cool Haskell tricks from a teammate in the process.
- White Noise (2006) Being able to manipulate audio files with programs or tools is also important.
- Noise in the Air (2004) Knowing your off the shelf cryptography tools (ie, openssl) is sometimes helpful
- Two-Timer (2004)
- A Problem With Printing (2003) This is probably my favorite mystery hunt software puzzle. It’s written in the postscript language, which is a great language for puzzlers to know, and makes use of the peculiarities of that language.
Programming Language Identification and Cryptograms
Many puzzles come down to identifying obscure or not very obscure programming languages. One thinng to be on the lookout for is knitting notation, which can often look like a programming language. Of course, writing programs is often still more efficient than knitting an actual object. Adding complexity, often the programs you are given are cryptograms, or otherwise obfuscated.
- Tragedy (2008)
- Badness 10000 (2006) Unfortunately no longer online, but I like the structure. You can read the solution.
- Square Mess (2005) presents you with a machine language and a set of constraints on the notation used for a program in it.
- Who’s There (2004)
- Sixty Degrees of Separation (2004)
- What Do You Do With A Genteel Sailor (2004)
- Whoa — I Know Knitting! (2003)
- A Nugget of Wisdom (2002) (answer)
- Use of Gothicism Considered Harmful (2002) (answer)
Blue Steel (2006) You can try to solve, but you probably just want to read the solution. It will remind you not to think so hard sometimes.
[Edited 2010-01-11 to add Twisty Little Passages (2008). Feel free to add other missing puzzles in the comments.]