using System;
using System.Drawing;
using System.Linq;
using System.Collections.Generic;

namespace Dungeon
{
    public class DungeonTask
    {
        public static MoveDirection[] FindShortestPath(Map map)
        {
            var start = map.InitialPosition;
            var exit = map.Exit;
            var chests = map.Chests;

            // если нет сундуков
            var wayNoChest = BfsTask.FindPaths(map, start, new Point[] { exit }).FirstOrDefault();
            if (wayNoChest == null) return new MoveDirection[0];
            // пути от старта и конца
            var wayFromStart = BfsTask.FindPaths(map, start, chests);
            var wayFromExit = BfsTask.FindPaths(map, exit, chests).DefaultIfEmpty();

            var pathToExit = wayNoChest.ToList();
            pathToExit.Reverse();
            if (chests.Any(c => pathToExit.Contains(c)) || wayFromStart.FirstOrDefault() == null)
                return pathToExit.Zip(pathToExit.Skip(1), MoveTo).ToArray();

            return CalculatePath(wayFromStart, wayFromExit);
        }

        private static MoveDirection[] CalculatePath(
            IEnumerable<SinglyLinkedList<Point>> start,
            IEnumerable<SinglyLinkedList<Point>> end)
        {
            var wayStartToExit = start.Join(end, e => e.Value, s => s.Value, (e, s) => new {
                Length = e.Length + s.Length,
                listFinish = e.ToList(),
                listStart = s.ToList()
            });

            var pathList = wayStartToExit
                .OrderBy(l => l.Length)
                .Select(p => Tuple.Create(p.listFinish, p.listStart))
                .First();
            pathList.Item1.Reverse();
            pathList.Item1.AddRange(pathList.Item2.Skip(1));
            return pathList.Item1.Zip(pathList.Item1.Skip(1), MoveTo).ToArray();
        }

        private static MoveDirection MoveTo(Point start, Point finish)
        {
            var d = new Point(finish.X - start.X, finish.Y - start.Y);
            if (d.X == -1) return MoveDirection.Left;
            else if (d.X == 1) return MoveDirection.Right;
            else if (d.Y == 1) return MoveDirection.Down;
            return MoveDirection.Up;
        }
    }
}