私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ダブルテトロミノ」（CodeIQ）を参照してください。
【概要】
図のように、黒いマスが 8つあります。
テトロミノ2つを使って黒いマスで示された図形を作るには、どんなテトロミノが必要なのか、全ての組み合わせを求めてください。
例えば図の場合、LとO、LとSという組み合わせが考えられます。
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
【詳細】
テトロミノは、下表の 5 種類があります：
裏返したり回転したりしてできるテトロミノは同じ名前です。
名前 I L O S T 形状
【入出力】
入力は
56 37 36 55 35 46 45 47
のような感じです。
空白区切りで黒いマスの位置が書かれています。
黒いマスの位置は、1文字目が x 座標、2文字目がy座標です。
出力は、
LO,LS
のような感じです。
ペアをコンマ区切りで並べてください。
ペア間もペア内も、アルファベット順に整列しておく必要があります。
下表の通りです。
誤 LS,LO 誤 OL,SL 正 LO,LS
入力の形が2つのテトロミノでは作れない場合は、
-
を出力してください。
【例】
入力 出力 状況 56 37 36 55 35 46 45 47 LO,LS
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 70 07 44 34 98 11 00 32 -
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 63 60 67 65 64 62 61 66 II
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
【補足】
不正な入力に対処する必要はありません。
入力には、かならず8マス含まれています。重複はありません。
Rubyで解答しています。
#!/usr/bin/ruby
Tetromino = {
# I
[[0,0], [0,1], [0,2], [0,3]] => "I",
[[0,0], [1,0], [2,0], [3,0]] => "I",
# L右
[[0,0], [0,1], [0,2], [1,2]] => "L",
[[0,0], [1,0], [2,0], [0,1]] => "L",
[[0,0], [1,0], [1,1], [1,2]] => "L",
[[0,0], [1,0], [2,0], [2,-1]] => "L",
# L左
[[0,0], [0,1], [0,2], [-1,2]] => "L",
[[0,0], [1,0], [2,0], [0,-1]] => "L",
[[0,0], [0,1], [0,2], [1,0]] => "L",
[[0,0], [1,0], [2,0], [2,1]] => "L",
# O
[[0,0], [1,0], [0,1], [1,1]] => "O",
# S(Z型)
[[0,0], [1,0], [1,1], [2,1]] => "S",
[[0,0], [0,1], [-1,1], [-1,2]] => "S",
# S(Z反転)
[[0,0], [1,0], [1,-1], [2,-1]] => "S",
[[0,0], [0,1], [1,1], [1,2]] => "S",
# T
[[0,0], [0,1], [0,2], [-1,1]] => "T",
[[0,0], [-1,1], [0,1], [1,1]] => "T",
[[0,0], [0,1], [0,2], [1,1]] => "T",
[[0,0], [1,0], [2,0], [1,1]] => "T",
}
# DEBUG
# テトロミノの図形確認用
def printTetromino()
Tetromino.each{|ptn, type|
arr = Array.new(5){Array.new(5, " ")}
base = [1,1]
for pos in ptn
x = base[0] + pos[0]
y = base[1] + pos[1]
arr[y][x] = "*"
end
for a in arr
puts a.join("")
end
}
end
def parseInput(line)
ret = Hash.new(false)
line.split.sort.map{|a|
v = a.split("")
ret[[v[0].to_i, v[1].to_i]] = true
}
return ret
end
def deletePtn(input, base, ptn)
nxt = input.dup
for vec in ptn
pos = [base[0]+vec[0], base[1]+vec[1]]
if nxt.delete(pos) == nil then return nil end
end
return nxt
end
def getNext(input, blocks, ptn, type)
results = []
input.each{|base, _|
ret = deletePtn(input, base, ptn)
if ret != nil then
results << [ret, blocks + [type]]
end
}
return results
end
def uniqResults(results)
if results.empty? then return ["-"] end
ret = []
for r in results
ret << r[1].sort.join("")
end
return ret.uniq.sort
end
def solve(input)
second = []
# 1回目
Tetromino.each{|ptn, type|
second += getNext(input, [], ptn, type)
}
results = []
for s in second
Tetromino.each{|ptn, type|
results += getNext(s[0], s[1], ptn, type)
}
end
return uniqResults(results)
end
# main
while line = gets
line.strip!
if line.empty? then next end
input = parseInput(line)
ret = solve(input)
puts ret.join(",")
end
割と簡単な問題と思います。
ただし、私のコードは無駄が多いです。実際に必要な数の2倍の計算をしているので、もっと効率的な方法があるような気がします。
私のプログラムは単純に総当たりしています。
多分、唯一のポイントはテトロミノをベクトルデータとして扱っていることです。
座標(0,0)の場所に必ずブロックがある状態として、そこから相対値でブロックのあるマスをデータ化します。
これに対して、始点となる任意の座標を与えるとテトロミノが占めるべきマスの座標がわかるという仕組みです。
parseInput()で入力値をパースし、solve()に渡して結果を求め、結果を印字します。
定数Tetrominoはテトロミノのベクトルデータです。考え方に書いた通り、(0,0)の位置にブロックが存在する状態でブロックが占める座標の相対値をリストにしています。同時に結果の文字列を求めるため連想配列にしています。
入力値をパースして{座標[x,y]=>true}の形式で返します。
連想配列にしているのは座標がテトロミノのブロックと一致するかのチェックの時、Array#include?()よりチェックが速いからです。
結果を求めます。
引数inputは入力値をparseInput()でパースした結果の連想配列です。
99〜100行目で1つめのテトロミノとして合致するものをチェックして、テトロミノによって占められる座標を削除したものをリストアップします。
104〜108行目で1回目の結果にテトロミノが合致するかをチェックして、結果をリストアップします。
110行目で重複を削除し、結果の文字列を返します。
引数はそれぞれ次の通りです。
input：入力値か1回目の処理が終わった残りの座標リスト。
blocks：inputから以前に削除したテトロミノの形状（文字列）。1回目はからの配列で2回目は1回目に入力から削除したテトロミノの形状（文字列）1つが入った状態。
ptn：テトロミノの1パターンのベクトルデータ。
type：ptnに対応する文字列。
inputの座標全てに対してptnの形状のテトロミノが当てはまるかをチェックします。
deletePtn()は座標リストの座標を1種類のテトロミノで埋められるかをチェックし、埋められればinputからテトロミノで埋められた座標を削除した座標リスト、埋められなければnilを返すので、nilでなければ結果をresultsに追加します。
resultsの1要素は[座標リスト, 使用したテトロミノの文字列リスト]です。
引数は次の通りです。
input：入力値か1回目の処理が終わった残りの座標リスト。
base：起点となる座標。
ptn：テトロミノ1種類のベクトルデータ。
64〜67行目でptnの相対座標1個ずつに対しbaseの座標を加えて、テトロミノが実際に占める座標を求め、4個の座標が全部一致していたらinputからテトロミノが占める座標を削除したものを返し、1個でもinputの座標になければnilを返します。
resultsは結果文字列の配列の配列（例：[["L","O"], ["O","L"]]）です。
例のようにアルファベット順でソートされておらず、重複があるので、ソートして文字列を連結し、同じ文字列を削除して返します。
計算量が厳しいかと思ったのですが、そうでもなく単純に総当たりで問題ありませんでした。
ただ、同じパターンを2つずつ求めてしまうのが不細工です（例えばLOとOLを両方処理してしまいます）。
同じのを2回やらなくて良いようにするには、1回目と2回目を2つのループにするのではなく再帰にして、結果を記録しておき、結果に含まれるパターンが来たら無視するとかになるのでしょうか？ それとももっと格好良い方法があるのかな？