[AoC2023] day05 lisp too slow

2 files changed, 314 insertions, 0 deletions

diff --git a/AoC2023/day05/input b/AoC2023/day05/input
new file mode 100644
index 0000000..6808607
--- /dev/null
+++ b/AoC2023/day05/input
@@ -0,0 +1,197 @@
+seeds: 1972667147 405592018 1450194064 27782252 348350443 61862174 3911195009 181169206 626861593 138786487 2886966111 275299008 825403564 478003391 514585599 6102091 2526020300 15491453 3211013652 546191739
+
+seed-to-soil map:
+325190047 421798005 78544109
+4034765382 1473940091 137996533
+403734156 658668780 288666603
+2574766003 2624114227 17352982
+1931650757 2203381572 98211987
+4263596455 2843660329 31370841
+1614547845 2641467209 55121215
+3441604278 2032673361 170708211
+692400759 563703672 94965108
+2992851755 3824700930 114550818
+3957953582 2540115966 24844899
+0 500342114 59804107
+4172761915 2577017231 47096996
+2029862744 3548344768 52256082
+2620304610 2875031170 99567251
+3982798481 3939251748 51966901
+2325101894 1616388089 203150170
+3612312489 1611936624 4451465
+787365867 0 77461445
+1341614907 4162572181 132395115
+2542801978 3468402968 31964025
+223387052 947335383 59156225
+2297805420 1819538259 27296474
+2082118826 3991218649 171353532
+3374211778 3040047171 67392500
+2592118985 1341614907 28185625
+2253472358 2495782904 44333062
+4219858911 3780963386 43737544
+59804107 560146221 3557451
+3107402573 3600600850 64973479
+1669669060 3115086052 235712356
+2719871861 1369800532 104139559
+3172376052 2301593559 194189345
+2980795389 2564960865 12056366
+1905381416 3350798408 26269341
+63361558 261772511 160025494
+2824011420 3377067749 91335219
+3366565397 3107439671 7646381
+282543277 77461445 42646770
+3713793353 2696588424 147071905
+2528252064 1877585624 14549914
+3927202691 1846834733 30750891
+3665815578 3500366993 47977775
+1474010022 1892135538 140537823
+3616763954 3665574329 49051624
+2915346639 2974598421 65448750
+864827312 120108215 141664296
+3860865258 3714625953 66337433
+
+soil-to-fertilizer map:
+3835605444 4098164436 1662218
+682286299 0 63480553
+396476124 2072802434 285810175
+1644893571 655614677 162631098
+3625179075 4099826654 40627721
+1431211762 1859120625 213681809
+2853687843 4140454375 103601386
+1390165578 2358612609 41046184
+2405285827 3959200676 138963760
+900243562 1478767251 170015757
+3727732722 3084190064 107872722
+893948759 1084467374 6294803
+210337617 818245775 186138507
+1807524669 63480553 592134124
+825849944 1090762177 68098815
+3837267662 3192062786 457699634
+0 1648783008 210337617
+3665806796 2405285827 61925926
+1070259319 1158860992 319906259
+745766852 1004384282 80083092
+2957289229 4244055761 50911535
+2544249587 3649762420 309438256
+3008200764 2467211753 616978311
+
+fertilizer-to-water map:
+1169336944 3024036226 46676171
+1263157944 1445876546 148868263
+2080390054 2683279801 65621604
+949040795 1266013203 61140343
+2146011658 2793621589 110265098
+525510412 2618124082 65155719
+2977122301 3122211455 179751286
+3885825304 713560214 409141992
+1081017627 4124851079 88319317
+590666131 2039951828 38597255
+3596454634 1981772613 58179215
+2256276756 2078549083 315165891
+1639631621 1122702206 143310997
+2858399301 1327153546 118723000
+3654633849 3301962741 72039868
+749412925 3549292249 161128796
+1412026207 541983534 151190298
+1054901322 4268850991 26116305
+1829368778 3374002609 175289640
+1216013115 2570979253 47144829
+2806900243 3070712397 51499058
+1563216505 3760425124 76415116
+1782942618 3710421045 29953038
+629263386 2903886687 120149539
+2060339013 3740374083 20051041
+3156873587 3836840240 52553243
+2693038006 4010988842 113862237
+3726673717 2411827666 159151587
+2004658418 4213170396 55680595
+1812895656 525510412 16473122
+1010181138 2748901405 44720184
+910541721 693173832 20386382
+930928103 2393714974 18112692
+3209426830 1594744809 387027804
+2571442647 3889393483 121595359
+
+water-to-light map:
+555269773 2142838063 230952411
+2879443939 2889030006 80512763
+192641991 2686257040 106620606
+786222184 967781117 56662479
+3467110983 4162792381 132174915
+1955778230 0 505352386
+2461130616 1138855522 99691153
+1436321461 1403321335 440861327
+2625559119 1024443596 104825859
+1255310011 2792877646 96152360
+1877182788 697994377 78595442
+3732975066 3467110983 374194949
+842884663 2373790474 56459390
+299262597 2430249864 256007176
+3599285898 3841305932 133689168
+4107170015 3974995100 187797281
+0 505352386 192641991
+1090535351 1238546675 164774660
+2959956702 1129269455 9586067
+1351462371 1844182662 84859090
+2730384978 1929041752 149058961
+899344053 776589819 191191298
+2560821769 2078100713 64737350
+
+light-to-temperature map:
+4103141199 3912772142 105835099
+1994281004 833968687 112844016
+4208976298 1124841590 85990998
+3756966983 4018607241 111390720
+3868357703 1907239336 234783496
+2368591640 1210832588 293667703
+882426579 2320467318 1111854425
+3064998388 717457244 33489309
+3578938096 946812703 178028887
+2107125020 750946553 83022134
+3157760738 3432321743 421177358
+717457244 4129997961 164969335
+2190147154 2142022832 178444486
+3098487697 3853499101 59273041
+2662259343 1504500291 402739045
+
+temperature-to-humidity map:
+0 1820412620 129662806
+613828383 2855382935 55943394
+4004726464 3519717349 290240832
+769767991 99996214 1720416406
+3126066249 3043992795 475724554
+2490184397 2434241003 421141932
+129662806 1950075426 484165577
+689805485 0 79962506
+669771777 79962506 20033708
+3601790803 3809958181 402935661
+3043992795 4212893842 82073454
+
+humidity-to-location map:
+1305211417 3371927062 89487200
+947159122 0 358052295
+324330151 2021970861 8067408
+332397559 654359706 174171341
+506568900 3311893445 60033617
+11065691 828531047 45586147
+3556729147 369117986 26689998
+3583419145 395807984 258551722
+2356886904 984938593 400606547
+1394698617 874117194 110821399
+566602517 3946624826 164852367
+2998901322 2301963630 256425441
+0 358052295 11065691
+3331964991 3087129289 34908052
+1505520016 2106676497 195287133
+56651838 2819450976 267678313
+3366873043 3293025783 18867662
+3385740705 3122037341 170988442
+2281795782 2799796942 19654034
+2301449816 1966533773 55437088
+3992934054 3677118500 118543139
+3255326763 2030038269 76638228
+3849868384 3803559156 143065670
+2757493451 2558389071 241407871
+3841970867 3795661639 7897517
+1700807149 1385545140 580988633
+731454884 3461414262 215704238
diff --git a/AoC2023/day05/solver.lisp b/AoC2023/day05/solver.lisp
new file mode 100644
index 0000000..be9008e
--- /dev/null
+++ b/AoC2023/day05/solver.lisp
@@ -0,0 +1,117 @@
+(ql:quickload '(fiveam str))
+
+(defparameter eg-input "seeds: 79 14 55 13
+
+seed-to-soil map:
+50 98 2
+52 50 48
+
+soil-to-fertilizer map:
+0 15 37
+37 52 2
+39 0 15
+
+fertilizer-to-water map:
+49 53 8
+0 11 42
+42 0 7
+57 7 4
+
+water-to-light map:
+88 18 7
+18 25 70
+
+light-to-temperature map:
+45 77 23
+81 45 19
+68 64 13
+
+temperature-to-humidity map:
+0 69 1
+1 0 69
+
+humidity-to-location map:
+60 56 37
+56 93 4")
+
+
+(defun translate (rules value)
+  (dolist (rule rules)
+    (destructuring-bind (dest source span) rule
+      (when (<= source value (+ source (1- span)))
+        (return-from translate (+ (- value source) dest)))))
+  value)
+
+(defun segment-translate (rules segments)
+  (let ((sorted-rules (sort rules #'< :key #'cadr)))
+    (mapcan
+     (lambda (segment)
+       (destructuring-bind (start . end) segment
+         (loop for (dest-start source-start span) in sorted-rules
+
+               )))
+     segments)))
+
+(sort '((50 98 2) (52 50 48)) #'< :key #'cadr)
+
+(fiveam:test parts
+  (let ((rules '((50 98 2) (52 50 48))))
+    (fiveam:is (= 9 (translate rules 9)))
+    (fiveam:is (= 61 (translate rules 59)))
+    (fiveam:is (= 51 (translate rules 99)))))
+
+(defun translator (translate-chain translator-rules)
+  (lambda (value)
+    (reduce
+     (lambda (acc fn)
+       (translate (gethash fn translator-rules) acc))
+     translate-chain
+     :initial-value value)))
+
+(defun parser (lines)
+  (let (seeds
+        maps-stack
+        (translators (make-hash-table)))
+    (dolist (line lines)
+      (cond
+        ((str:emptyp line))
+        ((str:starts-with? "seeds:" line)
+         (setf seeds
+               (mapcar #'parse-integer (cdr (str:split-omit-nulls #\Space line)))))
+        ((str:ends-with-p "map:" line)
+         (push (read-from-string line) maps-stack))
+        ((push (mapcar #'parse-integer (str:split-omit-nulls #\Space line))
+               (gethash (car maps-stack) translators)))))
+    (values (translator
+             (nreverse maps-stack)
+             translators)
+            seeds)))
+
+(defun solver1 (lines)
+  (multiple-value-bind (translator seeds) (parser lines)
+    (apply #'min (mapcar translator seeds))))
+
+
+(defun solver2 (lines)
+  (multiple-value-bind (translator seeds) (parser lines)
+    (loop for (start span) on seeds by #'cddr
+          minimize (loop for i from start below (+ start span)
+                         minimize (funcall translator i)))))
+
+(fiveam:test solutions
+  (fiveam:is
+   (= 35
+      (solver1
+       (uiop:split-string eg-input :separator '(#\Newline)))))
+  (fiveam:is
+   (= 46
+      (solver2
+       (uiop:split-string eg-input :separator '(#\Newline)))))
+  (fiveam:is
+   (= 662197086
+      (solver1
+       (uiop:read-file-lines "input"))))
+  (fiveam:is
+   (= 52510809
+      (solver2
+       (uiop:read-file-lines "input")))))