Solving Einstein’s Riddle with Ruby

Doing the rounds again at the moment is the so-called “Einstein’s Riddle”, a puzzle he allegedly described as being too difficult for 98% of the population to solve.

Also known as the Zebra puzzle, it involves deducing the nationality of inhabitants of a street of houses, the colour of those houses, and which drink, cigar and pet the occupant prefers.

There are five houses in five different colours in a row. In each house lives a person with a different nationality. The five owners drink a certain type of beverage, smoke a certain brand of cigar and keep a certain pet.

No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.

Other facts:

1. The Brit lives in the red house.
2. The Swede keeps dogs as pets.
3. The Dane drinks tea.
4. The green house is on the immediate left of the white house.
5. The green house’s owner drinks coffee.
6. The owner who smokes Pall Mall rears birds.
7. The owner of the yellow house smokes Dunhill.
8. The owner living in the center house drinks milk.
9. The Norwegian lives in the first house.
10. The owner who smokes Blends lives next to the one who keeps cats.
11. The owner who keeps the horse lives next to the one who smokes Dunhill.
12. The owner who smokes Bluemasters drinks beer.
13. The German smokes Prince.
14. The Norwegian lives next to the blue house.
15. The owner who smokes Blends lives next to the one who drinks water.

The question is: who owns the fish?

The specific attributes are interchangeable, but the puzzle always retains two key features: The number of possible combinations is enormous, and there is only one single valid combination that satisfies all the given facts.

Naïve Solution

In this puzzle, there are five sets of five options. Combinatorially, that works out at almost 25 billion combinations which is brute-forceable on a modern computer.

5! ×5! ×5! ×5! × 5! = 24,883,200,000

In a naïve solution, all we need to do is generate all possible combinations of colour, nationality, cigar, pet, and drink and then try them out with each house in the street. Every time we generate a new street, we test out the configuration against the facts we know — if any facts are contradicted then we move along to the next combination.

Ruby’s Array library has a handy method to help us out, Array#permutation.

This allows us to nest 5 loops in order to create every single valid street.

Now we need to think about how we check the facts laid out in the puzzle.

If we assume the ordering of each set to imply the house numbers then it makes our code quite simple as the house that each option appears in (colour, pet, cigar etc) matches its place in the array (assuming we index from one not zero) i.e.

Now we need to consider how to check whether the facts are validated. The simplest kind of fact in the puzzle is a statement of positional implication, i.e.

The owner living in the center house drinks milk.

or

The Norwegian lives in the first house.

We can easily test for this with an array index test:

The next type of fact matches two options into one house i.e.

The German smokes Prince.

In terms of predicate logic, we can define this rule as A→B, or “A implies B”. This means, if the cigar smoked in a certain house is “Prince” then the nationality of the occupant is German (and reflexively, B→A, since there can be no duplicates).

Rather than hardcoding that, let’s define a method #implies? that returns true or false for whether a house in the street contains both an occupant whose nationality is German, and an occupant who smokes Prince cigars.

Now we can define all the implies? facts as follows:

The next type of fact is an extension of the #implies? fact:

The green house is on the immediate left of the white house.

This is a simple twist on the #implies? fact test. Since we represent position as the ordering of the arrays, we can specify this as follows:

There’s a third type of fact that builds further on this i.e.

The owner who keeps the horse lives next to the one who smokes Dunhill.

This means the Dunhill smoker lives either to the left of the horse owner, or to the right. We can express this like so:

Ok! Now we have all the tools we need to check the known facts. Let’s put it all together.

Eventually (anywhere between minutes and hours) this will spit out the correct combination. If you still want to deduce the answer yourself, now would be a good time to bookmark this post for later ;-)

Scroll on for the answer…

=> [ [:yellow, :blue, :red, :green, :white], [:norwegian, :danish, :british, :german, :swedish], [:cats, :horses, :birds, :fish, :dogs], [:water, :tea, :milk, :coffee, :beer], [:dunhill, :blends, :pall_mall, :prince, :bluemasters]]

This translates to:

• House 1 is yellow. The owner is Norwegian, smokes Dunhill, drinks water, and keeps cats.
• House 2 is blue. The owner is Danish, smokes Blends, drinks tea, and keeps horses.
• House 3 is red. The owner is British, smokes Pall Mall, drinks milk, and keeps birds.
• House 4 is green. The owner is German, smokes Prince, drinks coffee, and keeps fish.
• House 5 is white. The owner is Swedish, smokes Bluemasters, drinks beer, and keeps dogs.

A faster implementation!

So we’ve got the building blocks for a solver for Einstein’s puzzle, but the algorithm is very inefficient. Because it uses nested loops, you can iterate over all of the interior loops before you get around to trying a new exterior combination i.e. if the colour permutation is wrong, you need to iterate through nationalities, pets, drinks and cigars before you switch to a new one.

Since only one permutation is correct, this means you have a 119/120 chance of starting with the wrong ordering and doing a whole heap of pointless tests in the process.

In terms of worst-case scenario, we’ll need to loop through all 24 billion combinations before reaching the correct one at the very end. Realistically, you’ll meet the combination on average in the middle somewhere, so you’ll average 12 billion tests before you get your answer.

Surely we can do better…

What if we could discount bad permutations at every level of iteration? We’d cut down the problem space significantly.

So we’ve cut down the problem space massively from 14,400 to 2,880 — that’s 80% smaller!

Let’s try this with the other facts, placing their tests at the right loop level.

Note our use of #shuffle when setting up the options. Without this, we’d get the same number of loops every single time we run the solver so it’s reassuring to see that it works in a sensible amount of time no matter what the initial ordering of the permutations is.

So now we have a solver that finds the correct solution in around 55,000 tests. That’s just 0.0002% of the number of tests needed by the naïve solver!

This runs consistently on my laptop in around a fifth of a second. Throw in some code to display it nicely and we’re about done with our smart solution.

Anyone for golf?

Since we’re mad on efficiency, how about we look at ways to get our solution squashed down super small? The solution above, with methods to display the code nicely works out at around 2,837 characters. How can we reduce that?

Short method names

We can save a lot of space by shrinking method names and arguments to single letters.

Simpler option representation

The content of our options doesn’t matter, so long as they’re all unique. May as well use integers

Merging left_of? with implies?

The #left_of? and #implies? methods are almost identical in their implementation so we can merge them into the same method.

Now we can throw away the #left_of? method and use i(a,b,c,d,1) instead.

Use #map instead of #each

We use the #each method to iterate over the collections of options in five places but Ruby’s #map method also iterates (and applies the block to every element, returning a new collection of the results). This saves us a few characters.

test || next

Instead of saying next unless for every test, we can suffix it with “ || next”. This way, if the test returns false, Ruby’s evaluates the other side of the || operator (OR) and skips to the next item in the iterator.

Alias the #permutation method

We use the permutation method five times. That’s 55 chars total. We can wrap this in our own def and claw back some more bytes.

Use curly braces

Instead of do..end, we can use {} to delimit our blocks.

Remove all unnecessary whitespace

Finally, we can remove all whitespace unless it forms part of a method call.

546 characters

With all these optimisations, we’ve shrunk our code down by more than 80%!

Pretty nifty! And that’s Einstein’s puzzle about done for me.

Full source on Github: https://github.com/seanhandley/einstein

EDIT: Thanks very much for all the comments folks! A lot of people have pointed out you don’t need code to solve this… and that’s true. I did it on pen and paper first and then thought “This’d be fun to solve with code!”. It’s definitely an enjoyable puzzle to do offline so don’t let all the code dissuade you from trying.