SHARE
TWEET

Snakes

Filkolev Oct 2nd, 2015 (edited) 199 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. namespace Snakes
  2. {
  3.     using System;
  4.     using System.Collections.Generic;
  5.     using System.Linq;
  6.  
  7.     public class Snakes
  8.     {
  9.         private static int size;
  10.         private static int countOfSnakesFound;
  11.         private static HashSet<string> usedSnakes = new HashSet<string>();
  12.  
  13.         public static void Main(string[] args)
  14.         {
  15.             size = int.Parse(Console.ReadLine());
  16.  
  17.             // used to prevent snake from overlapping itself
  18.             Stack<Cell> snake = new Stack<Cell>();
  19.             List<char> directions = new List<char>();
  20.  
  21.             GenerateSnake(new Cell { Row = 0, Column = 0 }, 'S', snake, directions);
  22.  
  23.             Console.WriteLine("Snakes count = {0}", countOfSnakesFound);
  24.         }
  25.  
  26.         private static void GenerateSnake(Cell cell, char direction, Stack<Cell> snake, List<char> directions)
  27.         {
  28.             if (snake.Count == size)
  29.             {
  30.                 string currentSnake = new string(directions.ToArray());
  31.  
  32.                 if (!usedSnakes.Contains(currentSnake))
  33.                 {
  34.                     Console.WriteLine(currentSnake);
  35.                     countOfSnakesFound++;
  36.                     usedSnakes.Add(currentSnake);
  37.                     MarkIsomorphicSnakes(directions.ToList());
  38.                 }
  39.  
  40.                 return;
  41.             }
  42.  
  43.             if (snake.Contains(cell))
  44.             {
  45.                 return;
  46.             }
  47.  
  48.             snake.Push(cell);
  49.             directions.Add(direction);
  50.  
  51.             GenerateSnake(new Cell { Row = cell.Row, Column = cell.Column + 1 }, 'R', snake, directions);
  52.  
  53.             // First cell is fixed as 'R'; removes three branches of unneeded recursion
  54.             if (snake.Count > 1)
  55.             {
  56.                 GenerateSnake(new Cell { Row = cell.Row + 1, Column = cell.Column }, 'D', snake, directions);
  57.             }
  58.  
  59.             if (snake.Count > 2)
  60.             {
  61.                 GenerateSnake(new Cell { Row = cell.Row, Column = cell.Column - 1 }, 'L', snake, directions);
  62.             }
  63.  
  64.             if (snake.Count > 3)
  65.             {
  66.                 GenerateSnake(new Cell { Row = cell.Row - 1, Column = cell.Column }, 'U', snake, directions);
  67.             }
  68.  
  69.             snake.Pop();
  70.             directions.RemoveAt(directions.Count - 1);
  71.         }
  72.  
  73.         private static void MarkIsomorphicSnakes(List<char> directions)
  74.         {
  75.             FlipSnake(directions);
  76.             usedSnakes.Add(new string(directions.ToArray()));
  77.  
  78.             SwitchSnakeHeadAndTail(directions);
  79.             directions.Reverse();
  80.             while (directions[1] != 'R')
  81.             {
  82.                 RotateSnakeClockwise(directions);
  83.             }
  84.  
  85.             usedSnakes.Add(new string(directions.ToArray()));
  86.  
  87.             FlipSnake(directions);
  88.             usedSnakes.Add(new string(directions.ToArray()));
  89.         }
  90.  
  91.         private static void SwitchSnakeHeadAndTail(List<char> directions)
  92.         {
  93.             char tmp = directions[0];
  94.             directions.RemoveAt(0);
  95.             directions.Add(tmp);
  96.  
  97.             for (int index = 0; index < directions.Count; index++)
  98.             {
  99.                 switch (directions[index])
  100.                 {
  101.                     case 'U':
  102.                         directions[index] = 'D';
  103.                         break;
  104.                     case 'D':
  105.                         directions[index] = 'U';
  106.                         break;
  107.                     case 'R':
  108.                         directions[index] = 'L';
  109.                         break;
  110.                     case 'L':
  111.                         directions[index] = 'R';
  112.                         break;
  113.                 }
  114.             }
  115.         }
  116.  
  117.         private static void RotateSnakeClockwise(List<char> directions)
  118.         {
  119.             for (int index = 0; index < directions.Count; index++)
  120.             {
  121.                 switch (directions[index])
  122.                 {
  123.                     case 'U':
  124.                         directions[index] = 'R';
  125.                         break;
  126.                     case 'D':
  127.                         directions[index] = 'L';
  128.                         break;
  129.                     case 'R':
  130.                         directions[index] = 'D';
  131.                         break;
  132.                     case 'L':
  133.                         directions[index] = 'U';
  134.                         break;
  135.                 }
  136.             }
  137.         }
  138.  
  139.         private static void FlipSnake(List<char> directions)
  140.         {
  141.             for (int index = 0; index < directions.Count; index++)
  142.             {
  143.                 switch (directions[index])
  144.                 {
  145.                     case 'U':
  146.                         directions[index] = 'D';
  147.                         break;
  148.                     case 'D':
  149.                         directions[index] = 'U';
  150.                         break;
  151.                 }
  152.             }
  153.         }
  154.     }
  155.  
  156.     public struct Cell
  157.     {
  158.         public int Row { get; set; }
  159.  
  160.         public int Column { get; set; }
  161.     }
  162. }
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