Как решить задачу правильно?

Question

[atsin4469]

Задача
Есть список из слов "NORTH", "WEST", "SOUTH" и "EAST". Если рядом стоят WEST и EAST или SOUTH и NORTH, то такая пара удаляется из списка (т.к. сделать шаг вперед, а потом шаг назад — все равно, что стоять на месте). Необходимо вернуть список, очищенный от таких пар с сохранением исходной очередности слов. То есть [NORTH, EAST] не равно [EAST, NORTH]

Примеры вывода

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"] >>> ['WEST']

["NORTH", "WEST", "SOUTH", "EAST"] >>> ["NORTH", "WEST", "SOUTH", "EAST"]

Мое неверное решение

def dirReduc(arr):
    x = 0
    y = 0
    l = []
    for i in arr:
    	if i == 'NORTH':
    		y += 1
    	elif i == 'SOUTH':
    		y -= 1
    	elif i == 'EAST':
    		x += 1
    	else:
    		x -= 1
    if x < 0:
    	l.append('WEST' * abs(x))
    elif x > 0:
    	l.append('EAST' * x)
    if y < 0:
    	l.append('SOUTH' * abs(y))
    elif y > 0:
    	l.append('NORTH' * y)
    return l

Решение не подходит, т.к. не сохраняет порядок слов и имеет другие проблемы

Comments

[dmshar]

.к. сделать шаг вперед, а потом шаг назад — все равно, что стоять на месте- хм, а последовательно сделать четыре шага "NORTH", "WEST", "SOUTH" и "EAST" - это не то-же самое, что стоять на месте?

Answer 1

[o5a]

Подобная задача проще всего решается через стэк.
Перебираем постепенно элементы исходного списка.
Если последний элемент стэка равен противоположному (NORTH-SOUTH и т.п.) текущего элемента списка, то удаляем (stack.pop()) этот элемент из стэка. В противном случае добавляем к стэку. В конце цикла в стэке останется только неисключенные элементы (без пар). Для соответствия пар можно задать словарь.
Примерно так (спрячу под спойлер, на случай если захочется реализовать самостоятельно):

spoiler

def dirReduc(arr):
    dirs = {"NORTH": "SOUTH", "SOUTH": "NORTH", "EAST": "WEST", "WEST": "EAST"}
    stack = []
    for d in arr:
        if stack and dirs[d] == stack[-1]:
            stack.pop()
        else:
            stack.append(d)
    return stack

Comments

[atsin4469]

Очень круто, спасибо!

Answer 2

[vutmuk123]

S=["NORTH", "WEST", "SOUTH", "EAST"]
pair1={"WEST", "EAST" }
pair2={"NORTH", "SOUTH"}

for i in range(len(S)-1,-1,-1):
    if {S[i], S[i - 1]} ==pair1 or {S[i], S[i - 1]} ==pair2:
        S.pop(i)
        S.pop(i-1)

print(S)

не уверен на 100% что верно, но оба примера проходят..)

Comments

[atsin4469]

Выдает такую ошибку:

Traceback (most recent call last):
  File "tests.py", line 38, in <module>
    test.assert_equals(dirReduc(a), ['NORTH', 'NORTH'])
  File "/workspace/default/solution.py", line 6, in dirReduc
    if {S[i], S[i - 1]} ==pair1 or {S[i], S[i - 1]} ==pair2:
IndexError: list index out of range

Задание из этой каты — https://www.codewars.com/kata/550f22f4d758534c1100...

[alegzz]

попробуй с
S = ["NORTH", "WEST", "SOUTH", "EAST", "SOUTH"]

[vutmuk123]

alegzz,

if ({S[i], S[i - 1]} ==pair1 or {S[i], S[i - 1]} ==pair2) and i !=0:

:))

[vutmuk123]

atsin4469,

но вообще я бы посоветовал разобраться в алгоритмах, это типо задача школьного уровня, даже я решил)

[atsin4469]

vutmuk123, попробуйте использовать кнопку Attempt, а не только Test. Там выдает ошибку по-прежнему

[vutmuk123]

atsin4469, точно, я ошибся(
решение через стеки самое изящное..

Answer 3

[alegzz]

def dirReduc(arr):
    DIRS = {'NORTH': 1, 'SOUTH': -1, 'WEST': 1, 'EAST': -1}
    dirs1 = ['WEST', 'EAST']
    dirs2 = ['NORTH', 'SOUTH']
    temparr = []
    previosdirs = []
    i = 0
    while i <= len(arr):
        if previosdirs == []:
            if arr[i] in dirs1:
                previosdirs = dirs1
            elif arr[i] in dirs2:
                previosdirs = dirs2
            steps = DIRS[arr[i]]
        else:
            if i < len(arr) and arr[i] in previosdirs:
                steps += DIRS[arr[i]]
            else:
                if steps > 0:
                    j = 0
                elif steps < 0:
                    j = 1
                temparr.extend([previosdirs[j]] * abs(steps))
                if i < len(arr):
                    if arr[i] in dirs1:
                        previosdirs = dirs1
                    else:
                        previosdirs = dirs2
                    steps = DIRS[arr[i]]
        i += 1

    return temparr

оптимизируй это