🌟 Advent of Code (AoC) 2024 🌟

using Position = (int x, int y);
var lines = File.ReadAllLines("input.txt");
(int sumpart1, int sumpart2, int max) = (0, 0, lines.Length);
HashSet<Position> obstacles = [];
(Position start, Position end) = ((0, 0), (0, 0));
for (int y = 0; y < max; y++)
    for (int x = 0; x < max; x++)
    {
        if (lines[y][x] == '#')
            obstacles.Add((x, y));
        else if (lines[y][x] == 'S')
            start = ((x, y));
        else if (lines[y][x] == 'E')
            end = ((x, y));
    }
int initial_distance = navigate(obstacles, start, end, out var walkable);
int aim_for = initial_distance - 100;
walkable[end] = initial_distance;

Parallel.ForEach(walkable, cheat_start =>
{
    foreach (var cheat_end in walkable.Where(c_end => c_end.Value > cheat_start.Value && manhattan(c_end.Key, cheat_start.Key) <= 20))
    {
        int mdist = manhattan(cheat_end.Key, cheat_start.Key);
        int cost = (initial_distance - cheat_end.Value) + mdist + cheat_start.Value;
        if (cost <= aim_for)
        {
            if (mdist == 2)
                Interlocked.Increment(ref sumpart1);
            Interlocked.Increment(ref sumpart2);
        }
    }
});
Console.WriteLine("Part 1: " + sumpart1);
Console.WriteLine("Part 2: " + sumpart2);

int navigate(HashSet<Position> obstacles, Position start, Position end, out Dictionary<Position, int> cost)
{
    cost = [];
    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 (obstacles.Contains(n))
                continue;
            if (n == end)
                return node.Value.cost + 1;
            seen.Add(n);
            cost[n] = node.Value.cost + 1;
            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 (x, y) in rel_pos)
    {
        var new_pos = (pos.x + x, pos.y + 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);
int manhattan(Position pos1, Position pos2) => Math.Abs(pos1.x - pos2.x) + Math.Abs(pos1.y - pos2.y);

import numpy as np
from itertools import product

maze = np.array([list(l.strip()) for l in open("input20.txt").readlines()])

def find_path(maze):
    path = [(row, col) for row in range(len(maze)) for col in range(len(maze[0])) if maze[row][col] == 'S']
    while maze[r := path[0][0]][c := path[0][1]] != 'E':
        for dir in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            if maze[r + dir[0]][c + dir[1]] in '.E' and (r + dir[0], c + dir[1]) not in path:
                path.insert(0, (r + dir[0], c + dir[1]))
    return path

path_length = np.zeros_like(maze, dtype=int)
for i, (r, c) in enumerate(find_path(maze)[::-1]):
    path_length[r][c] = i + 1

def create_distance_diamond(a, center, radius):
    r, c = np.ogrid[:a.shape[0], :a.shape[1]]
    dist = abs(r - center[0]) + abs(c - center[1])
    mask = dist <= radius
    diamond = np.zeros_like(a, dtype=int)
    diamond[mask] = dist[mask]
    return diamond

def cheats_in_radius(radius):
    count = 0
    for rc in product(range(maze.shape[0]), range(maze.shape[1])):
        if path_length[rc] != 0:
            distance = create_distance_diamond(path_length, rc, radius)
            cheats = (np.abs((path_length - path_length[rc])) - distance)[(distance != 0) & (path_length != 0)]
            count += sum(cheats >= 100)
    return count // 2

print(*[cheats_in_radius(r) for r in [2, 20]])

use rayon::prelude::*;
use std::{collections::VecDeque, fs::read_to_string};

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

type Vec2D = (i16, i16);

pub fn read_map(path: &str) -> (Vec<u8>, usize, usize, 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::new();
    let mut end_pos = (0, 0);
    let border_thickness = 20;
    for (y, line) in lines.iter().enumerate() {
        for (x, ch) in line.chars().enumerate() {
            if ch == 'E' {
                end_pos = ((x + border_thickness) as i16, (y + border_thickness) as i16);
            }
            map.push(ch as u8);
        }
    }
    let width = lines[0].len();
    (
        add_border(map, width, border_thickness),
        width + 2 * border_thickness,
        border_thickness + 1,
        end_pos,
    )
}

fn add_border(grid: Vec<u8>, width: usize, border_thickness: usize) -> Vec<u8> {
    let height = grid.len() / width;
    let new_width = width + 2 * border_thickness;
    let new_height = height + 2 * border_thickness;
    let mut bordered_grid = vec![b'#'; new_width * new_height];
    for y in 0..height {
        for x in 0..width {
            bordered_grid[(y + border_thickness) * new_width + (x + border_thickness)] =
                grid[y * width + x];
        }
    }
    bordered_grid
}

pub fn solve(
    map: &[u8],
    width: usize,
    border_thickness: usize,
    end_pos: Vec2D,
    min_save: i16,
) -> (u32, u32) {
    let mut steps_to_end = vec![i16::MAX; map.len()];
    let mut queue = VecDeque::new();
    let mut race_distance = 0;
    queue.push_front((end_pos, 0));
    steps_to_end[end_pos.0 as usize + end_pos.1 as usize * width] = 0;
    while let Some(((x, y), steps)) = queue.pop_back() {
        let next_steps = steps + 1;
        for (dx, dy) in [(0, 1), (1, 0), (0, -1), (-1, 0)] {
            let next_pos = (x + dx, y + dy);
            let i = next_pos.0 as usize + next_pos.1 as usize * width;
            let tile = map[i];
            if tile != b'#' && steps_to_end[i] > next_steps {
                steps_to_end[i] = next_steps;
                queue.push_front((next_pos, next_steps));
                if tile == b'S' {
                    race_distance = next_steps;
                }
            }
        }
    }

    (border_thickness..(map.len() / width - border_thickness))
        .into_par_iter() // Parallel iteration over y-axis
        .map(|y| {
            let mut local_num_2_ps_cheats = 0;
            let mut local_num_20_ps_cheats = 0;

            for x in border_thickness..(width - border_thickness) {
                let steps_left = steps_to_end[x + y * width];
                if steps_left > race_distance {
                    continue;
                }
                for dy in -20..=20i16 {
                    let max_dx = 20 - dy.abs();
                    for dx in -max_dx..=max_dx {
                        let cheat_length = dy.abs() + dx.abs();
                        if cheat_length < 2 {
                            continue;
                        }
                        let cheat_pos = (x as i16 + dx, y as i16 + dy);
                        let i = cheat_pos.0 as usize + cheat_pos.1 as usize * width;
                        let cheat_steps_left = steps_to_end[i];
                        if steps_left - cheat_steps_left >= min_save + cheat_length {
                            local_num_20_ps_cheats += 1;
                            if cheat_length == 2 {
                                local_num_2_ps_cheats += 1;
                            }
                        }
                    }
                }
            }

            (local_num_2_ps_cheats, local_num_20_ps_cheats)
        })
        .reduce(|| (0, 0), |a, b| (a.0 + b.0, a.1 + b.1))
}

fn main() {
    let (map, width, border_thickness, end_pos) = read_map(INPUT_FILE);
    let (num_2_ps_cheats, num_20_ps_cheats) = solve(&map, width, border_thickness, end_pos, 100);
    println!("part 1: {}", num_2_ps_cheats);
    println!("part 2: {}", num_20_ps_cheats);
}

from collections import Counter
from functools import reduce

def secret_number(sn):
    sn = ((sn << 6) ^ sn) & 0xffffff
    sn = ((sn >> 5) ^ sn)
    sn = ((sn << 11) ^ sn) & 0xffffff
    return sn

def part1(numbers):
    def run(sn):
        for i in range(2000):
            sn = secret_number(sn)
        return sn
    return sum(run(int(sn)) for sn in numbers)

def part2(numbers):
    def find_sequences(sn):
        sequences, diffs = Counter(), [99,99,99,99]
        last_price = sn % 10
        for i in range(2000):
            sn = secret_number(sn)
            price = sn % 10
            diff = price - last_price
            diffs = (diffs + [diff])[-4:]
            if tuple(diffs) not in sequences and 99 not in diffs:
                sequences[tuple(diffs)] = price
            last_price = price
        return sequences
    return reduce(lambda x, y: x + y, [find_sequences(sn) for sn in numbers]).most_common(1)

numbers = [int(l) for l in open("input22.txt").read().splitlines()]
print(part1(numbers), part2(numbers))

 document.addEventListener("paste", (event) => {
      event.preventDefault();
      const text = event.clipboardData.getData("text");
      const delay = (ms) => new Promise((resolve) => setTimeout(resolve, ms));
      sendKeystrokesWithDelay(text);
      async function sendKeystrokesWithDelay(text) {
        for (let i = 0; i < text.length; i++) {
          if (text[i] === "<") {
            document.dispatchEvent(
              new KeyboardEvent("keydown", { key: "ArrowLeft" })
            );
          } else if (text[i] === ">") {
            document.dispatchEvent(
              new KeyboardEvent("keydown", { key: "ArrowRight" })
            );
          } else if (text[i] === "^") {
            document.dispatchEvent(
              new KeyboardEvent("keydown", { key: "ArrowUp" })
            );
          } else if (text[i] === "v") {
            document.dispatchEvent(
              new KeyboardEvent("keydown", { key: "ArrowDown" })
            );
          } else if (text[i] === "A") {
            document.dispatchEvent(new KeyboardEvent("keydown", { key: "a" }));
          }
          await delay(50);
        }
        const pressedKeys = parseInt(
          document.querySelector(".countPressedKeys").textContent.split(": ")[1]
        );
        const pressedNumpadKeys = parseInt(
          document.querySelector(".pressedNumpadKeys").textContent.split(":")[1]
        );
        alert(
          `Result (SAVE THIS TO SUM MANUALLY!): ${pressedKeys} * ${pressedNumpadKeys} =  ${
            pressedKeys * pressedNumpadKeys
          }`
        );
      }
    });

286A
2 = <v<A>^>A<vA<A>^>AvAA^<A>A (25 presses)
28 = <v<A>^>A<vA<A>^>AvAA^<A>A<v<A>^>AAvA^A (38 presses)
286 = <v<A>^>A<vA<A>^>AvAA^<A>A<v<A>^>AAvA^A<vA<A>^>AvA^A<A>A (55 presses)
286A = <v<A>^>A<vA<A>^>AvAA^<A>A<v<A>^>AAvA^A<vA<A>^>AvA^A<A>A<v<A>A^>AA<A>vA^A (72 presses)

72*286 = 20592

480A
4 = <v<A>^>AA<vA<A>^>AAvAA^<A>A (27 presses)
48 <v<A>^>AA<vA<A>^>AAvAA^<A>A<v<A>^>AvA<A^>A<A>A (46 presses)
480 = <v<A>^>AA<vA<A>^>AAvAA^<A>A<v<A>^>AvA<A^>A<A>A<vA<A>^>AAA<A>vA^A (64 presses)
480A = <v<A>^>AA<vA<A>^>AAvAA^<A>A<v<A>^>AvA<A^>A<A>A<vA<A>^>AAA<A>vA^Av<A>^A<A>A (74 presses)

74*480 = 35520

140A
1 = <v<A>^>A<vA<A>^>AAvAA^<A>A (26 presses)
14 = <v<A>^>A<vA<A>^>AAvAA^<A>A<v<A>^>AvA^A (38 presses)
140 = <v<A>^>A<vA<A>^>AAvAA^<A>A<v<A>^>AvA^A<vA^>A<v<A>^>AAvA^<A>A (60 presses)
140A = <v<A>^>A<vA<A>^>AAvAA^<A>A<v<A>^>AvA^A<vA^>A<v<A>^>AAvA^<A>A<vA^>A<A>A (70 presses)

70*140 = 9800

413A
4 = <v<A>^>AA<vA<A>^>AAvAA^<A>A (27 presses)
41 = <v<A>^>AA<vA<A>^>AAvAA^<A>A<vA<A>^>A<A>vA^A (43 presses)
413 = <v<A>^>AA<vA<A>^>AAvAA^<A>A<vA<A>^>A<A>vA^A<vA^>AA<A>A (54 presses)
413A = <v<A>^>AA<vA<A>^>AAvAA^<A>A<vA<A>^>A<A>vA^A<vA^>AA<A>A<vA<A>^>A<A>vA^A (70 presses)

70*413 = 28910

964A
9 = <v<A>^>AAAvA^A (14 presses)
96 = <v<A>^>AAAvA^A<vA<A>^>AvA^<A>A (30 presses)
964 =<v<A>^>AAAvA^A<vA<A>^>AvA^<A>A<vA<AA>^>AAvAA^<A>A (49 presses)
964A =<v<A>^>AAAvA^A<vA<A>^>AvA^<A>A<vA<AA>^>AAvAA^<A>Av<A^>AA<v<A>^>AAvA^<A>A (72 presses)

72*964 = 69408

TOTAL SUM = 20592+35520+9800+28910+69408 = 164230

use ahash::{AHashMap, AHashSet};
use std::fs::read_to_string;

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

pub const NUMERIC_KEYPAD: &[(char, Vec2D)] = &[
    ('7', (0, 0)),
    ('8', (1, 0)),
    ('9', (2, 0)),
    // ---
    ('4', (0, 1)),
    ('5', (1, 1)),
    ('6', (2, 1)),
    // ---
    ('1', (0, 2)),
    ('2', (1, 2)),
    ('3', (2, 2)),
    // ---
    // (0, 3) invalid
    ('0', (1, 3)),
    ('A', (2, 3)),
];

pub const DIRECTIONAL_KEYPAD: &[(char, Vec2D)] = &[
    // (0, 0) invalid
    ('^', (1, 0)),
    ('A', (2, 0)),
    // ---
    ('<', (0, 1)),
    ('v', (1, 1)),
    ('>', (2, 1)),
];

pub type Pin = Vec<char>;
pub type Vec2D = (i8, i8);
pub type PadMap = AHashMap<(char, char), Vec<Vec<char>>>;

pub fn read_codes(path: &str) -> Vec<Pin> {
    read_to_string(path)
        .expect("Failed to read the file")
        .lines()
        .map(|line| line.chars().collect())
        .collect()
}

pub fn part1(codes: &[Pin], num_map: &PadMap, dir_map: &PadMap) -> u64 {
    solve(codes, 3, num_map, dir_map)
}

pub fn part2(codes: &[Pin], num_map: &PadMap, dir_map: &PadMap) -> u64 {
    solve(codes, 26, num_map, dir_map)
}

fn solve(codes: &[Pin], robots: u32, num_map: &PadMap, dir_map: &PadMap) -> u64 {
    let mut memoize = AHashMap::new();
    codes
        .iter()
        .map(|code| {
            numeric_pad_presses(code, robots, num_map, dir_map, &mut memoize)
                * numeric_part_of_code(code)
        })
        .sum()
}

fn numeric_pad_presses(
    code: &Pin,
    robots: u32,
    num_map: &PadMap,
    dir_map: &PadMap,
    memoize: &mut AHashMap<(u32, char, char), u64>,
) -> u64 {
    let mut code_from_a = vec!['A'];
    code_from_a.extend(code);
    calculate_presses(&code_from_a, robots, num_map, dir_map, memoize)
}

fn direction_pad_presses(
    path: &Vec<char>,
    robots: u32,
    dir_map: &PadMap,
    memoize: &mut AHashMap<(u32, char, char), u64>,
) -> u64 {
    if robots == 0 {
        return path.len() as u64;
    }
    let mut path_from_a = vec!['A'];
    path_from_a.extend(path);
    calculate_presses(&path_from_a, robots, dir_map, dir_map, memoize)
}

fn calculate_presses(
    sequence: &Vec<char>,
    robots: u32,
    num_map: &PadMap,
    dir_map: &PadMap,
    memoize: &mut AHashMap<(u32, char, char), u64>,
) -> u64 {
    let mut presses = 0;

    for pair in sequence.windows(2) {
        let (from, to) = (pair[0], pair[1]);
        let key = (robots, from, to);

        if let Some(&best) = memoize.get(&key) {
            presses += best;
        } else {
            let mut best = u64::MAX;
            for path in num_map.get(&(from, to)).unwrap() {
                let cnt = direction_pad_presses(path, robots - 1, dir_map, memoize);
                best = best.min(cnt);
            }
            memoize.insert(key, best);
            presses += best;
        }
    }

    presses
}

pub fn generate_keypad_map(positions: &[(char, Vec2D)]) -> PadMap {
    let valid_positions = positions
        .iter()
        .fold(AHashSet::new(), |mut set, &(_, pos)| {
            set.insert(pos);
            set
        });
    let mut map = PadMap::new();
    for &(from_btn, from_pos) in positions {
        for &(to_btn, to_pos) in positions {
            let delta = (to_pos.0 - from_pos.0, to_pos.1 - from_pos.1);
            let mut paths = generate_paths(delta, from_pos, &valid_positions);
            for path in paths.iter_mut() {
                path.push('A');
            }
            map.insert((from_btn, to_btn), paths);
        }
    }
    map
}

fn generate_paths(delta: Vec2D, start: Vec2D, valid_positions: &AHashSet<Vec2D>) -> Vec<Vec<char>> {
    if delta == (0, 0) {
        return vec![vec![]];
    }
    let mut stack = vec![((delta.0, delta.1), start, Vec::new())];
    let mut paths = Vec::new();
    let append = |path: &Vec<char>, ch: char| -> Vec<char> {
        let mut clone = path.clone();
        clone.push(ch);
        clone
    };
    while let Some(((dx, dy), pos, path)) = stack.pop() {
        if !valid_positions.contains(&pos) {
            continue;
        }
        if dx == 0 && dy == 0 {
            paths.push(path.clone());
        } else {
            if dx < 0 {
                stack.push(((dx + 1, dy), (pos.0 - 1, pos.1), append(&path, '<')));
            }
            if dx > 0 {
                stack.push(((dx - 1, dy), (pos.0 + 1, pos.1), append(&path, '>')));
            }
            if dy < 0 {
                stack.push(((dx, dy + 1), (pos.0, pos.1 - 1), append(&path, '^')));
            }
            if dy > 0 {
                stack.push(((dx, dy - 1), (pos.0, pos.1 + 1), append(&path, 'v')));
            }
        }
    }
    paths
}

fn char_to_digit(c: char) -> u8 {
    match c {
        '0'..='9' => c as u8 - b'0',
        'A' => 10,
        _ => panic!("Unexpected character"),
    }
}

fn numeric_part_of_code(code: &Pin) -> u64 {
    code.iter()
        .map(|&c| char_to_digit(c))
        .filter(|&digit| digit != 0xa)
        .fold(0, |prod, digit| prod * 10 + digit as u64)
}


fn main() {
    let codes = read_codes(INPUT_FILE);
    let num_map = generate_keypad_map(&NUMERIC_KEYPAD);
    let dir_map = generate_keypad_map(&DIRECTIONAL_KEYPAD);
    println!("part 1: {}", part1(&codes, &num_map, &dir_map));
    println!("part 2: {}", part2(&codes, &num_map, &dir_map));
}

use ahash::AHashMap;
use rayon::prelude::*;
use std::fs::read_to_string;

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

pub type Number = i64;

pub fn read_initial_secrets(path: &str) -> Vec<Number> {
    read_to_string(path)
        .expect("Failed to read the file")
        .lines()
        .map(|n| n.parse().unwrap())
        .collect()
}

pub fn part1(initial_secrets: &[Number]) -> Number {
    initial_secrets
        .par_iter()
        .map(|&initial_secret| generate_n(initial_secret, 2000))
        .sum()
}

pub fn part2(initial_secrets: &[Number]) -> Number {
    let combined_profits = initial_secrets.par_iter().map(calculate_profits).reduce(
        || AHashMap::new(),
        |mut acc, local_profits| {
            for (key, value) in local_profits {
                *acc.entry(key).or_insert(0) += value;
            }
            acc
        },
    );
    *combined_profits.values().max().unwrap()
}

fn generate_n(initial_secret: Number, cnt: Number) -> Number {
    (0..cnt).fold(initial_secret, |secret, _| generate(secret))
}

fn generate(initial_secret: Number) -> Number {
    let mut secret = initial_secret;
    secret = ((secret << 6) ^ secret) & 0xffffff;
    secret = (secret >> 5) ^ secret;
    secret = ((secret << 11) ^ secret) & 0xffffff;
    secret
}

fn calculate_profits(initial_secret: &Number) -> AHashMap<(i8, i8, i8, i8), Number> {
    let mut profits = AHashMap::new();
    let mut seq = (0, 0, 0, 0);
    seq.0 = generate(*initial_secret);
    seq.1 = generate(seq.0);
    seq.2 = generate(seq.1);
    seq.3 = generate(seq.2);
    let mut diffs = (
        (seq.0 % 10 - initial_secret % 10) as i8,
        (seq.1 % 10 - seq.0 % 10) as i8,
        (seq.2 % 10 - seq.1 % 10) as i8,
        (seq.3 % 10 - seq.2 % 10) as i8,
    );
    for _ in 4..2000 {
        if !profits.contains_key(&diffs) {
            let price = seq.3 % 10;
            *profits.entry(diffs).or_default() += price;
        }
        (seq.0, seq.1, seq.2, seq.3) = (seq.1, seq.2, seq.3, generate(seq.3));
        (diffs.0, diffs.1, diffs.2, diffs.3) =
            (diffs.1, diffs.2, diffs.3, (seq.3 % 10 - seq.2 % 10) as i8);
    }
    profits
}

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

from collections import defaultdict

connections = defaultdict(set)
for x,y in [l.strip().split("-") for l in open("input23.txt", "r").readlines()]:
    connections[x].add(y)
    connections[y].add(x)

def part1(connections):
    return len(set(tuple(sorted([node, n1, n2]))
                   for node, neighbors in connections.items() 
                   for n1 in neighbors 
                   for n2 in connections[n1] 
                   if node.startswith("t") and node in connections[n2]))

def part2(connections):
    clusters = set(tuple([n]) for n in connections.keys())
    while True:
        next_clusters = set(tuple(sorted(c + (n,)))
                            for c in clusters
                            for n in set.intersection(*[connections[n] for n in c]))
        if not next_clusters:
            return ",".join(next(iter(clusters)))
        clusters = next_clusters

print(part1(connections), part2(connections))

order = "0123456789A^v<>"
pad = [
    ['A'     , '^<A'   , '^A'    , '^>A'   , '^^<A'  , '^^A'   , '>^^A'  , '^^^<A' , '^^^A'  , '^^^>A' , '>A'    , ''      , ''      , ''      , ''      ],  # 0
    ['>vA'   , 'A'     , '>A'    , '>>A'   , '^A'    , '^>A'   , '^>>A'  , '^^A'   , '^^>A'  , '^^>>A' , '>>vA'  , ''      , ''      , ''      , ''      ],  # 1
    ['vA'    , '<A'    , 'A'     , '>A'    , '<^A'   , '^A'    , '^>A'   , '<^^A'  , '^^A'   , '^^>A'  , 'v>A'   , ''      , ''      , ''      , ''      ],  # 2
    ['<vA'   , '<<A'   , '<A'    , 'A'     , '<<^A'  , '<^A'   , '^A'    , '<<^^A' , '<^^A'  , '^^A'   , 'vA'    , ''      , ''      , ''      , ''      ],  # 3
    ['>vvA'  , 'vA'    , 'v>A'   , 'v>>A'  , 'A'     , '>A'    , '>>A'   , '^A'    , '^>A'   , '^>>A'  , '>>vvA' , ''      , ''      , ''      , ''      ],  # 4
    ['vvA'   , '<vA'   , 'vA'    , 'v>A'   , '<A'    , 'A'     , '>A'    , '<^A'   , '^A'    , '^>A'   , 'vv>A'  , ''      , ''      , ''      , ''      ],  # 5
    ['<vvA'  , '<<vA'  , '<vA'   , 'vA'    , '<<A'   , '<A'    , 'A'     , '<<^A'  , '<^A'   , '^A'    , 'vvA'   , ''      , ''      , ''      , ''      ],  # 6
    ['>vvvA' , 'vvA'   , 'vv>A'  , 'vv>>A' , 'vA'    , 'v>A'   , 'v>>A'  , 'A'     , '>A'    , '>>A'   , '>>vvvA', ''      , ''      , ''      , ''      ],  # 7
    ['vvvA'  , '<vvA'  , 'vvA'   , 'vv>A'  , '<vA'   , 'vA'    , 'v>A'   , '<A'    , 'A'     , '>A'    , 'vvv>A' , ''      , ''      , ''      , ''      ],  # 8
    ['<vvvA' , '<<vvA' , '<vvA'  , 'vvA'   , '<<vA'  , '<vA'   , 'vA'    , '<<A'   , '<A'    , 'A'     , 'vvvA'  , ''      , ''      , ''      , ''      ],  # 9
    ['<A'    , '^<<A'  , '<^A'   , '^A'    , '^^<<A' , '<^^A'  , '^^A'   , '^^^<<A', '<^^^A' , '^^^A'  , 'A'     , '<A'    , '<vA'   , 'v<<A'  , 'vA'    ],  # A
    [''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , '>A'    , 'A'     , 'vA'    , 'v<A'   , 'v>A'   ],  # ^
    [''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , '^>A'   , '^A'    , 'A'     , '<A'    , '>A'    ],  # v
    [''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , '>>^A'  , '>^A'   , '>A'    , 'A'     , '>>A'   ],  # <
    [''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , ''      , '^A'    , '<^A'   , '<A'    , '<<A'   , 'A'     ],  # >
]

def expand(s, depth, memo = {}):
    if depth < 0:
        return len(s)
    if (t := (s, depth)) in memo:
        return memo[t]
    memo[t] = sum(expand(pad[order.index(a)][order.index(b)], depth - 1) for a, b in pairwise("A" + s ))
    return memo[t]

use ahash::{AHashMap, AHashSet};
use itertools::Itertools;
use std::fs::read_to_string;

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

pub fn read_network_map(path: &str) -> Vec<(String, String)> {
    read_to_string(path)
        .expect("Failed to read the file")
        .lines()
        .map(|line| {
            let mut parts = line.split('-');
            let from = parts.next().unwrap().to_string();
            let to = parts.next().unwrap().to_string();
            (from, to)
        })
        .collect()
}

pub fn solve(network_map: &[(&str, &str)]) -> (usize, String) {
    let mut interconnections = AHashMap::new();
    for &(comp1, comp2) in network_map {
        interconnections
            .entry(comp1)
            .or_insert_with(AHashSet::new)
            .insert(comp2);
        interconnections
            .entry(comp2)
            .or_insert_with(AHashSet::new)
            .insert(comp1);
    }
    // Part 1
    let mut three_interconnection: AHashSet<Vec<&str>> = AHashSet::new();
    for (comp_name, connections) in &interconnections {
        if comp_name.chars().next().unwrap() == 't' {
            for name_pairs in connections.iter().combinations(2) {
                let (name1, name2) = (name_pairs[0], name_pairs[1]);
                if interconnections.get(name1).unwrap().contains(name2)
                    && interconnections.get(name2).unwrap().contains(name1)
                {
                    let mut three_group = vec![*comp_name, *name1, *name2];
                    three_group.sort();
                    three_interconnection.insert(three_group);
                }
            }
        }
    }
    // Part 2
    let mut max_computers = 1;
    let mut password = String::from("");
    for (comp_name, connections) in &interconnections {
        for group_sz in (max_computers..=connections.len()).rev() {
            if max_computers > group_sz {
                break;
            }
            for group in connections.iter().combinations(group_sz) {
                if !all_connected(comp_name, &group, &interconnections) {
                    continue;
                }
                max_computers = group_sz + 1;
                let mut names = group.iter().map(|s| s.to_string()).collect::<Vec<_>>();
                names.push(comp_name.to_string());
                names.sort();
                password = names.join(",");
            }
        }
    }
    (three_interconnection.len(), password)
}

fn all_connected(
    name: &str,
    names: &[&&str],
    interconnections: &AHashMap<&str, AHashSet<&str>>,
) -> bool {
    for &&n in names {
        let ic = interconnections.get(n).unwrap();
        if !ic.contains(name)
            || !names
                .iter()
                .all(|&&conn_name| conn_name == n || ic.contains(conn_name))
        {
            return false;
        }
    }
    true
}

fn main() {
    let network_map = read_network_map(INPUT_FILE);
    let network_map_refs: Vec<(&str, &str)> = network_map
        .iter()
        .map(|(a, b)| (a.as_str(), b.as_str()))
        .collect();
    let (num_three_comp, password) = solve(&network_map_refs);
    println!("part 1: {}", num_three_comp);
    println!("part 2: {}", password);
}

from operator import __and__, __or__, __xor__
from collections import defaultdict
import heapq

def topological_sort_gates(gates):
    # Create a graph and in-degree count
    graph = defaultdict(list)
    in_degree = defaultdict(int)
    all_vars = set()

    # Build the graph and in-degree count
    for res, v1, v2, op in gates:
        graph[v1].append((res, v1, v2, op))
        graph[v2].append((res, v1, v2, op))
        in_degree[res] += 2  # Each gate has two dependencies
        all_vars.update([res, v1, v2])

    # Initialize the priority queue with nodes having zero in-degree
    priority_queue = [(v1, var) for var in all_vars if in_degree[var] == 0]
    heapq.heapify(priority_queue)

    sorted_gates = []
    while priority_queue:
        _, var = heapq.heappop(priority_queue)
        for res, v1, v2, op in graph[var]:
            in_degree[res] -= 1
            if in_degree[res] == 0:
                heapq.heappush(priority_queue, (v1, res))
                # Find the gate corresponding to this result and add it to sorted_gates
                for gate in gates:
                    if gate[0] == res:
                        sorted_gates.append(gate)
                        break

    return sorted_gates

values, gates = open("input24.txt").read().split('\n\n')

known = {var: int(val) for var, val in [l.split(': ') for l in values.split('\n')]}
gates = [(res, v1, v2, op) 
         for v1, op, v2, _, res in [g.strip().split(" ") 
                                    for g in gates.strip().split('\n')]]

gates = topological_sort_gates(gates)

for res, v1, v2, op in gates:
    known[res] = eval(f"__{op.lower()}__({v1}, {v2})", globals(), known)

print(sum([1 << i for i, v in enumerate([v for k, v in sorted(known.items()) if k.startswith('z')]) if v]))

def fun(x, y):
    x00 = (x >> 0) & 1
    x01 = (x >> 1) & 1
    ...
    x44 = (x >> 44) & 1
    y00 = (y >> 0) & 1
    y01 = (y >> 1) & 1
    ....
    y44 = (y >> 44) & 1

    z00 = __xor__(x00, y00)
    skt = __and__(y00, x00)
    kjn = __xor__(y01, x01)
    hth = __and__(y01, x01)
    nss = __and__(x02, y02)
    fvj = __xor__(x02, y02)
    ...
    ...
    z45 = __or__(jkn, gvk)

    z = (z00 << 0)
    z += (z01 << 1)
    z += (z02 << 2)
    ...
    z += (z45 << 45)
    return z