🌟 Advent of Code (AoC) 2024 🌟

4329 385 0 1444386 600463 19 1 56615

use ahash::AHashMap;
use std::fs::read_to_string;

pub const INPUT_FILE: &str = "input.txt";

type Number = u64;
type Stones = AHashMap<Number, usize>;

pub fn read_stones(path: &str) -> Stones {
    read_to_string(path)
        .expect("File does not exist")
        .split_whitespace()
        .map(|num| num.parse::<Number>().unwrap())
        .fold(AHashMap::new(), |mut acc, num| {
            *acc.entry(num).or_insert(0) += 1;
            acc
        })
}

pub fn part1(stones: &Stones) -> usize {
    blink_n_times(stones, 25)
}

pub fn part2(stones: &Stones) -> usize {
    blink_n_times(stones, 75)
}

fn blink_n_times(stones: &Stones, n: usize) -> usize {
    let mut stones_odd_blink = AHashMap::new();
    let mut stones_even_blink = stones.clone();
    for blink_cnt in 0..n {
        if blink_cnt % 2 == 0 {
            blink(&stones_even_blink, &mut stones_odd_blink);
        } else {
            blink(&stones_odd_blink, &mut stones_even_blink);
        }
    }
    if n % 2 == 0 {
        stones_even_blink
    } else {
        stones_odd_blink
    }
    .values()
    .sum()
}

fn blink(current: &Stones, next: &mut Stones) {
    next.clear();
    for (&number, &count) in current.iter() {
        if number == 0 {
            *next.entry(1).or_default() += count;
        } else {
            let num_digits = log10(number) + 1;
            if num_digits % 2 == 0 {
                let factor = (10 as Number).pow(num_digits / 2);
                let a = number / factor;
                let b = number % factor;
                *next.entry(a).or_default() += count;
                *next.entry(b).or_default() += count;
            } else {
                let a = number * 2024;
                *next.entry(a).or_default() += count;
            }
        }
    }
}

fn log10(n: Number) -> u32 {
    let mut l = 0;
    let mut factor = 10;
    while factor <= n {
        factor *= 10;
        l += 1;
    }
    l
}

public static class Solver
{

    private enum Direction { Up, Down, Left, Right }

    private static Direction GetOppositeDirection(Direction dir) => dir switch
    {
        Direction.Up => Direction.Down,
        Direction.Down => Direction.Up,
        Direction.Left => Direction.Right,
        Direction.Right => Direction.Left,
        _ => throw new ArgumentOutOfRangeException(nameof(dir), dir, null)
    };

    private readonly struct Coordinate(int x, int y)
    {
        public int X { get; } = x;
        public int Y { get; } = y;
    }
    
    private static Coordinate GetCoordAtDirection(Coordinate coord, Direction dir) => dir switch
    {
        Direction.Up => new Coordinate(coord.X, coord.Y - 1),
        Direction.Down => new Coordinate(coord.X, coord.Y + 1),
        Direction.Left => new Coordinate(coord.X - 1, coord.Y),
        Direction.Right => new Coordinate(coord.X + 1, coord.Y),
        _ => throw new ArgumentOutOfRangeException(nameof(dir), dir, null)
    };

    private static bool IsDirValid(Coordinate coord, Direction dir, int width, int height) =>  dir switch
    {
        Direction.Up => coord.Y - 1 >= 0,
        Direction.Down => coord.Y + 1 < height,
        Direction.Left => coord.X - 1 >= 0,
        Direction.Right => coord.X + 1 < width,
        _ => false
    };

    private static Region? GetRegionAtDirection(List<Region> regions, Coordinate coordinate, Direction direction)
    {
        return regions.FirstOrDefault(region => region.ContainsPosition(GetCoordAtDirection(coordinate, direction)));
    }
    
    private static List<Region> GenerateRegions(string[] lines)
    {
        var height = lines.Length;
        var width = lines[0].Length;
        var dirs = Enum.GetValues<Direction>();

        int currentRegionId = 0;
        
        var regions = new List<Region>();
        // First pass to generate a rough list of regions
        for (var y = 0; y < height; y++)
        {
            for (var x = 0; x < width; x++)
            {
                var coordinate = new Coordinate(x, y);
                var type = lines[y][x];
                var foundRegion = false;
                foreach (var dir in dirs)
                {
                    if (!IsDirValid(coordinate, dir, width, height))
                        continue;
                    
                    var neighborRegion = GetRegionAtDirection(regions, coordinate, dir);
                    if (neighborRegion == null) continue;
                    if (neighborRegion.PlotType != type) continue;
                    
                    neighborRegion.AddPlot(coordinate);
                        
                    foundRegion = true;
                    break;
                }

                if (foundRegion) continue;
                
                var region = new Region(type, currentRegionId);
                currentRegionId++;
                region.AddPlot(coordinate);
                regions.Add(region);
            }
        }
        
        // Second pass to merge regions of same type
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                var coordinate = new Coordinate(x, y);
                var type = lines[y][x];
                var region = regions.FirstOrDefault(region => region.ContainsPosition(coordinate));
                if (region == null)
                {
                    Console.WriteLine($"Region {coordinate} not found");
                    continue;
                }

                var isMerged = false;
                foreach (var dir in dirs)
                {
                    if (!IsDirValid(coordinate, dir, width, height))
                        continue;
                    
                    var neighborRegion = GetRegionAtDirection(regions, coordinate, dir);
                    if (neighborRegion == null) continue;
                    if (neighborRegion.PlotType != type) continue;
                    if (neighborRegion.Id == region.Id) continue;
                    
                    // Merge regions
                    foreach (var plot in region.Plots ?? [])
                    {
                        neighborRegion.AddPlot(plot.Coordinate);
                    }

                    isMerged = true;

                }
                if(!isMerged) continue;
                
                regions = regions.Where(r => r.Id != region.Id).ToList();
            }
        }

        return regions;
    }
    
    public static int Run_PartOne(string input)
    {
        var lines = input.Split("\r\n", StringSplitOptions.RemoveEmptyEntries);
        var regions = GenerateRegions(lines);
        var fenceCost = regions.Sum(r => r.FenceCost);
        return fenceCost;
    }
    
    public static int Run_PartTwo(string input)
    {
        var lines = input.Split("\r\n", StringSplitOptions.RemoveEmptyEntries);
        var regions = GenerateRegions(lines);
        var fenceCost = regions.Sum(r => r.FenceCostDiscounted);
        return fenceCost;
    }
    
    private class Plot
    {
        public Coordinate Coordinate { get; init; }
        
        public int NumEdges { get; set; }
        public List<Direction> Edges { get; init; } = [];
    }

    private class Region(char type, int id)
    {
        public int Id { get; set; } = id;
        public char PlotType { get; init; } = type;

        public int NumberOfPlots => Plots?.Count ?? 0;
        
        public int FenceCost => Plots?.Count * GetPerimeter ?? 0; // Area * Edges = Fence Cost
        public int FenceCostDiscounted => Plots?.Count * GetNumberOfSides() ?? 0;
        public int GetPerimeter => Plots?.Select(p => p.NumEdges).Sum() ?? 0;
        public List<Plot>? Plots { get; private set; }
        
        public bool ContainsPosition(Coordinate coordinate) =>
            Plots?.Any(p => p.Coordinate.X == coordinate.X && p.Coordinate.Y == coordinate.Y) ?? false;
        
        public void AddPlot(Coordinate coord)
        {
            var numEdges = 0;
            var dirs = new List<Direction>();
            foreach (var dir in Enum.GetValues<Direction>())
            {
                var otherPlot = GetPlotAt(coord, dir);
                if (otherPlot == null)
                {
                   
                    numEdges++;
                    dirs.Add(dir);
                }
                else
                {
                    otherPlot.NumEdges--;
                    otherPlot.Edges.Remove(GetOppositeDirection(dir));
                }
            }
            
            Plots ??= [];
            
            Plots.Add(new Plot()
            {
                Coordinate = coord,
                NumEdges = numEdges,
                Edges = dirs
            });
        }
        
        private Plot? GetPlotAt(Coordinate coordinate, Direction direction)
        {
            var coord = GetCoordAtDirection(coordinate, direction);
            var plot = Plots?.FirstOrDefault(p => p.Coordinate.X == coord.X && p.Coordinate.Y == coord.Y);
            return plot;
        }
        
        private int GetNumberOfSides()
        {
            var sides = 0;

            foreach (var plot in Plots.Where(p => p.NumEdges > 0))
            {
                var plotSides = 0;
                var leftPlot = GetPlotAt(plot.Coordinate, Direction.Left);
                var topPlot = GetPlotAt(plot.Coordinate, Direction.Up);
                if (plot.Edges.Contains(Direction.Left))
                {
                    if (topPlot != null)
                    {
                        if (!topPlot.Edges.Contains(Direction.Left))
                            plotSides++;
                    }
                    else
                    {
                        plotSides++;
                    }
                }
                
                if (plot.Edges.Contains(Direction.Up))
                {
                    if (leftPlot != null)
                    {
                        if (!leftPlot.Edges.Contains(Direction.Up))
                            plotSides++;
                    }
                    else
                    {
                        plotSides++;
                    }
                }
                if (plot.Edges.Contains(Direction.Right))
                {
                    if (topPlot != null)
                    {
                        if (!topPlot.Edges.Contains(Direction.Right))
                            plotSides++;
                    }
                    else
                    {
                        plotSides++;
                    }
                }
                if (plot.Edges.Contains(Direction.Down))
                {
                    if (leftPlot != null)
                    {
                        if (!leftPlot.Edges.Contains(Direction.Down))
                            plotSides++;
                    }
                    else
                    {
                        plotSides++;
                    }
                }
                
                sides += plotSides;
            }
            
            return sides;
        }
    }
}

use ahash::AHashSet;
use std::fs::read_to_string;

pub const INPUT_FILE: &str = "input.txt";

type GardenPlots = Vec<Vec<char>>;

pub fn read_garden_plots(path: &str) -> GardenPlots {
    read_to_string(path)
        .expect("File does not exist")
        .lines()
        .map(|line| line.chars().collect())
        .collect()
}

pub fn part1(costs: &(u32, u32)) -> u32 {
    costs.0
}

pub fn part2(costs: &(u32, u32)) -> u32 {
    costs.1
}

pub fn calculate_total_fence_cost(garden_plots: &GardenPlots) -> (u32, u32) {
    let mut visited = AHashSet::new();
    let mut total_cost = 0;
    let mut total_discounted_cost = 0;
    for (y, row) in garden_plots.iter().enumerate() {
        for x in 0..row.len() {
            let pos = (x as i32, y as i32);
            if visited.contains(&pos) {
                continue;
            }
            visited.insert(pos);
            let costs = calculate_fence_cost(garden_plots, &pos, &mut visited);
            total_cost += costs.0;
            total_discounted_cost += costs.1;
        }
    }
    (total_cost, total_discounted_cost)
}

fn calculate_fence_cost(
    garden_plots: &GardenPlots,
    region_position: &(i32, i32),
    visited: &mut AHashSet<(i32, i32)>,
) -> (u32, u32) {
    let region = garden_plots[region_position.1 as usize][region_position.0 as usize];
    let height = garden_plots.len() as i32;
    let width = garden_plots[0].len() as i32;
    let adjacent_plots = |pos: &(i32, i32)| {
        [
            ((pos.0 - 1, pos.1), false),
            ((pos.0 + 1, pos.1), false),
            ((pos.0, pos.1 - 1), false),
            ((pos.0, pos.1 + 1), false),
            ((pos.0 - 1, pos.1 - 1), true),
            ((pos.0 + 1, pos.1 - 1), true),
            ((pos.0 - 1, pos.1 + 1), true),
            ((pos.0 + 1, pos.1 + 1), true),
        ]
    };
    let is_same_region = |pos: (i32, i32)| {
        pos.0 >= 0
            && pos.0 < width
            && pos.1 >= 0
            && pos.1 < height
            && garden_plots[pos.1 as usize][pos.0 as usize] == region
    };
    let mut region_area = 0;
    let mut region_perimeter = 0;
    let mut region_corners = 0;
    let mut stack = vec![*region_position];
    while !stack.is_empty() {
        let pos = stack.pop().unwrap();
        region_area += 1;
        let mut plot_perimeter = 4;
        let mut plot_adj_mask = 0;
        for (adj_pos, is_diagonal) in adjacent_plots(&pos) {
            if !is_same_region(adj_pos) {
                continue;
            }
            plot_adj_mask |= 1 << ((1 + adj_pos.0 - pos.0) + 3 * (1 + adj_pos.1 - pos.1));

            if !is_diagonal {
                plot_perimeter -= 1;

                if visited.insert(adj_pos) {
                    stack.push(adj_pos);
                }
            }
        }
        region_perimeter += plot_perimeter;
        region_corners += count_plot_corners(plot_adj_mask);
    }
    (region_area * region_perimeter, region_area * region_corners)
}

fn count_plot_corners(plot_adj_mask: i32) -> u32 {
    let mut plot_corners = 0;
    let all_clr = |bits| (plot_adj_mask & bits) == 0;
    let all_set = |bits| (plot_adj_mask & bits) == bits;
    // Convex corners
    for bits in [2 + 8, 2 + 32, 32 + 128, 8 + 128] {
        if all_clr(bits) {
            plot_corners += 1;
        }
    }
    // Concave corners
    for (s, c) in [(2 + 8, 1), (2 + 32, 4), (8 + 128, 64), (32 + 128, 256)] {
        if all_set(s) && all_clr(c) {
            plot_corners += 1;
        }
    }
    plot_corners
}

fn main() {
    let garden_plots = read_garden_plots(&INPUT_FILE);
    let costs = calculate_total_fence_cost(&garden_plots);
    println!("part 1: {}", part1(&costs));
    println!("part 2: {}", part2(&costs));
}

import MetalKit

let amplification_factor = 100_000;
let formatter = NumberFormatter()
formatter.numberStyle = .decimal

let device = MTLCreateSystemDefaultDevice()!
let commandQueue = device.makeCommandQueue()!
let library = device.makeDefaultLibrary()!

let commandBuffer = commandQueue.makeCommandBuffer()!
let encoder = commandBuffer.makeComputeCommandEncoder()!
encoder.setComputePipelineState(try device.makeComputePipelineState(function: library.makeFunction(name: "add")!))
let fileContents = try String(contentsOfFile: "/Users/kjn/input.txt", encoding: .utf8)
let lines = fileContents.split(separator: "\n")
let reports: [[Int32]] = lines.map { line in line.split(separator: " ").compactMap { Int32($0) } }
let reportStride = reports.map { $0.count }.max() ?? 0
let paddedReports: [[Int32]] = reports.map { report in
    report + Array(repeating: Int32(0), count: reportStride - report.count)
}
let inputTemplate: [Int32] = paddedReports.flatMap { $0 }
let input = Array(repeating: inputTemplate, count: amplification_factor).flatMap { $0 }

let numReports = input.count / reportStride

// kernel first arg
let reportStrideBuffer = device.makeBuffer(bytes: [reportStride], length: MemoryLayout<Int32>.stride, options: [])
encoder.setBuffer(reportStrideBuffer, offset: 0, index: 0)

// kernel second arg
let inputBuffer = device.makeBuffer(bytes: input as [Int32], length: MemoryLayout<Int32>.stride * input.count, options: [])
encoder.setBuffer(inputBuffer, offset: 0, index: 1)

// kernel third arg
let reductionResultBuffer = device.makeBuffer(length: MemoryLayout<Int32>.stride * 2, options: .storageModeShared)!
let reductionPointer = reductionResultBuffer.contents().bindMemory(to: Int32.self, capacity: 1)
reductionPointer.pointee = 0
encoder.setBuffer(reductionResultBuffer, offset: 0, index: 2)

// kernel thread configuration
let numThreads = 500
let threadsPerThreadgroup = MTLSize(width: numThreads, height: 1, depth: 1) // Number of threads in a threadgroup
let numThreadgroups = MTLSize(width: (numReports + numThreads - 1) / numThreads, height: 1, depth: 1)
encoder.dispatchThreadgroups(numThreadgroups, threadsPerThreadgroup: threadsPerThreadgroup)

encoder.endEncoding()

// Start kernel
print(String(format:"Go with %dM reports!", numReports / 1_000_000))
let startTime = DispatchTime.now()
commandBuffer.commit()
commandBuffer.waitUntilCompleted()
let doneTime = DispatchTime.now()

// gpuStartTime and gpuEndTime are a float representing host time in seconds when the kernel started and ended
let gpuExecutionTime = (commandBuffer.gpuEndTime - commandBuffer.gpuStartTime) * 1_000
print(String(format: "GPU time: %.2f ms", gpuExecutionTime))
print(String(format: "GPU capacity: %.0fM reports/sec", 1000.0 / Double(gpuExecutionTime) * Double(numReports) / 1_000_000.0))


let count = reductionResultBuffer.length / MemoryLayout<Int32>.stride // Calculate the number of elements
let pointer = reductionResultBuffer.contents().bindMemory(to: Int32.self, capacity: count)
let bufferPointer = UnsafeBufferPointer(start: pointer, count: count)
for (index, value) in bufferPointer.enumerated() {
    print(String(format: "%d: %d", index, value))
}

#include <metal_stdlib>
using namespace metal;

kernel void add(constant int &report_stride [[ buffer(0) ]],
                const device int *levels [[ buffer(1) ]],
                device atomic_int *result [[ buffer(2) ]],
                uint id [[ thread_position_in_grid ]]) {
    const int level_offset = id * report_stride;
    const int d0 = levels[level_offset + 1] - levels[level_offset + 0];
    const int lo = d0 < 0 ? -3 : 1;
    const int hi = d0 < 0 ? -1 : 3;
    
    int is_safe = 1;
    for (int i = 0; i < report_stride - 1; i++) {
        const int l1 = levels[level_offset + i + 1];
        if (l1 == 0) {
            break;
        }
        const int l0 = levels[level_offset + i];
        const int d = l1 - l0;
        if (d < lo || d > hi) {
            is_safe = 0;
            break;
        }
    }
    
    if (is_safe) {
        atomic_fetch_add_explicit(result, 1, memory_order_relaxed);
    }
    
    int is_safe_with_damper = is_safe;
    for (int ignore = 0; !is_safe_with_damper && ignore < report_stride; ignore++)
    {
        int ilo;
        int ihi;
        if (ignore == 0) {
            const int d0 = levels[level_offset + 2] - levels[level_offset + 1];
            ilo = d0 < 0 ? -3 : 1;
            ihi = d0 < 0 ? -1 : 3;
        } else if (ignore == 1)
        {
            const int d0 = levels[level_offset + 2] - levels[level_offset + 0];
            ilo = d0 < 0 ? -3 : 1;
            ihi = d0 < 0 ? -1 : 3;
        } else {
            ilo = lo;
            ihi = hi;
        }
     
        is_safe_with_damper = 1;
        for (int i = 0, j = 1; ; i++, j++) {
            if (i == ignore) {
                continue;
            }
            if (j == ignore) {
                j++;
            }
            if (j >= report_stride) {
                is_safe_with_damper = 0;
                break;
            }
            
            const int l1 = levels[level_offset + j];
            if (l1 == 0) {
                break;
            }
            const int l0 = levels[level_offset + i];
            const int d = l1 - l0;
            if (d < lo || d > hi) {
                is_safe_with_damper = 0;
                break;
            }
        }
    }
    
    if (is_safe_with_damper) {
        atomic_fetch_add_explicit(result + 1, 1, memory_order_relaxed);
    }
}

using Position = (int x, int y);
(int sumpart1, int sumpart2) = (0, 0);
var lines = File.ReadAllLines("input.txt");
Dictionary<Position, char> grid = [];
HashSet<Position> visited = [];
List<HashSet<Position>> regions = [];
int max = lines.Length; 
for (int x = 0; x < max; x++)
    for (int y = 0; max > y; y++)
        grid[(x, y)] = lines[x][y];

foreach (var plot in grid)
{
    if (visited.Contains(plot.Key))
        continue;
    HashSet<Position> current = [];
    Dictionary<Position, int> neighbourtouches = [];
    var (area, perimeter) = explorePlot(plot.Key, plot.Value, current, grid, max);
    sumpart1 += area * perimeter;
    var sides = countCorners(current);
    sumpart2 += area * sides;
    visited.UnionWith(current);
}

Console.WriteLine("Part 1: " + sumpart1);
Console.WriteLine("Part 2: " + (sumpart2));

static (int area, int perimeter) explorePlot(Position pos, char value, HashSet<Position> visited, Dictionary<Position, char> grid, int max)
{
    if (!inRange(pos, max))
        return (0, 1);
    var curr = grid[pos];
    if (curr != value)
        return (0, 1);
    if (visited.Contains(pos))
        return (0, 0);
    visited.Add(pos);
    (int area, int perim) = (1, 0);
    foreach (var n in getImmediateNeighbours(pos))
    {
        var r = explorePlot(n, value, visited, grid, max);
        (area, perim) = (area + r.area, perim + r.perimeter);
    }
    return (area, perim);
}

static int countCorners(HashSet<Position> region)
{
    int corners = 0;
    foreach (var pos in region)
    {
        var n = getAllNeighbours(pos);
        (bool up, bool dn, bool lt, bool rt, bool ul, bool ur, bool dl, bool dr) =
            (c(n.up), c(n.dn), c(n.lt), c(n.rt), c(n.ul), c(n.ur), c(n.dl), c(n.dr));
        if (up && lt && !ul) // inside upleft corner
            corners++;
        if (!up && !lt) // outside upleft corner
            corners++;
        if (up && rt && !ur) // inside upright corner
            corners++;
        if (!up && !rt) // outside upright corner
            corners++;
        if (dn && lt && !dl) //inside downleft corner
            corners++;
        if (!dn && !lt) //outside downleft corner
            corners++;
        if (dn && rt && !dr) //inside downright corner
            corners++;
        if (!dn && !rt) //outside downright corner
            corners++;
    }
    return corners;
    bool c(Position p) => region.Contains(p);
}

static (Position up, Position dn, Position lt, Position rt, Position ul, Position ur, Position dl, Position dr) getAllNeighbours(Position p)
{
    return (
        (p.x - 1, p.y), // up
        (p.x + 1, p.y), // down
        (p.x, p.y - 1), // left
        (p.x, p.y + 1), //right
        (p.x - 1, p.y - 1), // up-left
        (p.x - 1, p.y + 1), // up-right
        (p.x + 1, p.y - 1), // down-left
        (p.x + 1, p.y + 1)); // down-right
}

static IEnumerable<Position> getImmediateNeighbours(Position pos)
{
    Position[] rels = [(1, 0), (0, 1), (-1, 0), (0, -1)];
    foreach (var (x, y) in rels)
    {
        var npos = (pos.x + x, pos.y + y);
        yield return npos;
    }
    yield break;
}

static bool inRange(Position pos, int max) => (pos.x < max && pos.x >= 0 && pos.y < max && pos.y >= 0);

using System.Diagnostics;
Stopwatch sw = Stopwatch.StartNew();
var slots = File.ReadAllText("input.txt").Split("\r\n\r\n");
(long sumpart1, long sumpart2) = (0, 0);
foreach (var slot in slots)
{
    var split = slot.Split('\n');
    var axy = split[0][12..].Split(", Y+").Select(int.Parse).ToArray();
    (int x, int y) a = (axy[0], axy[1]);
    var bxy = split[1][12..].Split(", Y+").Select(int.Parse).ToArray();
    (int x, int y) b = (bxy[0], bxy[1]);
    var gxy = split[2][9..].Split(", Y=").Select(int.Parse).ToArray();
    (int x, int y) g = (gxy[0], gxy[1]);
    sumpart1 += solve(a, b, g);
    sumpart2 += solve(a, b, g, true);
}

Console.WriteLine("Part 1: " + sumpart1);
Console.WriteLine("Part 2: " + sumpart2);
Console.WriteLine("Time: " + sw.Elapsed);

static long solve((int x, int y) aval, (int x, int y) bval, (long x, long y) gval, bool part2 = false)
{
    long cost = 0;
    var (ax, ay) = aval;
    var (bx, by) = bval;
    var (gx, gy) = gval;
    if (part2)
    {
        gx += 10000000000000;
        gy += 10000000000000;
    }
    //      (gx * by) - (gy * bx)
    // a =  ---------------------
    //      (ax * by) - (ay * bx)
    // if ax * by == ay * bx, there is no solution (divide by zero) and we can return 0 immediately
    if (ax * by == ay * bx)
        return cost;
    var a = ((gx * by) - (gy * bx)) / ((ax * by) - (ay * bx));
    //     gx - ax*a
    // b = ---------
    //        bx
    var b = (gx - (ax * a)) / bx;
    // sanity check, press A a times and B b times and see if they equal the goal values
    if (a * ax + b * bx == gx && a * ay + b * by == gy)
        cost = 3 * a + b;
    return cost;
}

public static class Solver
{
    private static long CalculateMinimumTokenCost(List<Machine> machines, bool isLimited)
    {
        var cost = 0L;
        foreach (var machine in machines)
        {
            var ax = machine.A.X * machine.B.Y;
            var ay = machine.B.X * machine.A.Y;

            var a = ax - ay;
            
            var aPrice = (machine.Price.X * machine.B.Y) - (machine.Price.Y * machine.B.X);
            
            var numA = (aPrice / a);

            var bPrice = (machine.Price.X - (machine.A.X * numA));
            var numB = bPrice / machine.B.X;

            if (isLimited && (numA > 100 || numB > 100))
                continue;
            
            if (((machine.A.X * numA) + (machine.B.X * numB)) != machine.Price.X || ((machine.A.Y * numA) + (machine.B.Y * numB)) != machine.Price.Y)
                continue;
            
            cost += ((numA * machine.TokensA) + (numB * machine.TokensB));
        }

        return cost;
    }

    private static Point ParseMachineButtonLine(string line)
    {
        var x = line.Substring(line.IndexOf(':') + 2, line.IndexOf(',') - line.IndexOf(':') - 2).Replace("X+", "");
        var y = line[(line.IndexOf(',') + 2)..].Replace("Y+", "");
        
        return new Point { X = int.Parse(x), Y = int.Parse(y) };
    }
    private static Point ParseMachinePrizeLine(string line)
    {
        var x = line.Substring(line.IndexOf(':') + 2, line.IndexOf(',') - line.IndexOf(':') - 2).Replace("X=", "");
        var y = line[(line.IndexOf(',') + 2)..].Replace("Y=", "");
        
        return new Point() { X = int.Parse(x), Y = int.Parse(y) };
    }
    private static List<Machine> ParseMachinesInput(string input)
    {
        var machines = new List<Machine>();
        var lines = input.Split("\r\n", StringSplitOptions.RemoveEmptyEntries).ToList();

        for (var i = 0; i < lines.Count; i++)
        {
            var machineIndex = i / 3;
            var machine = machines.ElementAtOrDefault(machineIndex);
            if (machine == null)
            {
                machines.Add(new Machine(){ TokensA = 3, TokensB = 1});
                machine = machines.ElementAt(machineIndex);
            }
            
            if (lines[i].Contains('A'))
                machine.A = ParseMachineButtonLine(lines[i]);
            else if (lines[i].Contains('B'))
                machine.B = ParseMachineButtonLine(lines[i]);
            else
                machine.Price = ParseMachinePrizeLine(lines[i]);
            
        }
        return machines;
    }
    
    public static long Run_PartOne(string input)
    {
        var machines = ParseMachinesInput(input);
        var cost = CalculateMinimumTokenCost(machines, true);
        return cost;
    }

    public static long Run_PartTwo(string input)
    {
        var machines = ParseMachinesInput(input);
        foreach (var machine in machines)
        {
            machine.Price = new Point() { X = machine.Price.X + 10000000000000, Y =  machine.Price.Y + 10000000000000 };
        }
        var cost = CalculateMinimumTokenCost(machines, false);
        return cost;
    }
    
    private struct Point
    {
        public long X { get; init; }
        public long Y { get; init; }
    }
    private class Machine
    {
        public int TokensA { get; init; }
        public int TokensB { get; init; }
        
        public Point A { get; set; }
        public Point B { get; set; }
        
        public Point Price { get; set; }
    }
}

use regex::Regex;
use std::fs;

pub const INPUT_FILE: &str = "input.txt";

pub struct Machine {
    a: (Number, Number),
    b: (Number, Number),
    prize: (Number, Number),
}

type Number = i64;

pub fn read_machines(path: &str) -> Vec<Machine> {
    let content = fs::read_to_string(path).expect("File does not exist");
    let re = Regex::new(
        r"Button A: X\+(\d+), Y\+(\d+)\nButton B: X\+(\d+), Y\+(\d+)\nPrize: X=(\d+), Y=(\d+)",
    )
    .unwrap();
    re.captures_iter(&content)
        .map(|caps| Machine {
            a: (caps[1].parse().unwrap(), caps[2].parse().unwrap()),
            b: (caps[3].parse().unwrap(), caps[4].parse().unwrap()),
            prize: (caps[5].parse().unwrap(), caps[6].parse().unwrap()),
        })
        .collect()
}

pub fn part1(machines: &[Machine]) -> Number {
    machines
        .iter()
        .filter_map(calculate_button_pushes)
        .map(calculate_token_cost)
        .sum()
}

pub fn part2(machines: &[Machine]) -> Number {
    machines
        .iter()
        .map(|machine| Machine {
            a: machine.a,
            b: machine.b,
            prize: (
                machine.prize.0 + 10000000000000,
                machine.prize.1 + 10000000000000,
            ),
        })
        .filter_map(|machine| calculate_button_pushes(&machine))
        .map(calculate_token_cost)
        .sum()
}

fn calculate_button_pushes(m: &Machine) -> Option<(Number, Number)> {
    // This is the solved equation system, simplified to a single division
    let a_dominator = m.prize.1 * m.b.0 - m.prize.0 * m.b.1;
    let a_nominator = m.a.1 * m.b.0 - m.a.0 * m.b.1;
    if a_dominator % a_nominator != 0 {
        return None;
    }
    let a_pushes = a_dominator / a_nominator;
    let b_dominator = m.prize.0 - m.a.0 * a_pushes;
    let b_nominator = m.b.0;
    if b_dominator % b_dominator != 0 {
        return None;
    }
    let b_pushes = b_dominator / b_nominator;
    Some((a_pushes, b_pushes))
}

fn calculate_token_cost((a, b): (Number, Number)) -> Number {
    a * 3 + b * 1
}

import numpy as np

def find_clusters(matrix):
    rows, cols = matrix.shape
    visited = np.zeros(matrix.shape, dtype=bool)
    
    def dfs(r, c, char):
        stack = [(r, c)]
        coordinates = []
        while stack:
            x, y = stack.pop()
            if not visited[x, y] and matrix[x, y] == char:
                visited[x, y] = True
                coordinates.append((x, y))
                for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
                    if not visited[nx, ny] and matrix[nx, ny] == char:
                        stack.append((nx, ny))
        return coordinates
    
    return [dfs(r, c, matrix[r, c]) 
            for r in range(1, rows-1) 
            for c in range(1, cols-1)
            if not visited[r, c]]
                    
matrix = np.pad(np.array([list(line.strip()) 
                          for line in open('input12.txt', 'r')]), pad_width=1, mode='constant', constant_values=' ')

O = matrix[1:-1, 1:-1]
N = matrix[0:-2, 1:-1]
S = matrix[2:, 1:-1]
E = matrix[1:-1, 2:]
W = matrix[1:-1, 0:-2]
NE = matrix[0:-2, 2:]
SE = matrix[2:, 2:]
SW = matrix[2:, 0:-2]

def compute_fences(matrix):
    fences = np.zeros(matrix.shape, dtype=int)
    fences[1:-1, 1:-1] = (
        (O != W).astype(int) +
        (O != E).astype(int) +
        (O != N).astype(int) +
        (O != S).astype(int))
    return fences

def join_fences(matrix, fences):
    fences[1:-1, 1:-1] -= (
        ((O == S) & (O != W) & (S != SW)).astype(int) +
        ((O == S) & (O != E) & (S != SE)).astype(int) +
        ((O == E) & (O != N) & (E != NE)).astype(int) +
        ((O == E) & (O != S) & (E != SE)).astype(int))
    return fences

fences = compute_fences(matrix)
cluster_coordinates = find_clusters(matrix)

print(sum(len(c) * sum(fences[tuple(zip(*c))]) for c in cluster_coordinates))
join_fences(matrix, fences)
print(sum(len(c) * sum(fences[tuple(zip(*c))]) for c in cluster_coordinates))

import re

def solve(offset, x1, x2, y1, y2, s1, s2):
    b = (x2 * (s1 + offset) - x1 * (s2 + offset)) / (y1 * x2 - y2 * x1)
    a = (s1 + offset - b * y1) / x1
    return a, b

print(*[sum([int(a * 3 + b) 
             for i in open("input13.txt", "r").read().strip().split('\n\n') 
             for a, b in [solve(offset, *tuple(map(int, re.findall(r'\d+', i))))] 
             if a.is_integer() and b.is_integer()]) 
        for offset in [0, 10000000000000]])

import re
import numpy as np

sx, sy = 101, 103

floor = np.zeros((sy, sx), dtype=int)
for i in open("input14.txt", "r").readlines():
    px, py, vx, vy = tuple(map(int, re.findall(r'\-?\d+', i)))
    floor[(py + 100 * vy) % sy, (px + 100 * vx) % sx] += 1

sx, sy  = sx // 2, sy // 2

print(floor[:sy, :sx].sum() * floor[:sy, sx + 1:].sum() * 
      floor[sy + 1:, :sx].sum() * floor[sy + 1:, sx + 1:].sum())

use ahash::AHashSet;
use regex::Regex;
use std::fs;

pub struct Robot {
    position: (i32, i32),
    velocity: (i32, i32),
}

pub const INPUT_FILE: &str = "input.txt";

pub fn read_robots(path: &str) -> Vec<Robot> {
    let re = Regex::new(r"[-+]?\d+").expect("Invalid regex");
    fs::read_to_string(path)
        .expect("File does not exist")
        .lines()
        .map(|line| {
            let nums: Vec<i32> = re
                .find_iter(line)
                .map(|n| n.as_str().parse().expect("Invalid number"))
                .collect();
            Robot {
                position: (nums[0], nums[1]),
                velocity: (nums[2], nums[3]),
            }
        })
        .collect()
}

pub fn part1(robots: &[Robot], width: i32, height: i32, seconds: i32) -> i32 {
    let mid_x = width / 2;
    let mid_y = height / 2;
    let mut quadrants = [0, 0, 0, 0];
    for (x, y) in move_robots(robots, width, height, seconds) {
        if x != mid_x && y != mid_y {
            quadrants[(x / (mid_x + 1) + 2 * (y / (mid_y + 1))) as usize] += 1;
        }
    }
    quadrants
        .iter()
        .fold(1, |security_factor, cnt| security_factor * cnt)
}

fn move_robots(
    robots: &[Robot],
    width: i32,
    height: i32,
    seconds: i32,
) -> impl Iterator<Item = (i32, i32)> + '_ {
    robots.iter().map(move |robot| {
        (
            ((robot.position.0 + seconds * robot.velocity.0) % width + width) % width,
            ((robot.position.1 + seconds * robot.velocity.1) % height + height) % height,
        )
    })
}

pub fn part2(robots: &[Robot], width: i32, height: i32) -> i32 {
    let mid_y = height / 2;
    let mut seconds = 1;
    'done: loop {
        let mut floor = vec![vec![0; width as usize]; height as usize];
        for (x, y) in move_robots(robots, width, height, seconds) {
            floor[y as usize][x as usize] += 1;
        }
        for x_start in (width / 3)..(2 * width / 3) {
            if calculate_area(&floor, (x_start, mid_y)) > 10 {
                // Something solid in the middle, assume tree
                break 'done;
            }
        }
        seconds += 1;
    }
    seconds
}

fn calculate_area(floor: &[Vec<i32>], mid: (i32, i32)) -> i32 {
    if floor[mid.1 as usize][mid.0 as usize] == 0 {
        return 0;
    }
    let mut area = 0;
    let mut visited = AHashSet::new();
    let mut dfs_stack = vec![mid];
    visited.insert(mid);
    while !dfs_stack.is_empty() {
        let (x, y) = dfs_stack.pop().unwrap();
        area += 1;
        for adj_pos in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)] {
            if floor[adj_pos.1 as usize][adj_pos.0 as usize] > 0 && visited.insert(adj_pos) {
                dfs_stack.push(adj_pos);
            }
        }
    }
    area
}

fn main() {
    let robots = read_robots(&INPUT_FILE);
    println!("part 1: {}", part1(&robots, 101, 103, 100));
    println!("part 2: {}", part2(&robots, 101, 103));
}

using System.Text.RegularExpressions;
var lines = File.ReadAllLines("input.txt");
(int x, int y) tsize = (101, 103);
Dictionary<(int x, int y), List<(int x, int y)>> grid = [];
(int sumpart1, int sumpart2) = (0, 100);
var regex = new Regex(@(-?\d+));
foreach (var line in lines) 
{
    var m = regex.Matches(line);
    placeRobot((int.Parse(m[0].Value), int.Parse(m[1].Value)), (int.Parse(m[2].Value), int.Parse(m[3].Value)), grid);
}
// part 1
for (int i = 0; i < 100; i++)
    grid = moveRobots(grid);

var q1 = grid.Where(r => r.Key.x < tsize.x / 2 && r.Key.y < tsize.y / 2);
var q2 = grid.Where(r => r.Key.x > tsize.x / 2 && r.Key.y < tsize.y / 2);
var q3 = grid.Where(r => r.Key.x < tsize.x / 2 && r.Key.y > tsize.y / 2);
var q4 = grid.Where(r => r.Key.x > tsize.x / 2 && r.Key.y > tsize.y / 2);
sumpart1 = q1.Sum(x => x.Value.Count) * q2.Sum(x => x.Value.Count) * q3.Sum(x => x.Value.Count) * q4.Sum(x => x.Value.Count);

//Part 2
while (grid.Any(g => g.Value.Count > 1))
{
    grid = moveRobots(grid);
    sumpart2++;
}
visualise(grid);
Console.WriteLine("Part 1: " + sumpart1);
Console.WriteLine("Part 2: " + sumpart2);

Dictionary<(int x, int y), List<(int x, int y)>> moveRobots(Dictionary<(int x, int y), List<(int x, int y)>> grid)
{
    Dictionary<(int x, int y), List<(int x, int y)>> ret = [];
    foreach (var pos in grid)
        foreach (var robot in pos.Value)
            placeRobot(((pos.Key.x + robot.x + tsize.x) % tsize.x, (pos.Key.y + robot.y + tsize.y) % tsize.y), robot, ret);
    return ret;
}

void visualise(Dictionary<(int x, int y), List<(int x, int y)>> grid)
{
    for (int y = 0; y < tsize.y; y++)
    {
        for (int x = 0; x < tsize.x; x++)
            if (grid.TryGetValue((x, y), out var robots))
                Console.Write(robots.Count);
            else
                Console.Write(".");
        Console.WriteLine();
    }
}

void placeRobot((int x, int y) pos, (int x, int y) val, Dictionary<(int x, int y), List<(int x, int y)>> grid)
{
    if (grid.TryGetValue(pos, out var gridValue))
        gridValue.Add(val);
    else
        grid[pos] = [val];
}