Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursion question. Need help.  RSS feed

 
Manoj Prabahar Raju
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All

Please help me with this

The below recursive code is not working as I expect. Please find the code below



Output and Display lines:

Start--->0 target--->9
Start--->1 target--->1
Start--->3 target--->-3
Start--->4 target--->-4
Start--->4 target--->-3
Start--->1 target--->9---> why the control goes here instead of Start--->1 target--->1
Start--->3 target--->5
Start--->4 target--->4
Start--->4 target--->5
Answer is false

My doubt with above code is after two FALSE(Start--->4 target--->-3) why the control goes to (Start--->0 target--->9) instead of (Start--->1 target--->1).

I believe (Start--->1 target--->1) is never returned false.. Please help me with this. If it's not clear I can give more details. Thank you so much in advance.

 
Stephan van Hulst
Saloon Keeper
Posts: 7808
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursion is difficult enough to understand if we know what the purpose of the algorithm is. I have no idea what groupSum5() is supposed to do.

First explain what you expect groupSum5() to do, not how.
 
Manoj Prabahar Raju
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Stephan

Thank you so much for looking into this.

The question is from codingbat. Please find the problem below.

Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target, with this additional constraint: if there are numbers in the array that are adjacent and the identical value, they must either all be chosen, or none of them chosen. For example, with the array {1, 2, 2, 2, 5, 2}, either all three 2's in the middle must be chosen or not, all as a group. (one loop can be used to find the extent of the identical values).

I was approaching towards the solution. I expect a 'true' for it. In the middle when I got struckup, I tried to debug and I was wondering with my original question with what In started this thread. Thank you!
 
Stephan van Hulst
Saloon Keeper
Posts: 7808
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The additional constraint is trivial: Before searching for a group that sums to the target, you can replace adjacent identical numbers with their sum: {1,2,2,2,5,2} becomes {1,6,5,2}.

Then, the problem becomes equal to trying each of the numbers by subtracting it from the target, and recursively checking if you can make the new target using the remainder of the numbers.

This is probably easier if instead of arrays, you use lists.
 
Manoj Prabahar Raju
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Stephan

Yes sure I'll try as per your instructions and will let know if it worked.

Still can I get my question helped with a answer from anyone. I was trying to debug for last two days and I couldn't get why the control moved to line 1 instead of line 2 after line 3 returned false. The line numbers I mention here are from below print lines. The source code is given after print lines.




Code Snippet:



Please help me to get a answer for the above.Thank you!
 
Piet Souris
Rancher
Posts: 1980
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Manoj,

as you see, just printing start and target is not enough to tell
what's going on.

My advice is to add a parameter 'level' to your 'groupSum5' method,
and that you start the S.o.p line with level times the string "****",
so that you can see the level of nesting as well.
Or you could, just before going into the recursion (and there are
some places whare you do that), print the line number of that line,
so that you can also see from where you do a recursion.

Anyway: what I find suspicious, is that you see 'start' going from
1 to 3, while I would expect it to go from 1 to 2: there are only
two twos in your array.

My second advice would therefore be: follow Stephans advice and
transform your input array so that neighboring doubles are
summed and replaced by this sum. The whole error prone
'while' part can then be skipped.
 
Carey Brown
Bartender
Posts: 2995
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A tweak to your code to include levels (Piet beat me to it).
Also tests a number of targets that should return true.
Also changed the first if() inside your method.
Makes it better but still has some problem.
 
Manoj Prabahar Raju
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Than you all for all your valuable replies. I changed the line #23 return (groupSum5(start+1, nums, target-h)) to if(groupSum5(start+1, nums, target-h)) return true; and it worked.




Please find the final working code below.



Thank you all for all your valuable time.
 
Piet Souris
Rancher
Posts: 1980
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Manoj,

the code is not completely correct, unfortunately.

For the given array, the oucomes are correct. However,
try: int[] c = {8, 2, 2, 2, 1}
and check the outcome for target = 7 and 15.
Both should give 'true'.
 
Manoj Prabahar Raju
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for pointing out this. I have modified the code and it seem to work now. Thank you so much!

I added a check for adding identical numbers inside while loop with variable g.

 
Carey Brown
Bartender
Posts: 2995
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

I think you want to return true whenever target==0, even if you haven't reached the end.
 
Manoj Prabahar Raju
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes I want to return when Target==0. Thank you for looking into this.
 
Stephan van Hulst
Saloon Keeper
Posts: 7808
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't immediately return true when target == 0.

A list containing the numbers 1,2,3 can not sum to 0.
 
Stephan van Hulst
Saloon Keeper
Posts: 7808
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your code is quite unclear, because you're using local variables without descriptive names: h and g. It seems that g is the counter of the amount of identical adjacent values, while h is the sum of these values. In a week you will have forgotten what they mean, so you should use names like adjacentValueCount and adjacentValueSum instead. However, you don't need them at all if you get rid of identical neighbors first.

Another problem is that you have many points where you make recursive calls, and it's not immediately clear why this is. Strive to make only one recursive call per recursive method.

You can also get rid of the start parameter if you assume that *all* numbers in the list need to be tested. You can do this by making the recursive call using List.subList(), which returns a view of a part of the list.
 
Piet Souris
Rancher
Posts: 1980
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The problem was certainly not easy, and not many people
would be able to come up with a solution.

So, well done, Manoj!
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!