Day 18: Ram Run

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#

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

    }