Advent Of Code 2021

Today ( Day15 ) we are once again navigating through a cave, and we're trying to avoid hitting the walls. We've scanned the surroundings, and produced a map containing the risk levels of the cave. We need to find the least risky path through the cave. The risk map looks like this:

1 equals low risk, 9 equals high risk. We're entering the cave at the top left position, and leaving at the bottom right. At the end, we need to sum the risk levels of all the position we've entered on our path. So we're not counting the initial risk of the top left position, it would only count if we were to enter it again later on our path.

Today, I actually had to do some googling to find an algorithm that I could easily implement. I tried a couple of times on my own, but didn't get a solution that would work in a reasonable amount of time. What I found was Dijkstras Algorithm with a priority queue.

My implementation looks like this:

private static int GetRisk(Dictionary<(int, int), int> map)
{
    var startingPoint = (0, 0);
    var endpoint = (map.Keys.Max(x => x.Item1), map.Keys.Max(x => x.Item2));

    var pointQueue = new Dictionary<(int, int), int> { { startingPoint, 0 } };
    var finalMap = new Dictionary<(int, int), int> { { startingPoint, 0 } };

    while (pointQueue.Count > 0)
    {
        var point = pointQueue.FirstOrDefault(x => x.Value == pointQueue.Min(x => x.Value)).Key;
        pointQueue.Remove(point);

        foreach (var adjPoint in GetAdjacentPoints(point))
        {
            if (map.ContainsKey(adjPoint) && !finalMap.ContainsKey(adjPoint))
            {
                var sumRisk = finalMap[point] + map[adjPoint];
                finalMap[adjPoint] = sumRisk;

                if (adjPoint == endpoint)
                {
                    break;
                }

                pointQueue.Add(adjPoint, sumRisk);
            }
        }

    }

    return finalMap[endpoint];
}

First of all, we define our starting point and end point. Then, we create a point queue, which we will use to store our possible next steps and the sum of the risk along the way. You might wonder why I'm using a Dictionary for this? Because I'm doing this with .Net 5. In .Net 6, there is a thing called PriorityQueue which would work exactly the way we want it to. That is, like a queue except for when you Dequeue() something, the PriorityQueue will give you the item with the lowest priority. A regular Queue is first-in-first-out.

This also makes my solution alot slower than it needs to be, since I constantly have to check the pointQueue for the item with the lowest risk. So if you have .Net 6 installed, use the PriorityQueue instead.

Moving on, we're getting all the adjacent points to the current point, sum up the total risk if we're moving to that point and add them to the pointQueue. When we reach the endpoint, we're done and our finalMap will contain the endpoint and the sum of risks that we are looking for.

For Part 2, we're going to do this again but on a bigger scale. We mneed to scale up the map from Part 1 to be 5 times the initial size. So instead of 10x10, it's going to be 50x50.

The original map from Part 1 will repeat to the right and down. For each repetition, the risk level of a position will increase by 1. If it goes above 9, it reverts back to 1 again.

Here's how we can do that:

private static Dictionary<(int, int), int> ScaleMap(Dictionary<(int, int), int> map)
{
    var maxX = map.Keys.Max(x => x.Item1) +1;
    var maxY = map.Keys.Max(x => x.Item2) +1;

    var xValues = Enumerable.Range(0, maxX * 5);
    var yValues = Enumerable.Range(0, maxY * 5);

    var newMap = new Dictionary<(int, int), int>();
    foreach (var xVal in xValues)
    {
        foreach (var yVal in yValues)
        {
            var origX = xVal % maxX;
            var origY = yVal % maxY;

            var origRisk = map[(origX, origY)];
            var distance = (yVal / maxY) + (xVal / maxX);

            var riskLevel = (origRisk + distance - 1) % 9 + 1;

            newMap.Add((xVal, yVal), riskLevel);
        }
    }

    return newMap;
}

We get the original max values for X and Y from our initial map segment. Then we create a range of new values for X and Y, that we'll use to fill our new map with points. Then it's just a matter of calculating the risk level by taking the risk level of the original point, add the distance, get the remainder of modulus 9 and add 1 to increase the value.

Like I said earlier, this runs slow for Part 2 since the map is alot larger and my Dijkstra implementation is not optimal. There are surely better ways of doing this even without PriorityQueue, but this was the first that came to mind for me.

Edit: I installed .Net 6 and tried this with PriorityQueue instead of a suboptimal Dictionary. Execution time went from > 10 minutes to < 1 second, without any other changes. Probably should have done that from the start, would have saved me time even if we include the installation time in the comparison.

Markestedt

Markestedt

Advent Of Code 2021 - Day 15