Day24.cs

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

namespace AdventOfCode2016
{
    class Day24 : Day
    {
        public dynamic Input
        {
            get
            {
                return @"#######################################################################################################################################################################################
#.....................#.....#.#.......#.......#...#.....#.#...#.........#...........#...#.........#...#...#...#...#.........#.#.....#.........#.#.#.....#.....#.....#.#.#.............#
#.#.###.#.###.#.###.#.#.###.#.###.#########.#.#####.#####.#.###.#.#.#.#.###.#.###.#.#.#.#.###.#.#.#.#.###.#.#.#.#.###.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#####.###.#.#.#.#.#.###.#.#.#.#.#.#
#.........#.......#...#.....#.#.#.#.......#.#.....#...#.....#.....#.....#...............#.#.#...#...#.#.....#.......#.#...#.....#.......#...#.#.#...#2#...#.................#...#.....#
#.###.#.###.#.#.#.#.#.#.#.#.#.#.#.#####.#.#.#.###.#.###.#.#.#.###.#.#.#.###.#.#.###.#.#####.#.#.#####.#.#.#.#######.#.#####.###.###.###.#.#.#.#.#.#.#.#.###.###.###.###.#.#.#.#.#######
#.#....1#.....#...#.......#...#.#.#.....#.....#.....................#.#...........#...#.....#.....#.....#.......#.....#.#.......#...........#...#.#...#...#...............#.#.#.#.....#
#.#.#######.#.#.#.#.#############.#.###.###.###.#.#.#########.#.###.#.#.#.#.#.#.#.#####.#.#.#.###.#.#.#.#.#.#.#.#.#.###.#########.#.#.#############.#######.#.#.#.###.###.###.#####.###
#.#.#...#.........#.....#.........#.....#.#.#...#...........#...#.........#...#.#.....#.#...............#...#.....#.#.#.............#.....#...#.....#...........#.#.#.....#...#.......#
#.###.#.#.#.#.#######.#.#.#.#.###.###.#.#.#.#.#.#.#.#####.###.#.#.#.#.#.#######.#.###.#.#.#.###.#.###.#.#.###.#.#.#.#.#.#.#.#.#.#######.#.###.#.###.#.###.#.#.###.#.###.#.#.#.#.#.#.###
#...#.#.........#.#...#.....#...#.......#.#.#.......#.#.#...#.........#.....#.#...#.#.#...#...#...#.....#.........#.#.....#.......#.....#.......#.#...#...#.....#.....#.......#.#.#...#
#.#.#.#.#.#.###.#.#.#.#.###.#####.#####.#######.#.###.#.#.#.#####.#.#####.###.#.#.#.#.#.#.###.#.#.#.#####.#.#####.#.###.#####.#.#.#.###.###.###.#.#.#.#####.#.#.#####.#.#######.#.#.###
#.....#.#.....#.........#.#...#.......#...#.......#.........#...#.#.#.#.......#...#...............#.#...................#.#.#.......#.#.........#....0#...#.#.......#.#.#.#...#.....#.#
#######.#.#.#.#######.###.#.###.#.#.#.#.#.#.#.#.###.###.#####.#.#.###.#.#.###.#####.#.#.#.#.#####.#.###.###.#.#.#######.#.#.#.#######.#.#.#.#.#.#.#.#.#.###.#.###.#.###.#.#####.#.#.#.#
#.........#...#...#.....#.........#.......#...#...........#.#.#.#...#...#.#...#.#...#.#.#.......#.......#...#.....#.....#.#...#.#.#.#.........#...............#...#.#...........#.....#
#.#.#.#.#.#####.###.#####.#.#######.#.#.#.#.#.#.#.#####.###.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.###.#.###.#.###.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#####.###.###.#.#######.#.###.#.#######
#.#...#...#...#.....#.#.#.#...#.................#...#...#.#...#...#...#.#.#.#.....#.#.#.....#.#...#.#.......#.#.#...#...#.#...#.....#...#.#...#...#.....#.....#...#.....#.....#.#...#.#
#.###.###.###.###.#.#.#.#.#.#.#.#.#.###.#.###.#####.#.###.#.###.###.#.#.#.#.#.###.#.###.#####.###.###.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.###.#####.#.###########.#.#.#.###.#.#######.#.#.#
#..3#.#.......#...#.............#.....#.....#...#...#.#.....#.......#.....#...#.....#.#.#.........#...#.#.........#.....#...............#.........#...#...........#.#.#...#7#.#.....#.#
###.#.#.###.#.#.###.#############.###.#.#######.#.#####.#######.#####.#.###.#.#.#.#.#.#.#.#.#.#.#.###.#.#########.#.#.#.#.#.#.###.#.###.#####.#####.###.#.###.#.#.#.#.#.#.#.#.#.###.#.#
#.#...#.....#.#.#.#.#.#...........................#.......#...#.#.....#.#...#...#.#...#.........#...........#.#.....#.....#...#...#.#.......#.#.#...#...#.#.......#.......#...#.....#.#
#.#########.#.#.#.#.#.#.#.#####.###.#######.#.#####.#.#.#.#.###.#.#.#.#.#####.#######.#.#####.#.#.#.#####.#.#.#.###.#####.#.#######.#######.###.###.#.#.#.###.###.#.#########.#.#.###.#
#.#.......#...#.....#.#.......#.#...#.....#...........#.#...........#...#.....#.........#.......#...#.........#.#.....#.#...#.............#.............#...........#.....#...#.#.#.#.#
#.#.###.#.#.#.#.#.###.###.#####.#.#.#.#.#.###.#.#####.#.#.#.#.###.#####.#######.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#.#.#.#.#.###.#.###.#.###.#######.###.#.#.#.#.###.###.#.#.#.#.#.#.#.###
#.#.......................#.......#.......#.#.#.......#...........#...#...#.....#.#.#...#...#...#.......#.......#.#.#...#.....#.....#...#...#.....#.#...#...#...........#.....#...#...#
#.#.###.#####.#.###.#.#.###.#.#.#.#######.#.#####.#.#.###.#.#######.#.#.#.#.#.#.###.#.#.#.#.#.#.#.###.#.###.#.###.###.#######.#.###.###.#.#.#.###.#.###.###.###.#.#.#.#.#.#.#.#.###.#.#
#...#.....#.........#...#.#.....#...#...#.#.#...#.....#.#.#...#.......#.....#.......#.....#.....#.#.....#...#.#.#.......#...#.#...#.........#...#...........#...#...#...#.....#.#.#.#.#
#########.###.#####.#.#.#.#.#.###.#.#.###.#.#.#.#.###.#.#.#.#.#.#.###.#.###.#.#####.#######.#.###.#.###.#.#.###.#.#.#####.#######.#.###.#.###.###.#.###.#.#.#.###.#.#######.#.###.#.#.#
#.#...#...#...#.....#...#.#6......#.#.....#.....#.....#.#...#...#...#.#.....#...#...#...#...#.............#.#...#.......#.#...#...........#.#..5#...#.#.....#...#.....#...#...#.......#
#.###.#.#.###.###.#.#.#.#.#####.#.#.#####.#.#.###.#.#.#.#.#.#.###.#.#.###.#.#########.###.###.#######.#.#.#.#.#.#.#####.#.#.#.#.#.###.#.###.#####.#.#.#.#.#.#.#.###.#.###.#.###.#.#.#.#
#.#...#...#...#.........#...#.................#.....#.....#...............#.....#.#...#.....#.......#...#.....#.#.#.......#.............#.#.#.#...#.#...#.#.#...#.....#.......#.......#
#.###.#.###.###.###.#.#.#.#.#.###.###.#.#.###.###.###############.#####.#.#######.#.#.#.###########.###.#.#.#.#.#.#.#.###.#.#####.#######.###.#.#.#.#.###.#.#.#.#.###.###.###.#.#.###.#
#...................#...........#.#.#.........#.....#...#...#...#.#.....#.........#...#.#.......#...#...............#.#.................#.....#.....#.#.....#...#...#.#.....#...#.....#
#.#.#.#.#.###.###.#.###.#.#####.#.#.#########.#.#.###.#.###.#####.#.#.#.#.#.#.#######.#####.#.#.#.###.#.#.###.#####.#.#.#.###.###.###.###.#######.#.#.#.###.#.#.#.#.#.#.#.###.#.#.###.#
#.#...#.#.#.#.......#.#...#.#.....#.......#.#.#.....#.#.#.......#...#.#.....#.#...#...#.........#.......#.....#.#...#...#.......#.#...#...#.#.........#...#.........#.........#.#.#...#
###.#####.#.#.###.#.#.#.###.#.#.#.#.#.#.#.#.#.#####.###.#.###.#.#.#.#.#.#.#.#######.#.###.#.#####.###.#####.###.#.#.###.#.#.#.###.#.###.#.#.#.#.#####.#.#####.###.#.#.#.###.#####.#.#.#
#...........#...................#.....#.....#...............#...#.#.....#.......#...#...#...#...#.......#...#...#.....#...#...#...#.....#4#...#...#...#.....#.............#.#...#.....#
#######################################################################################################################################################################################";
            }
        }

        public string Part1(dynamic input)
        {
            return FindRoute(input, false);
        }

        public string FindRoute(string input, bool returnToStart)
        { 
            var map = ParseMap((string)input);
            var target = map.Count(n => n.ID.HasValue);
            var start = map.Where(n => n.ID == 0).First();

            var targets = new List<Node>();
            List<Node> best = null;

            for (int i = 1; i < target; i++)
            {
                targets.Add(map.Where(n => n.ID == i).First());
            }

            enumerateTargets(targets, new List<Node>() { start }, ref best, returnToStart);

            return (best.Count - 1).ToString();

        }

        private void enumerateTargets(List<Node> targets, List<Node> route, ref List<Node> best, bool returnToStart)
        {
            var lastNode = route.Last();

            foreach (var n in targets)
            {
                var extendedRoute = new List<Node>(route);
                var newtargets = new List<Node>(targets);
                newtargets.Remove(n);
                extendedRoute.AddRange(shortestRoute(lastNode, n));

                if (newtargets.Count == 0)
                {
                    if (returnToStart)
                    {
                        extendedRoute.AddRange(shortestRoute(n, route[0]));
                    }
                    if (best == null || best.Count > extendedRoute.Count)
                    {
                        best = extendedRoute;
                    }
                }

                enumerateTargets(newtargets, extendedRoute, ref best, returnToStart);
            }
        }

        private Route extend(Route route, Queue<Route> queue)
        {
            var node = route.head;
            if (node.ID.HasValue)
            {
                route.target = route.target.Replace(node.ID.Value.ToString(), "");
                if (route.target.Length == 0)
                {
                    return route;
                }
            }

            foreach (Step step in node.steps)
            {
                if (route.steps.IndexOf("->" + step.from.x + "," + step.from.y + "->" + step.to.x + "," + step.to.y + "->") < 0)
                {
                    queue.Enqueue(route.extend(step));
                }
            }

            return null;
        }

        private List<Node> ParseMap(string input)
        {
            var lines = Utils.splitLines(input).ToList();
            int height = lines.Count();
            int width = lines[0].Length;

            var nodes = new Node[width, height];
            var ret = new List<Node>();

            for (int y = 0; y < height; y++)
            {
                for (int x = 0; x < width; x++)
                {
                    char c = lines[y][x];

                    if (c != '#')
                    {
                        var node = new Node();
                        var above = nodes[x, y - 1];
                        var left = nodes[x - 1, y];

                        if (above != null)
                        {
                            node.addStep(above);
                            above.addStep(node);
                        }
                        if (left != null)
                        {
                            node.addStep(left);
                            left.addStep(node);
                        }

                        if (c != '.')
                        {
                            node.ID = int.Parse(c.ToString());
                        }
                        node.x = x;
                        node.y = y;

                        nodes[x, y] = node;
                        ret.Add(node);
                    }
                }
            }

            return ret;

        }

        public string Part2(dynamic input)
        {
            return FindRoute(input, true);
        }

        public void Test()
        {
            Utils.Test(Part1,
@"###########
#0.1.....2#
#.#######.#
#4.......3#
###########", "14");
        }

        private Dictionary<Tuple<Node, Node>, List<Node>> routeCache = new Dictionary<Tuple<Node, Node>, List<Node>>();

        private List<Node> shortestRoute(Node start, Node finish)
        {
            var cacheKey = Tuple.Create(start, finish);

            if (routeCache.ContainsKey(cacheKey))
            {
                return routeCache[cacheKey];
            }

            var used = new Dictionary<Node, List<Node>>();
            var queue = new Queue<Node>();

            queue.Enqueue(start);
            used[start] = new List<Node>();

            bool found = false;

            while (queue.Count > 0 && !found)
            {
                var next = queue.Dequeue();
                found = extendFrom(next, finish, used, queue);
            }

            var route = used[finish];

            routeCache[cacheKey] = route;

            return route;
        }

        private bool extendFrom(Node next, Node target, Dictionary<Node, List<Node>> used, Queue<Node> queue)
        {
            foreach (var adjacent in next.steps)
            {
                if (!used.ContainsKey(adjacent.to))
                {
                    var route = new List<Node>(used[next]);
                    route.Add(adjacent.to);
                    used[adjacent.to] = route;

                    queue.Enqueue(adjacent.to);

                    if (next == target)
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        private class Node
        {
            public int? ID;
            internal List<Step> steps;
            public int x;
            public int y;

            public Node()
            {
                steps = new List<Step>();
            }

            internal void addStep(Node target)
            {
                steps.Add(new Step() { from = this, to = target });
            }

            public override string ToString()
            {
                return x + "," + y + (ID.HasValue ? "[" + ID + "]" : "");
            }
        }

        private class Route
        {
            internal string steps = "->";
            public Node head;
            public string target;

            public Route(Node start, int target)
            {
                this.head = start;
                this.steps += start.x + "," + start.y + "->";
                this.target = "";
                for (int i = 0; i < target; i++)
                {
                    this.target = this.target + i.ToString();
                }
            }

            private Route() { }

            internal Route extend(Step step)
            {
                var extended = new Route()
                {
                    steps = steps + step.to.x + "," + step.to.y + "->",
                    head = step.to,
                    target = target
                };
                return extended;
            }

            internal void print()
            {
                Console.WriteLine(steps);
            }
        }
        private struct Step
        {
            public Node from;
            public Node to;
        }
    }
}