# Zebra Puzzles in Ruby

From Zebra Puzzle’s wiki page we know that:

• There are five houses in a line, each house with an owner, a pet, a cigarette, a drink, and a color
• The Englishman lives in the red house.
• The Spaniard owns the dog.
• Coffee is drunk in the green house.
• The Ukrainian drinks tea.
• The green house is immediately to the right of the ivory house.
• The Old Gold smoker owns snails.
• Kools are smoked in the yellow house.
• Milk is drunk in the middle house.
• The Norwegian lives in the first house.
• The man who smokes Chesterfields lives in the house next to the man with the fox.
• Kools are smoked in the house next to the house where the horse is kept.
• The Lucky Strike smoker drinks orange juice.
• The Japanese smokes Parliaments.
• The Norwegian lives next to the blue house.

And if we use number 1 to 5 to represent each of these unique things (house, color, nationality, animals, drinks, cigarettes).

With immediately to the right and next to methods defined like so:

```def immediate_right?(h1, h2)
(h1 - h2) == 1
end

def next_to?(h1, h2)
(h1 - h2).abs == 1
end
```

Then we translate above statements into the only legit use case of `for` loop here:

```def zebra_puzzle
houses = [*1..5]
first = 1
middle = 3
orderings = houses.permutation

for red, green, ivory, yellow, blue in orderings do
for englishman, spaniard, ukrainian, japanese, norwegian in orderings do
for dog, snails, fox, horse, zebra in orderings do
for coffee, tea, milk, oj, water in orderings do
for oldgold, kools, chesterfields, luckystrike, parliaments in orderings do
if englishman == red &&
spaniard == dog &&
coffee == green &&
ukrainian == tea &&
immediate_right?(green, ivory) &&
oldgold == snails &&
kools == yellow &&
milk == middle &&
norwegian == first &&
next_to?(chesterfields, fox) &&
next_to?(kools, horse) &&
luckystrike == oj &&
japanese == parliaments &&
next_to?(norwegian, blue)

return water, zebra
end
end
end
end
end
end
end

zebra_puzzle # => [1, 5]
```

This works and is very easy to understand.

But this will take hours to run because `5!^5 ≃ 24 billion` (5 house with 5 properties). I’m on a 2.9GHz MacBook Pro, which can execute 3 machine instructions in 1ns. let’s optimistically say that giant if statement takes 100 instructions to run.1

```24 billion * 100 instructions = 2400 billion instructions
2400 billion instructions / 3 / 1ns = 8000 seconds
8000 seconds = 133.3 minutes = 2.22 hours!
```

We could actually avoid computations by moving conditions not satisified we know for sure as early as we can. This rules out a lot of computations!

```def zebra_puzzle
houses = [*1..5]
first = 1
middle = 3
orderings = houses.permutation

for red, green, ivory, yellow, blue in orderings do
next if !immediate_right?(green, ivory)

for englishman, spaniard, ukrainian, japanese, norwegian in orderings do
next if englishman != red
next if norwegian != first
next if !next_to?(norwegian, blue)

for dog, snails, fox, horse, zebra in orderings do
next if spaniard != dog

for coffee, tea, milk, oj, water in orderings do
next if coffee != green
next if ukrainian != tea
next if milk != middle

for oldgold, kools, chesterfields, luckystrike, parliaments in orderings do
if oldgold == snails &&
kools == yellow &&
next_to?(chesterfields, fox) &&
next_to?(kools, horse) &&
luckystrike == oj &&
japanese == parliaments

return water, zebra
end
end
end
end
end
end
end

zebra_puzzle # => [1, 5]
```

Now this runs around 100ms, which is quite acceptable ;)