I am trying solve the CodingNinjas challenge Cut Into Segments:
You are given an integer ‘N’ denoting the length of the rod. You need to determine the maximum number of segments you can make of this rod provided that each segment should be of the length ‘X’, ‘Y’, or ‘Z’.
This is my code:
def cutSegments(n, x, y, z):
if n == 0:
return 0 # No segments needed for a rod of length 0
if n < 0:
return float('-inf') # Or a very large negative number
a = cutSegments(n - x, x, y, z) + 1
b = cutSegments(n - y, x, y, z) + 1
c = cutSegments(n - z, x, y, z) + 1
ans = max(a, b, c)
if ans>0:
return ans
else:
return 0
print(cutSegments(8, 3, 3, 3))
The expected output for the given input is 0, as there is no way to cut 8 into segments of 3, but the output my code gives is 2. What is my mistake in this solution? Is there a way to make it work with recursion?
3
The problem is that when a deep recursive call returns -inf, you translate it to 0, and so the upper-level recursive calls will treat it as a success instead of a failure and add 1 to it.
The challenge is that 0 is a kind of success when n is 0, but when there is a constant failure (n < 0) you also need to eventually return 0.
To make this distinction, wrap your recursive function with another, simple function: only that wrapper function will translate -inf to 0:
def cutSegments(n, x, y, z):
def recur(n):
if n == 0:
return 0
if n < 0:
return float('-inf')
a = recur(n - x)
b = recur(n - y)
c = recur(n - z)
return max(a, b, c) + 1 # don't replace -inf with 0 here
res = recur(n)
return 0 if res < 0 else res # ...only here!
Now it will work. Still, it is not very efficient. You could solve that with memoization. A simple implementation is by using functools.cache:
from functools import cache
def cutSegments(n, x, y, z):
@cache
def recur(n):
if n == 0:
return 0
if n < 0:
return float('-inf')
a = recur(n - x)
b = recur(n - y)
c = recur(n - z)
return max(a, b, c) + 1
res = recur(n)
return 0 if res < 0 else res