プログラム解説：CodeIQ「境界線の長さ」

問題の概要

問題を引用します。

【概要】
図のように、8×8のマス目を白と黒で塗り分けます。

黒と白の境界に線を引きます。
黒い領域の上下左右にある境界線（右図の、赤・緑・青・黄色）の総延長をそれぞれ数えるプログラムを書いてください。
マス目の外側との境界線は数えません。

【入出力】
入力は
f78f447ae68f20af
のように、16進数16桁で来ます。
2桁の16進数が1行を表します。
MSBが左で、1が黒を表します。
上記の入力が、右図に対応します。

出力は、
16,17,11,12
のような感じです。
上下左右の境界線の総延長をコンマ区切りでならべてください。
こちらは10進数です。

【例】

入力出力状況

f78f447ae68f20af 16,17,11,12

ffbc94fc89a34523 10,15,12,13

【補足】
不正な入力に対処する必要はありません。

入力	出力	状況
f78f447ae68f20af	16,17,11,12
ffbc94fc89a34523	10,15,12,13

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 入力値を2次元配列のマップに変換する
def makeMap(line)
	map = []
	map << Array.new(10)

	for i in 0...8
		l = line[2*i..(2*i+1)].to_i(16)

		m = Array.new(10)
		for j in 0...8
			m[8-j] = (l >> j) & 1
		end
		map << m
	end

	map << Array.new(10)

	return map
end

# 指定されたマスに上下左右の境界があるかをチェックする。
def countBorder(map, row, col)
	if map[row][col] == 0 then return [0,0,0,0] end

	ret = []
	directions = [[-1,0], [1,0], [0,-1], [0,1]]
	for d in directions
		ad = map[row+d[0]][col+d[1]]
		if (ad == nil) || (ad == 1) then ret << 0
		else ret << 1
		end
	end

	return ret
end

# 問題を解く
def solve(line)
	map = makeMap(line)

	ret = [0,0,0,0]
	for i in 1..8
		for j in 1..8
			cnt = countBorder(map, i, j)

			for k in 0...4
				ret[k] = ret[k] + cnt[k]
			end
		end
	end

	return ret
end

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

	puts solve(line).join(",")
end

解説

特に気をつけるところもなく、素直にやればできます。

考え方

黒いマスの上下左右をチェックし、白いマスなら境界としてカウントしてゆくだけです。

main

入力値を数値にしてsolve()に渡し、結果をコンマで連結して印字します。

solve(line)

makeMap()で入力値を2次元配列のマップにします。
retは[上,下,左,右]の境界の数です。
マップは8*8なのでループで1マスごとをチェックします。
countBorder()はそのマスの上下左右に境界があれば1、なければ0を返します。返却値は[上,下,左,右]なのでretにそれぞれの値を加算してゆきます。
retを返却して終わります。

makeMap(line)

入力値を次元配列に変換します。
入力値を2文字ずつ取り出して16進数の数値に変換し、1bitずつ変換するだけです。
多少の工夫が1周り大きい10*10のマップにして最外周をnilにしていることです。これで範囲外チェックを省くことができます。

countBorder(map, row, col)

mapのrow、colのマスが境界を持つかをチェックします。
白いマスは無視するのでmap[row][col]が0なら[0,0,0,0]を返却します。
あとは上下左右を見て黒いマスか端なら0、そうでなければ1にします。
結果を返却して終わります。

雑感

えらく素直な問題でした。
何か引っ掛けがあるのかな、と思いましたが何もありませんでした。
ちなみにマップを作ったりせず直接ビット演算でやってもできますが、全体のサイズも大したことがないのでデバッグ効率を考えてもマップを作ったほうがわかりやすいと思います。

CodeIQ：境界線の長さ