프로젝트 오일러 68

마방진 성질을 갖는 5각 도형에서 얻을 수 있는 16자리 수의 최대값 구하기

문제 자세히 보기: [국어] [영어]

5각 도형의 빈 칸을 다음과 같이 로 지정할 수 있다.

각 선을 따라 구한 합이 모두 같으려면 다음 식을 만족해야 한다.

이렇게 하면 의 순열을 에 대입해가며 위 조건을 만족하는 조합을 찾을 수 있다. 가장 작은 수부터 시작해 시계 방향으로 돌아가며 나열해야 하므로 가장 작은 수가 에 오도록 한다. 순으로 숫자를 나열해 이어붙여 숫자를 만든 다음, 16자리 수 중 가장 큰 값을 구하면 답이 된다.

(ns p068
  (:require [clojure.math.combinatorics :refer [permutations]]))

(defn solve []
  (->> (permutations [1 2 3 4 5 6 7 8 9 10])
       (filter (fn [[a b c d e f g h i j]]
                 (= (+ a b c)
                    (+ d c e)
                    (+ f e g)
                    (+ h g i)
                    (+ j i b))))
       (filter (fn [[a b c d e f g h i j]] (= a (min a d f h j))))
       (map (fn [[a b c d e f g h i j]] (apply str [a b c d c e f e g h g i j i b])))
       (filter #(= 16 (count %)))
       (map #(Long/parseLong %))
       (apply max)))

실행 결과는 다음과 같다.

user=> (time (p068/solve))
"Elapsed time: 1971.586311 msecs"
653103191484??25

참고

• 프로젝트 오일러 68 풀이 소스 코드