「ぐるぐるスクエア」「ぐるぐるペンタゴン」問題解答 ( CodeIQ )
はじめに
CodeIQというところでプログラミング問題に挑戦しましたので、ネタバレです。
今回、似たコンセプトの2問をまとめて記事にしました。
問題
それぞれ名前の通り、4角形、5角形を使い、下の図 ( 左が「ぐるぐるスクエア」右が「ぐるぐるペンタゴン」) のように渦巻き状に数字のマスを配置した領域において、入力で指定された数字に隣接した4つ/5つの数字を小さい順にカンマ区切りにして出力するものでした。
例えば入力が 12 であれば、「ぐるぐるスクエア」なら 3,11,13,29 「ぐるぐるペンタゴン」なら 11,13,30,31,32 と出力します。
ちなみに「法則は図から読み取ってください」ということで、敢えて座標は記されていませんでした。つまり、どのように座標系を構築するか、から始まっている訳ですね。
解説
ぐるぐるスクエア
まずは座標の取り方ですが、次の図のように、1 を核とし、そこから輪状に層が蓄積されているものと見ます。
そうすると、各層に含まれるマスの数は層の番号に比例しますから、入力で与えられた数字がどの層にあるかが分かります。加えて、各層をエリアに分割します。以下は第3層 ( 26～49 ) を分割した時の図です。
そうすると、同じエリアであれば、先頭のマスを除いて同じ規則で周囲の数字が配置されていることに気付きます。
この図のように第3層のエリア1であれば、隣接するマスは、前後の数字2マスに加えて、
- エリアの先頭のマスの場合は、+25,+27のマス ( 次の層のマス )
- それ以外の場合は、-19,+27のマス ( 次の層と前の層のマス )
この +25,+27,-19 の数字は、層とエリアの数から計算することができます。( エリアが進む毎にコーナーの分の差が出てくるため、数字が2ずつ変わってきます )
なお、たった1マスのエリア4は、次の層につながる所ということで、ちょっと規則性が変わります ( むしろエリア3の続きと見ても良いのですが )。
ということで、提出したRubyの実装です。層 n、エリア a、エリアの中のオフセット m を計算し、そこから直に隣接マスを計算します。なお、核の 1 だけは全く規則性が異なるため別扱いです。
puts ->x{
return [2,4,6,8] if x==1
n=(Math.sqrt(x-1).floor+1)/2
a,m=(x-(n*2-1)**2).divmod(n*2)
d=8*n+1+a*2
a==4 ? [x-d+10,x-1,x+1,x+d-2] :
m==0||a==0&&m==1 ? [x-1,x+1,x+d-2,x+d] : [x-d+8,x-1,x+1,x+d]
}[gets.to_i]*?,
ぐるぐるペンタゴン
こちらは、5角形がベースということもあって、上の「ぐるぐるスクエア」と随分と勝手が違うように見えます。が、こちらもやはり層状に分割して考えます。
しかし、このような 5角形のままでは扱い辛くてしようがありません。そこで、次の図のように「正3角形を3分割した台形」に変形して考えます。また、層の中心の核は 1,2,3 からなる正3角形とします。
そのようにして、歪のある6角形で層を区切っていきます。層の内部は内/外の更に2層に分かれることになります。同時に、放射状の正3角形の裾野で6つのエリア分けをします。ちょうど次の図のようになります。
図中水色が層の内側、中でも濃い水色が層の開始位置になります。これで、各マスが、層・エリア・内/外・エリア内オフセットの4パラメータで位置づけできたことになります。
後は隣接マスの位置についてです。が、よくよく見てみると、3種類に分かれることが分かります。
それぞれ、タイプ0,1,2とすると、隣接マスが同一エリア内/外のみか、それとも違う層にも来るか、といった違いがあります。( もちろん、対象のマスが内/外どちらかによっても変わるのですが、ここでは割愛します )
…というようなことを盛り込みRubyで実装しました。
f=->x{
n=Math.sqrt((x+1.0)/18).round
t=x-18*n*(n-1)-4
t,io,dw,h=t<18*n-3?[t,0,6*n-1,3*n+1]:[t-18*n+3,1,6*n+1,3*n+2]
b,t=(t+2).divmod(dw)
b%=3
t<h ? [n,io,b*2,t]:[n,io,b*2+1,t-h]
}
g=->n,io,area,off{
off+=1 if n==0
base=18*n*(n-1)+4+(18*n-3)*io
h=3*n+1+io
base+(area/2*(h*2-3)+area%2*h+off-2)%(h*6-9)
}
puts ->x{
return [x%3+1,(x+1)%3+1,g[1,0,x*2-2,2],g[1,0,x%3*2,1],g[1,0,x%3*2,2]] if x<=3
n,io,area,off=f[x]
oio=1-io
du=1-io*2
[[n,io,area,off-1],[n,io,area,off+1],[n,oio,area,off]].push(*(
case (off-1)*du%3
when 0;[[n, oio,area,off+du], [n-du,oio,area,off-du]]
when 1;[[n-du,oio,area,off-du*2],[n-du,oio,area,off-du]]
else ;[[n, oio,area,off+du], [n, oio,area,off-du]]
end
)).map{|r|g[*r]}
}[gets.to_i].sort*?,
構成としては、数字から位置への変換を行う f、逆に位置から数字への変換を行う g を実装し、メインの処理では、タイプを判定して隣接マスの位置をリストアップするようにしています。例によって、核となる 1,2,3 は別扱いです。
エリアの端については? というところですが、g の方で、端から1はみ出た位は吸収できてしまうので、特別な処理は必要ありません。ただ、細かい所ですが、第1層からみた内側の第0層、つまり 1,2,3 については位置からの変換に微妙にズレがでますので、g で調整を行っています。
最後に
実はというか、ご存じの人には予想どおりというか、出題者の鍋谷さんが作問された「五角形の世界」( オフラインリアルタイムどう書くE09参加しました - ange1のブログを参照 ) で出ていた、5角形を4角形に変形して座標を考える方法を流用しています。もちろん、大分違う問題ではあるのですが。これがなかったら割と途方にくれていただろうなあ、という問題でした。
