#!/usr/bin/perl

use strict;

# number of people in the room
my $people = shift || 0;
# how many times to run the simulator
my $iterations = shift || 0;

if ($people eq 0 || $iterations eq 0){
	print "E: you so stupid\n";
	exit 1;
}

my %results = ();
srand($$); # good enough for our purposes

# run the simulator $iterations times
for (my $i=0; $i<$iterations; $i++){
	my $winner = &pick_winner;
	$results{$winner} = $results{$winner} + 1;
}

# print the results
foreach my $key (keys(%results)){
	print "$key = $results{$key}\n";
}

sub pick_winner
{
	&debug("pick_winner");
	my $winner = 0;
	my $bit = 0;

	# populate the room with all the people
	my %room = ();
	for (my $i=0; $i<$people; $i++){
		$room{$i} = 1;
	}
	foreach my $key (keys(%room)){
		&debug("key=$key");
	}

	while (1){
		# flip the coin. 1 = heads, 0 = tails
		my $flip;
		if (int(rand(10)) > 4){
			$flip = 1;
		}
		else{
			$flip = 0;
		}
		my $round = 1 << $bit;
		&debug("flip=$flip, round=$round");

		# walk around the room and eliminate everyone who is not a
		# possible winner
		my $left = 0;
		foreach my $contestant (keys(%room)){
			&debug("contestant=$contestant,contestant&round=" . ($contestant & $round));
			my $match = 0;
			$match = 1 if ($contestant & $round);
			if ($match ne $flip){
				# kick the person out of the room
				delete $room{$contestant};
			}
			else{
				$left++;
			}
		}
		foreach my $key (keys(%room)){
			&debug("key=$key");
		}

		# somehow we kicked out everyone. that's bad.
		if ($left < 1){
			&debug("emptied the room, no winner");
			return -1;
		}
		# we have our single winner remaining
		if ($left eq 1){
			&debug("found a winner");
			@_ = keys(%room);
			return $_[0];
		}

		$bit++;
		&debug;
	}
}

sub debug
{
	my $msg = shift;
	#print "D: $msg\n";
}