🌟 Advent of Code (AoC) 2024 🌟

import numpy as np

def shift_slice(map, pos, slice, direction):
    for hit in np.where(slice == '.')[0]:
        if '#' in slice[:hit]:
            break
        slice[1:hit + 1] = slice[:hit]
        slice[0] = '.'
        pos = pos[0] + direction[0], pos[1] + direction[1]
        break
    return map, pos    

def up(map, pos):
    return shift_slice(map, pos, map[pos[0]::-1, pos[1]], (-1, 0))

def down(map, pos):
    return shift_slice(map, pos, map[pos[0]:, pos[1]], (1, 0))

def left(map, pos):
    return shift_slice(map, pos, map[pos[0], pos[1]::-1], (0, -1))

def right(map, pos):
    return shift_slice(map, pos, map[pos[0], pos[1]:], (0, 1))

def shift_boxes(map, pos, direction):
    def find_boxes(map, pos, direction):
        boxes, border = set(), set()
        stack = [pos]
        while stack:
            pos = stack.pop()
            boxes.add(pos)
            p0d = pos[0] + direction
            if map[(p0d , pos[1])] == '[':
                stack.extend([(p0d , pos[1]), (p0d , pos[1] + 1)])
            elif map[(p0d , pos[1])] == ']':
                stack.extend([(p0d , pos[1]), (p0d , pos[1] - 1)])
            else:
                border.add((p0d , pos[1]))
        return boxes, border

    boxes, border = find_boxes(map, pos, direction)
    if (map[tuple(zip(*border))] != '.').any():
        return map, pos
    shifted = np.full(map.shape, '.')
    shifted[tuple(zip(*boxes))] = map[tuple(zip(*boxes))]
    shifted = np.concatenate((shifted[-direction:], shifted[:-direction]), axis=0)
    map[tuple(zip(*(boxes | border)))] = shifted[tuple(zip(*(boxes | border)))]
    return map, (pos[0] + direction, pos[1])
    
def up2(map, pos):
    return shift_boxes(map, pos, -1)

def down2(map, pos):
    return shift_boxes(map, pos, +1)

def part(mp, f, target):
    mp = np.array([[c for c in r.strip()] for r in mp.split("\n")])
    pos = tuple(zip(*np.where(mp == '@')))[0]
    for m in "".join(moves.split("\n")):
        mp, pos = f[m](mp, pos)
    return sum(map((lambda p: 100 * p[0] + p[1]), zip(*np.where(mp == target))))

map1, moves = open("input15.txt", "r").read().split("\n\n")
map2 = map1.replace("#", "##").replace("O", "[]").replace(".", "..").replace("@", "@.")

print(*map(lambda x: part(*x), [(map1, {'^': up,  'v': down,  '<': left, '>': right}, 'O'), 
                                (map2, {'^': up2, 'v': down2, '<': left, '>': right}, '[')]))

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

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

type Vec2D = (i32, i32);

pub fn read_warehouse_and_moves(path: &str) -> (Vec<Vec<char>>, Vec2D, Vec<Vec2D>) {
    let content = read_to_string(path).expect("File does not exist");
    let mut sections = content.split("\n\n");
    let mut map = vec![];
    let mut start_position = (0, 0);
    for (y, line) in sections.next().unwrap().lines().enumerate() {
        map.push(
            line.chars()
                .enumerate()
                .map(|(x, c)| {
                    if c == '@' {
                        start_position = (x as i32, y as i32);
                        '.'
                    } else {
                        c
                    }
                })
                .collect(),
        );
    }
    let moves = sections
        .next()
        .unwrap()
        .chars()
        .filter_map(|c| match c {
            '^' => Some((0, -1)),
            'v' => Some((0, 1)),
            '<' => Some((-1, 0)),
            '>' => Some((1, 0)),
            _ => None,
        })
        .collect();

    (map, start_position, moves)
}

pub fn part1(initial_map: &[Vec<char>], start_pos: &Vec2D, moves: &[Vec2D]) -> usize {
    let mut map = initial_map.to_vec();
    let mut pos = *start_pos;
    for forward in moves {
        pos = try_move(&mut map, &pos, forward);
    }
    calculate_gps_sum(&map, 'O')
}

fn try_move(map: &mut Vec<Vec<char>>, pos: &Vec2D, forward: &Vec2D) -> Vec2D {
    let next_forward = |a: &Vec2D| (a.0 + forward.0, a.1 + forward.1);
    let next_pos = next_forward(pos);
    let mut front = next_pos;
    loop {
        let tile = map[front.1 as usize][front.0 as usize];
        if tile == '#' {
            return *pos;
        }
        if tile == '.' {
            map[front.1 as usize][front.0 as usize] = 'O';
            map[next_pos.1 as usize][next_pos.0 as usize] = '.';
            break;
        }
        front = next_forward(&front);
    }
    next_pos
}

fn calculate_gps_sum(map: &[Vec<char>], symbol: char) -> usize {
    let mut gps_sum = 0;
    for (y, row) in map.iter().enumerate() {
        for (x, &c) in row.iter().enumerate() {
            if c == symbol {
                gps_sum += y * 100 + x;
            }
        }
    }
    gps_sum
}

pub fn part2(initial_map: &[Vec<char>], start_pos: &Vec2D, moves: &[Vec2D]) -> usize {
    let mut map = to_wide_warehouse(initial_map);
    let mut pos = (start_pos.0 * 2, start_pos.1);
    for forward in moves {
        if forward.0 != 0 {
            pos = try_horizontal_move(&mut map, &pos, forward);
        } else {
            pos = try_vertical_move(&mut map, &pos, forward);
        }
    }
    calculate_gps_sum(&map, '[')
}

fn to_wide_warehouse(initial_map: &[Vec<char>]) -> Vec<Vec<char>> {
    let mut map = vec![vec!['.'; initial_map[0].len() * 2]; initial_map.len()];
    for (y, row) in initial_map.iter().enumerate() {
        for (x, &c) in row.iter().enumerate() {
            if c == 'O' {
                map[y][2 * x] = '[';
                map[y][2 * x + 1] = ']';
            } else if c == '#' {
                map[y][2 * x] = '#';
                map[y][2 * x + 1] = '#';
            }
        }
    }
    map
}

fn try_horizontal_move(map: &mut Vec<Vec<char>>, pos: &Vec2D, forward: &Vec2D) -> Vec2D {
    let next_forward = |a: &Vec2D| (a.0 + forward.0, a.1 + forward.1);
    let next_pos = next_forward(pos);
    let mut front = next_pos;
    loop {
        let tile = map[front.1 as usize][front.0 as usize];
        if tile == '#' {
            return *pos;
        }
        if tile == '.' {
            let row = &mut map[pos.1 as usize];
            let mut x = front.0;
            loop {
                row[x as usize] = row[(x - forward.0) as usize];
                x -= forward.0;
                if x == pos.0 {
                    break;
                }
            }
            break;
        }
        front = next_forward(&front);
    }
    next_pos
}

fn try_vertical_move(map: &mut Vec<Vec<char>>, pos: &Vec2D, forward: &Vec2D) -> Vec2D {
    let next_pos = (pos.0, pos.1 + forward.1);
    if map[next_pos.1 as usize][next_pos.0 as usize] == '.' {
        return next_pos;
    }
    let mut affected_boxes = Vec::new();
    let mut initial_xs = AHashSet::new();
    let mut y = next_pos.1;
    initial_xs.insert(pos.0);
    affected_boxes.push((initial_xs, pos.1 + forward.1));
    // Figure out if move is possible, if so what floor-tiles are affected
    loop {
        let xs = &affected_boxes.last().unwrap().0;
        if xs.iter().any(|&x| map[y as usize][x as usize] == '#') {
            return *pos;
        }
        if xs.iter().all(|&x| map[y as usize][x as usize] == '.') {
            break;
        }
        let row = &map[y as usize];
        let mut next_xs = AHashSet::new();
        for &x in xs {
            let tile_in_front = row[x as usize];
            if tile_in_front == '.' {
                continue;
            }
            next_xs.insert(x);
            if map[(y - forward.1) as usize][x as usize] != tile_in_front {
                if tile_in_front == ']' {
                    next_xs.insert(x - 1);
                } else {
                    next_xs.insert(x + 1);
                }
            }
        }
        y += forward.1;
        affected_boxes.push((next_xs, y));
    }
    // Update map
    for i in (1..affected_boxes.len()).rev() {
        let (prev_xs, from_y) = &affected_boxes[i - 1];
        let (xs, to_y) = &affected_boxes[i];
        for x in xs.iter() {
            map[*to_y as usize][*x as usize] = map[*from_y as usize][*x as usize];
        }
        for x in xs.difference(prev_xs) {
            map[*from_y as usize][*x as usize] = '.';
        }
    }
    map[next_pos.1 as usize][next_pos.0 as usize] = '.';
    next_pos
}

fn main() {
    let (map, start_pos, moves) = read_warehouse_and_moves("input.txt");
    println!("part 1: {}", part1(&map, &start_pos, &moves));
    println!("part 2: {}", part2(&map, &start_pos, &moves));
}

using System.Text;
var file = File.ReadAllText("input.txt").Split("\r\n\r\n");
var textgrid = file[0].Split("\r\n");
var moves = file[1].Replace("\r\n", "");
(int x, int y) robot1 = (0, 0);
(int x, int y) robot2 = (0, 0);
Dictionary<(int x, int y), char> grid1 = [];
Dictionary<(int x, int y), char> grid2 = [];
string[][] replacements = [["#", "##"], ["O", "[]"], [".", ".."], ["@", "@."]];
int gy = 0;
foreach (var line in textgrid)
{
    for (var gx = 0; gx < line.Length; gx++)
    {
        if (line[gx] == '@')
            robot1 = (gx, gy);
        grid1[(gx, gy)] = line[gx];
    }
    StringBuilder sb = new StringBuilder(line);
    foreach (var item in replacements)
        sb.Replace(item[0], item[1]);
    string line2 = sb.ToString();
    for (int gx = 0; gx < line2.Length; gx++)
    {
        if (line2[gx] == '@')
            robot2 = (gx, gy);
        grid2[(gx, gy)] = line2[gx];
    }
    gy++;
}

moveRobot1();
Console.WriteLine("Part 1: " + score(grid1));
moveRobot2();
Console.WriteLine("Part 2: " + score(grid2));

void moveRobot1()
{
    foreach (var move in moves)
    {
        (int dx, int dy) = move switch
        {
            '^' => (0, -1),
            '>' => (1, 0),
            'v' => (0, 1),
            _ => (-1, 0) // '<'
        };
        List<(char, (int x, int y))> positions = [('.', robot1)];
        var curr = robot1;
        bool canMove = true;
        while (true)
        {
            var currval = grid1[curr];
            (int x, int y) next = (curr.x + dx, curr.y + dy);
            var nextval = grid1[next];
            if (nextval == '#')
            {
                canMove = false;
                break;
            }
            else if (nextval == 'O')
            {
                positions.Add((currval, next));
            }
            else // '.'
            {
                positions.Add((currval, next));
                break;
            }
            curr = next;
        }
        if (canMove)
        {
            foreach (var pair in positions)
            {
                grid1[pair.Item2] = pair.Item1;
            }
            grid1[robot1] = '.';
            robot1 = (robot1.x + dx, robot1.y + dy);
        }
    }
}

void moveRobot2()
{
    foreach (var move in moves)
    {
        (int dx, int dy) = move switch
        {
            '^' => (0, -1),
            '>' => (1, 0),
            'v' => (0, 1),
            _ => (-1, 0) // '<'
        };
        LinkedList<(int x, int y)> targets = [];
        targets.AddLast(robot2);
        bool canMove = true;

        for (var node = targets.First; node != null; node = node.Next)
        {
            var curr = node.Value;
            (int x, int y) next = (curr.x + dx, curr.y + dy);
            if (targets.Contains(next))
                continue;
            var nextval = grid2[next];
            if (nextval == '#')
            {
                canMove = false;
                break;
            }
            if (nextval == '[')
            {
                targets.AddLast(next);
                targets.AddLast((next.x + 1, next.y));
            }
            if (nextval == ']')
            {
                targets.AddLast(next);
                targets.AddLast((next.x - 1, next.y));
            }
        }
        if (canMove)
        {
            var copy = grid2.ToDictionary();
            grid2[robot2] = '.';
            grid2[(robot2.x + dx, robot2.y + dy)] = '@';
            foreach (var pos in targets.Skip(1))
            {
                grid2[pos] = '.';
            }
            foreach (var pos in targets.Skip(1))
            {
                var next = (pos.x + dx, pos.y + dy);
                grid2[next] = copy[pos];
            }
            robot2 = (robot2.x + dx, robot2.y + dy);
        }
    }
}

static int score(Dictionary<(int x, int y), char> grid)
{
    int score = 0;
    foreach (var item in grid.Where(x => x.Value == 'O' || x.Value == '['))
    {
        score += 100 * item.Key.y + item.Key.x;
    }
    return score;
}

import heapq
from functools import reduce

def bfs(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    priority_queue = [(0, [start], (0, 1))] 
    
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited = {}
    best_score, best_paths = float('inf'), []
    
    while priority_queue:
        score, path, prev_dir = heapq.heappop(priority_queue)
        
        if path[0] == end:
            if score < best_score:
                best_score, best_paths = score, [path]
            elif score == best_score:
                best_paths.append(path)
            else:
                break
        
        for dir in dirs:
            if maze[nrow := path[0][0] + dir[0]][ncol := path[0][1] + dir[1]] != '#' and (nrow, ncol) not in path:
                new_score = score + 1 if dir == prev_dir else score + 1 + 1000 
                if (nrow, ncol, dir) not in visited or visited[(nrow, ncol, dir)] >= new_score:
                    visited[(nrow, ncol, dir)] = new_score
                    heapq.heappush(priority_queue, (new_score, [(nrow, ncol)] + path , dir))
    
    return best_paths, best_score

maze = [list(line.strip()) for line in open('input16.txt', 'r').readlines()]
paths, score = bfs(maze, (len(maze) - 2, 1), (1, len(maze[0]) - 2))

print(score, len(reduce(lambda acc, lst: acc.union(lst), paths, set())))

use ahash::AHashSet;
use std::{cmp::Reverse, collections::BinaryHeap, fs::read_to_string};

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

type Vec2D = (i32, i32);

#[derive(PartialEq, Eq)]
struct Node {
    score: usize,
    direction: usize,
    path: Vec<i32>,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.score.cmp(&other.score)
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

pub fn read_map(path: &str) -> (Vec<u8>, i32, Vec2D) {
    let content = read_to_string(path).expect("Failed to read the file");
    let lines: Vec<&str> = content.split('\n').collect();
    let mut map: Vec<u8> = Vec::new();
    let mut start: Vec2D = (0, 0);
    for (y, line) in lines.iter().enumerate() {
        for (x, ch) in line.chars().enumerate() {
            if ch == 'S' {
                start = (x as i32, y as i32);
            }
            map.push(ch as u8);
        }
    }
    (map, lines[0].len() as i32, start)
}

pub fn part1(map: &[u8], width: i32, start_pos: Vec2D) -> (usize, Vec<Vec<i32>>) {
    let mut best_score = usize::MAX;
    let mut paths = Vec::new();
    let mut visited = vec![usize::MAX; map.len() * 4];
    let mut queue = BinaryHeap::new();
    let start_index = start_pos.0 + width * start_pos.1;
    let visited_index = |index, direction| index as usize + direction as usize * map.len();

    queue.push(Reverse(Node {
        score: 0,
        direction: 0,
        path: vec![start_index],
    }));

    while let Some(Reverse(Node {
        score,
        direction,
        path,
    })) = queue.pop()
    {
        let index = *path.last().unwrap() as usize;
        if map[index] == b'E' {
            if score > best_score {
                break;
            }
            paths.push(path.clone());
            best_score = score;
            visited[visited_index(index, direction)] = score;
            continue;
        }

        for (nd, forward) in [(1, 0), (0, 1), (-1, 0), (0, -1)].iter().enumerate() {
            let next_index = (index as i32 + forward.0 + forward.1 * width) as usize;
            if nd ^ direction != 2 && map[next_index] != b'#' {
                let next_score = score + if direction == nd { 1 } else { 1000 + 1 };
                let vi = visited_index(next_index, nd);
                if visited[vi] >= next_score {
                    visited[vi] = next_score;
                    let mut next_path = path.clone();
                    next_path.push(next_index as i32);
                    queue.push(Reverse(Node {
                        score: next_score,
                        direction: nd,
                        path: next_path,
                    }));
                }
            }
        }
    }
    (best_score, paths)
}

pub fn part2(paths: &[Vec<i32>]) -> usize {
    let mut visited = AHashSet::new();
    for path in paths {
        for pos in path {
            visited.insert(pos);
        }
    }
    visited.len()
}

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

using System.Text.RegularExpressions;
var lines = File.ReadAllLines("input.txt");
var regex = new Regex(@(-?\d+));
long a = long.Parse(regex.Matches(lines[0])[0].Value);
long b = long.Parse(regex.Matches(lines[1])[0].Value);
long c = long.Parse(regex.Matches(lines[2])[0].Value);
List<int> program = regex.Matches(lines[4]).Select(x => int.Parse(x.Value)).ToList();

var output = runProgram(program, a, b, c);

Console.WriteLine("Part 1: " + string.Join(',', output));

static List<long> runProgram(List<int> program, long regA, long regB, long regC)
{
    List<long> output = [];
    int pc = 0;
    while (true)
    {
        if (pc >= program.Count)
            break;
        switch (program[pc])
        {
            case 0:
                inst_adv(program[pc + 1]);
                break;
            case 1:
                inst_bxl(program[pc + 1]);
                break;
            case 2:
                inst_bst(program[pc + 1]);
                break;
            case 3:
                inst_jnz(program[pc + 1]);
                break;
            case 4:
                inst_bxc(program[pc + 1]);
                break;
            case 5:
                inst_out(program[pc + 1]);
                break;
            case 6:
                inst_bdv(program[pc + 1]);
                break;
            case 7:
                inst_cdv(program[pc + 1]);
                break;
            default:
                break;
        }
    }
    return output;
    void inst_adv(int operand) // op 0
    {
        var denom = twopow(combo_operand(operand));
        regA /= denom;
        pc += 2;
    }

    void inst_bxl(int operand) // op 1
    {
        regB ^= operand;
        pc += 2;
    }

    void inst_bst(int operand) // op 2
    {
        var op = combo_operand(operand);
        regB = op % 8;
        pc += 2;
    }

    void inst_jnz(int operand) // op 3
    {
        if (regA == 0)
        {
            pc += 2;
            return;
        }
        pc = operand;
    }

    void inst_bxc(int operand) // op 4
    {
        regB ^= regC;
        pc += 2;
    }

    void inst_out(int operand) // op 5
    {
        var op = combo_operand(operand);
        output.Add(op % 8);
        pc += 2;
    }

    void inst_bdv(int operand) // op 6
    {
        var denom = twopow(combo_operand(operand));
        regB = regA / denom;
        pc += 2;
    }

    void inst_cdv(int operand) // op 7
    {
        var denom = twopow(combo_operand(operand));
        regC = regA / denom;
        pc += 2;
    }
    long combo_operand(long value)
    {
        return value switch
        {
            < 4 => value,
            4 => regA,
            5 => regB,
            6 => regC,
            _ => throw new ArgumentException("Invalid value for operand")
        };
    }
}

static long twopow(long value)
{
    return (long)(Math.Pow(2, value));
}

pub const INITIAL_A_PART_1: u64 = 17323786;
pub const WANTED_OUTPUT_PART2: &str = "2,4,1,1,7,5,1,5,4,1,5,5,0,3,3,0";

pub fn part1(initial_a: u64) -> String {
    program(initial_a)
        .iter()
        .map(|n| n.to_string())
        .collect::<Vec<_>>()
        .join(",")
}

pub fn part2(program_str: &str) -> u64 {
    let wanted_outputs = program_str
        .split(',')
        .map(|s| s.parse::<u8>().expect("Invalid number"))
        .collect::<Vec<_>>();
    let mut initial_as = vec![0u64];
    // This works because the program re-set B and C each iteration and divide A with 8 each round.
    // Must go backwards as the value of C depends on more than the 3 low bits of A.
    // However, terminal condition dictates that bit 4 and higher must be zero when producing the last
    // piece of output.
    // So go backwards and see what new low 3 bit value(s) that may produce the back-end part of the program.
    // Add one step until the whole program i reproduced
    for i in (0..wanted_outputs.len()).rev() {
        let wanted_slice = &wanted_outputs[i..];
        let mut new_initial_as = Vec::new();
        for initial_a in initial_as {
            for a_low in 0..8 {
                let candidate_a = (initial_a << 3) + a_low;
                if program(candidate_a) == wanted_slice {
                    new_initial_as.push(candidate_a);
                }
            }
        }
        initial_as = new_initial_as;
    }
    *initial_as.iter().min().unwrap()
}

fn program(initial_a: u64) -> Vec<u8> {
    let mut result = Vec::new();
    let mut a = initial_a;
    let mut b;
    let mut c;
    loop {
        // 1. bst A
        b = a % 8;
        // 2. blx 1
        b = b ^ 1;
        // 3. cdv B
        c = a / (1 << b);
        // 4. blx 5
        b = b ^ 5;
        // 5. bxc
        b = b ^ c;
        // 6. out B
        result.push((b % 8) as u8);
        // 7. adv 3
        a = a / 8;
        // 8. jnz 0
        if a == 0 {
            break;
        }
    }
    result
}

fn main() {
    println!("part 1: {}", part1(INITIAL_A_PART_1));
    println!("part 2: {}", part2(WANTED_OUTPUT_PART2));
}

use ahash::AHashSet;
use std::{cmp::Reverse, collections::BinaryHeap, fs::read_to_string};

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

type Vec2D = (i32, i32);

#[derive(PartialEq, Eq)]
struct Node {
    score: u32,
    direction: usize,
    step_index: usize,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.score.cmp(&other.score)
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

pub fn read_map(path: &str) -> (Vec<u8>, i32, Vec2D) {
    let content = read_to_string(path).expect("Failed to read the file");
    let lines: Vec<&str> = content.split('\n').collect();
    let mut map: Vec<u8> = Vec::new();
    let mut start: Vec2D = (0, 0);
    for (y, line) in lines.iter().enumerate() {
        for (x, ch) in line.chars().enumerate() {
            if ch == 'S' {
                start = (x as i32, y as i32);
            }
            map.push(ch as u8);
        }
    }
    (map, lines[0].len() as i32, start)
}

pub fn part1(map: &[u8], width: i32, start_pos: Vec2D) -> (u32, AHashSet<i32>) {
    let mut steps_storage = vec![(0 as u32, 0 as i32, 0 as usize); 200_000];
    let mut next_free_step = 0;
    let mut best_score = u32::MAX;
    let mut paths = Vec::new();
    let mut visited = vec![u32::MAX; map.len() * 4];
    let mut queue = BinaryHeap::new();
    let start_index = start_pos.0 + width * start_pos.1;
    let visited_index = |index, direction| index as usize + direction as usize * map.len();

    let initial_step = &mut steps_storage[next_free_step];
    next_free_step += 1;
    initial_step.1 = start_index;
    queue.push(Reverse(Node {
        score: 0,
        direction: 0,
        step_index: next_free_step - 1,
    }));

    while let Some(Reverse(Node {
        score,
        direction,
        step_index,
    })) = queue.pop()
    {
        let step = steps_storage[step_index];
        let map_index = step.1 as usize;
        if map[map_index] == b'E' {
            if score > best_score {
                break;
            }
            paths.push(step_index);
            best_score = score;
            visited[visited_index(map_index, direction)] = score;
            continue;
        }

        for (nd, forward) in [(1, 0), (0, 1), (-1, 0), (0, -1)].iter().enumerate() {
            let next_index = (map_index as i32 + forward.0 + forward.1 * width) as usize;
            if nd ^ direction != 2 && map[next_index] != b'#' {
                let next_score = score + if direction == nd { 1 } else { 1000 + 1 };
                let vi = visited_index(next_index, nd);
                if visited[vi] >= next_score {
                    visited[vi] = next_score;
                    let step = &mut steps_storage[next_free_step];
                    next_free_step += 1;
                    step.0 = next_score;
                    step.1 = next_index as i32;
                    step.2 = step_index;
                    queue.push(Reverse(Node {
                        score: next_score,
                        direction: nd,
                        step_index: next_free_step - 1,
                    }));
                }
            }
        }
    }
    let mut visited_pos = AHashSet::new();
    for start_step in paths {
        let mut step_index = start_step;
        loop {
            let step = steps_storage[step_index];
            visited_pos.insert(step.1);
            if step.0 == 0 {
                break;
            }
            step_index = step.2;
        }
    }

    (best_score, visited_pos)
}

pub fn part2(visited_pos: &AHashSet<i32>) -> usize {
    visited_pos.len()
}

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

from collections import Counter
import re

def part1(a, b, c, program):
    def operand(o):
        match o:
            case 0 | 1 | 2 | 3: return o
            case 4: return a
            case 5: return b
            case 6: return c

    ip, result = 0, []
    while ip < len(program):
        match program[ip]:
            case 0: 
                a, ip = a // (2 ** operand(program[ip + 1])), ip + 2
            case 1:
                b, ip = b ^ program[ip + 1], ip + 2
            case 2:
                b, ip = operand(program[ip + 1]) % 8, ip + 2
            case 3:
                ip = program[ip + 1] if a != 0 else ip + 2
            case 4:
                b, ip = b ^ c, ip + 2
            case 5:
                result.append(operand(program[ip + 1]) % 8)
                ip = ip + 2
            case 6: 
                b, ip = a // (2 ** operand(program[ip + 1])), ip + 2
            case 7: 
                c, ip = a // (2 ** operand(program[ip + 1])), ip + 2
    return ",".join(map(str, result))


def part2():
    def fun(a):
        l = []
        for i in range(16):
            l.append(((a % 8) ^ 6 ^ (a >> ((a % 8) ^ 3))) % 8)
            a = a >> 3
        return l

    base  = 32 * 1024 * 1024 * 1024 * 1024
    cands, solutions = set([0]), []
    for loop in range(18):
        new_cands = set()
        scale = 8 ** loop
        for c in cands:
            for i in range(1024):
                l = fun(base + c + i * scale)
                if l == program:
                    solutions.append(base + c + i * scale)
                if l[:loop + 1] == program[:loop + 1]:
                    new_cands.add(c + i * scale)
        cands = set([c % (scale * 8) for c in new_cands])
    return min(solutions)


integers = list(map(int, re.findall(r'\d+', open("input17.txt", 'r').read())))
a, b, c, program = integers[0], integers[1], integers[2], integers[3:]

print(part1(a, b, c, program), part2())

import numpy as np

maze = np.full((71,71), '.')
blocks = [tuple(map(int,l.split(","))) for l in open("input18.txt", 'r').readlines()]
maze[*zip(*blocks[:1024])] = '#'
maze = np.pad(maze, pad_width=1, mode='constant', constant_values='#')

def bfs(maze, start, end):
    queue = [[start]]
    visited = set()
    while queue:
        path = queue.pop(0)
        if path[0] == end:
            return path
        row, col = path[0]
        for dir in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nrow, ncol = row + dir[0], col + dir[1]
            if maze[nrow][ncol] == '.' and (nrow, ncol) not in visited:
                visited.add((nrow, ncol))
                queue.append([(nrow, ncol)] + path)
    return None

start, end = (1,1), (71,71)
path = bfs(maze, start, end)
for row, col in blocks[1024:]:
    maze[row + 1, col + 1] = '#'
    if not bfs(maze, start, end):
        print(f"Part 1:{len(path) - 1} Part 2: {row},{col}")
        break

using Position = (int x, int y);
int max = 70; //6; 
int stop_at = 1024; // 12
var lines = File.ReadAllLines("input.txt").Select(x => x.Split(',').Select(int.Parse).ToArray()).ToArray();
HashSet<Position> grid = [];
int count = 0;
foreach (var line in lines)
{
    if (count == stop_at)
        break;
    grid.Add((line[0], line[1]));
    count++;
}

Console.WriteLine("Part 1: " + navigate(grid));
Position sumpart2 = (0, 0);

for (int i = stop_at; i < lines.Count(); i++)
{
    grid.Add((lines[i][0], lines[i][1]));
    int ret = navigate(grid);
    if (ret == int.MaxValue)
    {
        sumpart2 = (lines[i][0], lines[i][1]);
        break;
    }
}
Console.WriteLine($"Part 2: {sumpart2.x},{sumpart2.y}");

int navigate(HashSet<Position> grid)
{
    Position start = (0, 0);
    Position end = (max, max);
    LinkedList<(Position position, int cost)> list = [];
    HashSet<Position> seen = [];
    list.AddLast((start, 0));
    for (var node = list.First; node != null; node = node.Next)
    {
        foreach (var n in neighbours(node.Value.position))
        {
            if (seen.Contains(n))
                continue;
            if (grid.Contains(n))
                continue;
            if (n == end)
            {
                return node.Value.cost + 1;
            }
            seen.Add(n);
            list.AddLast((n, node.Value.cost + 1));
        }
    }
    return int.MaxValue;
}

IEnumerable<Position> neighbours(Position pos)
{
    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))
            yield return new_pos;
    }
    yield break;
}

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

use std::collections::VecDeque;
use std::fs::read_to_string;

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

pub fn read_corrupted_addresses(path: &str) -> Vec<(i8, i8)> {
    read_to_string(path)
        .expect("Failed to read the file")
        .lines()
        .map(|line| {
            let parts: Vec<i8> = line
                .split(',')
                .map(|num| num.parse::<i8>().unwrap())
                .collect();
            (parts[0], parts[1])
        })
        .collect()
}

pub fn part1(corrupted_addresses: &[(i8, i8)], size: usize) -> u32 {
    bfs(corrupted_addresses, size).unwrap()
}

pub fn part2(corrupted_addresses: &[(i8, i8)], initial_lo: usize, size: usize) -> (i8, i8) {
    let mut lo = initial_lo;
    let mut hi = corrupted_addresses.len();
    while lo < hi {
        let mid = (hi + lo + 1) / 2;
        if bfs(&corrupted_addresses[..mid], size).is_none() {
            hi = mid - 1
        } else {
            lo = mid;
        }
    }
    corrupted_addresses[hi]
}

pub fn bfs(corrupted_addresses: &[(i8, i8)], size: usize) -> Option<u32> {
    let mut visited = vec![false; size * size];
    let mut map = vec![true; size * size];
    let mut queue = VecDeque::new();
    let get_index = |pos: (i8, i8)| pos.0 as usize + size * pos.1 as usize;
    let exit_pos = ((size - 1) as i8, (size - 1) as i8);

    for &pos in corrupted_addresses {
        map[get_index(pos)] = false;
    }
    queue.push_front(((0i8, 0i8), 0u32));
    while let Some((pos, steps)) = queue.pop_back() {
        if pos == exit_pos {
            return Some(steps);
        }
        let next_steps = steps + 1;
        for delta in [(0, 1), (1, 0), (0, -1), (-1, 0)] {
            let (x, y) = (pos.0 + delta.0, pos.1 + delta.1);
            if x < 0 || x >= size as i8 || y < 0 || y >= size as i8 {
                continue;
            }
            let index = get_index((x, y));
            if map[index] && !visited[index] {
                visited[index] = true;
                queue.push_front(((x, y), next_steps));
            }
        }
    }
    None
}

fn main() {
    let corrupted_addresses = read_corrupted_addresses(INPUT_FILE);
    println!("part 1: {}", part1(&corrupted_addresses[..1024], 71));
    let pos = part2(&corrupted_addresses, 1024, 71);
    println!("part 2: {},{}", pos.0, pos.1);
}

from collections import defaultdict
import heapq

class TrieNode:
    def __init__(self):
        self.children = [None] * 5
        self.is_match = False

    def insert(n, key):
        for level in range(len(key)):
            i = key[level]
            if not n.children[i]:
                n.children[i] = TrieNode()
            n = n.children[i]
        n.is_match = True

    def collect_matches(n, key):
        matches = []
        for level in range(len(key)):
            i = key[level]
            if not n.children[i]:
                break
            n = n.children[i]
            if n.is_match:
                matches.append(level + 1)
        return matches

def translate(s):
    return ["wubrg".index(c) for c in s]

def match(pattern, trie):
    priority_queue = [0]
    count = defaultdict(int)
    count[0] += 1
    
    while priority_queue:
        pos = heapq.heappop(priority_queue)
        if pos == len(pattern):
            return True, count[len(pattern)]
        matched_positions = TrieNode.collect_matches(trie, pattern[pos:])
        for match in matched_positions:
            npos = pos + match
            if npos not in priority_queue:
                heapq.heappush(priority_queue, npos)
            count[npos] += count[pos]
    return False, 0

towels, patterns = open("input19.txt").read().split('\n\n')
towels = list(map(translate, towels.split(', ')))
patterns = list(map(translate, patterns.strip().split('\n')))

root = TrieNode()
for t in towels:
    TrieNode.insert(root, t)

s1, s2 = 0, 0
for p in patterns:
    match_found, position_count = match(p, root)
    s1 += match_found
    s2 += position_count

print(s1, s2)

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

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

pub fn read_towels(path: &str) -> (Vec<String>, Vec<String>) {
    let content = read_to_string(path).expect("Failed to read the file");
    let mut lines = content.lines();
    let towels = lines
        .next()
        .unwrap()
        .split(", ")
        .map(|s| s.to_string())
        .collect();
    lines.next(); // Skip blank line
    let patterns = lines.map(|s| s.to_string()).collect();
    (towels, patterns)
}

pub fn part1(towels: &[String], patterns: &[String]) -> (usize, Vec<usize>) {
    let mut memoize = AHashMap::new();
    let results: Vec<usize> = patterns
        .iter()
        .map(|pattern| count_solutions(pattern, &towels, &mut memoize))
        .collect();
    let possible_designs = results.iter().filter(|&&n| n != 0).count();
    (possible_designs, results)
}

pub fn part2(possible_solutions: &[usize]) -> usize {
    possible_solutions.iter().sum()
}

fn count_solutions(
    pattern: &str,
    towels: &[String],
    memoize: &mut AHashMap<String, usize>,
) -> usize {
    if let Some(&result) = memoize.get(pattern) {
        return result;
    }
    if pattern.is_empty() {
        return 1;
    }
    let mut count = 0;
    for towel in towels {
        if pattern.starts_with(towel) {
            count += count_solutions(&pattern[towel.len()..], towels, memoize);
        }
    }
    memoize.insert(pattern.to_string(), count);
    count
}

fn main() {
    let (towels, patterns) = read_towels(INPUT_FILE);
    let (possible_designs, possible_solutions) = part1(&towels, &patterns);
    println!("part 1: {}", possible_designs);
    println!("part 2: {}", part2(&possible_solutions));
}

(int sumpart1, long sumpart2) = (0, 0);
var file = File.ReadAllLines("input.txt");
var towels = file[0].Split(", ").ToHashSet();
Dictionary<string, long> cache = [];
int maxlength = towels.MaxBy(x => x.Length)!.Length;
for (int i = 2; i < file.Length; i++)
{
    var line = file[i];
    long arr = arrangements(line);
    if (arr > 0)
    {
        sumpart1++;
        sumpart2 += arr;
    }
}

Console.WriteLine(sumpart1);
Console.WriteLine(sumpart2);

long arrangements(string line)
{
    if (string.IsNullOrWhiteSpace(line)) return 1;
    if (cache.TryGetValue(line, out var result)) return result;
    long count = 0;
    for (int i = 0; i <= Math.Min(line.Length, maxlength + 1); i++)
    {
        var first = line[0..i];
        var last = line[i..];
        if (towels.Contains(first))
            count += arrangements(last);
    }
    cache[line] = count;
    return count;
}

towels, patterns = open("input19.txt").read().split('\n\n')
towels, patterns = towels.split(', '), patterns.strip().split('\n')
 
def match_pattern(pat, pos):
    for i, p in enumerate(pos):
        for t in towels:
            if pat[i:].startswith(t):
                pos[i+len(t)] += p
    return p

l = [match_pattern(pat, [1] + [0] * len(pat)) for pat in patterns]
print(sum(map(bool, l)), sum(l))