I have checked with my 3 implementations, and they all say there should be 11 squares.

So, it's 11. :)

Well, in general const simply means "read only". Many information can be found about it on the web, some of them furiously recommending against using const at all while others recommend to maximize its use. Here is a short article that I liked: https://nullprogram.com/blog/2016/07/25/. Personally, I think const is a very good thing to have around, so I use it wherever I can (and so do the C and C++ standard libraries).

Whenever something is not supposed to change, it is good practice to declare it const. A function that takes a pointer to const (such as const char *) promises that it will only read the data the pointer points to, so const becomes a compiler-verifiable part of the interface documentation. You can also apply const to a pointer, as in char *const. This means the pointer itself is never changed, but the data it points to can still be written to. Thus, const char *const means you have a pointer that is never changed, and it points to data that is never changed.

Using const in data definitions can allow the compiler to apply optimizations. There is an impressive use of const at 28:00 in this excellent talk about using C++ for programming a Commodore 64: https://www.youtube.com/watch?v=zBkNBP00wJEF. Data definitions are also the place where declarations of const pointers make most sense (as opposed to pointers to const data, which make sense almost everywhere).

Finally, I'd like to note that getting const right is especially important in C++. One reason is that in C++ it is possible to provide overloaded const and non-const versions of a function, and these may do completely different things.

I see. I've fed the picture into my own solution (which is also used in the random checks as reference) as well as into another C++ solution sent by another user. Both return 11. That is, the expected answer should definitely be 11 for your input, not 3.

What's a bit odd about your input are the first few lines:

+----+
|    |
++---+
 |   |
 |   |
++-+ |      // first and last + don't match any rectangle
 |+-++++    // this line and the two below seem to be messed up
 |  |+-+
 +--+

The generator shouldn't be able to generate broken shapes like this. It generates coordinates for random rectangles and squares within given constraints, and stores these coordinates in a vector. In a second step, the shapes are drawn into an array of strings, preallocated so that writing beyond any boundaries is impossible. In the last step, any trailing spaces are removed from all strings, leading and trailing empty lines are discarded from the final picture.

Are you sure that your dump is accurate? Do we see multiple overlapping pictures here? Any chance there could be any "junk" left between invocations of your function?

Here:

+----+ +++    => Square 1x1 [starting from 3rd]
     +-++|
       +-+

There are two squares here, not only one: a 2x2 and a 3x3. They both share the upper left corner. The 3x3 square is this one:

+++
+ |
+-+

(center + removed).

As already suggested by FArekkusu, exit code 139 should correspond to signal 11 (SIGSEGV).

You can try sprinkling std::cout over your code to help you tracking down the line where your program crashes (assuming it is your program that is crashing the tests). Your program may access memory beyond the end of some line.

Thank you for reporting, I have fixed the tests (see my other reply for some details). Please try again, it should work now.

Thank you for reporting this. The tests picked up two functions defined only in my own solution, but not in the tests themselves. Running the tests against my own solution worked, so that's why the problem wasn't detected by the built-in validation. I'll know better next time. :)

It should work now, please try again.

I have added your example to the tests. Thank you for putting so much time into this! :)

I have also played around with random tests. So far, I have implemented a simple random generator which generates shapes of random size at random positions. Squares and rectanges are generated with equal probabilities, picture dimensions and min/max rectangle/square sizes can be given as parameters. There are 3 sets of random tests now, each generating 150 random pictures for a defined set of parameters passed to the generator. This gives us a total of 450 checks against random pictures.

To be reasonably sure that my own solution can serve as a reference implementation in the tests (there is no way to tell how many squares there are in the random instances other than counting them), I have generated a few 10000 of random pictures and threw them at my own implementation as well as at all the solutions submitted for this kata (4 for Python, 1 for C++). Each of them returned the same answers for any given picture, so this should be fine.

The random pictures can become pretty wild. I don't think other kinds of generators will be needed.

Thank you for your feedback! I think I could add random tests (see below). Out of curiosity: did you find any concrete corner cases that are not addressed by the existing tests?

For the random tests, I am thinking about two different kinds of picture generators: one which generates instances with only non-touching rectangles/squares, and another one which generates completely random instances. The restricted generator will be harder to implement, but the expected results will be trivial to check. The unrestricted generator will be easier to implement, but I will have to use and trust my own (or another) solution as reference to figure out the expected result.

A moment of sudden enlightening?

Hey, thanks! I'm glad you like it.

I'd like to repeat what others have said before me: Please rework the sorting instructions. It was quite frustrating to work out the details.

The function calls itself and returns the value it gets from the call to itself. It's called recursion. Parameter nth is used to limit the depth of recursion (nth - 1 is passed to the recursive call). The guard lines check for base cases for which the recursion is terminated. Once the function returns a value for one of its base cases, a series of returns follows that pass the final result up the call stack.