프로젝트 오일러 93 @ntalbs' stuff

숫자 4개와 사칙연산을 써서 가장 길게 이어지는 숫자 만들기
문제 자세히 보기: [국어] [영어]

숫자 네 개에 사칙연산자를 세 개 사용할 수 있으므로, 각 숫자를 A, B, C, D라 하고 사칙연산자를 Op₁, Op₂, Op₃라 하면, 다음과 같은 조합을 생각할 수 있다. 모든 연산은 괄호로 둘러싸 연산자 우선순위를 고려하지 않게 하면 생각하기가 조금 쉬워진다.

((A Op₁ B) Op₂ C) Op₃ D
(A Op₁ B) Op₂ (C Op₃ D)
(A Op₁ (B Op₂ C)) Op₃ D
A Op₁ ((B Op₂ C) Op₃ D)
A Op₁ (B Op₂ (C Op₃ D))

0부터 9까지 수 중 4개를 선택해 A, B, C, D에 할당하고 Op₁, Op₂, Op₃에 사칙연산을 할당해 계산한 결과를 모은 집합을 구한 다음 1부터 가장 길게 이어지는 숫자를 생성하는 A, B, C, D를 구하면 문제를 풀 수 있다. 0부터 9의 수 중 4개를 선택할 때는 combinations를, 이렇게 선택한 수의 순열을 구할 때는 permutations를 쓸 수 있다.

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

어떤 수를 0으로 나누면 예외가 발생하므로 다음과 같이 예외를 던지지 않는 div 함수를 만들어두는 것이 좋겠다. 이 함수는 제수가 0인 경우 nil을 리턴한다.

(defn- div [a b]
  (if (zero? b) nil (/ a b)))

+, -, *, div는 인자 중 하나가 nil이면 NullPointerException 예외를 던진다. 계산 편의를 위해 인자 중 하나가 nil이면 예외를 던지는 대신 nil을 리턴하는 사칙연산 함수를 만드는 게 좋겠다.

(defn- op [f]
  (fn [a b]
    (if-not (or (nil? a) (nil? b))
      (f a b))))

(op +)는 두 인자 모두 nil이 아닌 경우는 인자를 더해 리턴하고 인자 중 하나라도 nil이면 nil을 리턴하는 함수를 리턴한다.

주어진 A, B, C, D로 생성할 수 있는 숫자 목록을 만드는 함수는 다음과 같이 작성할 수 있다. 이 함수에서는 A, B, C, D의 순열을 고려하지 않는다. 리턴하기 전에 nil을 제거한다.

(defn- target [[a b c d]]
  (let [ops [(op +) (op -) (op *) (op div)]]
    (->> (for [op1 ops, op2 ops, op3 ops]
           [(op3 (op2 (op1 a b) c) d)
            (op2 (op1 a b) (op3 c d))
            (op3 (op1 a (op2 b c)) d)
            (op1 a (op3 (op2 b c) d))
            (op1 a (op2 b (op3 c d)))])
         (flatten)
         (remove nil?))))

A, B, C, D의 순열까지 고려해 생성 가능한 숫자 목록을 만드는 함수는 다음과 같이 작성할 수 있다. permutations를 이용해 $A, B, C, D$의 순열을 구해 위에서 정의한 target 함수를 호출한다. 생성된 목록에서 nil을 제거하고 중복을 제거한 후 양의 정수만 남긴 후 정렬한 후 맵에 저장한다. 문제는 abcd를 구하는 것이므로 [a b c d]를 맵에 함께 저장한다.

(defn- gen [[a b c d]]
  (->> (permutations [a b c d])
       (mapcat #(target %))
       (distinct)
       (filter #(and (pos? %) (integer? %)))
       (sort)
       (hash-map :set [a b c d] :target)))

숫자 목록이 얼마나 길게 이어지는 지 세는 함수는 다음과 같이 작성할 수 있다.

(defn- count-consective [ns]
  (->> (partition 2 1 ns)
       (take-while (fn [[a b]] (= a (dec b))))
       (count)
       (inc)))

[a b c d]를 abcd로 만들어주는 함수는 다음과 같이 간단히 작성할 수 있다.

(defn- digits->int [ds]
  (reduce (fn [acc x] (+ (* 10 acc) x)) ds))

이제 다음과 같이 문제를 풀 수 있다.

(defn solve []
  (->> (combinations (range 1 10) 4)
       (map gen)
       (apply max-key (fn [x] (count-consective (:target x))))
       (:set)))

실행 결과는 다음과 같다. 답을 구하는 데 2.5초 정도 걸린다.

p093=> (time (solve))
"Elapsed time: 2542.856429 msecs"
1??8

참고

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