# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1639417350 18000
# Node ID 6614131d7b10260a250d9caa7a700cbe0d55cfc0
# Parent  9312a3a851ccc53099d48e6b86bb7b05c59f1979
2021/11 2021/12 2021/13

diff -r 9312a3a851cc -r 6614131d7b10 data/2021/11.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/data/2021/11.txt	Mon Dec 13 12:42:30 2021 -0500
@@ -0,0 +1,10 @@
+2682551651
+3223134263
+5848471412
+7438334862
+8731321573
+6415233574
+5564726843
+6683456445
+8582346112
+4617588236
diff -r 9312a3a851cc -r 6614131d7b10 data/2021/12.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/data/2021/12.txt	Mon Dec 13 12:42:30 2021 -0500
@@ -0,0 +1,20 @@
+VJ-nx
+start-sv
+nx-UL
+FN-nx
+FN-zl
+end-VJ
+sv-hi
+em-VJ
+start-hi
+sv-em
+end-zl
+zl-em
+hi-VJ
+FN-em
+start-VJ
+jx-FN
+zl-sv
+FN-sv
+FN-hi
+nx-end
diff -r 9312a3a851cc -r 6614131d7b10 data/2021/13.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/data/2021/13.txt	Mon Dec 13 12:42:30 2021 -0500
@@ -0,0 +1,833 @@
+296,446
+559,232
+754,329
+1238,577
+1155,754
+378,674
+1064,567
+1310,206
+171,82
+1228,892
+890,114
+806,565
+408,558
+1210,347
+53,845
+636,836
+907,133
+1299,852
+967,333
+956,815
+1238,471
+1136,577
+853,849
+15,9
+522,392
+176,887
+877,67
+228,565
+952,861
+595,712
+715,264
+1043,854
+1014,476
+952,555
+94,199
+1019,297
+915,259
+242,338
+1014,787
+1236,770
+654,16
+453,562
+964,892
+1037,341
+964,129
+15,602
+546,367
+1089,422
+1099,477
+905,490
+279,477
+1078,404
+1298,439
+493,100
+566,12
+616,476
+1110,668
+1203,698
+1022,810
+1128,648
+1128,849
+967,490
+70,114
+1078,247
+624,28
+867,318
+529,546
+756,500
+1046,690
+1084,824
+642,96
+585,719
+209,88
+119,140
+771,29
+296,418
+1146,520
+1049,246
+1141,861
+1119,285
+554,652
+15,210
+478,7
+164,101
+788,616
+554,294
+954,77
+716,161
+703,831
+223,376
+1139,812
+771,128
+131,478
+895,649
+300,79
+1031,252
+1014,642
+668,439
+550,228
+904,450
+937,277
+867,352
+1266,780
+80,0
+1208,325
+1064,0
+406,682
+430,556
+1195,29
+1076,452
+1178,616
+527,570
+320,31
+373,165
+358,339
+453,105
+668,217
+788,866
+232,404
+862,502
+929,553
+813,47
+982,838
+1242,740
+952,221
+766,39
+100,500
+907,593
+223,294
+464,91
+981,336
+997,155
+326,56
+131,864
+100,347
+283,194
+1067,548
+1210,276
+544,631
+624,413
+744,124
+1222,124
+1002,577
+935,418
+1248,690
+964,450
+808,505
+1201,733
+107,644
+296,476
+131,416
+1002,836
+222,196
+1175,654
+567,369
+661,163
+1293,61
+1146,374
+576,58
+493,794
+699,656
+530,840
+662,863
+624,448
+309,509
+1109,777
+420,666
+482,414
+992,136
+296,787
+87,21
+1153,470
+1283,357
+354,367
+276,680
+1145,346
+510,648
+12,679
+552,674
+381,341
+300,815
+452,320
+54,712
+817,100
+271,298
+989,800
+857,49
+303,831
+688,108
+1149,234
+604,892
+274,71
+753,826
+258,359
+382,406
+87,873
+350,442
+68,154
+445,88
+750,266
+328,654
+185,740
+247,604
+554,515
+691,673
+782,338
+453,497
+1133,484
+264,690
+1218,218
+177,410
+365,343
+239,873
+431,600
+85,180
+371,327
+507,716
+962,214
+1092,367
+244,782
+801,509
+601,845
+1022,252
+882,376
+266,791
+164,569
+1243,187
+1027,700
+1148,392
+1216,880
+1056,541
+1195,542
+408,448
+977,94
+358,787
+554,276
+475,82
+12,889
+554,379
+1029,725
+264,196
+1101,88
+83,492
+202,616
+758,674
+299,509
+788,115
+1044,103
+234,4
+443,418
+858,320
+864,607
+756,518
+95,35
+648,863
+952,107
+267,854
+200,714
+80,205
+828,256
+366,252
+42,782
+1159,495
+1218,795
+600,264
+172,256
+969,199
+314,663
+857,789
+217,117
+1280,555
+1082,565
+1297,199
+634,2
+249,490
+132,616
+1228,444
+999,358
+765,733
+1156,190
+813,847
+311,358
+907,73
+1155,364
+1173,329
+289,343
+944,642
+922,469
+256,53
+251,593
+306,662
+666,375
+488,894
+1265,165
+642,217
+820,464
+393,745
+674,892
+761,248
+1210,547
+343,378
+294,562
+853,368
+74,770
+371,460
+105,24
+1113,849
+1039,746
+264,756
+507,194
+656,166
+289,551
+984,464
+1275,53
+381,553
+1,234
+209,806
+453,332
+624,866
+358,861
+567,525
+492,297
+619,225
+781,777
+1160,777
+174,374
+234,562
+557,182
+760,442
+30,866
+1205,472
+850,115
+544,756
+375,476
+97,826
+1139,292
+654,81
+296,225
+796,452
+880,338
+407,290
+68,311
+329,558
+42,334
+562,228
+1088,521
+999,404
+10,744
+654,688
+1071,873
+231,707
+264,652
+0,793
+1131,781
+1053,810
+959,831
+1200,301
+1185,49
+296,252
+308,836
+967,516
+1029,729
+320,353
+308,220
+154,190
+1081,516
+780,840
+1136,317
+1138,480
+443,318
+587,74
+475,44
+482,256
+639,716
+581,308
+1027,154
+1,660
+776,252
+35,112
+135,240
+403,73
+1231,458
+1006,890
+157,731
+271,746
+67,187
+1134,455
+927,596
+36,271
+343,113
+408,446
+890,452
+425,760
+765,777
+709,397
+642,455
+939,327
+446,607
+1223,817
+244,821
+1223,425
+1081,378
+229,378
+803,700
+877,198
+1231,436
+745,460
+550,754
+1149,112
+1066,112
+320,703
+1108,581
+165,560
+781,497
+1266,114
+249,154
+5,267
+1021,562
+35,745
+577,180
+1019,149
+87,369
+454,108
+428,376
+1139,28
+800,269
+715,182
+715,630
+750,647
+62,204
+632,676
+962,680
+758,220
+453,786
+582,245
+272,859
+38,476
+489,346
+488,450
+766,756
+161,212
+94,714
+465,117
+1056,247
+944,252
+222,890
+1287,511
+492,597
+283,740
+1250,14
+211,495
+686,339
+1241,308
+694,476
+1031,417
+490,430
+216,183
+157,175
+1146,430
+410,334
+1250,873
+313,259
+807,511
+686,28
+781,546
+556,329
+1022,84
+970,215
+251,749
+320,191
+1300,519
+1125,154
+529,777
+218,866
+595,630
+222,756
+341,199
+1108,313
+1288,442
+1228,17
+1230,894
+751,232
+643,607
+785,393
+884,693
+18,836
+1184,556
+311,404
+452,726
+1225,852
+750,247
+807,383
+477,483
+1014,252
+346,129
+433,67
+967,113
+37,252
+1251,182
+1054,332
+596,330
+867,399
+375,253
+443,399
+382,187
+594,161
+1116,115
+1248,204
+1218,556
+892,151
+1128,829
+387,712
+510,269
+594,385
+283,567
+366,642
+155,754
+88,770
+882,294
+639,516
+592,810
+373,185
+562,666
+69,623
+594,598
+199,169
+477,35
+482,480
+1049,872
+151,399
+1029,281
+211,477
+341,186
+1257,49
+502,505
+893,460
+967,714
+1238,201
+1222,322
+100,52
+1019,0
+944,532
+15,885
+1131,113
+309,385
+1002,220
+1213,68
+920,885
+281,725
+311,561
+398,562
+1191,551
+437,833
+62,662
+1149,794
+497,175
+428,204
+72,423
+1084,518
+653,212
+607,253
+1066,821
+89,460
+530,574
+1225,42
+952,787
+643,287
+488,24
+200,180
+699,208
+1185,565
+967,358
+1218,99
+497,399
+82,450
+1223,873
+1022,686
+1064,327
+976,353
+15,233
+601,117
+509,509
+405,852
+405,404
+1061,154
+489,782
+642,663
+611,602
+291,297
+1046,756
+733,180
+110,711
+291,8
+1029,169
+92,218
+821,782
+1205,291
+283,292
+882,204
+656,365
+822,0
+243,548
+443,417
+22,442
+288,686
+1086,14
+999,561
+974,758
+534,642
+407,436
+418,151
+1029,633
+351,831
+669,247
+1156,704
+60,780
+197,45
+759,331
+1295,806
+490,414
+997,259
+22,676
+989,94
+246,121
+161,334
+279,417
+668,5
+1179,416
+281,729
+15,806
+361,32
+126,338
+365,114
+365,623
+1099,417
+44,114
+756,276
+724,154
+373,281
+1257,845
+796,442
+1226,450
+592,612
+162,840
+530,54
+1287,383
+1242,647
+827,82
+221,422
+426,201
+756,618
+723,74
+234,452
+211,417
+857,105
+1027,140
+383,596
+283,700
+929,341
+306,641
+1310,345
+94,266
+1206,698
+667,287
+1029,261
+835,44
+631,63
+488,870
+433,696
+728,649
+454,786
+709,845
+366,810
+316,317
+1006,4
+246,327
+363,893
+676,450
+346,892
+457,401
+654,878
+313,35
+412,444
+1002,317
+104,666
+1029,617
+42,560
+1146,101
+355,206
+1295,602
+549,248
+676,2
+1111,469
+1093,565
+390,84
+161,660
+0,345
+1149,346
+723,820
+1036,599
+544,855
+1088,4
+530,392
+1275,112
+1019,393
+1166,625
+283,754
+542,81
+821,112
+862,392
+333,94
+420,452
+554,824
+699,292
+1298,889
+436,866
+788,278
+12,96
+1275,73
+912,562
+599,698
+586,602
+1238,319
+560,647
+1046,652
+902,448
+80,689
+242,444
+554,376
+281,261
+436,815
+1297,291
+201,49
+234,332
+796,890
+232,490
+679,319
+624,481
+288,84
+232,647
+11,287
+231,187
+244,429
+125,329
+0,206
+298,817
+1299,735
+1216,714
+994,317
+291,0
+221,472
+72,649
+171,866
+619,669
+248,506
+1149,334
+499,364
+490,325
+272,411
+607,831
+313,739
+318,136
+453,796
+1111,357
+609,729
+1064,110
+739,492
+817,794
+217,565
+218,367
+830,72
+1280,866
+418,743
+329,784
+60,598
+161,682
+932,276
+161,234
+600,859
+656,878
+82,892
+663,317
+904,444
+1228,450
+917,297
+503,383
+472,648
+88,124
+37,642
+1210,742
+248,836
+879,742
+1044,791
+1081,488
+768,81
+363,448
+872,711
+562,676
+1004,641
+144,625
+653,682
+756,416
+1010,815
+390,242
+191,14
+194,563
+1082,329
+229,516
+485,771
+162,480
+1191,343
+171,812
+10,822
+1138,256
+710,182
+1297,647
+182,648
+1014,446
+165,346
+748,228
+
+fold along x=655
+fold along y=447
+fold along x=327
+fold along y=223
+fold along x=163
+fold along y=111
+fold along x=81
+fold along y=55
+fold along x=40
+fold along y=27
+fold along y=13
+fold along y=6
diff -r 9312a3a851cc -r 6614131d7b10 src/2021/days/day-11.lisp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/2021/days/day-11.lisp	Mon Dec 13 12:42:30 2021 -0500
@@ -0,0 +1,48 @@
+(advent:defpackage* :advent/2021/11)
+(in-package :advent/2021/11)
+
+(defun simulate (data steps &aux (result 0))
+  (destructuring-bind (rows cols) (array-dimensions data)
+    (iterate
+      (for step :from 0)
+      (for flashed-this-round = 0)
+      (for to-flash = '())
+      (when steps
+        (until (= step steps)))
+      (labels ((inc (r c)
+                 (when (array-in-bounds-p data r c)
+                   (when (= 10 (incf (aref data r c)))
+                     (push (cons r c) to-flash))))
+               (initial-phase ()
+                 (do-range ((r 0 rows)
+                            (c 0 cols))
+                   (inc r c)))
+               (flash (row col)
+                 (incf flashed-this-round)
+                 (iterate
+                   (for (r c) :within-radius 1 :origin (row col) :skip-origin t)
+                   (inc r c)))
+               (flashing-phase ()
+                 (iterate (while to-flash)
+                          (for (r . c) = (pop to-flash))
+                          (flash r c)))
+               (reset-phase ()
+                 (do-array (n data)
+                   (when (>= n 10)
+                     (setf n 0)))))
+        (initial-phase)
+        (flashing-phase)
+        (reset-phase))
+      (if steps
+        (incf result flashed-this-round) ; part 1
+        (when (= flashed-this-round (* rows cols)) ; part 2
+          (return-from simulate (1+ step))))))
+  result)
+
+(define-problem (2021 11) (stream) (1594 437)
+  (let ((data (read-2d-array stream :key #'digit-char-p)))
+    (values (simulate (alexandria:copy-array data) 100)
+            (simulate (alexandria:copy-array data) nil))))
+
+
+#; Scratch --------------------------------------------------------------------
diff -r 9312a3a851cc -r 6614131d7b10 src/2021/days/day-12.lisp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/2021/days/day-12.lisp	Mon Dec 13 12:42:30 2021 -0500
@@ -0,0 +1,54 @@
+(advent:defpackage* :advent/2021/12)
+(in-package :advent/2021/12)
+
+(defun edge (graph from to)
+  (push to (gethash from graph))
+  (push from (gethash to graph)))
+
+(defun parse (stream)
+  (iterate
+    (with-result graph = (make-hash-table))
+    (for line :in-stream stream :using #'read-line)
+    (for (from to) = (str:split #\- line))
+    (edge graph (intern from :advent/2021/12) (intern to :advent/2021/12))))
+
+(defun bigp (cave)
+  (upper-case-p (char (symbol-name cave) 0)))
+
+(defun restrict-small-1 (node path)
+  (member node path))
+
+(defun used-small-twice (path)
+  ;; todo do something faster than this
+  (iterate (for (a . rest) :on path)
+           (unless (bigp a)
+             (dolist (b rest)
+               (thereis (eql a b))))))
+
+(defun restrict-small-2 (node path)
+  (cond
+    ((member node '(|start| |end|)) (member node path))
+    ((used-small-twice path) (member node path))
+    (t (member node (rest (member node path))))))
+
+(defun neighbors (graph path &key restriction)
+  (iterate (for node :in (gethash (first path) graph))
+           (when (or (bigp node) (not (funcall restriction node path)))
+             (collect node))))
+
+(defun paths (graph &key restriction)
+  (recursively ((path '(|start|)))
+    (if (eql '|end| (first path))
+      1
+      (iterate (for next :in (neighbors graph path :restriction restriction))
+               (summing (recur (cons next path)))))))
+
+(define-problem (2021 12) (graph parse) (5254 149385)
+  (values (paths graph :restriction #'restrict-small-1)
+          (paths graph :restriction #'restrict-small-2)))
+
+
+
+
+#; Scratch --------------------------------------------------------------------
+
diff -r 9312a3a851cc -r 6614131d7b10 src/2021/days/day-13.lisp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/2021/days/day-13.lisp	Mon Dec 13 12:42:30 2021 -0500
@@ -0,0 +1,47 @@
+(advent:defpackage* :advent/2021/13)
+(in-package :advent/2021/13)
+
+(defun dot (x y) (complex x y))
+(defun x (dot) (realpart dot))
+(defun y (dot) (imagpart dot))
+
+(defun parse (lines)
+  (iterate
+    (for line :in lines)
+    (ppcre:register-groups-bind ((#'parse-integer x y)) ("(\\d+),(\\d+)" line)
+      (collect (dot x y) :into dots))
+    (ppcre:register-groups-bind (axis n) ("fold along ([xy])=(\\d+)" line)
+      (collect (cons (char axis 0) (parse-integer n)) :into folds))
+    (returning dots folds)))
+
+(defun fold% (fold dot)
+  (destructuring-bind (axis . n) fold
+    (ecase axis
+      (#\x (if (> (x dot) n)
+             (complex (- n (- (x dot) n)) (y dot))
+             dot))
+      (#\y (if (> (y dot) n)
+             (complex (x dot) (- n (- (y dot) n)))
+             dot)))))
+
+(defun fold (fold dots)
+  (map-into dots (curry #'fold% fold) dots))
+
+(defun dots-to-hash-table (dots)
+  (iterate (for dot :in dots) (collect-hash (dot #\█))))
+
+(defun part1 (dots folds &aux (dots (copy-list dots)))
+  (length (remove-duplicates (fold (first folds) dots))))
+
+(defun part2 (dots folds &aux (dots (copy-list dots)))
+  (map nil (rcurry #'fold dots) folds)
+  ;; (print-hash-table-map (dots-to-hash-table dots) :flip-y t)
+  "WELP") ; My part 2 answer contains a slur so let's not hardcode THAT test case here.
+
+(define-problem (2021 13) (lines read-lines) (682 "WELP")
+  (multiple-value-bind (dots folds) (parse lines)
+    (values (part1 dots folds)
+            (part2 dots folds))))
+
+#; Scratch --------------------------------------------------------------------
+