Longest Snake Sequence in a list of numbers

Question

Question : A set of numbers separated by space is passed as input. The program must print the largest snake sequence present in the numbers. A snake sequence is made up of adjacent numbers such that for each number, the number on the right or left is +1 or -1 of it's value. If multiple snake sequences of maximum length is possible print the snake sequence appearing in the natural input order.

Example Input/Output 1:

Input:

9 8 7 5 3 0 1 -2 -3 1 2

Output:

3 2 1 0 1

Example Input/Output 2:

Input:

-5 -4 -3 -1 0 1 4 6 5 4 3 4 3 2 1 0 2 -3 9

Output:

6 5 4 3 4 3 2 1 0 -1 0 1 2

Example Input/Output 3:

Input:

5 6 7 9 8 8

Output:

5 6 7 8 9 8

I found a program in Python from this link: "Longest Snake in an array" as below but it fails to fulfill the following test case. As mentioned in the question in case of two or more sequence of maximum length the program has to print the snake sequence appearing in the Natural input order. I suspect that this the parameter that is creating the problem.

The output should be what this program is showing since the point of difference is 8 and 10.(If I am not wrong about what natural order means) 8 appearing before 10 in the input list should be taken into the sequence for correct output instead of 10 but that is not the expected output.

"""
Test case Input:
4 3 1 6 7 8 8 21 7 8 9 13 -1 2 14 9 10 11 10 9

Expected Output:
6 7 8 7 8 9 10 11 10 9 8 9

Your Program Output:
6 7 8 7 8 9 8 9 10 9 10 11
"""

from collections import Counter
def longest_snake(numbers,counts,path):
        best = path
        for n in sorted(counts, key = numbers.index, reverse=True):
                if counts[n] > 0 and (path == [] or abs(path[-1] - n) == 1):
                        counts[n] -= 1
                        res = longest_snake(numbers,counts,path + [n])
                        if (len(res) > len(best)):
                                best = res
                        counts[n] += 1
        return best
if __name__ == '__main__':
        numbers = list(map(int, raw_input().split()))
        output = longest_snake(numbers,Counter(numbers),[])[::-1]
        print(' '.join(map(str,output)))

Answer 1

I made a slight variation of my algorithm. It still does not satisfy all the test cases, but it's much closer to what I understand to be the "natural input order".

def longest_snake(numbers, counts, path, pos=0):
    visited = set()                                # keep track of visited nodes
    best, total = path, pos                        # best path and best pos
    for i in range(len(numbers)):                  # for one more round...
        n = numbers[(pos + i) % len(numbers)]      # wrap around edges, get n
        if n not in visited and counts[n] > 0 and (path == [] or abs(path[-1] - n) == 1):
            visited.add(n)
            counts[n] -= 1
            res, t = longest_snake(numbers, counts, path + [n], pos + i)
            if len(res) > len(best) or (len(res) == len(best) and t < total):
                best, total = res, t               # longer path or fewer steps
            counts[n] += 1
    return best, total                             # return both path and total steps

Here's how it works now:

• it keeps track of the current position in the input list (pos)
• when recursing, it continues at that position, passing pos + i to the recursive call, thus trying "chunks" of numbers first
• if pos + i is greater than the length of the input, it wraps around to the beginning
• if two snake paths have the same length, it takes the path that has a lower total position, i.e. for which less advancement in the input and less "wrapping around" to the beginning was necessary

As I said, it's much closer to the "natural input order", but still not perfect. Here's an example:

6 5 4 3 4 3 2 1 0 -1 0 1 2  # expected output
4 5 4 3 4 3 2 1 0 -1 0 1 2  # my output 

---

In the end, it all boils down to how "natural input order" is defined. Take the first test case, i.e. 9 8 7 5 3 0 1 -2 -3 1 2: This version of the code yields 1 0 1 2 3, but expected is 3 2 1 0 1. But why? My result has one pair of numbers that were next to each other in the input (1 2), while the expected output has none, and mine also has fewer "steps" (two times around and then up to 3, while the expected has two times around and up to one of the 1s).

Or to put it differently: You can take my algorithm and change the condition to this:

if len(res) > len(best) or (len(res) == len(best) and isMoreOrdered(numbers, res, best)):`

If you can define the function isMoreOrdered(numbers, new_path, old_path), then you are done. But from the few examples and the wording of the question, I certainly can not tell.

Anyway, maybe this gave you some ideas and you can figure out the rest on your own.