Project Euler 43: Ruby

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

This is yet another problem where I blatantly avoided all real math. (Maybe that’s why it takes 37 seconds to execute…) I found this problem interesting, pun intended. Not much going on here, but I am starting to dig the shorthand that can be used for simple mapping and reduction. For example, interestings.map(&:to_i).reduce(&:+). I’m also trying to respect the one-line rule when deciding to whether to bookend my blocks with mere braces or do’s and end’s.

As always, any feedback is welcome.

# Euler 43
# http://projecteuler.net/index.php?section=problems&id=43
# The number, 1406357289, is a 0 to 9 pandigital number
# because it is made up of each of the digits 0 to 9 in
# some order, but it also has a rather interesting
# sub-string divisibility property.
#
# Let d1 be the 1st digit, d2 be the 2nd digit, and so on.
# In this way, we note the following:
#
# d2d3d4=406 is divisible by 2
# d3d4d5=063 is divisible by 3
# d4d5d6=635 is divisible by 5
# d5d6d7=357 is divisible by 7
# d6d7d8=572 is divisible by 11
# d7d8d9=728 is divisible by 13
# d8d9d10=289 is divisible by 17
#
# Find the sum of all 0 to 9 pandigital numbers with this property.
timer_start = Time.now

def interesting?(n,p)
  1.upto(7) { |i|
    return false if (n.to_s.slice(i...i+3).to_i % p[i] != 0)
  }
  true
end

#puts interesting?(1406357289, [0,2,3,5,7,11,13,17])

interestings = [0,1,2,3,4,5,6,7,8,9] \
  .permutation(10) \
  .map { |x| x.join } \
  .select { |x| interesting?(x, [0,2,3,5,7,11,13,17])}

#puts interestings
puts interestings.map(&:to_i).reduce(&:+)

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 42. 

I don’t have much to say about this problem except for the fact that it holds strong ties to Euler 12 and Euler 22 so it doesn’t take long to piece this solution together. Minor note — you’ll notice I used reduce in the word_value method. I figured after my little rant about inject vs reduce the other day I should actually make the move to my preferred syntax.

As always, any feedback is welcome.

# Euler 42
# http://projecteuler.net/index.php?section=problems&id=42
# The nth term of the sequence of triangle numbers is
# given by, tn = ½n(n+1); so the first ten triangle numbers
# are:
#
# 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
#
# By converting each letter in a word to a number
# corresponding to its alphabetical position and adding
# these values we form a word value. For example, the word
# value for SKY is 19 + 11 + 25 = 55 = t10. If the word
# value is a triangle number then we shall call the word a
# triangle word.
#
# Using words.txt (right click and 'Save Link/Target As...'),
# a 16K text file containing nearly two-thousand common
# English words, how many are triangle words?
timer_start = Time.now

def word_value(word)
  word.enum_for(:each_byte) \
    .map { |c| c - 64 } \
    .reduce(0, :+)
end

def triangle_numbers(n)
  i,current_triangle = 0,0
  triangles = []
  n.times do
    i += 1
    current_triangle += i
    triangles << current_triangle
  end
  triangles
end

# We could limit the array of triangles
# based on the max word value but simply
# grabbing the first 100 will do.
triangles = triangle_numbers(100)

text = File.open("words.txt", "r").gets
words = text.gsub!('"','').split(',').sort

puts words.each \
    .map { |word | word_value(word) } \
    .select { |value| triangles.include?(value) } \
    .count

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 41. 

I started off by iterating through all prime numbers up to the max value but it took way too long for the routine to complete. Instead I ended up gathering all possible pandigitals and I iterated through each descending. It takes a little while to collect the pandigitals, but the rest of the routine is fast. As for Ruby, I don’t think we’ve played with permutations since the early problems and I feel like I haven’t used selectfor quite some time. It’s good to see it back in a solution.

As always, any feedback is welcome.

# Euler 41
# http://projecteuler.net/index.php?section=problems&id=41
# We shall say that an n-digit number is pandigital if it
# makes use of all the digits 1 to n exactly once. For
# example, 2143 is a 4-digit pandigital and is also prime.
#
# What is the largest n-digit pandigital prime that exists?
timer_start = Time.now

require 'mathn'

# Get every pandigital, 1 - 987654321
def pandigitals()
  base, result = [], []

  # We build the list like so...
  #[1].permutation(1).map { |x| x.join.to_i } + \
  #[1,2].permutation(2).map { |x| x.join.to_i } + \
  #[1,2,3].permutation(3).map { |x| x.join.to_i } + \
  # ...
  1.upto(9).each do |n|
     base << n
     result += base.permutation(n).map { |x| x.join.to_i }
  end

  # Start with the max values
  result.sort.reverse
end

puts pandigitals.select { |n| n.prime? }.take(1)

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 40. 

There’s nothing all that exciting going on here. I’m sure you noticed in past solutions that one can easily map a string to a range of characters. Perhaps the fact that Ruby can build a range of string values for you. In the solution below, I build a range from “1″ to “1000000″. Pretty neat, if you ask me.

As always, any feedback is welcome.

# Euler 40
# http://projecteuler.net/index.php?section=problems&id=40
# An irrational decimal fraction is created by
# concatenating the positive integers:

# 0.123456789101112131415161718192021...
#
# It can be seen that the 12th digit of the fractional
# part is 1.
#
# If dn represents the nth digit of the fractional part,
# find the value of the following expression.
#
# d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000

timer_start = Time.now

# Build a long string of the numbers 1 - 1 million
# and convert to char array
nums = ("1".."1000000").to_a.join.chars.to_a

i, answer = 1, 1
while i <= 1000000
  # Get the product of all numbers which fall in a
  # power of 10 position
  answer *= nums[i-1].to_i
  i*=10
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 39. 

I broke my rule again and I worked through the problem a couple of different ways. In the first solution, I’m incrementing the number of occurrences using a hash and then I get the max count using (surprise) the max method. In the second solution, I simply add all P’s — especially duplicates — to an array and then perform a group by to get the P with the most occurrences. Each routine takes roughly the same amount of time to execute. In either case, I’d rate the performance as moderately slow.

As always, any feedback is welcome.

# Euler 39
# http://projecteuler.net/index.php?section=problems&id=39
# If p is the perimeter of a right angle triangle with
# integral length sides, {a,b,c}, there are exactly three
# solutions for p = 120.
#
# {20,48,52}, {24,45,51}, {30,40,50}
#
# For which value of p <= 1000, is the number of solutions
# maximised?
timer_start = Time.now

right_triangles = Hash.new(0)

1.upto(500) { |a|
  (a+1).upto(500) { |b|
    (b+1).upto(500) { |c|
      break if (a + b + c > 1000)
      if ((a**2 + b**2) == c**2)
        right_triangles[a + b + c] += 1
      end
    }
  }
}

# Return max based on key [1000, 1]
# puts right_triangles.max

# Returns max value (8) which is the max count
# puts right_triangles.values.max

# What we really want -- return the key with the max value
# http://stackoverflow.com/questions/2562256
puts right_triangles.max {|a,b| a[1] <=> b[1]}  #=> [840, 8]

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

timer_start = Time.now

right_triangles = []

1.upto(500) { |a|
  (a+1).upto(500) { |b|
    (b+1).upto(500) { |c|
      break if (a + b + c > 1000)
      if ((a**2 + b**2) == c**2)
        right_triangles << a + b + c
      end
    }
  }
}

# http://stackoverflow.com/questions/2562256
def most_common_value(a)
  a.group_by do |e|
    e
  end.values.max_by(&:size).first
end

puts most_common_value(right_triangles)

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

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

I made a deal with myself. I intend to complete the first fifty Euler problems by Wednesday, August 18. That sounds more like a challenge rather than a deal but that’s besides the point. I figure the only way I’m going to pull this off is if I cut some corners and not worry about little details like performance. I’ll still respect the one-minute run-time rule imposed by the folks over at the Euler site, but I’m not going to muck around with finding the smallest upper bound, try to minimize iterations of my loops or what have you. I’m just going to solve the problems and continue to learn Ruby along the way.

With that, you’ll find two solutions to Problem 38 below. As you’ll see I didn’t stick to my plan and I tried to optimize! The “optimized” code is more functional but it runs a heck of a lot slower! I could have continued down the refactoring path and really “functionalize” this solution and even optimize by reducing the number of iterations but I think I’ve spent enough time on the problem already.

For the record, it took me less than ten minutes to solve the problem the first way. Refactoring added an extra hour or so mostly because I got caught up in reading about inject versus reduce. I don’t like inject. It’s one of the Ruby key words which isn’t expressive in my opinion. That said, for some reason (likely the surfeit of examples), I thought the Ruby community encouraged the use of inject over reduce so I kept using it. I believe I misunderstood. Since reduce came into the language with Ruby 1.8.7, it seems that reduce is actually preferred. Maybe for no other reason than the fact that it better aligns Ruby with other languages likes Python and JavaScript as opposed to SmallTalk where I think injectoriginated. Now, there’s a lot of speculation going on here so please read with a grain of salt and please correct me if I’m wrong.

And, for the record, I feel the same way about the yield keyword as Ruby’s yield doesn’t do what yield does (continuation-y stuff) in other languages. Discuss.

As always, any feedback is welcome. Thanks for your time.

# Euler 38
# http://projecteuler.net/index.php?section=problems&id=38
# Take the number 192 and multiply it by each of 1, 2, and 3:
#
# 192 x 1 = 192
# 192 x 2 = 384
# 192 x 3 = 576
#
# By concatenating each product we get the 1 to 9 pandigital,
# 192384576. We will call 192384576 the concatenated product
# of 192 and (1,2,3)
#
# The same can be achieved by starting with 9 and multiplying
# by 1, 2, 3, 4, and 5, giving the pandigital, 918273645,
# which is the concatenated product of 9 and (1,2,3,4,5).
#
# What is the largest 1 to 9 pandigital 9-digit number that
# can be formed as the concatenated product of an integer
# with (1,2, ... , n) where n > 1?
timer_start = Time.now

answer = 0

(1..99999).each do |a|
  s = ""
  (1..9).each do |b|
    s += (a*b).to_s
    if s.length == 9 && s.split(//).sort.join == "123456789"
      answer = s.to_i if s.to_i > answer
    elsif s.length > 9
      break;
    end
  end
end

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

timer_start = Time.now
answer = 0

def longest_concatenated_product_up_to(a, l)
  (1..9).inject("") do |x, n|
     (x + (a * n).to_s).length <= l ? x + (a * n).to_s : x
  end
end

(1..99999).each do |a|
  s = longest_concatenated_product_up_to(a, 9)
  if s.length == 9 && s.split(//).sort.join == "123456789"
    answer = s.to_i if s.to_i > answer
  end
end

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

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

There’s nothing pretty going on here. I can’t sleep so let’s call this a late night hack. It’s not that bad, but… Chop! — which I personally wish was called Chomp! — is new. Everything else is pretty much “meh.”

As always, any feedback is welcome.

# Euler 37
# http://projecteuler.net/index.php?section=problems&id=37
# The number 3797 has an interesting property. Being prime
# itself, it is possible to continuously remove digits from
# left to right, and remain prime at each stage:
# 3797, 797, 97, and 7. Similarly we can work from right to
# left: 3797, 379, 37, and 3.
#
# Find the sum of the only eleven primes that are both
# truncatable from left to right and right to left.
#
# NOTE: 2, 3, 5, and 7 are not considered to be
# truncatable primes.
timer_start = Time.now

require 'mathn'

def truncatable_prime?(i)
  nums = i.to_s.chars.to_a

  nums.length.times do
    return false if (!nums.join().to_i.prime?)
    nums.shift
  end

  nums = i.to_s
  while nums.length > 0
    return false if (!nums.to_i.prime?)
    nums.chop!()
  end

  return true
end

count = 0
answer = 0

Prime.each { |x|
  next if x < 10
  break if count == 11
  if truncatable_prime?(x)
    count +=1
    answer += x
  end
}

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