diff options
author | J.J <thechairman@thechairman.info> | 2023-11-30 17:10:00 -0500 |
---|---|---|
committer | J.J <thechairman@thechairman.info> | 2023-11-30 17:10:00 -0500 |
commit | 8ab65dc2da1742eb86ec636c50c7018385b68167 (patch) | |
tree | c4fd556aca9b867cfa1f2f174128c30857353884 /2021 | |
parent | fafbeaf9e3c09ba7a5bea7e47d5736001f8a5aa1 (diff) | |
download | gleam_aoc-8ab65dc2da1742eb86ec636c50c7018385b68167.tar.gz gleam_aoc-8ab65dc2da1742eb86ec636c50c7018385b68167.zip |
prep for 2023, renaming for consistency
Diffstat (limited to '2021')
32 files changed, 0 insertions, 2001 deletions
diff --git a/2021/day-01/day-01.pl b/2021/day-01/day-01.pl deleted file mode 100644 index d3c3fa7..0000000 --- a/2021/day-01/day-01.pl +++ /dev/null @@ -1,20 +0,0 @@ -:- 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 deleted file mode 100644 index 48ef158..0000000 --- a/2021/day-01/day-01.rkt +++ /dev/null @@ -1,20 +0,0 @@ -#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 deleted file mode 100644 index d37ab05..0000000 --- a/2021/day-02/day-02.ex +++ /dev/null @@ -1,32 +0,0 @@ -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 deleted file mode 100644 index 0bd0c3d..0000000 --- a/2021/day-02/day-02.rkt +++ /dev/null @@ -1,24 +0,0 @@ -#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)])) diff --git a/2021/day-03/day-03.rkt b/2021/day-03/day-03.rkt deleted file mode 100644 index 95b7efd..0000000 --- a/2021/day-03/day-03.rkt +++ /dev/null @@ -1,39 +0,0 @@ -#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 deleted file mode 100644 index c572f74..0000000 --- a/2021/day-04/day-04.rkt +++ /dev/null @@ -1,51 +0,0 @@ -#lang racket -(require advent-of-code - threading - (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 (apply map list 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) diff --git a/2021/day-05/day-05.rkt b/2021/day-05/day-05.rkt deleted file mode 100644 index e568490..0000000 --- a/2021/day-05/day-05.rkt +++ /dev/null @@ -1,57 +0,0 @@ -#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 deleted file mode 100644 index efe10e4..0000000 --- a/2021/day-06/day-06.ex +++ /dev/null @@ -1,35 +0,0 @@ -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 deleted file mode 100644 index 5ab794f..0000000 --- a/2021/day-06/day-06.livemd +++ /dev/null @@ -1,152 +0,0 @@ -<!-- vim: set syntax=markdown: --> -<!-- 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 deleted file mode 100644 index d8855ba..0000000 --- a/2021/day-06/day-06.rkt +++ /dev/null @@ -1,27 +0,0 @@ -#lang racket -(require advent-of-code - list-utils - 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) diff --git a/2021/day-06/input.txt b/2021/day-06/input.txt deleted file mode 100644 index ba3c3cc..0000000 --- a/2021/day-06/input.txt +++ /dev/null @@ -1 +0,0 @@ -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 deleted file mode 100644 index 89d5009..0000000 --- a/2021/day-07/day-07.rkt +++ /dev/null @@ -1,28 +0,0 @@ -#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)) diff --git a/2021/day-08/day-08.rkt b/2021/day-08/day-08.rkt deleted file mode 100644 index 6476eae..0000000 --- a/2021/day-08/day-08.rkt +++ /dev/null @@ -1,64 +0,0 @@ -#lang racket -(require threading - list-utils - "../../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.livemd b/2021/day-09/day-09.livemd deleted file mode 100644 index 3b984a5..0000000 --- a/2021/day-09/day-09.livemd +++ /dev/null @@ -1,138 +0,0 @@ -<!-- 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 deleted file mode 100644 index d550a9e..0000000 --- a/2021/day-09/day-09.rkt +++ /dev/null @@ -1,59 +0,0 @@ -#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 * _)) diff --git a/2021/day-09/input.txt b/2021/day-09/input.txt deleted file mode 100644 index 322b31f..0000000 --- a/2021/day-09/input.txt +++ /dev/null @@ -1,100 +0,0 @@ -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 diff --git a/2021/day-10/day-10.rkt b/2021/day-10/day-10.rkt deleted file mode 100644 index ea1b389..0000000 --- a/2021/day-10/day-10.rkt +++ /dev/null @@ -1,57 +0,0 @@ -#lang racket - -(require math/statistics - threading - "../../jj-aoc.rkt") - -(define chunks (port->lines (open-day 10 2021))) - -(define (opening-bracket? c) - (member c (string->list "([{<"))) - -(define (matching-brackets? c-left c-right) - (member (string c-left c-right) '("()" "[]" "{}" "<>"))) - -(define (parse-brackets lst [acc '()]) - (cond - [(empty? lst) acc] - [(opening-bracket? (first lst)) (parse-brackets (rest lst) (cons (first lst) acc))] - [(matching-brackets? (first acc) (first lst)) (parse-brackets (rest lst) (rest acc))] - [else (get-score (first lst))])) - -;; part 1 -(define (get-score c) - (match (string c) - [")" 3] - ["]" 57] - ["}" 1197] - [">" 25137])) - -(define (score-invalid-string chunk) - (match (parse-brackets (string->list chunk)) - [(? list?) 0] - [n n])) - -(for/sum ([chunk (in-list chunks)]) (score-invalid-string chunk)) - -;; part 2 -(define (completion-score lst) - (for/fold ([score 0]) ([c (in-list lst)]) - (define val - (match (string c) - ["(" 1] - ["[" 2] - ["{" 3] - ["<" 4])) - (+ (* 5 score) val))) - -(define (score-incomplete-string chunk) - (match (parse-brackets (string->list chunk)) - [(? list? lst) (completion-score lst)] - [n 0])) - -(~>> (for*/list ([chunk (in-list chunks)] - [score (in-value (score-incomplete-string chunk))] - #:when (> score 0)) - score) - (median <)) diff --git a/2021/day-11/day-11.rkt b/2021/day-11/day-11.rkt deleted file mode 100644 index bc22991..0000000 --- a/2021/day-11/day-11.rkt +++ /dev/null @@ -1,56 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading) - -(define coords - (~>> (for/list ([r (in-range 10)]) - (for/list ([c (in-range 10)]) - (cons r c))) - (apply append))) - -(define octopus-data - (~>> (for/list ([l (in-lines (open-day 11 2021))] #:unless (equal? l "")) - (~>> l string->list (map (λ~>> ~a string->number)))) - (apply append) - (map cons coords) - make-hash)) - -(define total-length (hash-count octopus-data)) -(define row-length (sqrt total-length)) - -(define (adjacent-to coord) - (match-define (cons r c) coord) - (for*/list ([row (in-list '(-1 0 1))] [col (in-list '(-1 0 1))] #:unless (= 0 row col)) - (cons (+ r row) (+ c col)))) - -(define (simulate-octopi-step data) - (define flashed-this-step (mutable-set)) - - (let look-for-more-flashes ([octopi (for/hash ([(k v) data]) - (values k (add1 v)))] - [flashes-so-far 0]) - (define-values (next-octopus-update flashes-this-update) - (for*/fold ([octopi octopi] [flashes 0]) - ([(p x) (in-hash octopi)] #:when (> x 9) #:unless (set-member? flashed-this-step p)) - (set-add! flashed-this-step p) - (define flashed-octopi - (for*/fold ([o (hash-set octopi p 0)]) - ([adj (in-list (adjacent-to p))] - #:when (hash-has-key? o adj) - #:unless (set-member? flashed-this-step adj)) - (hash-update o adj add1))) - (values flashed-octopi (add1 flashes)))) - (if (> flashes-this-update 0) - (look-for-more-flashes next-octopus-update (+ flashes-so-far flashes-this-update)) - (values next-octopus-update flashes-so-far)))) - -;; part 1 -(for/fold ([octopi octopus-data] [total-flashes 0] #:result total-flashes) ([step (in-range 100)]) - (define-values [next-state flashes-from-this-state] (simulate-octopi-step octopi)) - (values next-state (+ total-flashes flashes-from-this-state))) - -;; part 2 -(for/fold ([octopi octopus-data] [synchro-step 0] #:result synchro-step) ([step (in-naturals 1)]) - (define-values [next-state flashes-from-this-state] (simulate-octopi-step octopi)) - #:final (= flashes-from-this-state 100) - (values next-state step)) diff --git a/2021/day-12/day-12.rkt b/2021/day-12/day-12.rkt deleted file mode 100644 index 18ed86f..0000000 --- a/2021/day-12/day-12.rkt +++ /dev/null @@ -1,38 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading) - -(define path-pairs - (for/list ([l (in-lines (open-day 12 2021))]) - (match (string-split l "-") - [(list start end) (cons start end)]))) - -(define edges-hash (make-hash)) - -(for ([pair (in-list path-pairs)]) - (match-define (cons start end) pair) - (hash-update! edges-hash start (curry cons end) '()) - (hash-update! edges-hash end (curry cons start) '())) - -;; part 1 -(define (backtracking-disallowed? next prevs) - (and (equal? (string-downcase next) next) (member next prevs))) - -(define (look-for-next-cave [path-list '("start")] #:only-one-visit? [visit-used-up? #t]) - (define current-cave (car path-list)) - (cond - [(equal? current-cave "end") (list path-list)] - [else - (~>> (for/list ([next-path (in-list (hash-ref edges-hash current-cave null))] - #:when (and (not (equal? next-path "start")) - (not (and (backtracking-disallowed? next-path path-list) - visit-used-up?)))) - (look-for-next-cave - (cons next-path path-list) - #:only-one-visit? (or (backtracking-disallowed? next-path path-list) visit-used-up?))) - (apply append))])) - -(~> (look-for-next-cave) length time) - -;; part 2 -(~> (look-for-next-cave #:only-one-visit? #f) length time) diff --git a/2021/day-13/day-13.rkt b/2021/day-13/day-13.rkt deleted file mode 100644 index 153eabc..0000000 --- a/2021/day-13/day-13.rkt +++ /dev/null @@ -1,57 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading) - -(define (make-pt x y) - (hash 'x x 'y y)) -(struct fold (dir loc) #:transparent) -(define (make-fold dir loc) - (fold (string->symbol dir) (string->number loc))) - -(define data (port->lines (open-day 13 2021))) -(define-values (points-list folds-list) (splitf-at data (λ~> (equal? "") not))) - -(define pts - (for/set ([pt (in-list points-list)]) - (~> pt (string-split ",") (map string->number _) (apply make-pt _)))) - -(define folds - (for/list ([f (in-list (rest folds-list))]) - (~>> f (regexp-match #px"fold along (.)=(.*)") rest (apply make-fold)))) - -(define (fold-over f pts) - (define dir (fold-dir f)) - (define loc (fold-loc f)) - (for/set ([pt (in-set pts)]) - (cond - [(> (hash-ref pt dir) loc) (hash-update pt dir (λ (l) (- (* 2 loc) l)))] - [else pt]))) - -;; part 1 -(~>> pts (fold-over (first folds)) set-count) - -;; part 2 -(define final-pts - (for/fold ([pt pts]) ([f (in-list folds)]) - (fold-over f pt))) - -(define (max-dim pts dim) - (~>> (for/list ([pt (in-set pts)]) - (hash-ref pt dim)) - (apply max))) - -(for ([y (in-inclusive-range 0 (max-dim final-pts 'y))]) - (~>> (for/list ([x (in-inclusive-range 0 (max-dim final-pts 'x))]) - (if (set-member? final-pts (hash 'x x 'y y)) #\█ #\space)) - (apply string) - println)) - -#| -for this data set, the result looks like -" ██ █ █ ██ ██ ███ ██ ██ █ █" -"█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █" -"█ █ ████ █ █ █ █ █ █ █ █ █" -"████ █ █ █ ██ █ ███ █ ██ ████ █ █" -"█ █ █ █ █ █ █ █ █ █ █ █ █ █ █" -"█ █ █ █ ███ ██ █ ███ █ █ ██ " -|# diff --git a/2021/day-14/day-14.rkt b/2021/day-14/day-14.rkt deleted file mode 100644 index e445694..0000000 --- a/2021/day-14/day-14.rkt +++ /dev/null @@ -1,61 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading - memoize - algorithms - list-utils) - -(define data (port->lines (open-day 14 2021))) - -(define (starting-polymer d) - (~> d first string->list (sliding 2 1))) - -(define (first-char d) - (first (first (starting-polymer d)))) - -(define (starting-counts d) - (~> d first frequencies hash->list make-hash)) - -(define (starting-pairs d) - (~>> d (drop _ 2) (map (λ~> (substring 0 2) string->list)))) - -(define (new-pairs d) - (~>> d - (drop _ 2) - (map (λ~> (string-replace " -> " "") - string->list - ((match-lambda - [(list a b c) (list a c b)]) - _) - (sliding 2 1))))) - -(define (transform d) - (~>> (map list (starting-pairs d) (new-pairs d)) (append*) (apply hash))) - -(define transformation (transform data)) - -(define/memo (get-count polymer times) - (match times - [0 - (for/fold ([counts (hash)]) ([pair (in-list polymer)]) - (hash-update counts (second pair) add1 0))] - [_ - (for*/fold ([counts (hash)]) - ([pair (in-list polymer)] - [(c n) (in-hash (get-count (hash-ref transformation pair) (sub1 times)))]) - (hash-update counts c (λ~> (+ n)) 0))])) - -;; part 1 -(define (process-polymer d n) - (~> d - starting-polymer - (get-count _ n) - (hash-update _ (first-char d) add1 0) - hash-values - (sort >) - ((λ (l) (- (first l) (last l)))))) - -(process-polymer data 10) - -;; part 2 -(process-polymer data 40) diff --git a/2021/day-15/day-15-list-nodes.rkt b/2021/day-15/day-15-list-nodes.rkt deleted file mode 100644 index 38c558a..0000000 --- a/2021/day-15/day-15-list-nodes.rkt +++ /dev/null @@ -1,67 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading - graph) - -(define data - (for/fold ([cells (hash)]) - ([row (in-lines (open-day 15 2021))] - [x (in-naturals)]) - (for/fold ([cells cells]) - ([n (in-string row)] - [y (in-naturals)]) - (hash-set cells - `(,x ,y) - (~> n string string->number))))) - -(define x-max (~>> data hash-keys (map first) (apply max))) -(define y-max (~>> data hash-keys (map second) (apply max))) - -(define (neighbors pt d) - (match-define (list x y) pt) - (~>> (list (list (add1 x) y) - (list (sub1 x) y) - (list x (add1 y)) - (list x (sub1 y))) - (filter (curry hash-has-key? d)))) - -(define (grid-graph d) - (weighted-graph/directed - (for*/list ([coord (in-list (hash-keys d))] - [neighbor (in-list (neighbors coord d))] - [weight (in-value (hash-ref d neighbor))]) - (list weight coord neighbor)))) - -;; part 1 -(define (find-path-weight d) - (define grid (grid-graph d)) - (let-values ([(node-distances _) (dijkstra grid '(0 0))]) - (define xm (~>> d hash-keys (map first) (apply max))) - (define ym (~>> d hash-keys (map second) (apply max))) - (hash-ref node-distances (list xm ym)))) - -(~> data - find-path-weight - time) - -;; part 2 -(define nine-cycle - (in-cycle (inclusive-range 1 9))) - -(define (expand-data data) - (for/fold ([cells (hash)]) - ([coord (in-list (hash-keys data))]) - (match-define (list x y) coord) - (for*/fold ([cells cells]) - ([n (in-range 5)] - [m (in-range 5)] - [val (in-value (hash-ref data coord))]) - (hash-set cells - (list (+ x (* n (add1 x-max))) - (+ y (* m (add1 y-max)))) - (sequence-ref nine-cycle (+ val n m -1)))))) - -(~> data - expand-data - find-path-weight - time)
\ No newline at end of file diff --git a/2021/day-15/day-15.livemd b/2021/day-15/day-15.livemd deleted file mode 100644 index 2495c32..0000000 --- a/2021/day-15/day-15.livemd +++ /dev/null @@ -1,287 +0,0 @@ -<!-- vim: set syntax=markdown: --> -<!-- livebook:{"persist_outputs":true} --> - -# Advent of Code 2021, Day 15 - -## Short summary - -**Parts 1 and 2.** Find the least "risky" path through a grid of nodes, -where each node has a "risk" cost to enter. Part 1's grid is the given data, -while Part 2's is the data after undergoing a transformation. -Only orthogonal travel is possible. - -## Setup - -Using the `libgraph` library to build the graph -and use its implementation of the Dijkstra algorithm: - -```elixir -Mix.install([ - {:libgraph, github: "bitwalker/libgraph"} -]) -``` - -```output -* Getting libgraph (https://github.com/bitwalker/libgraph.git) -remote: Enumerating objects: 783, done. -remote: Counting objects: 100% (64/64), done. -remote: Compressing objects: 100% (52/52), done. -remote: Total 783 (delta 27), reused 24 (delta 10), pack-reused 719 -origin/HEAD set to main -==> libgraph -Compiling 14 files (.ex) -Generated libgraph app -``` - -```output -:ok -``` - -```elixir -floor = - with {:ok, data} <- File.read("./2021/day-15/input") do - data - |> String.split() - |> Enum.map(fn xs -> - String.graphemes(xs) - |> Enum.map(&String.to_integer/1) - end) - end -``` - -```output -[ - [4, 5, 5, 2, 2, 8, 5, 9, 8, 9, 4, 4, 1, 1, 2, 4, 7, 1, 9, 7, 9, 8, 4, 6, 5, 8, 2, 5, 7, 7, 3, 3, - 1, 8, 2, 5, 2, 2, 6, 9, 4, 2, 2, 6, 2, 5, 7, 3, 1, ...], - [8, 3, 1, 1, 8, 2, 6, 9, 1, 7, 6, 7, 7, 2, 9, 5, 5, 6, 1, 3, 9, 5, 7, 1, 6, 2, 4, 5, 4, 2, 6, 1, - 8, 4, 2, 1, 2, 4, 7, 1, 3, 1, 1, 2, 1, 4, 8, 5, ...], - [3, 1, 3, 4, 1, 5, 5, 5, 2, 8, 2, 3, 1, 2, 9, 6, 3, 1, 3, 2, 9, 2, 9, 5, 1, 6, 8, 9, 3, 7, 1, 6, - 7, 1, 6, 1, 1, 3, 5, 5, 1, 9, 9, 4, 2, 9, 3, ...], - [7, 1, 3, 4, 1, 5, 9, 6, 8, 1, 5, 3, 3, 3, 3, 1, 1, 7, 2, 9, 9, 1, 9, 3, 2, 8, 1, 9, 1, 2, 8, 7, - 1, 8, 1, 3, 1, 1, 2, 1, 4, 2, 8, 7, 1, 5, ...], - [3, 2, 9, 1, 6, 2, 2, 1, 2, 1, 8, 9, 3, 8, 2, 1, 2, 5, 8, 2, 1, 5, 1, 1, 1, 5, 3, 1, 6, 1, 4, 2, - 3, 3, 9, 9, 9, 6, 6, 1, 6, 4, 9, 2, 7, ...], - [9, 1, 1, 6, 1, 9, 7, 3, 1, 9, 9, 9, 2, 2, 2, 3, 7, 8, 4, 9, 7, 3, 7, 4, 9, 1, 5, 9, 9, 1, 2, 9, - 1, 8, 9, 4, 8, 5, 1, 4, 8, 5, 5, 2, ...], - [4, 9, 6, 8, 4, 3, 9, 1, 1, 4, 1, 3, 5, 9, 9, 6, 9, 2, 3, 9, 3, 9, 6, 2, 1, 5, 2, 1, 2, 2, 7, 4, - 3, 8, 6, 1, 6, 4, 3, 2, 2, 6, 2, ...], - [6, 2, 3, 9, 2, 1, 9, 7, 8, 5, 2, 3, 4, 6, 7, 5, 3, 9, 1, 2, 8, 1, 6, 4, 1, 1, 1, 4, 1, 4, 8, 2, - 2, 5, 9, 4, 2, 6, 2, 2, 1, 9, ...], - [1, 9, 3, 9, 2, 7, 3, 1, 5, 2, 1, 1, 4, 1, 6, 5, 8, 1, 5, 6, 2, 1, 8, 9, 8, 1, 3, 1, 7, 4, 1, 6, - 2, 5, 1, 4, 2, 2, 7, 3, 7, ...], - [3, 8, 1, 6, 2, 9, 5, 1, 2, 1, 2, 1, 1, 7, 1, 3, 9, 1, 9, 9, 1, 8, 1, 2, 9, 1, 4, 1, 5, 2, 1, 7, - 4, 8, 3, 1, 5, 5, 7, 9, ...], - [2, 8, 5, 2, 1, 7, 4, 3, 9, 2, 1, 7, 5, 2, 1, 7, 8, 9, 1, 2, 9, 2, 7, 6, 9, 2, 9, 7, 3, 2, 9, 7, - 3, 4, 1, 4, 1, 5, 2, ...], - [8, 1, 8, 3, 4, 1, 1, 9, 8, 1, 1, 3, 6, 7, 1, 8, 4, 2, 8, 8, 2, 3, 1, 2, 7, 6, 8, 1, 4, 1, 1, 2, - 4, 6, 5, 2, 8, 2, ...], - [3, 3, 3, 8, 4, 1, 8, 9, 5, 8, 8, 1, 8, 2, 2, 9, 3, 3, 1, 3, 9, 9, 5, 1, 3, 6, 9, 1, 9, 2, 1, 9, - 2, 1, 8, 6, 9, ...], - [6, 1, 1, 8, 5, 8, 2, 7, 6, 5, 3, 7, 5, 5, 4, 1, 1, 4, 4, 4, 9, 1, 5, 1, 9, 8, 7, 1, 1, 2, 3, 1, - 2, 1, 1, 7, ...], - [1, 4, 6, 9, 2, 5, 7, 4, 1, 8, 3, 1, 3, 2, 1, 8, 9, 5, 1, 2, 1, 1, 5, 1, 1, 5, 9, 1, 2, 2, 4, 2, - 8, 1, 8, ...], - [1, 4, 2, 2, 1, 1, 8, 4, 1, 9, 3, 1, 9, 5, 1, 5, 4, 9, 6, 1, 8, 9, 3, 9, 1, 1, 5, 8, 5, 1, 6, 4, - 6, 2, ...], - [8, 1, 6, 2, 5, 4, 6, 1, 3, 9, 9, 5, 2, 1, 3, 6, 1, 8, 9, 9, 1, 1, 1, 7, 7, 5, 3, 3, 3, 5, 7, 8, - 2, ...], - [1, 4, 8, 8, 2, 3, 9, 6, 1, 1, 4, 6, 1, 4, 9, 1, 9, 7, 3, 8, 6, 5, 1, 8, 5, 2, 4, 2, 9, 5, 9, 5, - ...], - [2, 2, 1, 8, 9, 1, 7, 6, 6, 1, 8, 6, 8, 1, 3, 3, 1, 4, 1, 2, 4, 3, 8, 1, 9, 9, 6, 2, 4, 1, 3, ...], - [5, 7, 3, 4, 3, 2, 6, 7, 3, 2, 8, 8, 4, 7, 9, 2, 4, 2, 8, 1, 9, 1, 2, 4, 1, 1, 2, 1, 1, 9, ...], - [1, 5, 1, 1, 9, 3, 5, 1, 1, 1, 8, 6, 1, 1, 2, 1, 9, 3, 5, 7, 4, 1, 7, 6, 8, 3, 3, 8, 9, ...], - [9, 6, 9, 1, 5, 6, 2, 1, 8, 3, 5, 1, 3, 3, 8, 8, 2, 2, 1, 7, 2, 6, 4, 9, 3, 8, 2, 1, ...], - [2, 7, 2, 9, 2, 3, 7, 5, 3, 2, 9, 5, 9, 4, 4, 4, 7, 3, 3, 2, 2, 5, 4, 3, 5, 9, 9, ...], - [7, 3, 1, 2, 5, 5, 9, 1, 8, 1, 3, 2, 3, 7, 4, 3, 9, 3, 8, 2, 2, 1, 2, 1, 2, 2, ...], - [9, 4, 1, 5, 7, 4, 7, 7, 3, 8, 3, 4, 6, 1, 4, 1, 6, 9, 1, 4, 1, 8, 8, 2, 5, ...], - [1, 7, 1, 6, 2, 6, 3, 1, 2, 1, 1, 1, 5, 6, 3, 1, 1, 4, 1, 7, 8, 4, 2, 5, ...], - [2, 1, 1, 3, 4, 1, 4, 9, 1, 1, 7, 3, 1, 1, 6, 4, 9, 6, 2, 3, 4, 2, 2, ...], - [5, 6, 1, 1, 9, 1, 2, 3, 3, 4, 9, 2, 7, 2, 2, 1, 2, 5, 2, 7, 1, 1, ...], - [1, 2, 3, 2, 3, 1, 3, 2, 7, 1, 1, 1, 3, 5, 5, 4, 1, 8, 9, 9, 5, ...], - [2, 9, 2, 8, 1, 2, 3, 1, 2, 1, 1, 9, 1, 2, 6, 7, 7, 2, 1, 3, ...], - [3, 7, 3, 8, 1, 5, 2, 5, 4, 4, 6, 2, 5, 5, 1, 6, 9, 1, 6, ...], - [4, 9, 7, 8, 9, 3, 2, 2, 3, 7, 3, 1, 2, 6, 1, 5, 4, 5, ...], - [3, 9, 1, 2, 8, 9, 9, 1, 8, 2, 7, 9, 8, 9, 1, 6, 6, ...], - [1, 1, 9, 2, 9, 2, 7, 4, 2, 1, 3, 7, 2, 5, 8, 4, ...], - [3, 9, 1, 1, 1, 8, 5, 2, 1, 5, 5, 8, 2, 4, 3, ...], - [2, 9, 5, 3, 2, 1, 6, 7, 2, 2, 8, 1, 5, 2, ...], - [1, 1, 9, 8, 3, 8, 2, 7, 6, 7, 2, 1, 8, ...], - [2, 7, 2, 1, 8, 8, 4, 4, 1, 2, 9, 4, ...], - [3, 1, 1, 5, 1, 1, 8, 2, 2, 6, 2, ...], - [1, 4, 6, 6, 1, 3, 8, 1, 5, 2, ...], - [9, 1, 2, 2, 1, 3, 4, 4, 5, ...], - [6, 6, 1, 9, 4, 1, 3, 2, ...], - [1, 5, 9, 1, 8, 4, 5, ...], - [9, 1, 4, 5, 6, 7, ...], - [1, 7, 5, 6, 3, ...], - [7, 1, 1, 5, ...], - [1, 5, 9, ...], - [1, 5, ...], - [2, ...], - [...], - ... -] -``` - -Give each node a label based on its coordinates: - -```elixir -floor_nodes = - for {row, i} <- Enum.with_index(floor), - {col, j} <- Enum.with_index(row), - into: %{} do - {{i, j}, col} - end -``` - -```output -%{ - {76, 13} => 1, - {37, 47} => 2, - {65, 63} => 5, - {38, 2} => 1, - {1, 26} => 4, - {83, 76} => 2, - {32, 15} => 6, - {89, 14} => 1, - {35, 30} => 7, - {37, 53} => 7, - {4, 5} => 2, - {8, 50} => 7, - {78, 98} => 7, - {95, 56} => 7, - {74, 12} => 9, - {11, 39} => 2, - {65, 43} => 4, - {22, 38} => 1, - {14, 86} => 4, - {20, 41} => 1, - {29, 25} => 1, - {86, 10} => 1, - {83, 36} => 3, - {29, 26} => 3, - {47, 27} => 9, - {4, 81} => 3, - {31, 42} => 1, - {9, 34} => 3, - {90, 0} => 3, - {67, 98} => 1, - {13, 85} => 1, - {63, 81} => 4, - {82, 60} => 4, - {47, 38} => 1, - {15, 92} => 1, - {58, 58} => 1, - {20, 3} => 1, - {61, 95} => 7, - {23, 67} => 4, - {78, 75} => 1, - {79, 17} => 2, - {75, 0} => 7, - {16, 73} => 2, - {76, 2} => 8, - {58, 84} => 1, - {58, 33} => 7, - {47, 44} => 2, - {54, 31} => 6, - {13, ...} => 1, - {...} => 9, - ... -} -``` - -We can travel in the four cardinal directions from each node, so we need -a function to identify a node's neighbors: - -```elixir -neighbors = fn {i, j}, nodes -> - [{i + 1, j}, {i - 1, j}, {i, j + 1}, {i, j - 1}] - |> Enum.filter(&Map.has_key?(nodes, &1)) -end - -[neighbors.({0, 0}, floor_nodes), neighbors.({50, 50}, floor_nodes)] -``` - -```output -[[{1, 0}, {0, 1}], [{51, 50}, {49, 50}, {50, 51}, {50, 49}]] -``` - -## Part 1 - -Now we fold all the edges into a `Graph`: - -```elixir -make_graph = fn nodes -> - for {coord, _} <- nodes, - neighbor <- neighbors.(coord, nodes), - risk = Map.get(nodes, neighbor), - reduce: Graph.new(vertex_identifier: fn v -> v end) do - acc -> Graph.add_edge(acc, coord, neighbor, weight: risk) - end -end - -floor_graph = make_graph.(floor_nodes) -``` - -```output -#Graph<type: directed, num_vertices: 10000, num_edges: 39600> -``` - -Now we just need to use Dijkstra's algorithm to find the best path from the upper left to the lower right, -and use the map of each node's risk value to sum up the total risk for the path. - -```elixir -get_lowest_risk_path = fn nodes -> - with {{min_c, _}, {max_c, _}} <- Enum.min_max_by(nodes, fn {{i, j}, _} -> i + j end) do - nodes - |> then(make_graph) - |> Graph.dijkstra(min_c, max_c) - |> tl() - |> Enum.reduce(0, fn coord, sum -> sum + Map.get(nodes, coord) end) - end -end - -get_lowest_risk_path.(floor_nodes) -``` - -```output -403 -``` - -## Part 2 - -The process for Part 2 will be similar; the only difference -is that the graph is five times bigger after the transform. - -If the transformed risk is greater than 9, it rolls over to 1, so a -`Stream.cycle` can be used to easily get the rolled-over values. - -```elixir -expanded_floor_nodes = - with {{max_i, max_j}, _} <- Enum.max_by(floor_nodes, fn {{i, j}, _} -> i + j end), - nine_cycle = Stream.cycle(1..9) do - for {{i, j}, risk} <- floor_nodes, - x <- 0..4, - y <- 0..4, - into: %{} do - {{i + x * (max_i + 1), j + y * (max_j + 1)}, Enum.at(nine_cycle, risk - 1 + x + y)} - end - end - -Enum.count(expanded_floor_nodes) -``` - -```output -250000 -``` - -We repeat the same steps as before: building the graph, -using Dijkstra's algorithm and summing up the risks along the best path. - -```elixir -get_lowest_risk_path.(expanded_floor_nodes) -``` - -```output -2840 -``` diff --git a/2021/day-15/day-15.rkt b/2021/day-15/day-15.rkt deleted file mode 100644 index 5e61c55..0000000 --- a/2021/day-15/day-15.rkt +++ /dev/null @@ -1,49 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading - graph) - -(struct Point (x y) #:transparent) - -(define data - (for/fold ([cells (hash)]) ([row (in-lines (open-day 15 2021))] [x (in-naturals)]) - (for/fold ([cells cells]) ([n (in-string row)] [y (in-naturals)]) - (hash-set cells (Point x y) (~> n string string->number))))) - -(define x-max (~>> data hash-keys (map Point-x) (apply max))) -(define y-max (~>> data hash-keys (map Point-y) (apply max))) - -(define (neighbors pt d) - (match-define (Point x y) pt) - (~>> (list (Point (add1 x) y) (Point (sub1 x) y) (Point x (add1 y)) (Point x (sub1 y))) - (filter (curry hash-has-key? d)))) - -(define (grid-graph d) - (weighted-graph/directed (for*/list ([coord (in-list (hash-keys d))] - [neighbor (in-list (neighbors coord d))] - [weight (in-value (hash-ref d neighbor))]) - (list weight coord neighbor)))) - -;; part 1 -(define (find-path-weight d) - (define grid (grid-graph d)) - (let-values ([(node-distances _) (dijkstra grid (Point 0 0))]) - (define xm (~>> d hash-keys (map Point-x) (apply max))) - (define ym (~>> d hash-keys (map Point-y) (apply max))) - (hash-ref node-distances (Point xm ym)))) - -(~> data find-path-weight time) - -;; part 2 -(define nine-cycle (in-cycle (inclusive-range 1 9))) - -(define (expand-data data) - (for/fold ([cells (hash)]) ([coord (in-list (hash-keys data))]) - (match-define (Point x y) coord) - (for*/fold ([cells cells]) - ([n (in-range 5)] [m (in-range 5)] [val (in-value (hash-ref data coord))]) - (hash-set cells - (Point (+ x (* n (add1 x-max))) (+ y (* m (add1 y-max)))) - (sequence-ref nine-cycle (+ val n m -1)))))) - -(~> data expand-data find-path-weight time) diff --git a/2021/day-16/day-16.rkt b/2021/day-16/day-16.rkt deleted file mode 100644 index 86083ef..0000000 --- a/2021/day-16/day-16.rkt +++ /dev/null @@ -1,97 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - bitsyntax - threading) - -(struct packet (version type type-id contents len) #:transparent) - -(define (BITS->bitstring str) - (integer->bit-string (string->number str 16) (* 4 (string-length str)) #true)) - -(define data (~> (open-day 16 2021) port->string string-trim BITS->bitstring)) - -(define (get-literal-contents bitstr) - (for/fold ([assembled (bit-string)] - [remaining bitstr] - [total-length 6] - [complete? #f] - #:result (values (bit-string->integer assembled #t #f) remaining total-length)) - ([_ (in-naturals)] #:break complete?) - (bit-string-case remaining - ([(= 1 :: bits 1) (number :: bits 4) (remaining :: binary)] - (values (bit-string-append assembled (integer->bit-string number 4 #t)) - remaining - (+ total-length 5) - #f)) - ([(= 0 :: bits 1) (number :: bits 4) (remaining :: binary)] - (values (bit-string-append assembled (integer->bit-string number 4 #t)) - remaining - (+ total-length 5) - #t))))) - -(define (get-type-0-contents cnt bitstr [acc '()] [len 0]) - (cond - [(<= cnt 0) (values (reverse acc) bitstr len)] - [else - (define-values (packet remaining) (identify-next-packet bitstr)) - (get-type-0-contents (- cnt (packet-len packet)) - remaining - (cons packet acc) - (+ len (packet-len packet)))])) - -(define (get-type-1-contents cnt bitstr [acc '()] [len 0]) - (cond - [(= cnt 0) (values (reverse acc) bitstr len)] - [else - (define-values (packet remaining) (identify-next-packet bitstr)) - (get-type-1-contents (sub1 cnt) remaining (cons packet acc) (+ len (packet-len packet)))])) - -(define (identify-next-packet bitstr) - (bit-string-case - bitstr - ([(packet-version :: bits 3) (= 4 :: bits 3) (remaining :: binary)] - (define-values (n now-remaining len) (get-literal-contents remaining)) - (values (packet packet-version 'literal 4 n len) now-remaining)) - ([(packet-version :: bits 3) - (type-id :: bits 3) - (= 0 :: bits 1) - (subpacket-length :: bits 15) - (remaining :: binary)] - (define-values (contents now-remaining sublength) - (get-type-0-contents subpacket-length remaining)) - (values (packet packet-version 'operator type-id contents (+ 22 sublength)) now-remaining)) - ([(packet-version :: bits 3) - (type-id :: bits 3) - (= 1 :: bits 1) - (subpacket-count :: bits 11) - (remaining :: binary)] - (define-values (contents now-remaining sublength) (get-type-1-contents subpacket-count remaining)) - (values (packet packet-version 'operator type-id contents (+ 22 sublength)) now-remaining)))) - -(match-define-values (outer-packet n) (identify-next-packet data)) - -;; part 1 -(define (packet-sum-version p) - (match p - [(packet v 'literal _type-id _contents _len) v] - [(packet v 'operator _type-id ps _len) (foldl (λ (p acc) (+ acc (packet-sum-version p))) v ps)])) - -(packet-sum-version outer-packet) - -;; part 2 -(define packet-f - (match-lambda - [0 +] - [1 *] - [2 min] - [3 max] - [5 (λ (a b) (if (> a b) 1 0))] - [6 (λ (a b) (if (< a b) 1 0))] - [7 (λ (a b) (if (= a b) 1 0))])) - -(define packet-eval - (match-lambda - [(packet _v 'literal _type-id n _len) n] - [(packet _v 'operator type-id ps _len) (~>> ps (map packet-eval) (apply (packet-f type-id)))])) - -(packet-eval outer-packet) diff --git a/2021/day-17/day-17.rkt b/2021/day-17/day-17.rkt deleted file mode 100644 index 7de44a0..0000000 --- a/2021/day-17/day-17.rkt +++ /dev/null @@ -1,43 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading) - -(define-values (x-min x-max y-min y-max) - (~> (open-day 17 2021) - port->string - (regexp-match #px"target area: x=(.*)\\.\\.(.*), y=(.*)\\.\\.(.*)\n" _) - rest - (map string->number _) - (apply values _))) - -(define (hit? x y) - (and (x . >= . x-min) (x . <= . x-max) (y . >= . y-min) (y . <= . y-max))) - -(define (miss? x y) - (or (y . < . y-min) (x . > . x-max))) - -(define (drag dx i) - (max (- dx i) 0)) -(define (gravity dy i) - (- dy i)) - -(define (find-trajectory-apex dx dy) - (for/fold ([x 0] [y 0] [y-apex 0] [result #f] #:result (list y-apex result)) - ([i (in-naturals)] #:break result) - (cond - [(hit? x y) (values dx dy y-apex 'hit)] - [(miss? x y) (values x y 'miss 'miss)] - [else (values (+ x (drag dx i)) (+ y (gravity dy i)) (if (y . > . y-apex) y y-apex) #f)]))) - -(define on-target - (for*/list ([dx (in-inclusive-range 1 x-max)] - [dy (in-inclusive-range y-min (abs (* 2 y-max)))] - [velocity (in-value (find-trajectory-apex dx dy))] - #:when (equal? (second velocity) 'hit)) - (list dx dy (first velocity)))) - -;; part 1 -(~>> on-target (argmax third) third) - -;; part 2 -(length on-target) diff --git a/2021/day-18/day-18.rkt b/2021/day-18/day-18.rkt deleted file mode 100644 index 45016b1..0000000 --- a/2021/day-18/day-18.rkt +++ /dev/null @@ -1,5 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading) - -;; tbd
\ No newline at end of file diff --git a/2021/day-19/day-19.rkt b/2021/day-19/day-19.rkt deleted file mode 100644 index 4c6334d..0000000 --- a/2021/day-19/day-19.rkt +++ /dev/null @@ -1,48 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading - racket/struct) - -(struct coord (x y z) #:transparent) - -(define (coord-broadcast f c1 c2) - (match-define (coord x1 y1 z1) c1) - (match-define (coord x2 y2 z2) c2) - (coord (f x1 x2) (f y1 y2) (f z1 z2))) - -(define (coord-reduce f c1 c2) - (foldl (λ (i1 i2 acc) (+ acc (f i1 i2))) 0 (struct->list c1) (struct->list c2))) - -(define coord-delta (curry coord-broadcast -)) -(define coord-sum (curry coord-broadcast +)) -(define coord-manhattan (curry coord-reduce (coord 0 0 0))) - -(define (create-scan-data d) - (for/list ([l (in-list d)]) - (for/list ([pt (in-list (~> (string-split l "\n") rest))]) - (~>> pt - (regexp-match #px"(-?\\d+),(-?\\d+),(-?\\d+)") - rest - (map string->number) - (apply coord))))) - -(define scanner-data (create-scan-data (~>> (open-day 19 2021) port->string (string-split _ "\n\n")))) - -(define (generate-rotations scanner) - (apply - map - list - (for*/list ([pt (in-list scanner)]) - (match-define (coord x y z) pt) - (define orientations (list (list x y z) (list x z (- y)) (list x (- y) (- z)) (list x (- z) y))) - (append* (for/list ([o (in-list orientations)]) - (match-define (list x* y* z*) o) - (list (list x y z) - (list (- x) z y) - (list z (- y) x) - (list y x (- z)) - (list (- y) (- z) x))))))) - -(define (find-overlaps scan1 scan2) - (for/list ([rotation (in-permutations scan2)]) - (map coord-sum scan1 rotation))) diff --git a/2021/day-19/test-scanners b/2021/day-19/test-scanners deleted file mode 100644 index b596cc4..0000000 --- a/2021/day-19/test-scanners +++ /dev/null @@ -1,136 +0,0 @@ ---- scanner 0 --- -404,-588,-901 -528,-643,409 --838,591,734 -390,-675,-793 --537,-823,-458 --485,-357,347 --345,-311,381 --661,-816,-575 --876,649,763 --618,-824,-621 -553,345,-567 -474,580,667 --447,-329,318 --584,868,-557 -544,-627,-890 -564,392,-477 -455,729,728 --892,524,684 --689,845,-530 -423,-701,434 -7,-33,-71 -630,319,-379 -443,580,662 --789,900,-551 -459,-707,401 - ---- scanner 1 --- -686,422,578 -605,423,415 -515,917,-361 --336,658,858 -95,138,22 --476,619,847 --340,-569,-846 -567,-361,727 --460,603,-452 -669,-402,600 -729,430,532 --500,-761,534 --322,571,750 --466,-666,-811 --429,-592,574 --355,545,-477 -703,-491,-529 --328,-685,520 -413,935,-424 --391,539,-444 -586,-435,557 --364,-763,-893 -807,-499,-711 -755,-354,-619 -553,889,-390 - ---- scanner 2 --- -649,640,665 -682,-795,504 --784,533,-524 --644,584,-595 --588,-843,648 --30,6,44 --674,560,763 -500,723,-460 -609,671,-379 --555,-800,653 --675,-892,-343 -697,-426,-610 -578,704,681 -493,664,-388 --671,-858,530 --667,343,800 -571,-461,-707 --138,-166,112 --889,563,-600 -646,-828,498 -640,759,510 --630,509,768 --681,-892,-333 -673,-379,-804 --742,-814,-386 -577,-820,562 - ---- scanner 3 --- --589,542,597 -605,-692,669 --500,565,-823 --660,373,557 --458,-679,-417 --488,449,543 --626,468,-788 -338,-750,-386 -528,-832,-391 -562,-778,733 --938,-730,414 -543,643,-506 --524,371,-870 -407,773,750 --104,29,83 -378,-903,-323 --778,-728,485 -426,699,580 --438,-605,-362 --469,-447,-387 -509,732,623 -647,635,-688 --868,-804,481 -614,-800,639 -595,780,-596 - ---- scanner 4 --- -727,592,562 --293,-554,779 -441,611,-461 --714,465,-776 --743,427,-804 --660,-479,-426 -832,-632,460 -927,-485,-438 -408,393,-506 -466,436,-512 -110,16,151 --258,-428,682 --393,719,612 --211,-452,876 -808,-476,-593 --575,615,604 --485,667,467 --680,325,-822 --627,-443,-432 -872,-547,-609 -833,512,582 -807,604,487 -839,-516,451 -891,-625,532 --652,-548,-490 -30,-46,-14
\ No newline at end of file diff --git a/2021/day-20/day-20.rkt b/2021/day-20/day-20.rkt deleted file mode 100644 index b7ed092..0000000 --- a/2021/day-20/day-20.rkt +++ /dev/null @@ -1,59 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading) - -(struct pixel (i j) #:transparent) - -(define-values (raw-enhancement raw-image) - (~> (open-day 20 2021) port->string (string-split "\n\n") (apply values _))) - -(define (char->pixel c) - (if (char=? #\# c) 'light 'dark)) -(define (pixel->char c) - (if (equal? 'light c) #\# #\.)) - -(define enhancement-algorithm - (for/hash ([(c i) (in-indexed (~> raw-enhancement (string-replace "\n" "")))]) - (values i (char->pixel c)))) - -(define image-hash - (for*/hash ([(row i) (in-indexed (string-split raw-image "\n"))] [(c j) (in-indexed row)]) - (values (pixel i j) (char->pixel c)))) - -(define (window->new-pixel p ps bg) - (match-define (pixel i j) p) - (~> (for*/list ([di '(-1 0 1)] [dj '(-1 0 1)]) - (if (equal? 'dark (hash-ref ps (pixel (+ i di) (+ j dj)) bg)) #\0 #\1)) - (apply string _) - (string->number _ 2) - (hash-ref enhancement-algorithm _))) - -(define (pad-hash ps bg) - (define coords (hash-keys ps)) - (define i-min (~>> coords (map pixel-i) (apply min))) - (define i-max (~>> coords (map pixel-i) (apply max))) - (define j-min (~>> coords (map pixel-j) (apply min))) - (define j-max (~>> coords (map pixel-j) (apply max))) - (for*/hash ([i (in-inclusive-range (- i-min 2) (+ i-max 2))] - [j (in-inclusive-range (- j-min 2) (+ j-max 2))]) - (values (pixel i j) (hash-ref ps (pixel i j) bg)))) - -(define (enhance-image ps bg) - (for/hash ([(p _) (in-hash (pad-hash ps bg))]) - (values p (window->new-pixel p ps bg)))) - -;; part 1 -;; looking at the enhancement algorithm, since a window of 0 -> light and 512 -> dark, -;; the infinite background flips colors every other enhancement step -;; instead of trying to account for this algorithmically I just hardcoded it in -(~> image-hash - (enhance-image 'dark) - (enhance-image 'light) - hash-values - (count (curry equal? 'light) _)) - -;; part 2 -(~> (for/fold ([img image-hash]) ([_ (in-range 25)]) - (~> img (enhance-image 'dark) (enhance-image 'light))) - hash-values - (count (curry equal? 'light) _)) diff --git a/2021/day-21/day-21.rkt b/2021/day-21/day-21.rkt deleted file mode 100644 index 9ca9b1b..0000000 --- a/2021/day-21/day-21.rkt +++ /dev/null @@ -1,59 +0,0 @@ -#lang racket -(require threading - memoize) - -;; not going to bother importing the data since it's just two lines of text -(define player-1-start 4) -(define player-2-start 6) - -(define track (sequence->stream (in-cycle (inclusive-range 1 10)))) -(define current-turn (in-cycle (list 'player-1 'player-2))) -(define die-rolls (sequence->stream (in-cycle (inclusive-range 1 100)))) - -;; part 1 -(~> (for/fold ([player-1-score 0] - [player-1-track (stream-tail track (sub1 player-1-start))] - [player-2-score 0] - [player-2-track (stream-tail track (sub1 player-2-start))] - [dice die-rolls] - [last-turn 0] - #:result (list (min player-1-score player-2-score) (* 3 last-turn))) - ([turn-count (in-naturals 1)] - [turn-for current-turn] - #:break (or (player-1-score . >= . 1000) (player-2-score . >= . 1000))) - (define rolls (apply + (stream->list (stream-take dice 3)))) - (match turn-for - ['player-1 - (define next-track (stream-tail player-1-track rolls)) - (values (+ player-1-score (stream-first next-track)) - next-track - player-2-score - player-2-track - (stream-tail dice 3) - turn-count)] - ['player-2 - (define next-track (stream-tail player-2-track rolls)) - (values player-1-score - player-1-track - (+ player-2-score (stream-first next-track)) - next-track - (stream-tail dice 3) - turn-count)])) - (apply * _)) - -;; part 2 -(define d3 (list 1 2 3)) -(define roll-space (~>> (cartesian-product d3 d3 d3) (map (λ~>> (apply +))))) - -(define/memo - (next-turns p1-score p2-score p1-start p2-start) - (cond - [(p1-score . >= . 21) '(1 0)] - [(p2-score . >= . 21) '(0 1)] - [else - (for/fold ([wins '(0 0)]) ([roll (in-list roll-space)]) - (define move-to (add1 (modulo (sub1 (+ roll p1-start)) 10))) - (define possible-wins (next-turns p2-score (+ p1-score move-to) p2-start move-to)) - (list (+ (first wins) (second possible-wins)) (+ (second wins) (first possible-wins))))])) - -(~>> (next-turns 0 0 player-1-start player-2-start) (apply max)) diff --git a/2021/day-25/day-25.rkt b/2021/day-25/day-25.rkt deleted file mode 100644 index 7a3a5ca..0000000 --- a/2021/day-25/day-25.rkt +++ /dev/null @@ -1,35 +0,0 @@ -#lang racket -(require "../../jj-aoc.rkt" - threading) - -(define sea-floor - (for*/hash ([(row i) (in-indexed (in-lines (open-day 25 2021)))] [(c j) (in-indexed row)]) - (values (list i j) c))) - -(define-values (max-i max-j) - (~> sea-floor hash-keys (argmax (λ (coord) (apply + coord)) _) (apply values _))) - -(define (cucumber-movement h c delta-i delta-j) - (define new-hash (hash-copy h)) - (for* ([(coord x) (in-hash h)] #:when (eq? x c)) - (match-define (list i j) coord) - (define neighbor (list (+ delta-i i) (+ delta-j j))) - (define neighbor-or-wrap - (if (hash-has-key? h neighbor) neighbor (list (if (= delta-i 0) i 0) (if (= delta-j 0) j 0)))) - (when (eq? #\. (hash-ref h neighbor-or-wrap)) - (hash-set*! new-hash coord #\. neighbor-or-wrap c))) - new-hash) - -(define (eastwards-movement h) - (cucumber-movement h #\> 0 1)) - -(define (southwards-movement h) - (cucumber-movement h #\v 1 0)) - -;; part 1 -(for/fold ([f sea-floor] [step 0] #:result (add1 step)) ([i (in-naturals 1)]) - (define f* (~> f eastwards-movement southwards-movement)) - #:break (equal? f* f) - (values f* i)) - -;; no part 2 -- merry Christmas |