From f3ef9e6eadb92abf7aeb6f22a12a87bde6433470 Mon Sep 17 00:00:00 2001 From: Oscar Najera Date: Tue, 5 Dec 2023 09:32:53 +0100 Subject: [AoC2023] day05 lisp too slow --- AoC2023/day05/input | 197 ++++++++++++++++++++++++++++++++++++++++++++++ AoC2023/day05/solver.lisp | 117 +++++++++++++++++++++++++++ 2 files changed, 314 insertions(+) create mode 100644 AoC2023/day05/input create mode 100644 AoC2023/day05/solver.lisp 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"))))) -- cgit v1.2.3