06. Snakes

using System;
using System.Collections.Generic;

static class Snakes
{
    private static List<char> listOfDirections = new List<char> { 'R', 'D', 'L', 'U' };
    private static Dictionary<char, int> directionNumber = new Dictionary<char, int>() { { 'R', 0 }, { 'D', 1 }, { 'L', 2 }, { 'U', 3 } };
    private static List<Tuple<int, int>> snakePath = new List<Tuple<int, int>>();
    private static HashSet<string> snakesFound = new HashSet<string>();
    private static int snakesCount = 0;
    private static int snakeLength;
    static void Main()
    {
        snakeLength = int.Parse(Console.ReadLine());

        //For all values of n, the first combination is SRR...RR, so this snake is the starting point
        char[] currentSnake = ('S' + new string('R', snakeLength - 1)).ToCharArray();
        snakePath = InitiateSnakePath(snakeLength);
        AddSnake(currentSnake);
        Console.WriteLine(String.Join("", currentSnake));
        //PrintSnake(currentSnake);
        for (int i = snakeLength - 1; i > 1; i--)
        {
            currentSnake[i] = ' ';
            snakePath.RemoveAt(snakePath.Count - 1);
            //To eliminate redundent combinations all  branches are generated downwards
            ForkSnake(currentSnake, new List<char> { 'D' }, i);
        }
        Console.WriteLine("Snakes count = {0}", snakesCount);

    }

    private static char IncrementDirection(char rotation, int increment = 1)
    {
        return listOfDirections[(directionNumber[rotation] + increment) % listOfDirections.Count];
    }

    private static char ReverseDirection(char direction)
    {
        return listOfDirections[(directionNumber[direction] + 2) % 4];
    }

    private static List<char> RemoveDirection(char directionForRemoval)
     //This method can limit the directioins in which the snake will expand
    {
        List<char> result = new List<char> { 'R', 'D', 'L', 'U' };
        result.Remove(directionForRemoval);
        return result;
    }

    private static void ForkSnake(char[] snake, List<char> availableDirections, int startposition)
        // The main method for generating the snake
    {
        if (startposition == snake.Length)
        {
            if (!snakesFound.Contains(new string(snake)))
            {
                AddSnake(snake);
                Console.WriteLine(String.Join("", snake));
                //PrintSnake(snake);
            }
        }
        else
        {
            foreach (char direction in availableDirections)
            {
                snakePath.Add(GetNewCoordinates(snakePath[startposition - 1], direction));
                if (IsPathAvailable(ref snakePath))
                {
                    snake[startposition] = direction;
                    //The snake is restricted from expanding to the originating position
                    ForkSnake(snake, RemoveDirection(ReverseDirection(direction)), startposition + 1);
                    snake[startposition] = ' ';
                    snakePath.RemoveAt(snakePath.Count - 1);
                }
                else snakePath.RemoveAt(snakePath.Count - 1);
            }
        }
    }

    private static List<Tuple<int, int>> InitiateSnakePath(int length)
    {
        var result = new List<Tuple<int, int>>();
        for (int i = 0; i < length; i++)
        {
            result.Add(new Tuple<int, int>(0, i));
        }
        return result;
    }

    private static Tuple<int, int> GetNewCoordinates(Tuple<int, int> coordinates, char direction)
    {
        int[] result = new int[2] { coordinates.Item1, coordinates.Item2 };
        switch (direction)
        {
            case 'R':
                result[1]++;
                break;
            case 'D':
                result[0]++;
                break;
            case 'L':
                result[1]--;
                break;
            case 'U':
                result[0]--;
                break;
        }
        return new Tuple<int, int>(result[0], result[1]);
    }

    private static bool IsPathAvailable(ref List<Tuple<int, int>> path)
        //Ensures that the snake will not cross itself
    {
        for (int i = 0; i < path.Count - 1; i++)
        {
            if (Tuple.Equals(path[i], path[path.Count - 1]))
                return false;
        }
        return true;
    }

    private static void AddSnake(char[] snake)
        //Generate all required variations of the snake and adds them to the HashSet with forbidden combinations
    {
        char[] flippedSnake = FlipSnake(snake);
        char[] reversedSnake = ReverseSnake(snake);
        string[] storedChecks = new string[8];

        snakesCount++;

        storedChecks[0] = new string(flippedSnake);
        storedChecks[1] = new string(RotateSnake(flippedSnake, 1));
        storedChecks[2] = new string(RotateSnake(flippedSnake, 2));
        storedChecks[3] = new string(RotateSnake(flippedSnake, 3));
        storedChecks[4] = new string(reversedSnake);
        storedChecks[5] = new string(RotateSnake(reversedSnake, 1));
        storedChecks[6] = new string(RotateSnake(reversedSnake, 2));
        storedChecks[7] = new string(RotateSnake(reversedSnake, 3));
        //All combinations which start in a direction other than 'R' can be safely discarded
        foreach (string check in storedChecks)
            if (check[1] == 'R') snakesFound.Add(check);
    }

    private static char[] RotateSnake(char[] snake, int rotation)
    {
        // rotation:
        // 1 = 90 degrees
        // 2 = 180 degrees
        // 3 = 270 degrees
        char[] result = new char[snake.Length];
        result[0] = 'S';
        for (int i = 1; i < snake.Length; i++)
        {
            result[i] = IncrementDirection(snake[i], rotation);
        }
        return result;
    }
    private static char[] FlipSnake(char[] snake)
        //Mirrors the snake horizontally
    {
        char[] result = new char[snakeLength];
        result[0] = 'S';
        for (int i = 1; i < snake.Length; i++)
        {
            if (snake[i] == 'L') result[snakeLength - i] = 'R';
            else if (snake[i] == 'R') result[snakeLength - i] = 'L';
            else result[snakeLength - i] = snake[i];

        }
        return result;
    }

    private static char[] ReverseSnake( char[] snake)
        //
    {
        char[] result = new char[snakeLength];
        result[0] = 'S';
        for (int i = 1; i < snake.Length; i++)
            result[snakeLength - i] = snake[i];
        return result;
    }

    private static void PrintSnake(char[] snake)
    //This can be used to visualize the snakes
    {
        char[,] matrix = new char[snake.Length * 2, snake.Length * 2];
        int x = snake.Length;
        int y = snake.Length;
        foreach (char character in snake)
        {
            switch (character)
            {
                case 'R':
                    x++;
                    break;
                case 'D':
                    y++;
                    break;
                case 'L':
                    x--;
                    break;
                case 'U':
                    y--;
                    break;
            }
            matrix[x, y] = '#';
        }
        Console.WriteLine();

        for (y = 0; y < snake.Length * 2; y++)
        {
            for (x = 0; x < snake.Length * 2; x++)
            {
                Console.Write(matrix[x, y]);
            }
            Console.WriteLine();
        }
    }
}