The Cracked Labyrinth

If you notice that this post is different from all my others, you'd be right! My very good friend (and one of the most loyal followers of this blog), Darrell Good wrote this as a guest post. I think he did a spectacular job on this post and if you want to let him know, send a message here and I'll forward it to him:

SPOILERS AHEAD!

If you're interested in solving my labyrinth puzzle, do not continue reading! Instead, click below to see the puzzle and try it for yourself. Darrell doesn't give you the answer, but he does have a few spoilers:

labyrinth

This one’s for all my treasure-hunting friends ;) We all know the story of the labyrinth. King Minos made the gods angry so they punished everyone around him instead of meeting him face to face. In due time, Minos hid his shame inside a torturous, tortuous prison without so much as

tateTate Shannon

I have to say, Darrell is one of the more brilliant people I've ever met. He was the third to solve the puzzle, and he solved it in such a creative way that I invited him to make this post.

Now, sit back, relax and enjoy my first-ever guest post!

-- Tate

The Cracked Labyrinth

By some reckoning, the measure of a craftsman is his ability to make his own tools. Carpenters build jigs, patterns, braces, and speed squares, to facilitate their work. Blacksmiths, using only a hammer, anvil and forge can recreate the tongs, punches, clamps and other tools that make up the arsenal in a smithy.

And programmers or software engineers, while not quite craftsmen in the traditional sense, do this perpetually by building functions and scripts. Like an iron tool, each block of code can be used, repurposed, or even heated in the furnace of some text editor and reformed entirely. So, when a new job is assigned or a new problem encountered, the engineer, like the smith before him, need not simply attack it with his base-line toolset but can borrow and customize his very tools to conquer it.

In my case, the problem at hand was a certain word puzzle, “The Labyrinth”, posed a few months ago on this blog. (If you haven’t already attempted it, stop reading now and go try! It is quite a challenge and the rest of this article will make more sense.)

The second half of the puzzle consists of unscrambling the (seemingly random) set of letters “notWenruatoniMcInehTsa”. After staring at them for a while and making only marginal progress, I had a sudden revelation. It was only a word puzzle. Why should I waste 30 minutes of my life in solving it when I could spend several hours writing the code to get a computer to do it for me!

I did first try finding one online, but these proved very scarce indeed. The only thing even close to a phrase unscrambler was a variety of Scrabble word generators. These, however, only gave the words that could be written with the given letters, not phrases, and most of them were limited to a handful of characters. So, I built my own.

Step 0: State the assumptions:

• The phrase is in English. I did briefly consider Latin or Greek as those would have been the language of the original myth(s), but I didn’t think Tate would be quite that cruel.
• All the needed letters are present, there are no duplicates, and there are no extras. In other words, it is a simple unscrambling, or permutation problem.
• Capital letters indicate the first letters of words. This means that there are only 4 words, starting with W, M, I, and T.

Before we continue, a bit of math is useful to determine if this is even a feasible project. We are trying to unscramble the letters “notWenruatoniMcInehTsa _ _ _”, with the three spaces representing the spaces between the four words. That is a total of 25 characters, the total number of ways of which to rearrange is “only” 25! That’s 25 factorial, which equals about 1.5×10²⁵ (about 15,000,000,000,000,000,000,000,000, or fifteen septillion). (The number of arrangements is actually less than that because of duplicates. The actual number is closer to 10²⁰ (100,000,000,000,000,000,000, or one hundred quintillion). That would still take my computer thousands of years to process. Maybe this is why there are no online unscrambling engines…)

However, there is hope. Remember, these are words, not random strings of letters, and there are a “measly” 170,000 or so words in current English. Plus, we even know what the words start with, which limits our options further. To iterate through all of these takes only a fraction of a second.

As an aside, this is why one should never, ever use passwords made up only of real words. They are far easier for the baddies to crack.

Step 1: Decompose problem

1. Find creatable words that start with T, I, W, or M.
2. Find combinations of those words that have the same number of letters as the original string.
3. Figure out which one is most likely correct.

Step 2: Define terms:

What does it mean for a word to be creatable? You might have an intuitive understanding or a working definition. My computer does not.

Does it mean that word is only composed of characters from the original string? Well, sort of.

The word “BANANA” is only composed of the letters “A”, “B”, and “N”, but you can’t unscramble “ABN” into the word “BANANA.” There simply are not enough letters to go around.

For a computer, figuring out if a word is “creatable” involves using a tool called a histogram. Basically, a histogram is just a table of the letters in a word and the number of times they appear (the frequency). For instance:

"MISSISSIPPI"

"BANANA"

If the histogram for a word is smaller (each frequency is smaller or the same) than the histogram of the original letters, then that word can be created.

So “BANANA” can be created from the letters “AN ANT AND A BAT”, but not “BAN”

Tada!!!🎉🎉 We have defined creatable!

Step 3: Solve the Problem!

Using the histogram on a database of English words and checking if each one is “smaller” than the original string of letters gives all the words that could possibly be in the phrase. Of these, I only need those that start with T, W, I, and M.

The correct phrase is some combination of these words, but which one? Through some educated guesses, I knew the word starting with “M” at this point, but there are still ~2 million other combinations to sort through!

Here our tool the histogram comes to the rescue once again. For each of the 2 million combinations, we check if the histogram of that phrase is identical to that of the original letters.

“Tenaces Whence Instance Meanest”  ❌

“Toes Whence Instance Meanest”        ❌

“Theta Whence Instance Meanest”      ❌

…

“Tech Wont Insane Minotaur”               ✔️

…

There are only ~800 of these, and it would be possible just read over all of them. The correct one would jump out before long.

However, that is not quite good enough. I want something that will give me THE most likely phrase. To do this, I can borrow a tool from someone else’s “shop”. (They are called libraries in python). This tool, “wordfreq”, gives a rating to any word you give it, based on how often it is used in everyday speech. So “Toes” is higher rated than “Tenaces”, “Was” higher than “Whence”, and so on.

Adding the scores of each word in each of the phrases gives a cumulative score for that phrase, and the ones with the highest scores are most likely to be right. And indeed, the top answer is correct!

“______ ____________ ________ __________”

But you will have to download the code and run it out for yourself. I’m not going to give it to you! You can get the code here:

GitHub - darzgood/unscrambled: unscrambles phrases from given letters

unscrambles phrases from given letters. Contribute to darzgood/unscrambled development by creating an account on GitHub.

GitHubdarzgood

Alternatively, one could just look at the puzzle and figure it out old-school, the way it was meant to be played. It might take a while, but you would probably get it. And in a lot of ways, that is astounding. Even with all the optimizations we talked about, there are still thousands of different ways to unscramble the puzzle, and our slow, measly human brains can still pick out the right one! Our ability to recognize patterns and derive meaning out of the world around us is a core part of what makes us human. Well, that and making tools.

“For you created my inmost being;
    you knit me together in my mother’s womb.
 I praise you because I am fearfully and wonderfully made.”
-- Psalm 139:13-14