From 6c08bcc84d51fd5a1a5152b3c611df44c93a3f00 Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Tue, 1 Dec 2020 13:12:07 +0100 Subject: chore(tazjin/aoc2019): Move out of //fun Change-Id: I9d065b672f4245b81444737dd900c8864447bc4d Reviewed-on: https://cl.tvl.fyi/c/depot/+/2211 Tested-by: BuildkiteCI Reviewed-by: tazjin --- users/tazjin/aoc2019/default.nix | 22 +++++++++++ users/tazjin/aoc2019/solution-day1.el | 28 ++++++++++++++ users/tazjin/aoc2019/solution-day2.el | 53 +++++++++++++++++++++++++ users/tazjin/aoc2019/solution-day3.el | 64 ++++++++++++++++++++++++++++++ users/tazjin/aoc2019/solution-day4.el | 73 +++++++++++++++++++++++++++++++++++ 5 files changed, 240 insertions(+) create mode 100644 users/tazjin/aoc2019/default.nix create mode 100644 users/tazjin/aoc2019/solution-day1.el create mode 100644 users/tazjin/aoc2019/solution-day2.el create mode 100644 users/tazjin/aoc2019/solution-day3.el create mode 100644 users/tazjin/aoc2019/solution-day4.el (limited to 'users/tazjin/aoc2019') 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))) + -- cgit 1.4.1