Because it's been a little while... Here's another Euler!

Project Eulers 7 and 8

Just a few more Euler’s left and I realized the other day how long it had been since I’d posted some answers! I’m also posting both 7 and 8 because really, problem 7 uses the prime library again, so the answer is really short and sweet.

So, first, here is the problem:
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

First, here are the tests:

require 'problem7/problem7'

describe 'Prime number positions' do 
  
  it "is the 6th prime number" do 
    expect(Problem7.prime_place(6)).to eq 13
  end

  it "is the 10001st prime number" do
    expect(Problem7.prime_place(10001)).to eq 104743
  end

end

The tests and the code are pretty simple. You’re just using the resources in the prime library and then use the library to list (take) the numbers up until a certain position (ie- the 10,001st position) and then put the last number which is the answer to the question. So, here’s the code:

require 'prime'

module Problem7

        def self.prime_place(position)
          prime_place = Prime.take(position).last
        end

  puts Prime.take(10001).last

end

And now for Euler 8. This problem was actually really tough for me for two reasons… first, it seemed different than most of the others I had done up until now and second, how the heck do you test this thing?!

Here’s the problem:

 Find the greatest product of five consecutive digits in the 1000-digit number.

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

So, first for the test. After asking around a bit, the best suggestion I got for testing was to break down the string and take 10 or 15 characters and figure out the largest product from that string and then do the same with the larger number.

Here are the tests:

require 'problem8/problem8'

describe 'largest products of consecutive numbers' do 
  it "is the largest product of 5 consective numbers" do 
    expect(Problem8.product(7316717653)).to eq 1764
  end

  it "is the largest product of 5 consecutive numbers" do 
    expect(Problem8.product(7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450)).to eq 40824
  end
end

And so, here’s the solution. First, I created an empty array. Then I wanted to use .each_cons which takes every set of consecutive numbers based on the number of characters you ask for (in this case, it would be 5 because I’m looking for the largest product of 5 consecutive numbers) but .each_cons wouldn’t work because you can’t call .each_cons on a string. So, first, I had to separate the string into individual characters by using each_char. Once the string was separated into each_char (each character) I used the map method to make each of the string characters into an array of integers. Then, I used each_cons(5) which separated the array of integers into arrays of every five characters. The I took the product of each of those integers and pushed it into an array. Finally, the max is called on that array which gives the largest number needed for the answer.

module Problem8
  
  def self.product
    arr = []

    "731671765313306249192251196744265747423553491949349698352"\
    "0312774506326239578318016984801869478851843858615607891129"\
    "4949545950173795833195285320880551112540698747158523863050"\
    "7156932909632952274430435576689664895044524452316173185640"\
    "3098711121722383113622298934233803081353362766142828064444"\
    "8664523874930358907296290491560440772390713810515859307960"\
    "8667017242712188399879790879227492190169972088809377665727"\
    "3330010533678812202354218097512545405947522435258490771167"\
    "0556013604839586446706324415722155397536978179778461740649"\
    "5514929086256932197846862248283972241375657056057490261407"\
    "9729686524145351004748216637048440319989000889524345065854"\
    "1227588666881164271714799244429282308634656748139191231628"\
    "2458617866458359124566529476545682848912883142607690042242"\
    "1902267105562632111110937054421750694165896040807198403850"\
    "9624554443629812309878799272442849091888458015616609791913"\
    "3875499200524063689912560717606058861164671094050775410022"\
    "5698315520005593572972571636269561882670428252483600823257"\
    "530420752963450".each_char.map(&:to_i).each_cons(5) { |a| p arr << a.reduce(:*) }     
    puts arr.max 
  end
end

Phew! Look forward to the last two Eulers, 9 and 10, which I’ll hopefully get to post soon.

6, I have 6 Eulers

Euler 6! This is getting a bit more difficult to post about the Euler problems because I've actually completed all 10 a few weeks ago now. When I go to post, I find that I'm trying to remember what I did, where I was at, and what my thought process was. So, a word of advice, if you're looking to blog about a bug or something you're working on, do it right after you finish figuring it out.

Now, onto the problem!

The sum of the squares of the first ten natural numbers is,
 12 + 22 + ... + 102 = 385

 The square of the sum of the first ten natural numbers is,
 (1 + 2 + ... + 10)2 = 552 = 3025

 Hence the difference between the sum of the squares of the first ten 
 natural numbers and the square of the sum is 3025 − 385 = 2640.

 Find the difference between the sum of the squares of the first one 
 hundred natural numbers and the square of the sum.

This one was a good one to roadmap out before I got started. Once I broke it down into a few pieces, it was also not super complicated to solve. So I know I had to find the sum of the squares. And then, the square of the sums. And finally, the difference between the two. Breaking it up into the three pieces also lent itself nicely to writing tests because I wrote tests for each of those three pieces and then a test set for the numbers up to 10 and a test set for the numbers up to 100. Here are the tests:

require 'problem6/problem6'

describe 'up to 10' do 
  it "finds the sum of the square of the first ten numbers" do     
    expect(Problem6.sum(1..10)).to eq 385
  end

  it "finds the square of the sum of the first ten numbers" do
    expect(Problem6.square(1..10)).to eq 3025
  end 

  it "finds the difference between the sum of the square and the square of the sums" do 
    expect(Problem6.difference(1..10)).to eq 2640
  end
end

describe 'up to 100' do 

  it "finds the sum of the square of the first one hundred numbers" do 
    expect(Problem6.sum(1..100)).to eq 338350 
  end

  it "finds the square of the sum of the first one hundred numbers" do 
    expect(Problem6.square(1..100)).to eq 25502500
  end 

  it "finds the difference between the sum of the square and the square of the sums" do 
    expect(Problem6.difference(1..100)).to eq 25164150 
  end 
end

And here's the code. You'll see each of the three pieces and how they work together. And you actually don't even need the three pieces. (Looking at it again now as I post, I'm seeing that the question only asks for the different so you don't even need to define the sum and the square separately.) For me, when I originally did this, it was easiest for me to define each to visualize it better but now I see that was unnecessary and the final piece is really the only thing I need.

module Problem6

def self.sum(number_set)
  sum = (number_set).map { |i| i*i }.reduce(:+)
    #put here the sum of squares of the numbers
  return sum
end

def self.square(number_set)
  square = (number_set).reduce(:+)**2
    # put the square of the sum of the numbers
  return square
end

def self.difference(number_set)
  difference = (number_set).reduce(:+)**2 - (number_set).map { |i| i*i }.reduce(:+)
  return difference
end

puts Problem6.difference(1..100)

end

If you wanted to keep each of the three parts, this is what the code would look like:

module Problem6

def self.sum(number_set)
  sum = (number_set).map { |i| i*i }.reduce(:+)
    #put here the sum of squares of the numbers
  return sum
end

def self.square(number_set)
  square = (number_set).reduce(:+)**2
    # put the square of the sum of the numbers
  return square
end

def self.difference(number_set)
  difference = square(number_set)-sum(number_set)
  return difference
end

puts Problem6.difference(1..100)

end

The primary difference is that, instead of taking the information for the difference and repeated all that code, you are taking the result of the sum method and the result of the square method to find the difference.

Halfway there. Euler 5.

Euler 5! Phew, so, this marked my halfway point through the 10 problems I decided to do in Project Euler.

So, here is the problem:

2520 is the smallest number that can be divided by each of the numbers 
 from 1 to 10 without any remainder.
 What is the smallest positive number that is evenly divisible by 
 all of the numbers from 1 to 20?

For this problem, I actually solved it in a really ugly, awful way and then went back to refactor . I can't remember exactly but I think the ugly way involved taking a range of numbers, multiplying all of them and then seeing which was the smallest that had a remainder of 0 for each of the numbers... whatever it was, it was super complicated. Anyway, so first, the tests:

require 'problem5/problem5'
describe 'lowest common multiple' do 
  it "find the smallest number that can be divided by 1 through 10 with no remainder" do 
    expect(Problem5.divided_by(1...10)).to eq 2520
  end

  it "finds the smallest number that can be divided by 1 through 20 with no remainder" do 
    expect(Problem5.divided_by(1...20)).to eq 232792560
  end
end

At this point, if you've been reading the Euler series of this blog, you'll notice a pattern to all of the tests. This may not be the most sophisticated way to execute the tests since rspec can do a lot of cool things, but using the same format worked for and was a way I became comfortable with seeing tests formats, running the tests, etc.

Now for the answer:

module Problem5

def self.divided_by(number_range)
  list = (number_range).inject(:lcm)
  return list
end

puts Problem5.divided_by(1..20)

end

so, once I started reading the ruby docs, I noticed there was a greatest common denominator and a least common multiple method with an integer. Looking into those, the least common multiple method was a perfect, simple way to solve this problem. The inject plus LCM method on an integer basically takes a list and finds the lowest common multiple of that range of numbers.

Euler 4! Onwards and upwards!

As I talk about doing these Project Euler problems, I increasingly realize how much they helped me crystalize certain concepts in the last few weeks. I knew they were helping me solidify some coding skills, but honestly, I wasn't sure if spending time on these was a waste of time and if I should have just continued to build things instead. One originally unseen benefit of having these problems done is being able to use them as a template to identify other things. For example, I solved my eulers by testing in rsepc and writing in ruby. The past few weeks, I've had more conversations about other testing languages including cucumber and minitest. I read about them first, but then I've searched for other people who have solved eulers and tested first using these different test suites. Because I'm familiar with the problem, I'm more easily able to identify with the example and look at how they wrote their tests.
Now, onto Problem 4.

A palindromic number reads the same both ways. The largest palindrome 
made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

First the tests:

require 'problem4/problem4'


describe "largest palindrome" do        

 it "finds the largest palindrome of 2 digit numbers" do
   expect(Problem4.answer(10...100)).to eq 9009
 end

 it "finds the largest palendrome of 3 digit numbers" do
   expect(Problem4.answer(100...1000)).to eq 906609
 end
end

Now for the solution code:

module Problem4

def self.answer(largest_palindrome_range)
  max = 0
  (largest_palindrome_range).each do |a|
    (a...largest_palindrome_range.end).each do |b|
       product = a*b
    max = [max, product].max if product.to_s == product.to_s.reverse
    end
  end
  return max
end

puts Problem4.answer(100...1000)
end

So, first, I thought about a palindrome. A palindrome is the reverse of itself. So, I took the range we were testing and took each number to get a and then did the same from a to the end of the range to get b. Then I multiplied all of the resulting 2 number possibilities. Finally, in order to find the maximum, you take the product, convert it to a string and then see if it equals the reverse of the string.

This one was really tough for me. I knew about how to find the max and I knew how to check if it was a palindrome and reversing the string, but the middle section of finding the products via the range given was pretty challenging for me to wrap my head around.

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'

describe 'answer' do 

  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[0]
  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.

Project Euler all DAY

This week I took a break from building things to go back to the basics a bit. I've been having trouble getting a good handle on the different parts of Ruby (ie- blocks, hashes, etc.) and also struggled at the code retreat last weekend when I had to write code for tests in order to make them pass. Recognizing this as we significant weakness, I decided to spend the week tackling Project Euler problems.

Project Euler problems are math problems that you then solve using code. First, I found that they help me take an issue and think about different approaches. Second, they are great for practicing test-driven development. Third, they create additional challenges. For example, you can solve the problem and then go back and refactor to make your code even better OR I've had a few amazing friends/mentors this week look at my solutions and give me additional constraints or challenges to make my code even cleaner and better or explore a different method to solve the problem. There isn't one solution to these problems and if you google "euler ruby" you'll find dozens of responses.

I'll walk through the setup and first problem.

For me, the setup was actually pretty confusing, although really simply once I received some direction. It may seem basic, but I couldn't find these instructions anywhere so I'm writing them to hopefully help others get set up.

I wanted one euler folder with each problem in it's folder. I originally put both the problem1.rb and problem1_spec.rb files in the same folder but then rspec wouldn't run! It turns out that rspec looks for a lib folder in order to run it. The simplest way around this was to create a lib folder and a spec folder in my euler folder. The lib folder contains all the problem files and the spec folder contains all the spec files. To run the tests, I typed into the command line: $rspec spec/problem1_spec.rb and to run the actual file I had to type $ruby lib/problem1/problem1.rb. Finally, in order to test my code, I have been running the answer through IRB. To get to IRB, you simply type irb into the terminal and then you can write each line of code to see if you get the correct answer. Finally, at the top of the spec, we need to require the problem so that the tests finds the code file.

Euler Problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

First, I'll start with the tests that I wrote. I use rspec:

require 'problem1/problem1'

describe 'solution' do

it "sums the multiples of 3 and 5 under 10" do
    expect(Problem1.multiples(10)).to eq 23
end

it "sums the multiples of 3 and 5 under 1000" do
    expect(Problem1.multiples(1000)).to eq 233168
end

end

This test format is pretty much what I have been using for all of the Euler problems and I have found it pretty useful. To start the test, you have to describe something and then describe it's characteristics. So, since we are given the answer, we are able to hard code (put in the actual numbers) the test. The test says that for the sum of the multiples of 3 and 5 under to, we should expect that problem1(module)'s multiples(method) of 10(parameters/argument) to equal 23 (because that's what the problem tells us. I did a similar format for the next test and plugged in the final number 233168 once I got the code working.

Now for the code:

module Problem1

  def self.multiples(stop_counting)
    (1...stop_counting).find_all { |i| i%3 == 0 || i%5 == 0 }.reduce(:+)
  end

end

So, first we defined what the module was. Then, we were trying to find the multiples of two numbers (3 and 5) up to a certain number. I put self on the method definition because we are calling the method on the module. I put stop_counting as the argument which helps the tests pass, because in the tests we put at what number I stop counting (10 in the first example and 1000 in the second example). By defining the argument as stop_counting, we have more flexibility on the tests to plug the numbers into the tests and not the code (I think of this like an excel document where you have you assumptions worksheet. When you have an assumptions worksheet, you can change the number there as your assumptions change and since the rest of the spreadsheet is built on those assumptions, the numbers used in the formulas on other worksheets will automatically change as opposed to having to go through each worksheet and redo all the math manually). So, the code says to look at all the numbers from 1 until stop_counting and then find all the numbers (I think you can also use .select here) that have a remainder of 0 when using the modulus
(or modulo) which is the operation used to find the remainder of dividing one number by another, in this case either 3 or 5. Then the reduce method takes all the remaining numbers and using the :+ operator, adds those numbers together to get the sum.

Also, while going through this process, I paused in the middle to complete Ruby Monk. While initially I was like, "OMG, I CANNOT do another tutorial", Ruby Monk was really helpful and I wish it had been recommended to me two months ago. As opposed to the traditional ruby tutorial that builds a site of some sort, Ruby Monk really explains the terms and parts that make up Ruby and I feel much more confident in the definitions and grammar of it all now that I've completed it.

I'll be posting more problems in the next few days.