Projecteuler.net Problem 2 using collection pipeline Pattern

Question

I solve projecteuler.net Problem 2 deferent way

1. Generate number from 1 to range ex 100 and get the even number
2. Get Fibonacci numbers from list
3. Reduce array

I have one problem with a large set of numbers like 1000000 or 4000000. can I ask how can I optimize the code? I am trying to solve the problem as a collection pipeline

swift code

var evenArray = ((0..<100).filter({0ドル % 2 == 0}))
print(evenArray)
var evenFibArray = evenArray.filter {(isPerfectSquare(5 * 0ドル * 0ドル + 4) || isPerfectSquare(5 * 0ドル * 0ドル - 4))}
print(evenFibArray)
var result = evenFibArray.reduce(into: 0){0ドル += 1ドル}
print(result)
func isPerfectSquare(_ x:Int ) -> Bool {
 let i = Int(sqrt(Double(x)))
 return (i * i == x)
}

• Martin R: Is there really a problem with large numbers? Your code runs in less than 50 milliseconds for an upper bound of 4,000,000. Did you compile the code in "Release" mode so that it is optimized? – I am not saying that it cannot be improved and optimized further, but just want to be sure of your expectations.
• NinjaDeveloper: I use playground
• NinjaDeveloper: Should I use the lazy property to improve the computing ?
• Martin R: A Playground is suitable for interactive programming, but horribly slow. The code is not optimized, and values are displayed in the side bar for each computation step. If you care for performance, use a "real" Xcode Command Line Tool project.
• NinjaDeveloper: I did not realize how bad the playground

Answer 1

General remarks

• Your code is readable; it works and does use the collection pipeline pattern. This pattern makes your code easily maintainable and debuggable;
• Apart from the name chosen for the square root i, the naming was done correctly. After all, it's a small code snippet;
• You could have used fewer parentheses;
• You could have taken advantage of the trailing closure syntax after reduce;
• Your code would look a bit nicer if the use of spaces before or after special characters (e.g: {, ), :, + or -) was more consistent.

Lucky escape

Your isPerfectSquare function should only accept non-negative numbers (natural numbers):

func isPerfectSquare(_ n: Int) -> Bool {
 guard n >= 0 else {
 return false
 }
 let root = Int(sqrt(Double(n)))
 return root * root == n
}

You are lucky Swift uses short-circuit evaluation of juxtaposed conditions. In the expression of evenFibArray the first element that's passed to filter is 0. So in this instance, 0ドル is 0. If isPerfectSquare(5 * 0ドル * 0ドル - 4) were to be evaluated, then you'd have got a Fatal error since the square root of a negative number in swift is not a number (-nan).

Luckily, the former condition isPerfectSquare(5 * 0ドル * 0ドル + 4) with 0ドル = 0 is true, and so, there is no need to evaluate the latter.

Conciseness

We don't really need the collection pipeline pattern since the initial numbers won't be transformed until the reduce. With the above remarks taken into consideration, here is what your code would look like:

let result = (0..<100)
 .filter { 0ドル % 2 == 0 }
 .filter { isPerfectSquare(5 * 0ドル * 0ドル + 4) || isPerfectSquare(5 * 0ドル * 0ドル - 4) }
 .reduce(0, +)

You could make it more concise: avoiding the first filter by using a stride instead:

let result = stride(from: 0, to: 100, by: 2)
 .filter { isPerfectSquare(5 * 0ドル * 0ドル + 4) || isPerfectSquare(5 * 0ドル * 0ドル - 4) }
 .reduce(0, +)

Or, if you like to use one reduce only, your code will become:

let result = stride(from: 2, to: 100, by: 2)
 .reduce(into: 0) { total, element in
 if isFibonacci(element) { total += element }
 }
func isFibonacci(_ n: Int) -> Bool {
 let square = n * n
 return isPerfectSquare(5 * square + 4) || isPerfectSquare(5 * square - 4)
}
func isPerfectSquare(_ n: Int) -> Bool {
 guard n >= 0 else { return false }
 let root = Int(sqrt(Double(n)))
 return root * root == n
}

There are other ways to test whether an integer is a perfect square.

Performance

Like you said, in your original code, you could avoid creating intermediate arrays in the pipeline by using the lazy keyword. The worst part about the original code is that you have to check for every number if it's even, and then check if it's a Fibonacci number. And there not so many Fibonacci numbers up to 4,000,000.

You could notice that in the Fibonacci series, every third element, is even:

fib(0)	fib(1)	fib(2)	fib(3)	fib(4)	fib(5)	fib(6)	fib(7)	...
0	1	1	2	3	5	8	13	...

Now, all we have to do is sum every third element in the Fibonacci series as long as it is less than the given limit (in your case 4,000,000). We could get the Fibonacci numbers using recursion, or Dynamic Programming, or Matrix Exponentiation, or more simply using the formula:

$$Fib[n] = \frac{A - B}{\sqrt{5}}$$

with:

$$A = (\frac{1 + \sqrt{5}}{2})^{n}$$ $$B = (\frac{1 - \sqrt{5}}{2})^{n}$$

Here is code for the new approach:

let sqrt5 = sqrt(5)
var sum = 0
stride(from: 3, through: 4_000_000, by: 3)
 .drop { n in
 let fn = fib(n)
 if fn <= 4_000_000 {
 sum += fn
 return true
 }
 return false
 }
func fib(_ n: Int) -> Int {
 let numerator = pow((1 + sqrt5)/2, Double(n)) - pow((1.0 - sqrt5)/2.0, Double(n))
 return Int(numerator/sqrt5)
}
print(sum) //4613732

drop(while:) makes sure we stop once the Fibonacci number exceeds 4,000,000.

Let's calculate a better end for the stride:
Since B is negligible, we could approximate the upper limit to which we should be calculating Fibonacci numbers:

$$Fib[n_{max}] \simeq \frac{(\frac{1 + \sqrt{5}}{2})^{n_{max}}}{\sqrt{5}} \leqslant 4\cdot10^{6}$$ $$\Rightarrow (\frac{1 + \sqrt{5}}{2})^{n_{max}} \leqslant 4\cdot\sqrt{5}\cdot10^{6}$$ $$\Rightarrow n_{max}\cdot\ln(\frac{1 + \sqrt{5}}{2}) \leqslant \ln(4\cdot\sqrt{5}\cdot10^{6})$$ $$\Rightarrow n_{max} \leqslant \frac{\ln(4\cdot\sqrt{5}\cdot10^{6})}{\ln(\frac{1 + \sqrt{5}}{2})}$$ $$\Rightarrow n_{max} \leqslant 33.26$$ $$\Rightarrow n_{max} = 33$$

Lucky for us, 33 is a multiple of 3!

Finally, here is the solution to the problem using the collection pipeline pattern:

let sqrt5 = sqrt(5)
func fib(_ n: Int) -> Int {
 let numerator = pow((1 + sqrt5)/2, Double(n)) - pow((1.0 - sqrt5)/2.0, Double(n))
 return Int(numerator/sqrt5)
}
let result = stride(from: 3, through: 33, by: 3)
 .lazy
 .map(fib)
 .reduce(0, +)
print(result) //4613732

One more thing 🤔

There has to be a better way, and indeed, there is an elegant solution to this problem. Enjoy!