More Ruby Way of Doing Project Euler #2

more ruby way of doing project euler #2

For a nice solution, why don't you create a Fibonacci number generator, like Prime or the Triangular example I gave here.

From this, you can use the nice Enumerable methods to handle the problem. You might want to wonder if there is any pattern to the even Fibonacci numbers too.

Edit your question to post your solution...

Note: there are more efficient ways than enumerating them, but they require more math, won't be as clear as this and would only shine if the 4 million was much higher.

As demas' has posted a solution, here's a cleaned up version:

class Fibo
  class << self
    include Enumerable

    def each
      return to_enum unless block_given?
      a = 0; b = 1
      loop do
        a, b = b, a + b
        yield a
      end
    end
  end
end

puts Fibo.take_while { |i| i < 4000000 }.
          select(&:even?).
          inject(:+)

More ruby-like solution to this problem?

Rather than solve the problem in one go, looking at the individual parts of the problem might help you understand ruby a bit better.

The first part is finding out what the triangle number would be. Since this uses sequence of natural numbers, you can represent this using a range in ruby. Here's an example:

(1..10).to_a => [1,2,3,4,5,6,7,8,9,10]

An array in ruby is considered an enumerable, and ruby provides lots of ways to enumerate over data. Using this notion you can iterate over this array using the each method and pass a block that sums the numbers.

sum = 0
(1..10).each do |x|
  sum += x
end

sum => 55

This can also be done using another enumerable method known as inject that will pass what is returned from the previous element to the current element. Using this, you can get the sum in one line. In this example I use 1.upto(10), which will functionally work the same as (1..10).

1.upto(10).inject(0) {|sum, x| sum + x} => 55

Stepping through this, the first time this is called, sum = 0, x = 1, so (sum + x) = 1. Then it passes this to the next element and so sum = 1, x = 2, (sum + x) = 3. Next sum = 3, x = 3, (sum + x) = 6. sum = 6, x = 4, (sum + x) = 10. Etc etc.

That's just the first step of this problem. If you want to learn the language in this way, you should approach each part of the problem and learn what is appropriate to learn for that part, rather than tackling the entire problem.

REFACTORED SOLUTION (though not efficient at all)

def factors(n)
  (1..n).select{|x| n % x == 0}
end

def triangle(n)
  (n * (n + 1)) / 2
end

n = 2

until factors(triangle(n)).size >= 500
  puts n
  n += 1
end

puts triangle(n) 

I solved Project Euler #15 the wrong way. Why did this work?

The number of repeated combinations of length r of n things is equal to (n + r - 1; r). See this website (the section titled "Combinations with Repetition") for why.

In your code, r is the same as n, so you can write this as (2n - 1; n), which is what a.repeated_combination(a.length).to_a.length returns. Multiplying this value by 2 gives (2n; n) in this particular case (because (2x - 1; x) * 2 is equal to (2x; x) for all integers x), which is the correct answer.

Ruby: #8 on Project Euler, solution doesn't seem to work, but I feel so close

I think you should try to use the String methods in Ruby a bit more. Please take a look at this page here.

You would reach the same results with the much simpler code here:

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

## This will remove all \n
seq = sequence.tr("\n","")

def multiply_arr(a)
  prod = 1
  a.each do |f|
    prod = prod * f.to_i    
  end
  prod
end

def max_product(s,n)
  max = -1
  lim = s.length - n
  (0..lim).each do |pos|
    ns = s.slice(pos,n)
    arr = ns.each_char.to_a
    prod = multiply_arr(arr)
    max = (prod > max) ? prod : max 
  end
  max
end

puts max_product(seq,4)
puts max_product(seq,13)

I ran it here and got the following output

5832
23514624000

As you may see, the first product is the same you got. Haven't verified the second, but this is easy for you to do.

By the way, this kind of code is much more general, indeed. Now you may write things like

puts max_product(seq,5)

and receive

40824

as an answer. Then you solved a much more general problem than 'calculate it for 4' and then 'calculate it for 13'.

By the way! If you want to know what sequence generate this max, you may easily rewrite your code to

def max_product(s,n)
  max = -1
  maxarr = []
  lim = s.length - n
  (0..lim).each do |pos|
    ns = s.slice(pos,n)
    arr = ns.each_char.to_a
    prod = multiply_arr(arr)
    if (prod > max) 
      max = prod
      maxarr = arr
    end
  end
  { "array" => maxarr, "prod" => max }
end

then you would get this

{"array"=>["9", "9", "8", "9"], "prod"=>5832}
{"array"=>["5", "5", "7", "6", "6", "8", "9", "6", "6", "4", "8", "9", "5"], "prod"=>23514624000}

Hope it helps!

Ruby - Project Euler # 18 - Maximum Path Sum

This is how I would do it.

Code

def longest_path(arr)
  return nil if arr.empty?

  h = { len: arr.first.first, path: [] }
  return h if arr.size == 1

  arr[1..-1].reduce([h]) do |l,row|
    h = l.first
    left = { len: h[:len]+row.first, path: h[:path]+[:l] }
    mid = l.each_cons(2).to_a.zip(row[1..-2]).map do |(h1,h2),v|
            if h1[:len] >= h2[:len]
              { len: h1[:len]+v, path: h1[:path]+[:r] }
            else
              { len: h2[:len]+v, path: h2[:path]+[:l] }
            end
          end
    h = l.last
    right = { len: h[:len]+row.last, path: h[:path]+[:r] }
    [left, *mid, right]
  end.max_by { |h| h[:len] }
end

Example

a = [   [3],
       [7,4],
      [2,4,6],
     [8,5,9,3]]

longest_path a
  #=> {:len=>23, :path=>[:l, :r, :r]}

Thus, the longest path has length 23. From 3 in the first row, down and left (:l) to 7 in the second row, down and right (:r) to 4 in the third row and down and right to 9 in the last row: 3+7+4+9 => 23.

Explanation

This question is as much about the implementation of an algorithm as the choice of algorithm. It seems to me that the latter is fairly obvious: solve for one row, use that to solve for two rows, and so on.

Consider the example array a above.

arr = a
arr.empty? #=> false, so continue

h = { len: arr.first.first, path: [] }
  #=> {:len=>3, :path=>[]}
return h if arr.size == 1 # arr.size => 4, so continue

As

arr[1..-1] => [[7, 4], [2, 4, 6], [8, 5, 9, 3]]

reduce passes [h] and [7, 4] into the block and assigns the block variables:

l   = [{ len: arr.first.first, path: [] }]
row = [7, 4]

It then computes:

h     = l.first
  #=> {:len=>3, :path=>[]}
left  = { len: h[:len]+row.first, path: h[:path]+[:l] }
  #=> {:len=>10, :path=>[:l]}
mid   = []
h     = l.last
  #=> {:len=>3, :path=>[]}
right = { len: h[:len]+row.last, path: h[:path]+[:r] }
  #=> {:len=>7, :path=>[:r]}
[left, *mid, right]
  #=> [{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}]

mid => [] because each_cons(2) is executed on an array of size 1.

This last line above provides information for the longest paths to each of the two elements in the second row. For the first element (7), the path is of length 10 and goes from the only element in the first row (3) and then down and "left" (:l) to the given element.

As [left, *mid, right] is computed in the last row of the reduce block, the block variable l is given that value for the processing of the next row of arr:

l   = [{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}]
row = [2, 4, 6]

Next we compute the following:

left = { len: h[:len]+row.first, path: h[:path]+[:l] }
  #=> {:len=>5, :path=>[:l]}
l.each_cons(2).to_a.zip(row[1..-2]).map do |(h1,h2),v|
   if h1[:len] >= h2[:len]
     { len: h1[:len]+v, path: h1[:path]+[:r] }
   else
     { len: h2[:len]+v, path: h2[:path]+[:l] }
   end
end
  #=> [{:len=>14, :path=>[:l, :r]}]
h = l.last
  #=> {:len=>7, :path=>[:r]}
right = { len: h[:len]+row.last, path: h[:path]+[:r] }
  #=> {:len=>13, :path=>[:r, :r]}
[left, *mid, right]
  #=> [{:len=>5, :path=>[:l]}, {:len=>14, :path=>[:l, :r]},
  #    {:len=>13, :path=>[:r, :r]}]

The calculations of left and right are similar to those done for the previous element of arr. Let's look at the calculation of mid:

pairs = l.each_cons(2).to_a
  #=>   [[{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}]]
vals  = pairs.zip(row[1..-2])
  #=>   pairs.zip([4])
  #=>   [[[{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}], 4]]

vals is an array containing one element. That element is passed into the map, decomposed and assigned to the block variables:

h1       = {:len=>10, :path=>[:l]}
h2       = {:len=> 7, :path=>[:r]}
v        = 4
h1[:len] #=> 10
h2[:len] #=> 7

As 10 > 7, we execute:

{ len: h1[:len]+v, path: h1[:path]+[:r] }

which is the value of mid. The block value l for reduce is now assigned the result of [left, *mid, right]:

l = [{:len=> 5, :path=>[:l]}, {:len=>14, :path=>[:l, :r]},
     {:len=>13, :path=>[:r, :r]}]

and processing of the third row commences. reduce returns:

d = [{:len=>20, :path=>[:l, :l, :l]}, {:len=>19, :path=>[:l, :r, :l]},
     {:len=>23, :path=>[:l, :r, :r]}, {:len=>16, :path=>[:r, :r, :r]}]

which provides information describing the longest path to each element of the last row. The last step is:

d.max_by { |h| h[:len] }
  #=> {:len=>23, :path=>[:l, :r, :r]}

Ruby project Euler #12 efficiency

Look at this answer:
All factors of a given number

Then you just count the number of elements in the array until you find one with more than 500 divisors.

Project Euler #17 Ruby - What's wrong?

I don't really know Ruby, but I do know this Euler question. After studying your code that you have, I would have to guess that your else statement is incorrect.

Say you have the number 111, which I think falls into your else statement. You wind up building a string that says, "onehundredandtenone" instead of "onehundredandeleven"

So it would look to me that the range from 111 - 119 would have incorrect strings built which will throw off your counts. Actually, this would be true for 211 - 219... 311 - 319... etc...

---

Related Topics