CodeIQ：アタック25に挑戦！

問題の概要

私のプログラム

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

解説

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

雑感

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