CodeIQ:マス目を回す

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「マス目を回す」(CodeIQ)を参照してください。

問題の概要

問題を引用します。
【概要】
4×4 のマス目があります。
マス目のうちいくつかは穴になっています。
abc-/d-ef/g-hi/opqr codeiqのような形で盤面の初期状態(abc-/d-ef/g-hi/opqr)と一連の操作(codeiq)を与えます。

操作は一連の文字です。
各文字は「その文字を中心として、隣接(斜め含む)しているマスの文字を時計回りに回す」という操作を示しています。

ただし、穴の位置は変えないようにします。
要するに、右図のような感じです。

sample

一連の操作を終えたあとのマス目の状態を出力して下さい。

【入出力】
入力は
abc-/d-ef/g-hi/opqr codeiq
のようになっています。
空白の前が4×4のマス目、空白の後が一連の操作です。

マス目はスラッシュ区切りで各行を表しています。
a〜z は普通のマス、「-」は穴を意味します。

出力は、最終的なマス目の状態です。
形式は入力の空白の前の文字列と同じです。
abc-/d-ef/g-hi/opqr codeiqに対応する出力は
pac-/o-dh/e-qf/grbi
です。

【例】
入力 出力 状況
abc-/d-ef/g-hi/opqr codeiq pac-/o-dh/e-qf/grbi fig.1
na-c/d-be/t---/g-hi nabetani ab-t/c-en/d---/g-hi fig.2
ab--/----/----/---c abcabc ab--/----/----/---c fig.3

【補足】
不正な入力に対処する必要はありません。
異なるマス目に同じアルファベットが割り当てられることはありません。
操作を表すアルファベットは、1文字以上10文字以下です。
マス目に含まれない文字が、操作を表す文字に含まれることはありません。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

#
#   0 1 2
#   7   3
#   6 5 4
#
# [row, col]
#         0        1       2      3      4      5      6       7
Pos = [[-1,-1], [-1,0], [-1,1], [0,1], [1,1], [1,0], [1,-1], [0,-1]]


def getPos(arr, a)
	for r in 0..3
		for c in 0..3
			return [r,c] if arr[r][c] == a
		end
	end
end

def move(arr, center, from)
	for i in 1..7
		nxt = from + i
		nxt -= 8 if nxt > 7

		to_r = center[0] + Pos[nxt][0]
		to_c = center[1] + Pos[nxt][1]

		if (to_r < 0) || (3 < to_r) then next
		elsif (to_c < 0) || (3 < to_c) then next
		elsif arr[to_r][to_c] == '-' then next
		else return nxt
		end
	end

	return from
end

def copy(arr)
	ret = []
	for a in arr
		ret << a.dup
	end
	return ret
end

def solve(map, center)
	arr = map.split("/")
	ret = nil

	center.chars{|a|
		center = getPos(arr, a)
#		printf("%s %s\n", a, center)
		ret = copy(arr)

		for i in 0..7
			t = Pos[i]
			r = center[0]+t[0]
			c = center[1]+t[1]

			next if (r < 0) || (3 < r)
			next if (c < 0) || (3 < c)
			next if arr[r][c] == '-'

			nxt = move(arr, center, i)
			to_r = center[0] + Pos[nxt][0]
			to_c = center[1] + Pos[nxt][1]
#			printf("arr[r][c]=%s, to=%s\n", arr[r][c], [to_r, to_c].to_s)
			ret[to_r][to_c] = arr[r][c]
		end
		arr = ret
#		p ret
	}

	return ret.join('/')
end

# main
while line = gets
	line.strip!
	next if line.empty?
	map, center = line.split
	puts solve(map, center)
end

解説

コツコツやればできるタイプの問題です。

考え方

移動位置を次の様にとらえます。
012
73
654

そして、n番を移動する場合n+1、n+2、...(8以上になったら0に戻る)と試し、'-'でないところが見つかったら移動先はそこになるというわけです。
問題で示された通り動かすというわけです。

後は、操作1文字ごとに移動前の状態を残しておいて結果を作る必要があることくらいです。

main

入力値をスペースで分割してマップ(map)と操作(center)に分けます。
それぞれをsolve()に渡し、結果を印字します。

solve(map, center)

問題を解きます。
引数mapは最初の配置、centerは操作です。

mapを'/'で分割します。Rubyの文字列は配列の様に扱えるのでarrはマップの二次元配列です。
retは返却値です。

centerの文字を1文字ずつ取り出して操作します。
操作の中心となる文字の座標を取得します(52行目)。
arrを操作してしまうとマップの文字が重複したり消えたりしてしまうのでディープコピーします(53行目)。

中心の文字から見て0〜7番の1の文字を順次動かします(56〜70行目)。
tは移動する文字の相対座標で、rは移動する文字の絶対座標(行)、cは移動する文字の絶対座標(列)です。
マップの範囲外の座標は無視します(61〜62行目)。
'-'は移動しないので無視します(63行目)。
move()で移動し、移動後の相対座標を取得します。
to_rとto_cは移動後の絶対座標(行と列)です。
返却値retの座標に移動後の絶対座標を指定し、移動前の文字をコピーします。

1回の操作を終えたらarrをretで更新し、次の操作前の状態にします。

全ての操作を終えたらretを'/'で連結した文字列を返却します。

getPos(arr, a)

二次元配列arrからaの文字のある座標を探して返します。

copu(arr)

arrのディプコピーを返します。

move(arr, center, from)

fromの番号の移動後の番号を返します。

引数arrはマップの二次元配列です。
引数centerは中心の座標です。
引数fromはcenterに対して移動対象の文字の場所を示す0〜7の数字です。

移動先を+1〜+7の順に移動できるか試します。
nxtはfromの移動先候補の番号です。番号が7より大きくなったら0に戻します。
to_rは移動後の絶対座標(行)、to_cは移動後の絶対座標(列)です。
移動後がマップの範囲外になったら無視します。
移動後が'-'の場所なら無視します。
そうでなければ移動先なのでnxtを返却します。
移動先が見つからずにループを抜けたら(移動先が全部'-'の場合など)はfromをそのまま返します。

雑感

問題の操作通りにコツコツ実装しました。
行列計算か何かを使ってうまくやる方法はあるんでしょうか?