Win a 3 month subscription to Marco Behler Videos this week in the Spring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

My first backtracking algorithm, how does it really work?  RSS feed

 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have stumbled upon some code that uses a recursive algorithm (backtracking?)
I am trying to figure out mentally how this would work for the simplest input.
The problem that this code solves is below:

[Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at consecutive positions would differ by exactly one character.

Example

    For inputArray = ["aba", "bbb", "bab"], the output should be
    stringsRearrangement(inputArray) = false;

    All rearrangements don't satisfy the description condition.

    For inputArray = ["ab", "bb", "aa"], the output should be
    stringsRearrangement(inputArray) = true.

    Strings can be rearranged in the following way: "aa", "ab", "bb".
    Input/Output

    [time limit] 3000ms (java)

    [input] array.string inputArray

    A non-empty array of strings of lowercase letters.

    Guaranteed constraints:
    2 ≤ inputArray.length ≤ 10,
    1 ≤ inputArray[i].length ≤ 15.]



Even thinking of the simplest input [q,q] that should give false, I cannot imagine this, what's the order of instructions?
And why used[i] = true; and then used[i] = false; ?


 
Stephan van Hulst
Saloon Keeper
Posts: 7507
135
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sergiu Dobozi wrote:Even thinking of the simplest input [q,q] that should give false, I cannot imagine this, what's the order of instructions?

The algorithm first tries to use the first "q" by setting used[0] to true, and then it tries to find a sub-sequence in the remaining unused strings, so that the sub-sequence can follow "q". So, in the second call to findSequence(), the first "q" is already used, and the algorithm tries to use the second "q". However, since it doesn't differ by one character, and there aren't any more unused strings to try, the second call returns unsuccessfully. The first call that triggered the second call then backtracks by un-using the first "q", and it tries the second "q". Then it tries to find a sub-sequence in the unused strings again, which this time is just the first "q". The result of that is the same as the first time. After backtracking again, the algorithm has run out of unused strings to try, and returns from the top-level findSequence() call, without the success field having changed to true.

And why used[i] = true; and then used[i] = false; ?

The algorithm tracks the progress by setting used[i] to true. It backtracks by setting used[i] to false. The algorithm is successful when all strings have been used.
 
Piet Souris
Rancher
Posts: 1916
66
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Sergiu,

There are some easy improvements possible.

All that is required to detect if a rearrangement is possible, is to see if 'success' is true in the end. Now, if you look at the 'findSequence' method, you will notice that the recursion goes on, even if 'success' has been put to 'true'.
Can you make a small change so that the method returns when that happens, without going into the recursion again?
(You can check the number of calls to the method 'findSequence' if you add a second field to your class, say int counter. Add as the first line in this method: counter++; and when done, print that variable).

In the method 'differByOne' you compare all the chars. What can you say about the outcome when, after the second comparison, count is 2?
 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:hi Sergiu,

There are some easy improvements possible.

All that is required to detect if a rearrangement is possible, is to see if 'success' is true in the end. Now, if you look at the 'findSequence' method, you will notice that the recursion goes on, even if 'success' has been put to 'true'.
Can you make a small change so that the method returns when that happens, without going into the recursion again?
(You can check the number of calls to the method 'findSequence' if you add a second field to your class, say int counter. Add as the first line in this method: counter++; and when done, print that variable).

In the method 'differByOne' you compare all the chars. What can you say about the outcome when, after the second comparison, count is 2?

If the count is 2 there is no need to go any further so it should return false. I changed that.
I am still working out the recursive backtracking in my brain, so I added a stop condition above the for loop in the first findSequence method, using my intuition rather than hard solid knowledge. Let me know if it's right or wrong, please :-)

 
Piet Souris
Rancher
Posts: 1916
66
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First of all: have a look at the method 'differByOne'. If the two strings are equal, what does the method return?

Then: it is not guaranteed that all array elements are equal in length, just that each has length between 2 and 15. What implications does tht have for your code?

And about 'findSequence': it is much more efficient than the original, indeed. The problem is that if, somewhere in the loop, 'success' becomes true, then the loop is still fully executed.

I took the liberty to write a simple application, that makes testing a little esier.


Now, the array used here is {"ag", "bc", "aa", "bb", "ab", "cc"}. Since this array can indeed be successfully arranged, you would expect that 7 calls to 'findSequence' would suffice (one call for n = 0, n = 1, ..., n = 6).
As you see, your second code is much more efficient that the original version., but it is not optimal yet.

 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:First of all: have a look at the method 'differByOne'. If the two strings are equal, what does the method return?

Then: it is not guaranteed that all array elements are equal in length, just that each has length between 2 and 15. What implications does tht have for your code?

And about 'findSequence': it is much more efficient than the original, indeed. The problem is that if, somewhere in the loop, 'success' becomes true, then the loop is still fully executed.

I took the liberty to write a simple application, that makes testing a little esier.

Now, the array used here is {"ag", "bc", "aa", "bb", "ab", "cc"}. Since this array can indeed be successfully arranged, you would expect that 7 calls to 'findSequence' would suffice (one call for n = 0, n = 1, ..., n = 6).
As you see, your second code is much more efficient that the original version., but it is not optimal yet.



Ok, so I am at work right now and downloaded BlueJ since we are not allowed to install software like Eclipse or IntelliJ (I work as a simple data analyst).
I realized I should just move the if(!success) condition right above the method (line 68) as it attacks it directly and now we only have 7 calls to it, it's almost completely optimized.
Now it should be fine for two equal strings (it should return false) but when I wrote the code like this before:


then the two equal strings would return true and that's not what we would need.
Finally, if even one string would have a different length from the rest then this program should return false, I haven't thought about it before. I think this deserves a new method of its own?


 
Knute Snortum
Sheriff
Posts: 3842
91
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is why I consider poor formatting a bug.  You wrote this:

Is it clear from the code that used[i] = false is executed regardless of whether success is true or not?  Instead, format like this:
Is that what you intended?
 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:This is why I consider poor formatting a bug.  You wrote this:
Is that what you intended?

Yes, sorry about that. I don't know why I wrote the if the other way around.
 
Piet Souris
Rancher
Posts: 1916
66
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It seems pretty optimal now, the only (insignificant) difference with what I had is that I had the test on ‘success’ inside the for loop, like:
Another nice way to look at this assignment is to look at it from the Graph way. A vertex is then simply one of the Strings, and two vertices are connected if they ‘differ by One’. The resulting question is then if there is a path in which each vertex appears once and only once. There is no solution for instance if there are three or more vertices that have only one neighbor, or when the Graph is not connected, et cetera. Well, not a handy point of view if you are given only three seconds to solve the question, but interesting nevertheless.

Anyway, rest assured: I won’t tease you any further ;)
 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:
Anyway, rest assured: I won’t tease you any further ;)


Thank you, you asked me really great questions 
 
Piet Souris
Rancher
Posts: 1916
66
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm sorry it slipped my mind, but for this fine example of recursion a cow is well deserved!
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!