テトロミノの置き方を数えようの解説解題

問題

問題は
テトロミノの置き方を数えよう
に置いた。

タイトルのとおり、テトロミノの置き方を数える問題。
テトロミノの種類は裏返しや回転で同じになるものは同じとみなすので I, L, O, S, T の 5種類。

出題意図など

テトロミノでなんか一問作ろうと思ったんだと思う。まあ憶えていないわけだけど。
テトロミノと言えば
テトロミノ認識〜横へな 2012.10.6 。
これをそのまま出すわけには行かないので、置き方を数える問題にした。んだと思う。

特に数学的背景やコンピューターサイエンス的含意はない。

実装方針

「ff 9d a5 a5 dd 9b b1 ff」のような入力文字列をなんとかする
テトロミノの候補を列挙する
テトロミノの候補がどのテトロミノなのか、同定する
集計結果の整形

の4段階になると思う。それぞれ説明すると。

入力文字列を何とかする

JavaScript 以外の環境だと 64bit 整数を扱える場合が多いと思う。
入力はちょうど 64bit なので、ひとつの整数にしてしまえばよい。
ruby で書くと、こんな

field=src.gsub(/\s/, "").to_i(16)

感じ。座標 x,y の値を知りたければ、ruby の場合

field[x+y*8]

でOK。

もちろん、空白で区切って 8個の整数にしてもいい。その場合はこんな

field=src.split(" ").map{|x| x.to_i(16) }

感じになる。座標 x, y の値は、ruby の場合

field[y][x]

となる。

テトロミノの候補を列挙する

列挙は、ビットが立っていないマスを集めてから combination すればいい。遅いかもしれないけど。
field に64bit 分の地図が入っているとすると、こんな感じになる：

whites=(8*8).times.select{|i| field[i]==0 }
whites.combination(4) do |a,b,c,d|
  # do something here
end

64個から4つ選ぶので、 64万通りぐらい。微妙。
ここは遅いかもね、と思いながら次へ進む。

テトロミノの候補がどのテトロミノなのか、同定する

裏返しや回転を無視するというルールなので、裏返しや回転に影響されない情報でテトロミノを記述すれば良い。
裏返しや回転に影響されない情報といえば、距離。
というわけで、4つのマスの距離の自乗を収集してみると、これがズバリうまくいくのである。

具体的にはこんな感じ：

def dist( a, b )
  (ax,ay),(bx,by)=[a,b].map{ |x| x.divmod(8) }
  dx=ax-bx
  dy=ay-by
  dx*dx+dy*dy
end

def ident(*a)
    d=a.combination(2).map{|x,y|
      dist( x, y )
    }.sort.join
    case d
    when '111449' then 0 # I
    when '111245' then 1 # L
    when '111122' then 2 # O
    when '111225' then 3 # S
    when '111224' then 4 # T
    else
        nil
    end
end

ident(1,9,10,11) とかやると、"L" を意味する 1 が帰ってくる。

集計結果の整形

ident が返す値がインデックスになっているので、そのまま利用すれば良い。

ix=ident(a,b,c,d)
results[ix]+=1 if ix

という具合。

最初の実装

というわけで、全部つなげるとこうなる：

def dist( a, b )
  dx=a%8 - b%8
  dy=a/8 - b/8
  dx*dx+dy*dy
end

def ident(*a)
    d=a.combination(2).map{|x,y|
      dist( x, y )
    }.sort.join
    case d
    when '111449' then 0 # I
    when '111245' then 1 # L
    when '111122' then 2 # O
    when '111225' then 3 # S
    when '111224' then 4 # T
    else
        nil
    end
end

def impl(field)
  whites=(8*8).times.select{|i| field[i]==0 }
  whites.combination(4).with_object([0]*5) do |(a,b,c,d),r|
    ix=ident(a,b,c,d)
    r[ix]+=1 if ix
  end
end

def solve(src)
  impl(src.gsub(/\s/, "").to_i(16)).join(",")
end

で。実行すると手元のマシンで最悪5秒ぐらい。やっぱり遅い。
impl の combination が遅そうだとわかっているんで、ここを速くする。

aとbが離れているなら、cとdを試す必要ないよね、とか、aとc が離れているなら d を試す必要ないよね、とか、そういうことを書けば速くなりそうだ。

で。最終的に下記のようになる：

#マンハッタン距離
def mdist( a, b )
  dx=a%8 - b%8
  dy=a/8 - b/8
  dx.abs+dy.abs
end

#ユークリッド距離の自乗
def dist( a, b )
  dx=a%8 - b%8
  dy=a/8 - b/8
  dx*dx+dy*dy
end

def ident(*a)
    d=a.combination(2).map{|x,y|
      dist( x, y )
    }.sort.join
    case d
    when '111449' then 0 # I
    when '111245' then 1 # L
    when '111122' then 2 # O
    when '111225' then 3 # S
    when '111224' then 4 # T
    else
        nil
    end
end

def impl(field)
  whites=(8*8).times.select{|i| field[i]==0 }
  whites.combination(2).with_object([0]*5) do |(a,b),r|
    next if 3<mdist(a,b)
    whites.select{ |c| c<[a,b].min }.each do |c|
      next if [a,b].any?{ |x| 3<mdist(x,c) }
      whites.select{ |d| d<c }.each do |d|
        next if [a,b,c].any?{ |x| 3<mdist(x,d) }
        ix=ident(a,b,c,d)
        r[ix]+=1 if ix
      end
    end
  end
end

def solve(src)
  impl(src.gsub(/\s/, "").to_i(16)).join(",")
end

これで、最悪でも 0.1秒以下になる。
ident が呼ばれる回数が約64万回だったのが、3205回に減った。200倍ぐらい違う。
枝刈り重要。

とはいえ

とはいえ、もっといいアルゴリズムがあるような気がしている。
どうだろう。

Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。