Wednesday, October 9, 2013

Eulers Continued: Problems 2 and 3

Continuing with the Project Euler problems, here's my solution for numbers 2 and 3.

Problem 2

Each new term in the Fibonacci sequence is generated by adding
the previous two terms.
By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose
values do not exceed four million, find the sum of the even-valued terms.

First, here are the tests that I wrote:

require 'problem2/problem2'

describe 'solution' do

it "sums the first two terms to generate the third term" do
expect(Problem2.fib(2)).to eq 1
end

it "sums the even-valued terms up to the limit" do
expect(Problem2.fib(4000000)).to eq 4613732
end
end

Similar to the tests written for the first problem, we want to check the answer and put the actual numbers in the test and then write the code so that it doesn't need a number, it just needs the argument to be noted and the argument in the code pulls the fixed number arguments from the test in order to run and pass. The Problem2 is the module and fib is the method.

So, onto the code:
module Problem2

def self.fib(limit)
arr = []
a,b = 0,1

while a < limit
arr << a
a, b = b, a + b
end

sum = arr.select { |i| i.even? }.reduce(:+)

end

fib(4000000) #sets the limit
end

To solve this problem, first, I decided to create an empty array, then I needed to put stuff in the array (that's the second line). The question gives a certain number as the limit (4000000) so while the number is under the limit, we want to push the new number onto the end of the array (arr << a). So that create the action of what will happen. Then we need to create the formula that will produce the number (the recursion formula). And that's that part of the problem. Next, once we have the Fibonacci sequence in the array, we need to solve the second part of the problem where we find the sum of the even-valued terms. In order to find the sum, we take the array and use the select method, passing the array through a block that looks for which numbers are even, selecting those numbers and then using the reduce :+ method to add those numbers together. Finally, fib(4000000) sets the limit of what we are looking for to put the result. One note about solving these problems. I've started outlining each step at the top of the problem to give myself a short roadmap to work from and then once I have the problem clarified in my mind and a roadmap worked out, I can work through each part until I find the solution and get working code.

Problem 3

I include both problems in this entry because my solution to problem 3 is a bit of a cheat. But before we go there, here's the problem:

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Here are the tests I wrote:

require 'problem3/problem3'

it 'will have the largest prime factor for 13195' do
expect(Problem3.prime(13195)).to eq 29
end

it 'will have a largest prime factor for 600851475143' do
expect(Problem3.prime(600851475143)).to eq 6857
end
end

And here's the code:

require 'prime'

module Problem3

def self.prime(num)
primes = Prime.prime_division(num)
primes.last
end
end

So, there's a Ruby library called Prime which makes doing anything with prime numbers really simple. First, I required that library. The I just defined primes and used prime_division which divides the number to determine which the prime numbers are. Finally, I took the last number in the list which would be the largest number. Really simple and straight forward.

1. Hey Allison,

Interesting testing strategy. Here is one thing to consider on Problem 2. You are pushing items to an Array, and therefore increasing the array size during each push. From the lower level perspective, what this means is that after so many pushes, you will be out of array memory (An array is initialized to a certain size, and once exceeded, a new array is initialized that is larger - often double the size - and then every item is copied over). When this happens (and I don't know the exact implementation of Ruby here), your code slows down a lot because you must iterate through the prior array. Then, once you have added each item to an array, you must then iterate through the whole array (which you have already done multiple times when copying the array to increase its size) and you run tests on each item of the array (is it even) and sum each together. This is not ideal when understood from this perspective.

What I would do is have the two fib values, as you really don't need to store all of the Fibonacci values, which are then passed into the fib method. I then would have a sum variable, which adds to that when the fib result is even. What this does is save you memory and is faster (because you are not reading and writing nearly as much to memory which is slower).

For future problems, here is a suggestion that might help you (if your goal is to write fast efficient code as opposed to just writing working ruby code). Look at data being stored. If you do not necessarily need to store it to answer the question (i.e. if you can sum numbers together without storing all of them in an array), don't do it. As the numbers get larger in project euler, storing unnecessary data will become more costly.

Hope this helps,

Stuart

2. Thanks Stuart!! Very helpful. I hadn't even thought about the issue of how much data is being stored in each of these solutions.