about summary refs log tree commit diff
path: root/users
diff options
context:
space:
mode:
authorVincent Ambo <mail@tazj.in>2020-12-01T12·12+0100
committertazjin <mail@tazj.in>2020-12-01T12·55+0000
commit6c08bcc84d51fd5a1a5152b3c611df44c93a3f00 (patch)
treee630b752c08018aded887c2708e29a30f9ab716d /users
parent7d7c15c9a69d1d88f66640285ce08eaa3b60078e (diff)
chore(tazjin/aoc2019): Move out of //fun r/1970
Change-Id: I9d065b672f4245b81444737dd900c8864447bc4d
Reviewed-on: https://cl.tvl.fyi/c/depot/+/2211
Tested-by: BuildkiteCI
Reviewed-by: tazjin <mail@tazj.in>
Diffstat (limited to 'users')
-rw-r--r--users/tazjin/aoc2019/default.nix22
-rw-r--r--users/tazjin/aoc2019/solution-day1.el28
-rw-r--r--users/tazjin/aoc2019/solution-day2.el53
-rw-r--r--users/tazjin/aoc2019/solution-day3.el64
-rw-r--r--users/tazjin/aoc2019/solution-day4.el73
5 files changed, 240 insertions, 0 deletions
diff --git a/users/tazjin/aoc2019/default.nix b/users/tazjin/aoc2019/default.nix
new file mode 100644
index 000000000000..5f1f248c504a
--- /dev/null
+++ b/users/tazjin/aoc2019/default.nix
@@ -0,0 +1,22 @@
+# Solutions for Advent of Code 2019, written in Emacs Lisp.
+#
+# For each day a new file is created as "solution-day$n.el".
+{ depot, ... }:
+
+let
+  inherit (builtins) attrNames filter head listToAttrs match readDir;
+  dir = readDir ./.;
+  matchSolution = match "solution-(.*)\.el";
+  isSolution = f: (matchSolution f) != null;
+  getDay = f: head (matchSolution f);
+
+  solutionFiles = filter (e: dir."${e}" == "regular" && isSolution e) (attrNames dir);
+  solutions = map (f: let day = getDay f; in {
+    name = day;
+    value = depot.writeElispBin { # TODO(tazjin): move writeElispBin to depot.nix
+      name = "aoc2019";
+      deps = p: with p; [ dash s ht ];
+      src = ./. + ("/" + f);
+    };
+  }) solutionFiles;
+in listToAttrs solutions
diff --git a/users/tazjin/aoc2019/solution-day1.el b/users/tazjin/aoc2019/solution-day1.el
new file mode 100644
index 000000000000..d805c22ec870
--- /dev/null
+++ b/users/tazjin/aoc2019/solution-day1.el
@@ -0,0 +1,28 @@
+;; Advent of Code 2019 - Day 1
+(require 'dash)
+
+;; Puzzle 1:
+
+(defvar day-1/input
+  '(83285 96868 121640 51455 128067 128390 141809 52325 68310 140707 124520 149678
+          87961 52040 133133 52203 117483 85643 84414 86558 65402 122692 88565 61895
+          126271 128802 140363 109764 53600 114391 98973 124467 99574 69140 144856
+          56809 149944 138738 128823 82776 77557 51994 74322 64716 114506 124074
+          73096 97066 96731 149307 135626 121413 69575 98581 50570 60754 94843 72165
+          146504 53290 63491 50936 79644 119081 70218 85849 133228 114550 131943
+          67288 68499 80512 148872 99264 119723 68295 90348 146534 52661 99146 95993
+          130363 78956 126736 82065 77227 129950 97946 132345 107137 79623 148477
+          88928 118911 75277 97162 80664 149742 88983 74518))
+
+(defun calculate-fuel (mass)
+  (- (/ mass 3) 2))
+
+(message "Solution to day1/1: %d" (apply #'+ (-map #'calculate-fuel day-1/input)))
+
+;; Puzzle 2:
+(defun calculate-recursive-fuel (mass)
+  (let ((fuel (calculate-fuel mass)))
+    (if (< fuel 0) 0
+      (+ fuel (calculate-recursive-fuel fuel)))))
+
+(message "Solution to day1/2: %d" (apply #'+ (-map #'calculate-recursive-fuel day-1/input)))
diff --git a/users/tazjin/aoc2019/solution-day2.el b/users/tazjin/aoc2019/solution-day2.el
new file mode 100644
index 000000000000..6ecac1e2016c
--- /dev/null
+++ b/users/tazjin/aoc2019/solution-day2.el
@@ -0,0 +1,53 @@
+;; -*- lexical-binding: t; -*-
+;; Advent of Code 2019 - Day 2
+(require 'dash)
+(require 'ht)
+
+(defvar day2/input
+  [1 0 0 3 1 1 2 3 1 3 4 3 1 5 0 3 2 1 9 19 1 19 5 23 1 13 23 27 1 27 6 31
+     2 31 6 35 2 6 35 39 1 39 5 43 1 13 43 47 1 6 47 51 2 13 51 55 1 10 55
+     59 1 59 5 63 1 10 63 67 1 67 5 71 1 71 10 75 1 9 75 79 2 13 79 83 1 9
+     83 87 2 87 13 91 1 10 91 95 1 95 9 99 1 13 99 103 2 103 13 107 1 107 10
+     111 2 10 111 115 1 115 9 119 2 119 6 123 1 5 123 127 1 5 127 131 1 10
+     131 135 1 135 6 139 1 10 139 143 1 143 6 147 2 147 13 151 1 5 151 155 1
+     155 5 159 1 159 2 163 1 163 9 0 99 2 14 0 0])
+
+;; Puzzle 1
+
+(defun day2/single-op (f state idx)
+  (let* ((a (aref state (aref state (+ 1 idx))))
+         (b (aref state (aref state (+ 2 idx))))
+         (p (aref state (+ 3 idx)))
+         (result (funcall f a b)))
+    (aset state p (funcall f a b))))
+
+(defun day2/operate (state idx)
+  (pcase (aref state idx)
+    (99 (aref state 0))
+    (1 (day2/single-op #'+ state idx)
+       (day2/operate state (+ 4 idx)))
+    (2 (day2/single-op #'* state idx)
+       (day2/operate state (+ 4 idx)))
+    (other (error "Unknown opcode: %s" other))))
+
+(defun day2/program-with-inputs (noun verb)
+  (let* ((input (copy-tree day2/input t)))
+    (aset input 1 noun)
+    (aset input 2 verb)
+    (day2/operate input 0)))
+
+(message "Solution to day2/1: %s" (day2/program-with-inputs 12 2))
+
+;; Puzzle 2
+(let* ((used (ht))
+       (noun 0)
+       (verb 0)
+       (result (day2/program-with-inputs noun verb)))
+  (while (/= 19690720 result)
+    (setq noun (random 100))
+    (setq verb (random 100))
+    (unless (ht-get used (format "%d%d" noun verb))
+      (ht-set used (format "%d%d" noun verb) t)
+      (setq result (day2/program-with-inputs noun verb))))
+
+  (message "Solution to day2/2: %s%s" noun verb))
diff --git a/users/tazjin/aoc2019/solution-day3.el b/users/tazjin/aoc2019/solution-day3.el
new file mode 100644
index 000000000000..b7dfdd245fb1
--- /dev/null
+++ b/users/tazjin/aoc2019/solution-day3.el
@@ -0,0 +1,64 @@
+;; -*- lexical-binding: t; -*-
+;; Advent of Code 2019 - Day 3
+
+(require 'cl-lib)
+(require 'dash)
+(require 'ht)
+(require 's)
+
+(defvar day3/input/wire1
+  "R1010,D422,L354,U494,L686,U894,R212,U777,L216,U9,L374,U77,R947,U385,L170,U916,R492,D553,L992,D890,L531,U360,R128,U653,L362,U522,R817,U198,L126,D629,L569,U300,L241,U145,R889,D196,L450,D576,L319,D147,R985,U889,L941,U837,L608,D77,L864,U911,L270,D869,R771,U132,L249,U603,L36,D328,L597,U992,L733,D370,L947,D595,L308,U536,L145,U318,R55,D773,R175,D505,R483,D13,R780,U778,R445,D107,R490,U245,L587,U502,R446,U639,R150,U35,L455,D522,R866,U858,R394,D975,R513,D378,R58,D646,L374,D675,R209,U228,R530,U543,L480,U677,L912,D164,L573,U587,L784,D626,L994,U250,L215,U985,R684,D79,L877,U811,L766,U617,L665,D246,L408,U800,L360,D272,L436,U138,R240,U735,L681,U68,L608,D59,R532,D808,L104,U968,R887,U819,R346,U698,L317,U582,R516,U55,L303,U607,L457,U479,L510,D366,L583,U519,R878,D195,R970,D267,R842,U784,R9,D946,R833,D238,L232,D94,L860,D47,L346,U951,R491,D745,R849,U273,R263,U392,L341,D808,R696,U326,R886,D296,L865,U833,R241,U644,R729,D216,R661,D712,L466,D699,L738,U5,L556,D693,R912,D13,R48,U63,L877,U628,L689,D929,R74,U924,R612,U153,R417,U425,L879,D378,R79,D248,L3,U519,R366,U281,R439,D823,R149,D668,R326,D342,L213,D735,R504,U265,L718,D842,L565,U105,L214,U963,R518,D681,R642,U170,L111,U6,R697,U572,R18,U331,L618,D255,R534,D322,L399,U595,L246,U651,L836,U757,R417,D795,R291,U759,L568,U965,R828,D570,R350,U317,R338,D173,L74,D833,L650,D844,L70,U913,R594,U407,R674,D684,L481,D564,L128,D277,R851,D274,L435,D582,R469,U729,R387,D818,R443,U504,R414,U8,L842,U845,R275,U986,R53,U660,R661,D225,R614,U159,R477")
+
+(defvar day3/input/wire2
+  "L1010,D698,R442,U660,L719,U702,L456,D86,R938,D177,L835,D639,R166,D285,L694,U468,L569,D104,L234,D574,L669,U299,L124,D275,L179,D519,R617,U72,L985,D248,R257,D276,L759,D834,R490,U864,L406,U181,R911,U873,R261,D864,R260,U759,R648,U158,R308,D386,L835,D27,L745,U91,R840,U707,R275,U543,L663,U736,L617,D699,R924,U103,R225,U455,R708,U319,R569,U38,R315,D432,L179,D975,R519,D546,L295,U680,L685,U603,R262,D250,R7,U171,R261,U519,L832,U534,L471,U431,L474,U886,R10,D179,L79,D555,R452,U452,L832,U863,L367,U538,L237,D160,R441,U605,R942,U259,L811,D552,R646,D353,L225,D94,L35,D307,R752,U23,R698,U610,L379,D932,R698,D751,R178,D347,R325,D156,R471,D555,R558,D593,R773,U2,L955,U764,L735,U438,R364,D640,L757,U534,R919,U409,R361,U407,R336,D808,R877,D648,R610,U198,R340,U94,R795,D667,R811,U975,L965,D224,R565,D681,L64,U567,R621,U922,L665,U329,R242,U592,L727,D481,L339,U402,R213,D280,R656,U169,R976,D962,L294,D505,L251,D689,L497,U133,R230,D441,L90,D220,L896,D657,L500,U331,R502,U723,R762,D613,L447,D256,L226,U309,L935,U384,L740,D459,R309,D707,R952,D747,L304,D105,R977,D539,R941,D21,R291,U216,R132,D543,R515,U453,L854,D42,R982,U102,L469,D639,R559,D68,R302,U734,R980,D214,R107,D191,L730,D793,L63,U17,R807,U196,R412,D592,R330,D941,L87,D291,L44,D94,L272,D780,R968,U837,L712,D704,R163,U981,R537,U778,R220,D303,L196,D951,R163,D446,R11,D623,L72,D778,L158,U660,L189,D510,L247,D716,L89,U887,L115,U114,L36,U81,R927,U293,L265,U183,R331,D267,R745,D298,L561,D918,R299,U810,L322,U679,L739,D854,L581,U34,L862,D779,R23")
+
+;; Puzzle 1
+
+(defun wire-from (raw)
+  (-map (lambda (s)
+          (cons (substring s 0 1) (string-to-number (substring s 1))))
+        (s-split "," raw)))
+
+(defun day3/move (x y next)
+  (cl-flet ((steps (by op)
+                   (-map op (reverse (number-sequence 1 by)))))
+    (pcase next
+      (`("L" . ,by) (steps by (lambda (n) (cons (- x n) y))))
+      (`("R" . ,by) (steps by (lambda (n) (cons (+ x n) y))))
+      (`("U" . ,by) (steps by (lambda (n) (cons x (+ y n)))))
+      (`("D" . ,by) (steps by (lambda (n) (cons x (- y n))))))))
+
+(defun day3/wire-points (wire)
+  (let ((points (ht))
+        (point-list (-reduce-from
+                     (lambda (acc point)
+                       (-let* (((x . y) (car acc))
+                               (next (day3/move x y point)))
+                         (-concat next acc)))
+                     '((0 . 0)) wire)))
+    (-map (-lambda ((s . p)) (ht-set! points p s))
+          (-zip (reverse (number-sequence 0 (- (length point-list) 1))) point-list))
+    (ht-remove! points '(0 . 0))
+    points))
+
+(defun day3/closest-intersection (crossed-points)
+  (car (-sort #'<
+              (-map (-lambda ((x . y))
+                      (+ (abs x) (abs y)))
+                    crossed-points))))
+
+(defun day3/minimum-steps (wire1 wire2 crossed)
+  (car (-sort #'<
+              (-map (-lambda (p)
+                      (+ (ht-get wire1 p) (ht-get wire2 p)))
+                    crossed))))
+
+;; Example:
+(let* ((wire1-points (day3/wire-points (wire-from day3/input/wire1)))
+       (wire2-points (day3/wire-points (wire-from day3/input/wire2)))
+       (crossed-points (-filter (lambda (p) (ht-contains? wire1-points p))
+                                (ht-keys wire2-points))))
+  (message "Solution for day3/1: %d" (day3/closest-intersection crossed-points))
+  (message "Solution for day3/2: %d" (day3/minimum-steps wire1-points
+                                                         wire2-points
+                                                         crossed-points)))
diff --git a/users/tazjin/aoc2019/solution-day4.el b/users/tazjin/aoc2019/solution-day4.el
new file mode 100644
index 000000000000..2805f3f4e9cd
--- /dev/null
+++ b/users/tazjin/aoc2019/solution-day4.el
@@ -0,0 +1,73 @@
+;; -*- lexical-binding: t; -*-
+;; Advent of Code 2019 - Day 4
+
+(require 'cl-lib)
+(require 'dash)
+
+;; Puzzle 1
+
+(defun day4/to-digits (num)
+  "Convert NUM to a list of its digits."
+  (cl-labels ((steps (n digits)
+                     (if (= n 0) digits
+                       (steps (/ n 10) (cons (% n 10) digits)))))
+    (steps num '())))
+
+(defvar day4/input (-map #'day4/to-digits (number-sequence 128392 643281)))
+
+(defun day4/filter-password (digits)
+  "Determines whether the given rules match the supplied
+  number."
+
+  (and
+   ;; It is a six digit number
+   (= 6 (length digits))
+
+   ;; Value is within the range given in puzzle input
+   ;; (noop because the range is generated from the input)
+
+   ;; Two adjacent digits are the same (like 22 in 122345).
+   (car (-reduce-from (-lambda ((acc . prev) next)
+                        (cons (or acc (= prev next)) next))
+                      '(nil . 0) digits))
+
+   ;; Going from left to right, the digits never decrease; they only
+   ;; ever increase or stay the same (like 111123 or 135679).
+   (car (-reduce-from (-lambda ((acc . prev) next)
+                        (cons (and acc (>= next prev)) next))
+                      '(t . 0) digits))))
+
+;; Puzzle 2
+;;
+;; Additional criteria: If there's matching digits, they're not in a group.
+
+(cl-defstruct day4/acc state prev count)
+
+(defun day4/filter-longer-groups (digits)
+  (let ((res (-reduce-from
+              (lambda (acc next)
+                (cond ;; sequence is broken and count was at 1 ->
+                 ;; match!
+                 ((and (= (day4/acc-count acc) 2)
+                       (/= (day4/acc-prev acc) next))
+                  (setf (day4/acc-state acc) t))
+
+                 ;; sequence continues, counter increment!
+                 ((= (day4/acc-prev acc) next)
+                  (setf (day4/acc-count acc) (+ 1 (day4/acc-count acc))))
+
+                 ;; sequence broken, reset counter
+                 ((/= (day4/acc-prev acc) next)
+                  (setf (day4/acc-count acc) 1)))
+
+                (setf (day4/acc-prev acc) next)
+                acc)
+              (make-day4/acc :prev 0 :count 0) digits)))
+    (or (day4/acc-state res)
+        (= 2 (day4/acc-count res)))))
+
+(let* ((simple (-filter #'day4/filter-password day4/input))
+       (complex (-filter #'day4/filter-longer-groups simple)))
+  (message "Solution to day4/1: %d" (length simple))
+  (message "Solution to day4/2: %d" (length complex)))
+