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

Need an alternative solution to this recursion problem using array  RSS feed

 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, everyone

Here's the question

Given an array of ints, compute recursively if the array contains somewhere a value followed in the array by that value times 10. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0.

These are the test cases the program has to pass
array220([1, 2, 20], 0) → true
array220([3, 30], 0) → true
array220([3], 0) → false
array220([], 0) → false
array220([3, 3, 30, 4], 0) → true
array220([2, 19, 4], 0) → false
array220([20, 2, 21], 0) → false
array220([20, 2, 21, 210], 0) → true
array220([2, 200, 2000], 0) → true
array220([0, 0], 0) → true
array220([1, 2, 3, 4, 5, 6], 0) → false
array220([1, 2, 3, 4, 5, 50, 6], 0) → true
array220([1, 2, 3, 4, 5, 51, 6], 0) → false
array220([1, 2, 3, 4, 4, 50, 500, 6], 0) → true

Here' my approach to the problem



I followed Junlu's tests, and thus handling all the test cases made this program. But I am desperate to know, if this problem could have been solved without using an for loop, or if there is some other approach that one could take.
And the function signature that must be stuck to is "public boolean array220(int[] nums, int index) ".

Regards,
Ranajoy Saha
 
Junilu Lacar
Sheriff
Posts: 11145
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote:
I followed Junlu's tests, and thus handling all the test cases made this program. But I am desperate to know, if this problem could have been solved without using an for loop, or if there is some other approach that one could take.
And the function signature that must be stuck to is "public boolean array220(int[] nums, int index) ".

Aside from the odd choice of name, this again does not quite follow the way a recursive solution is usually fashioned. You could absolutely do this without a for-loop and the solution is not unlike the other problems you have already discussed before.

You start out well enough by considering the minimal and trivial cases but when you go the more general cases you lost it. Go back to the previous posts and thoroughly understand what the pattern is for the recursive solutions that don't use loops.
 
Junilu Lacar
Sheriff
Posts: 11145
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your first check, if (nums.length <= 1), does not fit with your strategy to recurse with the index into the nums array. It should be something slightly different. See my modified tail-recursive solution in your other post that's fashioned after the solution that Chandler Deng suggested.
 
Campbell Ritchie
Marshal
Posts: 55715
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, you can easily do that by iteration. In fact, iteration and recursion are equivalent in the definitions of program semantics, so it should be possible to use either.
Do you mean that if you start in an array at index n, you can recursively walk the array until you find a value array[n + 1] which is ten times array[n]. You have been told to use a particular method header, which looks similar to what I would have chosen for that exercise, apart from its missing static. Yes, I would write that as a static method myself. It should read public static not static public, for reasons of good style.
Write down on paper how you are going to solve that.

I think your solution is too long. Why are you multiplying the first value of the array? Why have you got all those ifs? Check with your instructor what should happen if the array reads like this:-
[1, 2, 3, 4, 5, 6, 10, 20, 30, 40, 50, 60], 0
I think that should return false.
 
Junilu Lacar
Sheriff
Posts: 11145
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For the recursion solution, you really should be thinking of the basic question: "Is the next number == 10 * the current number?"

The trick is figuring out the appropriate way to represent "the current number" and "the next number" as you go through the evaluation and recurse.

The recursive part is when you get: "No, it's not, then do the same evaluation except use the next number as the current number"

 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I went through the post and saw that you created another method which cleared the string of duplicates iteratively. I'm sorry, I can't get your point clearly. The point where I need to focus is the I need to stick to "public boolean array220(int[] nums, int index)" this function signature, and the name array220 is odd I know. But that was the name given to me by this website CodingBat. I am following a path, where I am reducing the array of the first element after I have iterated through all the elements and didn't find a match. What approach should I take then?
 
Junilu Lacar
Sheriff
Posts: 11145
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Why have you got all those ifs?

It comes from not identifying redundant checks and simplifying/consolidating. This is the danger in just forging ahead without refactoring. This can happen even when you're driving the development of the solution with tests.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about thinking what represents your current value and previous value, even if you weren't recursing.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie, I'm afraid that the problems I've been solving were taken from the website http://codingbat.com/prob/p173469 and the test cases that I provided were taken from that site as well, so I'm kinda confused what [1, 2, 3, 4, 5, 6, 10, 20, 30, 40, 50, 60], 0 this gives because I'm unable to comprehend the entire meaning of "if the array contains somewhere a value followed in the array by that value times 10". What I assumed was that if there is an element1 in the array and if there exists another element2 in the array after element1 and if element1*10 == element2 then the method should return true other wise false, and I will take care about the program writing conventions hence forth. And Junilu Lacar, I'm working on finding a new approach to this problem, based on your suggestion.
 
Junilu Lacar
Sheriff
Posts: 11145
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I guess it also comes from thinking about specific cases rather than trivial and degenerate cases.

For example, the test if (index == 0) on line 12 is specific case, not a trivial or degenerate case. You have to remember that the index parameter is an absolute position in the nums array. You want to turn that into a relative value with respect to the "current" and "next" number concepts.
 
Junilu Lacar
Sheriff
Posts: 11145
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A simple Rename refactoring can lead you in the right direction:

You have to think of the ideas that you're dealing with and use names in your program that represent those ideas correctly. Poorly chosen names hide the solution and lead you astray.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's what I thought of based on Junilu's suggestions. I'm unable to determine when this approach should return false.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote:Given an array of ints, compute recursively if the array contains somewhere a value followed in the array by that value times 10.

I'm afraid that requirement is ambiguous. Specifically, what should:
array220([3, 5, 30, 4], 0)
return?

ie: does "followed in the array by" mean "followed immediately by" or "followed anywhere by"?

Because the solutions will be different.

Winston
 
Junilu Lacar
Sheriff
Posts: 11145
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you have misunderstood the requirements. It says "compute recursively if the array contains somewhere a value followed in the array by that value times 10". Look at the examples where the method should return true or false more carefully. You shouldn't be creating any new arrays or rearrange the numbers in the original. You're just walking through the array to see if there are any elements that are adjacent to each other that satisfy the condition of a number followed by 10 * that number.

For the input of [1, 2, 20] , the result should be true because the second element, 2, is followed by 20 (which is 10 * 2).
 
Junilu Lacar
Sheriff
Posts: 11145
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston, based on the examples given, I would say it means "followed immediately by..."

Therefore, the input ([3, 5, 30, 4], 0) should result in false.

Here are more examples:

([2, 20, 5, 6, 7], 2) --> false
([2, 20, 5, 6, 7], 1) --> false
([2, 20, 5, 6, 7], 0) --> true
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is it not ""followed anywhere by" in the array? If it's "followed immediately by" then the base case will be simple if(index == nums.length-1) return false, but what if it's "followed anywhere by" in the array. What should be the approach then?
 
Junilu Lacar
Sheriff
Posts: 11145
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote:Is it not ""followed anywhere by" in the array? If it's "followed immediately by" then the base case will be simple if(index == nums.length-1) return false, but what if it's "followed anywhere by" in the array. What should be the approach then?

Why are you trying to fly before you can even crawl?
 
Junilu Lacar
Sheriff
Posts: 11145
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote:if(index == nums.length-1) return false

Still not right. Please read my previous suggestions carefully.
Sorry. I don't know what I was thinking. That's actually on the right track.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just asking. And is my current base case "if(index == nums.length-1) return false;" correct?
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's the working code.



Now please tell me what if, instead of "followed immediately by"" in the array it's followed anywhere by" in the array. What should be the approach then?
 
Liutauras Vilda
Marshal
Posts: 4640
316
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote:Is it not ""followed anywhere by" in the array? If it's "followed immediately by" then the base case will be simple if(index == nums.length-1) return false, but what if it's "followed anywhere by" in the array. What should be the approach then?
About the base case think as about the simplest possible case/-s.

Since it is an array, that could be:
  • null
  • [] - an empty array
  • [1] - 1 element array
  • index is equal array length-1

  • So in those cases you return false as can not be otherwise.

    If none of those above conditions are true, then you need to worry only about the elements within the array immediately after the certain index AND only about the current element and element next to it.
    Every time you check, you check current with the next element if it is equal to current element * 10, then index gets increased and again the same.
     
    Ranajoy Saha
    Ranch Hand
    Posts: 105
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    The previous code doesn't work. Fixing the bug!
     
    Ranajoy Saha
    Ranch Hand
    Posts: 105
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    The fixed code. Thanks for the suggestion Liutauras Vilda, implemented those in the code.



    And please tell me now, Junilu Lacar, what if, instead of "followed immediately by"" in the array it's followed anywhere by" in the array. What should have been the approach then?
     
    Liutauras Vilda
    Marshal
    Posts: 4640
    316
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    That part is wrong, it can be true.
     
    Ranajoy Saha
    Ranch Hand
    Posts: 105
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Refactored the code as well.

     
    Liutauras Vilda
    Marshal
    Posts: 4640
    316
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    That looks right to me. Have you tested?
     
    Ranajoy Saha
    Ranch Hand
    Posts: 105
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Yes, it does work with all the test cases. Now what should I do about the next case type approach?
    Code-Runs-Succesfully.png
    [Thumbnail for Code-Runs-Succesfully.png]
     
    Junilu Lacar
    Sheriff
    Posts: 11145
    160
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Ranajoy Saha wrote:Here's the working code.

    It fails all of the assertions that are commented out:

    EDIT: some of the ones I said failed actually pass when I double checked. That's the problem with having too many asserts in one test. I've corrected it now.
     
    Ranajoy Saha
    Ranch Hand
    Posts: 105
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Now please tell me what if, instead of "followed immediately by"" in the array if it's followed anywhere by" in the array. What should be the approach then? Is there any different approach other than my first posted approach?
     
    Junilu Lacar
    Sheriff
    Posts: 11145
    160
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Ranajoy Saha wrote:The fixed code. Thanks for the suggestion Liutauras Vilda, implemented those in the code.

    ... Refactored the code as well

    Now that passes all the assertions.
     
    Junilu Lacar
    Sheriff
    Posts: 11145
    160
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Ranajoy Saha wrote:Now please tell me what if, instead of "followed immediately by"" in the array if it's followed anywhere by" in the array. What should be the approach then? Is there any different approach other than my first posted approach?

    Well, we wouldn't want to deprive you of the fun of trying to figure it out yourself first, would we?
     
    Ranajoy Saha
    Ranch Hand
    Posts: 105
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Please, no no no. Don't do this to me. I really can't think of any other solution other than the one that I provided in the first post. I could implement my shifting of the numbers in the array after they have been worked with to the last, provided I'm given the liberty to include another variable in the parameter of the function. But is there anyway this new problem could be solved by sticking to this function signature "public static boolean hasAdjacentMultiple(int num[], int index)"?
     
    Winston Gutkowski
    Bartender
    Posts: 10573
    65
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Junilu Lacar wrote:Winston, based on the examples given, I would say it means "followed immediately by..."

    True, but I didn't see any that specifically allow us to infer what the meaning of "followed by" is, because all the ones where it returns true are indeed "followed immediately by", but there are no examples like mine.

    ie: bad (or maybe really good) test set.

    Winston
     
    Winston Gutkowski
    Bartender
    Posts: 10573
    65
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Winston Gutkowski wrote:ie: bad (or maybe really good) test set.

    Which begs a question for you, Junilu, as our resident TDD guru:

    Based on the tests you've been given, you have - quite rightly - assumed that the program only needs to check for the next immediate value, because it's the simplest solution that satisfies all the tests.

    But what if that's not what was intended? It seems to me that it's far harder to determine what the intent of a set of tests is than it is to infer what the intent of a program is from its code.

    So how does TDD make sure that the tests completely convey intent?

    Winston
     
    Liutauras Vilda
    Marshal
    Posts: 4640
    316
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Ranajoy Saha wrote:Now please tell me what if, instead of "followed immediately by"" in the array if it's followed anywhere by" in the array. What should be the approach then? Is there any different approach other than my first posted approach?
    Only small hint:

    You'll need another signature, with 2 indices and 2 recursive calls.
     
    Ranajoy Saha
    Ranch Hand
    Posts: 105
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Liutauras Vilda wrote:
    Ranajoy Saha wrote:Now please tell me what if, instead of "followed immediately by"" in the array if it's followed anywhere by" in the array. What should be the approach then? Is there any different approach other than my first posted approach?
    Only small hint:

    You'll need another signature, with 2 indices and 2 recursive calls.


    Is there any way, the problem could be solved without changing the function signature?
     
    Liutauras Vilda
    Marshal
    Posts: 4640
    316
    BSD
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Winston Gutkowski wrote:So how does TDD make sure that the tests completely convey intent?

    It doesn't. TDD does not promise a guarantee correctness of your solution, in the same way as passed JUnit tests do not guarantee that (as you might missed the only one test case which was a key to collapse your solution), but rather forces you to think about the requirements prior jumping on the actual implementation.
    Even after all there is no guarantee you understood them well, BUT, as this came up question nicely shows, it raised some extra questions right away - I think that is the main intent of TDD, to improve developers chances to catch the logic flaw.
     
    Junilu Lacar
    Sheriff
    Posts: 11145
    160
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Likes 2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    To add to Liutauras' great observation (brings tears to my eyes, honestly), I see TDD as a way to build a framework of thinking around a problem. The "guarantee", if there ever was any, comes from the effort and skill that you put into writing the tests and thinking through the possible scenarios. That the tests completely convey intent comes from reading them out loud and determining whether they do or not and then refactoring as you deem necessary. As Liutauras mentioned though, there is no absolute guarantee. There's only enough to have confidence in saying that you're done and it's good enough, at least for the time being.
     
    Campbell Ritchie
    Marshal
    Posts: 55715
    163
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Winston Gutkowski wrote:. . . I'm afraid that requirement is ambiguous. Specifically, what should:
    array220([3, 5, 30, 4], 0)
    return? . . .
    I tried the coding bat example and there is no hint of a test like that. I think it should return false and coding bat have forgotten to include that test.
     
    It is sorta covered in the JavaRanch Style Guide.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!