johncoder/euler-rb

My solutions to https://projecteuler.net/ problems in Ruby

Project Euler

These are my solutions to the Project Euler problems, and I’m using this as an opportunity to learn some Ruby. 100% sure I’m going to be brute forcing many of the solutions.

Introduction

You might have been expecting markdown, but instead you’ve found your way into an org document. This uses org-babel to turn this into a so-called literate programming exercise. Works best in Emacs.

To get set up, make sure your .emacs file loads languages for org-babel:

(org-babel-do-load-languages
  'org-babel-load-languages
  '((ruby . t)))

Then, you can also disable the default behavior to confirm execution of blocks (although, this isn’t strictly necessary as it does create some additional risk).

(setq org-confirm-babel-evaluate nil)

Once you have it set up, you can execute org-babel-tangle by pressing C-c C-v t, which will take all the source code and tangle it into individual files (under the src directory, as indicated by the :tangle directive).

To run any individual source block, press C-c C-c, which will generate a results block immediately after the current source block. This is the output generated by the code in the block.

Utilities

Prime Numbers

module PrimeNumbers
  def PrimeNumbers.is_prime(n)
    if n == 2
      return true
    end
    result = false
    limit = (n/2.0).ceil
    candidates = (2..limit).to_a
    until candidates.length == 0
      candidate = candidates.shift
      if n % candidate == 0
        result = false
        break
      else
        result = true
      end
    end
    result
  end
end

Problem 1

link

#!/usr/bin/env ruby
def problem_1(limit)
  numbers = (1..limit).to_a
  multiples = numbers.filter do |n|
    (n % 3 == 0 or n % 5 == 0) ? n : nil
  end
  multiples.sum
end
p problem_1 10
p problem_1 1000

Problem 2

link

#!/usr/bin/env ruby
def problem_2
  prev = 1
  curr = 2
  def even?(n)
    n % 2 == 0
  end
  total = 2
  while curr < 4000000
    pprev = prev
    prev = curr
    curr = pprev + prev
    if even? curr
      total += curr
    end
  end
  total
end
p problem_2

Problem 3

link

Note that this one uses a table of primes to improve performance.

#!/usr/bin/env ruby
require "./src/problem_3_table.rb"

def problem_3(value)
  remainder = value
  factors = []
  primes = PrimeTable::Primes.map(&:dup)
  until primes.length == 0
    prime = primes.shift
    if prime <= remainder and remainder % prime == 0
      remainder /= prime
      factors.push prime
    end
  end
  factors
end

p problem_3 600851475143

Prime Table

module PrimeTable
  Primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,7927,7933,7937,7949,7951,7963,7993,8009,8011]
end

Problem 4

link

#!/usr/bin/env ruby
def problem_4
  left = 999
  right = 999
  while left != 0 and right != 0
    result = (left * right).to_s
    first, rest = result.chars.each_slice(3).to_a
    if first == rest.reverse
      break
    else
      if left < right
        right = left
      else
        left -= 1
      end
    end
  end

  return left, right # , left * right
end

p problem_4

Problem 5

link

For this one I had an idea that the list of all factors in the range from 1..N has some built in redundancy (i.e. if 10 is a factor, then its factors, 2 and 5 and 1, are implicit). Therefore, a simple optimization is to eliminate the implied factors in the list.

#!/usr/bin/env ruby
def problem_5(low, high)
  all_factors = (low..high).to_a.reverse
  factors = []
  until all_factors.length == 0
    factor = all_factors.shift
    implied = all_factors.filter do |f|
      factor % f == 0
    end
    all_factors = all_factors - implied
    factors << factor
  end

  # NOTE(john): Arbitrary?
  attempts = 1000000000000
  result = 1
  until result > attempts
    all_common_factors = factors.all? do |factor|
      result % factor == 0
    end

    if not all_common_factors
      result += 1
    else
      break
    end
  end
  result
end

p problem_5 1, 10
p problem_5 1, 20

Problem 6

link

#!/usr/bin/env ruby
def problem_6
  first_n = 101
  sum = 0
  sum_sq = 0
  first_n.times.each do |n|
    sum += n
    sum_sq += n**2
  end
  (sum**2) - sum_sq
end
p problem_6

Problem 7

link

#!/usr/bin/env ruby
require "./src/util/prime.rb"

def problem_7
  value = 0
  count = 0
  until count == 10001
    value += 1
    if PrimeNumbers::is_prime value
      count += 1
    end
  end
  value
end

p problem_7

Problem 8

link

I noticed that you could eliminate entire chunks of consecutive_count around any 0 that appears in the string since the product for the entire range would equal 0. The upshot is that unnecessary arithmetic is avoided, including division by zero.

The variable factors could also be initialized to Array.new(consecutive_count), but it wouldn’t allow for the << operator to be used any longer.

#!/usr/bin/env ruby
def problem_8(input, consecutive_count)
  offset = 0
  max_product = 1
  max_product_offset = 0
  product = 1
  factors = []

  until offset >= input.length
    v = input[offset].to_i
    offset += 1
    if v == 0
      product = 1
      factors = []
    else
      if factors.count == consecutive_count
        divisor = factors.shift
        product /= divisor
      end
      product *= v
      factors << v
      if factors.count == consecutive_count and product > max_product
        max_product = product
        max_product_offset = offset - consecutive_count
      end
    end
  end

  return input[max_product_offset...(max_product_offset + consecutive_count)], max_product.to_s
end

thousand_digits = [
  "73167176531330624919225119674426574742355349194934",
  "96983520312774506326239578318016984801869478851843",
  "85861560789112949495459501737958331952853208805511",
  "12540698747158523863050715693290963295227443043557",
  "66896648950445244523161731856403098711121722383113",
  "62229893423380308135336276614282806444486645238749",
  "30358907296290491560440772390713810515859307960866",
  "70172427121883998797908792274921901699720888093776",
  "65727333001053367881220235421809751254540594752243",
  "52584907711670556013604839586446706324415722155397",
  "53697817977846174064955149290862569321978468622482",
  "83972241375657056057490261407972968652414535100474",
  "82166370484403199890008895243450658541227588666881",
  "16427171479924442928230863465674813919123162824586",
  "17866458359124566529476545682848912883142607690042",
  "24219022671055626321111109370544217506941658960408",
  "07198403850962455444362981230987879927244284909188",
  "84580156166097919133875499200524063689912560717606",
  "05886116467109405077541002256983155200055935729725",
  "71636269561882670428252483600823257530420752963450",
].join('')
p problem_8(thousand_digits, 4)
p problem_8(thousand_digits, 5)
p problem_8(thousand_digits, 13)

Problem 9

link

First, I took the equation a + b + c = 1000 and solved for c to get c = 1000 - a - b. Then, I took the Pythagorean Theorem and solved for c to get c = Math.sqrt(a**2 + b**2). Both equations are solving for c, which means they are equal: 1000 - a - b = Math.sqrt(a**2 + b**2), which can be simplified to 1000 = Math.sqrt(a**2 + b**2) + a + b.

My approach uses trial and error, using valid values for a and b such that a < b, and a reasonable value for c is possible. All reasonable values for b where b > a are tested before a larger value a is tested.

• Given that b < c, a reasonable value for c can be tested when 2 * b + a < 1000.
• Given that b < c, an unreasonable value for c exists when 2 * b + a > 1000.

For practical reasons, a limit is introduced to avoid unbounded execution.

#!/usr/bin/env ruby
def problem_9(final_value)
  limit = 100000
  attempts = 1
  a, b = 1, 2

  until final_value == Math.sqrt(a**2 + b**2) + a + b
    if 2 * b + a < final_value
      b += 1
    elsif 2 * b + a >= final_value
      a += 1
      b = a + 1
    end

    attempts += 1
    if a >= (final_value / 3) or attempts > limit
      raise "No such luck: a=#{a} b=#{b}, attempts=#{attempts}"
    end
  end

  c = final_value - a - b

  p "a=#{a} b=#{b} c=#{c}, attempts=#{attempts}"

  # NOTE(john): A little self doubt?
  if a**2 + b**2 != c**2
    raise "doesn't work"
  end

  return a * b * c
end

p problem_9(3 + 4 + 5)
p problem_9 1000
# p problem_9 1096  # fails after 99919 attempts

Problem 10

link

#!/usr/bin/env ruby
require "./src/util/prime.rb"

def problem_10
  current = 0
  primes = 0
  sample = 200
  sum = 0

  until current >= 2000000
    if PrimeNumbers::is_prime current
      sum += current
      primes += 1
    end
    if current % sample == 0
      p "#{current} (#{primes} primes, #{sum} sum)"
    end
    current += 1
  end

  sum
end

p problem_10