「まわせ! Bouwkamp!!」の ruby による実装と解説

問題 http://nabetani.sakura.ne.jp/hena/orde01rotbk/
実装リンク集 http://qiita.com/Nabetani/items/4bf43031749c81c35526

問題は難しかった模様。

で。

当日お見せした実装を二件。
※ 一方はちょっと修正したけど

いつも通り、テストケースの大半は省略で。

# 短くて簡単で遅い実装

まずは、短くて簡単で遅い方。ちょっと修正したけど。

```ruby:ruby
def fill( w, a )
  a.each.with_object( [nil]*(w*w) ) do |s,m|
    y,x=(0..(w*w)).find{ |ix| !m[ix] }.divmod(w)
    s.times do|dy|
      m[(y+dy)*w+x,s]=[s]*s
    end
  end
end

def bk(w,m)
  0.upto(w-1).map{ |x|
    (w-1).downto(0).map{ |y| m[x+y*w] }.uniq
  }.inject([]) do |code,line|
    code+line.chunk{ |c| code.flatten.include?(c) && :_separator }.map(&:last)
  end
end

def solve(src0)
  bkcode=src0.split(":").last
  gn=src0.split(":").first.to_i-1
  w=bkcode.split(/[\(\)]/)[1].split(",").map(&:to_i).inject(&:+)
  m=fill( w, bkcode.scan( /\d+/ ).to_a .map(&:to_i))
  "("+bk(w,m)[gn].join(",")+")"
end

DATA.map{ |line|
  num, src, expected = line.split(/\s+/)
  actual=nil
  actual = solve( src )
  ok = actual==expected
  puts( "%d %s : %s / %s" % [ num.to_i, (ok ? "ok" : "**NG**" ), actual, expected ] )
  ok
}.tap{ |x| puts( x.all? ? "all ok" : "something wrong" ) }

__END__
9 6:(240,168,187)(149,19)(206)(163,77)(86,82,58)(40,18)(22,202)(4,78)(192,61)(62)(48,13)(35,118)(83)  (4,82)
0 4:(55,44,48)(40,4)(52)(26,29)(23,3)(20,31,21)(5,47)(43)(9,17)(1,8)(32)(25)  (32,31)
1 6:(33,29,50)(4,25)(37)(15,35)(16,9)(7,2)(17)(42,18)(6,11)(8,27)(24)(19) (6,17,2)
```

計算量を減らす努力を全然してない。
美しくないけど、10秒ぐらいで計算が終わるのでよし。

+ ビットマップのような地図を作る
+ 回転する
+ 行のあつまりを `uniq` する
+ 行内を `chunk` する

で、だいたい出来上がり。

ruby の `chunk` というメソッドが便利で、

```ruby:ruby
[4, 3, 0, 2, 6, 7, 5, 9, 4, 6].chunk( &:odd? ).to_a
#=> "[[false, [4]], [true, [3]], [false, [0, 2, 6]], [true, [7, 5, 9]], [false, [4, 6]]]"
```

という風に、性質が変わらない間をひとまとまりにしてくれる。
このメソッドには「 `:_separator` を返すと配列が作られない」という機能があって、

```ruby:ruby
[1, 3, 0, 3, 6, 0, 5, 9, 4, 6].chunk{|x|x==0 ? :_separator : x.odd? }.to_a.inspect
#=> "[[true, [1, 3]], [true, [3]], [false, [6]], [true, [5, 9]], [false, [4, 6]]]"
[11]
```

と、いらないものを捨ててくれる。今回は発見済みのものは不要なので、これを使って捨てている。

計算量を減らす努力は一切していないので遅いしメモリもたくさん使うけど、今回のニーズにはこれで十分。

# 比較的ちゃんとした実装

比較的ちゃんとした実装は以下：

```ruby:ruby
class Sq < Struct.new(:x, :y, :s )
  def r; x+s; end
  def b; y+s; end
  def rot; Sq.new( -b, x, s ); end
end

def find_xy(sqs, len, y=0)
  loop do
    aty=sqs.select{ |sq| sq.y<=y && y<sq.b }
    if aty.empty? || aty.map(&:s).inject(&:+)<len
      x=0
      aty.sort_by(&:x).each do |sq|
        break unless x==sq.x
        x=sq.r
      end
      return [x,y]
    else
      y=aty.map{ |sq| sq.b }.min
    end
  end
end

def extract(src)
  len=src.split(/[\(\)]/)[1].split(",").map(&:to_i).inject(&:+)
  m=src.scan( /\d+/ ).to_a .map(&:to_i)
  m.each.with_object([]) do |s, sqs|
    sqs.push(Sq.new(*find_xy(sqs,len),s))
  end
end

def bouwkamp(sqs)
  sqs=sqs.sort_by{ |sq| [sq.y,sq.x] }
  sqs.drop(1).each.with_object([[sqs.first]]) do |sq,g|
    pre=g.last.last
    if pre.y==sq.y && pre.r==sq.x
      g.last.push sq
    else
      g.push [sq]
    end
  end
end

def solve(src0)
  num=src0.split(":")[0].to_i
  src=src0.split(":")[1]
  sqs = extract(src)
  rotated=sqs.map{ |s| s.rot }
  "("+bouwkamp(rotated)[num-1].map{ |x| x.s }.join(",")+")"
end

DATA.map{ |line|
  num, src, expected = line.split(/\s+/)
  actual = solve( src )
  ok = actual==expected
  puts( "%d %s : %s / %s" % [ num.to_i, (ok ? "ok" : "**NG**" ), actual, expected ] )
  ok
}.tap{ |x| puts( x.all? ? "all ok" : "something wrong" ) }

__END__
0 4:(55,44,48)(40,4)(52)(26,29)(23,3)(20,31,21)(5,47)(43)(9,17)(1,8)(32)(25)  (32,31)
1 6:(33,29,50)(4,25)(37)(15,35)(16,9)(7,2)(17)(42,18)(6,11)(8,27)(24)(19) (6,17,2)
2 7:(60,50)(23,27)(24,22,14)(7,16)(8,6)(12,15)(13)(2,28)(26)(4,21,3)(18)(17)  (4,16)
```

`find_xy` の実装がなかなかこれ以上簡単にならない。

不十分だと思うけど、ちょっと説明してみる。
全体としては

* `extract` で、bouwkamp code を正方形の配列に変換する。
* `Sq#rot` で、正方形を回転する
* `bouwcamp` で、正方形の配列を bouwcamp code に変換する

という流れ。面倒なのは、 `extract` 内の `find_xy` だけだと思うのでそこに絞る。

`aty` は、現在の y 座標の場所にいる正方形。
`aty` にある正方形の辺の長さの合計を見ると、余白があるかどうか分かる。
余白がある場合、`x=0` から順に余白を探す。
　いま注目している `x` に正方形があったら、その正方形の右端に注目する
　なかったら、`[x,y]` が、正方形を置くべき場所。
余白がない場合、`aty` に含まれている正方形の下端がの最小値を新たな `y` にして、もう一回。

という感じ。