CodeIQ：ぐるぐるペンタゴン
私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ぐるぐるペンタゴン」（CodeIQ）を参照してください。
問題の概要
【概要】
右図のように五角形のマスに数が入っています。
マスは無限に広がっており、全てのマスに数が入っています。
数を指定するので、その数が書かれているマスに隣接する（つまり、辺を共有する）4つのマスに書かれている数を、小さい順に出力してください。
※法則は図から読み取ってください
【入出力】
入力は
12
のように、普通に 10進数で来ます。
出力は、
11,13,30,31,32
のような感じです。
5つの数をコンマ区切りで昇順に並べてください。
【例】
入力 出力 12 11,13,30,31,32 34 15,33,35,64,65 77 44,76,78,117,118
【補足】
不正な入力に対処する必要はありません。
入力は、1以上、1000以下です。
この問題よりも簡単なぐるぐるスクエアという問題も公開されています。よろしければ挑戦してみてください。
私のプログラム
Rubyで解答しています。
#!/usr/bin/ruby
SZ = 25 # mapの基準サイズ
# DEBUG
# Mapを印字する
def printMap(map)
puts "---------- map ----------"
for m in map
for l in m
if l == nil then printf("---- ")
else printf("%4d ", l)
end
end
puts ""
end
end
# 座標(cy,cy)の周りにある使用しないマスを0で埋める
# mapと新たに0で埋めたマスの座標リストを返す
def setUnuse(map, cx, cy)
around = [[-2, -4], [-3, +1], [-1, +5], [+2, +4], [+3, -1], [+1, -5]]
nexts = []
for a in around
x = cx + a[0]
y = cy + a[1]
# printf("x=%d, y=%d\n", x, y)
if (x<0) || (y<0) || (x>=SZ*2+1) || (y>=SZ*4+3) then next end
if map[y][x] == 0 then next end
map[y][x] = 0
nexts << [x,y]
end
return map, nexts
end
# mapはヘックスとして管理するので使わないマスを0で埋める
def fillUnuse(map, center)
queue = [center]
while !queue.empty?
pos = queue.shift
map, nexts = setUnuse(map, pos[0], pos[1])
# printMap(map)
queue += nexts
end
return map
end
# setValue()のmoveの値のうち次にどれを使うかを返す
# toに+1を指定した場合は前に進む。-1は次の場所がすでに使われていた場合に指定し、1つ前のパターンを返す。
# @param ptn 現在のパターン番号
# @param to 次（+1/-1）を指定
# @return 次のパターン番号
def nextPtn(ptn, to)
nxt = ptn + to
if nxt == -1 then return 5
elsif nxt == 6 then return 0
else return nxt
end
end
# mapを数字で埋める。
# @param map マップ
# @param val 現在マップにある最も大きな値
# @param pos 現在マップにある最も大きな値の座標
# @param ptn 次に値をセットする進行方向のパターン番号
# @return map, 最新の値, 最新の値の座標, 次の進行方向の候補
def setValue(map, val, pos, ptn)
move = [
[-1,+1], # 左下
[ 0,+2], # 下
[+1,+1], # 右下
[+1,-1], # 右上
[ 0,-2], # 上
[-1,-1], # 左上
]
nx = pos[0] + move[ptn][0]
ny = pos[1] + move[ptn][1]
if (nx<0) || (ny<0) || (nx>=SZ*2+1) || (ny>=SZ*4+3) then return map, nil, nil, nil
elsif map[ny][nx] != nil then return setValue(map, val, pos, nextPtn(ptn, -1))
else
nv = val + 1
map[ny][nx] = nv
return map, nv, [nx, ny], nextPtn(ptn, +1)
end
end
# mapを1〜の数字で埋める
def fillMap(map, start)
x = start[0]
y = start[1]
val = 0
# 1と2は特別
y -= 2
val += 1
map[y][x] = 1 # 1
y -= 2
val += 1
map[y][x] = 2 # 2
pos = [x,y]
ptn = 0
while val != nil
map, val, pos, ptn = setValue(map, val, pos, ptn)
end
return map
end
# mapを作成する
def makeMap()
map = Array.new(SZ*4+3){Array.new(SZ*2+1)}
map[SZ*2+1][SZ] = 0
map = fillUnuse(map, [SZ, SZ*2+1])
map = fillMap(map, [SZ, SZ*2+1])
return map
end
# nの座標を調べる
def searchStartPos(n, map)
for y in 0...(SZ*4+3)
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)
arr = [
map[y+1][x-1], # 左下
map[y+2][x], # 下
map[y+1][x+1], # 右下
map[y-1][x+1], # 右上
map[y-2][x], # 上
map[y-1][x-1], # 左上
]
return arr.sort[1,5]
end
# main
map = makeMap()
#printMap(map)
while line = gets
line.strip!
if line.empty? then next end
puts solve(line.to_i, map).join(",")
end
解説
前の問題ぐるぐるスクエアと比べるとクソ難しいです。
考え方
入力値の周辺の数だけを求める方法があるのかもしれませんがわからなかったのでやはりマップを作りました。
一番のポイントはマップを正六角形のマス目で埋め尽くされた座標系（以降ヘックス）ととらえることです。ヘックスとして考えることで二次元配列で扱うことができ、数値を埋めてゆく法則も見えてきます。
マップをヘックスととらえると1、4、5、6、7、8で囲まれた数字の入っていないマスが現れます。このようなマスの位置には法則があります。
任意の数字の入っていないマスを中心に据えると、その周囲6個の数字の入っていないマスは同じパターンで配置されます。なので、1の下の数字の入っていないマスを基準にその周囲の数字の入っていないマスを特定し、さらにそこからその周囲の数字の入っていないマス、…、という繰り返しでマップ上の全ての数字の入っていないマスを特定できます。
1→2だけが特別ですが、それ以降は次のように移動します。
- 基本は左下、下、右下、右上、上、左上、左下…と移動する。
- もし、移動先にすでに数値が入っているか、数値の入らないマスなら一つ手前の方向（例：4→5の移動は本来4から右下に移動しようとするが、数値の入っていないマスなので下=右下の一つ前の方向）に移動する。一つ前の方向もダメならさらに一つ前、…と遡って方向を決める。
xは数値の入らないマス、空欄は使用しないマスです。
| 15 | 13 | 11 | |||
| 16 | 14 | x | |||
| x | 2 | 10 | |||
| 17 | 3 | 9 | |||
| 18 | 1 | 26 | |||
| 39 | 4 | 8 | |||
| 19 | x | 25 | |||
| x | 5 | 7 | |||
| 20 | 6 | 24 |
最後の問題はマップサイズの見積もりです。
これに関してはよくわからないので、適当に決めました。
main
定数SZはマップのサイズの基準になる定数です。この値は1000を含む周より余裕を持ったサイズに設定しています。
入力値を数値に変換し、solve()に渡します。
solve()が結果を返すのでそれを印字して終わります。
makeMap()
定数SZを基準にマップを作ります。
上下に辺が来る方向のヘックスを二次元配列で表現した場合、六角形1つを方言するために縦方向5マス、横方向3マスが必要で、一回り大きくなるごとに縦は4マスずつ、横は2マスずつ増えます。
この考えに従って、縦はSZ*4+3、横はSZ*2+1として二次元配列の領域を確保します。
(SZ,2*SZ)の座標がちょうど中心になります。ここを1が入る場所としています。
124行目で1の下の数値の入らないマスを設定しています。
fillUnuse()で数値の入らないマスを全て設定します。
その後、fillMap()でマップを1〜の数値で埋めます。
fillUnuse(map, center)
引数mapはマップの二次元配列です。
centerは最初に固定した数値の入らないマスの座標です。
queueの初期値にcenterを設定します。
queueから先頭の要素を取り出し、setUnuse()を呼び出します。setUnuse()は新規に数値の入らないマスを設定したmapと、設定した座標の配列（nexts）を返すので、queueにnextsを追加し、queueが空になるまで繰り返します。
setUnuse(map, cx, cy)
引数mapはマップの二次元配列です。
cx,cyは中心となる数値の入らないマスの座標です。
定数aroundは(cx,cy)からどの位置にある座標が数値の入らないマスかを特定するための定数です。
aroundの要素だけループし（25〜36行目）、cx,cyに加算して周辺の数値の入らないマスの座標を求めます（26〜27行目）。
座標がmapの領域を超えるか、すでに0が設定されていたら無視します（31〜32行目）。
そうでなければその座標のmapの値を0に設定し、新規に設定した座標リスト（nexts）に座標を追加します。
aroundの要素全てを処理したらmapとnextsを返します。
fillMap(map, n)
引数mapはマップの二次元配列です。
startは1の下の数値の入らないマスの座標です。
x,yは数値を設定する座標、valは設定する値です。
1と2が入るマスはその後の法則通りではないので特別に設定します（103〜109行目）。
続いてそれ以降の値を設定します。
変数posは値を設定する座標の配列、ptnは次に進む方向を示す値を保持します。
値はmapをはみ出すまで設定しますが、そのためにsetValue()を呼びます。setValue()はmapをはみ出した場所に値を設定しようとしたらval=nilを返すのでそれまで繰り返し呼び出します。
setValue(map, val, pos, ptn)
引数mapはマップの二次元配列です。
valは現在mapに設定されている最大の値です。
posはvalの値が設定されている座標です。
ptnは次の値をセットする座標に進む方向の候補です。候補というのは単純に反時計回りに進めた場所をさしているためで、実際にはその場所にはすでに値があるかもしれないからです。
定数moveはptnの番号によってどの方向に進むかを決定するためのテーブルです。
六角形の各辺の方向で、左下から開始して反時計回りになっています。
posとmove[ptn]から次の座標を求めます（84〜85行目）。
もし、mapの範囲外ならmapは更新せず、map、val=nil、pos=nil、ptn=nilを返します。
もし、設定しようとしている座標にすでに値があるならnextPtn()で一つ前の方向を求めてsetValue()を再帰呼び出しし、その結果を返します。数値の入らないマスは0を設定しているのでここでチェックされます。また、再帰呼び出しでも数値が入っているマスだった場合は、再び1つ前の方向で再帰呼び出しされるので進める方向が見つかるまで一つずつ戻りながら方向を決定できます。
それ以外（数値の入っていないマス）ならval+1をmapの座標に設定し、更新したmap、設定した値、その座標、次の進行方向候補を返します。
nextPtn(ptn, to)
次の進行方向がどちらかを返します。値はsetValue()のmoveの添え字に対応しています。
引数ptnは現在の方向で、toには反時計回りに進む（+1）か戻る（-1）が入力されます。
関数にしている理由は6の次は0、0の前は6を返すようにするためです。
solve(n, map)
引数nは入力値、mapはmakeMap()で作ったマップです。
searchStartPos()で入力値の座標を探します。
その座標の上下左右の値を取得して配列にし、ソートして最初の要素以外を返します。結果には必ず数値の入らないマスの値0が含まれ、これが最小値になるのでそれ以外が答えになるからです。
searchStartPos(n, map)
何も考えずmapの二次元配列を先頭から順に探索し、nの座標を見つけたらそれを返します。
雑感
マップを作る以外はぐるぐるスクエアと同じですが、非常に苦労しました。プログラムはそれほど苦労していませんが、プログラムにたどり着くまでが大変でした。数字の並び順が全然わからない（苦笑）。
これはヘックスで考えるべきというの最初から頭にあって、1、4、5、6、7、8で囲まれた場所を0にすれば良いことに気づいたのが解決の糸口だったっけ。で、1の下は良いとして、その他の場所を特定する方法を考えるために2次元配列を手書きで埋めている時に、基本的には反時計回りに進んでいるということに気づきました。それがわかってから、手書きした2次元配列のマップを眺めていたら、数値が入らない場所を特定する方法を思いついて、マップを作れるようになったという感じでした。
マップのサイズを特定する方法はわかっていないのですが、なんとなくSZ＝25で若干大きいくらいというのは予想できていました。試してみたらまずまず（一回りくらい大きい）だったのでそれ以上追求しませんでしたが、もうちょっと考えるとサイズを特定する方法もわかったでしょうか？