4
$\begingroup$

This is a question from CodeFights.com:

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. (sic)

  • For inputArray = ["ab", "bb", "aa"], the output should be stringsRearrangement(inputArray) = true. Strings can be rearranged in the following way: "aa", "ab", "bb".

I found an exponential-time algorithm, but is there a polynomial-time algorithm? Is this problem NP-complete?

I know that a closely related problem, the Hamming Salesman Problem (HTSP), is NP-complete, and this problem is certainly reducible to HTSP, but I don't know if HTSP is reducible to this one.

$\endgroup$
  • $\begingroup$ Please don't use "EDIT:" or strikeout. Instead, revise the question to read well for someone who encounters it for the first time. Incorporate your edits into the text rather than marking them with "EDIT:". Anything that is no longer relevant should be deleted. Make sure it's clear what the question is. You don't need to mark changes or use strikeout to preserve old versions; we have revision history for that (see the "edited..." link under the question). See cs.meta.stackexchange.com/q/657/755 for more. $\endgroup$ – D.W. Oct 19 '17 at 15:42
4
$\begingroup$

Grid graphs are finite node-induced graphs of the infinite planar grid (whose vertices are integral points, and two vertices are linked when their Euclidean distance is 1). A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter proved that the Hamiltonian path problem on grid graphs is NP-complete.

To reduce that to your problem, suppose the grid graph has $m$ rows and $n$ columns. The $i$-th row is labeled with the string $a^ib^{m-i}$, and the $j$-th column is labeled with the string $a^jb^{n-j}$. Then a vertex corresponds to the concatenation of the two labels of its row and column. Now it is easy to show the unit disk graph under Hamming distance over all these concatenated strings is exactly the same as the original grid graph.

$\endgroup$
0
$\begingroup$

I am the someone who suggested the (apparently, now, failing algorithm). Here is a "reference implementation" in Python:

def consecutive(str1, str2): # are two strings consecutive?
    if str1 == str2:
        return False  # identical strings are not consecutive
    for i, L in enumerate(str1):  
        if L == str2[i]:  #compare strings one char at a time
            continue
        else:  # if the chars aren't the same
            str2 = list(str2)     
            str2[i] = L           # swap the letter of str2 with 
            str2 = "".join(str2)  # one from str2, and compare
            return str1 == str2   # if now strs are the same
    return True                   # they are consecutive

def stringsRearrangement(inputArray):

    ordered = [inputArray[0]]  
    left = inputArray[1:]

    previous_left = len(left) + 1 # sets the first iteration
                                  # of while loop to true

    while previous_left > len(left):  # less items than last iteration
        previous_left = len(left)  
        for i,string in enumerate(left): # iter through left
            if consecutive(ordered[-1], string): # try to move item
                ordered.append(left.pop(i))      # from left to ordered 
                break
            elif consecutive(ordered[0], string):
                ordered.insert(0, left.pop(i))
                break

    while left:                   # if still items in left
        previous_left = len(left) # to check if left is decreasing
        for i,string in enumerate(ordered): #iter thru ordered
            if consecutive(string, left[0]): #to find something in left
                try:                         # that can be inserted
                    if consecutive(left[0], ordered[i+1]):
                        ordered.insert(i+1, left.pop(0))
                        break
                except IndexError:  #if 
                    ordered.append(left.pop(0))
        if previous_left == len(left): #if nothing found
            break
    return not (bool(left)) # true if left is empty

I'm not sure how one would prove that it always works -- but I also cannot find a failing input.

-- EDIT

Could you explain your code with actual text or give the pseudocode?

added comments, let me know if that is enough

$\endgroup$
  • 2
    $\begingroup$ I found a counter example: ["ca", "ba", "aa", "ab", "ac", "bb"]. This program returns False. The correct answer is True. (The strings can be rearranged as follows: ["ca", "ba", "aa", "ac", "ab", "bb"].) Sorry, Adam... $\endgroup$ – Ron Inbar Oct 18 '17 at 21:00
  • 1
    $\begingroup$ Could you explain your code with actual text or give the pseudocode? $\endgroup$ – Evil Oct 18 '17 at 21:23
  • 4
    $\begingroup$ This doesn't appear to answer the question. This is not a coding site, so answers that consist solely or primarily of code aren't suitable here. We want answers to contain ideas, algorithms, concise pseudocode, and proofs/arguments of correctness. Also I don't see any reason to believe your code is correct. Finally, the question asks whether this algorithm is correct. Your answer says "I don't know if it is correct but I implemented it in Python". That doesn't answer the question. $\endgroup$ – D.W. Oct 18 '17 at 22:52
  • $\begingroup$ The Python code was my original implementation of my algorithm that the OP mentioned. (I am the someone who suggested it). I posted for reference. I could remove it, but I hardly see how that is helpful at this point. $\endgroup$ – Adam Michael Wood Oct 18 '17 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.