プログラム解説：CodeIQ「ぐるぐる曼荼羅」

問題の概要

問題を引用します。

【概要】
右図のように、(あるいは、巨大な表のように)正の整数が全て並んでいます。
数をひとつ指定しますので、その数のマスの上下左右に隣接しているマスの数を、昇順にコンマ区切りで出力してください。

【入力】
入力は標準入力から来ます。
35
のように、普通に10進数です。

【出力】
入力で指定された数のマスの上下左右に隣接しているマスの数を、昇順にコンマ区切りで出力してください。
先ほどの入力の場合、
8,34,36,100,101
を出力すれば正解です。

【例】

入力出力

35 8,34,36,100,101

43 11,42,44,119,120

【補足】
不正な入力に対処する必要はありません。
入力は、1以上十兆以下です。

入力	出力
35	8,34,36,100,101
43	11,42,44,119,120

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def a068156(n)
	return 3*(2**n) + 0**n - 3
end

def roundAndCount(n)
	r = 0
	fst = 1
	lst = 1

	loop{
		q = a068156(r)
		if r > 0 then
			fst = lst + 1
			lst = fst + q * 4 - 1
		end

#		p [fst, lst]
		break if (fst <= n) && (n <= lst)
		r += 1
	}

	return [r, n-fst, fst, lst]
end

# 指定された周回の最初の数と1辺のコマ数を返す
def roundFirstAndQ(r)
	fst = 1
	lst = 1
	q = 1

	for i in 1..r
		q = a068156(i)
		fst = lst + 1
		lst = fst + q * 4 - 1
	end

#	p [fst, q]
	return fst, q
end

# 内側で隣接するマスが内側の何番目か
# c 現在の周回の何番目か
# t 現在の周回のマス数
# bq 内側の1辺のマス数
def innerPos(c, t, bq)
	return 0 if bq == 1	# 中心の場合は特別

	x = c - 2
	if x == -2 then x = t - 2
	elsif x == -1 then x = t - 1
	end

	q = t / 4	# 辺のマス数
	h = x / q	# どの辺にあるか
	m = x % q	# 辺の何番目か

	if m < 2*bq then
		ret = h * bq + m / 2
	else
		ret = h * bq + bq - 1
	end

#	printf("inner: x=%d, q=%d, h=%d, m=%d, ret=%d\n", x, q, h, m, ret)

	return ret
end

# 外側で隣接する数が外側の何番目から何個か
# c 現在の周回の何番目か
# t 現在の周回のマス数
# nq 外側の1辺のマス数
def outerPos(c, t, nq)
#	printf("c=%d, t=%d, nq=%d\n", c, t, nq)
	return [0, 12] if t == 1

	q = t / 4	# 辺のマス数
	h = c / q	# どの辺にあるか
	m = c % q	# 辺の何番目か

	if m+1 < q then
		ret = [h*nq+(m+1)*2, 2]
	else
		ret = [h*nq+(m+1)*2, 5]
	end

#	printf("outer: q=%d, h=%d, m=%d, ret=%s\n", q, h, m, ret)

	return ret
end

def solve(n)
	r,c,f,l = roundAndCount(n)
	bf, bq = roundFirstAndQ(r-1)
	nf, nq = roundFirstAndQ(r+1)

#	printf("r=%d, c=%d, f=%d, l=%d, bf=%d, bq=%d, nf=%d, nq=%d\n", r, c, f, l, bf, bq, nf, nq)

	ret = []
	# 同じ周回で隣り合う数
	if n > 1 then
		ret << ((n-1 < f) ? l : n-1)
		ret << ((n+1 > l) ? f : n+1)
	end

	# 内側の周回で隣り合う数
	q = (l-f+1)/4
	ip = innerPos(c, l-f+1, bq)
	ret << (ip + bf) if (n > 1) && (c%q) != q-1

	# 外側の周回で隣り合う数
	op, ocnt = outerPos(c, l-f+1, nq)
	for i in 0...ocnt
		next if (i==2) || (i==5) || (i==8) || (i==11)
		x = op + i + nf
		x = nf if x == (nf + 4*nq)
		x = nf+1 if x == (nf + 4*nq + 1)
#		printf("i=%d, x=%d\n", i, x)
		ret << x
	end

	return ret.sort
end

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

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

解説

★★★の問題です。
相応に難しいですが1点だけ解決がつけば頑張ればできます。

考え方

一番の問題は内側からn周目がいくつからいくつまでかです。
これがわかればできます。
これは置いておいて、隣接する数について考えます。

ある数と同じ数字に隣接する数は次のようになります。
同じ周回で隣接する数は選んだ数±1です（その周回の最初と最後の数の場合は特殊）。
外側で隣接するのは、ある数が辺にあるなら2個で、角にあるなら5個で外側の最初の数が左上角の一つ下から始まるので計算でわかります。
内側で隣接するのは、1個でやはり内側の数は左上角から1つ下から始まるのでこれも計算でわかります。

で、最初の問題です。
内側からn周目がいくつからいくつまでかですが、私はOEISで探しました。A068156がその数列で、これはn周目の1辺の数字の数になります。なので2周目以降はその4倍ずつ数が増えてゆくので、周回の最初の数と最後の数を計算できます。

main

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

solve()

roundAndCount()でnが何周目か(r)、その周回の何番目か(c)、その周回の最初の数(f)、最後の数(l)を求めます。
内側の周回の最初の数(bf)と1辺のマス数(bq)をroundFirstAndQ(r-1)で求めます。
外側の周回の最初の数(nf)と1辺のマス数(nq)をroundFirstAndQ(r+1)で求めます。

同じ周回で隣り合う数を求めます。
これはn±1です。ただし、その周回の最後の数より大きくなる場合は最初の数、最初の数より小さくなる場合は最後の数になるよう調整します。

内側の周回で隣接する数を求めます。
qは1辺のマス数ですがbqと同じなので不要でした。
innetPos()で内側に隣接する数をipに求めます。
「if (n > 1) && (c%q) != q-1」の条件ですが、これはnが角にないことをチェックしています。角にある場合、問題にあるように上下左右で隣接ではなくなるので無視します。

外側の周回で隣接する数を求めます。
opは隣接する最初の数、ocntは隣接する数の数です。
114〜121行目のループは斜めの位置で隣接する数を除くためです。ocは2か5か12で角で隣接する場合は3個目だけが斜めになります。12になるのは1のマスの時だけで、これは4箇所を除くためiが2と5と8と11の時に覗きます。
117〜118行目は入力値が左上角の場合で、その周回の最大値を超えた場合に最小値とその次の値に変換するためのものです。

roundAndCount(n)

nが何周目か、その周回の何番目か、その周回の最初の数、最後の数を求めます。
これは0周目から順に最初の数と最後の数がいくつかを求め、nがその半にに入っている間ループすることで求めます。

変数rは周回、fstは最初の数、lstは最後の数です。
無限ループで、a068156(n)でr周回目の辺のマス数を求めます。
fstは前の周回のlst+1、lstはその周回の最初の数+a068156(n)の結果*4-1です。

nがfst以上、lst以下になったらループを抜けます。

返却値はr（何周目か）、n-fst（その周回の何番目の数か）、fst（その周回の最初の数）、lst（その周回の最後の数）になります。

a068156(n)

OEISの当該数列をみてください。

roundFirstAndQ(r)

指定された周回の最初の数と1辺のコマ数を返します。
これは0周目からr周目までa068156()で周回ごとのマス数を求め、それを積み上げて最初の数と最後の数を求めます。

innerPos(c, t, bq)

内側で隣接する数を求めます。
引数cは現在の周回の何番目かです。
引数tは現在の周回のマス数です。
引数bqは内側の1辺のマス数です。

入力値が1（中心）の場合は内側がないので0を返します。

50行目でx=c-2としているのは現在のマスから内側をみた時、現在の周回の最小の数がある場所に隣接するのは、内側の数の最小の数より2小さい数になるためです。最小の数より小さくなった場合、最大の数になるのでその調整を51〜52行目で行なっています。

59〜60行目は内側のマスが角に来ない場合です。
61〜62行目は内側のマスが角の場合です。

outerPos(c, t, nq)

内側で隣接する数を求めます。
引数cは現在の周回の何番目かです。
引数tは現在の周回のマス数です。
引数nqは外側の1辺のマス数

入力値が1（中心）の場合は特別なので[0,12]を返します。

59〜60行目は内側のマスが角に来ない場合です。
61〜62行目は内側のマスが角の場合です。

雑感

A068156の数列を見つけたので頑張ればできるというのははっきりしていたのですが、結構色々やらなければならないです。
ちなみに、最初隣接が上下左右だけで斜めを除外しなければならないことを見落としていてリジェクトになりました。

CodeIQ：ぐるぐる曼荼羅