🌟 Advent of Code (AoC) 2024 🌟

import numpy as np

offset = np.array([[-1, 0],[0, 1],[1, 0],[0, -1]])
d = "0123"
original = np.array([[c for c in l.strip()]
                     for l in open("input06.txt", "r").readlines()])
start = tuple(zip(*np.where(original == '^')))[0]

def find_loop(a):
    dir = 0
    pos = next = start
    while (0 <= next[0] < a.shape[0] and 0 <= next[1] < a.shape[1]):
        if a[next] == '#':
            dir = (dir + 1) % 4
        else:
            pos = next
            if a[pos] == d[dir]:
                return True
            a[pos] = d[dir]
        next = tuple(pos + offset[dir])
    return False

def relabel_visited(a):
    for i in range(4):
        a[a == d[i]] = 'X'

def part1(a):
    find_loop(a) # We will not find a loop but it walks the path
    relabel_visited(a)
    return a[a == 'X'].size + (a[start] == '^')

def test_obstacle(pos):
    a = original.copy()
    a[pos] = '#'
    return find_loop(a)

def part2(indices):
    return sum(test_obstacle(pos) for pos in indices)

a = original.copy()
print(part1(a))
print(part2(zip(*np.where(a == 'X'))))

use rayon::prelude::*;
use std::fs;

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

const DIRECTIONS: &[&Vec2D; 4] = &[
    &Vec2D { x: 0, y: -1 },
    &Vec2D { x: 1, y: 0 },
    &Vec2D { x: 0, y: 1 },
    &Vec2D { x: -1, y: 0 },
];

#[derive(Default, Clone, Copy)]
pub struct Vec2D {
    x: i32,
    y: i32,
}

pub type Map = Vec<Vec<bool>>;

pub fn read_map_and_start_pos(path: &str) -> (Map, Vec2D) {
    let mut start_pos = Vec2D::default();
    let mut map = Map::default();
    for (y, line) in fs::read_to_string(path)
        .expect(&format!("File {} should be present", path))
        .lines()
        .enumerate()
    {
        let mut row = Vec::new();
        for (x, ch) in line.chars().enumerate() {
            if '^' == ch {
                start_pos = Vec2D {
                    x: x as i32,
                    y: y as i32,
                }
            }
            row.push('#' == ch);
        }
        map.push(row);
    }
    (map, start_pos)
}

fn calc_num_distinct_tiles(map: &Map, start_pos: &Vec2D, added_block_pos: &Vec2D) -> (u32, bool) {
    let width = map[0].len() as i32;
    let height = map.len() as i32;
    let mut direction = 0;
    let mut visited = vec![vec![0u8; width as usize]; height as usize];
    let mut guard_pos = *start_pos;
    let mut next_forward_pos = *start_pos;
    let mut num_distinct_tiles = 0;

    while next_forward_pos.x >= 0
        && next_forward_pos.x < width
        && next_forward_pos.y >= 0
        && next_forward_pos.y < height
    {
        if (added_block_pos.x == next_forward_pos.x && added_block_pos.y == next_forward_pos.y)
            || map[next_forward_pos.y as usize][next_forward_pos.x as usize]
        {
            direction = (direction + 1) % 4;
        } else {
            guard_pos = next_forward_pos;
            let visited_tile = &mut visited[guard_pos.y as usize][guard_pos.x as usize];
            if *visited_tile == 0 {
                num_distinct_tiles += 1;
            } else if (*visited_tile & (1 << direction)) != 0 {
                return (num_distinct_tiles, true);
            }
            *visited_tile |= 1 << direction;
        }
        let forward = DIRECTIONS[direction];
        next_forward_pos = Vec2D {
            x: guard_pos.x + forward.x,
            y: guard_pos.y + forward.y,
        };
    }
    (num_distinct_tiles, false)
}

pub fn calc_num_distinct_tiles_before_leaving(map: &Map, start_pos: &Vec2D) -> u32 {
    let dummy_pos = Vec2D { x: -1, y: -1 };
    let (cnt, _) = calc_num_distinct_tiles(map, start_pos, &dummy_pos);
    cnt
}

pub fn calc_num_block_position_causing_loop(map: &Map, start_pos: &Vec2D) -> u32 {
    (0..map.len())
        .into_par_iter()
        .map(|y| {
            (0..map[0].len())
                .filter_map(|x| {
                    let block_pos = Vec2D {
                        x: x as i32,
                        y: y as i32,
                    };
                    if block_pos.x == start_pos.x && block_pos.y == start_pos.y
                        || map[block_pos.y as usize][block_pos.x as usize]
                    {
                        return None;
                    }
                    let (_, is_loop) = calc_num_distinct_tiles(map, start_pos, &block_pos);
                    if is_loop {
                        Some(1)
                    } else {
                        None
                    }
                })
                .sum::<u32>()
        })
        .sum()
}

fn main() {
    let (map, start_pos) = read_map_and_start_pos(INPUT_FILE);
    println!(
        "part 1: {}",
        calc_num_distinct_tiles_before_leaving(&map, &start_pos)
    );
    println!(
        "part 2: {}",
        calc_num_block_position_causing_loop(&map, &start_pos)
    );
}

type Direction = UP | DOWN | LEFT | RIGHT
type Spot = EMPTY | OBSTACLE | START
type Position = {X: int; Y: int}
type Movement = { position: Position; direction: Direction }

let data = System.IO.File.ReadAllLines("input.txt")
        |> Seq.mapi (fun x ->
            Seq.mapi (fun y c ->
                let spot = match c with
                           | '.' -> EMPTY
                           | '#' -> OBSTACLE
                           | '^' -> START
                           | _ -> failwith "Invalid input"
                ({X= x; Y=y}, spot) 
            ))
        |> Seq.concat
let startPosition = data |> Seq.find (fun (_, s) -> s = START) |> fst
let obstacles = data |> Seq.filter (fun (_, s) -> s = OBSTACLE) |> Seq.map fst |> Set.ofSeq
let bounds =
    let maxX = data |> Seq.map fst |>  Seq.maxBy _.X |> _.X
    let maxY = data |> Seq.map fst |> Seq.maxBy _.Y |> _.Y
    (maxX, maxY)


let move obstacles movement =
    let potentialNewMove = match movement.direction with
                           | UP -> { movement with position.X = movement.position.X - 1 }
                           | DOWN -> { movement with position.X = movement.position.X + 1 }
                           | LEFT -> { movement with position.Y = movement.position.Y - 1 }
                           | RIGHT -> { movement with position.Y = movement.position.Y + 1 }
    match Set.contains potentialNewMove.position obstacles with
    | false -> potentialNewMove
    | true -> match movement.direction with
              | UP -> { movement with direction = RIGHT; }
              | DOWN -> { movement with direction = LEFT;}
              | LEFT -> { movement with direction = UP;}
              | RIGHT -> { movement with direction = DOWN;}
    
let MoveUntilOutOfBounds obstacles movement =
    let rec MoveUntilOutOfBounds' pos cnt =
        let newMovement = move obstacles pos
        match newMovement.position.X < 0 || newMovement.position.Y < 0 || newMovement.position.X > fst bounds || newMovement.position.Y > snd bounds with
        | true -> cnt
        | false -> MoveUntilOutOfBounds' newMovement (cnt |> Set.add newMovement.position)
    MoveUntilOutOfBounds' movement  Set.empty
    
    
let visitedPositions = MoveUntilOutOfBounds obstacles {  position = startPosition; direction = UP }
printfn $"Task 1: %A{visitedPositions |> Set.count}"


let createsLoop movement obstacles =
    let rec MoveUntilOutOfBounds' pos cnt =
        let newMovement = move obstacles pos
        if newMovement.position.X < 0 || newMovement.position.Y < 0 || newMovement.position.X > fst bounds || newMovement.position.Y > snd bounds then false
        elif Set.contains newMovement cnt && newMovement <> pos then true
        else MoveUntilOutOfBounds' newMovement (cnt |> Set.add newMovement)
    MoveUntilOutOfBounds' movement  Set.empty


let obstaclesThatCreatesLoop = visitedPositions |> Set.filter (fun position -> createsLoop { position=startPosition; direction = UP } (Set.add position obstacles))
printfn $"Task 2: %A{obstaclesThatCreatesLoop |> Set.count}"

package main

import (
	"bufio"
	"fmt"
	"os"
)

type Position struct {
	y int
	x int
}

func isOutOfBounds(rows []string, pos Position) bool {
	if pos.y < 0 || pos.y >= len(rows) {
		return true
	} else if pos.x < 0 || pos.x >= len(rows[pos.y]) {
		return true
	}
	return false
}

func getNewDirection(dir Position) Position {
	if dir.y == -1 && dir.x == 0 { // north
		return Position{0, 1} // east
	} else if dir.y == 0 && dir.x == 1 { // east
		return Position{1, 0} // south
	} else if dir.y == 1 && dir.x == 0 { // south
		return Position{0, -1} // west
	} else if dir.y == 0 && dir.x == -1 { // west
		return Position{-1, 0} // north
	}
	panic("no supported direction")
}

func moveDirection(rows []string, pos, dir Position, visitMap map[int]map[int]int) (Position, Position, bool, int) {
	pos.y += dir.y
	pos.x += dir.x
	if isOutOfBounds(rows, pos) {
		return pos, dir, false, 0
	} else if rows[pos.y][pos.x] == '#' || rows[pos.y][pos.x] == 'O' {
		pos.y -= dir.y
		pos.x -= dir.x
		return pos, getNewDirection(dir), true, 0
	}

	//	fmt.Println("Visiting", pos.y, pos.x)
	visitCount := visit(rows, pos, visitMap)
	return pos, dir, true, visitCount
}

func visit(rows []string, pos Position, visitMap map[int]map[int]int) int {
	if _, exist := visitMap[pos.y]; !exist {
		visitMap[pos.y] = make(map[int]int, len(rows[pos.y]))
	}
	visitMap[pos.y][pos.x]++
	return visitMap[pos.y][pos.x]
}

func findStart(rows []string) (start, direction Position) {
	for y, row := range rows {
		for x, char := range row {
			if char == '^' { // direction up
				start.y, start.x = y, x
				direction.y, direction.x = -1, 0
				return start, direction
			}
		}
	}
	panic("no start position")
}

func moveUntilDone(rows []string, pos, dir Position, visitMap map[int]map[int]int) bool {
	var moving bool = true
	posCount := 0
	for moving {
		pos, dir, moving, posCount = moveDirection(rows, pos, dir, visitMap)
		if posCount > 4 {
			return true
		}
	}
	return false
}

func getPartOne(rows []string) (count int) {
	startPos, startDirection := findStart(rows)
	visitMap := make(map[int]map[int]int, len(rows))

	visit(rows, startPos, visitMap)
	moveUntilDone(rows, startPos, startDirection, visitMap)

	for _, v := range visitMap {
		count += len(v)
	}
	return count
}

func deepCopySlice(original []string) []string {
	copy := make([]string, len(original))
	for i, str := range original {
		copy[i] = str
	}
	return copy
}

func getPartTwo(_rows []string) (count int) {
	startPos, startDirection := findStart(_rows)
	visitMap := make(map[int]map[int]int, len(_rows))
	visit(_rows, startPos, visitMap)
	moveUntilDone(_rows, startPos, startDirection, visitMap)
	cntChan := make(chan int)

        // CHANGE MADE HERE!
	for _y, _v := range visitMap {
		go func(y int, v map[int]int, rows []string) {
			rowCnt := 0
			for x := range v {
				if startPos.y == y && startPos.x == x {
					continue
				}
				rows[y] = rows[y][:x] + "O" + rows[y][x+1:]
				newVisitMap := make(map[int]map[int]int, len(rows))

				if moveUntilDone(rows, startPos, startDirection, newVisitMap) {
					rowCnt++
				}
				rows[y] = rows[y][:x] + "." + rows[y][x+1:]
			}
			cntChan <- rowCnt
		}(_y, _v, deepCopySlice(_rows))
	}
	for i := len(visitMap); i > 0; i-- {
		count += <-cntChan
	}
	return count
}

func getRows(filename string) []string {
	file, err := os.Open(filename)
	if err != nil {
		panic(err)
	}
	defer file.Close()
	scanner := bufio.NewScanner(file)
	var rows []string
	for scanner.Scan() {
		row := scanner.Text()
		rows = append(rows, row)
	}
	return rows
}

func main() {
	fmt.Println("Part one:", getPartOne(getRows("input.txt")))
	fmt.Println("Part two:", getPartTwo(getRows("input.txt")))
}

from operator import add, mul

def test_operators(expect, terms, operators, computed = 0):
    if not terms:
        return expect if expect == computed else 0
    for o in operators:
        if test_operators(expect, terms[1:], operators, o(computed, terms[0])):
            return expect
    return 0

s1 = s2 = 0
for l in open("input07.txt", "r").readlines():
    expect, terms = l.split(": ")
    s1 += test_operators(int(expect), list(map(int, terms.split(" "))), [add, mul])
    s2 += test_operators(int(expect), list(map(int, terms.split(" "))), [add, mul, lambda x,y: int(str(x) + str(y))])
print(s1, s2)

from operator import add, mul

def test_operators(expect, terms, operators, computed = 0):
    if not terms:
        return expect if expect == computed else 0
    return any(test_operators(expect, terms[1:], operators, o(computed, terms[0])) for o in operators) and expect

print(*[sum(test_operators(expect, terms, os) 
            for expect, terms in [(int(expect), list(map(int, terms.split()))) for expect, terms in 
                                  (line.split(": ") for line in open("input07.txt", "r").readlines())]) 
        for os in [[add, mul], [add, mul, lambda x,y: int(str(x) + str(y))]]])

namespace Day_7;

public class Solver
{

    private enum Operator
    {
        Add,
        Mult,
        Concat
    }

    private static List<Operator[]> GetOperatorCombinations(int count, List<Operator> operators)
    {
        var result = new List<Operator[]>();
        GenerateCombinations(operators.ToArray(), count, new Operator[count], result, 0);
        return result;
    }

    private static void GenerateCombinations(Operator[] operators, int count, Operator[] current, List<Operator[]> result, int index)
    {
        if (index == count)
        {
            result.Add((Operator[])current.Clone());
            return;
        }

        foreach (var op in operators)
        {
            current[index] = op;
            GenerateCombinations(operators, count, current, result, index + 1);
        }
    }
    
    
    private static List<(long Value, List<long> Numbers)> ParseInput(List<string> data)
    {
        List<(long val, List<long> numbers)> result = new();
        foreach (var line in data)
        {
            var value = Int64.Parse(line.Substring(0, line.IndexOf(':')));
            var numbers = line[(line.IndexOf(':') + 1)..].Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(s => Int64.Parse(s.Trim())).ToList();
            result.Add((val: value, numbers: numbers));
        }

        return result;
    }
    public static long Run_PartOne(List<string> input)
    {
        var data = ParseInput(input);

        long totalValue = 0;
        foreach (var line in data)
        {
            long expectedValue = line.Value;
            var numbers = line.Numbers;

            var numberOfOperators = numbers.Count - 1;
            var combinations = GetOperatorCombinations(numberOfOperators, [Operator.Add, Operator.Mult]);
            

            for (int i = 0; i < combinations.Count; i++)
            {
                long val = 0;
                var operators = combinations.ElementAt(i);
                for (int j = 0; j < operators.Length; j++)
                {
                    var numberBefore = numbers[j];
                    var numberAfter = numbers[j + 1];
                    var currentOp = operators[j];
                    if (j == 0)
                    {
                        if (currentOp == Operator.Add)
                            val = numberBefore + numberAfter;
                        else if (currentOp == Operator.Mult)
                            val = numberBefore * numberAfter;
                    }
                    else
                    {
                        if (currentOp == Operator.Add)
                            val += numberAfter;
                        else if (currentOp == Operator.Mult)
                            val *= numberAfter;
                    }
                }

                if (val == expectedValue)
                {
                    totalValue += val;
                    break;
                }
            }

        }

        return totalValue;
    }
    
    public static long Run_PartTwo(List<string> input)
    {
        var data = ParseInput(input);
        
        long totalValue = 0;
        foreach (var line in data)
        {
            long expectedValue = line.Value;
            var numbers = line.Numbers;

            var numberOfOperators = numbers.Count - 1;
           
            var combinations = GetOperatorCombinations(numberOfOperators,
                [Operator.Add, Operator.Mult, Operator.Concat]);
            
            for (int i = 0; i < combinations.Count; i++)
            {
                long val = 0;
                var operators = combinations.ElementAt(i);
                for (int j = 0; j < operators.Length; j++)
                {
                    var numberBefore = numbers[j];
                    var numberAfter = numbers[j + 1];
                    var currentOp = operators[j];
                    if (j == 0)
                    {
                        if (currentOp == Operator.Add)
                            val = numberBefore + numberAfter;
                        else if (currentOp == Operator.Mult)
                            val = numberBefore * numberAfter;
                        else if (currentOp == Operator.Concat)
                            val = long.Parse($"{numberBefore}{numberAfter}");
                    }
                    else
                    {
                        if (currentOp == Operator.Add)
                            val += numberAfter;
                        else if (currentOp == Operator.Mult)
                            val *= numberAfter;
                        else if (currentOp == Operator.Concat)
                            val = long.Parse($"{val}{numberAfter}");
                        
                    }
                }

                if (val == expectedValue)
                {
                    totalValue += val;
                    break;
                }
            }

        }

        return totalValue;
    }
}

using System.Collections.Concurrent;
using System.Diagnostics;
var lines = File.ReadAllLines("input.txt").Select(x => x.Split(':'));
(long sumpart1, long sumpart2) = (0, 0);
long a(long x, long y) => x + y;
long m(long x, long y) => x * y;
long c(long x, long y) => long.Parse($"{x}{y}");
Stopwatch sw = Stopwatch.StartNew();
ConcurrentBag<long> p1 = [];
ConcurrentBag<long> p2 = [];
Parallel.ForEach(lines, line =>
{
    var expected = long.Parse(line[0]);
    var numbers = line[1].Trim().Split(' ').Select(long.Parse).Reverse().ToArray();
    if (Generatesolutions(numbers, [a, m]).Any(x => x == expected))
        p1.Add(expected);
    else if (Generatesolutions(numbers, [a, m, c]).Any(x => x == expected))
        p2.Add(expected);
});
sumpart1 = p1.Sum();
sumpart2 = sumpart1 + p2.Sum();
Console.WriteLine("Part 1: " + sumpart1);
Console.WriteLine("Part 2: " + sumpart2);
Console.WriteLine("Time:   " + sw.Elapsed);
static IEnumerable<long> Generatesolutions(long[] numbers, IEnumerable<Func<long, long, long>> funcs)
{
    if (numbers.Length == 1)
    {
	yield return numbers[0];
	yield break;
    }
    foreach (var op in funcs)
	foreach (var num in Generatesolutions(numbers[1..], funcs))
            yield return op(num, numbers[0]);
}

#include <stdio.h>

static inline int check_xmas(const char a[140][144], const int i, const int j)
{
    int count = 0;
    // check right
    if ((a[i][j] == 'X' && a[i][j+1] == 'M' && a[i][j+2] == 'A' && a[i][j+3] =='S') ||
        (a[i][j] == 'S' && a[i][j+1] == 'A' && a[i][j+2] == 'M' && a[i][j+3] =='X')) {
        count++;
    }
    // check down
    if ((a[i][j] == 'X' && a[i+1][j] == 'M' && a[i+2][j] == 'A' && a[i+3][j] =='S') ||
        (a[i][j] == 'S' && a[i+1][j] == 'A' && a[i+2][j] == 'M' && a[i+3][j] =='X')) {
        count++;
    }
    // diag - down right
    if ((a[i][j] == 'X' && a[i+1][j+1] == 'M' && a[i+2][j+2] == 'A' && a[i+3][j+3] =='S') ||
        (a[i][j] == 'S' && a[i+1][j+1] == 'A' && a[i+2][j+2] == 'M' && a[i+3][j+3] =='X')) {
        count++;
    }
    // diag - up left
    if ((a[i+3][j] == 'X' && a[i+2][j+1] == 'M' && a[i+1][j+2] == 'A' && a[i][j+3] =='S') ||
        (a[i+3][j] == 'S' && a[i+2][j+1] == 'A' && a[i+1][j+2] == 'M' && a[i][j+3] =='X')) {
        count++;
    }
    return count;
}

static inline int check_mas(const char a[140][144], const int i, const int j)
{
    if (((a[i][j] == 'M' && a[i+1][j+1] == 'A' && a[i+2][j+2] == 'S') ||
        (a[i][j] == 'S' && a[i+1][j+1] == 'A' && a[i+2][j+2] == 'M')) &&
       ((a[i+2][j] == 'M' && a[i+1][j+1] == 'A' && a[i][j+2] == 'S') ||
        (a[i+2][j] == 'S' && a[i+1][j+1] == 'A' && a[i][j+2] == 'M'))) {
        return 1;
    }
    return 0;
}

int main(int argc, char *argv[])
{
    FILE *fp;
    int i = 0, j = 0, part1 = 0, part2 = 0;
    char a[140][144] = {0}; // Add 4 bytes extra per row, avoids loop range
                            // checks at the cost of some minor extra compute...

    fp = fopen("input.txt", "r");
    while (fgets(a[i], 142, fp) != NULL) { // last 2 bytes are don't care: '\n\0'
        i++;
    }
    fclose(fp);

    for (i = 0; i < 140; i++) {
        for (j = 0; j < 140; j++) {
            part1 += check_xmas(a, i, j);
            part2 += check_mas(a, i, j);
        }
    }
    printf("part 1: %d\n", part1);
    printf("part 2: %d\n", part2);
    return 0;
}

public class Solver
{
    private struct Vector() : IEquatable<Vector>
    {
        public Vector(int x, int y) : this()
        {
            X = x;
            Y = y;
        }

        public Vector(Vector v) : this()
        {
            X = v.X;
            Y = v.Y;
        }
        
        public int X { get; private set; }
        public int Y { get; private set; }
        
        public static Vector operator - (Vector a, Vector b)
        {
            return new Vector(a.X - b.X, a.Y - b.Y);
        }
        public static Vector operator + (Vector a, Vector b)
        {
            return new Vector(a.X + b.X, a.Y + b.Y);
        }

        public static bool operator ==(Vector a, Vector b)
        {
            return a.X == b.X && a.Y == b.Y;
        }
        public static bool operator !=(Vector a, Vector b)
        {
            return a == b == false;
        }

        public bool Equals(Vector other)
        {
            return X == other.X && Y == other.Y;
        }

        public override bool Equals(object? obj)
        {
            return obj is Vector other && Equals(other);
        }

        public override int GetHashCode()
        {
            return HashCode.Combine(X, Y);
        }
    }
    private struct Node(Vector position, string value)
    {
        public Vector Position { get; set; } = position;
        public string Value { get; set; } = value;
    }
    
    private static Node[,] GetGrid(string input)
    {
        string[] lines = input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries);
        int height = lines.Length;
        int width = lines[0].Length;
        var grid = new Node[width, height];
        
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                grid[y, x] =  new Node(new Vector(x, y), lines[y][x].ToString());
            }
        }

        return grid;
    }
    private static Vector GetDistanceBetweenNodes(Node a, Node b)
    {
        return new Vector(a.Position - b.Position);
    }
    private static Node? GetNodeAtDistance(Vector distance, Node otherNode, Node[,] grid)
    {
        var pos = otherNode.Position + distance;
        if (pos.X < 0 || pos.X >= grid.GetLength(1))
        {
            return null;
        }
        if (pos.Y < 0 || pos.Y >= grid.GetLength(0))
        {
            return null;
        }
        
        return grid[pos.Y, pos.X];
    }

    private static List<Node> GetAllNodesInDirectionTowardsB(Node a, Node b, Node[,] grid)
    {
        var delta = b.Position - a.Position;
        
        var gcd = GCD(Math.Abs(delta.X), Math.Abs(delta.Y));
        int stepX = delta.X / gcd;
        int stepY = delta.Y / gcd;
        
        int x = a.Position.X;
        int y = a.Position.Y;
        var currentNode = a;
        
        var nodes = new List<Node>();
        while (true)
        {
            nodes.Add(currentNode);
            x += stepX;
            y += stepY;
            if ((x < 0 || x >= grid.GetLength(1)) ||
                (y < 0 || y >= grid.GetLength(0)))
                break;
            
            currentNode = grid[y, x];
        }
        return nodes;
    }

    private static int GCD(int a, int b)
    {
        while (b != 0)
        {
            int temp = b;
            b = a % b;
            a = temp;
        }

        return a;
    }
    
    public static int Run_PartOne(string input)
    {
        var grid = GetGrid(input);
        var distinctNodes = new Dictionary<string, List<Node>>();
        var antiNodes = new List<Node>();
        
        
        for (int y = 0; y < grid.GetLength(0); y++)
        {
            for (int x = 0; x < grid.GetLength(1); x++)
            {
                var node = grid[y, x];
                if (node.Value == ".") continue;
                
                if (!distinctNodes.TryAdd(node.Value, [node]))
                {
                    distinctNodes[node.Value].Add(node);
                }
            }
        }

        foreach (var kvp in distinctNodes)
        {
            foreach (var node in kvp.Value)
            {
                foreach (var node2 in kvp.Value)
                {
                    if (node.Position == node2.Position)
                        continue;
                    
                    var distance = GetDistanceBetweenNodes(node, node2);
                    var node3 = GetNodeAtDistance(distance, node, grid);
                    if (node3.HasValue)
                    {
                        antiNodes.Add(node3.Value);
                    }
                }
            }
        }
        
        return antiNodes.DistinctBy(x => x.Position).Count();
    }
    
    public static int Run_PartTwo(string input)
    {
        var grid = GetGrid(input);
        var distinctNodes = new Dictionary<string, List<Node>>();
        var antiNodes = new List<Node>();
        
        
        for (int y = 0; y < grid.GetLength(0); y++)
        {
            for (int x = 0; x < grid.GetLength(1); x++)
            {
                var node = grid[y, x];
                if (node.Value == ".") continue;
                
                if (!distinctNodes.TryAdd(node.Value, [node]))
                {
                    distinctNodes[node.Value].Add(node);
                }
            }
        }

        foreach (var kvp in distinctNodes)
        {
            foreach (var node in kvp.Value)
            {
                foreach (var node2 in kvp.Value)
                {
                    if (node.Position == node2.Position)
                        continue;

                    var nodes = GetAllNodesInDirectionTowardsB(node, node2, grid);
                    foreach (var node3 in nodes)
                    {
                        antiNodes.Add(node3);
                    }
                }
            }
        }
     
        return antiNodes.DistinctBy(x => x.Position).Count();
    }
}

use std::fs;

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

type Number = i64;

pub fn read_result_and_numbers(path: &str) -> Vec<(Number, Vec<Number>)> {
    fs::read_to_string(path)
        .expect("Failed to read input file")
        .lines()
        .map(|line| {
            let parts: Vec<&str> = line.split(':').collect();
            let test_value = parts[0].parse().expect("Failed to parse number");
            let numbers = parts[1]
                .split_whitespace()
                .map(|num| num.parse().expect("Failed to parse number"))
                .rev()
                .collect();
            (test_value, numbers)
        })
        .collect()
}

pub fn part1(equations: &[(Number, Vec<Number>)]) -> Number {
    total_calibration_result(equations, |result, numbers| {
        is_equation_valid(result, numbers, false)
    })
}

pub fn part2(equations: &[(Number, Vec<Number>)]) -> Number {
    total_calibration_result(equations, |result, numbers| {
        is_equation_valid(result, numbers, true)
    })
}

pub fn total_calibration_result(
    equations: &[(Number, Vec<Number>)],
    pred: impl Fn(Number, &[Number]) -> bool,
) -> Number {
    equations
        .iter()
        .filter(|(result, numbers)| pred(*result, &numbers))
        .map(|(result, _)| result)
        .sum()
}

fn is_equation_valid(result: Number, numbers: &[Number], use_concat: bool) -> bool {
    if numbers.is_empty() {
        return false;
    }
    let rhs = numbers[0];
    let lhs = &numbers[1..];
    (lhs.len() == 0 && result == rhs)
        || (use_concat && {
            let lhs_factor = next_larger_power_of_10(rhs); // lhs || rhs -> lhs * lhs_factor + rhs
            is_factor(result - rhs, lhs_factor) && is_equation_valid(result / lhs_factor, lhs, true)
        })
        || (is_factor(result, rhs) && is_equation_valid(result / rhs, lhs, use_concat))
        || (result >= rhs && is_equation_valid(result - rhs, lhs, use_concat))
}

fn is_factor(product: Number, number: Number) -> bool {
    product % number == 0
}

fn next_larger_power_of_10(n: Number) -> Number {
    let mut factor = 10;
    while factor <= n {
        factor *= 10;
    }
    factor
}

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

use std::fs;

use ahash::AHashMap;
use itertools::Itertools;

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

#[derive(Debug)]
pub struct Vec2D {
    x: i32,
    y: i32,
}

pub type AntennaPositions = Vec<Vec2D>;

pub fn read_map_dimensions_and_antenna_positions(
    path: &str,
) -> ((i32, i32), Vec<AntennaPositions>) {
    let content = fs::read_to_string(path).expect("Failed to read file");
    let mut antenna_positions: AHashMap<char, AntennaPositions> = AHashMap::new();
    let mut height = 0;
    let mut width = 0;
    for (y, line) in content.lines().enumerate() {
        height += 1;
        width = line.len() as i32;
        for (x, ch) in line.chars().enumerate() {
            if ch != '.' {
                antenna_positions
                    .entry(ch)
                    .or_insert_with(Vec::new)
                    .push(Vec2D {
                        x: x as i32,
                        y: y as i32,
                    });
            }
        }
    }
    ((width, height), antenna_positions.into_values().collect())
}

pub fn part1(width: i32, height: i32, antenna_positions: &[AntennaPositions]) -> u32 {
    let mut antinodes = vec![0u64; height as usize];
    let mut mark_antinode = |a: &Vec2D, b: &Vec2D| {
        let x = 2 * b.x - a.x;
        let y = 2 * b.y - a.y;
        if x >= 0 && x < width && y >= 0 && y < height {
            antinodes[y as usize] |= 1 << x;
        }
    };
    for positions in antenna_positions {
        for pair in positions.iter().combinations(2) {
            mark_antinode(pair[0], pair[1]);
            mark_antinode(pair[1], pair[0]);
        }
    }
    antinodes.into_iter().map(|row| row.count_ones()).sum()
}

pub fn part2(width: i32, height: i32, antenna_positions: &[AntennaPositions]) -> u32 {
    let mut antinodes = vec![0u64; height as usize];
    let mut mark_antinode_and_harmonics = |a: &Vec2D, b: &Vec2D| {
        let dx = b.x - a.x;
        let dy = b.y - a.y;
        let mut x = b.x;
        let mut y = b.y;
        while x >= 0 && x < width && y >= 0 && y < height {
            antinodes[y as usize] |= 1 << x;
            x += dx;
            y += dy;
        }
    };
    for positions in antenna_positions {
        for pair in positions.iter().combinations(2) {
            mark_antinode_and_harmonics(pair[0], pair[1]);
            mark_antinode_and_harmonics(pair[1], pair[0]);
        }
    }
    antinodes.into_iter().map(|row| row.count_ones()).sum()
}

fn main() {
    let ((width, height), antenna_positions) =
        read_map_dimensions_and_antenna_positions(&INPUT_FILE);
    println!("part 1: {}", part1(width, height, &antenna_positions));
    println!("part 2: {}", part2(width, height, &antenna_positions));
}

import numpy as np
from itertools import combinations

a = np.array([[c for c in l.strip()] for l in open("input08.txt", "r").readlines()])
p1 = set()
p2 = set()

def part1(x1, y1, x2, y2):
    dx, dy = x2 - x1, y2 - y1
    x1, y1 = x1 - dx, y1 - dy
    x2, y2 = x2 + dx, y2 + dy
    if 0 <= x1 < a.shape[0] and 0 <= y1 < a.shape[1]:
        p1.add((x1, y1))
    if  0 <= x2 < a.shape[0] and 0 <= y2 < a.shape[1]:
        p1.add((x2, y2))

def part2(x1, y1, x2, y2):
    dx, dy = x2 - x1, y2 - y1
    while 0 <= x1 < a.shape[0] and 0 <= y1 < a.shape[1]:
        p2.add((x1, y1))
        x1, y1 = x1 - dx, y1 - dy
    while 0 <= x2 < a.shape[0] and 0 <= y2 < a.shape[1]:
        p2.add((x2, y2) )
        x2, y2 = x2 + dx, y2 + dy
        
for c in np.unique(a[a != '.']):
    for (x1, y1), (x2, y2) in combinations(zip(*np.where(a == c)), 2):
        part1(x1, y1, x2, y2)
        part2(x1, y1, x2, y2)
print(len(p1), len(p2))