using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;

namespace MazePathfinder {
    #region toolClasses
    class Pos
    {
        public int X { get; set; }
        public int Y { get; set; }

        public Pos(int x, int y)
        {
            X = x;
            Y = y;
        }
    }

    class Explorer
    {
        public static List<Pos> AllHistory { get; set; } //collection of all positions in maze explored by any Explorer object

        public static bool BeenExplored(Pos p)
        {
            return AllHistory.Any(h => h.X == p.X && h.Y == p.Y);
        }

        public Pos Position { get; private set; }
        public List<Pos> Path { get; private set; } //the path that this explorer object has traversed

        public Explorer(int x, int y)
        {
            Position = new Pos(x, y);
            Path = new List<Pos>();
            Path.Add(Position);

            if (Explorer.AllHistory == null)
            {
                Explorer.AllHistory = new List<Pos>();
            }

            if (!Explorer.BeenExplored(Position)) {
                Explorer.AllHistory.Add(Position);
            }
        }

        public Explorer newPosition(int x, int y)
        {
            Explorer newEx = new Explorer(x, y);
            newEx.Path = Path.ToList();
            if (!newEx.Path.Any(p => p.X == Position.X && p.Y == Position.Y)) {
                newEx.Path.Add(Position);
            }

            if (!Explorer.BeenExplored(Position)) {
                Explorer.AllHistory.Add(Position);
            }

            return newEx;
        }
    }
    #endregion toolClasses

    internal class Program
    {

        private static void Main(string[] args) {
            char[,] mazeTxt = getMapFromFile();

            string waypoints = "01234567";

            Pos start = new Pos(-1, -1);

            for (int y = 0; y < mazeTxt.GetLength(1); y++) {
                for (int x = 0; x < mazeTxt.GetLength(0); x++) {
                    if (mazeTxt[x, y] == waypoints[0]) {
                        start = new Pos(x, y);
                    }
                }
            }

            if (start.X == -1 || start.Y == -1)
            {
                throw new Exception("Start not found");
            }


            int totalPath = 0;

            for (int w = 1; w < waypoints.Length; w++) {

                Explorer reachedPoint = explore(start, waypoints[w], mazeTxt);

                displayCompleted(reachedPoint, (char[,])mazeTxt.Clone(), waypoints);

                Console.WriteLine("");

                start = reachedPoint.Position;

                int steps = reachedPoint.Path.Count() - 1;

                totalPath += steps;

                Explorer.AllHistory.Clear();

                Console.WriteLine("Steps this leg: " + steps);

                Console.WriteLine("Total steps: " + totalPath.ToString());

                Console.ReadLine();
            }

            Console.WriteLine("Complete");

            Console.ReadLine();
        }


        private static char[,] getMapFromFile() {
            string[] file = System.IO.File.ReadAllLines("maze.txt");

            int txtWidth = file.Max(l => l.Trim().Length);
            int txtHeight = file.Length;

            char[,] mazeTxt = new char[txtWidth, txtHeight];

            Pos start = new Pos(-1, -1);

            for (int l = 0; l < file.Length; l++) //convert maze file to a 2-dimensional char array
            {
                char[] line = file[l].ToCharArray();
                for (int c = 0; c < line.Length; c++) {
                    mazeTxt[c, l] = line[c];
                }
            }

            return mazeTxt;
        }

        private static Explorer explore(Pos Start, char End, char[,] mazeTxt) {
            List<Explorer> explorerList = new List<Explorer>() { new Explorer(Start.X, Start.Y) };
            //will hold a list of Explorer objects representing one generation of the exploration

            Explorer reachedFinish = null; //will hold the Explorer object that reaches the exit



            while (reachedFinish == null) {
                List<Explorer> newExplorerList = new List<Explorer>();

                foreach (Explorer explorer in explorerList) //go through each explorer in the list
                {
                    Pos thisRoom = explorer.Position;

                    if (mazeTxt[thisRoom.X, thisRoom.Y] == End) //make sure we haven't reached the exit
                    {
                        reachedFinish = explorer;
                        break;
                    } else {
                        foreach (
                            Pos direction in
                                new List<Pos>() //check the four cardinal directions around the current position
                                {
                                    new Pos(thisRoom.X + 1, thisRoom.Y),
                                    new Pos(thisRoom.X - 1, thisRoom.Y),
                                    new Pos(thisRoom.X, thisRoom.Y + 1),
                                    new Pos(thisRoom.X, thisRoom.Y - 1)
                                }) {
                            if (mazeTxt[direction.X, direction.Y] != '#' &&
                                !Explorer.BeenExplored(direction))
                            //if the searched direction isn't a wall or a location that has allready been explored...
                            {
                                newExplorerList.Add(explorer.newPosition(direction.X, direction.Y));
                                //...generate a new Explorer object for that position and add it to the list for the next generation.
                            }
                        }
                    }
                }

                explorerList = newExplorerList;

                if (!explorerList.Any() && reachedFinish == null) {
                    throw new Exception("No path to exit");
                }

            }

            return reachedFinish;
        }




        private static void displayCompleted(Explorer reachedFinish, char[,] mazeTxt, string waypoints) {
            for (int x = 0; x < reachedFinish.Path.Count(); x++)
            //once an Explorer has found the exit, go through the path it took and write it to the maze array
            {
                Pos pos = reachedFinish.Path[x];
                Pos lastPos = (x == 0 ? pos : reachedFinish.Path[x - 1]);
                Pos nextPos = (x == reachedFinish.Path.Count() - 1 ? pos : reachedFinish.Path[x + 1]);

                if (!waypoints.Contains(mazeTxt[pos.X, pos.Y])) //fancy path graphics
                {
                    if ((lastPos.X > nextPos.X && lastPos.Y > nextPos.Y && lastPos.Y == pos.Y) ||
                        (lastPos.X < nextPos.X && lastPos.Y < nextPos.Y && lastPos.X == pos.X))
                        mazeTxt[pos.X, pos.Y] = '└';
                    else if ((lastPos.X > nextPos.X && lastPos.Y > nextPos.Y && lastPos.X == pos.X) ||
                             (lastPos.X < nextPos.X && lastPos.Y < nextPos.Y && lastPos.Y == pos.Y))
                        mazeTxt[pos.X, pos.Y] = '┐';
                    else if ((lastPos.X > nextPos.X && lastPos.Y < nextPos.Y && lastPos.Y == pos.Y) ||
                             (lastPos.X < nextPos.X && lastPos.Y > nextPos.Y && lastPos.X == pos.X))
                        mazeTxt[pos.X, pos.Y] = '┌';
                    else if ((lastPos.X > nextPos.X && lastPos.Y < nextPos.Y && lastPos.X == pos.X) ||
                             (lastPos.X < nextPos.X && lastPos.Y > nextPos.Y && lastPos.Y == pos.Y))
                        mazeTxt[pos.X, pos.Y] = '┘';
                    else if (lastPos.X == pos.X)
                        mazeTxt[pos.X, pos.Y] = '│';
                    else if (lastPos.Y == pos.Y)
                        mazeTxt[pos.X, pos.Y] = '─';
                }
            }


            Console.ForegroundColor = ConsoleColor.Gray;


            int width = mazeTxt.GetLength(1);
            int height = mazeTxt.GetLength(0);

            for (int y = 0; y < width; y++) {
                string line = "";
                for (int x = 0; x < height; x++) {
                        ConsoleColor color;

                        if (mazeTxt[x, y] == '#')
                            color = ConsoleColor.Gray;
                        else if (waypoints.Contains(mazeTxt[x, y]))
                            color = ConsoleColor.Red;
                        else
                            color = ConsoleColor.Yellow;

                        Console.ForegroundColor = color;
                        Console.Write(mazeTxt[x, y]);
                        Console.ForegroundColor = ConsoleColor.Gray;

                }
                Console.Write(Environment.NewLine);
            }

        }
    }
}