오일러 프로젝트 61 번 문제는 꼬리에 꼬리를 무는 N각수의 집합을 찾는 문제이다.
삼각수, 사각수, 오각수 같은 다각수들은 아래의 공식으로 만들 수 있습니다.
- 삼각수 –
> 1, 3, 6, 10, 15 …
- 사각수 –
> 1, 4, 9, 16, 25, …
- 오각수 –
>1, 5, 12, 22, 35, …
- 육각수 –
>1, 6, 15, 28, 45, …
- 칠각수 –
> 1, 7, 18, 34, 55, …
- 팔각수 –
> 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]검사함수 만들기
검사함수는 다음과 같은 알고리듬으로 전개된다.
- 임의의 다각수 N과, 재귀의 종료여부를 검사할 레벨값, 그리고 지금까지 만들어져 온 누적 연결고리 값을 받는다.
- 레벨이 0에 다다랐다면, 누적 연결고리의 끝과 처음이 다시 이어지는지 검사한다. 조건을 만족하면 누적 연결고리를 리턴하고, 그렇지 않으면 None을 리턴한다.
- 후보가 있다면, 각 후보에 대해서 현재 누적 연결고리 끝에 추가한 다음 재귀호출한다. 그 결과가 존재한다면 그대로 리턴하고 None이라면 다음 후보로 진행한다.
- 후보가 더이상 없다면 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))
break4자리 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()