#!/usr/bin/env ruby

TRIALS=100000

# Array of Knighs: BalIn and BalAn, and some schmucks.
KNIGHTS=["I","A","X","X","X","X","X","X"] 

# The knights are equally matched, so we need to randomize
# the selection of who wins each round.  Otherwise, this is
# very similar to problem16.rb.

# We're going to abuse the weak typing of ruby here.  Don't 
# do this for real.  
#
# Returns an array if we just continue on, returns nil if the
# brothers meet.
#
def round(seedings)
  next_round = []

  # Walk the seedings pairwise, looking for "A" and "I"
  # Note that order doesn't matter.

  i = 0
  while (i < seedings.length())
    return nil if (["A","I"] & seedings[i..i+1]).length == 2 # rubylicious.
    next_round.push( seedings[i + rand(2)] )
    i += 2
  end
  return next_round
end

def tourney()
  first_round = KNIGHTS.shuffle
  quarters = round(first_round)
  return true if !quarters

  semi = round(quarters)
  return true if !semi

  final = round(semi)
  return true if !final

  return false # tourney over
end

srand() # Our first call to shuffle is before our
        # first call to rand()...

n_match=0
TRIALS.times do
  n_match += 1 if tourney()
end

puts "In #{TRIALS} trials, the brothers met #{n_match} times."
puts "P=#{n_match/TRIALS.to_f}"