#!/usr/bin/ruby -w

# A solution to the 'Switch Room' puzzle,
# http://www.cartalk.com/content/puzzler/transcripts/200305/index.html
#
# It's a little chatty, so run it with
#   $ ./switch.rb > /dev/null
# to reduce the clutter.  It should complete within a few seconds.
#
# Copyright Nick Willson, nick@acrasis.net.
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License version 3, as
# published by the Free Software Foundation.  The text of the license is
# at http://www.gnu.org/licenses/gpl.html

require 'set'
HOW_MANY_PRISONERS = 23

# Make booleans look like switches.
class TrueClass; alias_method :old_to_s, :to_s; def to_s; "on"; end; end
class FalseClass; alias_method :old_to_s, :to_s; def to_s; "off"; end; end

# The switch room.
class SwitchRoom

   # The switches.
   attr_reader :left, :right
   # Remember the visitors in order to verify the claim that all have visited.
   attr_accessor :visitors

   def add_visitor (prisoner)
      self.visitors.add(prisoner)
   end

   def initialize
      # initialize switch randomly.
      self.left = [true, false][rand(2)]
      self.right = [true, false][rand(2)]
      self.visitors = Set.new
      puts("Switches initially: #{self}")
   end

   # Change the left switch to its other position.
   def invert_left
      self.left = ! self.left
      puts("left: #{self.left}")
   end

   # Ditto right switch.
   def invert_right
      self.right = ! self.right
      puts("right: #{self.right}")
   end

   # For printing self's switches' state.
   def to_s; "#{self.left}, #{self.right}"; end

   # Verify that self and rhs differ by exactly one switch position.
   def verify_one_switched (rhs)
      one_switched =
         (self.left == rhs.left && self.right != rhs.right) ||
         (self.left != rhs.left && self.right == rhs.right)
      raise "Uh oh! #{rhs} went to #{self}" unless one_switched
   end

private
   def left= (bool); @left = bool; end
   def right= (bool); @right = bool; end

end
#------------------------------------------------------------------------------

# Class for any prisoner.
class Prisoner
   # Self's memory of the switch room on completing self's last visit.
   # Self's name.
   attr_accessor :last, :name

   def initialize (name)
      self.last, self.name = nil, name
   end

   # Self has not visited the switch room before.
   def first_visit?; self.last.nil?; end

   # Since completing self's last visit, the left switch went from off to on.
   def left_turned_on?; self.last && !self.last.left && $sr.left; end

   # Ditto on to off.
   def left_turned_off?; self.last && self.last.left && !$sr.left; end

   # Similarly for the right switch
   def right_turned_on?; self.last && !self.last.right && $sr.right; end
   def right_turned_off?; self.last && self.last.right && !$sr.right; end

   def to_s; "#{self.name}" end

   # Self visits the switch room and makes his choice.
   def visit_switchroom
      puts("Prisoner #{self}")
      $sr.add_visitor(self)
      before_choice = $sr.dup
      make_choice
      # Verify that self really did switch exactly one switch.
      $sr.verify_one_switched(before_choice)
      # Remember the state of the switch room as self left it.
      remember_sr
   end

protected
   # Concrete classes override this.
   def make_choice; raise "Not implemented!"; end

private
   def remember_sr; self.last = $sr.dup; end

end
#------------------------------------------------------------------------------

# The prisoner chosen as the 'counter', the one who decides when
# to call the warden.
class Pcounter < Prisoner
   class CallWarden < RuntimeError; end
   attr_accessor :count_of_visitors, :i_turned_left_off
   def initialize (*args)
      super
      self.count_of_visitors = 0
      self.i_turned_left_off = false
      raise "I'm not called C but \`#{self.name}'!" unless 'C' == self.name
   end

   # Self increments his count of visitors on seeing that someone else
   # turned the left switch off.  Until the first time self observes that,
   # self keeps switching the left switch back and forth, so that another
   # prisoner can know to switch the left switch off.
   def make_choice
      if self.first_visit?
         # Switch left to off if it's on.
         if $sr.left
            $sr.invert_left
            self.i_turned_left_off = true
         else
            $sr.invert_right
         end
      elsif self.i_turned_left_off
         self.i_turned_left_off = false
         $sr.invert_left
      elsif left_turned_off?
         self.count_of_visitors += 1;
         puts("count_of_visitors #{count_of_visitors}")
         raise(CallWarden.new) if
            HOW_MANY_PRISONERS == self.count_of_visitors.succ
         $sr.invert_left
      else
         self.i_turned_left_off = $sr.left
         $sr.invert_left
      end
   end

end
#------------------------------------------------------------------------------

# A 'rank and file' prisoner.  His task is to 'announce' to the counter
# that he has visited.
class Pother < Prisoner
   attr_accessor :switched_left_off
   def initialize (*args)
      super
      self.switched_left_off = false
   end

   # The first time self sees the left switch turned on, self turns it
   # off.  That is the one and only time self turns the left switch off.
   def make_choice
      if self.first_visit?
         $sr.invert_right
      elsif self.switched_left_off
         $sr.invert_right
      elsif left_turned_on?
         $sr.invert_left
         self.switched_left_off = true
      else
         $sr.invert_right
      end
   end
end
#------------------------------------------------------------------------------

# Main starts here.

# Array of ASCII codes, one for each prisoner, in random order.
NAMES = ('A'[0]..('A'[0] + HOW_MANY_PRISONERS - 1)).to_a.sort_by { rand }
PASSES = 100
total_visits = 0
PASSES.times do |pass|

   $sr = SwitchRoom.new
   prisoners = NAMES.collect do |ascii_nbr|
      nm = ascii_nbr.chr
      'C' == nm ? Pcounter.new(nm) : Pother.new(nm)
   end
   count_of_visits_this_pass = 0
   while true
      begin
         p = prisoners[rand(HOW_MANY_PRISONERS)]
         count_of_visits_this_pass += 1
         p.visit_switchroom
      rescue Pcounter::CallWarden
         STDERR.puts(
            "Pass %2d, warden called on visit %4d, room says %2d/%2d" %
            [  pass, count_of_visits_this_pass,
               $sr.visitors.size, HOW_MANY_PRISONERS
            ]
            )
         raise "Failed!" unless HOW_MANY_PRISONERS == $sr.visitors.size
         total_visits += count_of_visits_this_pass
         break
      end
   end

end

STDERR.puts("Average visits per pass: #{total_visits/PASSES}")
exit(0)