CodeIQ:アタック25に挑戦!

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「アタック25に挑戦!」(CodeIQ)を参照してください。

問題の概要

この「アタック25」で次に選択できるパネル番号を求めるプログラムを作成します。
標準入力から赤(R)、青(B)、白(W)、緑(G)が現時点で取得しているパネル番号が与えられます。
このとき、それぞれの色の解答者が正解したときに選択できるパネル番号を、標準出力にコンマ区切りで出力してください。
アタックチャンスは考慮しません。
ルースの詳細はhttp://asahi.co.jp/attack25/rule/を参照してください。
【入力】
赤が13番、青が8番を獲得していたときは以下のデータが与えられます。
R,13
B,8
W
G

【出力】
このとき、以下のような出力になります。
R,3
B,18
W,2,3,4,7,9,12,14,17,18,19
G,2,3,4,7,9,12,14,17,18,19

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby
require 'set'

# パネル(周囲1マスを余分に作る)
Pannel = Array.new(7).map{Array.new(7,nil)}

# 現在所有しているパネル
Possession = Hash.new

# 周囲の座標計算用
Around = [[-1,-1], [-1,0], [-1,+1], [0,-1], [0,+1], [+1,-1], [+1,0], [+1,+1]]

# パネル番号を座標に変換する
def pannel2Pos(pannel)
	pannel -= 1	# 0始まりにする
	pos = [0,0]
	pos[0] = (pannel/5).floor + 1	# Y座標
	pos[1] = pannel % 5 + 1			# X座標
	return pos
end

# targetからdistの方向に反転可能なパネルの数を探索する
def getReverse(color, target, dist)
	ret = []	# 間のパネル
	pos = pannel2Pos(target)
	for i in 1..4
		n = [pos[0]+dist[0]*i, pos[1]+dist[1]*i]

		# 範囲外チェック
		if (n[0] <= 0) || (n[0] > 5) || (n[1] <= 0) || (n[1] > 5) then break end

		# 同じ色のパネルまでチェック
		if Pannel[n[0]][n[1]] == color then return ret.length				# 同じ色
		elsif Pannel[n[0]][n[1]] != nil then ret.push(Pannel[n[0]][n[1]])	# 違う色
		else return 0														# 空きマス
		end
	end

	# ライン上に同じ色がなかった
	return 0
end

# 配置可能な場所を探す
# color 色
# cand 配置候補パネル番号
def searchReverse(color, cand)
	ret = []

	# 1か所も所有していない場合はどこにでも置ける
	# TODO 間違っている(次にはさめる場所にしなければならない)
	if Possession[color].length == 0 then return ret end

	# 自分以外の色がない場合もどこにでも置ける
	others = 0
	Possession.each{|key, val|
		if key == color then next
		else others += val.length
		end
	}
	if others == 0 then return ret end

	# 反転可能なパネルがある場所のみを列挙
	for c in cand
		for a in Around
			if getReverse(color, c, a) != 0 then ret.push(c) end
		end
	end

	return ret
end

# 次に反転可能な場所華道家をチェックする
def checkReverseNext(color, target, dist)
	pos = pannel2Pos(target)
	for i in 1..4
		n = [pos[0]+dist[0]*i, pos[1]+dist[1]*i]

		# 範囲外チェック
		if (n[0] <= 0) || (n[0] > 5) || (n[1] <= 0) || (n[1] > 5) then break end

		# 同じ色のパネルまでチェック
		if Pannel[n[0]][n[1]] == nil then			# 空きマス
			# 空きマスで隣り合っている場合はダメ
			if i > 1 then	return true
			else return false
			end
		elsif Pannel[n[0]][n[1]] == color then		# 同じ色
			return false
		end
	end

	# ライン上に空いているマスがなかった(おけない)
	return false
end

# 次に反転可能な場所を探す
def canReverseNext(color, cand)
	ret = Set.new
	for c in cand
		for a in Around
			if checkReverseNext(color, c, a) then ret.add(c) end
		end
	end
	return ret.to_a
end

# 配置可能なパネルを特定する
def searchPosition(color, cand)
	# 引っ繰り返せる場所を探す
	ret = searchReverse(color, cand)
	if !ret.empty? then return ret end

	# 引っ繰り返せる場所がない場合、次に引っ繰り返せる場所
	ret = canReverseNext(color, cand)
	if !ret.empty? then return ret end

	# それもなかったら隣接場所のどれでも良い
	return cand
end

# 色を設定する
def setColor(color, pannel)
	pos = pannel2Pos(pannel)

	if Pannel[pos[0]][pos[1]] != nil then
		return
	else
		Pannel[pos[0]][pos[1]] = color
	end
end

# 配置可能な場所を抽出する
def search2Set()
	ret = Set.new
	for pannel in 1..25
		pos = pannel2Pos(pannel)
		if Pannel[pos[0]][pos[1]] != nil then next end

		# 色のついたパネルに隣接していたらセット
		for a in Around
			if (Pannel[pos[0]+a[0]][pos[1]+a[1]] != nil) then
				ret.add(pannel)
				break
			end
		end
	end
	return ret.to_a
end

def isFirst()
	Possession.each_value{|val|	if val.length != 0 then return false end}
	return true
end

#main
while line = gets
	line.strip!
	if line.empty? then
		next
	end

	input = line.split(",", 2)

	if input.length == 2 then
		Possession[input[0]] = input[1].split(",").map {|i| i.to_i}
		for i in Possession[input[0]]
			setColor(input[0], i.to_i)
		end
	else
		Possession[input[0]] = []
		next
	end
end

if isFirst() then
	Possession.each_key{|color| puts color + ",13"}
else
	cand = search2Set()
	Possession.each_key {|color|
		ret = searchPosition(color, cand)
		puts color + "," + ret.join(",")
	}
end

解説

この問題は同じ出題者の他の問題と比べて少し変わっています。この出題者の問題は数学的な思考が要求されますがプログラム自体は短くて済むという問題が多いのですが、この問題に関してはルール通りにプログラムを実装すれば解けます。
私の数学能力ではわからないだけで計算だけでできる方法があるのかもしれませんが。

考え方

空いているパネルを順番にチェックしてルールに従って取れるパネルの番号を列挙するだけです。結構面倒臭いですが。

入力値取得

入力値は毎の取得済みパネルをPosessionに設定し、setColor()でPanelにも色を設定します。
Panelは7×7で外周をnilにセットし、それ以外の5×5がゲームで取得可能な場所になっています。外周をnilにしているのは領域外のチェックを簡単にするためです。Panelのようそのうち各色で占められている場所には'R'、'B'、'W'、'G'が入ります。

isFirst()

これは最初(つまり誰もパネルを取っていない)状態を判断します。
最初に取得できる場所は13しかないので、最初の場合は「色,13」を出力して終わります。

search2Set()

この関数は1〜25番のパネルを順次チェックし、空きパネル(nilがセットされている)だったら、周囲のパネルをチェックします。そして周囲のパネルのいずれかに色がセットされていたら誰かが次に取れるパネルの候補とします。
最後までチェックしたら候補の集合を返します。

この関数内で使っているnannel2Pos()は1〜25番をPannelの座標に変換する関数です。

searchPosition()

引数に色とsearch2Set()で作成したパネル取得候補の番号リストを取り、配置可能な場所を探します。取得可能なパネルは次の優先順位で決定します。
1. 挟んで引っ繰り返せる場所
2. 引っ繰り返せる場所がないなら次に正解した時引っ繰り返せる場所
3. それもなければ取得済みのパネルに隣接する場所

3は引数candそのものです。
1と2はそれぞれsearchReverse()とcanReverseNext()で探します。

searchReverse()

まず、探索対象の色が他に1か所もパネルを取っていない場合、この条件で取れるパネルはありません(51行目)。
次に探索対象がすでに取得されているパネルの色全てを独占している場合もこの条件で取れるパネルはありません(54〜60行目)。
そうでないなら候補の場所から上下左右、各斜め方向に探索して自分の色ではさめるかをチェックします。このチェックを行うのがgetReverse()でgetReverse()が1以上を返したパネルの番号を結果として収集して返します。

getReverse()

引数に色(color)、候補のパネル番号(target)、探索方向(dist)をとり、distの方向に1つずつ移動しながら同じ色が出るかをチェックします。distは定数Aroundのどれかになります。
ここで気をつける必要があるのは間に空欄がある場合です。例えば現在の色がRで右方向に探索するとします。「(R),B,_,R,_」のようになっているとした場合(R)の場所には置けません(R,Bはそれぞれの色のパネルで_は空き)。この辺りのチェックを33〜35行目で行っています。
なお、実際の処理ではretにパネルの色を集めていますが、本来は必要ありません。これはデバッグしやすくするためです。

canReverseNext()

searchReverse()で置ける場所が見つからなかった時(=はさめる場所がなかった)、次もう一度正解したらはさめる場所を探します。 この関数では候補の場所に対してループするだけで探索はcheckReverseNext()で行います。checkReverseNext()でtrueになったパネルを対象として結果に収集します。

checkReverseNext()

基本的にgetReverse()と同じような処理ですが条件が異なります。
引数targetの番号から引数distの方向に探索しますが、探すのが空きパネルになります。そしてtargetの位置から空きパネルまでの間に1つ以上他の色のパネルがなければなりません。この判断を82〜89行目で行っています(81行目のコメントが間違っています)。

雑感

CodeIQの問題の中ではかなり長いプログラムになりました。
★★★の問題で相応に難しくはありますが、ルール通りにプログラムすればできるし、ルール通りにやって計算量が大変なことになるわけでもなかったので、どうしようもないという感じは無くやればできるという感じの比較的気楽な問題でした。