Merge branch 'main' of https://github.com/hunkyjimpjorps/AdventOfCode

6 files changed, 562 insertions, 0 deletions

diff --git a/2022/day-08/day-08.ipynb b/2022/day-08/day-08.ipynb
new file mode 100644
index 0000000..890a9bb
--- /dev/null
+++ b/2022/day-08/day-08.ipynb
@@ -0,0 +1,257 @@
+{
+ "cells": [
+  {
+   "attachments": {},
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "### Advent of Code 2022\n",
+    "#### Day 8: Treetop Tree House\n",
+    "\n",
+    "For a rectangular grid of trees of varying heights,\n",
+    "\n",
+    "**Part 1.** How many trees are visible (not blocked by same-height or taller trees in their row or column) from outside the patch?\n",
+    "\n",
+    "**Part 2.** What's the tree with the best \"scenic score\" (the product of the number of trees it can see in each cardinal direction)?\n",
+    "\n",
+    "For this solution, I didn't use any packages besides the standard distribution and `advent-of-code`."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 1,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [],
+   "source": [
+    "(require racket\n",
+    "         advent-of-code)"
+   ]
+  },
+  {
+   "attachments": {},
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "##### Part 1\n",
+    "\n",
+    "I built this array as a hashtable with a coordinate struct as the key and the tree height as the value, which makes it easy to check if a particular location falls outside the grid."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 2,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [],
+   "source": [
+    "(struct posn (r c) #:transparent)\n",
+    "\n",
+    "(define (make-tree-grid data)\n",
+    "  (for*/hash ([(row r) (in-indexed data)] [(col c) (in-indexed (in-string row))])\n",
+    "    (values (posn r c) (string->number (string col)))))\n",
+    "\n",
+    "(define tree-grid (make-tree-grid (in-lines (open-aoc-input (find-session) 2022 8))))"
+   ]
+  },
+  {
+   "attachments": {},
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "A tree is visible if there aren't any other trees as tall as it or taller blocking the visibility in at least one of the cardinal directions.  We check in a particular direction by repeatedly stepping outwards from the original coordinate and checking if we've found a blocking tree yet.\n",
+    "\n",
+    "The `for/first` returns `#true` if it finds a blocking tree and `#false` if it runs out of trees to check, and the result is negated to turn it into a predicate about whether the tree can see (and be seen from) outside."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 3,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [],
+   "source": [
+    "(define (can-see-to-outside? p height dr dc h)\n",
+    "  (match-define (posn r c) p)\n",
+    "  (not (for/first ([n (in-naturals 1)]\n",
+    "                   #:do [(define p* (posn (+ r (* n dr)) (+ c (* n dc))))]\n",
+    "                   #:break (not (hash-has-key? h p*))\n",
+    "                   #:when (<= height (hash-ref h p*)))\n",
+    "         #true)))"
+   ]
+  },
+  {
+   "attachments": {},
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "Now we need a function to check the four cardinal directions and see if at least one of them is unblocked."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 4,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [],
+   "source": [
+    "(define (visible-in-any-direction? p height h)\n",
+    "  (for*/or ([dr (in-list '(-1 0 1))] [dc (in-list '(-1 0 1))] #:when (= 1 (abs (+ dr dc))))\n",
+    "    (can-see-to-outside? p height dr dc h)))"
+   ]
+  },
+  {
+   "attachments": {},
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "Finally, add 1 to the count for every tree that's visible:"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 5,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/html": [
+       "<code>1733</code>"
+      ],
+      "text/plain": [
+       "1733"
+      ]
+     },
+     "execution_count": 5,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "(define (count-visible-trees trees)\n",
+    "  (for/sum ([(tree-posn height) (in-hash trees)])\n",
+    "           (cond\n",
+    "             [(visible-in-any-direction? tree-posn height trees) 1]\n",
+    "             [else 0])))\n",
+    "\n",
+    "(count-visible-trees tree-grid)"
+   ]
+  },
+  {
+   "attachments": {},
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "##### Part 2\n",
+    "\n",
+    "Now we're searching for the tree with the most interior visibility, which is the product of how far we can look in each cardinal direction before running out of visible trees. \n",
+    "\n",
+    "The search is similar, except now we're calculating a score instead of just checking a predicate. We walk one step at a time, increment the counter and check each tree; if we find a blocking tree, we return the counter, and if we run out of trees to check we break and return the previous counter value.  If there aren't any trees in a direction and the `for` body is never evaluated, `for/last` returns `#false`, which is equivalent to a visibility of 0."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 6,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [],
+   "source": [
+    "(define (scenic-score-in-direction p height dr dc h)\n",
+    "  (match-define (posn r c) p)\n",
+    "  (define score\n",
+    "    (for/last ([n (in-naturals 1)]\n",
+    "               #:do [(define p* (posn (+ r (* n dr)) (+ c (* n dc))))]\n",
+    "               #:break (not (hash-has-key? h p*))\n",
+    "               #:final (<= height (hash-ref h p*)))\n",
+    "      n))\n",
+    "  (if (not score) 0 score))\n",
+    "\n",
+    "(define (scenic-score p height h)\n",
+    "  (for*/product ([dr (in-list '(-1 0 1))] [dc (in-list '(-1 0 1))] #:when (= 1 (abs (+ dr dc))))\n",
+    "                (scenic-score-in-direction p height dr dc h)))"
+   ]
+  },
+  {
+   "attachments": {},
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "With these functions written, calculate each tree's score and find the maximum:"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 7,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/html": [
+       "<code>284648</code>"
+      ],
+      "text/plain": [
+       "284648"
+      ]
+     },
+     "execution_count": 7,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "(define (find-best-scenic-score trees)\n",
+    "  (apply max\n",
+    "         (for/list ([(tree-posn height) (in-hash trees)])\n",
+    "           (scenic-score tree-posn height trees))))\n",
+    "\n",
+    "(find-best-scenic-score tree-grid)"
+   ]
+  }
+ ],
+ "metadata": {
+  "kernelspec": {
+   "display_name": "Racket (Trusted)",
+   "language": "racket",
+   "name": "racket-trusted"
+  },
+  "language_info": {
+   "codemirror_mode": "scheme",
+   "file_extension": ".rkt",
+   "mimetype": "text/x-racket",
+   "name": "Racket",
+   "pygments_lexer": "racket",
+   "version": "8.7"
+  },
+  "orig_nbformat": 4,
+  "vscode": {
+   "interpreter": {
+    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
+   }
+  }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 2
+}
diff --git a/2022/day-08/day-08.rkt b/2022/day-08/day-08.rkt
new file mode 100644
index 0000000..6b60eca
--- /dev/null
+++ b/2022/day-08/day-08.rkt
@@ -0,0 +1,56 @@
+#lang racket
+
+(require advent-of-code)
+
+(struct posn (r c) #:transparent)
+
+(define (make-tree-grid data)
+  (for*/hash ([(row r) (in-indexed data)] [(col c) (in-indexed (in-string row))])
+    (values (posn r c) (string->number (string col)))))
+
+(define tree-grid (make-tree-grid (in-lines (open-aoc-input (find-session) 2022 8))))
+
+;; part 1
+
+(define (can-see-to-outside? p height dr dc h)
+  (match-define (posn r c) p)
+  (not (for/first ([n (in-naturals 1)]
+                   #:do [(define p* (posn (+ r (* n dr)) (+ c (* n dc))))]
+                   #:break (not (hash-has-key? h p*))
+                   #:when (<= height (hash-ref h p*)))
+         #true)))
+
+(define (visible-in-any-direction? p height h)
+  (for*/or ([dr (in-list '(-1 0 1))] [dc (in-list '(-1 0 1))] #:when (= 1 (abs (+ dr dc))))
+    (can-see-to-outside? p height dr dc h)))
+
+(define (count-visible-trees trees)
+  (for/sum ([(tree-posn height) (in-hash trees)])
+           (cond
+             [(visible-in-any-direction? tree-posn height trees) 1]
+             [else 0])))
+
+(count-visible-trees tree-grid)
+
+;; part 2
+
+(define (scenic-score-in-direction p height dr dc h)
+  (match-define (posn r c) p)
+  (define score
+    (for/last ([n (in-naturals 1)]
+               #:do [(define p* (posn (+ r (* n dr)) (+ c (* n dc))))]
+               #:break (not (hash-has-key? h p*))
+               #:final (<= height (hash-ref h p*)))
+      n))
+  (if (not score) 0 score))
+
+(define (scenic-score p height h)
+  (for*/product ([dr (in-list '(-1 0 1))] [dc (in-list '(-1 0 1))] #:when (= 1 (abs (+ dr dc))))
+                (scenic-score-in-direction p height dr dc h)))
+
+(define (find-best-scenic-score trees)
+  (apply max
+         (for/list ([(tree-posn height) (in-hash trees)])
+           (scenic-score tree-posn height trees))))
+
+(find-best-scenic-score tree-grid)
diff --git a/2022/day-09/day-09.rkt b/2022/day-09/day-09.rkt
new file mode 100644
index 0000000..0390d2e
--- /dev/null
+++ b/2022/day-09/day-09.rkt
@@ -0,0 +1,76 @@
+#lang racket
+(require advent-of-code
+         threading)
+
+(struct cmd (dir amt))
+(struct posn (x y) #:transparent)
+
+(define moves
+  (~> (fetch-aoc-input (find-session) 2022 9)
+      (string-split "\n")
+      (map (λ~> (string-split _)
+                (match _
+                  [(list dir amt) (cmd (string->symbol dir) (string->number amt))]))
+           _)))
+
+(define (move-head p dir)
+  (match-define (posn x y) p)
+  (match dir
+    ['U (posn x (add1 y))]
+    ['D (posn x (sub1 y))]
+    ['R (posn (add1 x) y)]
+    ['L (posn (sub1 x) y)]))
+
+(define (avg n m)
+  (/ (+ n m) 2))
+
+(define (manhattan-distance p1 p2)
+  (match-define (posn x1 y1) p1)
+  (match-define (posn x2 y2) p2)
+  (+ (abs (- x2 x1)) (abs (- y2 y1))))
+
+(define (follow-head head tail)
+  (match-define (posn hx hy) head)
+  (match-define (posn tx ty) tail)
+
+  (case (manhattan-distance head tail)
+    [(0 1) tail]
+    [(2 4)
+     (cond
+       [(and (= 1 (abs (- hx tx)) (abs (- hy ty)))) tail]
+       [else (posn (avg hx tx) (avg hy ty))])]
+    [(3)
+     (cond
+       [(= 2 (abs (- hx tx))) (posn (avg hx tx) hy)]
+       [(= 2 (abs (- hy ty))) (posn hx (avg hy ty))])]))
+
+;; part 1
+(for*/fold ([head (posn 0 0)] [tail (posn 0 0)] [tail-posns (set)] #:result (set-count tail-posns))
+           ([move (in-list moves)] #:do [(match-define (cmd dir amt) move)] [_ (in-range amt)])
+  (define new-head (move-head head dir))
+  (define new-tail (follow-head new-head tail))
+  (values new-head new-tail (set-add tail-posns new-tail)))
+
+;; part 2
+(for*/fold ([knots (make-list 10 (posn 0 0))] [tail-posns (set)] #:result (set-count tail-posns))
+           ([move (in-list moves)] #:do [(match-define (cmd dir amt) move)] [_ (in-range amt)])
+  (define updated-knots
+    (for/fold ([knots-list (list (move-head (first knots) dir))])
+              ([following-knot (in-list (rest knots))])
+      (cons (follow-head (car knots-list) following-knot) knots-list)))
+  (values (reverse updated-knots) (set-add tail-posns (first updated-knots))))
+
+;; refactor: part 1 and 2 combined
+(define (follow-tail move-list rope-length)
+  (for*/fold ([knots (make-list rope-length (posn 0 0))]
+              [tail-posns (set)]
+              #:result (set-count tail-posns))
+             ([move (in-list move-list)] #:do [(match-define (cmd dir amt) move)] [_ (in-range amt)])
+    (define updated-knots
+      (for/fold ([knots-list (list (move-head (first knots) dir))])
+                ([following-knot (in-list (rest knots))])
+        (cons (follow-head (car knots-list) following-knot) knots-list)))
+    (values (reverse updated-knots) (set-add tail-posns (first updated-knots)))))
+
+(time (follow-tail moves 2))
+(time (follow-tail moves 10))
diff --git a/2022/day-10/day-10.rkt b/2022/day-10/day-10.rkt
new file mode 100644
index 0000000..70c80d3
--- /dev/null
+++ b/2022/day-10/day-10.rkt
@@ -0,0 +1,43 @@
+#lang racket
+
+(require advent-of-code
+         threading
+         fancy-app
+         (only-in algorithms chunks-of))
+
+(define/match (process-instruction _)
+  [((list "noop")) (list 'noop)]
+  [((list "addx" (app string->number val))) (list 'noop (cons 'addx val))])
+
+(define instructions
+  (~> (fetch-aoc-input (find-session) 2022 10)
+      (string-split "\n")
+      (map (λ~> string-split process-instruction) _)
+      (apply append _)))
+
+;; part 1
+(define interesting-times (inclusive-range 20 220 40))
+
+(define/match (evaluate-instruction _op acc)
+  [('noop _) acc]
+  [((cons 'addx n) _) (+ acc n)])
+
+(for/fold ([acc 1] [interesting-strengths 0] #:result interesting-strengths)
+          ([inst (in-list instructions)] [i (in-naturals 1)])
+  (define new-interesting
+    (if (member i interesting-times) (+ interesting-strengths (* i acc)) interesting-strengths))
+  (values (evaluate-instruction inst acc) new-interesting))
+
+;; part 2
+(for/fold ([acc 1] [pixels '()] #:result (~> pixels reverse (chunks-of 40) (map (apply string _) _)))
+          ([inst (in-list instructions)] [i (in-naturals)])
+  (define new-pixel (if (member (modulo i 40) (list (sub1 acc) acc (add1 acc))) #\█ #\space))
+  (values (evaluate-instruction inst acc) (cons new-pixel pixels)))
+
+; for my data set,
+; '("███  ████ ████ █  █ ████ ████ █  █  ██  "
+;   "█  █    █ █    █ █  █    █    █  █ █  █ "
+;   "█  █   █  ███  ██   ███  ███  ████ █  █ "
+;   "███   █   █    █ █  █    █    █  █ ████ "
+;   "█ █  █    █    █ █  █    █    █  █ █  █ "
+;   "█  █ ████ ████ █  █ ████ █    █  █ █  █ ")
diff --git a/2022/day-11/day-11.rkt b/2022/day-11/day-11.rkt
new file mode 100644
index 0000000..af7b4ee
--- /dev/null
+++ b/2022/day-11/day-11.rkt
@@ -0,0 +1,85 @@
+#lang racket
+(require threading)
+
+(struct monkey ([items #:mutable] operation modulus yes no))
+
+;; really don't feel like parsing the input today
+(define monkeys-list
+  (list (cons 0 (monkey '(97 81 57 57 91 61)
+                        (λ (n) (* n 7))
+                        11 5 6))
+        (cons 1 (monkey '(88 62 68 90)
+                        (λ (n) (* n 17))
+                        19 4 2))
+        (cons 2 (monkey '(74 87)
+                        (λ (n) (+ n 2))
+                        5 7 4))
+        (cons 3 (monkey '(53 81 60 87 90 99 75)
+                        (λ (n) (+ n 1))
+                        2 2 1))
+        (cons 4 (monkey '(57)
+                        (λ (n) (+ n 6))
+                        13 7 0))
+        (cons 5 (monkey '(54 84 91 55 59 72 75 70)
+                        (λ (n) (* n n))
+                        7 6 3))
+        (cons 6 (monkey '(95 79 79 68 78)
+                        (λ (n) (+ n 3))
+                        3 1 3))
+        (cons 7 (monkey '(61 97 67)
+                        (λ (n) (+ n 4))
+                        17 0 5))))
+
+(define monkey-lcm (~> monkeys-list (map (λ~> cdr monkey-modulus) _) (apply lcm _)))
+
+;; part 1
+(define monkeys-count-pt1 (make-hash))
+(define monkeys-hash-pt1 (make-hash monkeys-list))
+
+(for
+    ([rnd (in-range 20)])
+  (for
+      ([turn (inclusive-range 0 7)])
+    (match-define (monkey items op modulus yes no) (hash-ref monkeys-hash-pt1 turn))
+    (for ([i (in-list items)])
+      (define i* (quotient (op i) 3))
+      (define m (if (= 0 (modulo i* modulus)) yes no))
+      (match-define (monkey items* op* modulus* yes* no*) (hash-ref monkeys-hash-pt1 m))
+      (hash-update! monkeys-count-pt1 turn add1 0)
+      (hash-set! monkeys-hash-pt1
+                 m
+                 (monkey (append items* (list i*)) op* modulus* yes* no*)))
+    (hash-set! monkeys-hash-pt1 turn (monkey '() op modulus yes no))))
+
+(~> monkeys-count-pt1
+    hash->list
+    (sort _ > #:key cdr)
+    (take _ 2)
+    (map cdr _)
+    (apply * _))
+
+;; part 2
+(define monkeys-count-pt2 (make-hash))
+(define monkeys-hash-pt2 (make-hash monkeys-list))
+
+(for
+    ([rnd (in-range 10000)])
+  (for
+      ([turn (inclusive-range 0 7)])
+    (match-define (monkey items op modulus yes no) (hash-ref monkeys-hash-pt2 turn))
+    (for ([i (in-list items)])
+      (define i* (op i))
+      (define m (if (= 0 (modulo i* modulus)) yes no))
+      (match-define (monkey items* op* modulus* yes* no*) (hash-ref monkeys-hash-pt2 m))
+      (hash-update! monkeys-count-pt2 turn add1 0)
+      (hash-set! monkeys-hash-pt2
+                 m
+                 (monkey (append items* (list (remainder i* monkey-lcm))) op* modulus* yes* no*)))
+    (hash-set! monkeys-hash-pt2 turn (monkey '() op modulus yes no))))
+
+(~> monkeys-count-pt2
+    hash->list
+    (sort _ > #:key cdr)
+    (take _ 2)
+    (map cdr _)
+    (apply * _))
\ No newline at end of file
diff --git a/2022/day-12/day-12.rkt b/2022/day-12/day-12.rkt
new file mode 100644
index 0000000..9120468
--- /dev/null
+++ b/2022/day-12/day-12.rkt
@@ -0,0 +1,45 @@
+#lang racket
+
+(require advent-of-code
+         fancy-app
+         graph)
+
+(define raw-terrain (fetch-aoc-input (find-session) 2022 12 #:cache #true))
+(define special-points (make-hash))
+
+(define terrain-mesh
+  (for*/hash ([(row x) (in-indexed (string-split raw-terrain))] [(col y) (in-indexed row)])
+    (case col
+      [(#\S)
+       (hash-set! special-points 'start (cons x y))
+       (values (cons x y) 0)]
+      [(#\E)
+       (hash-set! special-points 'end (cons x y))
+       (values (cons x y) 25)]
+      [else (values (cons x y) (- (char->integer col) (char->integer #\a)))])))
+
+(define (neighbors p)
+  (match-define (cons x y) p)
+  (for*/list ([dx (in-list '(-1 0 1))]
+              [dy (in-list '(-1 0 1))]
+              #:when (= 1 (abs (+ dx dy)))
+              #:do [(define p (cons (+ x dx) (+ y dy)))]
+              #:when (hash-has-key? terrain-mesh p))
+    p))
+
+(define paths
+  (directed-graph (for*/list ([p (in-list (hash-keys terrain-mesh))]
+                              [neighbor (in-list (neighbors p))]
+                              #:unless (> (sub1 (hash-ref terrain-mesh neighbor))
+                                          (hash-ref terrain-mesh p)))
+                    (list p neighbor))))
+
+;; part 1
+(match-define-values (distances _) (dijkstra paths (hash-ref special-points 'start)))
+(hash-ref distances (hash-ref special-points 'end))
+
+;; part 2
+(for/lists (lengths #:result (apply min lengths))
+           ([start (in-list (hash-keys terrain-mesh))] #:when (= 0 (hash-ref terrain-mesh start)))
+           (match-define-values (distances _) (dijkstra paths start))
+           (hash-ref distances (hash-ref special-points 'end)))