prisoner hat riddle

prisoner_hat.md

Answer

The tallest prisoner counts the white hats in front of him. If odd, he calls out "white"; if even he calls out "black".

Then each prisoner down the line makes the same calculation. If the color they compute is different from what was called out before them, they know their color is "white"; if it's the same, their color is "black". They call out their color.

Reasoning

The secret is the shared information each prisoner has: they can see everyone's hat who is shorter than they are. So progressing from shortest to tallest, each prisoner adds one bit of information. The tallest is missing one bit, but fortunately the puzzle only requires that N-1 have the right answer. :)

Let's assign value 1 to white and 0 to black.

The number of white hats visible to any prisoner is the XOR of the hat value of everyone shorter than they are. So an even number of white hats will XOR to 0; an odd number will XOR to 1. Every prisoner can compute their XOR value by looking at those who are shorter. The shortest sees none so he defaults to 0.

The tallest prisoner starts with a guess that the previous prisoner called out "black" (0).

Each prisoner hears the previous prisoner's color, and knows his owh visible XOR value. If they match, he knows his hat didn't flip the XOR, so it is "black" (0); if different, he knows his hat did flip the XOR, so it is "white" (1).

prisoner_hat.rb

class Hat
  attr_reader :index
  
  COLORS = ["black", "white"]
  COLORS_TO_INDEX = COLORS.map.with_index { |color, index| [color, index] }.to_h
  INDEXES = COLORS_TO_INDEX.values
  
  def initialize(color_or_index)
    @index = COLORS_TO_INDEX[color_or_index] || color_or_index
    INDEXES.include?(@index) or raise "value #{color_or_index.inspect} must be one of #{COLORS + INDEXES}"
  end
  
  def color
    COLORS[@index]
  end
  alias :to_s :color
  
  def ^(other)
    self.class.new(index ^ other.index)
  end
end

class Prisoners
  def initialize(hats)
    @hats = hats
  end
  
  def shout_out(index = @hats.size - 1, previous = Hat.new(0))
    visible = visible_xor(index)
    my_hat = visible ^ previous
    puts "[#{index}] #{my_hat}! (Because visible XOR is #{visible} and previous was #{previous}.)"
    shout_out(index - 1, visible) unless index.zero?
  end
  
private
  def visible_xor(index)
    @hats[0...index].reduce(Hat.new(0), &:^)
  end
end

puts "Enter hat colors from tallest to shortest"
hats = STDIN.each_line.map { |line| unless (chomped = line.chomp).empty?; Hat.new(chomped); end }

prisoners = Prisoners.new(hats.reverse)

prisoners.shout_out

the_input.txt

black
white
black
white
black
white
white
white
black
black

the_output.txt

$ ruby prisoner_hat.rb < the_input.txt
[9] white! (Because visible XOR is white and previous was black.)
[8] white! (Because visible XOR is black and previous was white.)
[7] black! (Because visible XOR is black and previous was black.)
[6] white! (Because visible XOR is white and previous was black.)
[5] black! (Because visible XOR is white and previous was white.)
[4] white! (Because visible XOR is black and previous was white.)
[3] white! (Because visible XOR is white and previous was black.)
[2] white! (Because visible XOR is black and previous was white.)
[1] black! (Because visible XOR is black and previous was black.)
[0] black! (Because visible XOR is black and previous was black.)