Project Euler on Swift #002 (021 ~ 030)

e021.swift

/*

n의 약수들 중에서 자신을 제외한 것의 합을 d(n)으로 정의했을 때,
서로 다른 두 정수 a, b에 대하여 d(a) = b 이고 d(b) = a 이면
a, b는 친화쌍이라 하고 a와 b를 각각 친화수(우애수)라고 합니다.

예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은 d(220) = 284 입니다.
또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로 d(284) = 220 입니다.
따라서 220과 284는 친화쌍이 됩니다.

10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요.*/


#!/usr/bin/swift

import Foundation

func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}

func sumOfDivisors(n:Int) -> Int {
    var a = 1
    var s = 0
    while true {
        if n % a == 0 {
            let b = n / a
            if a == b {
                s += a 
                return s
            } else if a > b {
                return s
            } else {
                s += (a + b)
            }
        }
        a += 1
    }
}

func getFriendNumber(n:Int) -> Int? {
    let f = sumOfDivisors(n) - n
    if sumOfDivisors(f) - f == n {
        return f == n ? nil : f
    }
    return nil
}
timeit {

    var fs = Set<Int>()
    for i in 2...10000 {
        if let s = getFriendNumber(i) {
            fs.insert(i)
            fs.insert(s)
        }
    }
    
    var result = 0
    for i in fs {
        result += i
    }
    
    print(result)
}


//31626
//time: 166.692018508911 ms

e022.swift

/*
여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일 names.txt 이 있습니다 (우클릭해서 다운로드 받으세요).
이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다.

먼저 모든 이름을 알파벳 순으로 정렬합니다.
각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 숫자(A=1, B=2, ..., Z=26)를 모두 더합니다.
여기에 이 이름의 순번을 곱합니다.
예를 들어 "COLIN"의 경우, 알파벳에 해당하는 숫자는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다.

names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까?
*/

import Foundation

func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}

let strings = "\"MARY\"" // 너무 길어서 생략. 답은 맞게 나옴.

extension String {
    subscript(r:Range<Int>) -> String {
        let r = (advance(startIndex, r.startIndex)..<advance(startIndex, r.endIndex))
        return self[r]    
    }
    
    func rawString() -> String {
        return self[1..<(characters.count - 1)]
    }
}

let WORDS = (strings as NSString).componentsSeparatedByString(",").map{($0 as String).rawString()}
let SA = WORDS.sort()


func calcPoint(str:String, _ rank:Int) -> Int {
    // UTF8 codeValue는 UInt8 포맷이므로, 계산 후 Int로 캐스팅해야 한다.
    let s = str.utf8.map{$0 - 64}.reduce(0, combine:+)
    return Int(s) * rank
}

timeit{
    var s = 0
    for (i, c) in SA.enumerate() {
        s += calcPoint(c, i+1)
    }
    print(s)
}

e023.swift

/*
자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다.
예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다.
또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.

12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다.
따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.

해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다.
두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.

그렇다면, 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?*/


func sumOfDivisors(n:Int) -> Int {
    var a = 1
    let l = Int(sqrt(Double(n)))
    var s = 0
    while a <= (l) {
        if n % a == 0 {
            s = s + a + (n / a)
        }
        a += 1
    }
    if l * l == n {
        s -= l
    }
    return s
}

func isOverNum(n:Int) -> Bool {
    return sumOfDivisors(n) - n > n
}

func timeit(@noescape f:()->()) {
    let s = NSDate()
    f()
    let e = NSDate().timeIntervalSinceDate(s)
    print("time: \(e * 1000) ms")
}

timeit{

    let limit = 28123
    
    var overnums = Array(2...limit).filter(isOverNum)
    var numbers = [Int](count:(limit + 1), repeatedValue:0)
    
    for x in overnums {
        for y in overnums {
            if x + y > limit {
                break
            }
            numbers[x+y] = x + y
        }
    }
    
    let result = (limit * (limit + 1) / 2) - numbers.reduce(0, combine:+)
    print(result)
}
//  4179871
//  time: 9334.53500270844 ms

e024.swift

/*
어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다.

이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다.
0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다.

012   021   102   120   201   210
0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까?
*/


import Foundation

func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}

func factorial(n:Int) -> Int {
    if n < 2 {
        return 1
    }
    return Array(1...n).reduce(1, combine:*)
}

func divmod(a:Int, _ b:Int) -> (Int, Int) {
    return (a / b, a % b)
}

func permutation<T>(n:Int, _ list:[T]) -> [T] {
    if list.count == 0 {
        return list
    }
    let (q, r) = divmod(n, factorial(list.count - 1))
    return [list[q]] + permutation(r, Array(list[0..<q]) + Array(list[(q+1)..<list.count]))
}

timeit{
    let result = "".join(permutation(999999, Array(0...9)).map{"\($0)"})
    print(result)
}

//2783915460
//time: 3.14396619796753 ms

e025.swift

/*
피보나치 수열은 아래와 같은 점화식으로 정의됩니다.

Fn = Fn-1 + Fn-2  (단, F1 = 1, F2 = 1).
이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
수열의 값은 F12에서 처음으로 3자리가 됩니다.

피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까?
*/

func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}


struct BigInt: CustomStringConvertible { 
    // Swift 2.0 에서는 Printable이 CustomStringConvertible로 변경됨

    static let UNIT = 100000000 // 8자리씩 끊어서 이용함. 32비트에서는 4자리로.
    let unit_count = 8
    typealias NumberBucket = (Int, Int)

    let data: [NumberBucket]


    init(_ buckets: [NumberBucket]) {
        data = BigInt.roundUp(buckets)
    }


    init(var _ intValue:Int) {
        var level = 0
        var temp = [NumberBucket]()

        while intValue > 0 {
            temp.append((intValue % BigInt.UNIT, level))
            level += 1
            intValue = intValue / BigInt.UNIT
        }

        data = temp
    }


    init(_ strValue:String) {
        var level = 0
        var temp = [NumberBucket]()
        let u = Array(strValue.utf8).map{ Int($0) - 48 }
        let l = u.count
        for a in 0...l/unit_count {
            var d = 0
            for b in 0..<unit_count {
                let c = l - (unit_count * a + unit_count - b - 1) - 1
                if c < 0 {
                    continue
                }
                d = d * 10 + u[c]
            }
            temp.append((d, level))
            level += 1
        }
        data = temp
    }


    var description: String {
        let d = data.sort{ $0.1 > $1.1 }
        return "\(d[0].0)" + "".join(d[1..<d.count].map{String(format:"%08d", $0.0)})
        // return "".join(d.map{String($0)})
    }


    static func roundUp(buckets:[NumberBucket]) -> [NumberBucket] {
        let maxKey = buckets.map{ $0.1 }.reduce(buckets[0].1){ $0 > $1 ? $0 : $1 }
        var result = [NumberBucket]()
        var flag = 0
        for k in 0...maxKey {
            var s = buckets.filter{ $0.1 == k }.map{ $0.0 }.reduce(flag, combine: +)
            if s >= BigInt.UNIT {
                flag = s / BigInt.UNIT
                s = s % BigInt.UNIT
            } else {
                flag = 0
            }
            result.append((s, k))
        }
        if flag > 0 {
            result.append((flag, maxKey+1))
        }
        return result
    }


    static func multiplyNumberBucket(l:NumberBucket, _ r:NumberBucket) -> [NumberBucket] {
        let x = l.0 * r.0
        let y = l.1 + r.1
        if x < BigInt.UNIT {
            return [(x, y)]
        }
        return [(x % BigInt.UNIT, y), (x / BigInt.UNIT, y+1)]
    }    

    func add(target:BigInt) -> BigInt {
        return BigInt(data + target.data)
    }

    func multiply(target:BigInt) -> BigInt {
        var result = [NumberBucket]()
        for a in data {
            for b in target.data {
                result += BigInt.multiplyNumberBucket(a, b)
            }
        }
        return BigInt(result)
    }
}

func +(lhs:BigInt, rhs:BigInt) -> BigInt {
    return lhs.add(rhs)
}

func *(lhs:BigInt, rhs:BigInt) -> BigInt {
    return lhs.multiply(rhs)
}


timeit{
    var a = BigInt("1")
    var b = BigInt("1")
    var n = 3
    while "\(b)".characters.count < 1000 {
        (a, b) = (b, a + b)
        // print("\(n): \(b)")
        n = n + 1
    }
    print(b)
    print(n - 1)
}

//4782
//time: 29415.2110219002 ms

e026.swift

#!/usr/bin/swift
import Foundation
/*


분자가 1인 분수를 단위분수라고 합니다. 분모가 2에서 10까지의 단위분수는 아래와 같습니다.

숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 "6"으로 0.166666...처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다.

d 를 1000 이하의 정수라고 할 때, 단위분수 1/d 의 순환마디가 가장 긴 수는 무엇입니까?
 */

// 1/7 을 계산해보자.

import Foundation


func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}


func findCircularUnit(num:Int) -> [Int] {
    var ds = [Int]()
    var ns = [Int]()
    var k = 1
    while true {
        if ds.contains(k) {
            let c = ds.indexOf(k)!
            let result = ns[c..<(ns.count)]
            return Array(result)
        }
        ds.append(k)
        let (q, r) = (k / num, k % num)
        if r == 0 {
            break
        }
        ns.append(q)
        k = 10 * r
    }
    return []
}

func min_<T:Comparable>(l:T, _ r:T) -> T {
    return l < r ? l : r
}


timeit{
    let result = Array(1...1000).map{ ($0, findCircularUnit($0).count) }.reduce((0,0)){
         let (a, x) = $0
         let (b, y) = $1
         return x < y ? $1 : $0
         }
    
    print(result.0)
}

//983
//time: 3335.56699752808 ms

e027.swift

#!/usr/bin/swift



/*


오일러는 다음과 같은 멋진 2차식을 제시했습니다.

    n2 + n + 41 

이 식의 n에다 0부터 39 사이의 숫자를 넣으면, 그 결과는 모두 소수가 됩니다.
하지만 n = 40일 때의 값 402 + 40 + 41 은 40×(40 + 1) + 41 이므로 41로 나누어지고, n = 41일 때 역시 412 + 41 + 41 이므로 소수가 아닙니다.

컴퓨터의 발전에 힘입어 n2 − 79n + 1601 이라는 엄청난 2차식이 발견되었는데, 이것은 n이 0에서 79 사이일 때 모두 80개의 소수를 만들어냅니다. 이 식의 계수의 곱은 -79 × 1601 = -126479가 됩니다.

아래와 같은 모양의 2차식이 있다고 가정했을 때,

    n2 + an + b   (단 | a | < 1000, | b | < 1000) 

0부터 시작하는 연속된 n에 대해 가장 많은 소수를 만들어내는 2차식을 찾아서, 그 계수 a와 b의 곱을 구하세요.
*/


/*
    -999~999 범위를 다 뒤져봐도 오래 걸리지는 않는데, 
    a는 음수이고, b는 -a보다 큰 양수임을 감안하면 역시 매우 빨리 끝낼 수 있다. 
*/

// swift 2.0 

import Foundation

func isPrime(n:Int) -> Bool {
    switch true {
    case n < 2:
        return false
    case n == 2, n == 3:
        return true
    case n % 2 == 0, n % 3 == 0:
        return false
    case n < 9:
        return true
    default:
        var k = 5
        let l = Int(sqrt(Double(n)))
        while k <= l {
            if n % k == 0 || n % (k + 2) == 0 {
                return false
            }
            k += 6
        }
        return true
    }
}


func make_equation(a:Int, _ b:Int) -> (Int) -> Int {
    func calc(n:Int) -> Int {
        return n*n + a * n + b
    }
    return calc
}

func test(@noescape f:(Int) -> Int) -> Int {
    var i = 0
    while true {
        let c = f(i)
        if c < 2 || !(isPrime(c)) {
            return i-1
        }
        i += 1
    }
}



func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}

timeit{
    var maxSep = 0
    var answer = (0,0,0)
    for a in -999...0 {
        for b in (-a)...999 {
            let f = make_equation(a, b)
            let seq  = test(f)
            if maxSep < seq {
                maxSep = seq
                answer = (a, b, a*b)
            }
        }
    }
    print(answer)
    print(maxSep)
}

// (-61, 971, -59231)
// 70
// time: 83.8729739189148 ms

e028.swift

/*
숫자 1부터 시작해서 우측으로부터 시계방향으로 감아 5×5 행렬을 만들면 아래와 같이 됩니다.

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

여기서 대각선상의 숫자를 모두 더한 값은 101 입니다.

같은 방식으로 1001×1001 행렬을 만들었을 때, 대각선상의 숫자를 더하면 얼마가 됩니까?
*/

import Foundation


func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}

timeit{
    var a = 1
    var s = 1
    var k = 2
    for _ in 1...500 {
        for _ in 1...4 {
            a += k
            s += a
        }
        k += 2
    }
    print(s)
}

//669171001
//time: 0.593006610870361 ms

e029.swift

/*
2 ≤ a ≤ 5 이고 2 ≤ b ≤ 5인 두 정수 a, b로 만들 수 있는 ab의 모든 조합을 구하면 다음과 같습니다.

22=4,  23=8,  24=16,  25=32
32=9,  33=27,  34=81,  35=243
42=16,  43=64,  44=256,  45=1024
52=25,  53=125,  54=625,  55=3125
여기서 중복된 것을 빼고 크기 순으로 나열하면 아래와 같은 15개의 숫자가 됩니다.

4,  8,  9,  16,  25,  27,  32,  64,  81,  125,  243,  256,  625,  1024,  3125

그러면, 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b를 가지고 만들 수 있는 ab는 중복을 제외하면 모두 몇 개입니까?*/

import Glibc
import Foundation


func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}


func transform(a: (Int, Int)) -> (Int, Int)
{
    guard case let l = Int(sqrt(Double(a.0))) where l < 2 
    else { return a }

    for i in 2...(l+1) {
        for j in 2...7 {
            let c = Int(pow(Double(i), Double(j)))
            if c == a.0 {
                return (i, j * a.1)
            }
            if c > a.0 {
                break
            }
        }
    }
    return a
}

let tuple2String: ((Int, Int)) -> String = {a in "\(a.0)^\(a.1)"}
let test: ((Int, Int)) -> Void = { x in
    print(tuple2String(transform(x)))
}


timeit{
    var s = Set<String>()

    for a in 2...100 {
        for b in 2...100 {
            let c = (a, b)
            let d = tuple2String(transform(c))
            s.insert(d)
        }
    }

    print(s.count)
}

// 9183
// time: 25.5889892578125 ms

e030.swift

/*
각 자리의 숫자를 4제곱해서 더했을 때 자기 자신이 되는 수는 놀랍게도 단 세 개밖에 없습니다.

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44
(1 = 14의 경우는 엄밀히 말해 합이 아니므로 제외합니다)

위의 세 숫자를 모두 더하면 1634 + 8208 + 9474 = 19316 입니다.

그렇다면, 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은 얼마입니까?
*/

import Foundation


func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}

func transform(var n:Int) -> Int {
    var s = 0
    while n > 0 {
        let c = n % 10
        s += (c * c * c * c * c)
        n = n / 10
    }
    return s
}

func test(n:Int) -> Bool {
    return n == transform(n)
}

timeit{
    var arr = [Int]()
    for i in 2...999999 {
        if test(i) {
            arr.append(i)
        }
    }
    
    let result = arr.reduce(0, combine: +)
    print(arr)
    print(result)
}

//443839
//time: 66.5490031242371 ms

24번

N 개 원소를 사전식으로 순열을 만드는 경우
첫번째 원소가 바뀌는 지점은 (N-1)! 이 오는 지점이다. 따라서
그 다음 글자 그 다음글자를 만드는 지점은 각각 (남은 원소의 수 - 1)! 로 나머지를 계속 나누어가면서
정의할 수 있게 된다.

따라서

let (q, r) = divmod(n, factorial(list.count - 1))
[list[q]] + permutation(r, {q번째를 뺀 나머지 원소들})

로 구할 수 있다.