Einstein's Puzzle

einstein.rb

# There are five houses in five different colors 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.

# The question is: who owns the fish?

time_start = Time.now

@house_numbers = [:one, :two, :three, :four, :five]
@all_house_numbers = @house_numbers.permutation.to_a

@colors        = [:yellow, :blue, :red, :green, :white].shuffle
@cigars        = [:dunhill, :blends, :pall_mall, :prince, :bluemasters].shuffle
@nationalities = [:norwegian, :danish, :british, :german, :swedish].shuffle
@drinks        = [:water, :tea, :milk, :coffee, :beer].shuffle
@pets          = [:cats, :horses, :birds, :fish, :dogs].shuffle

@empty_houses = {
  one:   {color: nil, cigar: nil, nationality: nil, drink: nil, pet: nil,
          left_neighbour: nil, right_neighbour: :two},
  two:   {color: nil, cigar: nil, nationality: nil, drink: nil, pet: nil,
          left_neighbour: :one, right_neighbour: :three},
  three: {color: nil, cigar: nil, nationality: nil, drink: nil, pet: nil,
          left_neighbour: :two, right_neighbour: :four},
  four:  {color: nil, cigar: nil, nationality: nil, drink: nil, pet: nil,
          left_neighbour: :three, right_neighbour: :five},
  five:  {color: nil, cigar: nil, nationality: nil, drink: nil, pet: nil,
          left_neighbour: :four, right_neighbour: nil},
}

def generate_options_set(seed)
  options_set = []
  (0...5).each do |i|
    options = []
    @house_numbers.each_with_index do |_, j|
      color        = @colors.rotate(i)[(seed + j) % 5]
      cigar        = @cigars.rotate(i)[(seed / 5 + j) % 5]
      nationality  = @nationalities.rotate(i)[(seed / 25 + j) % 5]
      drink        = @drinks.rotate(i)[(seed / 125 + j) % 5]
      pet          = @pets.rotate(i)[(seed / 625 + j) % 5]

      options << {color: color, cigar: cigar, nationality: nationality, drink: drink, pet: pet}
    end
    options_set << options
  end
  options_set
end

def generate_house_arrangements(options_set)
  house_arrangements = []

  options_set.each do |options|
    @all_house_numbers.map do |arrangement|
      houses = @empty_houses.dup
      arrangement.each_with_index do |house_number, i|
        houses[house_number] = houses[house_number].merge(options[i])
      end
      house_arrangements << houses
    end
  end

  house_arrangements
end

class Object
  def try(method, args)
    return nil if self == nil
    send(method, args)
  end
end

@rules = []

# The Brit lives in the red house.
@rules << Proc.new {|houses| houses.values.any?{|house| house[:color] == :red && house[:nationality] == :british}}
# The green house is on the immediate left of the white house.
@rules << Proc.new {|houses| houses.values.any?{|house| house[:color] == :white && houses[house[:left_neighbour]].try(:[], :color) == :green}}
# The owner of the yellow house smokes Dunhill.
@rules << Proc.new {|houses| houses.values.any?{|house| house[:color] == :yellow && house[:cigar] == :dunhill}}
# The owner living in the center house drinks milk.
@rules << Proc.new {|houses| houses[:three][:drink] == :milk}
# The Norwegian lives in the first house. 
@rules << Proc.new {|houses| houses[:one][:nationality] == :norwegian}
# The owner who keeps the horse lives next to the one who smokes Dunhill. 
@rules << Proc.new do |houses| houses.values.any?{|house|
    house[:pet] == :horses &&
    (
      houses[house[:left_neighbour]].try(:[], :cigar)  == :dunhill ||
      houses[house[:right_neighbour]].try(:[], :cigar) == :dunhill
    )
  }
end
# The Norwegian lives next to the blue house.
@rules << Proc.new do |houses| houses.values.any?{|house|
    house[:nationality] == :norwegian &&
    (
      houses[house[:left_neighbour]].try(:[], :color)  == :blue ||
      houses[house[:right_neighbour]].try(:[], :color) == :blue
    )
  }
end
# The green house's owner drinks coffee.
@rules << Proc.new {|houses| houses.values.any?{|house| house[:color] == :green && house[:drink] == :coffee}}
# The Dane drinks tea.
@rules << Proc.new {|houses| houses.values.any?{|house| house[:nationality] == :danish && house[:drink] == :tea}}
# The owner who smokes Bluemasters drinks beer.
@rules << Proc.new {|houses| houses.values.any?{|house| house[:cigar] == :bluemasters && house[:drink] == :beer}}
# The German smokes Prince.
@rules << Proc.new {|houses| houses.values.any?{|house| house[:cigar] == :prince && house[:nationality] == :german}}
# The Swede keeps dogs as pets.
@rules << Proc.new {|houses| houses.values.any?{|house| house[:nationality] == :swedish && house[:pet] == :dogs}}
# The owner who smokes Pall Mall rears birds.
@rules << Proc.new {|houses| houses.values.any?{|house| house[:cigar] == :pall_mall && house[:pet] == :birds}}
# The owner who smokes Blends lives next to the one who drinks water.
@rules << Proc.new do |houses| houses.values.any?{|house|
    house[:cigar] == :blends &&
    (
      houses[house[:left_neighbour]].try(:[], :drink)   == :water ||
      houses[house[:right_neighbour]].try(:[], :drink) == :water
    )
  }
end
# The owner who smokes Blends lives next to the one who keeps cats.
@rules << Proc.new do |houses| houses.values.any?{|house|
    house[:cigar] == :blends &&
    (
      houses[house[:left_neighbour]].try(:[], :pet)  == :cats ||
      houses[house[:right_neighbour]].try(:[], :pet)  == :cats
    )
  }
end

class Symbol
  def humanize
    result = self.to_s
    result.gsub!('_', ' ')
    result.split(' ').collect{|part| part.capitalize }.join(' ')
  end
end

max_seed = (5 ** 5)
seed = 0

@winning_combo = {}

while seed < max_seed
  options_set = generate_options_set(seed)
  house_arrangements = generate_house_arrangements(options_set)

  threads = []

  house_arrangements.each do |houses|
    threads << Thread.new do
      if @rules.all?{|rule| rule.call(houses)}
        @winning_combo = houses
      end
    end
  end

  threads.each(&:join)
  break if @winning_combo.keys.count > 0
  seed += 1
  print '.'
end

puts "Solved in #{Time.now - time_start} seconds."

puts "\n\n"

@winning_combo.each do |k,v|
  puts "House #{k.to_s} is #{v[:color]}. The owner is #{v[:nationality].humanize}, smokes #{v[:cigar].humanize}, drinks #{v[:drink]}, and keeps #{v[:pet]}."
end

# Solved in 5.027282 seconds.
#
# House one is yellow. The owner is Norwegian, smokes Dunhill, drinks water, and keeps cats.
# House two is blue. The owner is Danish, smokes Blends, drinks tea, and keeps horses.
# House three is red. The owner is British, smokes Pall Mall, drinks milk, and keeps birds.
# House four is green. The owner is German, smokes Prince, drinks coffee, and keeps fish.
# House five is white. The owner is Swedish, smokes Bluemasters, drinks beer, and keeps dogs.