CodeIQ:ダブルテトロミノ

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ダブルテトロミノ」(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)の場所に必ずブロックがある状態として、そこから相対値でブロックのあるマスをデータ化します。
これに対して、始点となる任意の座標を与えるとテトロミノが占めるべきマスの座標がわかるという仕組みです。

後は次の操作で入力値の座標を埋められるかをチェックできます。
  1. 任意の座標を任意のテトロミノに与えて、その図形が占めるべき座標を計算する。
  2. 入力値の座標とテトロミノが占める座標を比較する。
    • 4つの座標が入力値に含まれていたら、2回目の候補として記録する。候補からはテトロミノと一致した座標を削除しておく。
    • そうでなければ無視する。
  3. 1〜2を全ての入力値の座標、全てのテトロミノに対してチェックする。
  4. 1回目のチェックでリストアップした候補全てに対して、全てのテトロミノを同様にチェックする。同様に4つの座標が一致したものを結果として記録する
  5. 結果に残った図形から文字列を求め、重複を削除して、結果の数を返す。

main

parseInput()で入力値をパースし、solve()に渡して結果を求め、結果を印字します。
定数Tetrominoはテトロミノのベクトルデータです。考え方に書いた通り、(0,0)の位置にブロックが存在する状態でブロックが占める座標の相対値をリストにしています。同時に結果の文字列を求めるため連想配列にしています。

parseInput(line)

入力値をパースして{座標[x,y]=>true}の形式で返します。
連想配列にしているのは座標がテトロミノのブロックと一致するかのチェックの時、Array#include?()よりチェックが速いからです。

solve(input)

結果を求めます。
引数inputは入力値をparseInput()でパースした結果の連想配列です。

99〜100行目で1つめのテトロミノとして合致するものをチェックして、テトロミノによって占められる座標を削除したものをリストアップします。
104〜108行目で1回目の結果にテトロミノが合致するかをチェックして、結果をリストアップします。
110行目で重複を削除し、結果の文字列を返します。

getNext(input, blocks, ptn, type)

引数はそれぞれ次の通りです。
input:入力値か1回目の処理が終わった残りの座標リスト。
blocks:inputから以前に削除したテトロミノの形状(文字列)。1回目はからの配列で2回目は1回目に入力から削除したテトロミノの形状(文字列)1つが入った状態。
ptn:テトロミノの1パターンのベクトルデータ。
type:ptnに対応する文字列。

inputの座標全てに対してptnの形状のテトロミノが当てはまるかをチェックします。
deletePtn()は座標リストの座標を1種類のテトロミノで埋められるかをチェックし、埋められればinputからテトロミノで埋められた座標を削除した座標リスト、埋められなければnilを返すので、nilでなければ結果をresultsに追加します。
resultsの1要素は[座標リスト, 使用したテトロミノの文字列リスト]です。

deletePtn(input, base, ptn)

引数は次の通りです。
input:入力値か1回目の処理が終わった残りの座標リスト。
base:起点となる座標。
ptn:テトロミノ1種類のベクトルデータ。

64〜67行目でptnの相対座標1個ずつに対しbaseの座標を加えて、テトロミノが実際に占める座標を求め、4個の座標が全部一致していたらinputからテトロミノが占める座標を削除したものを返し、1個でもinputの座標になければnilを返します。

uniqResults(results)

resultsは結果文字列の配列の配列(例:[["L","O"], ["O","L"]])です。
例のようにアルファベット順でソートされておらず、重複があるので、ソートして文字列を連結し、同じ文字列を削除して返します。

雑感

計算量が厳しいかと思ったのですが、そうでもなく単純に総当たりで問題ありませんでした。
ただ、同じパターンを2つずつ求めてしまうのが不細工です(例えばLOとOLを両方処理してしまいます)。
同じのを2回やらなくて良いようにするには、1回目と2回目を2つのループにするのではなく再帰にして、結果を記録しておき、結果に含まれるパターンが来たら無視するとかになるのでしょうか? それとももっと格好良い方法があるのかな?