Самая длинная последовательность Snake в списке номеров

Question

Вопрос: В качестве входных данных передается набор чисел, разделенных пробелом. Программа должна печатать самую большую последовательность змеи, присутствующую в числах. Последовательность змеи состоит из смежных чисел, так что для каждого числа число справа или слева составляет +1 или -1 его значения. Если возможно несколько серий змейков максимальной длины, напечатайте последовательность змеи, появляющуюся в естественном порядке ввода.

Пример ввода/вывода 1:

Входной сигнал:

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

Выход:

3 2 1 0 1 

Пример ввода/вывода 2:

Входной сигнал:

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

Выход:

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

Пример ввода/вывода 3:

Входной сигнал:

5 6 7 9 8 8 

Выход:

5 6 7 8 9 8 

Я нашел программу в Python по этой ссылке: "Longest Snake in an array" как показано ниже, но он не выполняет следующий тестовый пример. Как упоминалось в вопросе в случае двух или более последовательности максимальной длины, программа должна печатать последовательность змеи, появляющуюся в порядке естественного ввода. Я подозреваю, что это параметр, создающий проблему.

Результат должен быть тем, что показывает эта программа, поскольку точка разницы равна 8 и 10. (Если я не ошибаюсь в отношении того, что означает естественный порядок) 8, появляющиеся до 10 в списке входных данных, должны быть взяты в последовательность для правильный выход вместо 10, но это не ожидаемый результат.

""" 
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

Я сделал небольшое изменение в моем алгоритме. Он все еще не удовлетворяет всем тестовым примерам, но он намного ближе к тому, что я понимаю как «естественный порядок ввода».

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 

Вот как это работает сейчас:

• он отслеживает текущую позицию в списке ввода (pos)
• при рекурсии, он по-прежнему в этом положении, проходя pos + i к рекурсивной вызовите, таким образом, пробуя «куски» чисел сначала
• , если pos + i больше длины ввода, оно обертывается к началу
• , если два пути змеи имеют одинаковую длину, он принимает путь, который имеет более низкое общее положение, т.е.для которых было необходимо меньшее продвижение на входе и меньшее «обертывание» до начала

Как я уже говорил, он намного ближе к «естественному порядку ввода», но все еще не идеален. Вот пример:

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 

---

В конце концов, все сводится к тому, как «естественный порядок ввода» определяется. Возьмите первый тестовый пример, то есть 9 8 7 5 3 0 1 -2 -3 1 2: Эта версия кода дает 1 0 1 2 3, но ожидается 3 2 1 0 1. Но почему? Мой результат имеет одну пару чисел, которые были рядом друг с другом на входе (1 2), в то время как ожидаемый результат не имеет, а у меня также меньше «шагов» (два раза вокруг, а затем до 3, а ожидаемый - два раз и до одного из 1 s).

Или, иначе говоря: Вы можете взять свой алгоритм и изменить условие к этому:

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

Если вы можете определить функцию isMoreOrdered(numbers, new_path, old_path), то вы сделали. Но из нескольких примеров и формулировки вопроса я, конечно, не могу сказать.

В любом случае, может быть, это дало вам некоторые идеи, и вы можете сами выяснить остальное.