🌟 Advent of Code (AoC) 2021 🌟

using System;
using System.Linq;

namespace Aoc2021.Puzzles
{
    internal class Day07 : Puzzle
    {
        public override object PartOne() => CalculateMinFuelCost(d => d);

        public override object PartTwo() => CalculateMinFuelCost(d => (d * d + d) / 2);

        private int CalculateMinFuelCost(Func<int, int> fuelCostFunc)
        {
            var positions = Utilities.GetInput(GetType())
                .Split(",")
                .Select(int.Parse)
                .ToArray();

            var (start, count) = (positions.Min(), positions.Max() - positions.Min() + 1);
            
            return Enumerable.Range(start, count)
                .AsParallel()
                .Min(position => CalculateFuelCostAtPosition(positions, position, fuelCostFunc));
        }

        private static int CalculateFuelCostAtPosition(int[] positions, int position, Func<int, int> fuelCostFunc)
        {
            return positions
                .Select(p => Math.Abs(position - p))
                .Sum(fuelCostFunc);
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Aoc2021.Puzzles
{
    internal class Day08 : Puzzle
    {
        public override object PartOne()
        {
            return ReadInput()
                .SelectMany(x => x.Output)
                .Count(x => new[] { 2, 3, 4, 7 }.Contains(x.Length));
        }

        public override object PartTwo()
        {
            return ReadInput()
                .Select(x => (x.Output, Map: DecipherSignalPatterns(x.Input)))
                .Sum(x => ConvertOutputSignalsToValue(x.Output, x.Map));
        }

        private static int ConvertOutputSignalsToValue(string[] output, IDictionary<int, string> map)
        {
            return output.Select(p => GetOutputDigit(map, p))
                .Select((x, i) => x * (int)Math.Pow(10, 3 - i))
                .Sum();
        }

        private static int GetOutputDigit(IDictionary<int, string> map, string pattern)
        {
            return map.Single(m => m.Value.ElementsEqual(pattern)).Key;
        }

        private static IDictionary<int, string> DecipherSignalPatterns(string[] patterns)
        {
            var map = new Dictionary<int, string>
            {
                { 1, patterns.Single(p => p.Length == 2) },
                { 4, patterns.Single(p => p.Length == 4) },
                { 7, patterns.Single(p => p.Length == 3) },
                { 8, patterns.Single(p => p.Length == 7) }
            };

            map.Add(3, patterns.Single(p => p.Length == 5 && map[7].All(p.Contains)));
            map.Add(9, patterns.Single(p => p.Length == 6 && map[3].All(p.Contains)));
            map.Add(0, patterns.Single(p => p.Length == 6 && map[7].All(p.Contains) && map.None(x => x.Value == p)));
            map.Add(6, patterns.Single(p => p.Length == 6 && map.None(x => x.Value == p)));
            map.Add(5, patterns.Single(p => p.Length == 5 && p.All(x => map[6].Contains(x))));
            map.Add(2, patterns.Single(p => map.None(x => x.Value == p)));

            return map;
        }

        private (string[] Input, string[] Output)[] ReadInput()
        {
            return Utilities.GetInput(GetType())
                .Split(Environment.NewLine)
                .Select(row => Regex.Matches(row, @\w{1,7}\b).Select(x => x.Value).ToArray())
                .Select(x => (x.Take(10).ToArray(), x.TakeLast(4).ToArray()))
                .ToArray();
        }
    }
}

val input = Using.resource(Source.fromFile("8.txt"))(_.getLines().toList)

input.map { case s"$_ | $s" => s.split(' ').count(x => Set(2, 3, 4, 7)(x.length)) }.sum

input.map { case s"$s1 | $s2" =>
   val pat  = s1.split(' ')
   val out  = s2.split(' ')
   val one  = pat.find(_.length == 2).get.toSet
   val four = pat.find(_.length == 4).get.toSet
   val mapping = pat.map { key =>
      key.sorted -> (key.length, key.count(one), key.count(four)).match
         case (2, _, _) => 1
         case (3, _, _) => 7
         case (4, _, _) => 4
         case (5, 1, 3) => 5
         case (5, _, 2) => 2
         case (5, _, _) => 3
         case (6, 1, _) => 6
         case (6, _, 3) => 0
         case (6, _, _) => 9
         case (7, _, _) => 8
   }.toMap
   out.map(x => mapping(x.sorted)).mkString.toInt
}.sum

use std::collections::HashMap;

const ZERO: &[usize; 6] = &[0, 1, 2, 4, 5, 6];
const ONE: &[usize; 2] = &[2, 5];
const TWO: &[usize; 5] = &[0, 2, 3, 4, 6];
const THREE: &[usize; 5] = &[0, 2, 3, 5, 6];
const FOUR: &[usize; 4] = &[1, 2, 3, 5];
const FIVE: &[usize; 5] = &[0, 1, 3, 5, 6];
const SIX: &[usize; 6] = &[0, 1, 3, 4, 5, 6];
const SEVEN: &[usize; 3] = &[0, 2, 5];
const EIGHT: &[usize; 7] = &[0, 1, 2, 3, 4, 5, 6];
const NINE: &[usize; 6] = &[0, 1, 2, 3, 5, 6];

fn main() {
    let input = std::fs::read_to_string("input.txt").unwrap();
    let input: Vec<_> = input
        .lines()
        .map(|s| s.split_once('|').unwrap())
        .map(|t| {
            let mut a = t.0.split_whitespace().collect::<Vec<_>>();
            let b = t.1.split_whitespace().collect::<Vec<_>>();
            a.sort_by(|a, b| a.len().cmp(&b.len()));
            (a, b)
        })
        .collect();

    println!("part 1: {}", part1(&input)); // 318
    println!("part 2: {}", part2(&input).unwrap()); // 996280
}

fn part1(data: &[(Vec<&str>, Vec<&str>)]) -> usize {
    data.iter()
        .flat_map(|p| &p.1)
        .filter(|p| matches!(p.len(), 2 | 3 | 4 | 7))
        .count()
}

fn part2(data: &[(Vec<&str>, Vec<&str>)]) -> Option<usize> {
    let mut total = 0;
    for (usp, out) in data.iter() {
        let segment_occurences: HashMap<char, u8> =
            usp.iter()
                .flat_map(|s| s.chars())
                .fold(HashMap::new(), |mut map, v| {
                    *map.entry(v).or_default() += 1;
                    map
                });

        let mut segments = [' '; 7];
        for code in usp.iter() {
            // Samlar ihop så vi slipper dubbelborrow
            let only_new_segments: Vec<_> = code
                .chars()
                .filter(|c| !segments.contains(c))
                .map(|c| (c, segment_occurences.get(&c).unwrap()))
                .collect();
            for (chr, occurences) in only_new_segments {
                match (code.len(), occurences) {
                    (2, 8) => segments[2] = chr,
                    (2, _) => segments[5] = chr,
                    (3, _) => segments[0] = chr,
                    (4, 6) => segments[1] = chr,
                    (4, _) => segments[3] = chr,
                    (7, 4) => segments[4] = chr,
                    (7, _) => segments[6] = chr,
                    _ => (),
                }
            }
        }
        // Bygg ihop talet
        total += out
            .iter()
            .fold(0usize, |acc, digit| acc * 10 + get_digit(&segments, digit));
    }
    Some(total)
}

fn get_digit(segments: &[char; 7], digit: &str) -> usize {
    match digit.len() {
        6 if chk_chrs(ZERO.iter().map(|&f| segments[f]), digit) => 0,
        2 if chk_chrs(ONE.iter().map(|&f| segments[f]), digit) => 1,
        5 if chk_chrs(TWO.iter().map(|&f| segments[f]), digit) => 2,
        5 if chk_chrs(THREE.iter().map(|&f| segments[f]), digit) => 3,
        4 if chk_chrs(FOUR.iter().map(|&f| segments[f]), digit) => 4,
        5 if chk_chrs(FIVE.iter().map(|&f| segments[f]), digit) => 5,
        6 if chk_chrs(SIX.iter().map(|&f| segments[f]), digit) => 6,
        3 if chk_chrs(SEVEN.iter().map(|&f| segments[f]), digit) => 7,
        7 if chk_chrs(EIGHT.iter().map(|&f| segments[f]), digit) => 8,
        6 if chk_chrs(NINE.iter().map(|&f| segments[f]), digit) => 9,
        _ => panic!("brunsås"),
    }
}

fn chk_chrs<'a>(mut segments: impl Iterator<Item = char>, digit: &str) -> bool {
    segments.all(|chr| digit.contains(chr))
}

object Day9 {
	val data = readLines("9/data.txt")
	val lines = data.map(_.map(_.toString.toInt))

	implicit class Adder(p: (Int, Int)) {
		def +(other: (Int, Int)) = (p._1 + other._1, p._2 + other._2)
	}

	val surrounding = Seq((-1,0), (0,-1), (1,0), (0,1))
	val zeroTo100 = 0 until 100
	def valid(p: (Int, Int)) = zeroTo100.contains(p._1) && zeroTo100.contains(p._2)
	def depth(p: (Int, Int)) = if (valid(p)) lines(p._2)(p._1) else 10
	def extend(p: (Int, Int)) = surrounding.map(dp => p + dp)

	def lowPoint(p: (Int, Int)) = {
		val center = depth(p)
		surrounding.forall(dp => depth(p + dp) > center)
	}

	val lowPoints = for {
		y <- lines.indices
		x <- lines.head.indices
		if valid(x, y) && lowPoint(x, y)
	} yield (x, y)

	def extendToBasin(p: (Int, Int)) = {
		val pointsToExtend = mutable.Queue(p)
		val basin = mutable.Set(p)
		while(pointsToExtend.nonEmpty) {
			val p = pointsToExtend.dequeue()
			val candidates = extend(p).filter { p =>
				valid(p) && depth(p) < 9 && !basin.contains(p)
			}
			basin.addAll(candidates)
			pointsToExtend.appendAll(candidates)
		}
		basin.toSet
	}

	def main(args: Array[String]): Unit = {
		// part 1
		println(lowPoints.map(p => depth(p) + 1).sum)

		// part 2
		val basins = ArrayBuffer[Set[(Int, Int)]]()
		for(lowPoint <- lowPoints if !basins.exists(_.contains(lowPoint))) {
			basins.append(extendToBasin(lowPoint))
		}

		val res = basins.sortBy(-_.size)
				.take(3)
				.map(_.size)
				.product

		println(res)
	}
}

import Data.List
import qualified Data.Set as Set

main = interact solve

solve input = "Problem 1: " ++ show (sum (map riskLevel lowPts)) ++ "\n"
           ++ "Problem 2: " ++ show ((product.(take 3).reverse.sort) (map ((Set.size).(getBasin heightmap)) lowPts)) ++ "\n"
    where
        riskLevel p = 1 + getHeight heightmap p
        lowPts = filter (isLowPoint heightmap) allPts
        allPts = [(x, y) | y <- [0..length heightmap-1], x <- [0..length (head heightmap)-1]]
        heightmap = lines input

within heightmap (x, y) = x>=0 && x<length (head heightmap) && y>=0 && y<length heightmap
getHeight heightmap (x, y) = read [((heightmap !! y) !! x)] :: Int

isLowPoint heightmap (x, y) = all higher surroundingPts
    where
        surroundingPts = filter (within heightmap) [(x, y-1), (x-1, y), (x+1, y), (x, y+1)]
        higher (x', y') = getHeight heightmap (x', y') > getHeight heightmap (x, y)


getBasin heightmap (x,y) = Set.union (Set.singleton (x,y))
         (Set.union (if relevant (x, y-1) then getBasin heightmap (x, y-1) else Set.empty)
         (Set.union (if relevant (x-1, y) then getBasin heightmap (x-1, y) else Set.empty)
         (Set.union (if relevant (x+1, y) then getBasin heightmap (x+1, y) else Set.empty)
                    (if relevant (x, y+1) then getBasin heightmap (x, y+1) else Set.empty))))
    where
        relevant (x', y') = valid (x', y') && higher (x', y') && (not.tooHigh) (x', y')
        valid (x', y') = within heightmap (x', y')
        higher (x', y') = getHeight heightmap (x', y') > getHeight heightmap (x, y)
        tooHigh (x', y') = getHeight heightmap (x', y') >= 9

internal class Puzzle9 : Puzzle<int>
{
    private static readonly (int x, int y)[] NeighborOffsets = new[] { (-1, 0), (1, 0), (0, -1), (0, 1) };

    private int _xLength;
    private int _yLength;
    private int[,] _map = default!;

    protected override void Solve(string[] lines)
    {
        _xLength = lines[0].Length;
        _yLength = lines.Length;
        _map = new int[_xLength, _yLength];

        foreach (var (x, y) in Iterate(_map))
        {
            _map[x, y] = lines[y][x] - '0';
        }

        var lowPoints = Iterate(_map).Where(IsLowPoint).ToArray();

        One = lowPoints.Sum(coord => 1 + _map[coord.x, coord.y]);
        Two = lowPoints
            .Select(c => GetBasinSize(c, new HashSet<(int x, int y)>()))
            .OrderByDescending(x => x)
            .Take(3)
            .Aggregate(1, (a,b) => a * b);
    }

    private bool IsLowPoint((int x, int y) coord) => NeighborOffsets
        .Select(offset => GetDepth(coord.x + offset.x, coord.y + offset.y, int.MaxValue))
        .All(n => n > _map[coord.x, coord.y]);

    private int GetBasinSize((int x, int y) coord, ISet<(int x, int y)> visitedNodes)
    {
        if (!visitedNodes.Add(coord))
        {
            return 0;
        }

        var depth = _map[coord.x, coord.y];
        if (depth == 9)
        {
            return 0;
        }

        return 1 + NeighborOffsets
            .Select(offset => new
            {
                coord = (coord.x + offset.x, coord.y + offset.y),
                depth = GetDepth(coord.x + offset.x, coord.y + offset.y, -1)
            })
            .Where(x => x.depth > depth)
            .Sum(x => GetBasinSize(x.coord, visitedNodes));
    }

    private int GetDepth(int x, int y, int defaultValue) => IsOutOfRange(x, y) ? defaultValue : _map[x, y];

    private bool IsOutOfRange(int x, int y) => x < 0 || x >= _xLength || y < 0 || y >= _yLength;

    private static IEnumerable<(int x, int y)> Iterate(int[,] arr)
    {
        for (int x = 0; x < arr.GetLength(0); x++)
        {
            for (int y = 0; y < arr.GetLength(1); y++)
            {
                yield return (x, y);
            }
        }
    }
}

(import std)

(define main
  (do io/bind
      (<- input (io/map unwrap! (read-file "inputs/day9.txt")))
      (let ((dim (string/length-bytes (iter/first! (lines input))))
            (height-array (array/collect (map (flip - ascii-0) (flat-map string/bytes (lines input)))))
            (heightmap (array/collect (array/chunks dim height-array)))
            (low-points (filter-map (fun (pt)
                                      (let ((h (array/lookup2d! pt heightmap))
                                            (adjs (filter-map (flip array/lookup2d heightmap)
                                                              (list/iter (adjecent-points pt)))))
                                        (if (all (< h) adjs)  (Some pt)  None)))
                                    (iter/cartesian (xrange (to-nat 0) (array/length heightmap))
                                                    (xrange (to-nat 0) dim))))))
      (display (str-append "Part 1: " (show-nat (part1 heightmap low-points))))
      (display (str-append "Part 2: " (show-nat (part2 heightmap low-points))))))

(define (part1 heightmap low-points)
  (sum (map (apps <o inc to-nat (flip array/lookup2d! heightmap)) low-points)))

(define (part2 heightmap low-points)
  (define (cmp-pt [i1 j1] [i2 j2]) (match (num/cmp i1 i2) (case Eq (num/cmp j1 j2)) (case x x)))
  (define (basin-size seen)
    (fmatch (case LNil (set/count seen))
            (case (LCons (Box [pt pts]))
                  (if (set/member? cmp-pt pt seen)
                      (basin-size seen pts)
                    (if (= 9 (maybe' 9 to-int (array/lookup2d pt heightmap)))
                        (basin-size seen pts)
                      (basin-size (set/insert cmp-pt pt seen)
                                  (list/append (adjecent-points pt) pts)))))))
  (apps |> low-points
        (map (<o (basin-size set/nil) list/singleton))
        array/collect
        (merge-sort num/cmp)
        array/iter-rev
        (take 3)
        product))

(define (adjecent-points [i j])
  (list [(dec i)   j]
        [i   (inc j)]
        [(inc i)   j]
        [i   (dec j)]))

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;
    neighbours.push_back(make_pair(1,0));
    neighbours.push_back(make_pair(-1,0));
    neighbours.push_back(make_pair(0,1));
    neighbours.push_back(make_pair(0,-1));

    return neighbours;
}

vector<coord> find_low_points(grid data, vector<coord> &neighbours)
{
    vector<coord> low_points;

    int n = data[0].size();
    int m = data.size();
    
    neighbours = get_neighbours();

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            bool low_point = true;
            int val = data[i][j];
            for(const auto nghrb : neighbours)
            {
                int ip = i + nghrb.first;
                int jp = j + nghrb.second;

                if (ip >= 0 && ip < m && jp >= 0 && jp < n)
                {
                    if (data[ip][jp] <= val) low_point = false;
                }
            }
            if (low_point)
            {
                low_points.push_back(make_pair(i,j));
            }
        }
    }

    return low_points;
}

int solve_part1(grid data)
{
    
    int count = 0;
    vector<coord> neighbours;
    vector<coord> low_points = find_low_points(data, neighbours);

    for (auto const &point:low_points)
    {
        count += (data[point.first][point.second]+1);
    }   
    
    return count;

}

int solve_part2(grid data)
{

    int n = data[0].size();
    int m = data.size();

    vector<coord> nghbrs;
    vector<coord> low_points = find_low_points(data, nghbrs);

    vector<int> b_sizes(3,0);
    vector<int> b_copy(4,0);

    set<coord>::iterator it;
    std::pair<set<coord>::iterator,bool> ret;

    for (auto const &low_point : low_points)
    {
        set<coord> basin;
        set<coord> coords,new_coords;
        
        new_coords.insert(low_point);

        do
        {
            coords = new_coords;
            new_coords.clear();

            for (it = coords.begin(); it != coords.end(); ++it)
            {

                int i = it->first;
                int j = it->second;

                for (auto const &nghbr : nghbrs)
                {
                    int ip = i + nghbr.first;
                    int jp = j + nghbr.second;
                    
                    if (ip >= 0 && ip < m && jp >= 0 && jp < n)
                    {
                        if (data[ip][jp] < 9)
                        {
                            ret = basin.insert(make_pair(ip, jp));
                            if (ret.second == true)
                            {
                                new_coords.insert(make_pair(ip, jp));
                            }
                        }
                    }
                }
            }
        } while (new_coords.size() > 0);

        copy(b_sizes.begin(), b_sizes.end(),b_copy.begin());
        b_copy.insert
        (
            upper_bound(b_copy.begin(), b_copy.end(), basin.size(),greater<int>()),
            basin.size()
        );
        copy(b_copy.begin(), --b_copy.end(), b_sizes.begin());
        b_copy.erase(--b_copy.end());
    }

    return b_sizes[0] * b_sizes[1] * b_sizes[2];

}

type ColData<'a> = (Option<&'a usize>, Option<&'a usize>, Option<&'a usize>);
type RowData<'a> = (ColData<'a>, ColData<'a>, ColData<'a>);

fn main() {
    let 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(&input).iter().map(|(r, _, _)| r + 1).sum::<usize>()
    );
    println!("{}", part2(&input).unwrap());
}

fn part1(data: &[Vec<usize>]) -> Vec<(usize, usize, usize)> {
    let mut hits = Vec::new();
    for row in 0..data.len() {
        for col in 0..data[0].len() {
            if let Some(&risk_lvl) = part1_matcher(fetch_row(data, row, col)) {
                hits.push((risk_lvl, row, col));
            }
        }
    }
    hits
}

fn part2(data: &[Vec<usize>]) -> Option<usize> {
    let lows = part1(data);
    let mut sizes = vec![];
    for (_, row, col) in lows {
        sizes.push(solve(data, &mut vec![], row, col));
    }
    sizes.sort_unstable();
    Some(sizes.pop()? * sizes.pop()? * sizes.pop()?)
}

fn solve(data: &[Vec<usize>], res: &mut Vec<(usize, usize)>, row: usize, col: usize) -> usize {
    if res.contains(&(row, col)) {
        return 0;
    }
    let mut accum = 1;
    let (up, mid, down) = fetch_row(data, row, col);
    res.push((row, col));
    for i in [
        (up.1, if row > 0 { row - 1 } else { 0 }, col),
        (mid.0, row, if col > 0 { col - 1 } else { 0 }),
        (mid.2, row, col + 1),
        (down.1, row + 1, col),
    ] {
        accum += match i {
            (Some(&x), row, col) if x != 9 => solve(data, res, row, col),
            _ => 0,
        };
    }
    accum
}

fn part1_matcher((up, mid, down): RowData) -> Option<&usize> {
    match (up.1, mid, down.1) {
        (None, (None, x @ Some(a), Some(b)), Some(c)) if [b, c].iter().all(|v| a < v) => x,
        (None, (Some(d), x @ Some(a), Some(b)), Some(c)) if a < b && a < c && a < d => x,
        (None, (Some(b), x @ Some(a), None), Some(c)) if [b, c].iter().all(|v| a < v) => x,
        (Some(c), (None, x @ Some(a), Some(b)), Some(d)) if [b, c, d].iter().all(|v| a < v) => x,
        (Some(c), (Some(d), x @ Some(a), Some(b)), Some(e))
            if [b, c, d, e].iter().all(|v| a < v) =>
        {
            x
        }
        (Some(c), (Some(b), x @ Some(a), None), Some(d)) if [b, c, d].iter().all(|v| a < v) => x,
        (Some(c), (None, x @ Some(a), Some(b)), None) if [b, c].iter().all(|v| a < v) => x,
        (Some(c), (Some(d), x @ Some(a), Some(b)), None) if [b, c, d].iter().all(|v| a < v) => x,
        (Some(c), (Some(b), x @ Some(a), None), None) if [b, c].iter().all(|v| a < v) => x,
        _ => None,
    }
}

fn fetch_row(input: &[Vec<usize>], row: usize, col: usize) -> RowData {
    (
        row.checked_sub(1)
            .map(|v| fetch_col(input.get(v), col))
            .unwrap_or((None, None, None)),
        fetch_col(input.get(row), col),
        row.checked_add(1)
            .map(|v| fetch_col(input.get(v), col))
            .unwrap_or((None, None, None)),
    )
}

fn fetch_col(row: Option<&Vec<usize>>, col: usize) -> ColData {
    if let Some(value) = row {
        (
            col.checked_sub(1).map(|v| value.get(v)).flatten(),
            value.get(col),
            col.checked_add(1).map(|v| value.get(v)).flatten(),
        )
    } else {
        (None, None, None)
    }
}

#include <stdio.h>
#include <stdlib.h>

#define MAP_W   100
#define MAP_H   100

#define INDEX(x, y) ((x) + (y) * MAP_W)

int g_height[MAP_W * MAP_H];

int *g_basin;
int g_basins;

int get_pos(int cur, int dx, int dy) {
        int cur_x, cur_y;

        cur_x = cur % MAP_W;
        cur_y = cur / MAP_W;
        cur_x += dx;
        cur_y += dy;

        if (cur_x < 0 || cur_x >= MAP_W)
                return 11;
        if (cur_y < 0 || cur_y >= MAP_H)
                return 11;
        return g_height[INDEX(cur_x, cur_y)];
}


int basin_size(int i) {
        int cur_x, cur_y, size, here;

        cur_x = i % MAP_W;
        cur_y = i / MAP_W;

        if (g_height[i] == 9)
                return 0;

        here = g_height[i];

        g_height[i] = 9;
        size = 1;
        if (cur_x > 0 && here <= get_pos(i, -1, 0))
                size += basin_size(INDEX(cur_x - 1, cur_y));
        if (cur_x + 1 < MAP_W && here <= get_pos(i, 1, 0))
                size += basin_size(INDEX(cur_x + 1, cur_y));
        if (cur_y > 0 && here <= get_pos(i, 0, -1))
                size += basin_size(INDEX(cur_x, cur_y - 1));
        if (cur_y + 1 < MAP_H && here <= get_pos(i, 0, 1))
                size += basin_size(INDEX(cur_x, cur_y + 1));
        return size;
}


void analyze_basin(int i) {
        int q;

        q = g_basins++;
        g_basin = realloc(g_basin, sizeof(*g_basin) * g_basins);
        g_basin[q] = basin_size(i);
}


int basin_cmp(const void *q1, const void *q2) {
        return *((int *) q1) - *((int *) q2);
}


int main(int argc, char **argv) {
        int i;
        int risk;

        for (i = 0; i < MAP_W * MAP_H; i++)
                fscanf(stdin, "%1d", &g_height[i]);
        for (i = risk = 0; i < MAP_W * MAP_H; i++) {
                if (get_pos(i, -1, 0) <= g_height[i])
                        continue;
                if (get_pos(i, 1, 0) <= g_height[i])
                        continue;
                if (get_pos(i, 0, -1) <= g_height[i])
                        continue;
                if (get_pos(i, 0, 1) <= g_height[i])
                        continue;
                risk += (g_height[i] + 1);
                analyze_basin(i);
        }

        qsort(g_basin, g_basins, sizeof(*g_basin), basin_cmp);

        printf("Solution A: %i\n", risk);
        printf("Solution B: %i (%i %i %i)\n", g_basin[g_basins - 1] * g_basin[g_basins - 2] * g_basin[g_basins - 3], g_basin[g_basins - 1], g_basin[g_basins - 2], g_basin[g_basins - 3]);
        return 0;
}

from typing import Generator, Tuple
from math import prod

data = [[int(x) for x in line.rstrip()] for line in open("9.in")]
HEIGHT = len(data)
WIDTH = len(data[0])


def generate_neighbours(i: int, j: int) -> Generator[Tuple[int, int], None, None]:
    for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        if 0 <= (n_i := i + di) < HEIGHT and 0 <= (n_j := j + dj) < WIDTH:
            yield n_i, n_j


def measure_basin(i: int, j: int) -> int:
    seen = set()
    frontier = [(i, j)]
    while frontier:
        point = frontier.pop(-1)
        seen.add(point)
        frontier += [p for p in generate_neighbours(*point) if p not in seen and data[p[0]][p[1]] < 9]
    return len(seen)


low_points = [
    (i, j)
    for i in range(HEIGHT)
    for j in range(WIDTH)
    if all(data[n_i][n_j] > data[i][j] for n_i, n_j in generate_neighbours(i, j))
]

p1 = sum(data[i][j] + 1 for i, j in low_points)
p2 = prod(sorted(measure_basin(*low_point) for low_point in low_points)[-3:])

print(p1, p2)

object Day10 {
	val data = readLines("10/data.txt")

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

		case class LexerResult(unexpected: Option[Char], open: List[Char])

		def check(remaining: String, open: List[Char] = Nil): LexerResult = {
			if(remaining.isEmpty) {
				LexerResult(None, open)
			} else {
				remaining.head match {
					case '(' => check(remaining.tail, ')' :: open)
					case '[' => check(remaining.tail, ']' :: open)
					case '{' => check(remaining.tail, '}' :: open)
					case '<' => check(remaining.tail, '>' :: open)
					case c if c == open.head => check(remaining.tail, open.tail)
					case unexpected => LexerResult(Some(unexpected), open)
				}
			}
		}

		// part 1
		def score1(line: String) = check(line).unexpected match {
			case Some(')') => 3
			case Some(']') => 57
			case Some('}') => 1197
			case Some('>') => 25137
			case None => 0
		}
		println(data.map(score1).sum)

		// part 2
		val scores = data.map(line => check(line))
				.filter(_.unexpected.isEmpty)
				.map { res =>
					res.open.foldLeft(0L) { case (score, ch) =>
						score * 5 + (ch match {
							case ')' => 1
							case ']' => 2
							case '}' => 3
							case '>' => 4
						})
					}
				}
				.sorted
		println(scores(scores.length / 2))
	}
}

from typing import Tuple


start_chars = "[{<("
end_chars = "]}>)"

char_opposites = dict(zip(start_chars, end_chars)) | dict(zip(end_chars, start_chars))
char_scores = {")": 3, "]": 57, "}": 1197, ">": 25137, "(": 1, "[": 2, "{": 3, "<": 4}


def score_line(line: str) -> Tuple[int, int]:
    valid_score = 0
    invalid_score = 0
    stack = []
    for c in line:
        if c in start_chars:
            stack.append(c)
        elif stack.pop(-1) != char_opposites[c]:
            return 0, char_scores[c]
    while stack:
        c = stack.pop(-1)
        valid_score = valid_score * 5 + char_scores[c]
    return valid_score, invalid_score


valid_scores, invalid_scores = zip(*((score_line(line.rstrip())) for line in open("10.in")))
valid_non_zero = [x for x in valid_scores if x > 0]

print(sum(invalid_scores))
print(sorted(valid_non_zero)[len(valid_non_zero) // 2])

internal class Puzzle10 : Puzzle<long>
{
    private static readonly string[] Chunks = new string[] { "()", "[]", "{}", "<>" };

    protected override void Solve(string[] lines)
    {
        var corruptedLines = lines
            .Select((x, idx) => new { score = FindIllegalCharacter(x), idx })
            .Where(x => x.score > 0)
            .ToList();
                
        One = corruptedLines.Select(x => x.score).Sum();

        var corruptedLineIndexes = corruptedLines.Select(x => x.idx).ToList();

        var fixedLines = lines
            .Where((x, idx) => !corruptedLineIndexes.Contains(idx))
            .Select(x => FixIncompleteLines(x))
            .OrderBy(x => x)
            .ToList();

        Two = fixedLines[fixedLines.Count / 2];
    }

    private static long FixIncompleteLines(string line) => GetOpenChars(line, false, out _)
        .Reverse()
        .Select(GetClosedChar)
        .Aggregate(0L, (totalScore, b) => totalScore * 5 + b switch
        {
            ')' => 1,
            ']' => 2,
            '}' => 3,
            '>' => 4,
            _ => 0
        });

    private static int FindIllegalCharacter(string line)
    {
        _ = GetOpenChars(line, true, out var point);
        return point;
    }

    private static char? GetOpenChar(char @char) => Chunks.FirstOrDefault(x => x[1] == @char)?[0];
    private static char GetClosedChar(char @char) => Chunks.Single(x => x[0] == @char)[1];

    private static IEnumerable<char> GetOpenChars(string line, bool checkIllegal, out int illegalCharPoint)
    {
        illegalCharPoint = 0;

        var openChars = new List<char>();
        foreach (var @char in line)
        {
            var openChar = GetOpenChar(@char);
            if (openChar == null)
            {
                openChars.Add(@char);
            }
            else if (checkIllegal && openChars[^1] != openChar)
            {
                illegalCharPoint = @char switch
                {
                    ')' => 3,
                    ']' => 57,
                    '}' => 1197,
                    '>' => 25137,
                    _ => 0
                };
                break;
            }
            else
            {
                openChars.RemoveAt(openChars.Count - 1);
            }
        }

        return openChars;
    }
}

(import std)

(define main
  (do io/bind
      (<- input (io/map unwrap! (read-file "inputs/day10.txt")))
      (let1 [corrupteds incompletes] (partition-eithers (map execute (lines input))))
      (display (str-append "Part 1: "
                           (apps |> corrupteds
                                 list/iter
                                 (map corrupted-points)
                                 sum
                                 show-int)))
      (display (str-append "Part 2: "
                           (apps |> incompletes
                                 list/iter
                                 (map incomplete-score)
                                 array/collect
                                 (merge-sort num/cmp)
                                 array/middle
                                 unwrap!
                                 show-int)))))

(data Bracket Round Square Curly Angle)

(define corrupted-points
  (fmatch (case Round 3) (case Square 57) (case Curly 1197) (case Angle 25137)))

(define (incomplete-score missings)
  (foldl  (fun (tot b) (+ (* 5 tot) (inc (bracket-to-int b))))  0  (list/iter missings)))

;;? Returns Left with last token when corrupted, and Right with the missing brackets when incomplete
(define (execute line)
  (define (go stack)
    (define (open bracket) (Right (list/cons bracket stack)))
    (define (close b2)
      (match (list/uncons stack)
        (case None (Left b2))
        (case (Some [b1 stack']) (if (bracket-eq b1 b2) (Right stack') (Left b2)))))
    (fmatch (case None (Right stack))
            (case (Some [symbol rest])
                  (match (match symbol
                           (case "(" (open Round))
                           (case "[" (open Square))
                           (case "{" (open Curly))
                           (case "<" (open Angle))
                           (case ")" (close Round))
                           (case "]" (close Square))
                           (case "}" (close Curly))
                           (case _   (close Angle)))
                    (case (Left bracket) (Left bracket))
                    (case (Right stack') (go stack' (next rest)))))))
  (go LNil (next (map string/singleton-byte (string/bytes line)))))

(define (bracket-eq b1 b2) (= (bracket-to-int b1) (bracket-to-int b2)))
(define (bracket-to-int b) (to-int (: (transmute b) Nat8)))

#include <iostream>
#include <iomanip>
#include <stack>
#include <map>
#include <algorithm>

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

typedef unsigned long long ull;
map<char,char> delims;

void set_delims()
{
    delims['('] = ')';
    delims['['] = ']';
    delims['{'] = '}';
    delims['<'] = '>';
}

bool opens(char inp)
{
    return delims.count(inp) > 0? true : false;
}

int calc_score(vector<char> const illegals)
{
    map<char,int> points;
    points[')'] = 3;
    points[']'] = 57;
    points['}'] = 1197;
    points['>'] = 25137;

    int score = 0;

    int n_illegals = illegals.size();
    for (int i = 0; i < n_illegals; i++)
    {
        score += points.at(illegals[i]);
    }
    return score;
}

int calc_score(vector<vector<char>> const missing)
{
    vector<ull> scores;
    map<char,int> points;
    points[')'] = 1;
    points[']'] = 2;
    points['}'] = 3;
    points['>'] = 4;

    int n_rows = missing.size();
    for (int i = 0; i < n_rows; i++)
    {
        ull row_score = 0;
        vector<char> row = missing[i];
        int row_size = row.size();
        for (int j = 0; j < row_size; j++)
        {
            row_score = row_score * 5 + points.at(row[j]);
        }
        scores.insert(upper_bound(scores.begin(), scores.end(),row_score),row_score);
    }

    return scores[scores.size()/2];
}

void scan_lines(vector<string> str_data, vector<vector<char>> &missing, vector<char> &illegals)
{
    set_delims();

    int n_rows = str_data.size();
    for (int row = 0; row < n_rows; row++)
    {
        stack<char> chunks;
        bool illegal = false;
        vector<char> row_miss;

        string row_d = str_data[row];
        int n_chars = row_d.length();
        for (int pos = 0; pos < n_chars; pos++)
        {
            char char_ = row_d[pos];
            if (opens(char_))
            {
                chunks.push(char_);
            }
            else
            {
                if (char_ != delims.at(chunks.top()))
                {
                    illegals.push_back(char_);
                    illegal = true;
                    break;
                }
                else
                {
                    chunks.pop();
                }
            }
        }
        if (!illegal)
        {
            while(chunks.size()>0)
            {
                row_miss.push_back(delims.at(chunks.top()));
                chunks.pop();
            }
            missing.push_back(row_miss);
        }
    }
}

vector<int> solve(vector<string> str_data)
{
    vector<vector<char>> missing;
    vector<char> illegals;
    vector<int> results;

    scan_lines(str_data, missing, illegals);
    
    results.push_back(calc_score(illegals));
    results.push_back(calc_score(missing));

    return results;

}

int main()
{
    string filename = "../../input/day_10.txt";
    vector<string> string_data = read_file<string>(filename,true);
    
    vector<int> result = solve(string_data);
    cout << setw(30) << left << "Day 10 Part 1 solution: " << result[0] << endl;
    cout << setw(30) << left << "Day 10 Part 2 solution: " << result[1] << endl;
}