Aug
14
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
I’m learning Ruby as well with Project Euler. It’s a great way to learn, I can’t recommend it enough! Anyway, this runs in 200 milliseconds :
a = [] high = 0 high_num = 0 1.upto 500 do |m| 1.upto 500 do |n| if m < n z = m**2 + n**2 if Math.sqrt(z) % 1 == 0 a << m + n + Math.sqrt(z).to_i end end end end a.uniq.each do |p| if a.count(p) > high high = a.count(p) high_num = p end end puts high puts high_num@Ty, Thanks for the contribution. I like what you did – particularly with count(). Big speed improvement indeed.