Directions Reduction

مساله:

روزی روزگاری، در مسیر قدیمی غرب کوهستانی وحشی…

… به مردی دستور داده شد که از نقطه ای به نقطه دیگر برود. مسیرها “شمال” ، “جنوب” ، “غرب” ، “شرق” بود. واضح است که “شمال” و “جنوب” در مقابل، “غرب” و “شرق” نیز در مقابل هم قرار دارند.

رفتن به یک جهت و برگشتن بلافاصله جهت مخالف، تلاشی بی مورد است. از آنجا که این غرب وحشی است، با آب و هوای وحشتناک و نداشتن آب زیاد، مهم است که در انرژی خود صرفه جویی کنید، در غیر این صورت ممکن است از تشنگی بمیرید!

چطوری از راه بیابانی کوهستان با هوشمندی عبور کنیم؟

جهت هایی که به مرد داده می شود، به عنوان مثال، موارد زیر است (بسته به زبان):

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"].
or
{ "NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST" };
or
[North, South, South, East, West, North, West]

سریع می توانید ببینید که رفتن به “شمال” و بلافاصله “جنوب” معقول نیست، بهتر است در همان مکان بمانید! بنابراین وظیفه این است که یک نسخه ساده از طرح را به مرد ارائه دهیم. یک برنامه بهتر در این مورد به سادگی این است:

["WEST"]
or
{ "WEST" }
or
[West]

نمونه های دیگر:

در [“شمال” ، “جنوب” ، “شرق” ، “غرب”]، جهت “شمال” + “جنوب” در حال رفتن به شمال است و بلافاصله باز می گردد. مسیر تبدیل [“شرق” ، “غرب”] “شرق” و “غرب” یکدیگر را از بین می برند، بنابراین نتیجه نهایی [] است(در Clojure صفر است).

وظیفه:

تابع dirReduc را طوری بنویسید که آرایه ای از رشته را از شما بگیرد و آرایه ای از رشته ها که مسیرهای غیرمناسب هست را حذف کرده باشد

Description:

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 mountainous desert the smart way.

The directions given to the man are, for example, the following (depending on the language):

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"].
or
{ "NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST" };
or
[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:

["WEST"]
or
{ "WEST" }
or
[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”].

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, East, West, South}.

See more examples in “Sample Tests:”

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

if you want to translate, please ask before translating.

راه حل ها:

import java.util.Stack;

public class DirReduction {
    public static String[] dirReduc(String[] arr) {
        final Stack<String> stack = new Stack<>();

        for (final String direction : arr) {
            final String lastElement = stack.size() > 0 ? stack.lastElement() : null;

            switch(direction) {
                case "NORTH": if ("SOUTH".equals(lastElement)) { stack.pop(); } else { stack.push(direction); } break;
                case "SOUTH": if ("NORTH".equals(lastElement)) { stack.pop(); } else { stack.push(direction); } break;
                case "EAST":  if ("WEST".equals(lastElement)) { stack.pop(); } else { stack.push(direction); } break;
                case "WEST":  if ("EAST".equals(lastElement)) { stack.pop(); } else { stack.push(direction); } break;
            }
        }
        return stack.stream().toArray(String[]::new);
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DirReduction {
    public static String[] dirReduc(String[] arr) {
      List<String> dirs = new ArrayList<String>(Arrays.asList(arr));
      for (int i = 0; i + 1 < dirs.size(); i++) {
        if ("NORTHSOUTH,SOUTHNORTH,EASTWEST,WESTEAST".contains(dirs.get(i) + dirs.get(i + 1))) {
          dirs.remove(i + 1);
          dirs.remove(i);
          i = -1;
        }
      }
      return dirs.toArray(new String[dirs.size()]);
    }
}

import java.util.Stack;

public class DirReduction {
  public static String[] dirReduc(String[] arr) {
        Stack<String> dist = new Stack<String>();
        
        for (String i: arr) 
          if (dist.isEmpty() || !getOpposite(dist.lastElement()).equals(i))
             dist.push(i);
          else dist.pop(); 
        return dist.toArray(new String[]{});
    }
  
  private static String getOpposite(String str){
    switch (str){
      case "NORTH": return "SOUTH";
      case "SOUTH": return "NORTH";
      case "EAST": return "WEST";
      case "WEST": return "EAST";
    }
    return null;
  }
}

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Map;
import java.util.HashMap;

public class DirReduction {

  private static final Map<String, Integer> dirs = new HashMap<>();
  static {
    dirs.put("NORTH", 1);
    dirs.put("SOUTH", -1);
    dirs.put("EAST", 2);
    dirs.put("WEST", -2);
  }
  
  public static String[] dirReduc(String[] a) {
    Deque<String> list = new ArrayDeque<>();
    for (String d: a) {
      Integer c = dirs.get(d);
      Integer p = dirs.get(list.peekLast());
      if (p == null || p + c != 0) list.addLast(d);
      else list.removeLast();
    }
    return list.toArray(new String[list.size()]);
  }
}