# [Community Puzzle] Rod cutting problem

https://www.codingame.com/training/medium/rod-cutting-problem

Send your feedback or ask for help here!

Created by @MisterFlos,validated by @JBM,@_CPC_Tamno and @Abysse.
If you have any issues, feel free to ping them.

The last test should be reworked imo. Some languages like javascript/python get a call stack error, but itâ€™s fine for others like C++/C#. That kind of asymmetry should be avoided when possible.

3 Likes

First of all, there is absolutely no need for a recursive implementation here.
That said, in Python, you can use `sys.setrecursionlimit()` to increase the stack.

1 Like

True, but I still stand by my point. Thereâ€™s no reason to penalize some languages by creating this kind of asymmetry, unless it canâ€™t be avoided for some reason.

1 Like

Again, this puzzle is solvable in these languages without any problem through a simple iterative implementation.

1 Like

Agree to @Djoums point. Existence of a different solution does not mean its ok to ignore errors of a typical approach.

â€śErrorsâ€ť? I am talking about a different implementation of the same approach. The recursive approach is only more natural/typical here because you have decided so!
Some languages (such as Python) have a very limited call stack and/or do not implement tail call optimization, should we consequently ban all puzzles that could possibly be solved using a too deep recursive approach from CG?
If you actually want to efficiently use a language, you have to be able to deal with its limitations.

1 Like

Lets agree to disagree. No one ever talked about banning puzzles. The discussion was about a test.

1 Like

With all due respect to the other opinion, I tend to agree with Niako here. A good medium puzzle should have test cases to prevent inefficient solutions to work. Nerfing the test case would just also allow a brute-force approach to be viable.
Rod cutting is the typical coursebook example for dynamic programming (at least I met it in the CLRS book). For this puzzle, the bottom-up approach is even simpler (7 lines of code for meâ€¦) than the top-down, recursive, memoized one.

Oh I agree with what you say, but creating a test like the last one for this puzzle simply removes options from some languages and not from others, for no good reason that I can see.

Sure you can say that the limitation comes from the language, but you could also say that itâ€™s the authorâ€™s responsibility to create their tests with those limitations in mind, particularly in this case since feedback about the stack was given several times during the contribution process. Yet that feedback was ignored, and no justification was provided.
Thatâ€™s why I donâ€™t like the last test, otherwise the puzzle is totally fine.

Edit : one last point. If the goal was to prevent people from using recursion, which would be fine, then its simple version should be blocked for all languages (=impossible without tail call optimization). The fact that itâ€™s only the case for a subset of people and for one test makes me think that this is unintended and sloppy.

1 Like

By your logic, if you want to post the following classical problem (which probably exists on CG):

Find the path that maximize the sum in a square grid filled with integers, going from top-left corner to bottom-right by only using Down and Left moves,

you must limit the problem to a 30 x 30 grid or such.

The problem is that with 30 x 30, you can do it recursively without memoization, while the point of this problem is to force you to memoize or use dynamic programming.
So of course youâ€™re going for a bigger grid like 100 x 100, and YES sys.setrecursionlimit will be mandatory for a recursive approach, but how is that a problem ?
Any Python course about recursion introduces sys.setrecursionlimit very early.

The constraints say length â‰¤ L, so why do the last two test cases have so many inputs that violate this?

0 < length â‰¤ L , Not respected

1 Like

I edited that, it is now bounded by 10**10.

That doesnâ€™t make sense. You canâ€™t cut it into pieces longer than the rod. The inputs should be edited instead.

Or just remove the constraint.

I noticed someone has sorted the lengths in their solution. Maybe mention the lengths are already given sorted, so they donâ€™t have to?

Why is sorting the lengths a bad thing?

How many features are built-in in Python and not in C? Shall we avoid puzzles that require those features?

BTW, this is becoming a nightmare in C, far beyond the 15 medium puzzles Iâ€™ve solved.
I obviously need to work in memoization (which is, incidentally, cited for exactly 4 of the 192 Medium puzzles).
Any tips as to how to go about that for this problem?