🌟 Advent of Code (AoC) 2024 🌟

<?php
$data = "https://adventofcode.com/2024/day/7/input";
$lines = array_map('rtrim', explode("\n", $data));

foreach ($lines as $key => $line) {
    $lines[$key] = explode(": ", $line);
}

$operators = ["+", "*"];
$sumOfValidCalculations = 0;

foreach ($lines as $line) {

    $line[1] = explode(" ", $line[1]);
    $line[1] = array_map('intval', $line[1]);
    $intVal = intval($line[0]);
    $line[0] = array_map('intval', str_split($line[0]));

    $testGeneratedCombinations = generateCombinations($operators, count($line[1]) - 1, true);

    foreach ($testGeneratedCombinations as $testGeneratedCombination) {
        $testString = insertValuesBetweenOtherValues($testGeneratedCombination, $line[1]);
        echo "Testing string: " . $testString . "\n";
        $result = calcFromLeftToRightPerOperatorInString($testString);

        if ($result === $intVal) {
            echo "Result: " . $result . " = " . $intVal . " | Adding to sum!\n";
            $sumOfValidCalculations += $result;
            break;
        }
    }
}

echo "Part 1: " . $sumOfValidCalculations;
?>

function calcFromLeftToRightPerOperatorInString($stringToCalc)
{
    if (!preg_match('/^[\d\+\-\*\/]+$/', $stringToCalc)) {
        return "calcFromLeftToRightPerOperatorInString(): Valid Math String is: \d+ and/or +, -, *, /";
    }

    $numbers = preg_split('/[\+\-\*\/]/', $stringToCalc);
    $operators = preg_split('/[\d]+/', $stringToCalc, -1, PREG_SPLIT_NO_EMPTY);

    $result = $numbers[0];

    for ($i = 0; $i < count($numbers) - 1; $i++) {
        switch ($operators[$i]) {
            case "+":
                $result += $numbers[$i + 1];
                break;
            case "-":
                $result -= $numbers[$i + 1];
                break;
            case "*":
                $result *= $numbers[$i + 1];
                break;
            case "/":
                $result /= $numbers[$i + 1];
                break;
            default:
                return "calcFromLeftToRightPerOperatorInString(): Invalid operator found.";
        }
    }
    echo "Result for testing $stringToCalc: $result\n";
    return $result;
}

function generateCombinations($arrayValues, $numberOfPlaces, $returnAsArray = false)
{
    if (!is_array($arrayValues)) {
        throw new Exception("(generateCombinations): First parameter must be an array.");
    }
    if (!is_int($numberOfPlaces)) {
        throw new Exception("(generateCombinations): Second parameter must be an integer.");
    }

    $totalCombinations = pow(count($arrayValues), $numberOfPlaces);
    for ($i = 0; $i < $totalCombinations; $i++) {
        $combination = "";
        for ($j = 0; $j < $numberOfPlaces; $j++) {

            // We add the index of the arrayValues which is the floor of
            // the current index divided by the count of the arrayValues
            // which is then modulo the count of the arrayValues. This works
            // because the index will always be a multiple of the count of the
            // arrayValues, and then we just divide by the count of the arrayValues
            // to get the correct index of the arrayValues.
            // SÄKERT chatGPT, SÄKERT...
            $combination .= $arrayValues[floor($i / pow(count($arrayValues), $j)) % count($arrayValues)];
        }

        if ($returnAsArray) {
            yield str_split($combination);
        }
        else {
            yield $combination;
        }
    }
}

function insertValuesBetweenOtherValues($arrayReplaceValues, $arrayOtherValues)
{
    if (!is_array($arrayReplaceValues) || !is_array($arrayOtherValues)) {
        throw new Exception("(insertValuesBetweenOtherValues) :Both parameters must be arrays.");
    }

    if (count($arrayReplaceValues) >= count($arrayOtherValues)) {
        throw new Exception("(insertValuesBetweenOtherValues) :First array must have one element fewer than the second array.");
    }

    $result = "";
    for ($i = 0; $i < count($arrayOtherValues); $i++) {
        $result .= $arrayOtherValues[$i];
        if ($i < count($arrayReplaceValues)) {
            $result .= $arrayReplaceValues[$i];
        }
    }
    return $result;
}

// Jag ser att den inuti index för $arrayValues nyttjar floor() och vill dela något index med 
// upphöjningen  av antalet av $arrayvalues och sedan modulus av antalet $arrayValues. 
// Här är det något matematiskt som jag inte riktigt förstår mig på. Men funkar gör det!
$combination .= $arrayValues[floor($i / pow(count($arrayValues), $j)) % count($arrayValues)];

// Ok, vad jag ser är att kombinationsantalet är exponentprodukten 
// som den vill dela och jämna ut utifrån. Något åt det hållet, må tro?

<?php
// // Part 2: First prepare values with fresh values
$data = "https://adventofcode.com/2024/day/7/input";
$lines2 = array_map('rtrim', explode("\n", $data));
foreach ($lines2 as $key => $line2) {
    $lines2[$key] = explode(": ", $line2);
}
$operators = ["+", "*", "|"];
$sumOfValidCalculations = 0;

foreach ($lines2 as $line2) {

    // Split and convert to an array of integers
    $line2[1] = explode(" ", $line2[1]);
    $line2[1] = array_map('intval', $line2[1]);
    $intVal = intval($line2[0]);
    $line2[0] = array_map('intval', str_split($line2[0]));

    $testGeneratedCombinations = generateCombinations($operators, count($line2[1]) - 1, true);

    foreach ($testGeneratedCombinations as $testGeneratedCombination) {
        $testString = insertValuesBetweenOtherValues($testGeneratedCombination, $line2[1]);
        $result = calcFromLeftToRightPerOperatorInString($testString);

        if ($result === $intVal) {
            $sumOfValidCalculations += $result;
            echo "Result: " . $result . " = " . $intVal . " | Adding to sum! | Sum so far: $sumOfValidCalculations \n";
            break;
        } else {
            echo "Result: " . $result . " != " . $intVal . " | Skipping! | Sum so far: $sumOfValidCalculations \n";
        }
    }
}
echo "Part 2: " . $sumOfValidCalculations;

// From: _helpers.php
function calcFromLeftToRightPerOperatorInString($stringToCalc)
{
    if (!preg_match('/^[\d\+\-\*\/\|]+$/', $stringToCalc)) {
        return "calcFromLeftToRightPerOperatorInString(): Valid Math String is: \d+ and/or +, -, *, /, or |";
    }

    $numbers = preg_split('/[\+\-\*\/\|]/', $stringToCalc);
    $operators = preg_split('/[\d]+/', $stringToCalc, -1, PREG_SPLIT_NO_EMPTY);
    $result = $numbers[0];

    for ($i = 0; $i < count($numbers) - 1; $i++) {
        switch ($operators[$i]) {
            case "+":
                $result = intval($result);
                $result += $numbers[$i + 1];
                break;
            case "-":
                $result = intval($result);
                $result -= $numbers[$i + 1];
                break;
            case "*":
                $result = intval($result);
                $result *= $numbers[$i + 1];
                break;
            case "/":
                $result = intval($result);
                $result /= $numbers[$i + 1];
                break;
            case "|":
                $result = (string)$result . (string)$numbers[$i + 1];
                $result = intval($result);
                break;
            default:
                return "calcFromLeftToRightPerOperatorInString(): Invalid operator found.";
        }
    }
    echo "Calculated from Left->Right: $stringToCalc = $result\n";
    return $result;
}

public class Solver
{
    private struct File(int id, int index, bool isEmpty)
    {
        public int Id { get; set; } = id;
        public int Index { get; set; } = index;
        public bool IsEmpty { get; set; } = isEmpty;
        public long Checksum => Id * Index;
    }
    
    public static long Run_PartOne(string input)
    {
        // Parse string
        var numbers = input.Select(c => int.Parse(c.ToString())).ToList();

        // Generate filestructure
        List<File> files = new List<File>();
        for (int i = 0; i < numbers.Count; i++)
        {
            var count = numbers[i];
            
            for (int j = 0; j < count; j++)
            {
                files.Add(new File(i / 2, i, i % 2 != 0));
            }
        }

        // Rearrange files
        bool isDone = false;
        int startIndex = 0;
        for (int i = files.Count - 1; i > 0 && !isDone; i--)
        {
            var fileA = files[i];
            if (fileA.IsEmpty) continue;
            
            for (int j = startIndex; j < files.Count; j++)
            {
                var fileB = files[j];
                if (!fileB.IsEmpty) continue;
                if (j > i)
                {
                    isDone = true;
                    break;
                }

                files[i] = new File(fileB.Id, i, fileB.IsEmpty);
                files[j] = new File(fileA.Id, j, fileA.IsEmpty);
                startIndex = j + 1;
                break;
            }
            if (isDone) break;
        }
        
        // Re-index files
        for (int i = 0; i < files.Count; i++)
        {
            files[i] = new File(files[i].Id, i, files[i].IsEmpty);
        }

        // Validate checksum
        return files.Sum(file => file.IsEmpty ? 0L : file.Checksum);
    }
    
    public static long Run_PartTwo(string input)
    {
        // Parse string
        var numbers = input.Select(c => int.Parse(c.ToString())).ToList();
        
        // Generate filestructure
        List<File> files = new List<File>();
        for (int i = 0; i < numbers.Count; i++)
        {
            var count = numbers[i];
            
            for (int j = 0; j < count; j++)
            {
                files.Add(new File(i / 2, i, i % 2 != 0));
            }
        }
        
        // Rearrange files
        for (int i = files.Count - 1; i > 0; i--)
        {
            var fileA = files[i];
            if (fileA.IsEmpty)
            {
                continue;
            }
           
            // Get size for files
            var numberOfFiles = 0;
            for (int j = i; j > 0; j--)
            {
                if (files[j].Id != fileA.Id)
                {
                    break;
                }
                
                numberOfFiles++;
            }

            // Make sure files fit
            bool fileFits = false;
            int fitIndex = 0;
            for (int j = 0; j < files.Count && j < i; j++)
            {
                if (!files[j].IsEmpty) continue;
                
                int emptyFileCount = 1;
                for (var k = j + 1; k < numberOfFiles + j && k < files.Count; k++)
                {
                    if (!files[k].IsEmpty)
                    {
                        break;
                    }
                    emptyFileCount++;
                    if (emptyFileCount == numberOfFiles) break;
                }

                if (emptyFileCount != numberOfFiles)
                {
                    j += emptyFileCount - 1;
                    continue;
                }
                
                fileFits = true;
                fitIndex = j;
                break;
            }
            if (!fileFits)
            {
                i -= numberOfFiles - 1;
                continue;
            }

            // Move files
            int rightIndex = i;
            for (int j = fitIndex; j < fitIndex + numberOfFiles; j++)
            {
                var fileB = files[j];
                
                files[rightIndex] = new File(fileB.Id, rightIndex, fileB.IsEmpty);
                files[j] = new File(fileA.Id, j, fileA.IsEmpty);
                rightIndex--;
            }
            i -= numberOfFiles - 1;
        }
       
        // Re-index files
        long sum = 0L;
        for (int i = 0; i < files.Count; i++)
        {
            files[i] = new File(files[i].Id, i, files[i].IsEmpty);
            
            if(files[i].IsEmpty) continue;
            
            sum += files[i].Checksum;
        }
     
        // Validate checksum
        return sum;
    }
}

l= [int(digit) for digit in open("input09.txt", "r").read().strip()]

def split_input(l):
    files, gaps = [], []
    pos = 0
    for i, digit in enumerate(l):
        if i % 2 == 0:
            files.append([pos, digit, i // 2])
        else:
            if digit:
                gaps.append([pos, digit])
        pos += digit
    return files, gaps, []

def place_file1(pos, size, id):
    while size and gaps and gaps[0][0] < pos:
        pos2, size2 = gaps.pop(0)
        msize = min(size, size2)
        compacted.append([pos2, msize, id])
        size -= msize
        if size:
            files.append((pos, size, id))
        pos2 += msize
        size2 -= msize
        if size2 > 0:
            gaps.insert(0, [pos2, size2])
        return
    if size:
        compacted.append([pos, size, id])

def place_file2(pos, size, id):
    for i in range(len(gaps)):
        if gaps[i][0] < pos and gaps[i][1] >= size:
            pos2, size2 = gaps.pop(i)
            compacted.append([pos2, size, id])
            pos2 += size
            size2 -= size
            if size2 > 0:
                gaps.insert(i, [pos2, size2])
            return
    compacted.append([pos, size, id])

for f in [place_file1, place_file2]:
    files, gaps, compacted = split_input(l)
    while files:
        pos, size, id = files.pop()
        f(pos, size, id)
    print(sum([sum([x for x in range(pos, pos + n)]) * id for pos, n, id in compacted]))

var line = File.ReadAllText("input.txt");
(long sumpart1, long sumpart2) = (0, 0);

bool file = true;
int filecounter = 0;
List<(int value, bool empty)> disklist = [];
List<(int value, bool empty, int length)> disklist2 = [];
for (int i = 0; i < line.Length; i++)
{
    int sectorlength = line[i] & 15;
    if (file)
    {
        disklist2.Add((filecounter, false, sectorlength));
        for (int x = 0; x < sectorlength; x++)
        {
            disklist.Add((filecounter, false));
        }
        filecounter++;
        file = false;
    }
    else
    {
        disklist2.Add((0, true, sectorlength));
        for (int x = 0; x < sectorlength; x++)
        {
            disklist.Add((0, true));
        }
        file = true;
    }
}

var disk1 = disklist.ToArray();

int backwards = disk1.Length - 1;
// part 1
for (int i = 0; i < disk1.Length; i++)
{
    if (!disk1[i].empty)
        continue;
    while (backwards > i)
        if (disk1[backwards].empty)
            backwards--;
        else
            break;
    (disk1[i], disk1[backwards]) = (disk1[backwards], disk1[i]);
}


for (int i = 0; i < disk1.Length; ++i)
{
    sumpart1 += i * disk1[i].value;
}

// part 2
List<(long value, bool empty, int length)> p2list = [];

while (true)
{
    var curr = disklist2.First();
    if (!curr.empty)
    {
        p2list.Add(curr);
        disklist2.Remove(curr);
    }
    else // curr is empty
    {
        int length = curr.length;
        while (length > 0)
        {
            var last_matches = disklist2.Where(x => !x.empty && x.length <= length);
            if (last_matches.Count() == 0)
                break;
            var last_match = last_matches.Last();
            length -= last_match.length;
            p2list.Add(last_match);
            var last_idx = disklist2.IndexOf(last_match);
            disklist2[last_idx] = (0, true, last_match.length);
            disklist2.Remove(last_match);
            
        }
        if (length > 0)
        {
            p2list.Add((0, true, length));
        }
        disklist2.Remove(curr);
    }
    if (disklist2.Count == 0)
        break;
}



List<(long value, bool empty)> disk2 = [];
foreach (var sektor in p2list)
{
    for (int i = 0; i < sektor.length; i++)
    {
        disk2.Add((sektor.value, sektor.empty));
    }
}

for (int i = 0; i < disk2.Count; ++i)
{
    sumpart2 += i * disk2[i].value;
}

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

use std::array::from_fn;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::fs;
use std::iter::repeat;

pub const INPUT_FILE: &str = "input.txt";
pub const FREE_BLOCK: Block = u16::MAX;

pub type Block = u16;

#[derive(Eq, PartialEq)]
struct FreeRange {
    begin: usize,
    end: usize,
}

struct FreeBlocks {
    sizes: [BinaryHeap<FreeRange>; 10],
}

impl Ord for FreeRange {
    fn cmp(&self, other: &Self) -> Ordering {
        other.begin.cmp(&self.begin)
    }
}

impl PartialOrd for FreeRange {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.begin.partial_cmp(&self.begin)
    }
}

pub fn read_blocks(path: &str) -> Vec<Block> {
    let content = fs::read_to_string(path).expect("Failed to read file");
    let mut blocks = Vec::new();
    let mut id: Block = 0;

    for (offset, length_ch) in content.trim_ascii_end().chars().enumerate() {
        let length = length_ch.to_digit(10).unwrap() as usize;
        if offset % 2 == 0 {
            blocks.extend(repeat(id).take(length));
            id += 1;
        } else {
            blocks.extend(repeat(FREE_BLOCK).take(length));
        }
    }
    blocks
}

pub fn part1(blocks: &[Block]) -> usize {
    let mut compacted_blocks = blocks.to_vec();
    let mut free_offset = 0;
    let next_free_offset = |offset: usize, bs: &[Block]| {
        let mut new_offset = offset;
        while bs[new_offset] != FREE_BLOCK {
            new_offset += 1;
        }
        new_offset
    };
    let mut block_offset = compacted_blocks.len() - 1;
    let next_block_offset = |offset: usize, bs: &[Block]| {
        let mut new_offset = offset;
        while bs[new_offset] == FREE_BLOCK {
            new_offset -= 1;
        }
        new_offset
    };
    loop {
        free_offset = next_free_offset(free_offset, &compacted_blocks);
        block_offset = next_block_offset(block_offset, &compacted_blocks);
        if free_offset > block_offset {
            break;
        }
        compacted_blocks.swap(free_offset, block_offset);
    }
    checksum(&compacted_blocks[0..free_offset])
}

pub fn part2(blocks: &[Block]) -> usize {
    let mut compacted_blocks = blocks.to_vec();
    let mut free_blocks = find_free_blocks(&compacted_blocks);
    let mut offset = compacted_blocks.len() - 1;
    let mut id = Block::MAX;
    loop {
        while compacted_blocks[offset] >= id {
            offset -= 1;
        }
        let last = offset;
        id = compacted_blocks[offset];
        if id == 0 {
            break;
        }
        while compacted_blocks[offset] == id {
            offset -= 1;
        }
        let size = last - offset;
        if let Some(best_sz) = get_best_free_range_size(&free_blocks, offset, size) {
            let mut free_range = free_blocks.sizes[best_sz].pop().unwrap();
            for i in 0..size {
                compacted_blocks.swap(free_range.begin + i, offset + 1 + i);
            }
            free_range.begin += size;
            if free_range.begin < free_range.end && free_range.begin < offset {
                free_blocks.sizes[free_range.end - free_range.begin].push(free_range);
            }
        }
    }
    checksum(&compacted_blocks)
}

fn get_best_free_range_size(
    free_blocks: &FreeBlocks,
    max_offset: usize,
    size: usize,
) -> Option<usize> {
    let mut best_sz = None;
    let mut best_offset = 0;
    for sz in size..free_blocks.sizes.len() {
        if !free_blocks.sizes[sz].is_empty() {
            let offset = free_blocks.sizes[sz].peek().unwrap().begin;
            if offset <= max_offset && (best_sz.is_none() || best_offset > offset) {
                best_sz = Some(sz);
                best_offset = offset;
            }
        }
    }
    best_sz
}

fn find_free_blocks(blocks: &[Block]) -> FreeBlocks {
    let mut sizes = from_fn(|_| BinaryHeap::new());
    let mut offset = 0;
    while offset < blocks.len() {
        if blocks[offset] != FREE_BLOCK {
            offset += 1;
            continue;
        }
        let free_block_start = offset;
        loop {
            offset += 1;
            if blocks[offset] != FREE_BLOCK {
                break;
            }
        }
        let free_range = FreeRange {
            begin: free_block_start,
            end: offset,
        };
        sizes[offset - free_block_start].push(free_range);
    }
    FreeBlocks { sizes }
}

fn checksum(blocks: &[Block]) -> usize {
    blocks
        .iter()
        .enumerate()
        .filter_map(|(offset, &id)| {
            if id == FREE_BLOCK {
                None
            } else {
                Some(offset * id as usize)
            }
        })
        .sum()
}

fn main() {
    let blocks = read_blocks(&INPUT_FILE);
    println!("part 1: {}", part1(&blocks));
    println!("part 2: {}", part2(&blocks));
}

import numpy as np

filename = "input10.txt"

# Read the file and create a 2D numpy array
a = np.array([[int(c) for c in line.strip()] for line in open(filename, "r").readlines()])

print(a)

# Pad the array with -1 all around
padded_a = np.pad(a, pad_width=1, mode='constant', constant_values=-1)

print(padded_a)

# Define the find_path function (updated implementation)
def find_path(position, peaks):
    x, y = position
    current_value = padded_a[x, y]
    next_value = current_value + 1
    print(f"Finding path from position: {position}, current value: {current_value}")

    # If the current value is 9, return 1
    if current_value == 9:
        peaks.add(position)
        return 1

    # Mark the current position as visited

    # Check surrounding elements and sum the results of recursive calls
    total_paths = 0
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_x, new_y = x + dx, y + dy
        new_position = (new_x, new_y)
        if padded_a[new_x, new_y] == next_value:
            total_paths += find_path(new_position, peaks)

    return total_paths

# Find the positions of all zeros in the array
zero_positions = np.argwhere(padded_a == 0)

# Iterate over the positions and call find_path with each position
s1 = 0
s2 = 0
for pos in zero_positions:
    peaks = set()
    s2 += find_path(tuple(pos), peaks)
    s1 += len(peaks)

print(f"Total paths: {s, s2}")

using System.Diagnostics;
using Position = (int x, int y);
Stopwatch sw = Stopwatch.StartNew();
var lines = File.ReadAllLines("input.txt");
(int sumpart1, int sumpart2, int max) = (0, 0, lines.Length); 
Dictionary<Position, int> grid = [];
List<Position> heads = [];
for (int x = 0; x < max; x++)
    for (int y = 0; y < max; y++)
    {
        var val = lines[x][y] & 15;
        grid[(x, y)] = val;
        if (val == 0)
            heads.Add((x, y));
    }

foreach (var head in heads)
{
    HashSet<Position> found = [];
    sumpart2 += ascend(grid, head, 0, max, found);
    sumpart1 += found.Count;
}

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

IEnumerable<(int x, int y)> neighbours(Position pos, int max)
{
    Position[] rel_pos = [(0, 1), (1, 0), (0, -1), (-1, 0)];
    foreach (var rel in rel_pos)
    {
        var new_pos = (pos.x + rel.x, pos.y + rel.y);
        if (inRange(new_pos, max))
            yield return new_pos;
    }
    yield break;
}

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

int ascend(Dictionary<Position, int> grid, Position pos, int sought, int max, HashSet<Position> found)
{
    var curr = grid[pos];
    if (curr == sought)
    {
        if (sought == 9)
        {
            found.Add(pos);
            return 1;
        }
        int retval = 0;
        foreach (var neighbour in neighbours(pos, max))
            retval += ascend(grid, neighbour, sought + 1, max, found);
        return retval;
    }
    else
        return 0;
}

use std::fs::read_to_string;

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

pub fn read_map(path: &str) -> (Vec<Vec<u8>>, Vec<(i8, i8)>) {
    let content = read_to_string(path).expect("Failed to read file");
    let mut map = Vec::new();
    let mut start_positions = Vec::new();
    for (y, line) in content.lines().enumerate() {
        let row: Vec<u8> = line
            .chars()
            .enumerate()
            .map(|(x, c)| {
                let digit = c.to_digit(10).expect("Not a digit") as u8;
                if digit == 0 {
                    start_positions.push((x as i8, y as i8))
                }
                digit
            })
            .collect();
        map.push(row);
    }
    (map, start_positions)
}

pub fn part1(map: &[Vec<u8>], start_positions: &[(i8, i8)]) -> u32 {
    count_trails(map, start_positions, true)
}

pub fn part2(map: &[Vec<u8>], start_positions: &[(i8, i8)]) -> u32 {
    count_trails(map, start_positions, false)
}

fn count_trails(map: &[Vec<u8>], start_positions: &[(i8, i8)], count_trailheads: bool) -> u32 {
    let height = map.len() as i8;
    let width = map[0].len() as i8;
    let get_adjacent_positions = |x: i8, y: i8| {
        [
            if x > 0 { Some((x - 1, y)) } else { None },
            if x < width - 1 { Some((x + 1, y)) } else { None },
            if y > 0 { Some((x, y - 1)) } else { None },
            if y < height - 1 { Some((x, y + 1)) } else { None },
        ]
    };
    let mut visited = vec![0u64; map.len()];
    let mut trails = Vec::new();
    let mut num_trails = 0;
    for start_position in start_positions {
        if count_trailheads {
            for visited_row in &mut visited {
                *visited_row = 0;
            }
        }
        trails.push((*start_position, 0));
        while !trails.is_empty() {
            let ((x, y), height) = trails.pop().unwrap();
            if height == 9 {
                num_trails += 1;
            } else {
                let next_height = height + 1;
                for adj_pos in get_adjacent_positions(x, y) {
                    if let Some((adj_x, adj_y)) = adj_pos {
                        if map[adj_y as usize][adj_x as usize] == next_height
                            && (!count_trailheads || visited[adj_y as usize] & (1 << adj_x) == 0)
                        {
                            visited[adj_y as usize] |= 1 << adj_x;
                            trails.push(((adj_x, adj_y), next_height));
                        }
                    }
                }
            }
        }
    }
    num_trails
}

fn main() {
    let (map, start_positions) = read_map(&INPUT_FILE);
    println!("part 1: {}", part1(&map, &start_positions));
    println!("part 2: {}", part2(&map, &start_positions));
}

def read_map(file_path):
    with open(file_path, 'r') as f:
        return [[int(c) for c in line.strip()] for line in f]


def analyze_paths(grid):
    rows, cols = len(grid), len(grid[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    unique_paths_count = 0
    unique_reachable = set()

    def dfs(r, c, start, path_seen):
        nonlocal unique_paths_count
        if grid[r][c] == 9:
            unique_paths_count += 1  # Count all paths to '9'
            # Count unique '0' -> '9' pairs
            unique_reachable.add((start, (r, c)))
            return
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in path_seen and grid[nr][nc] == grid[r][c] + 1:
                dfs(nr, nc, start, path_seen | {(nr, nc)})

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0:
                dfs(r, c, (r, c), {(r, c)})

    return unique_paths_count, len(unique_reachable)


if __name__ == "__main__":
    file_path = "input.txt"
    grid = read_map(file_path)
    total_paths, unique_pairs = analyze_paths(grid)

    print(f"Total unique paths: {unique_pairs}")
    print(f"Total paths: {total_paths}")

from collections import deque


def parse_map(input_map):
    return [list(map(int, line.strip())) for line in input_map.splitlines()]


def find_trailheads(map_data):
    trailheads = []
    for i, row in enumerate(map_data):
        for j, height in enumerate(row):
            if height == 0:
                trailheads.append((i, j))
    return trailheads


def find_hiking_trails(map_data, start):
    rows, cols = len(map_data), len(map_data[0])
    queue = deque([(start, [start])])
    trails = set()

    while queue:
        (x, y), path = queue.popleft()
        current_height = map_data[x][y]

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy

            if 0 <= nx < rows and 0 <= ny < cols:
                next_height = map_data[nx][ny]
                if next_height == current_height + 1 and (nx, ny) not in path:
                    new_path = path + [(nx, ny)]
                    queue.append(((nx, ny), new_path))

                    if next_height == 9:
                        trails.add(tuple(new_path))

    return trails


def calculate_trailhead_scores(map_data):
    trailheads = find_trailheads(map_data)
    total_score = 0

    for trailhead in trailheads:
        trails = find_hiking_trails(map_data, trailhead)
        total_score += len(set(trail[-1] for trail in trails))

    return total_score


def calculate_trailhead_ratings(map_data):
    trailheads = find_trailheads(map_data)
    total_rating = 0

    for trailhead in trailheads:
        trails = find_hiking_trails(map_data, trailhead)
        total_rating += len(trails)

    return total_rating


if __name__ == "__main__":
    with open('input.txt', 'r') as file:
        file_content = file.read()
    map_data = parse_map(file_content)

    # Part 1
    trailhead_score = calculate_trailhead_scores(map_data)
    print(f"Sum of trailhead scores (Part 1): {trailhead_score}")

    # Part 2
    trailhead_rating = calculate_trailhead_ratings(map_data)
    print(f"Sum of trailhead ratings (Part 2): {trailhead_rating}")

public class Solver
{
    private enum Direction { Up, Down, Left, Right }
    private static (int x, int y) GetCoordAtDirection(int xPos, int yPos, Direction dir)
    {
        return dir switch
        {
            Direction.Up => (xPos, yPos - 1),
            Direction.Down => (xPos, yPos + 1),
            Direction.Left => (xPos - 1, yPos),
            Direction.Right => (xPos + 1, yPos),
            _ => throw new ArgumentOutOfRangeException(nameof(dir), dir, null)
        };
    }

    private static bool IsDirValid(int xPos, int yPos, Direction dir, int width, int height)
    {
        return dir switch
        {
            Direction.Up => yPos - 1 >= 0,
            Direction.Down => yPos + 1 < height,
            Direction.Left => xPos - 1 >= 0,
            Direction.Right => xPos + 1 < width,
            _ => false
        };
    }
    
    private static List<(int x, int y)> GetAvailableNodes(int[,] grid, int x, int y)
    {
        var nextAvailablePositions = new List<(int x, int y)>();
        foreach (var dir in Enum.GetValues<Direction>())
        {
            if (!IsDirValid(x, y, dir, grid.GetLength(1), grid.GetLength(0))) continue;
            var coord = GetCoordAtDirection(x, y, dir);

            if (grid[coord.y, coord.x] == (grid[y, x] + 1))
            {
                nextAvailablePositions.Add((coord.x, coord.y));
            }
        }

        return nextAvailablePositions;
    }

    private static (int uniqueEnds, int numberOfPaths) GetNumberOfPaths(int[,] grid, int x, int y)
    {
        HashSet<(int x, int y)> visited = [];
        int numPaths = 0;
        
        var nextAvailablePositions = GetAvailableNodes(grid, x, y);
        TraverseGrid(nextAvailablePositions);

        return (visited.Count, numPaths);

        void TraverseGrid(List<(int x, int y)> nodesToCheck)
        {
            foreach (var node in nodesToCheck)
            {
                if (grid[node.y, node.x] == 9)
                {
                    numPaths++;
                    visited.Add((node.x, node.y));
                }
                else
                {
                    var newNodes = GetAvailableNodes(grid, node.x, node.y);
                    TraverseGrid(newNodes);
                }
            }
        }
    }
    
    private static (int, int) ParseGrid(int[,] grid)
    {
        var unique = 0;
        var num = 0;
        
        for (var y = 0; y < grid.GetLength(0); y++)
        {
            for (var x = 0; x < grid.GetLength(1); x++)
            {
                if (grid[y, x] != 0) continue;

                var res = GetNumberOfPaths(grid, x, y);
                unique += res.uniqueEnds;
                num += res.numberOfPaths;
            }
        }

        return (unique, num);
    }
    
    private static int[,] GetGrid(string input)
    { 
        var lines = input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries);
        var height = lines.Length;
        var width = lines[0].Length;
        var grid = new int[width, height];
        
        for (var y = 0; y < height; y++)
        {
            for (var x = 0; x < width; x++)
            {
                grid[y, x] =  int.Parse(lines[y][x].ToString());
            }
        }

        return grid;
    }
    
    public static int Run_PartOne(string input)
    {
        // Parse string
        var grid = GetGrid(input);

        var sum = ParseGrid(grid).Item1;
      
        return sum;
    }
    
    public static int Run_PartTwo(string input)
    {
        var grid = GetGrid(input);

        var sum = ParseGrid(grid).Item2;
        return sum;
    }
}

from collections import Counter

def handle_stone(stone, times, output):
    s = str(stone)
    if stone == 0:
        output[stone + 1] += times
    elif (l := len(s)) % 2 == 0:
        output[int(s[0:l//2])] += times
        output[int(s[l//2:])] += times
    else:
        output[stone * 2024] += times

def blink(input):
    output = Counter()
    for stone, times in input.items():
        handle_stone(stone, times, output)
    return output
    
for part in [25, 75]:
    c = Counter(int(i) for i in open("input11.txt", "r").read().split())
    for i in range(part):
        c = blink(c)
    print(sum(c.values()))

using System.Diagnostics;
Stopwatch sw = Stopwatch.StartNew();
var line = File.ReadAllText("input.txt").Split(' ');
Dictionary<string, long> dict = [];
foreach (var item in line)
    dict[item] = 1;

dict = blink_times(dict, 25);
Console.WriteLine("Part 1: " + dict.Sum(x => x.Value));
Console.WriteLine(sw.Elapsed);
dict = blink_times(dict, 50);
Console.WriteLine("Part 2: " + dict.Sum(x => x.Value));
Console.WriteLine(sw.Elapsed);

static Dictionary<string, long> blink(Dictionary<string, long> dict)
{
    Dictionary<string, long> ret = [];
    foreach (var item in dict)
    {
        if (item.Key == "0")
        {
            add(ret, "1", item.Value);
        }
        else if (item.Key.Length % 2 == 0)
        {
            add(ret, long.Parse(item.Key[(item.Key.Length / 2)..]).ToString(), item.Value);
            add(ret, long.Parse(item.Key[..(item.Key.Length / 2)]).ToString(), item.Value);
        }
        else
        {
            add(ret, (long.Parse(item.Key) * 2024).ToString(), item.Value);
        }
    }
    return ret;
    static void add(Dictionary<string, long> d, string k, long v)
    {
        if (d.TryGetValue(k, out long value))
            d[k] = value + v;
        else
            d[k] = v;
    }
}

static Dictionary<string, long> blink_times(Dictionary<string, long> dict, int times)
{
    for (int i = 0; i < times; i++)
    {
        var output = blink(dict);
        dict = output;
    }
    return dict;
}