Win a copy of Machine Learning Systems: Designs that scale this week in the Scala forum
or Xamarin in Action: Creating native cross-platform mobile apps in the Android forum!
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:
Sheriffs:
Saloon Keepers:
Bartenders:

# My first backtracking algorithm, how does it really work?

Ranch Hand
Posts: 109
2
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; ?

Saloon Keeper
Posts: 8892
166

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.

Master Rancher
Posts: 2644
91
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: 109
2

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
Master Rancher
Posts: 2644
91
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: 109
2

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?

Sheriff
Posts: 4865
136
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: 109
2

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
Master Rancher
Posts: 2644
91
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: 109
2

Piet Souris wrote:
Anyway, rest assured: I won’t tease you any further ;)

Thank you, you asked me really great questions

Piet Souris
Master Rancher
Posts: 2644
91
I'm sorry it slipped my mind, but for this fine example of recursion a cow is well deserved!

 it's a teeny, tiny, wafer thin ad: Rocket Oven Kickstarter - from the trailboss https://coderanch.com/t/695773/Rocket-Oven-Kickstarter-trailboss