Splitting a “true” rectangle into squares, a simple C++ algorithm

In this first episode of “Codewars explained” I’m going to show you a simple algorithm that will understand how to split a given rectangle into squares.

If you didn’t know, Codewars is a huge place where coders meet altogether. Choose your favourite languages and train with some automatically proposed problems, called kata.

For each kata you solve, you level up and unlock some in-website goodies.

Ok, let’s get back to us.

This problem is taken from this kata and the one below is my personal solution that you can also find here on Codewars.

So, given h and b, the height and width of the rectangle, return a list containing the sides of the squares you can extract from.

I’ve written it in C++, but of course you can train it in almost every language you want, if supported from Codewars.

 

WHAT’S THE MEANING BEHIND IT?

The idea is really simple. ( Yeah, my drawing skills really suck )

At every iteration your rectangle will change its height and width since you are building squares in it.

To build a square you have firstly to understand which of the sides is the shortest, then you can build it having such a size.

Following the image above:

  1. h = 3, w = 5; h is less than w, so we build a square having a side of 3. The height is still the same, but the width not, the new w = 5 – 3 = 2
  2. h = 3, w = 2, w is less than h, so we build a square having a side of 2. The height changes, now h = 3 – 2 = 1, the width keeps unchanged.
  3. h = 1, w = 2, h is less than w, so we build a square having a side of 1. The height is still the same, but the width not, the new w = 2 – 1 = 1
  4. Done, the last square is automatically done.

If you missed: The functional paradigm in Java – What are lambda expressions?

If you find any bug in my code or you have better ideas, feel free to comment!

Hope you enjoyed, see you to the next kata!

Leave a Reply

Your email address will not be published.