#!/usr/bin/env perl
#
# Solution to the problem presented at 
# http://www.techinterview.org/Puzzles/twoswitches.html
#
use strict;
use warnings;

use Data::Dumper;

my $num_prisoners = shift || 23;

# Name all the prisoners
my @prisoners = map { "p$_" } (1..$num_prisoners);

# The switchbox
my %switches = (
                'A' => int rand(2),
                'B' => int rand(2),
                );

# Copy of the switchbox, solely for reporting purposes 
# at the end of the test.
my %initial_state = %switches;

# Who's toggled what, and how many times
my %toggled;

# This is explained in the while() loop. :-)
my $booger_on_wall;

$SIG{'INT'} = \&dump_state;

# Print the initial state.
printf("     [ %s, %s ]\n", @switches{'A', 'B'});

my $visits;
while ( my $prisoner = $prisoners[rand @prisoners] ) {
    ++$visits;

    # Since we don't know the initial position of the switches
    # before the test begins, we'll have to wait for p1 to put
    # them in an agreed-upon state. We'll say that before anyone
    # other than p1 can touch switch A, the switch must be in the
    # down (0) position. Once switch A is in the up (1) position,
    # only p1 can turn it off, when he does, he increments his counter.
    # If the switch is up already, there are two possibilities...
    # either someone else flipped it up, or this is the initial
    # state of the switch. 
    # 
    # If we assume that this is the intial state, when in fact
    # it is up because someone else flipped it, we'll have an
    # off-by-one error that will leave us in jail forever
    # since we never counted the first guy's flip.
    #
    # If we assume that someone else has flipped the switch before
    # p1 got here, we run the risk of an off-by-one error that will
    # get us all killed.
    #
    # This sucks, so we'll have a little rule that says that nobody
    # is allowed to touch the first switch until p1 has initialized
    # it to the off position. How do we communicate to the other 
    # prisoners that p1 has been in the cell? Easy...p1 puts a booger
    # on the wall above the switchplate to let the other guys know
    # that if they see switch A in the off position, they can toggle
    # it up. :-)
    my $switch;
    if ( ! $booger_on_wall ) {
        if ( $prisoner eq 'p1' ) {
            print "** booger **\n";
            $booger_on_wall = 1;
            $switch = ( $switches{'A'} ) ? 'A' : 'B';
            toggle(\%switches, $prisoner, $switch);
            next;
        } else {
            $switch = 'B';
        }
    } else {
        # If A is down and the prisoner has never toggled
        # the 'A' switch before, it's his turn to toggle it.
        if ( $prisoner eq 'p1' ) {
            $switch = ( $switches{'A'} ) ? 'A' : 'B';
        } elsif ( $switches{'A'} == 0 and 
                  not $toggled{$prisoner}{'A'} ) 
        {
            $switch = 'A';
        } else {
            $switch = 'B';
        }
    }

    ++$toggled{$prisoner}{$switch};
    
    toggle(\%switches, $prisoner, $switch);

    # If prisoner p1 has flipped A down one minus the number
    # of prisoners times, he knows
    # for certain that everyone else has visited the cell.
    my $p1_A_toggle_count = $toggled{'p1'}{'A'};
    if ( $prisoner eq 'p1' and 
         $p1_A_toggle_count and 
         $p1_A_toggle_count == $#prisoners ) 
    {
        print "All prisoners have been in after $visits visits\n";
        dump_state();
    }

}

sub dump_state {
    print Dumper { 
        initial_state => \%initial_state,
        been_in       => scalar(keys %toggled),
        toggled       => \%toggled,
    };
    exit;
}

sub toggle {
    my ($switches, $prisoner, $switch) = @_;

    $switches->{$switch} = ( $switches->{$switch} ) ? 0 : 1;

    my $marker = "";
    if ( $switch eq 'A' ) {
        $marker = ( $prisoner eq 'p1' ) ? "+++" : "x";
    }

    printf("%3s: [ %s, %s ] %s\n",
           $prisoner,
           @{$switches}{'A', 'B'},
           $marker);
}