🌟 Advent of Code (AoC) 2021 🌟

const PAIR: &[char; 4] = &['<', '(', '[', '{'];
const SCORE: &[u32; 4] = &[25137, 3, 57, 1197];
const SCORE2: &[usize; 4] = &[4, 1, 2, 3];

fn main() {
    let input = std::fs::read_to_string("input.txt").unwrap();
    println!(
        "Part 1: {}",
        input
            .lines()
            .filter_map(|f| process(f, false).err())
            .map(|chr| match_with(chr, SCORE))
            .sum::<u32>()
    ); // 411471

    let mut scores = input
        .lines()
        .filter(|f| process(f, false).is_ok())
        .filter_map(|f| process(f, true).ok())
        .map(|f| {
            f.iter()
                .fold(0usize, |acc, &chr| acc * 5 + match_with(chr, SCORE2))
        })
        .collect::<Vec<_>>();
    scores.sort_unstable();
    println!("Part 2: {}", scores[scores.len() / 2]); // 3122628974
}

fn process(s: &str, repair: bool) -> Result<Vec<char>, char> {
    let mut acc = vec![];
    for value in s.chars() {
        if matches!(value, '>' | ')' | ']' | '}') {
            if repair {
                acc.pop();
            } else {
                acc.pop()
                    .filter(|&p| p == match_with(value, PAIR))
                    .ok_or(value)?;
            }
        } else {
            acc.push(value)
        }
    }
    acc.reverse();
    Ok(acc)
}

fn match_with<T: Copy>(chr: char, m: &[T; 4]) -> T {
    match chr {
        '>' | '<' => m[0],
        ')' | '(' => m[1],
        ']' | '[' => m[2],
        '}' | '{' => m[3],
        _ => panic!("brunsås"),
    }
}

internal class Day09 : Puzzle
{
    private static int _xMax;
    private static int _yMax;

    public override object PartOne()
    {
        var map = GetLocations().ToDictionary(p => (p.X, p.Y));
        
        return map.Where(p => GetAdjacentLocations(map, p.Key.X, p.Key.Y).All(a => a.Height > p.Value.Height))
            .Sum(p => p.Value.Height + 1);
    }

    public override object PartTwo()
    {
        var map = GetLocations().ToDictionary(p => (p.X, p.Y));
        
        return map.Where(p => GetAdjacentLocations(map, p.Key.X, p.Key.Y).All(a => a.Height > p.Value.Height))
            .Select(x => GetBasinSize(map, x.Key.X, x.Key.Y))
            .OrderByDescending(x => x)
            .Take(3)
            .Aggregate(1, (current, basin) => current * basin);
    }

    private static IEnumerable<Location> GetAdjacentLocations(IDictionary<(int, int), Location> map, int x, int y)
    {
        return new (int X, int Y)[] { (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1) }
            .Where(a => a.X.IsBetween(0, _xMax) && a.Y.IsBetween(0, _yMax))
            .Select(a => map[(a.X, a.Y)]);
    }

    private static int GetBasinSize(IDictionary<(int, int), Location> map, int x, int y) => GetBasin(map, x, y).Distinct().Count() + 1;

    private static IEnumerable<Location> GetBasin(IDictionary<(int, int), Location> map, int x, int y)
    {
        var higherAdjacentLocations = GetAdjacentLocations(map, x, y)
            .Where(a => a.Height != 9 && a.Height > map[(x, y)].Height)
            .ToArray();

        return higherAdjacentLocations.Concat(higherAdjacentLocations.SelectMany(a => GetBasin(map, a.X, a.Y)));
    }

    private IEnumerable<Location> GetLocations()
    {
        var rows = Utilities.GetInput(GetType())
            .Split(Environment.NewLine);

        _yMax = rows.Length - 1;
        _xMax = rows[0].Length - 1;

        for (var y = 0; y < rows.Length; y++)
        for (var x = 0; x < rows[y].Length; x++)
            yield return new Location(x, y, (int)char.GetNumericValue(rows[y][x]));
    }

    private record Location(int X, int Y, int Height);
}

internal class Day10 : Puzzle
{
    public override object PartOne()
    {
        return GetChunks()
            .Select(x => ValidateChunk(x, new Stack<char>()))
            .Where(x => x.Status == ChunkStatusEnum.Corrupted)
            .Sum(x => GetChunkOperator(x.FirstInvalidCharacter).FirstScore);
    }

    public override object PartTwo()
    {
        var scores = GetChunks()
            .Select(x => ValidateChunk(x, new Stack<char>()))
            .Where(x => x.Status == ChunkStatusEnum.Incomplete)
            .Select(x => CalculateScore(x.RemainingCharacters))
            .OrderBy(x => x)
            .ToArray();

        return scores[(scores.Length - 1) / 2];
    }

    private static (ChunkStatusEnum Status, char? FirstInvalidCharacter, Stack<char> RemainingCharacters) ValidateChunk(Queue<char> chunk, Stack<char> openings)
    {
        if (chunk.Count == 0)
            return openings.Count == 0 ? (ChunkStatusEnum.Valid, null, openings) : (ChunkStatusEnum.Incomplete, null, openings);

        var currentChar = chunk.Dequeue();

        if (IsClosingCharacter(currentChar))
            return openings.Pop() == GetChunkOperator(currentChar).Opening ? ValidateChunk(chunk, openings) : (ChunkStatusEnum.Corrupted, currentChar, openings);

        openings.Push(currentChar);
        return ValidateChunk(chunk, openings);
    }

    private static long CalculateScore(IEnumerable<char> characters) => characters.Aggregate<char, long>(0, (sum, c) => sum * 5 + GetChunkOperator(c).SecondScore);
    private static ChunkOperator GetChunkOperator(char? op) => ChunkOperators.Single(x => x.Opening == op || x.Closing == op);
    private static bool IsClosingCharacter(char op) => ChunkOperators.Any(x => x.Closing == op);

    private static ChunkOperator[] ChunkOperators => new[]
    {
        new ChunkOperator('(', ')', 3, 1), 
        new ChunkOperator('[', ']', 57, 2), 
        new ChunkOperator('{', '}', 1197, 3), 
        new ChunkOperator('<', '>', 25137, 4)
    };

    private IEnumerable<Queue<char>> GetChunks()
    {
        return Utilities.GetInput(GetType())
            .Split(Environment.NewLine)
            .Select(x => new Queue<char>(x.ToCharArray()));
    }

    private record ChunkOperator(char Opening, char Closing, int FirstScore, int SecondScore);

    private enum ChunkStatusEnum
    {
        Valid,
        Incomplete,
        Corrupted
    }
}

const ADJACENT: &[(i64, i64); 8] = &[
    (-1, -1),
    (0, -1),
    (1, -1),
    (-1, 0),
    (1, 0),
    (-1, 1),
    (0, 1),
    (1, 1),
];
const WIDTH: i64 = 10;
const HEIGHT: i64 = 10;

macro_rules! check_and_update {
    ($input:expr, $arr:expr, $count:expr, $x:expr, $y:expr) => {{
        $input[$y][$x] += 1;
        if $input[$y][$x] > 9 {
            $input[$y][$x] = 0;
            $count += 1;
            $arr.push(($x, $y))
        }
    }};
}

fn main() {
    let mut input: Vec<Vec<_>> = std::fs::read_to_string("input.txt")
        .unwrap()
        .lines()
        .map(|s| {
            s.chars()
                .filter_map(|c| c.to_digit(10).map(|d| d as usize))
                .collect()
        })
        .collect();

    println!("{}", part1(&mut input.clone())); // 1665
    println!("{}", part2(&mut input)); // 235
}

fn part1(input: &mut Vec<Vec<usize>>) -> u64 {
    (0..100).fold(0, |acc, _| acc + calc_step(input))
}

fn part2(input: &mut Vec<Vec<usize>>) -> u64 {
    let mut steps = 0;
    while !input.iter().all(|a| a.iter().all(|&b| b == 0)) {
        calc_step(input);
        steps += 1;
    }
    steps
}

fn calc_step(input: &mut Vec<Vec<usize>>) -> u64 {
    let mut flashes = vec![];
    let mut count = 0;
    for y in 0..input.len() {
        for x in 0..input[0].len() {
            check_and_update!(input, flashes, count, x, y);
        }
    }

    while !flashes.is_empty() {
        for flash in flashes.drain(0..).collect::<Vec<_>>() {
            flashes.append(
                &mut adjacent(flash).iter().fold(vec![], |mut acc, &(x, y)| {
                    if input[y][x] != 0 {
                        check_and_update!(input, acc, count, x, y);
                    }
                    acc
                }),
            )
        }
    }
    count
}

fn adjacent((x, y): (usize, usize)) -> Vec<(usize, usize)> {
    ADJACENT
        .iter()
        .filter(|&(dx, dy)| {
            let x = x as i64;
            let y = y as i64;
            x + dx >= 0 && y + dy >= 0 && x + dx < WIDTH && y + dy < HEIGHT
        })
        .map(|&(dx, dy)| ((x as i64 + dx) as usize, (y as i64 + dy) as usize))
        .collect()
}

object Day11 {
	val data = readLines("11/data.txt")

	case class Elem(idx: Int, value: Int, affect: Seq[Int]) {
		def reset = copy(value = 0)
		def inc(count: Int) = copy(value = value + count)
	}

	def main(args: Array[String]): Unit = {

		def idx(x: Int, y: Int) = y * 10 + x

		val elems = for(y <- 0 until 10; x <- 0 until 10) yield {
			val value = data(y)(x).toString.toInt
			val valid = (0 until 10).toSet
			val affect = for {
				dy <- -1 to 1
				dx <- -1 to 1
				if dx != 0 || dy != 0
				if valid(x + dx) && valid(y + dy)
			} yield idx(x + dx, y + dy)
			Elem(idx(x, y), value, affect)
		}

		def step(elems: Seq[Elem], toIncrease: Seq[Int]): (Seq[Elem], Int) = {
			if(toIncrease.isEmpty) {
				(elems, 0)
			} else {
				val plusOne = elems.map { e => e.inc(toIncrease.count(_ == e.idx)) }
				val (flashed, other) = plusOne.partition(_.value > 9)
				val affected = flashed.flatMap(_.affect)
				val (subSeq, subFlashed) = step(other, affected)
				(subSeq ++ flashed.map(e => e.reset), flashed.size + subFlashed)
			}
		}

		// part 1
		var es: Seq[Elem] = elems
		var totFlashes = 0
		for(_ <- 0 until 100) {
			val (newEs, flashes) = step(es, 0 until 100)
			totFlashes += flashes
			es = newEs
		}
		println(totFlashes)

		// part 2
		es = elems
		val allFlashStepOpt = Iterator.from(1).find { i =>
			val (newEs, flashes) = step(es, 0 until 100)
			es = newEs
			flashes == 100
		}
		println(allFlashStepOpt)
	}
}

internal class Puzzle11 : Puzzle<int>
{
    private int[,] _grid = default!;

    protected override void Solve(string[] lines)
    {
        _grid = Grid.CreateGrid(lines);

        int step = 0, totalFlashCount = 0;
        while (true)
        {
            step++;
            var flashedSquids = new HashSet<(int x, int y)>();
            var flashCount = Grid.Iterate(_grid).Sum(c => Flash(c, flashedSquids));
            if (step <= 100)
            {
                totalFlashCount += flashCount;
            }
            if (flashCount == _grid.Length)
            {
                break;
            }
        }

        One = totalFlashCount;
        Two = step;
    }

    private int Flash((int x, int y) coord, ISet<(int x, int y)> flashedSquids)
    {
        if (flashedSquids.Contains(coord))
        {
            return 0;
        }

        if (_grid[coord.x, coord.y] < 9)
        {
            _grid[coord.x, coord.y]++;
            return 0;
        }

        _grid[coord.x, coord.y] = 0;
        flashedSquids.Add(coord);

        return 1 + Grid.GetNeighbours(_grid, coord, true)
            .Sum(n => Flash(n, flashedSquids));
    }
}

(import std)

(define main
  (do io/bind
      (<- input (io/map unwrap! (read-file "inputs/day11.txt")))
      (let ((flat-array (array/collect (map (<o to-int (flip - ascii-0))
                                            (flat-map string/bytes (lines input)))))
            (grid (array/collect (array/chunks (to-nat 10) flat-array)))))
      (display (str-append "Part 1: " (show-int (part1 grid))))
      (display (str-append "Part 2: " (show-int (part2 1 grid))))))

(define (part1 grid)
  (car (foldl (fun ([n grid] _) (map-car (+ n) (step grid))) [0 grid] (xrange 0 100))))

(define (part2 n-steps grid)
  (let1 [n grid] (step grid) (if (= n 100) n-steps (part2 (inc n-steps) grid))))

(define (step grid)
  (define (filter-flashing grid ixs) (filter (<o (= 10) (flip array/lookup2d! grid)) ixs))
  (define (flash-octopuses n grid)
    (fmatch
      (case None [n (array/map (array/map (fun (x) (if (> x 9) 0 x))) grid)])
      (case (Some [ix rest])
            (let ((as (adjecents (map-both to-int ix)))
                  (grid (foldl (fun (grid a) (array/modify2d! inc a grid)) grid as)))
              (flash-octopuses (+ n 1) grid (next (iter/chain rest (filter-flashing grid as))))))))
  (let ((grid (array/map (array/map inc) grid))
        (flashing (filter-flashing grid (iter/cartesian (range (to-nat 0) (to-nat 9))
                                                        (range (to-nat 0) (to-nat 9)))))
        ([n grid] (flash-octopuses 0 grid (next flashing))))
    [n grid]))

(define (adjecents [i j])
  (iter/cartesian (range (to-nat (max 0 (- i 1))) (to-nat (min 9 (+ i 1))))
                  (range (to-nat (max 0 (- j 1))) (to-nat (min 9 (+ j 1))))))

import numpy as np
from scipy.signal import convolve2d

grid = np.array([[int(x) for x in line.rstrip()] for line in open("11.in")])

flash_count = 0
step = 0
while grid.any():
    step += 1
    grid += 1
    has_flashed = np.zeros_like(grid, dtype=bool)
    while not np.all((could_flash := (grid > 9)) == has_flashed):
        grid += convolve2d(could_flash & ~has_flashed, [[1, 1, 1], [1, 0, 1], [1, 1, 1]], "same")
        has_flashed[could_flash] = True
    flash_count += np.sum(has_flashed)
    grid[could_flash] = 0
    if step == 100:
        print(flash_count)
print(step)

#include <set>
#include <climits>
#include <chrono>

#include "../utils/file_reader.cpp"
#include "../utils/result_printer.cpp"

typedef pair<int,int> coord;
typedef vector<vector<int>> grid;

grid parse(vector<string> str_data)
{
    vector<vector<int>> data;
    int n_rows = str_data.size();
    for (auto const row:str_data)
    {
        vector<int> row_data;
        for (char const num:row)
        {
            row_data.push_back(num-48);
        }
        data.push_back(row_data);
    }

    return data;
}

vector<coord> get_neighbours()
{
    vector<coord> neighbours = {{1,-1},{1,0},{1,1},{0,1},{0,-1},{-1,-1},{-1,0},{-1,1}};
    return neighbours;
}

int solve(grid data, bool part2)
{
    int n_flashes = 0;
    int step_flashes;
    int n_steps = part2? INT_MAX : 100;
    
    int n = data[0].size();
    int m = data.size();
    int nm = n*m;

    set<pair<int,int>> flash_coords;
    vector<coord> nbs = get_neighbours();

    for (int step = 0; step < n_steps; step++)
    {
        if (part2 && step_flashes == nm)
        {
            return step;
        }
        step_flashes = 0;

        //first substep
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (data[i][j] == 9)
                {
                    data[i][j] = 0;
                    n_flashes++;
                    step_flashes++;
                    flash_coords.insert(make_pair(i, j));
                }
                else
                {
                    data[i][j]++;
                }
            }
        }

        //second substep
        while (flash_coords.size() > 0)
        {
            set<pair<int, int>> coords(flash_coords);
            flash_coords.clear();

            for (const auto &coord : coords)
            {                
                for (const auto &nb:nbs)
                {
                    int ip = coord.first + nb.first;
                    int jp = coord.second + nb.second;
                    if (ip >= 0 && ip < m && jp >= 0 && jp < n)
                    {
                        if (data[ip][jp] == 9)
                        {
                            data[ip][jp] = 0;
                            n_flashes++;
                            step_flashes++;
                            flash_coords.insert(make_pair(ip,jp));
                        }
                        else if (data[ip][jp]>0)
                        {
                            data[ip][jp]++;
                        }    
                    }
                }
            }
        }
    }

    return n_flashes;
}

int main()
{
   
    int day = 11;

    auto start = chrono::high_resolution_clock::now();
    
    string filename = "../../input/day_" + to_string(day) + ".txt";
    vector<string> string_data = read_file<string>(filename,true);
    grid data = parse(string_data);
    auto parsed = chrono::high_resolution_clock::now();
    
    int part_1 = solve(data, false);
    int part_2 = solve(data, true);
    auto solved = chrono::high_resolution_clock::now();
    
    vector<chrono::high_resolution_clock::time_point> time_stamps{start , parsed, solved};
    print_results<int>(day, part_1, part_2, time_stamps);

}

from collections import defaultdict
from typing import List

neighbours = defaultdict(list)
for line in open("12.in"):
    a, b = line.rstrip().split("-")
    neighbours[a].append(b)
    neighbours[b].append(a)


def explore(cave: str, seen: List[str], allow_double_visits: bool) -> int:
    return int(cave == "end") + sum(
        explore(neighbour, seen + [cave] if cave.islower() else seen, not_seen and allow_double_visits)
        for neighbour in neighbours[cave]
        if ((not_seen := (neighbour not in seen)) or allow_double_visits) and cave not in ("start", "end")
    )


print(sum(explore(start, [], False) for start in neighbours["start"]))
print(sum(explore(start, [], True) for start in neighbours["start"]))

object Day12 {
	val data = readLines("12/data.txt")

	val links = data.flatMap { case s"$from-$to" => Seq(from -> to, to -> from) } .groupMap(_._1)(_._2)

	def large(cave: String) = cave.head.isUpper
	def small(cave: String) = !large(cave)

	def main(args: Array[String]): Unit = {
		type Path = Seq[String]

		// part 1
		def explore1(path: Path): Seq[Path] = {
			if(path.last == "end") {
				Seq(path)
			} else {
				val paths = for {
					cave <- links(path.last)
					if large(cave) || !path.contains(cave)
				} yield explore1(path :+ cave)
				paths.flatten
			}
		}
		println(explore1(Seq("start")).size)


		// part 2
		def explore2(path: Path, allowDuplicates: Boolean = true): Seq[Path] = {
			if(path.last == "end") {
				Seq(path)
			} else {
				val paths = for {
					cave <- links(path.last)
					duplicate = small(cave) && path.contains(cave)
					if cave != "start"
					if large(cave) || !duplicate || allowDuplicates
				} yield explore2(path :+ cave, allowDuplicates && !duplicate)
				paths.flatten
			}
		}
		println(explore2(Seq("start")).size)
	}

}