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; }
}
}
If your app uses silver light, VB6 or something like that where modern OSs, browsers etc just don’t support it and there is no upgrade path.
It could also be written in a language that is supported, but you just can’t hire Devs for.