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 equallength 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 nonempty 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; ?
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 subsequence in the remaining unused strings, so that the subsequence 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 unusing the first "q", and it tries the second "q". Then it tries to find a subsequence 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 toplevel 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.
The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.
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?
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 :)
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.
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?
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 ;)
The moth suit and wings road is much more exciting than taxes. Or this tiny ad:
The WEB SERVICES and JAXRS Course
https://coderanch.com/t/690789/WEBSERVICESJAXRS
