從列表中刪除多餘的移動

Question

假設您有一個從起點到終點的方向列表。什麼是消除多餘運動的有效方法？是否有可能不需要在二維數組中繪製出整個運動？

I.e.如果通過方向列表繼續前進的兩個位置彼此相鄰，則可以移除兩個位置之間的所有移動（如果位置之間存在間隙則不能縮短）。例如。 ...南，東，北...可簡寫爲...東...但是...南，東，東，北...無法縮短。

enum Dir 
    { 
     North, 
     South, 
     East, 
     West 
    }; 

Answer 1

enum Dir 
{ 
    North, South, East, West 
} 


static class RedundancyRemover { 

    internal static IList<Dir> RemoveRedundancy(IEnumerable<Dir> listOriginal)  { 

     List<LinkedListNode<Dir>>[] nodeHistory = new List<LinkedListNode<Dir>>[4]; 
     for (int i = 0; i < 4; i++) 
      nodeHistory[i] = new List<LinkedListNode<Dir>>(); 

     LinkedList<Dir> list = new LinkedList<Dir>(listOriginal); 
     LinkedListNode<Dir> curNode = list.First; 

     while (curNode != null) { 
      var curDirInd = (int) curNode.Value; 
      var nextNode = curNode.Next; 

      var oppHistory = nodeHistory[curDirInd^1]; 
      int oppHistCount = oppHistory.Count; 

      if (oppHistCount > 0) { 
       // Has pair - remove this node with its pair 
       list.Remove(curNode); 
       list.Remove(oppHistory[--oppHistCount]); 
       oppHistory.RemoveAt(oppHistCount); 
      } 
      else 
       nodeHistory[curDirInd].Add(curNode); 

      curNode = nextNode; 
     } 

     return list.ToArray(); 

    } 



} 

Answer 2

更簡單的方法：只計算每個方向：

enum Dir 
{ 
    North, South, East, West 
} 

static class RedundancyRemover 
{ 

    static IList<Dir> RemoveRedundancy(IList<Dir> list) { 
     int[] occurenceCount = new int[4]; 

     foreach (var dir in list) occurenceCount[(int)dir]++; 

     var newList = new List<Dir>(); 

     for (int i=0; i<4; i+=2) { 
      int v1 = occurenceCount[i]; 
      int v2 = occurenceCount[i+1]; 
      if (v1 > v2) 
       repeat(newList, (Dir)i, v1 - v2); 
      else 
      if (v1 < v2) 
       repeat(newList, (Dir)(i + 1), v2 - v1); 

     } 

     return newList; 

    } 

    private static void repeat(IList<Dir> list, Dir dir, int count) { 
     while (--count >= 0) list.Add(dir); 
    } 

}