Swift the Euler Way

Quick notes on learning functional Swift with Project Euler. Presented at the Brooklyn Swift Meetup in July 28, 2015

http://www.meetup.com/Brooklyn-Swift-Developers/
https://github.com/dbgrandi/EulerKit
https://twitter.com/dbgrandi

Transcript

1. LEARNING SWIFT THE ULER WAY
5. PROJECT EULER ~500 MATH PROBLEMS THAT RANGE FROM EASY TO INSANELY DIFFICULT
6. PROBLEM #1 FIND THE SUM OF ALL THE MULTIPLES OF 3 OR 5 BELOW 1000
7. PROBLEM #454 DIOPHANTINE RECIPROCALS III IN THE FOLLOWING EQUATION , , AND ARE POSITIVE INTEGERS. FOR A LIMIT WE DEFINE F( ) AS THE NUMBER OF SOLUTIONS WHICH SATISFY . WE CAN VERIFY THAT F(15) = 4 AND F(1000) = 1069.
8. FIND F( )
9. FIND F(1 TRILLION)
10. FIND F(5 )
11. FIND F( )
12. SOME THINGS I'M NOT REALLY GREAT AT...
13. SWIFT FUNCTIONAL PROGRAMMERING MATH
14. SOME THINGS I EXCELL AT...
15. OPENING BROWSER TABS HITTING ⌘-U AND ⌘-R TIMES
16. PROBLEM #1 FIND THE SUM OF ALL THE MULTIPLES OF 3 OR 5 BELOW 1000.
17. extension Int { func isMultipleOf(i: Int) -> Bool { return i != 0 && self % i == 0 } }
18. extension Int { func isMultipleOf(i: Int) -> Bool { return i != 0 && self % i == 0 } func isMultipleOfAny(nums:[Int]) -> Bool { for i in nums { if self.isMultipleOf(i) { return true } } return false } }
19. WHAT IS FUNCTIONAL PROGRAMMING?
20. Functional programming is programming without assignment statements. — Uncle Bob
21. extension Int { func isMultipleOf(i: Int) -> Bool { return i != 0 && self % i == 0 } func isMultipleOfAny(nums:[Int]) -> Bool { return nums.map(isMultipleOf).reduce(false) {$0 || $1} } }
22. let sum = (1...999).filter{ $0.isMultipleOfAny([3,5]) }.reduce(0, combine:+)
23. SOME FUN THINGS...
24. SEQUENCES
25. struct FibonacciSequence: SequenceType { func generate() -> AnyGenerator<Int> { var last = 0, current = 1 return anyGenerator { let next = last + current last = current current = next return next } } }
26. struct PrimeSequence: SequenceType { func generate() -> AnyGenerator<Int> { var currentPrime = 1, nextPrime = 1 return anyGenerator { nextPrime = currentPrime+1 while !nextPrime.isPrime() { nextPrime += 1 } currentPrime = nextPrime return nextPrime } } }
27. WHAT ABOUT? // // There are infinite prime numbers. Math is tricky like that. // for p in PrimeSequence() { print(p) }
28. struct LimitSequence<S: SequenceType, T where T == S.Generator.Element>: SequenceType { let test: (Int,T) -> Bool let sequence: S init(sequence:S, test: (Int,T) -> Bool) { self.sequence = sequence self.test = test } func generate() -> AnyGenerator<T> { var generator = self.sequence.generate() var counter:Int = 0 return anyGenerator { let next = generator.next() if next != nil && self.test(++counter, next!) { return next } return .None } } }
29. PROBLEM 2 // // By considering the terms in the Fibonacci sequence whose values do not // exceed four million, find the sum of the even-valued terms. // let seq = LimitSequence(sequence: FibonacciSequence()) { $1 < 4_000_000 } let sum = seq.filter(isEven).reduce(0,combine: +)
30. PROBLEM 7 // // What is the 10,001st prime number? // // If I use $0 here, compiler complains. So, explicitly using "(i,_) -> Bool" let primes = LimitSequence(sequence:PrimeSequence()) { (i, _) -> Bool in i < 10_001 } let lastPrime = Array(primes).last
32. WWDC 2015 - PROTOCOL-ORIENTED PROGRAMMING IN SWIFT
33. extension SequenceType { typealias ValueTest = (Self.Generator.Element) -> Bool func take(i:Int) -> LimitSequence<Self, Self.Generator.Element> { return LimitSequence(sequence: self) { (counter,_) -> Bool in i < counter } } func takeWhile(test:ValueTest) -> LimitSequence<Self, Self.Generator.Element> { return LimitSequence(sequence: self) { test($1) } } func last() -> Self.Generator.Element { return Array(self).last! } }
34. PROBLEM 2 (CRUSTIFIED) // // By considering the terms in the Fibonacci sequence whose values do not // exceed four million, find the sum of the even-valued terms. // let sum = FibonacciSequence().takeWhile({ $0 < 4_000_000 }).filter(isEven).reduce(0,combine: +)
35. PROBLEM 7 (CRUSTIFIED) // // What is the 10,001st prime number? // let lastPrime = PrimeSequence().take(10_001).last()
36. BIGNUM
37. PROBLEM 20 // // n! means n × (n − 1) × ... × 3 × 2 × 1 // // For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800, // and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27. // // Find the sum of the digits in the number 100! //
38. // WILL NOT WORK let total:Int = 9332621544394415268169923885626670049071596826438162146859 2963895217599993229915608941463976156518286253697920827223 758251185210916864000000000000000000000000
39. ATTEMPT 1: STRINGNUM // // multiplyString does what we learned in gradeschool // let total = (2...100).reduce("1") { multiplyString($0, times: $1) } print("sum = \(sumOfDigits(total))")
40. PROBLEM 25 WHAT IS THE INDEX OF THE FIRST TERM IN THE FIBONACCI SEQUENCE TO CONTAIN 1000 DIGITS?
41. struct StringFibonacciSequence: SequenceType { func generate() -> AnyGenerator<String> { var last = "0", current = "1" return anyGenerator { let next = addStringInteger(last, rhs: current) last = current current = next return next } } }
42. ATTEMPT 2: JKBIGNUM struct BigNumFibonacciSequence: SequenceType { func generate() -> AnyGenerator<JKBigInteger> { var last = JKBigInteger(string:"0"), current = JKBigInteger(string:"1") return anyGenerator { let next = last + current last = current current = next return next } } }
43. XCTEST PERFORMANCE TESTS
44. func testIsPalindromePerformance() { self.measureBlock() { for i in 0...10000 { isPalindrome(995000 + i) } } }
45. SWIFT FUNCTIONAL PROGRAMMERING MATH
46. Mostly SWIFT FUNCTIONAL PROGRAMMERING MATH
47. Mostly SWIFT Lots of FUNCTIONAL PROGRAMMERING MATH
48. Mostly SWIFT Lots of FUNCTIONAL PROGRAMMERING OMG MATH is hard
49. These are hard problems, but they are known to be solveable.
50. WHAT'S NEXT FOR ME? ▸ still not heavy production Swift ▸ prototype in Swift ▸ nonnull/nullable
51. WHAT'S NEXT FOR YOU? ▸ Try these out ▸ I took out the answers HTTPS://GITHUB.COM/DBGRANDI/EULERKIT
52. Questions?
53. I'm @dbgrandi Stay Crusty
54. Links Euler: http://projecteuler.net Uncle Bob Quote: https://pragprog.com/magazines/2013-01/functional-programming-basics EulerKit: https://github.com/dbgrandi/EulerKit Protocol Oriented Programming: https://developer.apple.com/videos/wwdc/2015/?id=408 JKBigInteger: https://github.com/kirsteins/JKBigInteger Images Not a dinosaur: http://www.kappit.com/img/pics/201408_2234_aechh_sm.jpg Ruby on Rails: https://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Ruby_on_Rails_logo.svg/2000px-Ruby_on_Rails_logo.svg.png Ruby: https://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Ruby_logo.svg/1024px-Ruby_logo.svg.png Milky Way Galaxy: http://www.nasa.gov/images/content/63376main_image_feature_202_jwfull.jpg Milky Way Chocolate: https://upload.wikimedia.org/wikipedia/en/5/5e/Small-milky-way-package.jpg Krusty the Clown: https://upload.wikimedia.org/wikipedia/en/5/5a/Krustytheclown.png Crusty: screenshot from WWDC Video (above)