見習村15 - Directions Reduction

15 - Directions Reduction

Don’t say so much, just coding…

Instruction

Once upon a time, on a way through the old wild mountainous 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 right away 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 a mountain desert the smart way.
The directions given to the man are, for example, the following (depending on the language):

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

You can immediatly see that going “NORTH” and immediately “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:

1
["WEST"]

Other examples:

In ["NORTH", "SOUTH", "EAST", "WEST"], the direction “NORTH” + “SOUTH” is going north and coming back right away.

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

Ruby

Init

1
2
3
def dirReduc(arr)
  ... your code ...
end

Sample Testing

1
2
3
4
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"])

Javascript

Init

1
2
3
function dirReduc(arr){
  // ...
}

Sample Testing

1
2
3
Test.assertSimilar(dirReduc(["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]), ["WEST"])
Test.assertSimilar(dirReduc(["NORTH", "WEST", "SOUTH", "EAST"]), ["NORTH", "WEST", "SOUTH", "EAST"])
Test.assertSimilar(dirReduc(["NORTH", "SOUTH", "EAST", "WEST", "EAST", "WEST"]), [])

Thinking

想法(1): 這邊的想法要稍微想一下，如果是南北、東西互相抵銷的時候必須不能顯示，這就會先要一開始定義然後去比比對了。
想法(2): 比對宣告的陣列中，如果進來的值對應到相同的，必須被移除在陣列中，沒有的話，則會被推進去。

https://ithelp.ithome.com.tw/upload/images/20200930/20120826EqNRv3mPkX.jpg
圖片來源：Unsplash Aleks Marinkovic

Hint & Reference

Solution

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Solution 1
OPPOSITE = {
  "NORTH" => "SOUTH",
  "SOUTH" => "NORTH",
  "EAST"  => "WEST",
  "WEST"  => "EAST"
}

def dirReduc(arr)
  result = []
  arr.each do |dir|
    OPPOSITE[dir] == result.last ? result.pop : result.push(dir)
  end
  result
end

Javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Solution 1
const OPPOSITE = {
  "NORTH": "SOUTH",
  "SOUTH": "NORTH",
  "EAST" : "WEST",
  "WEST" : "EAST",
}

function dirReduc(arr){
  return arr.reduce((result, item) => {
    if (OPPOSITE[item] === result[result.length - 1]) {
      result.pop();
    } else {
      result.push(item);
    }
    return result;
  }, []);
}

// Solution 2
const OPPOSITE = {
  "NORTH": "SOUTH",
  "SOUTH": "NORTH",
  "EAST" : "WEST",
  "WEST" : "EAST",
}

function dirReduc(arr){
  return arr.reduce((result, item) => {
    OPPOSITE[item] === result[result.length - 1] ? result.pop() : result.push(item)
    return result;
  }, []);
}