CodeIQ：ぐるぐるスクエア

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ぐるぐるスクエア」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
【概要】
右図のように四角形のマスに数が入っています。
マスは無限に広がっており、全てのマスに数が入っています。
数を指定するので、その数が書かれているマスに隣接する（つまり、辺を共有する）4つのマスに書かれている数を、小さい順に出力してください。
※法則は図から読み取ってください

【入出力】
入力は
12
のように、普通に 10進数で来ます。

出力は、
3,11,13,29
のような感じです。

4つの数をコンマ区切りで昇順に並べてください。

【例】
入力出力
123,11,13,29
3415,33,35,61
7746,76,78,116

【補足】
不正な入力に対処する必要はありません。
入力は、1以上、1000以下です。
この問題よりも難しいぐるぐるペンタゴンという問題も公開されています。よろしければ挑戦してみてください

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

SZ = 17

def fillMap(map, n)
	px = SZ + n
	py = SZ - n
	base = (n*2+1)**2
	map[py][px] = base

	move = [
		[0, +1],
		[-1, 0],
		[0, -1],
		[+1, 0]
	]

	for i in 1..4
		mx = move[i-1][0]
		my = move[i-1][1]

		for _ in 1..(n*2)
			px += mx
			py += my
			base -= 1
			if map[py][px] == nil then map[py][px] = base end
		end
	end

	return map
end

def makeMap()
	map = Array.new(SZ*2+1){Array.new(SZ*2+1)}
	map[SZ][SZ] = 1

	for i in 1..SZ
		map = fillMap(map, i)
	end

	return map
end

def searchStartPos(n, map)
	for y in 0...(SZ*2+1)
		for x in 0...(SZ*2+1)
			if n == map[y][x] then return x,y end
		end
	end
end

def solve(n, map)
	x,y = searchStartPos(n, map)
	return [map[y-1][x], map[y+1][x], map[y][x-1], map[y][x+1]].sort
end

#main
map = makeMap()
while line = gets
	line.strip!
	if line.empty? then next end

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

解説

難しくありません。次の問題ぐるぐるペンタゴンの小手慣らし的な問題だと思います。

考え方

入力値の最大が1000なのでマップを作成してしまえば簡単です。
図の右肩を辿ってゆくと、1、9、25、49、81、…となっていて、奇数の二乗が続いています。つまり、中心をからn周目（n>0）の最も大きい数は(2n-1)2になります。
また、マップは二次元配列で表現できます。目的の数がn周目にあるとすると、マップは縦横(2n+1)あれば良いことがわかります。
これだけのことがわかれば、中心から数字を埋めていってマップを作れるので、マップ上から目的の数を探してその上下左右の数字をピックアップすれば良いわけです。

main

定数SZはマップのサイズの基準になる定数です。この値は1000を含む周より1周多いマップのサイズに設定しています。入力値から動的に決定することもできますが、どうせ最悪の計算量が要求されるテストケースは1000なのでこのサイズ決めうちで作ってしまっても問題ないという判断です。
入力値を数値に変換し、solve()に渡します。
solve()が結果を返すのでそれを印字して終わります。

makeMap()

定数SZを基準にマップを作ります。
マップの縦横はSZ*2+1なので(SZ,SZ)の座標はちょうど中心になります。
中心は1に決まっているので1をセットしてしまいます。
あとは1周ずつfillMap()でマップを埋めてゆきます。

fillMap(map, n)

引数mapはマップの二次元配列です。
nは中心を0として何周目かを表す値です。

px、pyはn周目の右肩の座標です。座標(SZ,SZ)が中心なのでそこからx方向にn、y方向に-nの場所になります。
baseはn周目の右肩の値で(n*2+1)2（n≧1）になります。
moveはどの方向に数値を埋めてゆくかを表す定数で下左上右になっています。
18〜28行目のループでn周目の右辺、下辺、左辺、上辺の順に時計回りにbaseから1ずつ減らしながら数値を埋めてゆきます。
右肩の下から始めると2nマスごとに反時計回りに90度方向を変えれば良いので、そのように値を埋めてゆきます（22〜27行目）。なお、最後に右肩の値を上書きしてしまうのですでに値が入っている場所は無視します（26行目）。
1周分の数値を書き込んだmapをリターンします。

solve(n, map)

引数nは入力値、mapはmakeMap()で作ったマップです。
searchStartPos()で入力値の座標を探します。
その座標の上下左右の値を取得して配列にし、ソートして返します。

searchStartPos(n, map)

何も考えずmapの二次元配列を先頭から順に探索し、nの座標を見つけたらそれを返します。

雑感

頭の悪そうなプログラムです。
1回ごとの処理時間を短くするなら入力値が含まれる周回とその内周と外周だけマップを作って、マップを作ると同時に入力値の座標を記録しておいて、そこから結果を返すのも難しくありません。
私のプログラムはmakeMap()を入力値の読み込み前に1回だけ行って、入力値は複数回受け取れるようになっています。実際のテストケースは1回の実行ごとに1パターンしか入力されませんが、複数行の入力があって複数行の出力が必要な場合、マップを1回しか作らない私のコードの方がトータルでは速くなります。
実際の業務でこういうプログラムが必要になった時はマップをstaticな領域に1回しか作らないか、サイズが足りなくなったら大きくするような仕組みにしなければならないと思うのでそれに近いコードにしたというわけです。