オフラインリアルタイムどう書くE08 の問題の ruby による実装例

問題 : http://mtsmfm.github.io/2016/10/01/doukaku-e08.html
実装リンク集 : http://qiita.com/mtsmfm/items/94ebd353fa3b7e608f68

真剣にワーストケースを考えるとなかなか面倒な問題のような気がしている(詳しく検討すらできていない)んだけど、テストケースはそれほど厳しくないのでテストケースを通す方針でさらりと。

ruby2.3.1p112

require "benchmark"

class Array
  def x; self[0]; end
  def y; self[1]; end
end

def rev(m)
  m.size.times.with_object({}){ |e,o| o[m[e]]=e }
end

def fields( sq, rev_enemy )
  xr,yr = 2.times.map{ |e| sq.map{ |f| f[e] }.uniq.sort }.map{ |a,b| (a..b) }
  xr.each.with_object({}) do |x,o|
    yr.each do |y|
      o[[x,y]]=true if x!= xr.last && y != yr.last
      return {} if rev_enemy[[x,y]]
    end
  end
end

def solve_impl( me, enemy )
  rev_me = rev(me)
  rev_enemy = rev(enemy)
  me.size.times.with_object({}){ |ia,o|
    ia.times do |ib|
      a = me[ia]
      b = me[ib]
      next if a.x==b.x || a.y==b.y
      next unless ic = rev_me[[a.x, b.y]]
      next unless id =rev_me[[b.x, a.y]]
      o.merge!( fields( [a,b,me[ic], me[id] ], rev_enemy ) )
    end
  }.size
end

def solve( src )
  wb=src.split(",").map{ |b|
    b.scan(/([a-z])([0-9]+)/).map{ |a,b|
      [a.ord-?a.ord, b.to_i]
    }
  }
  [ solve_impl( *wb ), solve_impl( *wb.reverse ) ].join(",")
end

$stdout.sync=true

DATA.map do |line|
  /(?<num>\d+).*"(?<src>.+)".*"(?<expected>.+)"/=~line
  actual = nil
  tick = Benchmark.realtime{ actual = solve( src ) }
  okay = actual==expected
  puts( "%s %s %s->%s ( e:%s ) %f" % [ ( okay ? "ok" : "**NG**" ), num, src[0,70], actual, expected, tick ] )
  okay
end.all?.tap{|x| puts( x ? "everything is ok" : "something wrong" ) }

__END__
/*0*/ test("d3d4e3e4d9h7h9j3j4j7j9,f4f6g4g5g6h5h6", "5,3")
/*1*/ test("a1,s19", "0,0")

いろいろまずい点はあるものの、1時間経った時点でのソースコード。
二重ループは combination を使うべきだとか、Array に x とか勝手に生やすなとか、後置 unless の中で代入するなとか、Array を Hash のキーにするなとか、いろいろ。

私は Hash を Set 代わりに使ったんだけど、どうせ重複がそれほど多くないので Array を使って最後に uniq した方がよかったなぁと思ったり。

あと。「-?a.ord」は不要だった。これもなんかくやしい。

これで、手元で実行して 0.2秒弱。

ちょっともやもやしているんだけど、よしとする。

追記

のテストケースを追加すると 12秒。やっぱりダメか。
ハッシュのキーを [x,y] ではなく [x*32+y] にするだけで 3.3秒になるんだけど、本質的ではないよね。