オフラインリアルタイムどう書くE19の実装例


問題 : http://mtsmfm.github.io/2017/11/04/doukaku-e19.html
実装リンク集 : https://qiita.com/mtsmfm/items/67bf5c121ecbd9b5fab3

まずは最初に書いた、`combination` で過剰に全探索しそうになるのを `uniq` で抑えただけの遅い実装

```ruby:ruby2.4
require "benchmark"

def rest_of( all, x )
  r=all.dup
  x.each do |e|
    r[r.index(e)]=nil
  end
  r.compact
end

def solve( src )
  pats = src.split(",")
  len = pats[0].size
  all = ([*1..len]*2).sort
  all.combination(len).uniq.each.flat_map{ |x|
    rest = rest_of( all, x )
    codes = [x,rest].map{ |e| e.map{ |n| n.even? ? "x" : "o" }.join }
    if codes==pats
      p [ pats, [x, rest] ]
      [[x,rest].flatten.join(",")]
    else
      []
    end
  }.join("|")
end

$stdout.sync=true

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

__END__
/*0*/ test("xxoxo,oooxo", "2,2,3,4,5,1,1,3,4,5");
/*1*/ test("ooxxo,ooxxo", "1,1,2,2,5,3,3,4,4,5|3,3,4,4,5,1,1,2,2,5");
```

手元のマシンで 61秒。

テストケースの最大が 12×2 なので、

```math
_{12} \mathrm{C} _{24}
```

約270万件。
これは数え上げられる数だと見込んでの実装……といいたいところだけ現場では間違えて $_{11} \mathrm{C} _{22}$ を計算してしまっていた。
でもまあ現実的な時間で計算できたので良しとしよう。

で。

次に、数え上げる量を減らしたバージョン。

```ruby:ruby2.4
require "benchmark"

def each_cards(sel0, target)
  return if sel0.size<=target
  sel = sel0.dup
  sum = sel.sum
  total = sel.size
  cands = [total - sum, 2 ].min
  (0..cands).each do |e|
    sel[target]=e
    if sel.sum==total
      yield(sel)
    else
      each_cards(sel, target+1){ |x| yield(x) }
    end
  end
end

def solve( src )
  pats = src.split(",").map{ |e| e.chars.map{ |c| c=="x" } }
  len = pats[0].size
  r=[]
  each_cards([0]*len, 0) do |c|
    c0 = c.flat_map.with_index(1){ |count,ix| [ix]*count }
    c1 = c.flat_map.with_index(1){ |count,ix| [ix]*(2-count) }
    codes = [c0,c1].map{ |e| e.map{ |n| n.even? } }
    if codes==pats
      r.push [c0,c1].flatten.join(",")
    end
  end
  r.sort.join("|")
end
```

テスト実行部は同じなので省略。
これで 7秒。まだ遅い。

次に、真面目に枝刈りしつつ数え上げる作戦。

```ruby:ruby2.4
require "benchmark"

def each_cards(sel0, target, pats)
  return if sel0.size<=target
  sel = sel0.dup
  total = sel.size
  cands = [total - sel.sum, 2 ].min
  (0..cands).each do |e|
    sel[target]=e
    c = [->(x){ x }, ->(x){ 2-x }].map{|f|
      sel[0,target+1].flat_map.with_index(1){ |count,ix|
        [ix]*f[count]
      }
    }
    next unless [0,1].all?{ |ix| pats[ix][0,c[ix].size]==c[ix].map(&:even?) }
    if sel.sum==total && target==sel.size-1
      yield(c)
    else
      each_cards(sel, target+1, pats){ |x| yield(x) }
    end
  end
end

def solve( src )
  pats = src.split(",").map{ |e| e.chars.map{ |c| c=="x" } }
  len = pats[0].size
  r=[]
  each_cards([0]*len, 0, pats) do |c|
    r.push c.flatten
  end
  r.sort.map{ |x| x.join(",") }.join("|")
end
```

小さい数から順に詰めていく作戦。
途中までしか詰まっていない状態で、ox のパターンと合っているかどうか調査して、合っていなかったらそれ以上詰めても無駄なので skip するというもの。

これで一瞬で終わるようになった。

それにしても面白い問題だったと思う。