오일러 프로젝트 42

오일러 프로젝트 42 번 문제는 단어의 각 글자를 값으로 치환하여 더한 값이 삼각수가 되는지를 검사한다. 삼각수를 검사하는 로직만 만들면 그외에는 단순 입출력과 계산 문제이다.

n번째 삼각수는 tn = ½ n (n + 1) 이라는 식으로 구할 수 있는데, 처음 10개는 아래와 같습니다. 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, … 어떤 영어 단어에 대해서, 각 철자의 알파벳 순서(A=1, B=2, …, Z=26)를 모두 더한 값을 ‘단어값’이라 부르기로 합니다. 예를 들어 ‘SKY’의 단어값은 19 + 11 + 25 = 55가 되는데, 이것은 우연히도 t10과 같습니다. 이렇게 어떤 단어의 단어값이 삼각수일 경우에는 이 단어를 ‘삼각단어’라 부르기로 합니다. 약 16KB의 텍스트 파일 words.txt에는 2000개 정도의 영어 단어가 수록되어 있습니다. 이 중에서 삼각단어는 모두 몇 개입니까?  (http://euler.synap.co.kr/prob_detail.php?id=42)

접근

n 번째 삼각수는 로 구한다. 이를 거꾸로 풀어보면 가 된다. 이 값을 계산하여 정수가 되는지를 살펴보면 검사할 수 있다. 아니면 영어 단어가 길어봐야 60글자까지 있을 수 있으니¹ 5200정도 까지의 삼각수를 구해놓고 여기에 포함되는지로 검사하는 방법도 있을 수 있다.
예전에는 단어를 전부 소스에다가 복사해서 박아서 썼는데, 네트워크를 통하든 디스크를 통하든 파일 입출력을 다루는 것은 매우 기본적이고 필수적인 소양이라 보고, 네트워크를 통해서 단어 데이터를 받아오도록 처리했다.

from urllib.request import urlopen
def e42():
  make_tri = lambda n: n*(n+1)//2
  ts = set(make_tri(x) for x in range(1, 1000))
  def word_point(word):
    return sum(ord(c) - 64 for c in word)
  with urlopen('http://euler.synap.co.kr/files/words.txt') as f:
    words = (w.strip('"') for w in f.read().decode().split(',')
    points = (word_point(x) for x in words)
    print(sum(1 for x in points if x in ts))
%time e42()

Swift 풀이

동일한 알고리듬이다. 단어 점수를 구할 때, 따옴표를 제외하기 위해서 A…Z 까지의 문자인지는 코드값의 범위로 처리하고 (범위 외에는 nil 로 계산) 이를 flatMap 에 적용해서 간단히 필터링과 맵핑을 동시에 적용할 수 있다. (트리밍 기능은 NSString 에 있기 때문에 이를 써도 되는데 이는 뒤에서 다시 언급한다.)
그외에 Swift에서는 의외로, String(contentsOf:) 에서 URL 데이터를 주고 디스크나 네트워크의 파일을 같은 방식으로 읽어온다. 참고로 해당 기능은 동기식으로 동작한다.

import Foundation
main: do {
  guard let url = URL(string: "http://euler.synap.co.kr/files/words.txt"),
        let contents = try? String(contentsOf: url)
  else { break main }
  func wordPoint(_ s: Substring) -> Int {
    return s.utf8.flatMap{ b in
      let c = Int(b)
      guard (65...90) ~= c else { return nil } // A...Z 범위가 아니면 제외
      return c - 64
      }.reduce(0, +)
  }
  let make_t: (Int) -> Int = { $0 * ($0 + 1) / 2 }
  let ts = Set((1...1000).map(make_t))
  let result = contents.split(separator:",").map(wordPoint)
               .filter{ ts.contains($0) }.count
  print(result)
}  

Swift의 String 타입에는 양끝의 문자들을 트리밍하는 메소드가 없다. 이는 NSString 에 trimmingCharacters(in:) 으로 정의되어 있으므로 이를 대신할 수 있다. 따라서 wordPoint() 는 다음과 같이 작성할 수 있다.

func wordPoint(_ s: Substring) -> Int {
  return  s.trimmingCharacters(in: CharacterSet(charactersIn: "\""))
         .utf8.map{ Int($0) - 64 }.reduce(0,  +)
}

대략 네트워크통신 시간 포함해서 0.1초 가량 걸린다.