aboutsummaryrefslogtreecommitdiff
path: root/2021
diff options
context:
space:
mode:
Diffstat (limited to '2021')
-rw-r--r--2021/day-01/day-01.pl20
-rw-r--r--2021/day-01/day-01.rkt20
-rw-r--r--2021/day-02/day-02.ex32
-rw-r--r--2021/day-02/day-02.rkt39
-rw-r--r--2021/day-03/day-03.rkt50
-rw-r--r--2021/day-04/day-04.rkt62
-rw-r--r--2021/day-05/day-05.rkt63
-rw-r--r--2021/day-06/day-06.ex35
-rw-r--r--2021/day-06/day-06.livemd151
-rw-r--r--2021/day-06/day-06.rkt33
-rw-r--r--2021/day-06/input.txt1
-rw-r--r--2021/day-07/day-07.rkt30
-rw-r--r--2021/day-08/day-08.rkt83
-rw-r--r--2021/day-09/day-09.bak60
-rw-r--r--2021/day-09/day-09.livemd138
-rw-r--r--2021/day-09/day-09.rkt78
-rw-r--r--2021/day-09/input.txt100
17 files changed, 995 insertions, 0 deletions
diff --git a/2021/day-01/day-01.pl b/2021/day-01/day-01.pl
new file mode 100644
index 0000000..d3c3fa7
--- /dev/null
+++ b/2021/day-01/day-01.pl
@@ -0,0 +1,20 @@
+:- use_module(library(yall)).
+:- use_module(library(apply)).
+
+get_data(Result) :-
+ setup_call_cleanup(open("day-01/input.txt", read, In),
+ (read_string(In, _, Str),
+ split_string(Str, "\n", "\s\t\n", Lines),
+ maplist(number_string, Result, Lines)),
+ close(In)).
+
+calculate_diffs(Result, WindowWidth) :-
+ get_data(Xs),
+ length(TrimLeft, WindowWidth), append(TrimLeft, RightSide, Xs),
+ length(TrimRight, WindowWidth), append(LeftSide, TrimRight, Xs),
+ maplist([X, Y, Z]>>(Z is Y - X), LeftSide, RightSide, Diffs),
+ include([X]>>(X > 0), Diffs, Increases),
+ length(Increases, Result).
+
+part1_answer(Result) :- calculate_diffs(Result, 1).
+part2_answer(Result) :- calculate_diffs(Result, 3). \ No newline at end of file
diff --git a/2021/day-01/day-01.rkt b/2021/day-01/day-01.rkt
new file mode 100644
index 0000000..48ef158
--- /dev/null
+++ b/2021/day-01/day-01.rkt
@@ -0,0 +1,20 @@
+#lang racket
+(require advent-of-code
+ threading)
+
+;; part 1
+(define sensor-data
+ (~> (open-aoc-input (find-session) 2021 1 #:cache (string->path "./cache"))
+ (port->list read _)))
+
+(define (count-increases data offset)
+ (for/sum ([x (in-list data)]
+ [y (in-list (drop data offset))]
+ #:when (< x y))
+ 1))
+
+(~a "Part 1: " (count-increases sensor-data 1))
+
+;; part 2
+
+(~a "Part 2: " (count-increases sensor-data 3)) \ No newline at end of file
diff --git a/2021/day-02/day-02.ex b/2021/day-02/day-02.ex
new file mode 100644
index 0000000..d37ab05
--- /dev/null
+++ b/2021/day-02/day-02.ex
@@ -0,0 +1,32 @@
+defmodule Day02 do
+ def part_one(data) do
+ data
+ |> Enum.reduce(%{pos: 0, dep: 0}, &method_one/2)
+ |> get_answer()
+ end
+
+ def part_two(data) do
+ data
+ |> Enum.reduce(%{pos: 0, dep: 0, aim: 0}, &method_two/2)
+ |> get_answer()
+ end
+
+ defp method_one({:forward, x}, s), do: %{s | pos: s.pos + x}
+ defp method_one({:up, x}, s), do: %{s | dep: s.dep - x}
+ defp method_one({:down, x}, s), do: %{s | dep: s.dep + x}
+
+ defp method_two({:forward, x}, s), do: %{s | pos: s.pos + x, dep: s.dep + s.aim * x}
+ defp method_two({:up, x}, s), do: %{s | aim: s.aim - x}
+ defp method_two({:down, x}, s), do: %{s | aim: s.aim + x}
+
+ defp get_answer(s), do: s.pos * s.dep
+end
+
+data =
+ File.read!("day-02/input.txt")
+ |> String.split("\n", trim: true)
+ |> Enum.map(&String.split/1)
+ |> Enum.map(fn [dir, amt] -> {String.to_atom(dir), String.to_integer(amt)} end)
+
+Day02.part_one(data) |> IO.inspect()
+Day02.part_two(data) |> IO.inspect()
diff --git a/2021/day-02/day-02.rkt b/2021/day-02/day-02.rkt
new file mode 100644
index 0000000..dbd1275
--- /dev/null
+++ b/2021/day-02/day-02.rkt
@@ -0,0 +1,39 @@
+#lang racket
+(require advent-of-code
+ threading
+ algorithms)
+
+(define motion-data
+ (~> (open-aoc-input (find-session) 2021 2 #:cache (string->path "./cache"))
+ (port->list read _)
+ (chunks-of _ 2)))
+
+;; part 1
+(for/fold ([depth 0]
+ [position 0]
+ #:result (* depth position))
+ ([motion (in-list motion-data)])
+ (match motion
+ [(list 'forward x) (values depth
+ (+ position x))]
+ [(list 'up x) (values (- depth x)
+ position)]
+ [(list 'down x) (values (+ depth x)
+ position)]))
+
+;; part 2
+(for/fold ([aim 0]
+ [depth 0]
+ [position 0]
+ #:result (* depth position))
+ ([motion (in-list motion-data)])
+ (match motion
+ [(list 'forward x) (values aim
+ (+ depth (* aim x))
+ (+ position x))]
+ [(list 'up x) (values (- aim x)
+ depth
+ position)]
+ [(list 'down x) (values (+ aim x)
+ depth
+ position)])) \ No newline at end of file
diff --git a/2021/day-03/day-03.rkt b/2021/day-03/day-03.rkt
new file mode 100644
index 0000000..f26d5a4
--- /dev/null
+++ b/2021/day-03/day-03.rkt
@@ -0,0 +1,50 @@
+#lang racket
+(require advent-of-code
+ threading)
+
+(define data
+ (~> (open-aoc-input (find-session) 2021 3 #:cache (string->path "./cache"))
+ port->lines
+ (map string->list _)))
+
+;; part 1
+(define most-common-bits
+ (for*/list ([row (in-list (apply map list data))]
+ [len (in-value (length data))])
+ (if (> (count (λ (c) (char=? #\1 c)) row) (/ len 2))
+ #\1
+ #\0)))
+(define (bit-list->number lst)
+ (~> lst
+ (apply string _)
+ (string->number _ 2)))
+
+(define gamma
+ (bit-list->number most-common-bits))
+(define epsilon
+ (~> most-common-bits
+ (map (λ (c) (if (char=? c #\1) #\0 #\1)) _)
+ bit-list->number))
+
+(* gamma epsilon)
+
+;; part 2
+(define (rating-search data comparison)
+ (for/fold ([candidates data]
+ #:result (bit-list->number (first candidates)))
+ ([bit (in-list most-common-bits)]
+ [bit-index (in-range 0 (length most-common-bits))])
+ #:break (= 1 (length candidates))
+ (define keep-bit
+ (~> candidates
+ (apply map list _)
+ (list-ref _ bit-index)
+ (count (λ (c) (char=? #\1 c)) _)
+ (comparison _ (/ (length candidates) 2))
+ (if _ #\1 #\0)))
+ (filter (λ (row) (char=? keep-bit (list-ref row bit-index))) candidates)))
+
+(define oxygen-rating (rating-search data >=))
+(define scrubber-rating (rating-search data <))
+
+(* oxygen-rating scrubber-rating)
diff --git a/2021/day-04/day-04.rkt b/2021/day-04/day-04.rkt
new file mode 100644
index 0000000..fdf1ea1
--- /dev/null
+++ b/2021/day-04/day-04.rkt
@@ -0,0 +1,62 @@
+#lang racket
+(require advent-of-code
+ threading
+ (only-in awesome-list transpose)
+ (only-in algorithms chunks-of))
+
+(define data
+ (for/list ([l (in-lines (open-aoc-input (find-session) 2021 4 #:cache (string->path "./cache")))]
+ #:unless (equal? l ""))
+ l))
+
+(define call-sheet
+ (~> data
+ car
+ (string-split ",")
+ (map string->number _)))
+(define bingo-cards
+ (~> data
+ cdr
+ (map string-split _)
+ (map (λ (row) (map string->number row)) _)
+ (chunks-of 5)))
+
+(define test-card (first bingo-cards))
+
+(define (mark-card card call)
+ (for/list ([row (in-list card)])
+ (for/list ([col (in-list row)])
+ (if (eq? col call) 'X col))))
+
+(define (check-card card)
+ (for/or ([row (in-sequences card (transpose card))])
+ (equal? row '(X X X X X))))
+
+(define (multiply-by-last-call n call)
+ (match n
+ ['X 0]
+ [n (* n call)]))
+
+(define (evaluate-cards cards calls [check (curry ormap check-card)] [exception not])
+ (for/fold ([current-cards cards]
+ [last-call 0]
+ #:result (~> current-cards
+ (findf check-card _)
+ flatten
+ (map (λ (n) (multiply-by-last-call n last-call)) _)
+ (apply + _)))
+ ([call (in-list calls)])
+ #:break (check current-cards)
+ (values (for/list ([card (in-list current-cards)]
+ #:unless (exception card))
+ (mark-card card call))
+ call)))
+
+;; part 1
+(evaluate-cards bingo-cards call-sheet)
+;; part 2
+(evaluate-cards bingo-cards
+ call-sheet
+ (λ (cards) (and (= (length cards) 1)
+ (check-card (first cards))))
+ check-card) \ No newline at end of file
diff --git a/2021/day-05/day-05.rkt b/2021/day-05/day-05.rkt
new file mode 100644
index 0000000..49ce502
--- /dev/null
+++ b/2021/day-05/day-05.rkt
@@ -0,0 +1,63 @@
+#lang racket
+(require advent-of-code
+ threading)
+
+(define data
+ (for/list ([l (in-lines (open-aoc-input (find-session) 2021 5 #:cache (string->path "./cache")))])
+ (~> l
+ (string-replace " -> " ",")
+ (string-split ",")
+ (map string->number _))))
+
+(define (trace-line! x y vec)
+ (define linear-coord (+ y (* 1000 x)))
+ (vector-set! vec
+ linear-coord
+ (+ 1 (vector-ref vec linear-coord))))
+
+(define/match (orthogonal? coord-pair)
+ [((or (list n _ n _) (list _ n _ n))) #t]
+ [(_) #f])
+
+(define-values (orthogonal-lines diagonal-lines)
+ (partition orthogonal? data))
+
+(define (dir a b) (if (< a b) 1 -1))
+
+(define (trace-orthogonal! coord-pairs tracer result)
+ (for ([coord-pair (in-list coord-pairs)])
+ (match coord-pair
+ [(list x y1 x y2)
+ (for ([y (inclusive-range y1 y2 (dir y1 y2))])
+ (tracer x y result))]
+ [(list x1 y x2 y)
+ (for ([x (inclusive-range x1 x2 (dir x1 x2))])
+ (tracer x y result))])))
+
+(define (trace-diagonal! coord-pairs tracer result)
+ (for ([coord-pair (in-list coord-pairs)])
+ (match-define (list x1 y1 x2 y2) coord-pair)
+ (for ([x (inclusive-range x1 x2 (dir x1 x2))]
+ [y (inclusive-range y1 y2 (dir y1 y2))])
+ (tracer x y result))))
+
+;; part 1
+(define sea-floor (make-vector 1000000))
+(trace-orthogonal! orthogonal-lines trace-line! sea-floor)
+(vector-count (curry <= 2) sea-floor)
+
+;; part 2
+;; since the orthogonal lines have already been traced,
+;; all I need to do is add the diagonal ones to the existing vector
+(trace-diagonal! diagonal-lines trace-line! sea-floor)
+(vector-count (curry <= 2) sea-floor)
+
+;; alternate sparse representation
+(define (trace-line-sparse! x y dict)
+ (hash-update! dict (list x y) (curry + 1) 0))
+
+(define sea-floor-dict (make-hash))
+(trace-orthogonal! orthogonal-lines trace-line-sparse! sea-floor-dict)
+(count (curry <= 2) (hash-values sea-floor-dict))
+(trace-diagonal! diagonal-lines trace-line-sparse! sea-floor-dict)
+(count (curry <= 2) (hash-values sea-floor-dict))
diff --git a/2021/day-06/day-06.ex b/2021/day-06/day-06.ex
new file mode 100644
index 0000000..efe10e4
--- /dev/null
+++ b/2021/day-06/day-06.ex
@@ -0,0 +1,35 @@
+defmodule Day06 do
+ def next_day(state) do
+ with one_day_older <- Enum.into(state, %{}, fn {k, v} -> {k - 1, v} end),
+ {n, s} <- Map.pop(one_day_older, -1, 0) do
+ Map.update(s, 6, n, &(&1 + n))
+ |> Map.put(8, n)
+ end
+ end
+end
+
+school =
+ with {:ok, data} <- File.read("input.txt") do
+ data
+ |> String.trim()
+ |> String.split(",")
+ |> Enum.map(&String.to_integer/1)
+ end
+
+starting_state = Enum.frequencies(school)
+
+Enum.reduce(
+ Enum.to_list(1..80),
+ starting_state,
+ fn _, acc -> Day06.next_day(acc) end
+)
+|> Enum.reduce(0, fn {_, v}, acc -> v + acc end)
+|> IO.inspect()
+
+Enum.reduce(
+ Enum.to_list(1..256),
+ starting_state,
+ fn _, acc -> Day06.next_day(acc) end
+)
+|> Enum.reduce(0, fn {_, v}, acc -> v + acc end)
+|> IO.inspect()
diff --git a/2021/day-06/day-06.livemd b/2021/day-06/day-06.livemd
new file mode 100644
index 0000000..87224e9
--- /dev/null
+++ b/2021/day-06/day-06.livemd
@@ -0,0 +1,151 @@
+<!-- livebook:{"persist_outputs":true} -->
+
+# Advent of Code 2021, Day 6
+
+## Short problem summary
+
+A school of fish reproduce according to the following rules:
+
+* Every fish has an "internal timer"
+* The timer decrements by one every day
+* If the timer is at 0, the timer is instead reset to 6,
+ and a new fish with an internal timer of 8 is added to the school
+
+Questions:
+
+1. How many fish are in the school after 80 days?
+2. How many fish are in the school after 256 days?
+
+## Setting up
+
+The initial input is a list of fish, represented by the initial value of their internal timer:
+
+```elixir
+school =
+ with {:ok, data} <- File.read("day-06/input.txt") do
+ data
+ |> String.trim()
+ |> String.split(",")
+ |> Enum.map(&String.to_integer/1)
+ end
+```
+
+```output
+[5, 4, 3, 5, 1, 1, 2, 1, 2, 1, 3, 2, 3, 4, 5, 1, 2, 4, 3, 2, 5, 1, 4, 2, 1, 1, 2, 5, 4, 4, 4, 1, 5,
+ 4, 5, 2, 1, 2, 5, 5, 4, 1, 3, 1, 4, 2, 4, 2, 5, 1, ...]
+```
+
+Every fish with the same starting internal timer will reproduce at the same time,
+as will all of the children of those fish and their children, and so forth,
+so we don't need to track individual fish; we just need to group the fish based on
+their starting internal timer and track those groups throughout the simulation.
+
+```elixir
+starting_state = Enum.frequencies(school)
+```
+
+```output
+%{1 => 88, 2 => 45, 3 => 54, 4 => 52, 5 => 61}
+```
+
+Every time a day passes, the following things happen:
+
+* All the internal timers decrement by 1
+* The group of fish with an internal timer of -1 is reset to 6
+ (added to any existing fish whose timers are already at 6),
+ and an equal-sized group of fish with internal timer 8 is added
+
+```elixir
+defmodule Day06 do
+ def next_day(state) do
+ with one_day_older <- Enum.into(state, %{}, fn {k, v} -> {k - 1, v} end),
+ {n, s} <- Map.pop(one_day_older, -1, 0) do
+ Map.update(s, 6, n, &(&1 + n))
+ |> Map.put(8, n)
+ end
+ end
+end
+
+day1 = Day06.next_day(starting_state)
+```
+
+```output
+%{0 => 88, 1 => 45, 2 => 54, 3 => 52, 4 => 61, 6 => 0, 8 => 0}
+```
+
+After the first day there's not any fish old enough to reproduce yet, but after the second day,
+
+```elixir
+day2 = Day06.next_day(day1)
+```
+
+```output
+%{0 => 45, 1 => 54, 2 => 52, 3 => 61, 5 => 0, 6 => 88, 7 => 0, 8 => 88}
+```
+
+The 88 fish whose timers were at 0 have rolled over to 6 and created 88 more fish with timers at 8.
+
+## Solution
+
+Now we just need to apply the transformation function the necessary number
+of times and sum up the total population in the end:
+
+```elixir
+part1_state =
+ Enum.reduce(
+ Enum.to_list(1..80),
+ starting_state,
+ fn _, acc -> Day06.next_day(acc) end
+ )
+ |> IO.inspect()
+ |> Enum.reduce(0, fn {_, v}, acc -> v + acc end)
+```
+
+```output
+%{
+ 0 => 24572,
+ 1 => 43660,
+ 2 => 30525,
+ 3 => 48458,
+ 4 => 41318,
+ 5 => 47697,
+ 6 => 57731,
+ 7 => 23218,
+ 8 => 33738
+}
+```
+
+```output
+350917
+```
+
+Identically for part 2,
+
+```elixir
+part2_state =
+ Enum.reduce(
+ Enum.to_list(1..256),
+ starting_state,
+ fn _, acc -> Day06.next_day(acc) end
+ )
+ |> IO.inspect()
+ |> Enum.reduce(0, fn {_, v}, acc -> v + acc end)
+```
+
+```output
+%{
+ 0 => 139170477178,
+ 1 => 162618979933,
+ 2 => 169389497028,
+ 3 => 188231720546,
+ 4 => 207908029672,
+ 5 => 217769615201,
+ 6 => 252681772250,
+ 7 => 117023886952,
+ 8 => 138124736869
+}
+```
+
+```output
+1592918715629
+```
diff --git a/2021/day-06/day-06.rkt b/2021/day-06/day-06.rkt
new file mode 100644
index 0000000..f687db9
--- /dev/null
+++ b/2021/day-06/day-06.rkt
@@ -0,0 +1,33 @@
+#lang racket
+(require advent-of-code
+ awesome-list
+ threading
+ racket/hash)
+
+(define fish-data
+ (~> (open-aoc-input (find-session) 2021 6 #:cache (string->path "./cache"))
+ port->string
+ string-trim
+ (string-split ",")
+ (map string->number _)))
+
+(define (simulate-fish time-period)
+ (for/fold ([state (frequencies fish-data)]
+ #:result (~> state
+ hash-values
+ (apply + _)))
+ ([day (inclusive-range 1 time-period)])
+ (define day-older-fish
+ (for/hash ([(days pop) (in-hash state)])
+ (values (sub1 days) pop)))
+ (define breeding-fish
+ (hash-ref day-older-fish -1 0))
+ (hash-union (hash-remove day-older-fish -1)
+ (hash 8 breeding-fish 6 breeding-fish)
+ #:combine +)))
+
+;; part 1
+(simulate-fish 80)
+
+;; part 2
+(simulate-fish 256) \ No newline at end of file
diff --git a/2021/day-06/input.txt b/2021/day-06/input.txt
new file mode 100644
index 0000000..ba3c3cc
--- /dev/null
+++ b/2021/day-06/input.txt
@@ -0,0 +1 @@
+5,4,3,5,1,1,2,1,2,1,3,2,3,4,5,1,2,4,3,2,5,1,4,2,1,1,2,5,4,4,4,1,5,4,5,2,1,2,5,5,4,1,3,1,4,2,4,2,5,1,3,5,3,2,3,1,1,4,5,2,4,3,1,5,5,1,3,1,3,2,2,4,1,3,4,3,3,4,1,3,4,3,4,5,2,1,1,1,4,5,5,1,1,3,2,4,1,2,2,2,4,1,2,5,5,1,4,5,2,4,2,1,5,4,1,3,4,1,2,3,1,5,1,3,4,5,4,1,4,3,3,3,5,5,1,1,5,1,5,5,1,5,2,1,5,1,2,3,5,5,1,3,3,1,5,3,4,3,4,3,2,5,2,1,2,5,1,1,1,1,5,1,1,4,3,3,5,1,1,1,4,4,1,3,3,5,5,4,3,2,1,2,2,3,4,1,5,4,3,1,1,5,1,4,2,3,2,2,3,4,1,3,4,1,4,3,4,3,1,3,3,1,1,4,1,1,1,4,5,3,1,1,2,5,2,5,1,5,3,3,1,3,5,5,1,5,4,3,1,5,1,1,5,5,1,1,2,5,5,5,1,1,3,2,2,3,4,5,5,2,5,4,2,1,5,1,4,4,5,4,4,1,2,1,1,2,3,5,5,1,3,1,4,2,3,3,1,4,1,1
diff --git a/2021/day-07/day-07.rkt b/2021/day-07/day-07.rkt
new file mode 100644
index 0000000..81a2e4f
--- /dev/null
+++ b/2021/day-07/day-07.rkt
@@ -0,0 +1,30 @@
+#lang racket
+(require advent-of-code
+ threading
+ math/statistics)
+
+(define crab-data
+ (~> (open-aoc-input (find-session) 2021 7 #:cache #t)
+ port->string
+ string-trim
+ (string-split ",")
+ (map string->number _)))
+
+(define (gauss-sum n) (/ (* n (+ n 1)) 2))
+(define (compute-fuel-use f crabs align-to)
+ (for/sum ([crab (in-list crabs)])
+ (f (abs (- crab align-to)))))
+
+;; using the fact that the optimum location is at the median
+;; of the crabs' starting location for the linear relationship
+;; and at a coordinate within 1 unit of the mean for the quadratic one
+
+(~>> crab-data
+ (median <)
+ (compute-fuel-use identity crab-data))
+
+(~>> crab-data
+ mean
+ ((λ (m) (list (floor m) (ceiling m))))
+ (map (curry compute-fuel-use gauss-sum crab-data))
+ (apply min)) \ No newline at end of file
diff --git a/2021/day-08/day-08.rkt b/2021/day-08/day-08.rkt
new file mode 100644
index 0000000..ff54817
--- /dev/null
+++ b/2021/day-08/day-08.rkt
@@ -0,0 +1,83 @@
+#lang racket
+(require threading
+ awesome-list
+ "../../jj-aoc.rkt")
+
+(struct trial-data (signal output) #:transparent)
+
+(define (string->sets s)
+ (~> s
+ string-split
+ (map (λ~> string->list
+ list->set) _)))
+
+(define data
+ (for/list ([l (in-lines (open-day 8))]
+ #:unless (equal? l ""))
+ (~> l
+ (string-split _ " | ")
+ (map string->sets _)
+ (apply trial-data _))))
+
+;; part 1
+(for*/sum ([trial (in-list data)]
+ [output (in-list (trial-data-output trial))]
+ #:when (ormap (λ~> (= (set-count output))) '(2 3 4 7)))
+ 1)
+
+;; part 2
+(define (matching-pattern len trial)
+ (define solution-set
+ (for*/list ([signal (in-list (trial-data-signal trial))]
+ #:when (= (set-count signal) len))
+ signal))
+ (match solution-set
+ [(list s) s]
+ [s (apply set-intersect s)]))
+
+(define (determine-arrangement t)
+ (let*
+ ([pattern-1 (matching-pattern 2 t)]
+ [pattern-4 (matching-pattern 4 t)]
+ [pattern-7 (matching-pattern 3 t)]
+ [pattern-8 (matching-pattern 7 t)]
+ [pattern-shared-235 (matching-pattern 5 t)]
+ [pattern-3 (set-union pattern-1
+ pattern-shared-235)]
+ [pattern-9 (set-union pattern-4
+ pattern-shared-235)]
+ [pattern-shared-069 (matching-pattern 6 t)]
+ [pattern-just-f (set-subtract pattern-shared-069 pattern-shared-235)]
+ [pattern-just-e (set-subtract pattern-8
+ (set-union pattern-4
+ pattern-shared-235
+ pattern-shared-069))]
+ [pattern-2 (set-union (set-subtract pattern-3 pattern-just-f)
+ pattern-just-e)]
+ [pattern-just-c (set-subtract (set-intersect pattern-4 pattern-7)
+ pattern-just-f)]
+ [pattern-6 (set-subtract pattern-8 pattern-just-c)]
+ [pattern-5 (set-subtract pattern-6 pattern-just-e)]
+ [pattern-0 (set-union (set-subtract pattern-8
+ pattern-shared-235)
+ pattern-shared-069)]
+ )
+ (~> (list pattern-0
+ pattern-1
+ pattern-2
+ pattern-3
+ pattern-4
+ pattern-5
+ pattern-6
+ pattern-7
+ pattern-8
+ pattern-9)
+ enumerate
+ make-hash)))
+
+(for/sum ([trial (in-list data)])
+ (~>> trial
+ trial-data-output
+ (map (λ~>> (hash-ref (determine-arrangement trial))))
+ (apply ~a)
+ string->number))
diff --git a/2021/day-09/day-09.bak b/2021/day-09/day-09.bak
new file mode 100644
index 0000000..11ef8e6
--- /dev/null
+++ b/2021/day-09/day-09.bak
@@ -0,0 +1,60 @@
+#lang racket
+
+(require threading
+ "../jj-aoc.rkt")
+
+(define data
+ (for/vector ([l (in-lines (open-day 9))]
+ #:unless (equal? l ""))
+ (~>> l
+ string->list
+ (map (λ~>> ~a string->number))
+ list->vector)))
+
+(define max-rows (vector-length data))
+(define max-cols (vector-length (vector-ref data 0)))
+(define-values (min-rows min-cols) (values 0 0))
+
+(define (vector2d-ref vec coord)
+ (match-define `(,r ,c) coord)
+ (~> vec
+ (vector-ref r)
+ (vector-ref c)))
+
+(define (adjacent coords)
+ (match-define `(,r ,c) coords)
+ `((,(add1 r) ,c)
+ (,(sub1 r) ,c)
+ (,r ,(add1 c))
+ (,r ,(sub1 c))))
+
+(define (valid-coordinate coord)
+ (match-define `(,r ,c) coord)
+ (and (>= r min-rows)
+ (< r max-rows)
+ (>= c min-cols)
+ (< c max-cols)))
+
+(define (check-adjacent vec coord)
+ (define x (vector2d-ref vec coord))
+ (for*/and ([neighbor (in-list (adjacent coord))]
+ #:when (valid-coordinate neighbor))
+ (x . < . (vector2d-ref vec neighbor))))
+
+;; part 1
+(for*/sum ([r (in-range min-rows max-rows)]
+ [c (in-range min-cols max-cols)]
+ [x (in-value (vector2d-ref data `(,r ,c)))]
+ #:when (check-adjacent data `(,r ,c)))
+ (add1 x))
+
+;; part 2
+(define visited (make-hash))
+(define (flood-fill vec coord)
+ (if (and (< (vector2d-ref vec coord) 9)
+ (not (hash-has-key? visited coord)))
+ ((hash-set! visited coord 'visited)
+ (add1 (for/sum [(neighbor (in-list (adjacent coord)))
+ #:when (valid-coordinate neighbor)]
+ (flood-fill vec neighbor))))
+ 0)) \ No newline at end of file
diff --git a/2021/day-09/day-09.livemd b/2021/day-09/day-09.livemd
new file mode 100644
index 0000000..3b984a5
--- /dev/null
+++ b/2021/day-09/day-09.livemd
@@ -0,0 +1,138 @@
+<!-- vim: set syntax=markdown: -->
+<!-- livebook:{"persist_outputs":true} -->
+
+# Advent of Code 2021, Day 9
+
+## Short problem summary
+
+
+
+**Part 1.** Find the total "risk level" of all the local minima on a relief map, represented by a
+100 $\times$ 100 array of integers from 1 to 9. Only orthogonal neighbors count.
+The risk level is the elevation plus one.
+
+**Part 2.** Find the product of the areas of the three largest basins on the relief map. Basins are regions
+bordered by the edges of the map or by points with elevation 9.
+Again, only orthogonal neighbors count.
+
+## Setup
+
+I'm using [Nx](https://github.com/elixir-nx/nx/tree/main/nx#readme) tensors
+since this problem will require a lot of arbitrary indexing.
+
+```elixir
+Mix.install([
+ {:nx, "~> 0.1.0-dev", github: "elixir-nx/nx", sparse: "nx", override: true}
+])
+```
+
+```output
+:ok
+```
+
+Bringing in the data as a new 2D tensor:
+
+```elixir
+floor =
+ with {:ok, data} <- File.read("input.txt") do
+ data
+ |> String.trim()
+ |> String.split("\n")
+ |> Enum.flat_map(&String.graphemes/1)
+ |> Enum.map(&String.to_integer/1)
+ |> Enum.chunk_every(100)
+ |> Nx.tensor(names: [:y, :x])
+ end
+```
+
+```output
+#Nx.Tensor<
+ s64[y: 100][x: 100]
+ [
+ [7, 6, 5, 9, 9, 9, 1, 0, 9, 8, 9, 9, 9, 8, 7, 6, 5, 7, 9, 9, 1, 0, 1, 2, 9, 8, 7, 9, 9, 9, 9, 8, 7, 6, 4, 3, 2, 1, 2, 3, 4, 5, 9, 8, 7, 4, 3, 4, 5, 5, ...],
+ ...
+ ]
+>
+```
+
+## Part 1
+
+For a given coordinate $(x, y)$, we want to examine its orthogonal neighbors,
+but only the ones that exist within the map.
+
+```elixir
+defmodule Day09.Part1 do
+ def neighbors({x, y}) do
+ [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}]
+ |> Enum.filter(fn {x, y} -> x >= 0 && x < 100 && y >= 0 && y < 100 end)
+ end
+end
+```
+
+```output
+{:module, Day09.Part1, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:neighbors, 1}}
+```
+
+Now scan the whole array to check each cell's neighbors,
+and return the "risk level" for each local minimum, then accumulate the sum.
+
+```elixir
+risk_level =
+ for x <- 0..99,
+ y <- 0..99,
+ reduce: 0 do
+ acc ->
+ Day09.Part1.neighbors({x, y})
+ |> Enum.all?(fn {xn, yn} -> floor[x][y] < floor[xn][yn] end)
+ |> if(do: acc + Nx.to_number(floor[x][y]) + 1, else: acc)
+ end
+```
+
+```output
+591
+```
+
+## Part 2
+
+Now we need to recursively walk outwards from each previously-unwalked point
+until we can't walk any further. An agent will keep track of the visited points.
+
+```elixir
+defmodule Day09.Part2 do
+ def walkable?({x, y} = coords, tensor, pid) do
+ Nx.to_number(tensor[x][y]) < 9 && not Agent.get(pid, fn m -> Map.has_key?(m, coords) end)
+ end
+
+ def walk_it(coords, tensor, pid) do
+ if walkable?(coords, tensor, pid) do
+ Agent.update(pid, fn m -> Map.put(m, coords, true) end)
+
+ for c <- Day09.Part1.neighbors(coords) do
+ walk_it(c, tensor, pid)
+ end
+ |> Enum.reduce(1, fn x, acc -> acc + x end)
+ else
+ 0
+ end
+ end
+end
+```
+
+```output
+{:module, Day09.Part2, <<70, 79, 82, 49, 0, 0, 11, ...>>, {:walk_it, 3}}
+```
+
+```elixir
+{:ok, tracker} = Agent.start_link(fn -> %{} end)
+
+for x <- 0..99, y <- 0..99 do
+ Day09.Part2.walk_it({x, y}, floor, tracker)
+end
+|> Enum.sort(:desc)
+|> Enum.take(3)
+|> Enum.reduce(fn x, acc -> acc * x end)
+```
+
+```output
+1113424
+```
diff --git a/2021/day-09/day-09.rkt b/2021/day-09/day-09.rkt
new file mode 100644
index 0000000..7c55d43
--- /dev/null
+++ b/2021/day-09/day-09.rkt
@@ -0,0 +1,78 @@
+#lang racket
+
+(require threading
+ "../../jj-aoc.rkt")
+
+(define sea-floor-data
+ (for/vector ([l (in-lines (open-day 9))]
+ #:unless (equal? l ""))
+ (~>> l
+ string->list
+ (map (λ~>> ~a string->number))
+ list->vector)))
+
+(define max-rows (vector-length sea-floor-data))
+(define max-cols (vector-length (vector-ref sea-floor-data 0)))
+(define-values (min-rows min-cols) (values 0 0))
+
+(define (vector2d-ref vec coord)
+ (match-define `(,r ,c) coord)
+ (~> vec
+ (vector-ref r)
+ (vector-ref c)))
+
+(define (adjacent coords)
+ (match-define `(,r ,c) coords)
+ `((,(add1 r) ,c)
+ (,(sub1 r) ,c)
+ (,r ,(add1 c))
+ (,r ,(sub1 c))))
+
+(define (valid-coordinate coord)
+ (match-define `(,r ,c) coord)
+ (and (>= r min-rows)
+ (< r max-rows)
+ (>= c min-cols)
+ (< c max-cols)))
+
+;; part 1
+(define (lowest-point? vec coord)
+ (for*/and ([neighbor (in-list (adjacent coord))]
+ #:when (valid-coordinate neighbor))
+ (< (vector2d-ref vec coord) (vector2d-ref vec neighbor))))
+
+(for*/sum ([r (in-range min-rows max-rows)]
+ [c (in-range min-cols max-cols)]
+ [coord (in-value `(,r ,c))]
+ #:when (lowest-point? sea-floor-data coord))
+ (add1 (vector2d-ref sea-floor-data coord)))
+
+;; part 2
+;; all the basins are bordered by the edges or by ridges of elevation 9,
+;; so it's not really necessary to start at a low point
+(define walked (make-hash))
+
+(define (walkable? vec coord)
+ (and (< (vector2d-ref vec coord) 9)
+ (not (hash-has-key? walked coord))))
+
+(define (walk-the-basin vec coord)
+ (cond
+ [(walkable? vec coord)
+ (hash-set! walked coord 'visited)
+ (add1 (for/sum [(neighbor (in-list (adjacent coord)))
+ #:when (valid-coordinate neighbor)]
+ (walk-the-basin vec neighbor)))]
+ [else 0]))
+
+(define basins
+ (for*/list ([r (in-range min-rows max-rows)]
+ [c (in-range min-cols max-cols)]
+ [coord (in-value `(,r ,c))]
+ #:when (walkable? sea-floor-data coord))
+ (walk-the-basin sea-floor-data coord)))
+
+(~> basins
+ (sort >)
+ (take 3)
+ (apply * _)) \ No newline at end of file
diff --git a/2021/day-09/input.txt b/2021/day-09/input.txt
new file mode 100644
index 0000000..322b31f
--- /dev/null
+++ b/2021/day-09/input.txt
@@ -0,0 +1,100 @@
+7659991098999876579910129879999876432123459874345567890126678999876588975767899323456989767899432101
+8998789987898765467891239868899876541012398765123456789234567897643467894656798912399878948678944212
+9867678976789878598954398756789997632343459873234569898765679999856578943547987893989865434567894323
+7654567895896989679767499847994398755456579987656778969876892198767989652129876889876976725678965734
+8767678954345698799898987659943219876577694598787889545987931019879996543298965679965987438789876799
+9898789921239799898989899798794399987688965679898993534598942123989987654987654567894596549899989987
+4969999892398989987876789987689989998789898789979992123989653934598798965976543678943987678999999876
+3459898789497878976545678986567878999895679898768989239879869896789659879865432469432198799998789765
+2498765699976567995434389765434567899934989977655679356965998789896545989865321258921019999987678954
+3987654398765456789321238979325456799329898766434798999876797698987432198754310347894329789876567893
+4696543219876967998910147998214345678998789954323987689999977567898543479885541456789498678988678932
+5987654423987878987521236987601234567891678893219876567898765479987654567976632367899987569899789321
+6798767834698989997432345698524568698932456789398765466989876567898765689987545478959768456789893210
+7899898945679499876545656997434578799843569892987654345678989679999876799798658569349654367878964322
+8977999498789398987896769876545689998767678931999869656789698789999987987698767895498743212567895433
+9656789329898987899929879987676790199898989949877998767896559899878998977569978999987654323458986654
+8797995434987896989434989798989891987919499896765569888921434998767789865452989998998795434569997765
+9979899549876785678945995639698999876329398764354456999990125899545678954321299987899987895678949878
+9865678998765434567899894324567892985498999863212347898989436798434599876210389996789999998789434999
+7654567899896647978989789212459921296987899954393478987678945987324879965341567895679891019998959865
+8543878901987656789765678901268933459876999895989569658567959876412568897432467894599789923987898654
+9212389919898767897654577892999545998765798789878978945456899954323456789576578923989679899876789543
+9543457898769879986543456789889959876543987676567899432345789976436567897697989219878565678965678932
+8754568987654989765432347898767899989432976543456964321012498987545679998989892109867434699764567891
+9867689298543299986541034987656789998743989654677895632134987898696789989878789298754324789543488989
+1978792129654569987732129874543567897654799965789976853239876799989999878765678999865455697601245678
+0989893098765678998653298763212375789795679878994989966398754889879898765464569899976566789212346789
+9898954239987789998784987654301234699989789989873398765459765678968789884323456789987677894323456898
+8777895345698999899895698976214345789878999997762129876589896789345678965434567999898989976564568967
+7656976457899019767987899765423456789569899876543299987678987891234569876545898998769394987875679456
+6546899568992198657898939878534677893456789987654989898789398932347678999856789889843212398986989345
+5435688979879932545679929989665788902569991298779878789899299543458789798767895678932101569997890123
+4323567899767891434589898998776899543457899999898768655978987654569899679878934569643219878998921254
+6764579987658910123456797879887899656568978789987653234567998785678998532989545678954399989999432765
+7875689998767891234567896569998998967989767698798767145678999896789987643498756789765989992987543876
+8976796899878932545678997998769467899899854599659898657789985959897898784569867899876978931098954987
+9697895799989873467889989999652348999799965678943939768999664543956789895679878979989867892129895698
+4598954569899964578999878987643499997689978789432129879998543212345678976989989459899756789298789789
+3499543798798765699998767898984987843579899996583235989987632105468789987899992398789898999987678991
+4985432987679876789999658989876986532498798889874346798798743236589893498989891987678989459986568990
+9876521296567987899876545878989875421987656778965498987669654587679999999876789898547678998765456789
+9876432987678998998765434569998767410996545567896569896556965689789987898865676789435589765432369999
+3987543498799549769886325679987654329877434456789698789439879789899976987764545678923459879321287899
+4599656789989432458997212568999769498764321298999987688956989897999899876743236789212398998932456998
+9798767897678921367989323459998998999875210147899876567897891956789798765432145794301987897893569997
+8999878996569432349876534569987687898654321236789767456789932345679659976545012689419876896789878986
+7899989987458943499998765678976546789985434545678954345679543567789545987983234568998765645678989565
+6789199654347896589989876789987434579876545758789543237789654579895434499874356789329874234567893434
+5679298789756789678976987899874323459987859767899654345678965989965421298765667895499932125689932123
+4568999898969898789765698998765212398498869878998765656789879898965432399876878976987891034567894034
+3456789987898999899894329987654323987349978989999898767896999797896743987987899989896789123678985125
+2346899876767892999989212398765499876567989999899959878934987676989659876798945698765695434679876789
+1256998765458993498979903459876989987698999999789943989949898455678998765759899987654989545689989899
+4349879876569989986567894967989878999789989897678892099898789334569987674545678998743478957897696999
+5478968987678979765456999898998767879899876789546789298788699212989876543234567998932569768998565678
+6568956998789569876567897789999857867998975695437995987657598909898995432123459886521678989895434567
+7678939879892458987678956699896645456987764789567894696543467898767986321019598765432789496789323878
+8789998765901456798789545598775435349876543999698943495432356789656997432198969876547892345689439989
+9895987654312345789899434459654324234987875898789212989321234896549876545997656989856921234579998997
+6954398767433566789998921398743210125698986789894309878540145789432997859876543398767890123467897686
+5695999876544678998787892987654341234589987895999498765431236894320989767987432129898921294878987575
+4989899987698789987656789398765492395678998934998989896549898965999878979876421012969939989999098464
+2976789998789899876543789249876989989989239019887678987656789879878767898985432123457898679889198323
+9895678999894968987654590123989879978990129198764569998987894998765459987899543434568987546778987634
+8654547899923656798985891294598768969893298998765678999598912349821398795698976546699876435569876545
+6543336789012349899876789989987656756789987899976789989499909496543989654567898687987665523456987676
+7652125978923598987987899878996541234567896569899899978987898987859878965678998789876563212345698787
+6543234567894987876798998769876532345978943456799998767896987598998969898799989898765432101234569898
+7685346878999876765689987655989645567899212566778987658965398459987856789899978999876543212385789999
+8876798989998765434569976743498756789956401234568998789876999349876546899988769899987654525678999999
+9987899697989954323798765632359867899543212345679239899989899956997635789879656789999769434789898989
+4599996546567893212987654321235978998764637566989139999998789899986523998967545698999898945699787678
+3499989435457899433498765435348989689895547677891098988997655798765439897645634567899976896789676567
+2989978921345678994569876546757894578987678788992987677893234569898698765430125698999865689896543456
+9879868935458789989778987987868943989998989999789987566989123456989789876321234789997684578965432123
+8965657899599999878989998999979659899879596545678976435778934569879894987432545679876543467896673294
+7654545698989997569999999998989799789965432434789897324567895979964933498545789789987432456998784989
+6543234987978965478999899987899987656974321023498788212379976798763212379676899899997544567899999878
+5432129876568896567898789656789976549875432164589654323568987987654343456987895978999655778956798967
+4321019987456789678987698943495987678987543765678965454569998998765454567898954567898776789345987954
+5432998765345698989996587992976798789798765897789876875678999869876569878979943459979987893212986543
+6549879876234767899985456789897899997659897899897987996789998754997878989767892598965398994323497632
+7698765438123456789876323496789992198943998943956998987899987643298989997656999987890139989434598745
+8899954321014567899865212345678989989894989012345899498989998759109499998747988976789239878965987656
+9998765732125678999954345489789679878789876543456789349678939998912349876434567895678949867896798767
+4349876653346789998769497679898998765699998754678991234569019887893498765325658934589998758659999878
+4239999778659899899898989989967987854897899869789893965678998766799987654312349898699896549237899989
+9398999889767998789987978995459876543786789878898789896799987655678998895401256789798765432126789997
+8987899999879987678976567894398765432645699989997678789929876543767899986212868999899654321034599896
+7856789432989876569875456894298764321237989899986565678910987432347678997343479756998789532123456789
+6545678921098765454986587932129879854349876799867434568924596541234599987654569545689898743454567895
+5436889932129854323697698943234988765698765987654523567895987762345789598968678934578999654765678954
+4321968894298765634598789954445699878987654599763212348997898943579893459899789545678998765878789875
+5872456789349878745679897895768789989877653459894103456789999874568932598789897676789129878989899986
+8763878995467989856789976979879899998765432345989294567899899865679943987699998989899234989299999899
+7654567896568995977891234568999978919876521239878989678956756978989894976568999195978976790199899788
+8765698987878923988910123456789567923987432399765679789432347989998769876456789234567897892988698677
+9878789498999219899321256587995456894898643989813478997643458994987656987567894345679998999876545556
+2989893219879998765432347898932345995798759876524567899856969543499897897698987457989899298765434345
+1099954523467899876545456999545476789899899976435788923987897652101998998789876567897654349854321237
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-23 20:29:32 +0000