Apr 24, 2015 / Discussion
I found a nice little challenge on the CodingBat.com website called ‘make bricks’. The website only has support for Python and Java, so I originally did the challenge in Python and then ported it to Ruby. The ‘make bricks’ problem goes like this:
We want to make a row of bricks that is goal inches long. We have a number of small bricks (1 inch each) and big bricks (5 inches each). Return true if it is possible to make the goal by choosing from the given bricks. This is a little harder than it looks and can be done without any loops.
I thought about it for a while and came up with a solution to complete it without using loops as required. It wasn’t a bad effort but turned out that there was an even better way to do it.
Let’s start off with the RSpec tests for the challenge:
expect(subject.make_bricks?(3, 1, 8)).to be_truthy; expect(subject.make_bricks?(3, 2, 9)).to be_falsey; expect(subject.make_bricks?(0, 3, 10)).to be_truthy; expect(subject.make_bricks?(22, 2, 33)).to be_falsey; expect(subject.make_bricks?(20, 4, 39)).to be_truthy;
Here is my first solution that I came up with, without doing any research on it:
def make_bricks?(small, big, goal) diff = goal - big * 5 return false if diff > 0 && diff > small return false if diff < 0 && goal - ((goal / 5).to_i * 5) > small return true end
The tests pass using this solution and I didn’t think it was a bad effort. But I then read up on the suggested solution and it actually made a lot more sense than my solution (although they are not too different). The idea behind the suggested solution is that you really only have to do 2 simple checks:
- Do we have a enough total bricks
- If so, do we have enough small bricks
To check the small bricks, you only have to do a modulus calculation on the goal length and size of the big bricks to find out how many small bricks you need (i.e. the left over amount) and then check if you have that amount, this is of course provided the first test passes. Here is the suggested solution written in Ruby:
def make_bricks_final?(small, big, goal) return false if big * 5 + small < goal return false if goal % 5 > small return true end
This was a really fun challenge! Try it out yourself and see what you can come up with. I’ve commited both solutions to Github with the tests.