For practice with Ruby and Rspec, I’ve been working through some Project Euler problems. One of my favorites so far is #9, which asks us to find the one Pythagorean triplet for which
a + b + c == 1000. Here is the GitHub repo with my solution for you to look at while you read long, if you’re into that.
Disclaimer: I’m no math wiz. This exercise is more about using tests well and writing good Ruby code rather than discovering an efficient algorithm to figure out which numbers to check. It’s probably pretty inefficient to use nested loops from 2 to 1000 for this problem.
Having done 8 of these types of problems before, I’ve come to realize that you’re going to be writing two general types of methods: “checkers” and “doers” (I just made this distinction up).
For Euler #9 an example of a reasonable “checker” would be this:
def makes_triplet?(a,b) c = (a**2 + b**2)**0.5 c % 1 == 0 end
Obviously we’re going to need to know if a given triangle (defined by 2 of its sides), makes a Pythagorean triplet. This method calculates
c and then checks to make sure it’s a whole number using the modulus operator.
TTD Isn’t So Bad
Does this method work? Old Sam would have put in a
binding.pry and played around, but I wanted to be more methodical and test-driven. But I wanted to only use tests when it made sense (as per DHH’s recent blog posts on the subject). Here was, I think, a great place where a test would make my life easier.
So I wrote:
describe 'can recognize triplets' do it 'knows that 3 4 5 is a triplet' do expect(makes_triplet?(3,4)).to be(true) end it 'knows that 2 4 5 is not a triplet' do expect(makes_triplet?(2,4)).to be(false) end end
And both tests pass, so that’s cool.
Obviously the most important test is that we actually find the triplet. I kept that nice and simple:
describe "Find the triplet" do it 'can find the product of the three numbers that make up a pythagorean triplet and sum to 1000' do expect(find_the_triplet).to eq(31875000) end end
This Whole Object-Oriented Thing Is Pretty Handy
So, with my tests set up it was time to make them pass. Here is the first version of my solution:
def sum_one_thousand?(a,b,c) a + b + c == 1000 end def makes_triplet?(a,b) c = (a**2 + b**2)**0.5 c % 1 == 0 end def qualifies?(a, b) c = (a**2 + b**2)**0.5 makes_triplet?(a,b) && sum_one_thousand?(a, b, c) end def find_the_triplet a = 2 while (a < 1000) b = 2 while (b < 1000) if qualifies?(a,b) c = (a**2 + b**2)**0.5 return (a*b*c) end b = b + 1 end a = a + 1 end end
If we were to categorize these 4 methods into “checkers” and “doers”, I’d say the first 3 are checkers and
find_the_triplet is a doer.
This works fine, but as you can see I need to re-calculate
c, the third side of the triangle, three separate times. This is not DRY at all.
Passing one variable to different methods? Sounds like I needed was a triangle object. Here’s what I did for that:
class Triangle attr_reader :product def initialize(a,b) @a = a @b = b @c = (a**2 + b**2)**0.5 @product = @a * @b * @c end def sum_one_thousand? @a + @b + @c == 1000 end def makes_triplet? @c % 1 == 0 end def qualifies? makes_triplet? && sum_one_thousand? end end
That’s more like it. Now I can create instances of triangles, using just two of its sides, and use an instance variable to pass the value of
c around. Furthermore, I can define semantic methods like
qualifies? that clearly state the given qualifications required.
My “doer” method remains outside of the Triangle class. Let’s revisit it:
def find_the_triplet a = 2 while (a < 1000) b = 2 while (b < 1000) @this_triangle = Triangle.new(a,b) if @this_triangle.qualifies? return @this_triangle.product end b = b + 1 end a = a + 1 end end
Sweet. Look how semantic that is! “If this triangle qualifies, return this triangle’s product” indeed!
But there’s still plenty to be desired of this code. It’s my natural instinct, thanks to my C++ background, to use nested
while loops for these types of problems. How could we use something more Ruby-like?
upto instead of
def find_the_triplet 2.upto(1000) do |a| 2.upto(1000) do |b| @this_triangle = Triangle.new(a,b) if @this_triangle.qualifies? return @this_triangle.product end end end end
Better! We eliminated the
b initializing lines and the
+ 1 lines.
To make this even more Ruby-like we can’t have the method short-circuit out with the
return @this_triangle.product line.
The argument against this practice is that having
returns spread out within your methods makes it difficult to understand what they do, which I more or less buy in to at this point.
However this was an issue I ran into frequently when working on Euler problems.
One solution would be to assign
product = @this_triangle.product and then return
product at the end of the method, but this isn’t ideal because we’d have to go all the way through both nested loops even if we found what we were looking for early on.
I would naturally go to the
break keyword here, but since we’re in nested loops, we’d need two breaks.
def find_the_triplet 2.upto(1000) do |a| 2.upto(1000) do |b| @this_triangle = Triangle.new(a,b) break if @this_triangle.qualifies? end break if @this_triangle.qualifies? end @this_triangle.product end
We’re no longer short-circuiting with
return in the middle of the method, but the two
breaks are both inefficient and repetitive. Hm. Let’s Google.
Using Catch and Throw
Googling “ruby break nested loops” led me to this Stack Overflow question, which suggested Ruby’s catch and throw keywords. I’d never heard of
throw but the example was pretty close to exactly what I envisioning for a solution.
def find_the_triplet catch :found_it do 2.upto(1000) do |a| 2.upto(1000) do |b| @this_triangle = Triangle.new(a,b) throw :found_it if @this_triangle.qualifies? end end end @this_triangle.product end
We have a
catch up top and a
throw within the nested loops. When the
throw line is executed, Ruby breaks out of the
catch block. It’s pretty much just what we needed.
catch can also return a variable that is “thrown” to it, which I learned from this Ruby Monk post on the subject. So our code can be a little more efficient:
def find_the_triplet catch :found_it do 2.upto(1000) do |a| 2.upto(1000) do |b| @this_triangle = Triangle.new(a,b) throw :found_it, @this_triangle.product if @this_triangle.qualifies? end end end end
Our tests pass and we’re no longer short circuiting. I like this method enough that I pushed it up in a separate branch called throw_catch, but it’s still not quite right.
(For more on catch and throw there’s also this great post from Ruby Learning.)
Nested Detect Loops
throw solution isn’t much better semantically than short circuiting, as it’s a little tricky to tell what’s going to be returned. Plus, I have the feeling there must be a way to use Ruby’s higher lever iterators here.
In this case we’re going to use is detect (aliased as
find– the choice is basically semantic). The trick is we’ll need to nest them like so:
def find_the_triplet (2..1000).detect do |a| (2..1000).detect do |b| @this_triangle = Triangle.new(a,b) @this_triangle.qualifies? end end @this_triangle.product end
find) returns the first instance where the block inside of it is
So let’s start with the outer
detect. It starts with
a = 2 and then runs through its block again and again until its block evalutes to
true or it has reached the end of the range. Of course this outer
detect’s block is another
No triangles with an
a of 2 qualifies, so the inner
nil 998 times. Thus, in the first iteration of the outer loop, its block is never evaluated to
true. So it moves on to
a = 3 and so on.
Finally, when we get to
a = 200, then iterates through the inner
b = 375, the inner loop will return true, and thus the outer loop will evalute to true as well. At this point we will break out of the outer
@this_triangle set to the qualifying triangle. We then call
.product on it to return
a*b*c, as the problem requests.