Internationali­zation Puzzles

Gulliver's puzzle dictionary

Your mind is terribly foggy when you are awakened by the morning sun's rays. A storm... a ship wreck... You appear to be on a beach. You try to move but you can't. You discover that your hands and feet are tied down by innumerable tiny ropes. You must still be dreaming, because next you see a tiny person, no larger than your thumb. He climbs up a ladder, sits on your chest, and starts talking.

He explains that he is from the illustrious empire of Lilliput. He implores your assistance in a matter of grave national importance, namely solving his crossword puzzle1. With your giant stature, he reasons, you must clearly be of great power and intellect. Solving the puzzle would bring glory to his nation. He promises to set you free if you solve the problem. Not seeing any other choice, you grudgingly agree.

To explain, he starts with an example:

   ..s....
  ...w..
 ....i
.....f..
    .t.......

You must fill in a word in each row. The word has to fit the letters that are already there. The vertical lines (columns) do not need to form a word, except for the single word swift that is already filled in.

The test input comes with an encoded test dictionary. You may only use words from the dictionary that you're given. 

616e77c3a4686c65
796c74e46de47373e4
efbbbf73796b6b696dc3a46bc3b6
0070006f00eb0065006d
feff0069007400e4007000e400e4006800e4006e
61757373e46774
626c6173c3a9
637261776cc3a9
6c00e20063006800e2007400
64657370656e68e1
6c6964e172656973
fffe6700e20063006800e9006500
6500700069007400e100660069006f00
feff007300fc006e006400650072006e
fffe7200f600730074006900

This dictionary has been compiled by a committee with representatives from the nations of Lilliput, Blefuscu, Laputa and Balnibarbi. The trouble is that the representatives could never come to an agreement on what encoding to use.

The Lilliputians encode words with utf-16 le (little endian). When writing a 16 bit word, obviously they write the little end (lower byte) first, in the same way that they crack the little end of their boiled egg for breakfast2.

Blefuscudians encode words with utf-16 be (big endian), because the mean Blefuscudians have not yet unlearned their wicked ways, and they write the big end (higher byte) first for any 16 bit pair.

The Laputians, from their lofty floating island, use utf-8 encoding. Just use utf-8 everywhere they say, and everything will be perfect! Unfortunately, down here on earth, some of us have to work with legacy systems that can not be upgraded.

Finally, the poor Balnibarbis are stuck in the past using latin-1 encoding, a.k.a ISO-8859-1.

Each line of the dictionary is a sequence of bytes encoded in hexadecimal. For example, 616e77c3a4686c65 represents the bytes 61 6e 77 c3 a4 68 6c 65. If you decode this using utf-8, you get the word: 'anwähle'. Unfortunately this word doesn't fit in the puzzle anywhere, so you'll have to look further. Take instead the hexadecimal '61 75 73 73 e4 67 74'. Applying latin-1 encoding, you can convert this to 'aussägt'. This word fits perfectly on the first row.

"And then there is the BOM of course", your lilliputian hostage taker continues.

"A bomb? Where?", you ask. You try to move your arms to protect your face, but all the tiny ropes prevent this.

"No, a Byte Order Marker".

See, in an attempt to clarify the confusion, the dictionary committee started adding these markers. Take for example fe ff 00 69 00 74 00 e4 00 70 00 e4 00 e4 00 68 00 e4 00 6e. The first two bytes, FE and FF, together form a BOM, which can be used to deduce that we're dealing with big-endian utf-16. Thus we can determine that this word reads itäpäähän. The byte order mark does not occupy any space, so we have to ignore it when fitting words in the puzzle. BOMs are supported in utf-8 and utf-16, but not in latin-1. And even then, not every string starts with a BOM like it should.

Now it's up to you to deduce which line uses which encoding. For example, by carefully studying the properties of the four different encodings, you can determine that each line of the test dictionary can be decoded as follows:

The solution of the puzzle then looks like this:

   aussägt
  crawlé
 rösti
epitáfio
    itäpäähän

To calculate your final result, take the sum of the row numbers of the words that form your solution. For example, aussägt is the 6th word. So take 6 + 8 + 15 + 13 + 5 and the final result is 47.

What is the sum of the row numbers of the words that complete the puzzle in your input?

  1. This type of puzzle is called Filippine in Dutch - It's not quite like an acrostic. I'm not aware of a good English translation. ↩

  2. See gulliver's travels ↩

To play, please log in with one of these options:
GitHub Login | Google Login