Internet Problem Solving Contest

IPSC 2008

Solution to Problem F – Find the Meaning

As the letters were dated 1929, no-one really cared too much about privacy back then. Therefore nothing special was needed to decode the inputs. The only exception could be that we have to decode the input several times until we get the right answer (which should be clear once we do one step and we receive something readable, such as a plain text in the easy test case).

Easy test case

When we look at the numeric values, it should be evident that the range of numbers present is quite small. A frequency analysis of these numbers should very closely match that of normal English text - without any permutation at all. Yes, it is as simple as subtracting a fixed constant and using the result as an ASCII code; given the above, it is easy to find out that the additive constant is 9847, and the text then reads:

The method relies on the confirmed design outlined in the recent little-known  
work by H. Elang et al. in the field of programming languages. All of this may  
or may not actually hold in reality. Next, on a similar note, despite the  
results by Sleigh and Waterson, we can prove that virtual machines and the  
memory bus are largely incompatible. Even that physicists generally postulate  
the exact opposite, Ringy-pug depends on this property for correct behavior.  
In our application we do not require such a typical storage to run correctly,  
but it doesn’t hurt. Surely, this is a robust property of Ringy-pug. Although  
end-users rarely assume the exact opposite, our algorithm depends on this  
property for correct behavior. Nevertheless, we assume that each component of  
our application provides multimodal communication, independent of all other  
components. Despite the fact that computational biologists entirely believe  
the exact opposite, our application depends on this property for correct  
behavior. Our software was hand hex-editted using Microsoft developer’s studio  
built for Inter-Zero’s toolkit for topologically controlled e-commerce. Even  
though Rutherford et al. also proposed this method, we harnessed it  
independently and simultaneously.

Clearly, this was a step in the right direction, but not the final one (the answer should be just one word).

The problem statement offers a hint – look for the ANSWER. And indeed, it is easy to find these uppercase letters in the first part of the text. Reading all the capital letters yields:


From this the correct answer, ”RANDOMIZER”, is clear now.

The sample shell script to solve this task is very simple:

cat f-easy.txt | tr " " "\n" | ( while read a; do printf "%02x" $((a-9847)) ; done ) |  
xxd -r -p | tr -cd "[:upper:]"

Hard test case

The first thing one would imagine is that those letters might describe some floating-point numbers since all of them contain a dot somewhere in the middle.

Once we have (even) number of floating-point numbers, what would you do with them? Treat them as coordinate pairs? Plot those points somehow? Yes, that sounds quite well, so let’s try it this way.

How can we represent numbers with letters? Are they encoded in Base-26? Doesn’t seem so… This is where having two messages helps, we can notice the patterns. It seems that the messages differ only locally, and the set of differences is small. For example, BA is the same as K.

If we harvest the entire set of differences, everything should be pretty obvious: the letters A to Z represent the strings 0 to 25. Thus, for example, FN.L is 513.11.

Now let’s try to plot these coordinate pairs. The easiest way is to use gnuplot with a little preprocessing (putting 2 numbers on a line) and using something like this within gnuplot:

set pointsize 0.5  
plot "f-hard.xy" with points 3  
(or better:  plot [:][300:0]"f-hard.xy" with points 3)

What do we see? A text? Well, that can’t be just a coincidence, can it?


So let’s move to the next step. It does look as some Latin text (and those of you speaking Latin will probably notice quickly that it doesn’t really make sense); however, googling for its 2 first words, ”Lorem ipsum”, shows us what it is: a popular placeholder text used in publishing and design. There are several versions, but this one is the most common one:

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. For more information about this piece of text, see http://en.wikipedia.org/wiki/Lorem_ipsum

And what to do now? Do we have exactly the same version as the one above? Actually, we don’t. In our version, there are several extra words:

draco dormiens nunquam titillandus

Another Latin text, but much shorter. Let’s try to google once again – the answer, HOGWARTS, should be clear (it is a motto of Hogwarts School of Witchcraft and Wizardry).