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.¹

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 and highly readable ;)

Last edited at over 1 year ago