SHARE
TWEET

06. Snakes

a guest Oct 2nd, 2015 113 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. static class Snakes
  5. {
  6.     private static List<char> listOfDirections = new List<char> { 'R', 'D', 'L', 'U' };
  7.     private static Dictionary<char, int> directionNumber = new Dictionary<char, int>() { { 'R', 0 }, { 'D', 1 }, { 'L', 2 }, { 'U', 3 } };
  8.     private static List<Tuple<int, int>> snakePath = new List<Tuple<int, int>>();
  9.     private static HashSet<string> snakesFound = new HashSet<string>();
  10.     private static int snakesCount = 0;
  11.     private static int snakeLength;
  12.     static void Main()
  13.     {
  14.         snakeLength = int.Parse(Console.ReadLine());
  15.  
  16.         //For all values of n, the first combination is SRR...RR, so this snake is the starting point
  17.         char[] currentSnake = ('S' + new string('R', snakeLength - 1)).ToCharArray();
  18.         snakePath = InitiateSnakePath(snakeLength);
  19.         AddSnake(currentSnake);
  20.         Console.WriteLine(String.Join("", currentSnake));
  21.         //PrintSnake(currentSnake);
  22.         for (int i = snakeLength - 1; i > 1; i--)
  23.         {
  24.             currentSnake[i] = ' ';
  25.             snakePath.RemoveAt(snakePath.Count - 1);
  26.             //To eliminate redundent combinations all  branches are generated downwards
  27.             ForkSnake(currentSnake, new List<char> { 'D' }, i);
  28.         }
  29.         Console.WriteLine("Snakes count = {0}", snakesCount);
  30.  
  31.     }
  32.  
  33.     private static char IncrementDirection(char rotation, int increment = 1)
  34.     {
  35.         return listOfDirections[(directionNumber[rotation] + increment) % listOfDirections.Count];
  36.     }
  37.  
  38.     private static char ReverseDirection(char direction)
  39.     {
  40.         return listOfDirections[(directionNumber[direction] + 2) % 4];
  41.     }
  42.  
  43.     private static List<char> RemoveDirection(char directionForRemoval)
  44.      //This method can limit the directioins in which the snake will expand
  45.     {
  46.         List<char> result = new List<char> { 'R', 'D', 'L', 'U' };
  47.         result.Remove(directionForRemoval);
  48.         return result;
  49.     }
  50.  
  51.     private static void ForkSnake(char[] snake, List<char> availableDirections, int startposition)
  52.         // The main method for generating the snake
  53.     {
  54.         if (startposition == snake.Length)
  55.         {
  56.             if (!snakesFound.Contains(new string(snake)))
  57.             {
  58.                 AddSnake(snake);
  59.                 Console.WriteLine(String.Join("", snake));
  60.                 //PrintSnake(snake);
  61.             }
  62.         }
  63.         else
  64.         {
  65.             foreach (char direction in availableDirections)
  66.             {
  67.                 snakePath.Add(GetNewCoordinates(snakePath[startposition - 1], direction));
  68.                 if (IsPathAvailable(ref snakePath))
  69.                 {
  70.                     snake[startposition] = direction;
  71.                     //The snake is restricted from expanding to the originating position
  72.                     ForkSnake(snake, RemoveDirection(ReverseDirection(direction)), startposition + 1);
  73.                     snake[startposition] = ' ';
  74.                     snakePath.RemoveAt(snakePath.Count - 1);
  75.                 }
  76.                 else snakePath.RemoveAt(snakePath.Count - 1);
  77.             }
  78.         }
  79.     }
  80.  
  81.     private static List<Tuple<int, int>> InitiateSnakePath(int length)
  82.     {
  83.         var result = new List<Tuple<int, int>>();
  84.         for (int i = 0; i < length; i++)
  85.         {
  86.             result.Add(new Tuple<int, int>(0, i));
  87.         }
  88.         return result;
  89.     }
  90.  
  91.     private static Tuple<int, int> GetNewCoordinates(Tuple<int, int> coordinates, char direction)
  92.     {
  93.         int[] result = new int[2] { coordinates.Item1, coordinates.Item2 };
  94.         switch (direction)
  95.         {
  96.             case 'R':
  97.                 result[1]++;
  98.                 break;
  99.             case 'D':
  100.                 result[0]++;
  101.                 break;
  102.             case 'L':
  103.                 result[1]--;
  104.                 break;
  105.             case 'U':
  106.                 result[0]--;
  107.                 break;
  108.         }
  109.         return new Tuple<int, int>(result[0], result[1]);
  110.     }
  111.  
  112.     private static bool IsPathAvailable(ref List<Tuple<int, int>> path)
  113.         //Ensures that the snake will not cross itself
  114.     {
  115.         for (int i = 0; i < path.Count - 1; i++)
  116.         {
  117.             if (Tuple.Equals(path[i], path[path.Count - 1]))
  118.                 return false;
  119.         }
  120.         return true;
  121.     }
  122.  
  123.     private static void AddSnake(char[] snake)
  124.         //Generate all required variations of the snake and adds them to the HashSet with forbidden combinations
  125.     {
  126.         char[] flippedSnake = FlipSnake(snake);
  127.         char[] reversedSnake = ReverseSnake(snake);
  128.         string[] storedChecks = new string[8];
  129.  
  130.         snakesCount++;
  131.  
  132.         storedChecks[0] = new string(flippedSnake);
  133.         storedChecks[1] = new string(RotateSnake(flippedSnake, 1));
  134.         storedChecks[2] = new string(RotateSnake(flippedSnake, 2));
  135.         storedChecks[3] = new string(RotateSnake(flippedSnake, 3));
  136.         storedChecks[4] = new string(reversedSnake);
  137.         storedChecks[5] = new string(RotateSnake(reversedSnake, 1));
  138.         storedChecks[6] = new string(RotateSnake(reversedSnake, 2));
  139.         storedChecks[7] = new string(RotateSnake(reversedSnake, 3));
  140.         //All combinations which start in a direction other than 'R' can be safely discarded
  141.         foreach (string check in storedChecks)
  142.             if (check[1] == 'R') snakesFound.Add(check);
  143.     }
  144.  
  145.     private static char[] RotateSnake(char[] snake, int rotation)
  146.     {
  147.         // rotation:
  148.         // 1 = 90 degrees
  149.         // 2 = 180 degrees
  150.         // 3 = 270 degrees
  151.         char[] result = new char[snake.Length];
  152.         result[0] = 'S';
  153.         for (int i = 1; i < snake.Length; i++)
  154.         {
  155.             result[i] = IncrementDirection(snake[i], rotation);
  156.         }
  157.         return result;
  158.     }
  159.     private static char[] FlipSnake(char[] snake)
  160.         //Mirrors the snake horizontally
  161.     {
  162.         char[] result = new char[snakeLength];
  163.         result[0] = 'S';
  164.         for (int i = 1; i < snake.Length; i++)
  165.         {
  166.             if (snake[i] == 'L') result[snakeLength - i] = 'R';
  167.             else if (snake[i] == 'R') result[snakeLength - i] = 'L';
  168.             else result[snakeLength - i] = snake[i];
  169.  
  170.         }
  171.         return result;
  172.     }
  173.  
  174.     private static char[] ReverseSnake( char[] snake)
  175.         //
  176.     {
  177.         char[] result = new char[snakeLength];
  178.         result[0] = 'S';
  179.         for (int i = 1; i < snake.Length; i++)
  180.             result[snakeLength - i] = snake[i];
  181.         return result;
  182.     }
  183.  
  184.     private static void PrintSnake(char[] snake)
  185.     //This can be used to visualize the snakes
  186.     {
  187.         char[,] matrix = new char[snake.Length * 2, snake.Length * 2];
  188.         int x = snake.Length;
  189.         int y = snake.Length;
  190.         foreach (char character in snake)
  191.         {
  192.             switch (character)
  193.             {
  194.                 case 'R':
  195.                     x++;
  196.                     break;
  197.                 case 'D':
  198.                     y++;
  199.                     break;
  200.                 case 'L':
  201.                     x--;
  202.                     break;
  203.                 case 'U':
  204.                     y--;
  205.                     break;
  206.             }
  207.             matrix[x, y] = '#';
  208.         }
  209.         Console.WriteLine();
  210.  
  211.         for (y = 0; y < snake.Length * 2; y++)
  212.         {
  213.             for (x = 0; x < snake.Length * 2; x++)
  214.             {
  215.                 Console.Write(matrix[x, y]);
  216.             }
  217.             Console.WriteLine();
  218.         }
  219.     }
  220. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top