Project Euler Al Dente

I like to code in the bath. However, I often find myself getting wrapped up in a huge task, forgetting I'm in the tub, and ending up rather cold and feeling like some kind of large overdone pasta. I needed to find fun and finite little projects to occupy my time dans la baignoire, and then I remembered Project Euler.

Working on these problems is not only a fantastic mental boot camp, but has evolved my style and approach to programming. Here are some tips, Ruby and otherwise, that will help you navigate the slippery and slightly addictive slope that is Project Euler.

1. Refactor your factors

Often you will have to determine how many factors a particular number has, or work with the factors themselves. Keep in mind you only have to look up to the square root of a number to find its factors. This will make your code much faster when working with larger numbers. 

# Slower
def factors(n)
  (1..n).select { |d| n % d == 0 }
end

# Faster
def factors(n)
  (1..Math.sqrt(n)).select { |d| n % d == 0 }.inject([]) do |factors, d| 
    factors << n / d if d != n / d
    factors << d
  end
end

Remember that ranges aren't arrays themselves but you can .each, .map, etc them. If you need an array immediately, they respond to .to_a.

2. Write a solid prime number method

def prime?(n)
  (2..Math.sqrt(n)).each { |d| return false if n % d == 0 }
  true
end

Project Euler loves primes. My method takes a number, and iterates over a range of two through the square root of that number. If the number is evenly divisible by any of the numbers in the range, the method returns false. It returns true if the number is only divisible by itself and one.

3. Inject

Get real comfy with .inject. Problem 1, for example, asks you to find the sum of all the multiples of 3 or 5 below 1000.

# Without inject
def sum_multiples(limit)
  sum = 0
  multiples = (3...limit).select { |n| n % 3 == 0 || n % 5 == 0 }
  multiples.each { |n| sum += n }
  sum
end

# With inject
def sum_multiples(limit)
  (3...limit).select { |n| n % 3 == 0 || n % 5 == 0 }.inject {|sum, i|  sum + i }
end

# With inject and a proc
def sum_multiples(limit)
  (3...limit).select { |n| n % 3 == 0 || n % 5 == 0 }.inject(:+)
end

In Problem 6, I used .inject with blocks to sum and square a set of numbers.

def sum_square_difference(limit)
  sum_of_squares = (1..limit).inject { |sum, n| sum + n**2 }
  square_of_sum  = (1..limit).inject { |sum, n| sum + n }**2
  square_of_sum - sum_of_squares
end

4. Loop Infinitely

Using loop do or while true is a simple way to create an infinite loop that you can break later in the code. Problem 5 asks for the smallest positive number that is evenly divisible by all of the numbers from 1 to 20. I break the loop by explicitly returning n.

def evenly_divisible?(n)
  (1..20).each { |i| return false if n % i != 0 }
end

def smallest_multiple
  n = 2520
  loop do
    if evenly_divisible?(n)
      return n
    else
      n += 20
    end  
  end  
end

5. Cheat

Ruby has methods and libraries that can greatly help you solve these problems quicker. Sometimes they're so good it feels like magic. If you use them, definitely still challenge yourself to achieve the same results without them. Here are a few that are pure sorcery.

Problem 24 asks for the millionth lexicographic permutation of the digits 0-9. .permutation allows you to solve this in one line.

def permutate(numbers, nth_permutation)
  numbers.permutation(10).to_a[nth_permutation-1]
end

permutate([0,1,2,3,4,5,6,7,8,9], 1000000)

Project Euler likes to throw large sequences of numbers at you, so practice forcing them into exactly whatever format you need. Problem 11 is, to put it nicely, kind of a bitch. Maybe I'm biased because I forgot you have to use double quotes when splitting at a newline character, but I digress. I used a heredoc to make a the grid into a string, then:

grid.split("\n").map { |row| row.split(' ').map { |n| n.to_i } }

Methods like .transpose and .zip are useful to apply to your formatted result, especially when you're going for a column/row kind of thing.

Next up is the mathn library, which changes the way Ruby does math. Below are two problems solved with and without it.

Problem 7 using Prime.

require 'mathn'

def nth_prime(n)
  Prime.take(n).last
end

# vs

def prime?(number)
  (2..(Math.sqrt(number))).each { |d| return false if number % d == 0 }
end
 
def nth_prime(n)
  number = 3
  i = 1
  loop do
    i += 1 if prime?(number)
    return number if i == n
    number += 2
  end
end

Problem 3 using .prime_division to get the prime factors of 600851475143.

require 'mathn'

def largest_prime_factor(n)
  n.prime_division[-1][0]
end

# vs

def largest_prime_factor(n)
  factors = []
  divisor = 2
  until n == 1
    if n % divisor == 0
      factors << divisor
      n /= divisor
    end
    divisor += 1
  end
  factors[-1]
end

6. Sound smart

It's pronounced "oyler", don't let anyone tell you otherwise.

Tags