Day 20: Race Condition

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • NighedEnglish
    1·
    2 days ago

    C#

    Dijkstra to get each path’s distance from the start. Then for each path, look up to 20 away (mix X and Y movement) for a shortcut. (the actual path in between doesn’t matter)

    Calculating weights for the walls as I was originally going to try and use Dijkstra to path through walls

    spoiler

    public class Day20 { public void Go() { var inputText = File.ReadAllText(“C:\Users\Alex_\Documents\Programming\Advent of Code\AdventOfCode2024\AoC\src\day_20\input.txt”); var grid = PopulateInputGrid(inputText, out Node start, out Node end); FindDistances(grid, start);

        var results = SearchForValidShortcuts(grid);

    var groupedResults = results.GroupBy(shortcut => shortcut.Saving()).ToDictionary(grouping => grouping.Key, grouping => grouping.Select(shortcut => shortcut));
    var sortedResults = groupedResults.OrderBy(shortcut => shortcut.Key);
    
    foreach (var group in sortedResults)
    {
        Console.WriteLine($"There are {group.Value.Count()} cheats that save {group.Key} picoseconds.");
    }

    Console.WriteLine($"shortcuts saving more than 100: {results.Where(pair => pair.Saving() >= 100).Count()}");
}

public void GoPart2()
{
    var inputText = File.ReadAllText("C:\\Users\\Alex_\\Documents\\Programming\\Advent of Code\\AdventOfCode2024\\AoC\\src\\day_20\\input.txt");
    var grid = PopulateInputGrid(inputText, out Node start, out Node end);
    FindDistances(grid, start);        
    var results = SearchForValidShortcuts2(grid);
    var groupedResults = results.GroupBy(shortcut => shortcut.Saving()).ToDictionary(grouping => grouping.Key, grouping => grouping.Select(shortcut => shortcut));
    var sortedResults = groupedResults.OrderBy(shortcut => shortcut.Key);
    
    
    foreach (var group in sortedResults)
    {
        Console.WriteLine($"There are {group.Value.Count()} cheats that save {group.Key} picoseconds.");
    }

    Console.WriteLine($"shortcuts saving more than 100: {results.Where(pair => pair.Saving() >= 100).Count()}");
    var best = sortedResults.Last().Value.First();
    Console.WriteLine($"best shortcut is from: ({best.Start.Column},{best.Start.Row}) to: ({best.End.Column},{best.End.Row})");

}

private List<Shortcut> SearchForValidShortcuts2(List<List<Node>> grid)
{
    var shortcuts = new List<Shortcut>();
    var pathNodes = grid.SelectMany(list => list.Where(node => node.IsPath && !node.IsFinish));

    foreach (var node in pathNodes)
    {
        for (int i = -20; i <= 20; i++)
        {
            for (int j = -20; j <= 20; j++)
            {
                var distance = int.Abs(i) + int.Abs(j);
                if (distance > 20)
                {
                    continue;
                }

                if (node.Row + i < 0 || node.Row + i > grid.Count-1 || node.Column + j < 0 || node.Column + j > grid[0].Count-1)
                {
                    continue;
                }
                
                var endNode = grid[node.Row+i][node.Column+j];

                if (!endNode.IsPath)
                {
                    continue;
                }

                if (node.CostFromStart.Value+distance < endNode.CostFromStart.Value)
                {
                    shortcuts.Add(new Shortcut(node, endNode));
                }
            }
        }
    }
    
    return shortcuts;
}

private List<Shortcut> SearchForValidShortcuts(List<List<Node>> grid)
{
    var shortcuts = new List<Shortcut>();
    var pathNodes = grid.SelectMany(list => list.Where(node => node.IsPath && !node.IsFinish));

    foreach (var node in pathNodes)
    {
        if ((node.Left?.IsWall??false) && (node.Left.Left?.IsPath??false) && node.CostFromStart.Value+2 < node.Left.Left.CostFromStart.Value)
        {
            shortcuts.Add(new Shortcut(node, node.Left.Left));
        }
        if ((node.Right?.IsWall??false) && (node.Right.Right?.IsPath??false) && node.CostFromStart.Value+2 < node.Right.Right.CostFromStart.Value)
        {
            shortcuts.Add(new Shortcut(node, node.Right.Right));
        }
        if ((node.Up?.IsWall??false) && (node.Up.Up?.IsPath??false) && node.CostFromStart.Value+2 < node.Up.Up.CostFromStart.Value)
        {
            shortcuts.Add(new Shortcut(node, node.Up.Up));
        }
        if ((node.Down?.IsWall??false) && (node.Down.Down?.IsPath??false) && node.CostFromStart.Value+2 < node.Down.Down.CostFromStart.Value)
        {
            shortcuts.Add(new Shortcut(node, node.Down.Down));
        }
    }
    
    return shortcuts;
}

private List<List<Node>> GenerateGrid(int width, int height)
{
    var grid = new List<List<Node>>();
    for (int i = 0; i < height; i++)
    {
        var row = new List<Node>();
        for (int j = 0; j < width; j++)
        {
            row.Add(new Node(i,j));
        }
        grid.Add(row);
    }
    return grid;
}

private void FindDistances(List<List<Node>> grid, Node startNode)
{
    startNode.CostFromStart = 0;
    var queue = new PriorityQueue<Node,int>();
    var visited = new HashSet<Node>();
    queue.Enqueue(startNode,0);
    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        if (visited.Contains(node))
        {
            continue;
        }
        visited.Add(node);

        foreach (var neighbor in node.GetNeighbors())
        {
            var moveCost = neighbor.Cost;
            if (!neighbor.CostFromStart.HasValue || neighbor.CostFromStart > moveCost + node.CostFromStart)
            {
                neighbor.CostFromStart = moveCost + node.CostFromStart;
                queue.Enqueue(neighbor, neighbor.CostFromStart.Value);
            }
        }
    }
}

private List<List<Node>> PopulateInputGrid(string input, out Node startCoordinate, out Node endCoordinate)
{
    startCoordinate = null;
    endCoordinate = null;
    
    var inputLines = input.Split(new string[] { "\r\n", "\n" }, StringSplitOptions.RemoveEmptyEntries);
    var grid = GenerateGrid(inputLines[0].Length, inputLines.Length);

    for (var i = 0; i < grid.Count; i++)
    {
        var row = grid[i];
        for (var j = 0; j < row.Count; j++)
        {
            var node = row[j];
            var stringValue = inputLines[i][j];

            switch (stringValue)
            {
                case '#':
                    node.IsWall = true;
                    break;
                case 'S':
                    node.IsStart = true;
                    node.IsPath = true;
                    startCoordinate = node;
                    break;
                case 'E':
                    node.IsFinish = true;
                    node.IsPath = true;
                    endCoordinate = node;
                    break;
                default:
                    node.IsPath = true;
                    break;
            }
            
            if (node.Row < grid.Count-1)
            {
                node.Down = grid[node.Row+1][node.Column];
            }
    
            if (node.Column < grid[0].Count-1)
            {
                node.Right = grid[node.Row][node.Column+1];
            }

            if (node.Row > 0 )
            {
                node.Up = grid[node.Row-1][node.Column];
            }
    
            if (node.Column > 0 )
            {
                node.Left = grid[node.Row][node.Column-1];
            }
        }
    }

    return grid;
}

private class Shortcut
{
    public Shortcut(Node start, Node end)
    {
        Start = start;
        End = end;
    }

    public Node Start { get; set; }
    public Node End { get; set; }
    
    public int Saving()
    {
        return End.CostFromStart.Value - (Start.CostFromStart.Value + Math.Abs(Start.Column-End.Column) + Math.Abs(Start.Row-End.Row));
    }
}

private class Node:Coordinate
{
    public bool IsWall { get; set; }
    public bool IsStart { get; set; }
    public bool IsFinish { get; set; }
    
    public bool IsPath { get; set; }
    
    public int? CostFromStart { get; set; }
    
    public int Cost
    {
        get { return IsPath ? 1 : 100000; }
    }
    
    public Node? Left{ get; set; }
    public Node? Right{ get; set; }
    public Node? Up { get; set; }
    public Node? Down { get; set; }
    
    public Node(int row, int column): base(row,column)
    {
        
    }

    public List<Node> GetNeighbors()
    {
        var moves = new List<Node>();
    
        if (Left != null)
        {
            moves.Add(Left);
        }
        if (Right != null)
        {
            moves.Add(Right);
        }
        if (Up != null)
        {
            moves.Add(Up);
        }
        if (Down != null)
        {
            moves.Add(Down);
        }
        
        return moves;
    }

}
private class Coordinate
{
    public Coordinate(int row, int column)
    {
        Row = row;
        Column = column;
    }
    
    public int Row { get; set; }
    public int Column { get; set; }
}

    }