Project Euler Q68 【Magic 5-gon ring】

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; $ 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$까지의 순열을 내는 좋은 방법은 없을까 검색해 보았는데, 파이썬에서 함수가 있는 것 같았기 때문에 이용하게 했다.

대답

이쪽의 사이트님과 일치하고 있으면 OK로 했다.
h tp // 킨쿄지마. 네 t/p지/068. HTML

참고로 한 사이트

파이썬에서 직적, 순열, 조합, 계승 계산 _ 분말 @ 그것은 바람처럼 (일기)
파이썬 팁 : 원라이너가 쓰고 싶다 - Life with Python