Avicii

Wake Me Up - Avicii / Aloe Blacc

鸽子王走了

一.题目

今天题目挺长的

Once upon a time, on a way through the old wild west,…

… 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"].

or

{ "NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST" };

or (haskell)

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

or

{ "WEST" }

or (haskell)

[West]

or (rust)

[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 [] (nil in Clojure).

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

The Haskell version takes a list of directions with data Direction = North | East | West | South. The Clojure version returns nil when the path is reduced to nothing. The Rust version takes a slice of enum Direction {NORTH, SOUTH, EAST, WEST}.
Examples

dirReduc(@[@"NORTH", @"SOUTH", @"SOUTH", @"EAST", @"WEST", @"NORTH", @"WEST"]); // => @[@"WEST"]
dirReduc(@[@"NORTH", @"SOUTH", @"SOUTH", @"EAST", @"WEST", @"NORTH"]); // => @[]

See more examples in "Example Tests"
Note

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

大致意思就是

一个男人在荒漠中迷失了，现在他得到一条指令前往下一个地点，只有东南西北四个方向，很明显，如果往东走后再往西走是没有必要的。这只会浪费他的体力，而他的体力有限，必须尽量缩少移动的步数，所以请写一个函数，传入列表，里面是东南西北四个方向。判断有哪些可以不必走的指令（走东后走西，走西后走东，走南后走北，走北后走南），删除这些制定，最后返回最简指令。不过如果指令是[北，西，南，东]没有可以缩减的指令，因为东和西，南和北没有直接相连，所以没有可以缩减的指令，最后返回它自己。

初始代码

def dirReduc(arr):

举个栗子

a = ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
test.assert_equals(dirReduc(a), ['WEST'])
u=["NORTH", "WEST", "SOUTH", "EAST"]
test.assert_equals(dirReduc(u), ["NORTH", "WEST", "SOUTH", "EAST"])

2.思路和代码

思路

最开始还一位是简单的判断南多少个，北多少个，然后直接互相抵消。但仔细看最后的说明，题目说了，如果不是直接相连的相反方向的指令是不能消除的，这也是为什么

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

并没有缩减指令的原因。

这时想起了学数据结构时候学的一个概念——栈（stack）

栈又称先进后出表，也可以叫后进先出表。栈包含两个部分，栈顶和栈底。但这里并不详细的讲栈，而是讲讲栈的思想
栈的思想是这样的，如果我要存入3个字符A、B和C，这时候按顺序A先，然后是B，最后是C进入。

| (空)
'A' |
'A' ,'B'|
'A' ,'B', 'C' |

如果要删除B的话，只能把C删除，再删除B，不能直接删除B

'A' ,'B', 'C' |
'A' ,'B'|
'A' |

后进先出的思想就体现在这里，先进入的元素（A），进入栈底。我们增加元素和删除元素的操作，都只能在尾端也就是栈顶操作。如果要操作的元素并不在栈顶，也就是最尾端，那就不能对其操作。只能对尾端的元素操作，也就是后进来的元素操作，这就是后进先出。

所以在这里我们构造一个空列表，我命名为stack。
然后遍历一次传进来的指令，按顺序把方向指令一个一个进入，并判断尾端两个是否是相反的指令,是就删除，不是就不做任何操作。
例如stack最后两个指令如果是南和北，那么最后两位赋值为空，即删除。然后下一个方向进来，判断最后两个是否相等。

代码

def dirReduc(arr):
    stack=[]
    for direction in arr:
        stack.append(direction)
        while set(stack[-2:])==set(['NORTH','SOUTH']) or set(stack[-2:])==set(['WEST','EAST']):
            stack[-2:]=[]
    return stack

代码解析

命名一个stack空列表，然后做遍历，每个元素依次放入我们的栈stack中，如果最后两位相等则删除。遍历结束，返回栈。
这里判断相等的方法我用的是集合，set()函数将列表后两位变为集合，与我们的目标集合判断是否相等。

set(stack[-2:])==set(['NORTH','SOUTH'])

set(stack[-2:])==set(['WEST','EAST'])

不过当时写的时候脑子秀逗了，用了while，现在都忘了当时为什么这么写，┑(￣Д ￣)┍

while set(stack[-2:])==set(['NORTH','SOUTH']) or set(stack[-2:])==set(['WEST','EAST']):

其实使用if判断即可

if set(stack[-2:])==set(['NORTH','SOUTH']) or set(stack[-2:])==set(['WEST','EAST']):

三.最优解代码

Best Practices

代码如下

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

嗯，看得出这才是栈的最正确用法。。。233红红火火恍恍惚惚🤣

准确来说，栈对元素的操作是最后一个，而我的代码是对尾端两个元素的操作，只能说是我的代码是借了栈的思想，但并不是栈。
另外在这里，我们可以看到他判断方向相反的方法是字典，字典是一种映射关系。冒号 （:）左边是键，右边是值（key-value即键值对）。四个方向都有自己相反方向的映射。举个例子，如果列表非空，最后一个元素是南，下一个方向进来了——北。通过字典我们查到北的相反方向是南，与列表最后一位相等，删除列表最后的元素南。

假设 此时列表非空，最后一个元素是南
new_plan[-1]='南'
d = '北'
opposite[d]=‘南’
new_plan[-1]==opposite[d] 是true
new_plan.pop() 删除最后一个元素

讲完第一的答案我们来说说第二的答案，第二的答案可以说非常的有意思。 我很喜欢这种新奇的思路。

def dirReduc(arr):
    dir = " ".join(arr)
    dir2 = dir.replace("NORTH SOUTH",'').replace("SOUTH NORTH",'').replace("EAST WEST",'').replace("WEST EAST",'')
    dir3 = dir2.split()
    return dirReduc(dir3) if len(dir3) < len(arr) else dir3

给我一个列表
我把他们列表每个元素用空格连接，变成了字符串
我用字符串的方法，去掉了相邻的相反的指令
不过缩短一次可不够，新生成的短指令可能还存在可以缩短的指令哦
那就来个递归吧，如果这次缩短了，我的长度变短，那就再对这个列表进行缩短指令的函数，如果这次长度没有变短，说明已经是最简指令了，返回最简指令。

为什么用递归，
用题目中的那个例子举例

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

如果只做一次，dir3将得到

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

这里还能再缩短一次，因为原本SOUTH和 NORTH之间的EAST和WEST去除了，现在SOUTH和 NORTH连接在一起应该去除的但指令就做到这了，所以用递归的方法。

四.总结

1.相反方向的判断
我的方法是用集合，第一的答案是用字典（映射的思想）。

2.栈的思想
一个列表对最后一个元素的地方进行添加和删除。（后进先出）

3.递归
递归可以视为一种循环，递归很厉害，但我对递归的掌握还不是很熟悉。

一点题外话

起床看到的第一条消息就是Avicii死亡的消息，当时只觉得在开玩笑吗。但是当确认是真的时候，很震撼又很难受。
Without You 这首歌已经忘了听了几遍了。真是好听....