advent of code 2022

day01-1.awk

#!/usr/bin/env awk -f

BEGIN { RS = ""; FS = "\n"; }

{
	for (i=1; i<=NF; i++) {
		sum += $i
	}
	if (sum > max) {
		max = sum
	}
	sum = 0
}

END { print max }

day01-2.awk

#!/usr/bin/env gawk -f

BEGIN { RS = ""; FS = "\n"; }

{
	for (i=1; i<=NF; i++) {
		sum += $i
	}
	arr[alen++] = sum
	sum = 0
}

END {
	asort(arr)
	print arr[alen] + arr[alen-1] + arr[alen-2]
}

day02-1.sh

#!/usr/bin/env bash
set -eu

declare -A scores=(
	[AX]=3 [AY]=6 [AZ]=0
	[BX]=0 [BY]=3 [BZ]=6
	[CX]=6 [CY]=0 [CZ]=3
)
declare -A play=([X]=1 [Y]=2 [Z]=3)
score=0
while read O M; do
	score=$(( $score + ${scores[$O$M]} + ${play[$M]} ))
done

echo $score

day02-2.sh

#!/usr/bin/env bash
set -eu

declare -A scores=(
	[AX]=3 [AY]=6 [AZ]=0
	[BX]=0 [BY]=3 [BZ]=6
	[CX]=6 [CY]=0 [CZ]=3
)
declare -A plays=(
	[AX]=Z [AY]=X [AZ]=Y
	[BX]=X [BY]=Y [BZ]=Z
	[CX]=Y [CY]=Z [CZ]=X
)
declare -A play=([X]=1 [Y]=2 [Z]=3)
score=0
while read O M; do
	M=${plays[$O$M]}
	score=$(( $score + ${scores[$O$M]} + ${play[$M]} ))
done

echo $score

day03-1.tcl

#!/usr/bin/env tclsh
package require struct::set

set sum 0

foreach line [read stdin] {
	set lstr [split $line {}]
	set half [expr {[llength $lstr] / 2}]
	set s1 [lrange $lstr 0 $half-1]
	set s2 [lrange $lstr $half end]

	set itemtype [lindex [::struct::set intersect $s1 $s2] 0]
	set code [scan $itemtype %c]

	if { $code > 90 } {
		set priority [expr {$code - 96}]
	} else {
		set priority [expr {$code - 38}]
	}
	incr sum $priority
}

puts $sum

day03-2.tcl

#!/usr/bin/env tclsh
package require struct::set

set group 1
set sum 0
set l1 [list]
set l2 [list]
set l3 [list]

foreach line [read stdin] {
	set l$group [split $line {}]

	if {$group == 3} {
		set itemtype [lindex [::struct::set intersect $l1 $l2 $l3] 0]
		set code [scan $itemtype %c]

		if { $code > 90 } {
			set priority [expr {$code - 96}]
		} else {
			set priority [expr {$code - 38}]
		}
		incr sum $priority
		set group 0
	}
	incr group
}

puts $sum

day04-1.easylang

# paste the following in https://easylang.online/ide/
pairs[][] = [ [ 2 4 6 8 ] [ 2 3 4 5 ] [ 5 7 7 9 ] [ 2 8 3 7 ] [ 6 6 4 6 ] [ 2 6 4 8 ] ]
contained = 0
i = 1
on animate
   clear
   color 000
   move 5 20
   textsize 3
   text "contained: " & contained
   if i <= len pairs[][]
      a = pairs[i][1]
      b = pairs[i][2]
      c = pairs[i][3]
      d = pairs[i][4]
      i += 1
      if a >= c and b <= d or c >= a and b >= d
         contained += 1
      .
      color 900
      move a 5
      rect 1 + b - a 1
      color 009
      move c 6
      rect 1 + d - c 1
      sleep 0.5
   .
.

day04-2.easylang

# paste the following in https://easylang.online/ide/
pairs[][] = [ [ 2 4 6 8 ] [ 2 3 4 5 ] [ 5 7 7 9 ] [ 2 8 3 7 ] [ 6 6 4 6 ] [ 2 6 4 8 ] ]
overlapping = 0
i = 1
on animate
   clear
   color 000
   move 5 20
   textsize 3
   text "overlapping: " & overlapping
   if i <= len pairs[][]
      a = pairs[i][1]
      b = pairs[i][2]
      c = pairs[i][3]
      d = pairs[i][4]
      i += 1
      if b >= c and d >= a
         overlapping += 1
      .
      color 900
      move a 5
      rect 1 + b - a 1
      color 009
      move c 6
      rect 1 + d - c 1
      sleep 0.5
   .
.

day05.rs

use text_io::scan;

fn day05() {
    let data = include_str!("../data/05");
    let mut iter = data.lines();
    let mut stacks_part1 = [
        vec![],
        vec![],
        vec![],
        vec![],
        vec![],
        vec![],
        vec![],
        vec![],
        vec![],
    ];
    let mut stacks_part2 = stacks_part1.clone();

    for line in iter.by_ref().take_while(|l| !l.is_empty()) {
        // stacks
        let stack_values = [
            line.get(1..2).unwrap(),
            line.get(5..6).unwrap(),
            line.get(9..10).unwrap(),
            line.get(13..14).unwrap(),
            line.get(17..18).unwrap(),
            line.get(21..22).unwrap(),
            line.get(25..26).unwrap(),
            line.get(29..30).unwrap(),
            line.get(33..34).unwrap(),
        ];
        if stack_values[0] == "1" {
            break;
        }
        for i in 0..9 {
            if stack_values[i] != " " {
                stacks_part1[i].push(stack_values[i]);
                stacks_part2[i].push(stack_values[i]);
            }
        }
    }
    stacks_part1.iter_mut().for_each(|s| s.reverse());
    stacks_part2.iter_mut().for_each(|s| s.reverse());

    iter.next(); // skip empty line
    for line in iter {
        // instructions
        let from: usize;
        let n: usize;
        let to: usize;
        scan!(line.bytes() => "move {} from {} to {}", n, from, to);
        for _ in 0..n {
            let v = stacks_part1[from - 1].pop().unwrap();
            stacks_part1[to - 1].push(v);
        }

        let to_move = stacks_part2[from - 1].split_off(stacks_part2[from - 1].len() - n);
        stacks_part2[to - 1].extend(to_move);
    }
    let part1 = stacks_part1
        .iter_mut()
        .map(|s| s.pop().unwrap())
        .collect::<String>();

    let part2 = stacks_part2
        .iter_mut()
        .map(|s| s.pop().unwrap())
        .collect::<String>();
    println!("05-1: {part1}");
    println!("05-1: {part2}");
}

day06.py

import sys

def day6():
	line = sys.stdin.read()
	def find_marker(window):
		for i in range(window, len(line)+1):
			if len(set([*line[i-window:i]])) == window:
				return i
	part1 = find_marker(4)
	part2 = find_marker(14)
	print(part1, part2)

day07.py

#!/usr/bin/env python3.11

from collections import namedtuple

with open('input') as f:
	lines = [line.strip() for line in f.readlines()]

File = namedtuple('File', ['length'])
Dir = namedtuple('Dir', ['parent', 'entries'])
fs = Dir(None, {})
current = fs
file_sizes = []

def parse(line):
	global current
	global file_sizes
	match line[:4]:
		case '$ cd':
			dname = line[5:]
			if dname == '..':
				current = current.parent
			else:
				if not dname in current.entries:
					current.entries[dname] = Dir(current, {})
				current = current.entries[dname]
		case '$ ls' | 'dir ':
			pass
		case _:
			[size, fname] = line.split(' ')
			size = int(size)
			file_sizes.append(size)
			current.entries[fname] = File(size)

for line in lines:
	parse(line)

def part():
	sizes = []
	def walk(d):
		size = 0
		for e in d.entries.values():
			if type(e) is File:
				size += e.length
			else:
				size += walk(e)
		sizes.append(size)
		return size
	walk(fs)
	return sizes

used = 70000000 - sum(file_sizes)
required = 30000000 - used
part1 = sum([sz for sz in part() if sz <= 100000])
part2 = min([sz for sz in part() if sz >= required])
print(part1, part2)

day08.c

// clang -std=c17 -Wall -Werror -o day8 day8.c && ./day8
#include <stdio.h>

#define INPUT_FILE "input"
#define GRID 99
int trees[GRID][GRID] = {0};

// get height from lower bits
#define TREE_HEIGHT(col,row) (trees[col][row]&0x00ff)
// set visibility in higher bits
#define SET_TREE_VISIBLE(col,row) (trees[col][row] |= 0xff00)
// get visibility from higher bits
#define TREE_VISIBLE(col,row) ((trees[col][row]&0xff00) == 0xff00)

void part1();
void part2();

int main() {
	FILE *fp = fopen(INPUT_FILE, "r");
	if (!fp) perror("failed to read input file");

	int row=0, col=0, tree=0;
	while ((tree = fgetc(fp)) != EOF) {
		if (tree == '\n') {
			row++; col = 0;
			continue;
		}
		trees[col++][row] = tree;
	}
	fclose(fp);

	part1();
	part2();
}

int score(int col, int row) {
	int tree_height = TREE_HEIGHT(col,row);
	int vleft=0, vright=0, vup=0, vdown=0;

	// left
	int y = col;
	while (y-- > 0) {
		vleft++;
		if (tree_height <= TREE_HEIGHT(y,row)) break;
	}
	// right
	y = col;
	while (y++ < GRID-1) {
		vright++;
		if (tree_height <= TREE_HEIGHT(y,row)) break;
	}
	// up
	int x = row;
	while (x-- > 0) {
		vup++;
		if (tree_height <= TREE_HEIGHT(col,x)) break;
	}
	x = row;
	while (x++ < GRID-1) {
		vdown++;
		if (tree_height <= TREE_HEIGHT(col,x)) break;
	}

	return vleft*vright*vup*vdown;
}

void part2() {
	int max=0, s=0;
	for (int row = 0; row < GRID; row++) {
		for (int col = 0; col < GRID; col++) {
			s = score(col, row);
			if (s > max)
				max = s;
		}
	}
	printf("high score = %d\n", max);
}

void part1() {
	int row, col, left, right, up, down;
	// horizontal
	for (row = 1; row < GRID-1; row++) {
		left = TREE_HEIGHT(0,row);
		right = TREE_HEIGHT(GRID-1,row);

		for (col = 1; col < GRID-1; col++) {
			// left
			if (TREE_HEIGHT(col,row) > left) {
				left = TREE_HEIGHT(col,row);
				SET_TREE_VISIBLE(col,row);
			}

			// right
			if (TREE_HEIGHT(GRID-col-1,row) > right) {
				right = TREE_HEIGHT(GRID-col-1,row);
				SET_TREE_VISIBLE(GRID-col-1, row);
			}
		}
	}

	// vertical
	for (col=1; col<GRID-1;col++) {
		up = TREE_HEIGHT(col,0);
		down = TREE_HEIGHT(col,GRID-1);

		for (row=1; row<GRID-1; row++) {
			// up
			if (TREE_HEIGHT(col,row) > up) {
				up = TREE_HEIGHT(col,row);
				SET_TREE_VISIBLE(col,row);
			}

			// down
			if (TREE_HEIGHT(col,GRID-row-1) > down) {
				down = TREE_HEIGHT(col,GRID-row-1);
				SET_TREE_VISIBLE(col, GRID-row-1);
			}
		}
	}

	int visible_trees = GRID*4-4;

	for (row=0; row<GRID; row++) {
		for (col=0; col<GRID; col++) {
			if (TREE_VISIBLE(col,row)) {
				visible_trees++;
				// printf("*%c ", trees[col][row] ^ 0xff00);
			} else {
				// printf(" %c ", trees[col][row]);
			}
		}
		// printf("\n");
	}

	printf("visible trees = %d\n", visible_trees);
}

day09.nim

import std/sets
import std/strscans
import std/strutils

type
    Follower = object
        x, y: int
        visited: HashSet[(int, int)]

proc newFollower(): Follower =
    result = Follower()
    result.visited.incl((0,0))

proc step(f: var Follower, tx, ty: int) =
    if abs(tx-f.x) <= 1 and abs(ty-f.y) <= 1:
        # single step away, don't move
        return
    elif ty == f.y:
        # along x to tx
        f.x += (if tx > f.x: 1 else: -1)
    elif tx == f.x:
        # along y to ty
        f.y += (if ty > f.y: 1 else: -1)
    elif ty > f.y:
        # diagonal
        f.y += 1
        f.x += (if (tx - f.x) < 0: -1 else: 1)
    elif ty < f.y:
        f.y -= 1
        f.x += (if (tx - f.x) < 0: -1 else: 1)
    elif tx > f.x:
        f.x += 1
        f.y += (if (ty - f.y) < 0: -1 else: 1)
    elif tx < f.x:
        f.x -= 1
        f.y = (if (ty - f.y) < 0: -1 else: 1)
    f.visited.incl((f.x, f.y))

var
    x, y: int
    fs: seq[Follower]

for n in 0..<9:
    fs.add(newFollower())

for line in readFile("input").strip().splitLines():
    let (_, dir, mag) = line.scanTuple("$c $i")
    for n in 0..<mag:
        case dir:
        of 'R': x+=1
        of 'L': x-=1
        of 'U': y+=1
        of 'D': y-=1
        else:
            discard
        for i, _ in fs:
            if i == 0:
                fs[i].step(x, y)
            else:
                fs[i].step(fs[i-1].x, fs[i-1].y)

echo "part1=", fs[0].visited.card
echo "part2=", fs[8].visited.card

day10.py

#!/usr/bin/env python3.11
import fileinput

(clock, X, signals, pos) = (0, 1, 0, 0)

def tick():
	global clock
	global X
	global signals
	global pos
	if abs(X - pos) < 2:
		print('⬜', end='')
	else:
		print('⬛', end='')
	pos += 1
	if pos % 40 == 0:
		print()
		pos = 0
	clock += 1
	if (clock - 20) % 40 == 0:
		signals += clock * X

for line in fileinput.input():
	match line.strip().split(' '):
		case ['noop']:
			tick()
		case ['addx', x]:
			tick()
			tick()
			X += int(x)

print(signals)

day11.py

#!/usr/bin/env python3.11
from collections.abc import Callable
from dataclasses import dataclass
from functools import partial

@dataclass
class Monkey:
	num: int
	items: list[int]
	operation: Callable[[int], int]
	test: Callable[[int], int]
	inspections: int = 0

	def play(self, ms, part1=True, common_divisor=0):
		self.inspections += len(self.items)
		for item in self.items:
			if part1:
				wl = self.operation(item) // 3
			else:
				wl = self.operation(item) % common_divisor
			ms[self.test(wl)].items.append(wl)
		self.items = []

def parse():
	ms = []
	common_divisor = 1
	with open('input') as f:
		lines = f.read().strip()
	for defn in lines.split('\n\n'):
		[idn, items, op, test, true, false] = defn.split('\n')
		idn = int(idn[7:-1])
		items = [*map(int, items[18:].split(', '))]
		match op[19:].split(' '):
			case ['old', '*', 'old']:
				op = lambda old: old * old
			case ['old', '*', val]:
				op = partial(lambda v, old: v * old, int(val))
			case ['old', '+', val]:
				op = partial(lambda v, old: v + old, int(val))
			case other:
				raise Exception(f'unknown operation: {other}')
		divBy = int(test.split(' ')[-1:][0])
		common_divisor *= divBy
		true = int(true.split(' ')[-1:][0])
		false = int(false.split(' ')[-1:][0])
		test = partial(lambda t,f,d,n: t if n % d == 0 else f, true, false, divBy)
		ms.append(Monkey(idn, items, op, test))
	return ms, common_divisor


ms, common_divisor = parse()

def part1():
	for _ in range(20):
		for m in ms:
			m.play(ms)
	[a, b] = sorted([m.inspections for m in ms], reverse=True)[:2]
	print(a*b)

def part2():
	for m in ms: m.inspections = 0
	for _ in range(10000):
		for m in ms:
			m.play(ms, False, common_divisor)
	[a, b] = sorted([m.inspections for m in ms], reverse=True)[:2]
	print(a*b)

part1()
part2()

day12.py

#!/usr/bin/env python3.11

def parse():
	with open('input') as f:
		grid = [[*l.strip()] for l in f.readlines()]
	mx, my = len(grid[0]), len(grid)
	adj = {}
	def neighbor(x, y):
		adj[(x,y)] = set()
		for dx,dy in (-1,0), (1,0), (0,1), (0,-1):
			dx=x+dx
			dy=y+dy
			if dx <0 or dy <0 or dx >= mx or dy >= my:
				continue
			if ord(grid[y][x]) <= ord(grid[dy][dx]) or ord(grid[y][x]) == 1+ord(grid[dy][dx]):
				adj[(x,y)].add((dx,dy))

	part2_targets = set()
	for x in range(mx):
		for y in range(my):
			if grid[y][x] == 'S':
				end = (x,y)
				grid[y][x] = 'a'
			if grid[y][x] == 'E':
				start = (x,y)
				grid[y][x] = 'z'
			if grid[y][x] == 'a':
				part2_targets.add((x,y))
	for x in range(mx):
		for y in range(my):
			neighbor(x, y)
	return adj, start, end, part2_targets

def bfs(adj, start, end):
	q = [start]
	parent = {start: None}
	while len(q) > 0:
		v = q.pop(0)
		if v == end:
			break
		for w in adj[v]:
			if w not in parent:
				q.append(w)
				parent[w] = v
	steps=0
	while v != start:
		v = parent[v]
		steps+=1
	return steps

adj, start, end, part2_targets = parse()
part1 = bfs(adj, start, end)
print(part1)

part2 = min(bfs(adj, start, end) for end in part2_targets)
print(part2)

day13.py

#!/usr/bin/env python3.11
import functools, json, sys
def parse():
	lines = [l.strip() for l in sys.stdin.readlines()]
	inputs = []
	for i in range(0,len(lines)-1,3):
		inputs.extend([json.loads(lines[i]), json.loads(lines[i+1])])
	return inputs

inputs = parse()

def compare(l, r):
	# print('compare',l,r)
	match l,r:
		case int(),int():
			return 0 if l==r else 1 if l<r else -1
		case list(),list():
			if not l and r:
				return 1
			elif l and not r:
				return -1
			elif not l and not r:
				return 0
			else:
				for i in range(len(l)):
					if i >= len(r):
						return -1
					res = compare(l[i], r[i])
					if res != 0:
						return res
				if len(l) < len(r):
					return 1
				else:
					return res
		case int(),list():
			return compare([l],r)
		case list(),int():
			return compare(l,[r])


part1_results = [compare(inputs[i],inputs[i+1]) for i in range(0,len(inputs)-1,2)]
part1 = 0
for i, v in enumerate(part1_results):
	part1 += i+1 if v >0 else 0

inputs.extend([ [[2]], [[6]] ])
inputs.sort(reverse=True,key=functools.cmp_to_key(compare))
part2 = (1+inputs.index([[2]])) * (1+inputs.index([[6]]))
print(part1, part2)

day14.py

#!/usr/bin/env python3.11
from itertools import pairwise
import sys
def parse():
	lines = [[[*map(int, coord.split(','))]
				for coord in l.strip().split(' -> ')]
				for l in sys.stdin.readlines()]
	points = set()
	for line in lines:
		for pair in pairwise(line):
			[[x1,y1],[x2,y2]] = sorted(pair)
			points.update((x,y) for x in range(x1,x2+1) for y in range(y1, y2+1))
	(minx, maxx) = min(x for (x,_) in points), max(x for (x,_) in points)
	maxy = max(y for (_,y) in points)
	return points, minx, maxx, maxy

def print_sand(points, minx, maxx, maxy):
	for y in range(maxy+1):
		chrs = ['o' if (x,y) in points else '.' for x in range(minx, maxx+1)]
		print(''.join(chrs), '\n')

def step(points, maxy, part2=False):
	x, y = 500, 0

	while True:
		if y+1 == maxy and part2:
			points.add((x,y))
			return True
		elif y > maxy:
			return False
		elif (x,y+1) not in points:
			y+=1
		elif (x-1,y+1) not in points:
			x-=1; y+=1
		elif (x+1,y+1) not in points:
			x+=1; y+=1
		elif (x,y) == (500, 0):
			return False
		else:
			points.add((x,y))
			return True

points, minx, maxx, maxy = parse()
part1 = 0
while step(points, maxy):
	part1+=1
part2 = part1 + 1
while step(points, maxy+2, True):
	part2+=1
print(part1, part2)
# print_sand(points, minx-20,maxx+20,maxy+2)

day15.py

#!/usr/bin/env python3.11
import math, re, sys
def parse():
	p=re.compile(r'(-?\d+)')
	sensors=set()
	for line in sys.stdin.readlines():
		(sx,sy,bx,by) = map(int, p.findall(line.strip()))
		d = abs(sx-bx)+abs(sy-by)
		sensors.add((sx,sy,d))
	return sensors

def part1(sensors):
	minx, maxx = math.inf, -1*math.inf
	for x,y,d in sensors:
		dy = abs(2_000_000 - y)
		if dy > d:
			continue
		dx = d - dy
		minx=min(x-dx,minx)
		maxx=max(x+dx,maxx)
	return maxx-minx

def part2(sensors):
	def solve(y):
		ranges = []
		for sx, sy, d in sensors:
			dy = abs(y-sy)
			if dy > d:
				continue
			dx = d - dy
			ranges.append((sx-dx, sx+dx))
		ranges.sort()
		prev_x2 = ranges[0][1]
		for x1,x2 in ranges[1:]:
			if x1>prev_x2:
				return prev_x2+1
			prev_x2=max(x2, prev_x2)
		return False
	for y in range(4_000_000):
		if x := solve(y):
			return x*4_000_000+y

sensors = parse()
print(part1(sensors))
print(part2(sensors))