1997-98
NEW MEXICO
HIGH SCHOOL
SUPERCOMPUTING
CHALLENGE

Interim Report


Team Number: 065
School Name: Gallup High School
Area of Science: Computer Science
Project Title: Intelligent Decryption
Project Abstract: http://mode.lanl.k12.nm.us/97.98/abstracts/065.html
Interim Report: http://mode.lanl.k12.nm.us/97.98/interims/065.html
Final Report: http://mode.lanl.k12.nm.us/97.98/finalreports/065/finalreport.html

The problem: alphabet soup. That's what we start with. We start out with a cryptogram with the standard letter-for-letter swapping, and we want to know what the darn thing says. We could probably figure it out on our own, but we're just too lazy, so instead we are going to write a program that lets the supercomputer do it for us. Sounds easy, right? Not exactly, but it is fun.

Now that we know what we want the computer to do, we have to tell it how. If this were Hollywood, we could just stick the paper with the cryptogram in the slot marked "INSERT CRYPTOGRAM HERE" and it would spit out the answer. Unfortunately, no matter how hard I look, I can't seem to find that slot, so I guess we'll have to do this the hard way, with C++ even!

Now, you don't just plunge headfirst into a programming job like this one without some kind of plan(well, I usually do, but that's not how its supposed to be done:). So out plan is this: create a searchable database of words for the computer to go through. This will be its knowledge base. Then we will write routines that parse and sort the input file, so the computer can more easily use it. We will proceed to write routines that have the computer search its database for matches to the patterns of letters in the cryptogram. After it has done this a couple of times, the computer has most likely figured out several valid replacements for letters. It can now go through all of the words, replacing letters it knows as it goes.(I made a rhyme:) The computer will proceed this way, matching patterns and replacing letters, until it has come up with a final answer. This answer will be its output.

Maybe you think the program is done at that point. WRONG! If that is all that it did, it wouldn't be too intelligent. Since it has figured out all of these neat words, it wouldn't be smart just to forget about them, so the computer goes through and finds ones that it doesn't know yet and learns them. That is, it adds them to its database of words so that it can use it again later on. Pretty smart, huh?

Well, so far we have done most of the research we need. We bought a good book on Artificial Intelligence that goes over different ways to search a state space. As for the actual code itself, we are almost done with the input parsing and sorting section. We ran into a little snag with an undocumented "feature" of the istream.get() member function. It turns out that once you have read to the end of the stream, you can't rewind back to the start of the file even though the file buffer is still there. Tracking down a problem like that can drive a person insane, because there is nothing obviously wrong with the source code. To get around this problem we just close the file and open it again to "rewind" it. This may not be the most efficient way to re-read a file, but since we only do it a couple of times in the program, it is not a big problem.

If we complete the pattern matching and replacement routines, hopefully the computer will spit out something intelligible when we feed it a bunch of gibberish. If we make it that far without hitting any major snags, we might have some time to kill. Then we could use a library that we found to add grammar checking to the program, which will probably make it run more efficiently.

Do we dare give the computer an understanding of grammar? Do we dare risk breaking down all forms of protecting information? Do we dare use this program to solve the cryptograms in the Sunday paper while we sit and watch mindless television, then impress all of our relatives by showing them that "we" solved the diabolical puzzle, inflating our ego's and reducing our minds to mush? Only time will tell.

Team Members:

Sponsoring Teacher(s):

Project Advisor(s):


New Mexico High School Supercomputing Challenge
http://mode.lanl.k12.nm.us