• 8 Posts
  • 248 Comments
Joined 11 months ago
cake
Cake day: January 13th, 2024

help-circle

  • 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; }
    }
    

    }


  • C#

    I had an error in the escape clause of the recursion that stumped me for a bit - wasn’t counting the last towel!

    This might be the first time I have ever had to use a long/ulong in 9 years of C# dev! (corp dev is obviously boring)

    spoiler

    using System.Collections.Concurrent;

    namespace AoC2024.day_19;

    public class Day19 { private ConcurrentDictionary<string,ulong> _cachedPossibilities = new ConcurrentDictionary<string, ulong>();

    public void GoPart1()
    {
        var inputText = File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\day_19\\input.txt");
        var availableTowels = GetAvailableTowels(inputText);
        var requiredPatterns = GetTargetPatterns(inputText);
        int reachablePatterns = 0;
        
        foreach (var targetPattern in requiredPatterns)
        {
            var result = DoTowelsMatch(targetPattern, availableTowels);
    
            if (result.Item1)
            {
                reachablePatterns++;
                Console.WriteLine($"Target pattern {targetPattern} can be reached with the following towels: {result.Item2.Aggregate("",(s, s1) => $"{s},{s1}")}");
            }
            else
            {
                Console.WriteLine($"Target pattern {targetPattern} can't be reached");
            }
        }
        
        Console.WriteLine($"reachable patterns: {reachablePatterns}");
    }
    
    public void GoPart2()
    {
        var inputText = File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\day_19\\input.txt");
        //var inputText = File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\day_19\\testInput.txt");
        var availableTowels = GetAvailableTowels(inputText);
        var requiredPatterns = GetTargetPatterns(inputText);
        ulong patternCount = 0;
        
        var tasks = new List<Task<ulong>>();
        
       // requiredPatterns = requiredPatterns.Take(5).ToList();
        
        
        foreach (var targetPattern in requiredPatterns)
        {
            var task = new Task<ulong>(() =>
            {
                Console.WriteLine(targetPattern);
                ulong taskPatternCount = 0;
                var result = DoTowelsMatch2(targetPattern, availableTowels);
    
                if (result.Item1)
                {
                    taskPatternCount = result.Item2;
                    Console.WriteLine($"Target pattern {targetPattern} can be reached with {result.Item2} permutations");
                }
                else
                {
                    Console.WriteLine($"Target pattern {targetPattern} can't be reached");
                }
    
                return taskPatternCount;
            });
            
            task.Start();
            tasks.Add(task);
        }
    
        Task.WaitAll(tasks);
    
        tasks.ForEach(task => patternCount += task.Result);
        Console.WriteLine($"{tasks.Count(task => task.Result > 0)} of the patterns were achieved");
        
        Console.WriteLine($"reachable patterns: {patternCount}");
    }
    
    private (bool,ulong) DoTowelsMatch2(string targetPattern, List<string> towelPatterns)
    {
        ulong possiblePatternCount = 0;
       
        if (_cachedPossibilities.ContainsKey(targetPattern))
        {
            _cachedPossibilities.TryGetValue(targetPattern, out possiblePatternCount);
            return (possiblePatternCount > 0,possiblePatternCount);
        }
        
        foreach (var towelPattern in towelPatterns)
        {
            if (targetPattern.StartsWith(towelPattern))
            {
                var newTargetPattern = targetPattern.Substring(towelPattern.Length);
    
                if (string.IsNullOrEmpty(newTargetPattern))
                {
                    possiblePatternCount++;
                    continue;
                }
                
                var doTowelsMatchResult = DoTowelsMatch2(newTargetPattern, towelPatterns);
                if (doTowelsMatchResult.Item1)
                {
                    possiblePatternCount += doTowelsMatchResult.Item2;
                }
            }
        }
    
        _cachedPossibilities.TryAdd(targetPattern, possiblePatternCount);
        
        return (possiblePatternCount>0,possiblePatternCount);
    }
    
    private (bool,List<string>?) DoTowelsMatch(string targetPattern, List<string> towelPatterns)
    {
        foreach (var towelPattern in towelPatterns)
        {
            if (targetPattern.StartsWith(towelPattern))
            {
                var newTargetPattern = targetPattern.Substring(towelPattern.Length);
    
                if (string.IsNullOrEmpty(newTargetPattern))
                {
                    return (true, new List<string>(){ towelPattern });
                }
                
                var doTowelsMatchResult = DoTowelsMatch(newTargetPattern, towelPatterns);
                if (doTowelsMatchResult.Item1)
                {
                    doTowelsMatchResult.Item2.Insert(0, towelPattern);
                    return (true, doTowelsMatchResult.Item2);
                }
            }
        }
    
        return (false,null);
    }
    
    private List<string> GetAvailableTowels(string input)
    {
        return input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries).First().Split(',', StringSplitOptions.RemoveEmptyEntries).Select(s => s.Trim()).ToList();
    }
    
    private List<string> GetTargetPatterns(string input)
    {
        var lines = input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries).ToList();
        lines.RemoveAt(0);
        return lines.Select(s => s.Trim()).ToList();
    }
    

    }


  • C#

    I did flood fill because i normally just do Dijkstra for this kind of stuff. watching the map print as it flooded was cool, had to disable it for part two though as it was too slow. Just let it run while I made a cup of tea instead of doing a binary search.

    spoiler

    namespace AoC2024.Day_18;

    public class Day18 {

    public const string CLEAR = ".";
    public const string BLOCKED = "#";
    public const string TRAVELED = "O";
    
    public void Go()
    {
        var testGrid = GenerateGrid(71, 71);
        PrintGrid(testGrid);
        var coords = GetInputCoordinates(File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\Day_18\\input.txt"));
        
        testGrid = ApplyCoords(testGrid, coords.Take(1024).ToList(), BLOCKED);
        PrintGrid(testGrid);
        FloodFillGrid(testGrid, new Coordinate(0,0), new (70,70));
    }
    
    public void GoPart2()
    {
        var testGrid = GenerateGrid(71, 71);
        PrintGrid(testGrid);
        var coords = GetInputCoordinates(File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\Day_18\\input.txt"));
    
        for (int i = 1; i <= coords.Count; i++)
        {
            testGrid = ApplyCoords(testGrid, coords.Take(i).ToList(), BLOCKED);
            PrintGrid(testGrid);
            var result = FloodFillGrid(testGrid, new Coordinate(0,0), new (70,70));
            if (result.Item2 == int.MaxValue)
            {
                var badCoord = coords[i - 1];
                Console.WriteLine($"!!!!Coord Number: {i} with a value of ({badCoord.Column},{badCoord.Row}) IS A BLOCKER!!!!");
                break;
            }
            else if (i%100 == 0)
            {
                var goodCoord = coords[i - 1];
                Console.WriteLine($"Coord Number: {i} with a value of ({goodCoord.Column},{goodCoord.Row}) allows an exit in {result.Item2} steps");
            }
        }
    }
    
    public List<List<string>> GenerateGrid(int width, int height)
    {
        var grid = new List<List<string>>();
        for (int i = 0; i < height; i++)
        {
            var row = new List<string>();
            for (int j = 0; j < width; j++)
            {
                row.Add(CLEAR);
            }
            grid.Add(row);
        }
    
        return grid;
    }
    
    public void PrintGrid(List<List<string>> grid)
    {
        // foreach (var row in grid)
        // {
        //     foreach (var value in row)
        //     {
        //         Console.Write($" {value} ");
        //     }
        //     Console.WriteLine();
        // }
    }
    
    public List<List<string>> ApplyCoords(List<List<string>> grid, List<Coordinate> coordinates, string value)
    {
        foreach (var coord in coordinates)
        {
            grid[coord.Row][coord.Column] = value;
        }
    
        return grid;
    }
    
    public List<Coordinate> GetInputCoordinates(string input)
    {
        var coords = new List<Coordinate>();
        foreach (var pair in input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries))
        {
            var values = pair.Split(',', StringSplitOptions.RemoveEmptyEntries);
            coords.Add(new Coordinate(values[1], values[0]));
        }
    
        return coords;
    }
    
    public (List<List<string>>, int) FloodFillGrid(List<List<string>> grid, Coordinate start, Coordinate target)
    {
        var newGrid = grid.Select(list => new List<string>(list)).ToList();
        var previousGrid = grid;
        newGrid[start.Row][start.Column] = TRAVELED;
        int stepCounter = 0;
        while (newGrid[target.Row][target.Column] != TRAVELED)
        {
            bool valueUpdatedInLoop = false;
            previousGrid = newGrid;
            newGrid = newGrid.Select(list => new List<string>(list)).ToList().ToList();
            
            for (var row = 0; row < grid.Count; row++)
            {
                for (var column = 0; column < grid[row].Count; column++)
                {
                    if (previousGrid[row][column] == CLEAR && IsAdjacentEqual(previousGrid, new Coordinate(row,column), TRAVELED))
                    {
                        newGrid[row][column] = TRAVELED;
                        valueUpdatedInLoop = true;
                    }
                }
            }
            stepCounter++;
    
            if (!valueUpdatedInLoop)
            {
                return (newGrid,int.MaxValue);
            }
            
            //Console.WriteLine($"Step counter: {stepCounter}");
            PrintGrid(newGrid);
            
        }
    
        return (newGrid,stepCounter);
    }
    
    private bool IsAdjacentEqual(List<List<string>> grid, Coordinate location, string value)
    {
        if (location.Row < grid.Count-1 && grid[location.Row+1][location.Column] == value)
        {
            return true;
        }
        
        if (location.Column < grid[0].Count-1 && grid[location.Row][location.Column+1] == value)
        {
            return true;
        }
    
        if (location.Row > 0 && grid[location.Row-1][location.Column] == value)
        {
            return true;
        }
        
        if (location.Column > 0 && grid[location.Row][location.Column-1] == value)
        {
            return true;
        }
    
        return false;
    }
    
    public struct Coordinate
    {
        public Coordinate(int row, int column)
        {
            Row = row;
            Column = column;
        }
        
        public Coordinate(string row, string column)
        {
            Row = int.Parse(row);
            Column = int.Parse(column);
        }
        
        public int Row { get; set; }
        public int Column { get; set; }
    }
    

    }


  • I’m almost always of the opinion that refactoring is better than a rewrite as long as the tech stack is supportable.

    Everyone wants to rewrite stuff, because the old system is ‘needlessly complicated’. 90% of the time though, they end up finding it was complicated for a reason and it all ends up going back in. It does allow a system to be written with the full knowledge of its scope though, instead of an old system that has been repeatedly bodjed and expanded. Finally, if your old tech stack is unsupportable (not just uncool, unsupportable) then it can be the most feasible way. It will take ages though with no/little return until it’s all finished.

    Refactoring is more difficult, as developers need to understand the existing codebase more to be able to safely upgrade it in situ. It does mean you can get continuous improvement through the process though as you update things bit by bit. You do need to test that each change doesn’t have unexpected impact though, and this can be difficult to do in badly written systems.

    Most Devs hate working on other people’s code though, so prefer rewrites.

    (Ran out of time to go into more detail)