🌟 Advent of Code (AoC) 2021 🌟

import { GetFileRows } from "./fileReader";

type FishCounter = { [key: number]: number };
const emptyFishCounter: FishCounter = {
    0: 0,
    1: 0,
    2: 0,
    3: 0,
    4: 0,
    5: 0,
    6: 0,
    7: 0,
    8: 0,
};

const countFishAfterNumberOfDays = (currentFish: FishCounter, days: number): number => {
    if (days === 0) {
        return Object.values(currentFish).reduce((prev, curr) => (prev += curr), 0);
    }
    let newDayFishCounter: FishCounter = { ...emptyFishCounter };

    newDayFishCounter[0] = currentFish[1];
    newDayFishCounter[1] = currentFish[2];
    newDayFishCounter[2] = currentFish[3];
    newDayFishCounter[3] = currentFish[4];
    newDayFishCounter[4] = currentFish[5];
    newDayFishCounter[5] = currentFish[6];
    newDayFishCounter[6] = currentFish[0] + currentFish[7];
    newDayFishCounter[7] = currentFish[8];
    newDayFishCounter[8] = currentFish[0];

    return countFishAfterNumberOfDays(newDayFishCounter, --days);
};



const solve = (rows: string[]) => {
    const inputNumbers: number[] = rows[0].split(",").map((n) => parseInt(n));

    let yesterdayFishCounter: FishCounter = inputNumbers.reduce<FishCounter>(
        (allFish, numberInArr) => {
            allFish[numberInArr] = ++allFish[numberInArr];
            return allFish;
        },
        { ...emptyFishCounter }
    );

    console.log(countFishAfterNumberOfDays(yesterdayFishCounter, 80));
    console.log(countFishAfterNumberOfDays(yesterdayFishCounter, 256));
};

const solveDay6 = async () => {
    const rows = await GetFileRows("./src/inputs/input-day6.txt");
    solve(rows);
};

type Instruction = FoldX of int | FoldY of int

let parse filename =
    let data = System.IO.File.ReadAllLines filename
    let parseInstruction (line:string) = 
        let parts = line.Split " " |> Seq.last |> (fun x -> x.Split "=")
        match (parts |> Seq.head) with 
        | "x" -> FoldX (parts |> Seq.item 1 |> int)
        | "y" -> FoldY (parts |> Seq.item 1 |> int)
        | _ -> failwithf "Strange input"

    let parseLine set (line:string) = 
        let parts = line.Split(",")
        let pos = (Seq.item 0 parts |> int, Seq.item 1 parts |> int)
        Set.add pos set
    let map  = data |> Seq.takeWhile ((<>) "") |> Seq.fold (parseLine) Set.empty
    let instructions = data |> Seq.skipWhile ((<>) "") |> Seq.skip 1 |> Seq.map parseInstruction |> List.ofSeq
    (map, instructions)

let fold map instruction =
    let foldX pos map (x,y) = 
            if x<pos then map else map |> Set.remove (x,y) |> Set.add (2*pos - x, y)
    let foldY pos map (x,y) = 
            if y<pos then map else map |> Set.remove (x,y) |> Set.add (x, 2*pos - y)

    let folder =
        match instruction with
        | FoldY pos -> foldY pos
        | FoldX pos -> foldX pos
    map |> Set.fold folder map

let task1 (map, instructions) =
    instructions |> List.head |> fold map |> Seq.length

let task2 (map, instructions) =
    instructions |> List.fold (fold) map

let print (map :(int*int) Set) =
    let maxX = map |> Seq.map fst |> Seq.max
    let maxY = map |> Seq.map snd |> Seq.max
    for y in 0..maxY do
        for x in 0..maxX do
            if map.Contains (x,y)
            then printf "##"
            else (printf "  ")
        printfn ""

let input = parse "input.txt"

printfn "Task 1: %i" (input |> task1)
input |> task2 |> print

type manual struct {
  markings      map[int]position
  height, width int
}

type position struct {
  x, y int
}

func main() {
  lines, _ := helpers.ReadLines("input.txt")

  start := time.Now()
  man, index := getMarkings(lines)
  result := 0
  for i, instruction := range lines[index:] {
    man.fold(instruction)
    if i == 0 {
      result = len(man.markings)
    }
  }
  duration := time.Since(start)
  fmt.Println(result)
  man.print()
  fmt.Println(duration)
}

func getMarkings(input []string) (manual manual, index int) {
  manual.markings = make(map[int]position)
  height, width := 0, 0

  for i, line := range input {
    if line == "" {
      index = i + 1
      break
    }
    values := strings.Split(line, ",")
    x, y := helpers.GetInt(values[0]), helpers.GetInt(values[1])

    if x > width {
      width = x
    }
    if y > height {
      height = y
    }

    hash := helpers.Hash(x, y)
    manual.markings[hash] = position{x, y}
  }
  manual.height = height + 1
  manual.width = width + 1
  return
}

func (manual *manual) fold(instruction string) {
  args := strings.Split(strings.Split(instruction, " ")[2], "=")
  dir, index := args[0], helpers.GetInt(args[1])
  if dir == "x" {
    manual.performFold(index+1, false)
    manual.width = index
  } else {
    manual.performFold(index+1, true)
    manual.height = index
  }
}

func (manual *manual) performFold(limit int, horizontal bool) {
  for key, mark := range manual.markings {
    if horizontal && mark.y >= limit {
      delete(manual.markings, key)
      index := 2*(limit-1) - mark.y
      hash := helpers.Hash(mark.x, index)
      mark.y = index
      manual.markings[hash] = mark
    } else if !horizontal && mark.x >= limit {
      delete(manual.markings, key)
      index := 2*(limit-1) - mark.x
      hash := helpers.Hash(index, mark.y)
      mark.x = index
      manual.markings[hash] = mark
    }
  }
}

func (manual manual) print() {
  fmt.Printf("height: %v, width: %v\n", manual.height, manual.width)

  for y := 0; y < manual.height; y++ {
    for x := 0; x < manual.width; x++ {
      if _, ok := manual.markings[helpers.Hash(x, y)]; ok {
        fmt.Print("#")
      } else {
        fmt.Print(".")
      }
    }
    fmt.Println()
  }
}

import { Solution } from './solution.js';
import { Perf, readLines } from './common.js';

import { Permutation } from 'js-combinatorics';

const SEGMENT_MAP : Record<string, number> = {
     "abcefg": 0, "cf": 1, "acdeg": 2, "acdfg": 3, "bcdf": 4,
     "abdfg": 5, "abdefg": 6, "acf": 7, "abcdefg": 8, "abcdfg": 9
};

 class Digit {
     segments: string;
     constructor(segments: string) {
         this.segments = segments.split('').sort().join('');
     }

    // Map from invalid segments (e.g. dgb) to valid (e.g. acf, for 7)
    remap(conversionTable: Record<string, string>): Digit {
        this.segments = this.segments.split('')
                                     .map(c => conversionTable[c])
                                     .sort()
                                     .join('');
        return this;
    }

    // If these (actual) segments are lit, what digit is displayed?
    value(): number {
        return SEGMENT_MAP[this.segments];
    }
 }

export class Day8_TESTING implements Solution {
    ALL_MAPPINGS: Record<string, string>[] = [];

    calculateSegmentMap(patterns: string[]): Record<string, string> {
        const isValid = (mapping: Record<string, string>) =>
            patterns.every(p => new Digit(p).remap(mapping).value() !== undefined);

        for (let mapping of this.ALL_MAPPINGS) {
            if (isValid(mapping))
                return mapping;
        }

        return {};
    }

    answer() {
        readLines("data/day8.txt", (data) => {
            let perf = new Perf();

            // First, generate all possible segment mappings, once.
            for (let p of new Permutation("abcdefg")) {
                this.ALL_MAPPINGS.push({a: p[0], b: p[1], c: p[2], d: p[3], e: p[4], f: p[5], g: p[6]});
            }

            let patterns : string[][] = [];
            let outputValues : string[][] = [];
            for (let line of data) {
                let [pattern, output] = line.split(" | ");
                patterns.push(pattern.split(" "));
                outputValues.push(output.split(" "));
            }

            let sum = 0;
            for (let i = 0; i < patterns.length; i++) {
                let mapping = this.calculateSegmentMap(patterns[i]);
                let outputDigits = outputValues[i].map(s => new Digit(s).remap(mapping).value());
                let outputValue = parseInt(outputDigits.reduce((prev, curr) => prev + curr, "")); // Feeling lazy
                sum += outputValue;
            }

            console.log(`Day 8 Part 2: ${sum}`);

            perf.end();
        });
    }
}

use std::fs::File;
use std::io::Read;
use std::collections::HashMap;
use itertools::Itertools;
use lazy_static::lazy_static;
use phf::phf_map;
use std::time::Instant;

static SEGMENT_MAP: phf::Map<&'static str, i32> = phf_map! {
     "abcefg" => 0, "cf" => 1, "acdeg" => 2, "acdfg" => 3, "bcdf" => 4,
     "abdfg" => 5, "abdefg" => 6, "acf" => 7, "abcdefg" => 8, "abcdfg" => 9
};

struct Digit {
    segments: String
}

impl From<&String> for Digit {
    fn from(seg: &String) -> Self {
        Digit { segments: seg.clone() }
    }
}

impl Digit {
    fn remap(mut self, conversion_table: &HashMap<char, char>) -> Digit {
        self.segments = self.segments.chars()
                                     .map(|c| conversion_table[&c])
                                     .sorted()
                                     .collect();
        self
    }

    fn value(&self) -> Option<&i32> {
        SEGMENT_MAP.get(&self.segments)
    }
}

fn is_valid_map(patterns: &Vec<String>, mapping: &HashMap<char, char>) -> bool {
    patterns.iter().all(|p| Digit::from(p).remap(mapping).value().is_some())
}

fn calculate_segment_map(patterns: &Vec<String>) -> &'static HashMap<char, char> {
    return ALL_MAPPINGS.iter()
                       .filter(|m| is_valid_map(&patterns, m))
                       .next().unwrap();
}

lazy_static! {
    static ref ALL_MAPPINGS: Vec<HashMap<char, char>> = {
        let mut all_maps = Vec::new();
        for p in "abcdefg".chars().permutations(7).unique() {
            let mut map = HashMap::new();
            map.insert('a', p[0]);
            map.insert('b', p[1]);
            map.insert('c', p[2]);
            map.insert('d', p[3]);
            map.insert('e', p[4]);
            map.insert('f', p[5]);
            map.insert('g', p[6]);
            all_maps.push(map);
        }
        assert!(all_maps.len() == 5040);
        all_maps
    };
}

fn main() {
    let mut input = String::new();
    let mut file = File::open("../../data/day8.txt").expect("Failed to open file");
    file.read_to_string(&mut input).expect("Failed to read file");

    let start = Instant::now();

    let mut patterns: Vec<Vec<String>> = Vec::new();
    let mut output_values: Vec<Vec<String>> = Vec::new();
    for line in input.split("\r\n") {
        let mut parts = line.split(" | ");
        patterns.push(parts.next().unwrap().split(" ").map(str::to_string).collect());
        output_values.push(parts.next().unwrap().split(" ").map(str::to_string).collect());
    }

    let mut sum = 0;
    for i in 0..patterns.len() {
        let mapping = calculate_segment_map(&patterns[i]);
        let output_digits = output_values[i].iter().map(|s| Digit::from(s).remap(mapping).value().unwrap().to_string());
        let output_value: i32 = output_digits.fold(String::new(), |prev, curr| prev + &curr).parse::<i32>().unwrap();
        sum += output_value;
    }

    println!("Day 8 Part 2: {}", sum);
    println!("Time taken: {} us", start.elapsed().as_micros());
}

import re
from collections import Counter, defaultdict

s, rules0 = open("input14").read().split("\n\n")
rules = {(a,b) : c for a,b,c in re.findall("([A-Z])([A-Z]) -> ([A-Z])", rules0)}

def steps(s, n):
    counts, elements = defaultdict(int), defaultdict(int)
    for i in range(len(s) - 1):
        counts[(s[i], s[i + 1])] += 1
    for i in range(n):
        counts2 = defaultdict(int)
        for (a, c), i in counts.items():
            b = rules[(a,c)]
            counts2[(a,b)] += i
            counts2[(b,c)] += i
        counts = counts2

    elements[s[-1]] = 1
    for (a, _), n in counts.items():
        elements[a] += n
    return (max(elements.values()) - min(elements.values()))

print(steps(s, 10), steps(s, 40))

import { GetFileRowAsNumbers, GetFileRows } from "./fileReader";

const solve = (crabPositions: number[]) => {

    crabPositions.sort((a, b) => a - b);
    const median = crabPositions[crabPositions.length/2]
    const answerPart1 = crabPositions.filter(pos => pos !== median).reduce((acc, curr) => {
        acc = acc + Math.abs(curr-median);
        return acc
    }, 0)
    console.log(answerPart1)


    const sum = crabPositions.reduce((acc, curr) => acc+=curr, 0)
    const averages = [Math.floor(sum/crabPositions.length),Math.round(sum/crabPositions.length)]
    const answerPart2 = crabPositions.reduce((acc, curr) => {
        const steps = [Math.abs(curr-averages[0]), Math.abs(curr-averages[1])]
        //calculate factorial but with + instead of * using formula (n^2+n)/2
        const factorialMenMedPlus = steps.map(s => (s*s+s)/2)
        //console.log(`pos: ${curr} fact: ${factorialMenMedPlus} steps: ${steps}  avg: ${average}`)
        acc = {first: acc.first + factorialMenMedPlus[0], second: acc.second + factorialMenMedPlus[1]};
        return acc
    }, {first: 0, second: 0})

    console.log(Math.min(...Object.values(answerPart2)))
    

};


const solveDay7 = async () => {
    const crabPositions = await GetFileRowAsNumbers("./src/inputs/input-day7.txt");
    solve(crabPositions);
};

export default solveDay7;

type polymer struct {
  template       polyTemplate
  pairOccurances map[string]int
  occurances     map[string]int
  max, min       int
}

type polyTemplate map[string]string

func main() {
  lines, _ := helpers.ReadLines("input.txt")

  start := time.Now()

  polymer := initPolymerization(lines)
  polymer.performPolymerization(10)
  fmt.Printf("%v %v %v\n", polymer.min, polymer.max, polymer.max-polymer.min)
  polymer = initPolymerization(lines)
  polymer.performPolymerization(40)
  fmt.Printf("%v %v %v\n", polymer.min, polymer.max, polymer.max-polymer.min)
  duration := time.Since(start)
  fmt.Println(duration)
}

func initPolymerization(input []string) (polymer polymer) {
  polymer.occurances = make(map[string]int)
  polymer.pairOccurances = make(map[string]int)
  polymer.max = math.MinInt64
  polymer.min = math.MaxInt64

  for i := 0; i < len(input[0])-1; i++ {
    c1, c2 := string(input[0][i]), string(input[0][i+1])
    pair := c1 + c2
    polymer.pairOccurances[pair]++
  }

  for i := 0; i < len(input[0]); i++ {
    polymer.occurances[string(input[0][i])]++
  }

  polymer.template = make(polyTemplate)
  for _, line := range input[2:] {
    line = strings.ReplaceAll(line, " ", "")
    args := strings.Split(line, "->")
    instruction, result := args[0], args[1]
    polymer.template[instruction] = result
  }
  return
}

func (polymer *polymer) performPolymerization(times int) {
  for t := 0; t < times; t++ {
    newPairOccurances := make(map[string]int)

    for pair, value := range polymer.pairOccurances {
      newChar := polymer.template[pair]
      polymer.occurances[newChar] += value

      firstPair := string(pair[0]) + newChar
      secondPair := newChar + string(pair[1])
      newPairOccurances[firstPair] += value
      newPairOccurances[secondPair] += value
    }

    polymer.pairOccurances = newPairOccurances
  }

  for _, val := range polymer.occurances {
    if val > polymer.max {
      polymer.max = val
    } else if val < polymer.min {
      polymer.min = val
    }
  }
}

use crate::solution::Solution;
use fnv::FnvHashSet;
use std::cmp::max;

type Pos = (u32, u32);

#[derive(Clone, Copy)]
enum Fold {
    Up(u32),
    Left(u32),
}

struct Day13 {
    dots: FnvHashSet<Pos>,
    folds: Vec<Fold>,
}

impl Solution for Day13 {
    fn part1(&mut self) -> String {
        fold_paper(self.folds[0], &self.dots)
            .len()
            .to_string()
    }

    fn part2(&mut self) -> String {
        draw_dots(&self.all_folds())
    }
}

impl Day13 {
    fn all_folds(&self) -> FnvHashSet<Pos> {
        let mut dots = self.dots.clone();
        for &fold_instr in &self.folds {
            dots = fold_paper(fold_instr, &dots);
        }
        dots
    }
}

fn fold_paper(fold_instr: Fold, dots: &FnvHashSet<Pos>) -> FnvHashSet<Pos> {
    dots
        .iter()
        .map(|&dot| fold_along(fold_instr, dot))
        .collect()
}

fn fold_along(fold_instr: Fold, pos: Pos) -> Pos {
    match fold_instr {
        Fold::Left(x) if x < pos.0 => (2 * x - pos.0, pos.1),
        Fold::Up(y) if y < pos.1 => (pos.0, 2 * y - pos.1),
        _ => pos,
    }
}

fn draw_dots(dots: &FnvHashSet<Pos>) -> String {
    let (width, height) = canvas_size(dots);
    let mut canvas = String::new();
    for y in 0..=height {
        canvas.push('\n');
        for x in 0..=width {
            if dots.contains(&(x, y)) {
                canvas.push('█');
            } else {
                canvas.push(' ');
            }
        }
    }
    canvas
}

fn canvas_size(dots: &FnvHashSet<Pos>) -> (u32, u32) {
    dots
        .iter()
        .fold((0, 0), |sz, dot| (max(sz.0, dot.0), max(sz.1, dot.1)))
}

pub fn new(input: &str) -> Box<dyn Solution> {
    let mut lines = input.lines();

    let mut dots = FnvHashSet::default();
    loop {
        let dot_desc = lines.next().unwrap();
        if dot_desc.is_empty() {
            break;
        }
        let dot = scan_fmt!(dot_desc, "{d},{d}", u32, u32).expect("Invalid dot");
        dots.insert(dot);
    }

    let mut folds = Vec::new();
    for fold_desc in lines {
        let (axis, pos) =
            scan_fmt!(fold_desc, "fold along {}={d}", String, u32).expect("Invalid fold format");
        folds.push(if axis == "x" {
            Fold::Left(pos)
        } else {
            Fold::Up(pos)
        });
    }

    Box::new(Day13 { dots, folds })
}

use crate::solution::Solution;
use fnv::FnvHashMap;
use itertools::{MinMaxResult, Itertools};

const ELEMENT_BITS: usize = 5;
const DENSE_ARRAY_SZ: usize = 1 << ELEMENT_BITS;
const SPARSE_ARRAY_SZ: usize = 1 << ELEMENT_BITS * 2;

type Synthesises = [u8; SPARSE_ARRAY_SZ];
type ElementCount = [u64; DENSE_ARRAY_SZ];

struct Day14 {
    synthesises: Synthesises,
    step: usize,
    element_counts: ElementCount,
    element_pairs: FnvHashMap<(u8, u8), u64>,
}

impl Solution for Day14 {
    fn part1(&mut self) -> String {
        self.after_step(10).to_string()
    }

    fn part2(&mut self) -> String {
        self.after_step(40).to_string()
    }
}

impl Day14 {
    fn after_step(&mut self, n: usize) -> u64 {
        for _ in self.step..n {
            let mut next_elem_pairs = FnvHashMap::default();
            next_elem_pairs.reserve(self.element_pairs.len());

            for (&elem_pair, &count) in &self.element_pairs
            {
                // Each pair adds one new element to the polymer...
                let new_element = self.synthesises[pair_idx(elem_pair)];
                self.element_counts[element_idx(new_element)] += count;
                // ...which produce two new target pairs per source pair
                *next_elem_pairs.entry((elem_pair.0, new_element)).or_default() += count;
                *next_elem_pairs.entry((new_element, elem_pair.1)).or_default() += count;
            }
            self.element_pairs = next_elem_pairs;
        }

        self.step = n;
        minmax_delta(self.element_counts.into_iter().filter(|&cnt| cnt > 0))
    }
}

fn minmax_delta(cnts: impl Iterator<Item=u64>) -> u64 {
    match cnts.minmax() {
        MinMaxResult::MinMax(small, large) => large - small,
        _ => panic!("Unexpected argument"),
    }
}

fn element_idx(element: u8) -> usize {
    (element - 'A' as u8) as usize
}

fn pair_idx(p: (u8, u8)) -> usize {
    (element_idx(p.1) << ELEMENT_BITS) + element_idx(p.0)
}

pub fn new(input: &str) -> Box<dyn Solution> {
    let mut lines = input.lines();
    let start_polymer = lines.next().unwrap().to_owned();
    lines.next();

    let mut synt = FnvHashMap::default();
    for line in lines {
        let (from, to) = line.split_once(" -> ")
            .expect("Invalid data format");
        let mut from_ch = from.chars();
        synt.insert((from_ch.next().unwrap() as u8, from_ch.next().unwrap() as u8), to.chars().next().unwrap() as u8);
    }

    let mut synthesises = [0; SPARSE_ARRAY_SZ];
    for (pair, elem) in synt {
        synthesises[pair_idx(pair)] = elem;
    }

    let mut element_counts = [0; DENSE_ARRAY_SZ];
    for element in start_polymer.bytes() {
        element_counts[element_idx(element)] += 1;
    }

    let mut element_pairs = FnvHashMap::default();
    for elem_pair in start_polymer.bytes().zip(start_polymer.bytes().skip(1)) {
        *element_pairs.entry(elem_pair).or_default() += 1;
    }
    
    Box::new(Day14{
        synthesises,
        step: 0,
        element_counts,
        element_pairs,
    })
}

from heapq import heappush, heappop
import numpy as np

a= np.array([[int(i) for i in s.strip()] for s in open("input15").readlines()])

def neighbors(p, a):
    x, y = p
    if x > 0:              yield (x - 1, y)
    if x < a.shape[0] - 1: yield (x + 1, y)
    if y > 0:              yield (x, y - 1)
    if y < a.shape[1] - 1: yield (x, y + 1)

def bfs(a):
    start, end = (0,0), (a.shape[0] - 1, a.shape[1] - 1)
    low = np.full(a.shape, 99999)
    low[start] = 0
    paths = []
    heappush(paths, (0, start))
    while paths:
        risk, pos = heappop(paths)
        for n in neighbors(pos, a):
            if (newrisk := risk + a[n]) < low[n]:
                low[n] = newrisk
                heappush(paths, (newrisk, n))
    return risk

print(bfs(a))

b = np.concatenate([a, a + 1, a + 2 , a + 3, a + 4])
c = np.concatenate([b, b + 1, b + 2 , b + 3, b + 4], axis = 1)
c = (c - 1) % 9 + 1

print(bfs(c))