Zebra Puzzles in Ruby

From Zebra Puzzle‘s wiki page we know that:

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 ;)