日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。
問６８「"magic" 5-gon ring に当てはまる16桁の数字列は何か?」
下に示す図のようなものを"magic" 3-gon ringという.
これは1～6の数字を当てはめて, 各列の数字の和が9となっている.
これを例として説明する.
例えば例のものは4,3,2; 6,2,1; 5,1,3という組で説明することができる.
1～6の数字を当てはめて, 各列の数字の和が等しくなるものは次の8通りある.
| 合計 | 組 |
| 9 | 4,2,3; 5,3,1; 6,1,2 |
| 9 | 4,3,2; 6,2,1; 5,1,3 |
| 10 | 2,3,5; 4,5,1; 6,1,3 |
| 10 | 2,5,3; 6,3,1; 4,1,5 |
| 11 | 1,4,6; 3,6,2; 5,2,4 |
| 11 | 1,6,4; 5,4,2; 3,2,6 |
| 12 | 1,5,6; 2,6,4; 3,4,5 |
| 12 | 1,6,5; 3,5,4; 2,4,6 |
例えば, 上の図のものは4,3,2; 6,2,1; 5,1,3であるので432621513である.
さて, 下の図に1～10の数字を当てはめ, 各列の数字の和が等しくなる"magic" 5-gon ringを作って, それを表す16桁または17桁の数字のうち, 16桁のものの最大の数字を答えよ.
(注, 3つの場合の例を見ても分かる通り, 列の始まりの数字を比べた時一番小さい数字で始まる列から時計回りに繋げるという条件のもとで文字列を生成する必要があります. この条件下で最大となる数字を答えてください. )
－－－－－
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
私の解答例は以下です。畳んでいます。
def g(M, Li, Lt): t = min(Lt) for L in M: if t in L: break L = [t]+sorted([s for s in L if s!=t], reverse=True) R = [L] while len(R)<len(M): for P in M: if sorted(P)!=sorted(L) and (L[-1] in P): break L = [s for s in P if s in Lt] + [L[-1]] \ + [s for s in P if s in Li and s!=L[-1]] R.append(L) return "".join([str(s) for L in R for s in L]) def f(n): import itertools N = n*2 Q = [] for Li in itertools.combinations(xrange(1, N+1), n): Li, Lt = list(Li), [s for s in xrange(1, N+1) if s not in Li] Sa = N*(N+1)//2 + sum([i for i in Li]) LL = [list(L)+[Sa//n-sum(L)] for L in itertools.combinations(Li, 2)] for M in itertools.combinations(LL, n): La = [s for L in M for s in L] if sorted(La)==sorted(list(Li)+list(Li)+Lt): Q.append(g(M, Li, Lt)) t = min([len(s) for s in Q]) return max([int(s) for s in Q if len(s)==t]) n = 5 print f(n)
関数を２つ使用しています。
１．関数g(M, Li, Lt)
・枝リストから、一番外側の数字が最小である枝から時計回りに、
全ての枝のノードの連結値のうちの最大値を返します。
・引数Mは枝（ノードのリスト）のリスト、Liは内側ノードのリスト、Ltは外側ノードのリストです。
・t = min(Lt)
tは外側ノードの最小値
・for L in M:
if t in L: break
for文で枝リストMからノードリストをループ変数Lとして取り出します。
if文で外側ノードの最小値がある枝の場合、for文を抜けます。
ノードリストLは外側ノードの最小値を持つ枝で、最初の枝ということになります。
・L = [t]+sorted([s for s in L if s!=t], reverse=True)
最初の枝のノードリストLを並び替えます。
並び順は、外側ノード、その後に内側ノードの大きい順です。
これで最初の枝のノード並びが確定します。
sorted文で、内側ノードを大きい順に並び替えています。
sorted文の第１引数のリストは内包表記しています。
ノードリストLからループ変数としてノードsを取り出し、後ろのif文に回します。
if文でsとtが異なる場合、つまり内側ノードの場合、sorted対象のリストの要素としてためます。
そして第２引数reverse=Trueで、逆順（大きい順）に並べるように指定します。
外側ノードtを[]でリスト化し、内側ノードリストと結合して、改めてリストLとします。
・R = [L]
ノード並びが確定したので、最初の枝を結果リストRにためます。
・while len(R)<len(M):
結果リストRの要素数が元の枝の数になるまで、２本目以降の枝の処理をします。
・for P in M:
if sorted(P)!=sorted(L) and (L[-1] in P): break
前の枝の末尾ノードは次の枝にだけ共有されていることを利用して、次の枝Pを求めます。
「for P in M」で枝リストMから枝をループ変数Pとします。
if文で枝P枝と１つ前の枝Lとをそれぞれソートして異なること、そして前の枝Lの末尾ノードL[-1]が存在するような枝Pになったところで処理を抜けます。
・L = [s for s in P if s in Lt] + [L[-1]] \
+ [s for s in P if s in Li and s!=L[-1]]
枝のノードを外側からの順に並び替えます。
並び替え後ノードリストLは、Pの次のループで前の枝として扱います。
まず、[s for s in P if s in Lt]は外側ノード１つだけのリストです。
内包表記です。まず枝Pからノードを１つずつ取り出しループ変数sとして
後ろのif文に回します。そして外側ノードリストLtにある場合だけ先頭に回します。
次に、[L[-1]]は１つ前の枝の最後の値だけのリストです。枝Pでは２番目の要素です。
最後に、[s for s in P if s in Li and s!=L[-1]]は上記２つ以外のノードです。
内包表記です。まず枝Pからノードを１つずつ取り出しループ変数sとして
後ろのif文に回します。そして内側ノードリストLiにあり、先ほどの２番目の要素と異なる場合だけ採用し先頭に回します。
この文全体で上記３要素それぞれだけのリスト３つを+演算子で１つのリストに結合します。
・R.append(L)
枝のノードが実際の並びになったので、結果リストRに追加してためます。
・return "".join([str(s) for L in R for s in L])
すべての枝のノードを並び直したので、全ノードを文字扱いして順に連結た値を返します。
内包表記です。前のfor文で結果リストRから枝Lを取り出し後ろに回します。
後ろのfor文で枝Lからノードsを取り出し先頭に回します。
先頭で文字型に変換し、その全要素をリストにします。
そしてこのリストをjoin関数で区切り文字なしで連結します。
２．関数f(n):
・マジックn角形リングについて、問題で求めるノードの連結値を返します。
具体的には、マジックn角形リングの外側から内側へ各ノードの値を連結した枝のうち、一番外側の数字が最小の枝から時計回りに、全ての枝数字を連結して最小桁数の最大値を返します。
引数nは枝の本数でもあります。
・import itertools
組合せの関数を使用するために、標準モジュールの「itertools」を使えるようにしておきます。
・N = n*2
Nはノード数です。マジック五角形はノードが10個あります。
・Q = []
Qは返却する連結値候補リストです。初期クリアしておきます。
・for Li in combinations(xrange(1, N+1), n):
Liはすべての内側ノードのリストです。
xrange関数で1からNまでの整数を発生させ、combinations関数でそのうちn個ずつの組合せをLiとします。この時点ではLiはタプルです。
・Li, Lt = list(Li), [s for s in xrange(1, N+1) if s not in Li]
Liは内側ノードリストで、タプルからリストに変換しておきます。
Ltは外側ノードリストです。1からNまで整数のうち内側ノードリストに無い値のリストです。
内包表記です。1からNまで整数をループ変数sとして後ろに回し、if文で内側ノードリストLiに無い値だけ、先頭に回してリストにためます。
・Sa = N*(N+1)//2 + sum([i for i in Li])
Saはライン総和です。ライン総和には内側ノード２回分と外側ノード１回分が使われるので、「ノード総和＋内側ノード総和」としています。
「N*(N+1)//2」はノード総和です。1からNまでの整数の和の公式そのままです。
//演算子は割り算で商の整数部を返します。
「sum([i for i in Li])」は内側ノードLiの総和です。
・LL = [list(L)+[Sa//n-sum(L)] for L in combinations(Li, 2)]
リストLLは枝候補リストです。内包表記で記述しています。
まず内側ノードLiからノード２つの組合せタプルをループ変数Lとして先頭に回します。
list(L)は直後にリストを連結するため、編集不可のタプルから編集可能なリストへ変換しておきます。
「Sa//n」はライン総和Saを枝数nで割ることで枝ライン１つ分の和のことです。
[Sa//n-sum(L)]は、この枝１つ分の和から内側ノード２つ分の和sum(L)を差し引くことで、 この枝の外側ノードの値となります。
list(L)+[Sa//n-sum(L)の全体で、枝候補リストになります。
・for M in combinations(LL, n):
枝候補リストLLから、枝本数分の組合せを取り出した枝候補組合せリストをループ変数Mとします。
・La = [s for L in M for s in L]
Laは枝候補組合せリストMの全ノードリストです。内包表記しています。
枝候補組合せリストMから枝Lを取り出し後ろに回します。
そして取り出した枝Lからノードsを取り出し、先頭に回しそのままリストにためます。
・if sorted(La)==sorted(Li+Li+Lt): Q.append(g(M, Li, Lt))
上記の枝候補組合せリストの全ノードについて、内側ノードLiが２回と外側ノードLtが１回使われているかチェックします。
リストLaと、内側ノードLi２つ分と外側ノードLtの連結リストについて、
それぞれsorted関数で小さい順に並べて、まったく同じになるかをチェックします。
チェックOKならば、関数gに枝候補組合せリストM、内側ノードリストLi、外側ノードリストLtを
渡してます。
そして、関数gの戻り値である、外側ノード最小値からのノード連結値が最大になるようにを並べ替えた
連結値を連結値候補リストQにためます。
ここまでで全ての枝候補組合せについて、その連結値候補を取得しました。
・t = min([len(s) for s in Q])
tは連結候補の最小桁数です。
連結値候補リストQから連結値をループ変数sとして取り出し先頭に回し、
len関数で桁数を求めてリストにためます。
min関数でそのリストの最小値を取得します。
・return max([int(s) for s in Q if len(s)==t])
連結値候補リストQから連結値をループ変数sとして取り出し、後ろのif文に回します。
そして最小桁数と一致する場合だけ先頭に回し、int関数で数値化してリストにためます。
max関数でそのリストの最大値を取得し、呼び出し元に返却します。
上記処理は１秒程度で終わるので１分ルールは守っていますが、
処理速度をさらに向上するアイデアは以下の通りです。
・ライン総和Saがライン数nで割り切れない組は処理を飛ばす。
・枝候補リストLLでの外側ノード値が、外側ノードリストLtにない組は処理を飛ばす。
・枝候補リストLLでの外側ノード値で、外側ノードリストLtの全要素を使ってなければ処理を飛ばす。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
6531031914842725
（追記）
・20130120 ネタバレ注意の追記など
0 件のコメント:
コメントを投稿