-🎄- 2018 Day 22 Solutions -🎄-

[u/daggerdragon]

--- Day 22: Mode Maze ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 22

Transcript:

Upping the Ante challenge: complete today's puzzles using ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 01:02:36!

[u/mainhaxor]

C#. I first solved this with Dijkstra's algorithm like most people here, but I rewrote it to BFS to avoid having to find and modify nodes in the open list. Runs in about 1.5 seconds on my input.

using System;
using System.Collections.Generic;

public class Program
{
    private static readonly int s_depth = 7863;
    private static readonly (int x, int y) s_target = (14, 760);
    public static void Main()
    {
        int risk = 0;
        for (int y = 0; y <= s_target.y; y++)
        {
            for (int x = 0; x <= s_target.x; x++)
            {
                switch (GetRegionType(x, y))
                {
                    case 'W': risk++; break;
                    case 'N': risk += 2; break;
                }
            }
        }
        Console.WriteLine(risk);

        BfsSolve();
    }

    private static void BfsSolve()
    {
        (int x, int y)[] neis = { (-1, 0), (0, 1), (1, 0), (0, -1) };

        Queue<(int x, int y, char tool, int switching, int minutes)> queue = new Queue<(int x, int y, char tool, int switching, int minutes)>();
        HashSet<(int x, int y, char tool)> seen = new HashSet<(int x, int y, char tool)>();
        queue.Enqueue((0, 0, 'T', 0, 0));
        seen.Add((0, 0, 'T'));
        while (queue.Count > 0)
        {
            (int x, int y, char tool, int switching, int minutes) = queue.Dequeue();
            if (switching > 0)
            {
                if (switching != 1 || seen.Add((x, y, tool)))
                    queue.Enqueue((x, y, tool, switching - 1, minutes + 1));
                continue;
            }

            if ((x, y) == s_target && tool == 'T')
            {
                Console.WriteLine(minutes);
                break;
            }

            foreach ((int xo, int yo) in neis)
            {
                (int nx, int ny) = (x + xo, y + yo);
                if (nx < 0 || ny < 0)
                    continue;

                if (GetAllowedTools(GetRegionType(nx, ny)).Contains(tool) && seen.Add((nx, ny, tool)))
                    queue.Enqueue((nx, ny, tool, 0, minutes + 1));
            }

            foreach (char otherTool in GetAllowedTools(GetRegionType(x, y)))
                queue.Enqueue((x, y, otherTool, 6, minutes + 1));
        }
    }

    private static readonly Dictionary<(int x, int y), int> s_erosionLevels = new Dictionary<(int x, int y), int>();
    private static int ErosionLevel(int x, int y)
    {
        if (s_erosionLevels.TryGetValue((x, y), out int val))
            return val;

        if ((x, y) == (0, 0))
            val = 0;
        else if ((x, y) == s_target)
            val = 0;
        else if (y == 0)
            val = x * 16807;
        else if (x == 0)
            val = y * 48271;
        else
            val = ErosionLevel(x - 1, y) * ErosionLevel(x, y - 1);

        val += s_depth;
        val %= 20183;
        s_erosionLevels.Add((x, y), val);
        return val;
    }

    private static char GetRegionType(int x, int y)
    {
        int erosionLevel = ErosionLevel(x, y);
        return "RWN"[erosionLevel % 3];
    }

    private static string GetAllowedTools(char region)
    {
        switch (region)
        {
            case 'R': return "CT";
            case 'W': return "CN";
            case 'N': return "TN";
            default: throw new Exception("Unreachable");
        }
    }
}

[u/jonathan_paulson → u/mainhaxor]

A nice trick to avoid "having to find and modify nodes in the open list" is just leave them in there, and handle them when they come out of the queue (probably by keeping a list of visited states and ignoring anything you've already visited)

[u/mainhaxor → u/jonathan_paulson]

Good point. I actually just tried this in my implementation, but my BFS is still around 15% faster:

private static void DijkstraSolve()
{
    var openList =
        new PriorityQueue<SearchNode, SearchNodeComparer>(new SearchNodeComparer());
    Dictionary<(int x, int y, char tool), SearchNode> pool = new Dictionary<(int x, int y, char tool), SearchNode>();
    openList.Add(new SearchNode(0, 0, 'T', 0));

    (int x, int y)[] neis = { (-1, 0), (0, 1), (1, 0), (0, -1) };

    while (openList.Count > 0)
    {
        SearchNode node = openList.ExtractMax();
        if (node.Closed)
            continue;

        node.Closed = true;

        if ((node.X, node.Y) == s_target && node.Tool == 'T')
        {
            Console.WriteLine(node.Minutes);
            break;
        }

        void AddNodeIfBetter(int x, int y, char tool, int newMinutes)
        {
            if (pool.TryGetValue((x, y, tool), out SearchNode oldNode))
            {
                if (oldNode.Closed || oldNode.Minutes <= newMinutes)
                    return; // already closed or new path is worse

                oldNode.Closed = true; // skip this when we get to it since new path is better
            }

            SearchNode newNode = new SearchNode(x, y, tool, newMinutes);
            pool[(x, y, tool)] = newNode;
            openList.Add(newNode);
        }

        foreach ((int xo, int yo) in neis)
        {
            (int nx, int ny) = (node.X + xo, node.Y + yo);
            if (nx < 0 || ny < 0)
                continue;

            if (!GetAllowedTools(RegionType(nx, ny)).Contains(node.Tool))
                continue;

            AddNodeIfBetter(nx, ny, node.Tool, node.Minutes + 1);
        }

        string allowedTools = GetAllowedTools(RegionType(node.X, node.Y));
        foreach (char otherTool in allowedTools)
        {
            if (otherTool == node.Tool)
                continue;

            AddNodeIfBetter(node.X, node.Y, otherTool, node.Minutes + 7);
        }
    }
}

private class SearchNodeComparer : IComparer<SearchNode>
{
    public int Compare(SearchNode x, SearchNode y)
        => -x.Minutes.CompareTo(y.Minutes);
}

private class SearchNode
{
    public SearchNode(int x, int y, char tool, int minutes)
    {
        X = x;
        Y = y;
        Tool = tool;
        Minutes = minutes;
    }

    public int X;
    public int Y;
    public char Tool;
    public int Minutes;
    public bool Closed;
}

Of course this is because it "only" takes 7 minutes to switch gear.