Advent of Code is a yearly series of daily programming puzzles released every December. Previous iterations featured 25 unique puzzles, but this year it was reduced to 12. I took this as an opportunity to use a new language every day, and I wanted each language to be distinct enough (for example, no mixing C and C++).
These were the languages I ended up using, ordered by the day I used them, the languages in italics indicate that I used them for the first time.
For most of the days, I would solve it in Python first before porting my solution to another language. I also revisited some days in Uiua, as I found it to be a very fun language to work with. My solutions are contained in this GitHub repo, and this blog post just goes through more of my thought process for each day.
Here is a summarised execution time for each day, day 2 was omitted because it had a mean execution time of 4.8 seconds.
Day 1: Uiua
Execution time: 276ms
From Uiua's website:
Uiua (wee-wuh) is a general purpose array-oriented programming language with a focus on simplicity, beauty, and tacit code.
I first heard of Uiua 2 months ago when I was browsing Code Golf Stack Exchange and saw a really short solution that was made up of incomprehensible glyphs. It instantly got me hooked on the language, and I felt it was easy to pick up with some functional programming experience and I also found the Uiua Language Tour to be really well made and easy to follow.
My solution for both parts is just 109 bytes, you may view it on the interactive editor:
&fras"1"
⬚0+[50]×⊙≡(˜ⁿ¯1=@L↙1°□)⊸≡(⋕↘1°□)⊜□⊸≠@\n
A←◿100+
B←/+=0\A
C←/+≡(/+°□=0)A⊃(≡□↘¯1\+)(≡(□+⇡⟜(>0))↘1)
⊃C BIt can be optimized a lot, but since this was my first time using the language, there were a lot of idioms I was unfamiliar with. It first processes the puzzle input into numbers, so R30 becomes 30 and L50 becomes -50, 50 is also prepended to the array. For the first part, I just scanned through the array and found all the spots where the dial would hit 0, using a scan with add. For the second part, I used a really inefficient method, where I generate the range of numbers seen by each turn of the dial, and count all the numbers that are congruent to 0 modulo 100.
Day 2: Chez Scheme
Execution time: 4.87s
I love S-Expressions.
In contrast with yesterday's solution, today's solution is 76 lines long, as I had to write helper functions to split strings and numbers.
(define (split-string s delim)
(letrec ([run
(lambda (xs curr acc)
(if (null? xs)
(reverse (cons (list->string (reverse curr)) acc))
(if (equal? (car xs) delim)
(run (cdr xs) '() (cons (list->string (reverse curr)) acc))
(run (cdr xs) (cons (car xs) curr) acc))))
]) (run (string->list s) '() '())))
(display "enter your puzzle input: ")
(define puzzle (get-line (current-input-port)))
(define parsed (map (lambda (s) (map string->number (split-string s #\-))) (split-string puzzle #\,)))
;; inclusive end
(define (range start end)
(map (lambda (x) (+ x start)) (iota (- end start -1))))
(define (log10 n)
(/ (log n) (log 10)))
(define (num-digits n)
(inexact->exact (floor (1+ (log10 n)))))
(define (split-num n)
(let [(delim (expt 10 (/ (num-digits n) 2)))]
(cons (floor (/ n delim)) (mod n delim))))
(define (invalid n)
(if (odd? (num-digits n))
#f
(let [(x (split-num n))]
(= (car x) (cdr x)))))
;; x is number of digits in each split
(define (split-num2 n x)
(letrec [(run (lambda (n acc)
(if (<= (num-digits n) x)
(cons n acc)
(let [(delim (expt 10 x))]
(run (floor (/ n delim)) (cons (mod n delim) acc))
))
))] (run n '())))
(define (invalid2 n)
(letrec [(num (num-digits n)) (run (lambda (x)
(if (= x 0)
#f
(if (and (zero? (mod num x)) (apply = (split-num2 n x)))
#t
(run (1- x))
)
)
))] (run (1- (num-digits n))))
)
(define (sol parsed invalid)
(fold-left
(lambda (x y)
(+ x (fold-left
(lambda (x y)
(if (invalid y)
(+ x y)
x))
0
(apply range y))))
0
parsed))
(display (sol parsed invalid))
(newline)
(display (sol parsed invalid2))It's just a simple brute force, I did have to spend a short while debugging my part 2, because one of my functions wasn't tail-recursive and it ended up hanging my laptop, but after fixing that it spits out the solution in 5 seconds.
Day 3: C
Execution time: 12.6ms
For day 3, I solved it first in C using a typical DP solution. Then I solved it again in Uiua using a greedy approach.
#include <stdio.h>
#include <math.h>
long long getDigit(char line[100], int i) {
return line[i] - 48;
}
long long sol(char line[100], int n) {
// let dp[i][n] denote the max joltage only considering index i onwards, with n digits
long long dp[100][n + 1];
dp[99][0] = 0;
dp[99][1] = getDigit(line, 99);
for (int i = 1; i < 100; i++) {
for (int j = 0; j < n + 1; j++) {
if (j == i+1) {
dp[99 - i][j] = dp[99 - i + 1][j - 1] + getDigit(line, 99 - i) * pow(10, j - 1);
break;
}
if (j)
dp[99 - i][j] = fmax(dp[99 - i + 1][j], dp[99 - i + 1][j - 1] + getDigit(line, 99 - i) * pow(10, j - 1));
else
dp[99 - i][0] = 0;
}
}
return dp[0][n];
}
int main() {
FILE *fptr = fopen("3", "r");
char line[100];
int part1 = 0;
long long part2 = 0;
while (fscanf(fptr, "%s", line) == 1) {
part1 += sol(line, 2);
part2 += sol(line, 12);
}
printf("Part 1: %d\n", part1);
printf("Part 2: %lli", part2);
}I'm honestly not sure why I used DP here, I initially solved part 1 with the greedy approach, I guess I just didn't realise it generalises to any digit number. The greedy solution is still faster by a constant factor and takes less memory.
You may view my solution on the interactive editor.
&fras"3"
⊜∘⊸≠@\n
A←/+≡(⋕≡⊡⊙¤-1↘1⊸˜\(++1⊙(⊢⍖˜↘)⟜↘))¤⊂[0]+1⇌⇡¯
⊃(A12|A2)We basically just find the index of the max character from [0:-11], lets call this index n. Then we find the index of the max character from [n:-10], and keep repeating this procedure until we get all 12 characters. Uiua has a handy function called fall that returns the indices of the list if its elements were sorted in descending order, while this is O(n log n), if we use the first function to only get the max index, the Uiua interpreter optimizes it to O(n).
Day 4: Rust
Execution time: 37.3ms
I originally solved today's solution with a simple brute force in Python because I was busy. After getting home past midnight, I decided I did not want to waste Python on such an easy day, so I learnt Rust and wrote a more efficient solution.
use std::fs;
fn get_surrounding_rolls(contents: &[Vec<u8>], row: usize, col: usize) -> Vec<(usize, usize)> {
let height = contents.len();
let width = contents[0].len();
let row_start = row.saturating_sub(1);
let row_end = (row + 2).min(height);
let col_start = col.saturating_sub(1);
let col_end = (col + 2).min(width);
contents[row_start..row_end]
.iter()
.enumerate()
.flat_map(|(i, r)| {
r[col_start..col_end]
.iter()
.enumerate()
.filter(move |&(j, &cell)| {
cell == b'@' && (row_start + i, col_start + j) != (row, col)
})
.map(move |(j, _)| (row_start + i, col_start + j))
})
.collect()
}
fn main() {
let binding = fs::read_to_string("4").expect("read the file");
let mut contents: Vec<Vec<u8>> = binding.lines().map(|s| s.as_bytes().to_vec()).collect();
let height = contents.len();
let width = contents[0].len();
let mut indices = Vec::new();
for row in 0..height {
for col in 0..width {
if contents[row][col] == b'@' && get_surrounding_rolls(&contents, row, col).len() < 4 {
indices.push((row, col));
contents[row][col] = b'.';
}
}
}
let mut total = indices.len();
println!("Part 1: {}", total);
while !indices.is_empty() {
let mut temp = Vec::new();
for (r, c) in indices {
for (row, col) in get_surrounding_rolls(&contents, r, c) {
if get_surrounding_rolls(&contents, row, col).len() < 4 {
temp.push((row, col));
contents[row][col] = b'.';
}
}
}
total += temp.len();
indices = temp;
}
println!("Part 2: {}", total);
}The key idea is that after solving part 1, you just need to keep track of the rolls that got removed, and keep repeating part 1 until no rolls can be removed. It took a bit of fighting with the borrow checker, but I'm quite happy with my solution. I had a good first experience with Rust and I'm looking forward to using it for other bigger projects (probably for a compiler).
Day 5: Zig
Execution time: 17.3ms
const std = @import("std");
const fs = std.fs;
const twople = struct { start: i64, end: i64, };
const ArrayList = std.ArrayList;
fn compareTwople(_: void, a: twople, b: twople) bool {
return a.start < b.start;
}
pub fn main() !void {
const file = try fs.cwd().openFile("5", .{});
const reader = file.reader().any();
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var buf: [1024]u8 = undefined;
var ranges = ArrayList(twople).init(allocator);
defer ranges.deinit();
var ids = ArrayList(i64).init(allocator);
defer ids.deinit();
while (try reader.readUntilDelimiterOrEof(buf[0..], '\n')) |line| {
if (line.len == 0) {
break;
}
var it = std.mem.splitScalar(u8, line, '-');
const range = twople{ .start = try std.fmt.parseInt(i64, it.next() orelse "" , 10), .end = try std.fmt.parseInt(i64, it.next() orelse "", 10) };
try ranges.append(range);
}
while (try reader.readUntilDelimiterOrEof(buf[0..], '\n')) |line| {
try ids.append(try std.fmt.parseInt(i64, line, 10));
}
std.mem.sort(twople, ranges.items, {}, compareTwople);
var i: usize = 0;
while (i < ranges.items.len - 1) {
const curr_range = ranges.items[i];
const next_range = ranges.items[i+1];
if (next_range.start <= curr_range.end + 1) {
if (next_range.end > curr_range.end) {
ranges.items[i] = twople { .start = curr_range.start, .end = next_range.end};
}
_ = ranges.orderedRemove(i+1);
}
else {
i += 1;
}
}
var part1: i16 = 0;
for (ids.items) |id| {
for (ranges.items) |r| {
if (r.start <= id and id <= r.end) {
part1 += 1;
break;
}
}
}
var part2: i64 = 0;
for (ranges.items) |r| {
part2 += r.end - r.start + 1;
}
std.debug.print("{d}\n", .{part1});
std.debug.print("{d}\n", .{part2});
}There's nothing much to say here, it is basically just the merge intervals leetcode problem.
Day 6: Elixir
Execution time: 624ms (Part 2 only)
Today, I initially solved with Python, then solved part 2 with Uiua and Elixir because part 1 is pretty boring... that counts right?
View my Uiua code on the iteractive editor.
&fras"6"
⊜∘⊸≠@\n
⟜(⊜⊢⊸≠@ ⊣)
⍉↘¯1
⊜(□⋕)⊸(≠0≡/+≠@ )
/+˜≡◇(⨬/+/×⊢=@*)I wrote a full explanation for how it works, but I feel like it is far too lengthy to be contained in this blog post, curious readers can refer to the explanation on the GitHub
Here is my part 2 Elixir code:
{:ok, file} = File.read("6")
inputs = String.split(file, "\n")
nums = Enum.map(Enum.slice(inputs, 0..3), fn x -> String.graphemes(x) end)
zipped = Enum.zip_with(nums, fn [w, x, y, z] -> [w, x, y, z] end)
ops = String.split(Enum.at(inputs, 4))
defmodule Part2 do
def solve([], [], acc) do
acc
end
def solve([nums | rest_nums], [op | rest_ops], acc) do
if op == "*" do
solve(rest_nums, rest_ops, acc + Enum.reduce(nums, fn x, y -> x * y end))
else
solve(rest_nums, rest_ops, acc + Enum.sum(nums))
end
end
def parse([], acc) do
Enum.reverse(acc)
end
def parse([head | tail], [acc_head | acc_tail]) do
if head == [" ", " ", " ", " "] do
parse(tail, [[] | [acc_head | acc_tail]])
else
parsed = String.to_integer(String.trim(List.to_string(head)))
parse(tail, [[parsed | acc_head] | acc_tail])
end
end
def parse(nums) do
parse(nums, [[]])
end
end
IO.puts(Part2.solve(Part2.parse(zipped), ops, 0))Day 7: Go
Execution time: 4.38ms
Day 7 was super easy, my Go solution was pretty much just a port of my Python solution.
package main
import (
"bufio"
"fmt"
"os"
"strings"
)
func main() {
filePath := "7"
file, _ := os.Open(filePath)
defer file.Close()
scanner := bufio.NewScanner(file)
scanner.Scan()
line := scanner.Text()
beams := make([]int, len(line))
beams[strings.IndexByte(line, 'S')] = 1
part1 := 0
for scanner.Scan() {
line := scanner.Text()
new_beams := make([]int, len(line))
for i, r := range line {
if r == '^' {
if beams[i] != 0 {
new_beams[i-1] += beams[i]
new_beams[i+1] += beams[i]
part1 += 1
}
} else {
new_beams[i] += beams[i]
}
}
beams = new_beams
}
part2 := 0
for _, n := range beams {
part2 += n
}
fmt.Println(part1)
fmt.Println(part2)
}I solved it again in Uiua, and it is my shortest solution yet, when golfed it is just 59 bytes! The solution method also slightly differs, as I iterate through the input, I keep track of the number of beams in each column. For each row in the input, I mask the beams the hit a splitter, apply a rotate left and right to simulate them splitting, and add them up together with the beams that did not hit the splitters. At the end of the iteration I can just do a reduce add.
View my Uiua code on the interactive editor.
0
&fras"7"
⊜∘⊸≠@\n # Parse by new line
=@S°⊂ # create array of 0s except for start
˜⊙∘
Part₁ ← +/+≠0× # Count number of beams that hit splitters
# Get beams that hit splitters,
# rotate 1 and rotate -1,
# add together with beams that miss splitters
Part₂ ← ++⊃(⊃(↻1|↻¯1)×|׬)
∧(⊃(Part₂|Part₁)=@^)
/+Day 8: OCaml
Execution time: 249ms
My favourite day so far, probably cause its the hardest so far. The implementation is quite simple, stick all pair combinations in a heap, where the priority is the euclidean distance between the two points, then use a UFDS (Union Find Disjoin Set) to efficiently track the circuits. Luckily OCaml added priority queues to the standard library about 2 months ago, but there's no UFDS so I implemented my own.
UFDS:
type 'a t = {
parent : ('a, 'a) Hashtbl.t;
rank : ('a, int) Hashtbl.t ;
}
let create (n : int) : 'a t = {
parent = Hashtbl.create n;
rank = Hashtbl.create n;
}
let rec find ds x = match Hashtbl.find_opt ds.parent x with
| Some parent ->
if parent = x then parent
else begin
let parent = find ds parent in
Hashtbl.replace ds.parent x parent;
parent
end;
| None -> (
Hashtbl.add ds.parent x x;
Hashtbl.add ds.rank x 0;
x
)
let union ds a b =
let a = find ds a in
let b = find ds b in
if a <> b then
let a_rank = Hashtbl.find ds.rank a in
let b_rank = Hashtbl.find ds.rank b in
if a_rank < b_rank then
Hashtbl.replace ds.parent a b
else begin
Hashtbl.replace ds.parent b a;
if a_rank = b_rank then Hashtbl.replace ds.rank a (a_rank + 1)
endMain solution:
open Day8
module Prio : Pqueue.OrderedType with type t = int = struct
type t = int
let compare = compare
end
module PrioQueue = Pqueue.MakeMinPoly(struct
type 'a t = Prio.t * 'a
let compare (p1, _) (p2, _) = Prio.compare p1 p2
end)
exception Value_not_found of string
let () =
let start_time = Sys.time() in
let pq = PrioQueue.create() in
let ic = open_in "../8" in
let rec read_lines ic acc =
match input_line ic with
| exception End_of_file -> acc
| line ->
let nums = line |> String.split_on_char ','
|> List.map (fun s -> int_of_string ) in
match nums with
| [x; y; z] -> read_lines ic ((x, y, z) :: acc)
| _ -> failwith ("Invalid line: " ^ line)
in
let result = read_lines ic [] in
let rec all_pair_combinations coords acc = match coords with
| [] -> acc
| hd :: tl -> all_pair_combinations tl ((List.map (fun x -> (hd, x)) tl) @ acc)
in
let square x = x * x in
let distance (x1, y1, z1) (x2, y2, z2) = square (x1 - x2) + square (y1 - y2) + square (z1 - z2) in
List.iter (fun x -> PrioQueue.add pq (distance (fst x) (snd x), x)) (all_pair_combinations result []);
let get_x (x, _, _) = x in
let uf = List.length result |> Union_find.create in
let rec solve i n =
let pair = match PrioQueue.pop_min pq with
| Some (x, y) -> y
| None -> raise (Value_not_found "Expected a pair")
in
if i = 1000 then begin
Hashtbl.to_seq_keys uf.parent
|> Seq.iter (fun x -> Union_find.find uf x |> ignore);
Hashtbl.to_seq_values uf.parent
|> Seq.fold_left (fun acc x -> (match Hashtbl.find_opt acc x with
| Some v -> Hashtbl.replace acc x (v+1)
| None -> Hashtbl.add acc x 1
); acc)
(Hashtbl.create 100)
|> Hashtbl.to_seq_values
|> List.of_seq
|> List.sort (fun x y -> -(compare x y))
|> List.take 3
|> List.fold_left (fun x y -> x * y) 1
|> Printf.printf "Part 1: %d\n"
end;
if Union_find.find uf (fst pair) <> Union_find.find uf (snd pair) then begin
Union_find.union uf (fst pair) (snd pair);
if n = 2 then
Printf.printf "Part 2: %d\n" ((fst pair |> get_x) * (snd pair |> get_x))
else
solve (i + 1) (n - 1)
end
else solve (i + 1) n
in
solve 0 (List.length result);
Printf.printf "Execution time: %f seconds\n" (Sys.time() -. start_time);Day 9: Java
Execution time: 107ms
Today's puzzle had a pretty hard part 2, but upon inspecting the inputs you will find that the points given are very nice and you can exploit the structure of the shape formed. I based my solution off the shape of the input, which allows me to achieve 30ms solves with Python. Some people may not agree with this approach, but imo finding ways to exploit the input is part of these puzzles.
Part 1 is trivial, since you can just do an O(n^2) brute force, and actually takes up most of the runtime. Part 2 is more interesting, and I used a ray casting algorithm to detect if a point was in the overall polygon.
Before starting on part 2, I plotted out all the points, and joined the adjacent points together, and found out that today's inputs has the following shape:
This trivialises the problem a lot, observe that to obtain the maximum area, we must choose one of those 2 points lying in the middle. Furthermore if we choose the higher mid point, then we can only form rectangles with points above it, otherwise it will cross the gap in the middle. Same thing for the lower mid point.
So my solving strategy was to first find these 2 mid points, then iterate over all points to the left of them, and try to form a valid rectangle. To detect if a rectangle is valid, I check if the other 2 corners of the rectangle lie inside the polygon, using a simple ray casting trick. If you shoot a beam to the left of the point, and it intersects an odd number of vertical walls, then it is in the polygon.
Along with some minor optimizations, I got my overall solution down to 30ms on my machine! I did have one hiccup, where my area function was defined wrongly (try and spot the mistake below), and I spent half an hour debugging my code before realising.
def area(p1, p2):
return abs((p1[0] - p2[0] + 1) * (p1[1] - p2[1] + 1))Here is my overall solution, while I did solve it with Java, the solution method did not differ from my original Python solution, and it's just more verbose, so I will just paste my Python solution here:
inp = list(map(lambda x: tuple(map(int, x.split(","))), open("9").read().splitlines()))
def area(p1, p2):
return (abs(p1[0] - p2[0]) + 1) * (abs(p1[1] - p2[1]) + 1)
max_area = 0
for i in range(len(inp)):
for j in range(i + 1, len(inp)):
max_area = max(max_area, area(inp[i], inp[j]))
print(f"Part 1: {max_area}")
vertical_lines = sorted(
[sorted(inp[i : i + 2], key=lambda x: x[1]) for i in range(0, len(inp), 2)],
key=lambda x: x[0][0],
)
horizontal_lines = [
sorted(inp[i : i + 2], key=lambda x: x[0]) for i in range(1, len(inp) - 1, 2)
]
def in_poly(p):
# Ray cast to left
num_crossings = 0
lows = set()
highs = set()
for line in vertical_lines:
if line[0][0] >= p[0]:
break
if line[0][1] <= p[1] <= line[1][1]:
if line[0][1] == p[1] and p[1] in highs:
continue
if line[1][1] == p[1] and p[1] in lows:
continue
lows.add(line[0][1])
highs.add(line[1][1])
num_crossings += 1
return num_crossings % 2 == 1
longest_two = sorted(
horizontal_lines, key=lambda x: abs(x[0][0] - x[1][0]), reverse=True
)
mid1 = (
longest_two[0][0]
if longest_two[0][0][0] > longest_two[0][1][0]
else longest_two[0][1]
)
mid2 = (
longest_two[1][0]
if longest_two[1][0][0] > longest_two[1][1][0]
else longest_two[1][1]
)
if mid1[1] < mid2[1]:
mid1, mid2 = mid2, mid1
mid1_ylimit = 0
mid2_ylimit = 0
for i in horizontal_lines:
if i[0][1] > mid1[1] and i[0][0] <= mid1[0] <= i[1][0]:
mid1_ylimit = i[0][1]
if i[0][1] < mid2[1] and i[0][0] <= mid2[0] <= i[1][0]:
mid2_ylimit = i[0][1]
max_area = 0
for p in inp:
m = None
if p[0] >= mid1[0]:
continue
if mid1[1] <= p[1] <= mid1_ylimit:
m = mid1
elif mid2[1] <= p[1] <= mid2_ylimit:
m = mid2
if m is not None:
p1, p2 = (p[0], m[1]), (m[0], p[1])
if (a := area(m, p)) > max_area and in_poly(p1) and in_poly(p2):
max_area = aThis was the rectangle my code found:
Day 10: Python
Execution time: 1.04s
Day 10 was the hardest day out of all 12 days, which is why it is the Python day. The second part required math I did not know, so I honestly did not solve it until the last day, where it was required to get the last star. In the end, I still don't fully understand the underlying math, I just googled a bit on how to use z3 and plugged the problem into the optimizer to find the minimal solution. It surprisingly only took like half an hour to figure out how to use z3 and express the problem in it.
from collections import deque
from z3 import Int, Optimize, Sum, sat
inp = list(map(str.split, open("10").read().splitlines()))
data = []
for line in inp:
temp = []
temp.append(sum(1 << i for i, v in enumerate(line[0][1:-1]) if v == "#"))
temp += list(map(lambda x: tuple(map(int, x[1:-1].split(","))), line[1:-1]))
temp.append(tuple(map(int, line[-1][1:-1].split(","))))
data.append(tuple(temp))
part1 = 0
for line in data:
goal = line[0]
q = deque([(i, 0, 0) for i in line[1:-1]])
visited = set()
while (curr := q.popleft())[1] != goal:
new = curr[1]
switch = 0
for i in curr[0]:
switch += 1 << i
new ^= switch
if new in visited:
continue
visited.add(new)
q.extend([(i, new, curr[2] + 1) for i in line[1:-1]])
part1 += curr[2]
print(f"Part 1: {part1}")
part2 = 0
for line in data:
ints = []
s = Optimize()
for i in range(len(line[1:-1])):
ints.append(Int(f"v{i}"))
s.add(ints[i] >= 0)
for i in range(len(line[-1])):
x = []
for j in range(len(line[1:-1])):
if i in line[j + 1]:
x.append(ints[j])
s.add(Sum(x) == line[-1][i])
s.minimize(Sum(ints))
if s.check() == sat:
m = s.model()
part2 += m.evaluate(Sum(ints)).as_long()
print(f"Part 2: {part2}")Day 11: JavaScript
Execution time: 52.2ms
Day 11 was so much easier than day 10, that it was kinda underwhelming. It's basically just a depth first search with memoization.
const fs = require("fs");
let memo = {};
let edges = {};
function num_paths(src, dst) {
const key = `${src} ${dst}`;
if (!(key in memo)) {
ret = 0;
edges[src].forEach((x) => {
if (x === dst) ret += 1;
else ret += num_paths(x, dst);
});
memo[key] = ret;
}
return memo[key];
}
fs.readFile("11", "utf8", (err, data) => {
if (err) {
console.log(err);
return;
}
data.split("\n").forEach((line) => {
if (line.length != 0) {
let temp = line.split(":");
edges[temp[0]] = temp[1].trim().split(" ");
}
});
edges["out"] = [];
console.log(`Part 1: ${num_paths("you", "out")}`);
console.log(
`Part 2: ${num_paths("svr", "fft") * num_paths("fft", "dac") * num_paths("dac", "out")}`,
);
});We can just define a memoized recursive function that finds the number of paths from source to destination. Part 2 is just num_paths("svr", "fft") * num_paths("fft", "dac") * num_paths("dac", "out").
Day 12: JLox
Execution time: 194ms
The last day presented us with an NP-Hard problem, which shocked many of us when we initially saw it. We are given a set of 6 irregular shapes, each line in the puzzle gives us the area of a grid and the number of each shape we must fit in the grid. Then we have to find the number of grids where such an arrangement is possible.
Luckily, the inputs were very nice, and in all cases, you can just check if the grid is large enough to fit all the shapes laid out side by side without any intersection between the shapes.
Since the solution is so simple, I decided to implement it in my own programming language! I have been working on JLox from Crafting Interpreters and decided to add enough native functions such as stringSplit and read to make the problem solvable. I found it funny that although stringSplit returns an array, there is no way to actually create arrays in my language yet. This program was run on this specific commit in my JLox implementation.
var inp = stringSplit(read("12"), "\n");
var part1 = 0;
for (var i = 30; i < arrayLength(inp); i = i + 1) {
var line = stringSplit(inp[i], ":");
var size = stringSplit(line[0], "x");
var maxBlocks = floor(stringToNumber(size[0]) / 3) * floor(stringToNumber(size[1]) / 3);
var total = 0;
for (var j = 1; j < 7; j = j + 1)
total = total + stringToNumber(stringSplit(line[1], " ")[j]);
if (total <= maxBlocks)
part1 = part1 + 1;
}
print "Part 1: ${part1}";Conclusion
While I did manage to solve some puzzles in new languages I have not touched before, I can't say that I have truly learned those languages, since I mostly relied on a lot of Googling along the lines of "how to accomplish <task> in <language>". That said it did give me a nice exposure to each of these languages, and there will certainly be less friction if I decide to work on a project in any of them in the future. For future years, I will just go back to focusing on one single language.
I felt that this year's Advent of Code was far easier than previous years, and not just because of the reduced days. Day 10 was the only puzzle that really stood out as difficult, and in the end it can just be solved by expressing the problem in z3. Nonetheless, I still had a lot of fun with AOC, and enjoyed interacting with different communities throughout the 12 days. I really appreciate Eric's work towards designing these puzzles every year for the past 11 years, and look forward to the next one!