Language Club – Battle of the Dynamic Languages

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 50. 

And this is Euler Problem 50. I did it — I met my goal of completely the first 50 Euler Problems in Ruby by tomorrow, August 18. This was a fun problem which I did entirely on paper, in the living room, while the rest of the family watched TV. Oh how I wish that solution “just worked” but I neglected to move the counter to 1 and establish the new sum in the outer loop. Luckily, it didn’t take long to resolve, but, again, how I wish my solution to Problem 50 “just worked” the first time.

Is there any new Ruby goodness going on here? Nope, but I was reminded of my very first Ruby error which took a while to debug the first time around:

in `+’: nil can’t be coerced into Fixnum (TypeError)

If you notice below that (s+1) evaluates to an integer which allows the upto() loop to work its magic. Remove those parenthesis and you have a completely different expression — one which throws the above error. I don’t know. I figured I’d mention it, mostly because it offered me a nice reminder of how far I’ve come.

As always, any feedback is welcome.

# Euler 50
# http://projecteuler.net/index.php?section=problems&id=50
# The prime 41, can be written as the sum of six
# consecutive primes:
#
# 41 = 2 + 3 + 5 + 7 + 11 + 13
# This is the longest sum of consecutive primes that adds
# to a prime below one-hundred.
#
# The longest sum of consecutive primes below one-thousand
# that adds to a prime, contains 21 terms, and is equal to 953.
#
# Which prime, below one-million, can be written as the sum
# of the most consecutive primes?
timer_start = Time.now

require 'mathn'

top = 1_000_000

p = []
Prime.each do |a|
  break if a > top
  p << a
end

max_consecutive = 0
upper = p.length - 1
sum, ctr, answer = 0, 0, 0

0.upto(upper) do |s|
  sum, ctr = p[s], 1

  (s+1).upto(upper) do |e|
    sum += p[e]
    break if sum > top

    ctr += 1
    next if ctr < max_consecutive

    if sum.prime? && ctr > max_consecutive
      max_consecutive, answer = ctr, sum
    end
  end
end

puts max_consecutive
puts answer
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 49. 

Here, you will find that I took advantage of Ruby’s Prime Class and the Array.permutations method yet again. I think the solution is straight-forward and easy to read — unlike the problem description which I didn’t find very clear at all. After wrestling with the problem for a while I decided to see if 3330 was significant. Apparently, it was.

As always, any feedback is welcome.

# Euler 49
# http://projecteuler.net/index.php?section=problems&id=49
# The arithmetic sequence, 1487, 4817, 8147, in which each
# of the terms increases by 3330, is unusual in two ways:
# (i) each of the three terms are prime, and, (ii) each of
# the 4-digit numbers are permutations of one another.
#
# There are no arithmetic sequences made up of three 1-,
# 2-, or 3-digit primes, exhibiting this property, but
# there is one other 4-digit increasing sequence.
#
# What 12-digit number do you form by concatenating the
# three terms in this sequence?
timer_start = Time.now
require 'mathn'

answer = ""
Prime.each do |a|
  next if a == 1487

  b, c =  a + 3330, a + 6660
  next if !b.prime? || !c.prime?

  perms = a.to_s.chars.to_a.permutation(4).map{|p| p.join.to_i}
  next if !perms.include?(b) || !perms.include?(c)

  answer = a.to_s + b.to_s + c.to_s
  break
end

puts answer
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 48. 

I challenged myself to complete the first 50 Euler Problems in Ruby by tomorrow. Having such an easy problem show up this late in the game gave me great hope that I’d meet my goal. Coming up with this solution took no time at all and unfortunately I don’t think I learned anything about Ruby over the 5 or so lines of code.

As always, any feedback is welcome.

# Euler 48
# http://projecteuler.net/index.php?section=problems&id=48
# The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.
#
# Find the last ten digits of the series,
# 1^1 + 2^2 + 3^3 + ... + 1000^1000.
timer_start = Time.now

sum = (1..1000).reduce{ |agg, i| agg + i**i}.to_s
puts sum[sum.length - 10, 10]

puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 47. 

This solution shows off the power of built-in Ruby Array methods. You will notice Array.uniq returns a new array by removing duplicate values in self and Array.transpose, which I haven’t used prior to this solution, assumes that self is an array of arrays and transposes the rows and columns. I think the code below is a perfect example of how this method should/could be used.

As always, any feedback is welcome.

# Euler 47
# http://projecteuler.net/index.php?section=problems&id=47
# The first two consecutive numbers to have two distinct
# prime factors are:
#
# 14 = 2 x 7
# 15 = 3 x 5
#
# The first three consecutive numbers to have three
# distinct prime factors are:
#
# 644 = 2² x 7 x 23
# 645 = 3 x 5 x 43
# 646 = 2 x 17 x 19.
#
# Find the first four consecutive integers to have four
# distinct primes factors. What is the first of these numbers?
timer_start = Time.now

require 'mathn'

distinct_factors, consecutive_integers = 4, 4
counter, answer, i = 0, 0, 1

while counter < consecutive_integers
  primes, powers = i.prime_division.transpose

  if (primes != nil && primes.uniq.length >= distinct_factors)
    counter += 1
    answer = i if counter == 1
  else
    counter, answer = 0, 0
  end

  i += 1
end

puts answer
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 46. 

I could be wrong, but I don’t see any exciting and new Ruby stuff going on here. The prime class continues to come in handy and I’m extending the integer class, but that’s about it.

As always, any feedback is welcome.

# Euler 46
# http://projecteuler.net/index.php?section=problems&id=46
# It was proposed by Christian Goldbach that every odd
# composite number can be written as the sum of a prime
# and twice a square.
#
# 9 = 7 + 212
# 15 = 7 + 222
# 21 = 3 + 232
# 25 = 7 + 232
# 27 = 19 + 222
# 33 = 31 + 212

# It turns out that the conjecture was false.
#
# What is the smallest odd composite that cannot be written
# as the sum of a prime and twice a square?
timer_start = Time.now

require 'mathn'

class Integer
  def composite?
    return !self.prime? && self != 1
  end

  def goldbach?
    # Loop through primes and numbers until
    # we exceed the value of self
    Prime.each do |p|
       return false if p >= self

       t, i = 1, 1
       while (t <= self)
        # prime + twice a square
        t = p + (2 * (i * i))

        return true if t == self
        i += 1
       end
    end

    false
  end
end

answer, i = 0, 1
while answer == 0
  answer = i if i.composite? && !i.goldbach?
  i+=2 # step 2 for odds
end

puts answer
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 45. 

After the last problem, I figure to heck with trying to optimize. Below you’ll find another brute force solution which completes in less than a second. The trick was finding the intersection of the three arrays which is a snap in Ruby. I bet the math is cool, but I completely avoided it again. Good for me, I guess.

As always, any feedback is welcome.

# Euler 45
# http://projecteuler.net/index.php?section=problems&id=45
# Triangle, pentagonal, and hexagonal numbers are
# generated by the following formulae:
#
# Triangle	 	Tn=n(n+1)/2 	1, 3, 6, 10, 15, ...
# Pentagonal	Pn=n(3n-1)/2 	1, 5, 12, 22, 35, ...
# Hexagonal	Hn=n(2n-1)	 	1, 6, 15, 28, 45, ...
# It can be verified that T285 = P165 = H143 = 40755.
#
# Find the next triangle number that is also pentagonal
# and hexagonal

timer_start = Time.now

class Integer
  def triangle
    return self * (self + 1) / 2
  end

  def pentagonal
    return self * (3 * self - 1) / 2
  end

  def hexagonal
    return self * (2 * self - 1)
  end
end

#puts 285.triangle
#puts 165.pentagonal
#puts 143.hexagonal

t, p, h = [], [], []
1.upto(100000) { |i|
  t << i.triangle
  p << i.pentagonal
  h << i.hexagonal
}

puts (t & p & h).select { |x| x > 40755}[0]
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 44. 

So much for my brute-force-only-just-get-the-answer-in-less-than-one-minute approach. I worked through this problem four different ways — each time holding x number of pentagonal numbers in a various data structure for quick comparison. That was a bad move as each attempt took forever to complete. Instead I tried calculating each pentagonal on the fly and Wikipedia clued me into the pentagonal? check. Premature optimization. Still bad most of the time.

Other than the newly discovered math, there are a few bits I’d like to point out. There’s the natural number check found within the pentagonal? method and I guess there’s no concept of Integer::Max in Ruby so I stole someone else’s implementation. Should I be surprised that Integer::Max doesn’t exist?

As always, any feedback is welcome.

# Euler 44
# http://projecteuler.net/index.php?section=problems&id=44
# Pentagonal numbers are generated by the formula,
# Pn=n(3n1)/2. The first ten pentagonal numbers are:
#
# 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
#
# It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However,
# their difference, 70 - 22 = 48, is not pentagonal.
#
# Find the pair of pentagonal numbers, Pj and Pk, for which
# their sum and difference is pentagonal and D = |Pk - Pj|
# is minimised; what is the value of D?
timer_start = Time.now

class Integer
  def pentagonal
    return self*(3*self-1)/2
  end

  # http://en.wikipedia.org/wiki/Pentagonal_number
  # If n is a natural number, then x is the nth pentagonal
  # number. If result is not a natural number,
  # then self is not pentagonal.
  def pentagonal?
    return ((Math.sqrt(24*self + 1) + 1) / 6) % 1.0 == 0.0;
  end

  # http://drawohara.com/post/117643208/
  # ruby-integer-max-and-integer-min
  N_BYTES = [42].pack('i').size
  N_BITS = N_BYTES * 8
  MAX = 2 ** (N_BITS - 2) - 1
  MIN = -MAX - 1
end

# Another upper bound guess
upper_bound = 5000
answer = Integer::MAX

1.upto(upper_bound) do |j|
  (j+1).upto(upper_bound) do |k|
    pk, pj = k.pentagonal, j.pentagonal
    d = pk - pj

    break if d > answer
    next if !d.pentagonal?

    s = pj + pk
    if s.pentagonal? then
      answer = d
    end
  end
end

puts answer
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"