#!/usr/bin/ruby


if ARGV[0] == nil 
  print <<EOM;

This modifies the typical Swiss System to compute the first tie break
differently. See the posting by Karl Juhnke:
  http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=events;action=display;num=1255748924

The basic principles of a Swiss System tournament are:

   1. The number of rounds to be played is declared beforehand.
   2. Two players may play each other only once.
   3. Players are paired with others of the same score, or nearest score.
   4. When possible, a player is given the white pieces as many times 
       as he is given the black pieces.
   5. When possible, a player is given the colour other than that he 
       was given the previous round.
   6. The final ranking order is determined by the aggregate of points 
       won: 1 point for a win, 0.5 point for a draw and 0 point for a 
       loss. A player whose opponent fails to appear for a scheduled 
       game receives one point. 

A plain and simple swiss tournament.

Order the players by score from highest to lowest,
  then by sum of opponent score from highest to lowest
  then by pre-tournament rating from highest to lowest
  then by unique random number assigned at start of round

Player scores 2 for each win, 1 for draw, 0 for loss, 2 for bye.

If there is a an odd number of players the player at the
very bottom of the list gets a bye.

If a pair of players have already played before then they
cannot be paired again.

Pair the players from the top of the list to the bottom
as follows:

If the player is in the top half of the score group and
has not already been paired then
try to pair the player against the player in the bottom half
of the score group starting at the same relative position
in the bottom half as the player is in the top half. If a
pair cannot be made then continue down the list within
the same score group. After reaching the bottom of the 
score group then work upwords within the same score group.
If a match cannot be found within the same score group
then work down the list starting from the top of the
next score group.

If the player is in the bottom half of the score group
and has not already been paired then pair the player
against the next player below them in the list and continue
down the list until a pair is found.

Within each pairing the player who has played a color
fewer times plays that color. If both players have played
a color the same number of times then the even numbered
players play white and odd numbered player play black.
If still the same color then the color is assigned randomly.

The number of rounds should be:
  int(log(N)/log(2))+2  where N is the number of players.
or about
  int(1.3*log(N)/log(2))  where N is the number of players.


After the rounds are over order the players as defined
earlier and select the player at the top of the list as 
the winner.

Refrences for number of rounds:
http://www.oxfordcroquet.com/tech/appleton/index.asp
http://www.scoutingresources.org.uk/ideabase_swiss.html

EOM
  exit;
end

pa, xa, ga, ra, ph, rn = getTournState(ARGV[0]);

# make the round number a global variable
$rn = rn;

if (pa.length == 0)
  print "done\n"
  exit
end


# Determine number of loses for each player
#   field called 'loses' is set in the player record
for x in 0 ... pa.length
  pa[x]['loses'] = 0
  pa[x]['oplos'] = 0
  pa[x]['wins'] = 0
  pa[x]['opwin'] = 0
end
for x in 0 ... ga.length
  e = ''
  f = ''
  if ga[x]['w'] == ga[x]['1']
    e = ga[x]['2']
    f = ga[x]['1']
  else
    e = ga[x]['1']
    f = ga[x]['2']
  end
  if e != "BYE"
    pa[ph[e]]['loses'] += 1
  end
  if f != "BYE"
    pa[ph[f]]['wins'] += 1
  end
end

# Determine the number of losses our opponents have had
for x in 0 ... ga.length
  e1 = ga[x]['1']
  e2 = ga[x]['2']
  if e1 != "BYE"
    pa[ph[e1]]['oplos'] += pa[ph[e2]]['loses']
    pa[ph[e1]]['opwin'] += pa[ph[e2]]['wins']
  end
  if e2 != "BYE"
    pa[ph[e2]]['oplos'] += pa[ph[e1]]['loses']
    pa[ph[e2]]['opwin'] += pa[ph[e1]]['wins']
  end
end


# Is there a winner yet
mpa = pa
mpa.sort! {|x,y| x['loses'] <=> y['loses']}
if mpa[0]['loses'] < mpa[1]['loses']
  if ra[1] != nil
    print "done\n"
    exit
  end
#  print "result #{mpa[0]['n']} 1\n"
#  exit
end


# Used for testing; can be commented out
  mpa = pa
  mpa.sort! {|x,y| y['r'] <=> x['r']}
  for x in 0 ... mpa.length
#    print "* #{mpa[x]['n']} #{mpa[x]['r']} #{mpa[x]['loses']} #{mpa[x]['oplos']}\n"
    print "* #{mpa[x]['n']} #{mpa[x]['r']} #{mpa[x]['wins']} #{mpa[x]['opwin']} #{mpa[x]['tb1']}\n"
  end
  print "\n"



res = matchPlayers(pa, xa, ga, ph)
print "* Round #{rn+1}\n"
print "#{res}"


exit;


BEGIN{

def val(v=0)
  if v==nil; return 0 end
  if v==""; return 0 end
  return v
end

def matchPlayers(pa=[], xa=[],  ga=[], ph=Hash.new)
  m = ""

# Determine how many times each player has played another
#   also count number of byes and times played as first (gold) player
  v = Hash.new
  byes = Hash.new
  first = Hash.new
  i = 0
  leastByes = 999
  for i in 0 ... ga.length
    p1 = ga[i]['1']
    p2 = ga[i]['2']
    v[p1+p2] = val(v[p1+p2]) + 1
    v[p2+p1] = val(v[p2+p1]) + 1
    first[p1] = val(first[p1]) + 1
    if p2 == 'BYE'; byes[p1] = val(byes[p1]) + 1 end
    if val(byes[p1]) < leastByes; leastByes = val(byes[p1]) end
  end

# Setup the scores for ordering the players later
#    score - is used when pairing the players
#    bsc - is used when giving a player a bye
#    fsc - is used when deciding which player plays first
#    also mark that they have not been paired
  for i in 0 ... pa.length

# order by wins, opponent wins, rating, random number
#    pa[i]['score'] = sprintf("%03d%04d%08d%06d", val(pa[i]['wins']), val(pa[i]['opwin']), pa[i]['r'], rand(999999))

# 2009.11.13 commented out the above and changed it to this:
    tb1 = 100000.0/(1+10**(4*(val(pa[i]['wins'])-val(pa[i]['opwin']))/($rn+1)))
    pa[i]['tb1'] = tb1
    pa[i]['score'] = sprintf("%03d%06d%08d%06d", val(pa[i]['wins']), tb1, pa[i]['r'], rand(999999))


#print "    #{pa[i]['n']}  #{pa[i]['score']} \n";
    pa[i]['bsc'] = sprintf("%03d%03d%08d", 99-val(byes[pa[i]['n']]),
                        99-val(pa[i]['loses']), pa[i]['r'])
    pa[i]['fsc'] = val(first[pa[i]['n']])
    pa[i]['paired'] = 0
  end

# remove players that have been removed from the tournament
#   just go through the xa array and remove them from the pa array
  for i in 0 ... xa.length
    for j in 0 ... pa.length
      if xa[i]['n'] == pa[j]['n']
        pa.delete_at(j)
        break
      end
    end
  end


# Order the players by score generted above
  pa.sort! {|x,y| y['score'] <=> x['score']}

# Used for testing; can be commented out
  mpa = pa
#  mpa.sort! {|x,y| y['r'] <=> x['r']}
  print "* player rankings\n"
#  print "* name rating loses opponent-loses\n"
  print "* name rating wins opponent-wins tie-break score\n"
  for x in 0 ... mpa.length
#    print "* #{mpa[x]['n']} #{mpa[x]['r']} #{mpa[x]['loses']} #{mpa[x]['oplos']}\n"
    print "* #{mpa[x]['n']} #{mpa[x]['r']} #{mpa[x]['wins']} #{mpa[x]['opwin']} #{mpa[x]['tb1']} #{mpa[x]['score']}\n"
  end
  print "\n"

#    also re-generate the player name index
  ph.clear
  for i in 0 ... pa.length
    ph[pa[i]['n']] = i
  end

# If there are odd number of players; give the last player in the list
#   a bye unless the player already had a bye in which case
#   try giving the bye to the next higher player working up the list
  if pa.length % 2 == 1
    i = pa.length - 1
    while(i >= 0)
      p1 = pa[i]['n']
      if val(byes[p1]) <= leastByes
        m = m + "pick #{p1} BYE\n"
#        pa[ph[p1]]['paired'] = 1;
        pa[i]['paired'] = 1;
        break;
      end
      i -= 1
    end
#    bpa = pa.sort {|x,y| y['bsc'] <=> x['bsc']}
#    p1 = bpa[0]['n']
  end

# Mark the top and bottom index of different groups based on losses
  topi = Hash.new
  boti = Hash.new
  for i in 0 ... pa.length
    group = pa[i]['wins']
    if topi[group] == nil
      topi[group] = i
    end
    boti[group] = i
  end

# Now pair the players
  for i in 0 ... pa.length
    p1 = pa[i]
    if p1['paired'] != 0; next end

# get the indexes of unpaired players in our group
    opa = []
    group = p1['wins']
    ti = topi[group]
    bi = boti[group]
    for j in ti .. bi
      if j <= i; next end
      p2 = pa[j]
      if p2['paired'] != 0; next end
      opa.push(p2)
    end

    op = - 1
    if opa.length > 0
# take the bottom half of opponent array and put it at the top and
#   reverse the top half and put it at the bottom
      mi = (opa.length-1)/2
      th = opa[0 ... mi]
      bh = opa[mi .. -1]
      opa = bh + th.reverse
  
      for j in 0 ... opa.length
        p2 = opa[j]
        if val(v[p1['n']+p2['n']]) != 0; next end
        op = j
        break
      end
    end



## look for opponent in our group going down from the middle
#    group = p1['loses']
#    ti = topi[group]
#    bi = boti[group]
##print "* first player is #{p1['n']}  ti=#{ti} bi=#{bi} \n"
#    mi = (ti+bi)/2 + (bi-ti)%2
#    si = mi
#    if si <= i; si = i + 1 end
##    si = i + (mi-ti)
#    op = -1
#    for j in si .. bi
#      p2 = pa[j]
#      if j <= i; next end
#      if p2['paired'] != 0; next end
#      if val(v[p1['n']+p2['n']]) != 0; next end
#      op = j
#      break;
#    end
## if we didn't find opponent; look in our group going up from the middle
#    if op < 0
##      j = i + (mi-ti) + 1
#      j = mi + 1
#      while j > i
#        j = j - 1
#        if j <= i; next end
#        if j >= pa.length; next end
#        p2 = pa[j]
#        if p2['paired'] != 0; next end
#        if val(v[p1['n']+p2['n']]) != 0; next end
#        op = j
#        break;
#      end
#    end

# if we didn't find it; look starting at the top of the next group going down
    if op < 0
      for j in bi ... pa.length
        if j <= i; next end
        p2 = pa[j]
#print "* looking in next group j=#{j}  player2=#{p2['n']}\n"
        if p2['paired'] != 0; next end
        if val(v[p1['n']+p2['n']]) != 0; next end
        op = j
        break;
      end
    end

# p2 should now have the second player; op<0 means p2 not found
    if op < 0
      print "* no opponents found for #{p1['n']} \n"
      next
    end
  

# Old stuff from using folding pairing
#    op = []
#    for j in i+1 ... pa.length
#      p2 = pa[j]
##print "     i is  #{i}    j is #{j}  \n"
#      if p2['paired'] != 0; next end
#      p2['nsc'] = sprintf("%03d%03d%08d", 99 - val(v[p1['n']+p2['n']]), 
#                       99 - val(p2['loses']), 9999999 - p2['r'])
#      op.push(p2)
#    end
##print "    #{p1['n']}    #{p2['n']} \n"
#    op.sort! {|x,y| y['nsc'] <=> x['nsc']}
#    p2 = op[0]


    p1['paired'] = 1
    p2['paired'] = 1
    if p1['fsc'] < p2['fsc']
      m = m + "pick #{p1['n']} #{p2['n']}\n"
    elsif p2['fsc'] < p1['fsc']
      m = m + "pick #{p2['n']} #{p1['n']}\n"
    else
      if rand(2)>0
        m = m + "pick #{p1['n']} #{p2['n']}\n"
      else
        m = m + "pick #{p2['n']} #{p1['n']}\n"
      end
    end
  end
  return m
end

# Not used
#def shuffle!(a=[])
#  x = a.length
#  if x < 2 
#    return
#  end
#  for n in 1 .. 5*x
#    p1 = rand(x)
#    p2 = rand(x)
#    a[p1], a[p2] = a[p2], a[p1]
#  end
#end


# General tournament routines

def getTournState(tf)
  p, g, w, e = [], [], [], []
  i = Hash.new
  round = 0

  l = IO.readlines(tf)
  l.each do |x|
# read the player
    if x =~ /^player +(\w+) +(\d+)/
      r = Hash.new
      r['n'], r['r'] = $1, $2.to_i
      p.push(r)
      i[$1] = p.length - 1
    end
# read the player
    if x =~ /^remove +(\w+)/
      r = Hash.new
      r['n'] = $1
      e.push(r)
    end
# read the game
    if x =~ /^(pair|pick) +(\w+) +(\w+) winner +(\w+) *(\w*)/
      r = Hash.new
      r['1'], r['2'], r['w'] = $2, $3, $4
      if $5 != nil
        r['d'] = [$4,$5].join(" ")
      end
      g.push(r)
    end
# read the result
    if x =~ /^result +(\w+) *(\w*)/
      w[$2.to_i] = $1
    end
    if x =~ /^done$/
      break;
    end
# read the player properites we set
    if x =~ /^\* +set +player +(\w+) +(\w+) +(\w+)/
      if i[$1] != nil
        p[i[$1]][$2] = $3
      end
    end
# read the round number
    if x =~ /^\* Round +(\d+)/i
      round = $1.to_i
    end
  end
  return p, e, g, w, i, round
end

def printPlayerProp(p, k, v)
  print "* set player #{p} #{k} #{v}\n"
end

def printPlayersProp(p, k)
  p.each do |r|
    print "* set player #{r['n']} #{k} #{r[k]}\n"
  end
end


}

exit