Project Euler on Swift # 000 (001 ~ 010)

e001.swift

// 10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다.
// 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?

import Foundation

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

timeit{
  let a = Array(0..<1000).filter({ $0 % 3 == 0 || $0 % 5 == 0})
  print(a.reduce(0, combine: +))
  
}
// 233168
// time: 1.37102603912354 ms


timeit{
    var s = 0
    for i in 1..<1000 {
        if i % 3 == 0 || i % 5 == 0 {
            s += i
        }
    }
    print(s)
}
// 234168
// time: 0.0370144844055176 ms

e002.swift

/*
피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.

    1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 

짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?
*/

import Foundation

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


func makeGenerator() -> () -> Int {
    var a = 0
    var b = 1
    func f() -> Int {
        (a, b) = (b, a+b)
        return b
    }
    return f
}

timeit{
    let fib = makeGenerator()
    var s = 0
    while true {
        let c = fib()
        if c > 400_0000 {
            break
        }
        if c % 2 == 0 {
            s += c
        }
    }
    
    print(s)
}
// 4613732
// time: 0.454962253570557 ms

e003.swift

/*
어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.

600851475143의 소인수 중에서 가장 큰 수를 구하세요.
*/


import Foundation

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

timeit {
    
    var s = 600851475143
    var i = 3
    
    
    while s > i {
        if s % i == 0 {
            s = s / i
        } else {
            i += 2
        }
    }
    
    print(s)
}
// 6857
// time: 0.493943691253662 ms

e004.swift

/*
앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.
세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?
*/

// Swift 2.1
import Foundation

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

extension Int {
    var isPalindrome: Bool {
        var l = [Int]()
        var s = self
        while s > 0 {
            l.append(s % 10)
            s = s / 10
        }
        return l.reduce(0){ $0 * 10 + $1 } == self
    }
}

timeit{
    var m = 0
    for a in 999.stride(to:500, by:-1) {
        for b in 999.stride(to:500, by:-1) {
          if case let c = a * b where c.isPalindrome && c > m {
            m = c
          }
        }
    }
    print(m)
}

// 906609
// time: 950.99800825119 ms <-- 1156.97801113129 ms

e005.swift

/*
1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?
*/



import Foundation

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


func gcd(a:UInt, _ b:UInt) -> UInt {

    guard a * b != 0 else { return 0 }
    
    let (x, y) = (max(a,b), min(a,b))
    if x % y == 0 {
        return y
    }
    
    return gcd(y, x % y)
}

func lcm(a:UInt, _ b:UInt) -> UInt {
    let g = gcd(a, b)
    return a / g * b
}

timeit{
    print(Array(1...20).reduce(1, combine: lcm))
}
// 232792560
// time: 0.585019588470459 ms

e006.swift

/*
1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).

    12 + 22 + ... + 102 = 385

1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).

    (1 + 2 + ... + 10)2 = 552 = 3025

따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.

그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?
*/

import Foundation

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

timeit{
    let sumOfSquare = Array(1...100).map{ $0 * $0 }.reduce(0, combine:+)
    let sum = Array(1...100).reduce(0, combine: +)
    let result = sum * sum - sumOfSquare
    print(result) 
}

// 25164150
// time: 0.81104040145874 ms

e007.swift

/*
소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.

이 때 10,001번째의 소수를 구하세요.*/


import Foundation

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


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(floor(sqrt(Double(n))))
        while k <= l {
            if n % k == 0 || n % (k + 2) == 0 {
                return false
            }
            k += 6
        }
        return true
    }
}

timeit{
    var c = 1
    var n = 3
    while c < 10_000 {
        if isPrime(n) {
            c += 1
        }
        n += 2
    }
    print(n-1) 
}

// 104743
// time: 11.6269588470459 ms

e008.swift

/*


다음은 연속된 1000자리 숫자입니다 (읽기 좋게 50자리씩 잘라놓음).

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

여기서 붉게 표시된 71112의 경우 7, 1, 1, 1, 2 각 숫자를 모두 곱하면 14가 됩니다.
이런 식으로 맨 처음 (7 × 3 × 1 × 6 × 7 = 882) 부터 맨 끝 (6 × 3 × 4 × 5 × 0 = 0) 까지 5자리 숫자들의 곱을 구할 수 있습니다.

이렇게 구할 수 있는 5자리 숫자의 곱 중에서 가장 큰 값은 얼마입니까?*/

import Foundation

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


timeit{
  let theString = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
  let numbers = theString.utf8.map{ Int($0) - 48 }
  let products = Array(0..<(numbers.count - 5)).map{numbers[$0..<($0+5)].reduce(1, combine: *)}
  let result = products.reduce(products[0], combine: max)
  print(result) // 4.4 msec
}

40824
time: 3.74197959899902 ms

e009.swift

/*
a + b + c = 1000 이 되는 피타고라스 수를 찾아, 그 곱을 구하세요.
*/


import Foundation

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

timeit{
    for a in 1...1000/3 {
        for b in a...(1000-a)/2 {
            let c = 1000 - a - b
            if (a*a + b*b == c*c) {
                print("\(a*b*c)")
                return
            } 
        }
    }
}

// 31875000
// time: 2.94202566146851 ms

e010.swift

import Foundation

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


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(floor(sqrt(Double(n))))
        while k <= l {
            if n % k == 0 || n % (k + 2) == 0 {
                return false
            }
            k += 6
        }
        return true
    }
}

timeit{
    let result = Array(1...200_0000).filter(isPrime).reduce(0, combine: +)
    print(result)
}

// 142913828922
// time: 1530.3590297699 ms

// 배열을 이용한 함수형 풀이보다 루프를 도는 것이 더 빠르다.


/* much faster (at swiftstub.com) */
timeit{
    var result = 2 
    for i in 3.stride(to:200_0000, by:2)  {
        if isPrime(i) {
            result += i
        }
    }
    print(result)
}
// 142913828922
// time: 680.725991725922 ms


/* distributed process */


func process(n:Int, _ r:Int) -> Int {
  var result = 0
  for i in n..<n+r {
    if isPrime(i) { result += i }
  }
  return result
}

timeit{

    var result = 0
    var c = 4

    let queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0)
    let sq = dispatch_queue_create("sq", DISPATCH_QUEUE_SERIAL)
    /*:
      각 구간에서 계산한 값은 한 곳에서 취합한다.
      그 부분이 `result`에 업데이트되는데
      이를 안전하게 처리하기 위해서는 직렬 큐를 이용해서 업데이트한다.
      
      1. 메인큐를 이용해서 dispatch_async를 이용하는 경우: 결과가 업데이트되지 못하고 끝난다. 
      2. 메인큐를 이용해서 dispatch_sync를 이용하는 경우: 이미 메인큐는 비동기 그룹의 작업을 기다리는 중이므로 데드락이 발생한다.
      
      따라서 별도로 처리되는 독립 시리얼 큐를 만들고 취합을 여기서 한다.
    */
    let group = dispatch_group_create() // 그룹을 이용해서 최종적으로 동기화한다.

    let r = 200_0000 / c
    for i in 0..<c {
        dispatch_group_async(group, queue){ 
            let a = process(i*r, r)
            dispatch_main {
                result += a
            }
            //print("block \(i*r) ... \(i * r + r) : \(a)")
        }
    }
    dispatch_group_wait(group, DISPATCH_TIME_FOREVER)
    print(result)
}
// 약 581 ms
// 듀얼 코어 시스템에서는 구간을 3개 이상으로 쪼개는 것이 성능에 크게 영향을 주지 않는다.
// 쿼드 코어 시스템에서는 이 수치가 4일때까지는 거의 비례하게 성능이 증가한다.