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?