Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
下に示す図のようなものを"magic" 3-gon ringという. これは$1$～$6$の数字を当てはめて, 各列の数字の和が$9$となっている. これを例として説明する.
外側のノードのうち一番小さいものの付いた列(例では$4,3,2$)から時計回りに回ってそれぞれ列の数字を$3$つ連ねて説明する. 例えば例のものは$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$ |
この組の各数字を連結して, $9$桁の数字で表すことができる. 例えば, 上の図のものは$4,3,2; 6,2,1; 5,1,3$であるので$432621513$である.
さて, 下の図に$1$～$10$の数字を当てはめ, 各列の数字の和が等しくなる"magic" 5-gon ringを作って, それを表す$16$桁または$17$桁の数字のうち, $16$桁のものの最大の数字を答えよ.
(注, $3$つの場合の例を見ても分かる通り, 列の始まりの数字を比べた時一番小さい数字で始まる列から時計回りに繋げるという条件のもとで文字列を生成する必要があります. この条件下で最大となる数字を答えてください. )
アプローチ
五角形に入る値を$a_1$、...$a_5$、外側の値で$a_1$から伸びているものを$a_6$、以下$a_k$から伸びているものを$a_{k+5}$とおく。
$16$桁にせよという条件より、$10$は$a_6$から$a_{10}$のいずれかにあることがわかる。
この条件により全パターンを考えても$1814400$通りしかない。
面倒なので全パターン計算してみる。
解答
time seq -s"," 10 |
python -c "import itertools;print list(itertools.permutations(input(),10))" |
sed 's/),/)\n/g' |
tr -d "[]()'," |
awk '$6$7$8$9$10 ~ ".*10.*"' |
awk '{print $0,$6+$1+$2,$7+$2+$3,$8+$3+$4,$9+$4+$5,$10+$5+$1}' |
awk '$11==$12' |
awk '$12==$13' |
awk '$13==$14' |
awk '$14==$15' |
awk '{min=10;for(i=6;i<=10;i++){if($i<min){min=$i;m=i}};print $0,m}' |
awk '{print $6$1$2,$7$2$3,$8$3$4,$9$4$5,$10$5$1,$NF}' |
awk '{print $1,$2,$3,$4,$5,$1,$2,$3,$4,$6}' |
awk '{for(i=$NF-5;i<=$NF-1;i++){printf $i};print ""}' |
sort |
tail -1
6531031914842725
real 0m18.051s
user 0m23.208s
sys 0m1.129s
$1$から$10$までの順列を出すうまい方法はないかと検索してみたところ、pythonで関数があるようだったので利用させてもらった。
答え合わせ
こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/068.html
参考にさせて頂いたサイト様
Pythonで直積，順列，組み合わせ，階乗の計算 _ 粉末@それは風のように (日記)
Python Tips：ワンライナーが書きたい - Life with Python