오일러 프로젝트 61

오일러 프로젝트 61 번 문제는 꼬리에 꼬리를 무는 N각수의 집합을 찾는 문제이다.

삼각수, 사각수, 오각수 같은 다각수들은 아래의 공식으로 만들 수 있습니다.

  • 삼각수 – P_{3,n} = n \cdot (n + 1) / 2 > 1, 3, 6, 10, 15 …
  • 사각수 – P_{4,n} = n^2 > 1, 4, 9, 16, 25, …
  • 오각수 – P_{5,n} = n \cdot (3n - 1) / 2 >1, 5, 12, 22, 35, …
  • 육각수 – P_{6,n} = n \cdot (2n - 1) >1, 6, 15, 28, 45, …
  • 칠각수 – P_{7,n} = n \cdot (5n - 3) / 2 > 1, 7, 18, 34, 55, …
  • 팔각수 – P_{8,n} = n \cdot (3n - 2) > 1, 8, 21, 40, 65, …

그런데, 4자리 숫자 8128, 2882, 8281 (순서대로) 에는 세 가지 재미있는 성질이 있습니다. 먼저 각 숫자들은 두 자리씩 꼬리를 물고 진행합니다. 그리고 각 숫자들은 모두 서로 다른 다각수입니다. (순서대로 3, 4, 5각수) 이런 성질을 갖는 네자리 숫자 세 개는 이들이 유일합니다.

이렇게 순환하면서 서로 다른 다각수가 되는 4자리 숫자 여섯개의 유일한 순서쌍을 찾고 그 합을 구하세요

접근

서로 연결되어야 하는 다각수는 “다른 다각수”이면 되지 삼각수 다음에 사각수, 다음에 오각수… 이런 순서가 지켜져야 할 필요는 없다. (그냥 문제의 예시가 공교로울 뿐) 접근 방식은 간단한데. 어떤 N각수 A가 주어지면 그로부터 연결 가능한 후보의 성질은 명확한데, N각이 아닌 다각수이면서 그 앞 두자리가 A의 끝 두자리와 같은 것이다.

여기서는 4자리 수라는 범위가 정해졌으므로 4자리의 삼각~팔각수를 모조리 구한 다음에,  모든 대상에 대해서 연결을 만들어 놓고 찾아나가면 된다. 찾는 과정은 재귀적으로 쓰면 간결하게 쓸 수 있다.

파이썬 구현

모든 네 자리 다각수 구하기

다각수 구하는 공식은 모두 문제에 나와 있다.  n의 범위가 문제인데, 삼각수가 가장 잘게(?) 분포하는데 P3,100은 5050 이므로 200개 항에 대해서 다각수들을 모두 만들고,  그 중에 네 자리 인 것만 추리면 된다. 단, 이렇게 만들어진 다각수는 몇 각수인지를 구분해야 한다. 이는 간단하게 튜플을 이용해서 마치 익명타입처럼 사용할 수 있다.

def make_numbers(n):
  return [ n * (n +1) // 2, n * n, n * ( 3 * n - 1) // 2,
           n * (2 * n - 1), n * (5 * n - 3) // 2, n * (3 * n - 2) ]

numbers = []
for n in range(1, 200):
  for i, m in enumerate(make_numbers(n)):
    if 1000 <= m < 10000:
      numbers.append[(i+3, m)]

모든 링크 만들기

만들어진 다각수 하나에 대해 뒤쪽으로 연결 가능한 모든 수를 결정한다. 이 맵이 모든 문제 해결의 출발점이 될 것이다.

links = dict()
for x in numbers:
    links[x] = [y for y in numbers if y[0] != x[0] and x[1] % 100 == y[1] // 100]

검사함수 만들기

검사함수는 다음과 같은 알고리듬으로 전개된다.

  1.  임의의 다각수 N과, 재귀의 종료여부를 검사할 레벨값, 그리고 지금까지 만들어져 온 누적 연결고리 값을 받는다.
  2. 레벨이 0에 다다랐다면, 누적 연결고리의 끝과 처음이 다시 이어지는지 검사한다. 조건을 만족하면 누적 연결고리를 리턴하고, 그렇지 않으면 None을 리턴한다.
  3. 후보가 있다면, 각 후보에 대해서 현재 누적 연결고리 끝에 추가한 다음 재귀호출한다. 그 결과가 존재한다면 그대로 리턴하고 None이라면 다음 후보로 진행한다.
  4. 후보가 더이상 없다면 None을 리턴한다.

이를 코드로 옮기면 다음과 같다.

def test(node, level, acc):
  if level is 0:
    if acc[-1][1] % 100 == acc[0][1] // 100:
      return acc
    return None

  ## 현재 노드에서 연결될 수 있는 노드 중에서, 누적 링크와 같은 다각수는 제외하고 체크
  for c in [x for x in links[node] if x[0] not in [y[0] for y in acc]]:
    new_acc = acc + [c]
    result = test(c, level - 1, new_acc)
    if result:
      return result
   return None

재귀 코드는 늘 단순하고 간결하다. 최종 정리

for n in numbers:
  result = test(n, 6, [])
  if result:
    print(sum(x[1] for x in result))
    break

4자리 n 각수를 모두 구한다고 해봐야 몇 개 안되기 때문에 매우 빨리 끝난다. (약 40ms)

Swift 풀이

Swift도 똑같은 방식으로 처리할 수 있는데, 한가지 문제가 있다. Swift의 사전의 키는 Hashable 프로토콜을 따라야 하는데 튜플은 해시를 잡지 못하기 때문에 그대로 쓸 수가 없다. 따라서 별도의 타입을 만들어야 한다.  다행히 모든 값의 크기는 4자리 정수이므로, 5자리째에 다각수형태를 넣는 식으로 해시값을 만들 수 있다.

그외의 다른 동작들은 위 파이썬 코드와 동일하다. 별개의 타입을 따로 만든 관계로 코드는 보다 읽기가 수월한 편이다.

struct NumberNode: Hashable {
  let n: Int
  let value: Int
  let head: Int
  let tail: Int

  init(n: Int, value: Int) {
    self.n = n
    self.value = value
    head = value / 100
    tail = value % 100
  }

  var hashValue: Int { return n * 10000 + value }
}

func makeNumbers(_ n: Int) -> [Int] {
  return [ n * (n + 1) / 2, n * n, n * (3 * n - 1) / 2,
           n * (2 * n - 1), n * (5 * n - 3) / 2, n * (3 * n - 2)]
}

let numbers: Set<NumberNode> = {
  var n = Set<NumberNode>()
  for i in 1...200 {
    let ns = makeNumbers(i)
    for (i, x) in ns.enumerated() {
      n.insert(NumberNode(n: i+3, value: x))
    }
  }
  return n
}()

var links = Dictionary<NumberNode, Set<NumberNode>>()
for n in numbers {
  if links[n] == Set(numbers.filter{ $0.n != n.n && $0.head == n.tail })
}

func test(node: NumberNode, level: Int, acc: [NumberNode]) -> [NumberNode]? {
  guard level > 0 else {
    if acc.first!.head == acc.last!.tail { return acc }
    return nil
  }
  guard candidates = links[node] else { return nil } 
  for c in candidates {
    let newAcc = acc + [c]
    if let result = test(node: c, level: level - 1, acc: newAcc) {
      return result
    }
  }
  return nil
}

func solve() {
  for n in numbers {
    if let result = test(node: n, level: 6, acc:[]) {
      print(result.map{ $0.value }.reduce(0, +))
      return
     }
   }
}

solve()