Python-сообщество

Fixx_Jr · Авг. 7, 2019 20:18:35

условие задачи.
… a man was given directions to go from one point to another. The directions were “NORTH”, “SOUTH”, “WEST”, “EAST”. Clearly “NORTH” and “SOUTH” are opposite, “WEST” and “EAST” too. Going to one direction and coming back the opposite direction is a needless effort. Since this is the wild west, with dreadfull weather and not much water, it's important to save yourself some energy, otherwise you might die of thirst!
How I crossed the desert the smart way.

The directions given to the man are, for example, the following:

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

You can immediatly see that going “NORTH” and then “SOUTH” is not reasonable, better stay to the same place! So the task is to give to the man a simplified version of the plan. A better plan in this case is simply:

 ["WEST"]

Other examples:

In

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

the direction “NORTH” + “SOUTH” is going north and coming back right away. What a waste of time! Better to do nothing.

The path becomes

 ["EAST", "WEST"]

, now “EAST” and “WEST” annihilate each other, therefore, the final result is

[]

In

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

“NORTH” and “SOUTH” are not directly opposite but they become directly opposite after the reduction of “EAST” and “WEST” so the whole path is reducible to

 ["WEST", "WEST"]

Task

Write a function dirReduc which will take an array of strings and returns an array of strings with the needless directions removed (W<->E or S<->N side by side).

Notes

Not all paths can be made simpler. The path

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

is not reducible. “NORTH” and “WEST”, “WEST” and “SOUTH”, “SOUTH” and “EAST” are not directly opposite of each other and can't become such. Hence the result path is itself :

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

.

Одно из решений такое:

 opposite = {'NORTH': 'SOUTH', 'EAST': 'WEST', 'SOUTH': 'NORTH', 'WEST': 'EAST'}
def dirReduc(plan):
    new_plan = []
    for d in plan:
        if new_plan and new_plan[-1] == opposite[d]:
            new_plan.pop()
        else:
            new_plan.append(d)
    return new_plan

Вопросы:
1. по условию удалять надо пары значений, а здесь удаляется одно. Почему это работает?
2. Сравнение двух элементов списка со словарем. Как это работает без перебора элементов?

Отредактировано Fixx_Jr (Авг. 7, 2019 20:25:43)

py.user.next · Авг. 8, 2019 03:13:21

Fixx_Jr
1. по условию удалять надо пары значений, а здесь удаляется одно. Почему это работает?

Потому что он не добавляет второе значение, если оно противоположно проверяемому, а вместо этого удаляет проверяемое.

Fixx_Jr
2. Сравнение двух элементов списка со словарем. Как это работает без перебора элементов?

Похоже, ты просто не вкурил, как работает эта функция. Она не проверяет два значения в списке. Она проверяет значение перед тем как его добавить в список.

Псевдокод этой функции

цикл для каждого элемента во входном_плане выполнять
  если в выходном_плане нет элементов то
    добавить элемент в выходной_план
  иначе
    если элемент противоположен последнему_добавленному_элементу в выходном_плане то
      удалить из выходного_плана последний_добавленный_элемент
    конец если
  конец если
конец цикла
| утв: в выходном_плане только непротивоположные элементы

Отредактировано py.user.next (Авг. 8, 2019 03:18:35)

Fixx_Jr · Авг. 8, 2019 21:33:43

спасибо, огромное!
я даже с объяснениями не сразу допер, но все-таки осилил

Python-сообщество

Уведомления

#1 Авг. 7, 2019 20:18:35

Не могу разобрать решение задачи. Нужна помощь.

#2 Авг. 8, 2019 03:13:21

Не могу разобрать решение задачи. Нужна помощь.

#3 Авг. 8, 2019 21:33:43

Не могу разобрать решение задачи. Нужна помощь.

Board footer