Win a copy of Pragmatic AI this week in the Artificial Intelligence forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Jeanne Boyarsky
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Junilu Lacar
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Ganesh Patekar
  • Tim Moores
  • Pete Letkeman
  • Stephan van Hulst
Bartenders:
  • Carey Brown
  • Tim Holloway
  • Joe Ess

Recursion question. Need help.  RSS feed

 
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.

 
Saloon Keeper
Posts: 9145
173
  • 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: 9145
173
  • 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!
 
Master Rancher
Posts: 2758
93
  • 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.
 
Bartender
Posts: 4547
50
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
Master Rancher
Posts: 2758
93
  • 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: 4547
50
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: 9145
173
  • 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: 9145
173
  • 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
Master Rancher
Posts: 2758
93
  • 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!
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!