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

問題 : https://gist.github.com/kunitoo/76b1d56cc6ffeef9bb62
経緯とか : http://qiita.com/kunitoo/items/d39c5337d400ad53f224

ruby で解いてみました。35分。

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)")

35分経った時点でのコード。 test の大半は省略。
最初方針を間違えてロスしたのがくやしい感じ。

リファクタリング前の状態とはいえ、メソッド名が悲惨。すいません。

やっている処理は：
"(RPS)(R)(RSP)(SP)(RSSP)" のような入力を普通に字句解析してから、残り試合数と zip して reverse して、
[["RSSP", 3], ["SP", 3], ["RSP", 2], ["R", 2], ["RPS", 2]]のようにする。
reverse はしなくていいかもしれないんだけど、右から戦うほうがわかりやすいかなと思って。

あとは、残り試合数が同じ人同士を戦わせることを繰り返せば良いという寸法。

a.first * count のところは長くし過ぎだけどどんまい。剰余で書いたほうがよかったね。

楽しめました。
ありがとうございます。