ESMじゃんけん大会を解いてみた

def winner(a, b)
  count = a.first.size.lcm( b.first.size )
  w=nil
  ha = a.first * count
  hb = b.first *  count
  count.times do |ix|
    if ha[ix] != hb[ix]
      w=case ha[ix]+hb[ix]
      when "RS", "SP", "PR"; a
      else; b
      end
      break
    end
  end
  w ||= b
  [w[0], w[1]-1]
end

def solve_core(s0)
  s=s0.dup
  loop do
    ix=(s.size-1).times.find{ |x|
      s[x].last==s[x+1].last
    }
    s[ix,2] = [winner( s[ix], s[ix+1] )]
    return s[0][0] if s.size==1
  end
end

def solve_impl(s)
  max_match = Math.log2(s.size).ceil
  min_match = Math.log2(s.size).floor
  rest = (s.size - 2**min_match)*2
  m = [min_match]*(s.size-rest)+[max_match]*rest
  solve_core( s.zip(m).reverse )
end

def solve( s )
  r=solve_impl(s.scan( /\(([^\)]+)\)/ ).to_a.flatten)
  "("+r+")"
end

def test( s, expected )
  actual = solve(s)
  ok = actual==expected
  puts [ ok ? "ok" : "**NG**", s, actual, expected ].join(" ")
end


test("(RSP)(R)(RPS)(SP)", "(RPS)")
test("(RPS)(R)(RSP)(SP)(RSSP)", "(RSSP)")