From 865aaa11171035a74b6ab50835ad3d1c8625de89 Mon Sep 17 00:00:00 2001 From: Steven Le Rouzic Date: Sun, 22 Dec 2024 15:19:14 +0100 Subject: Day 22 --- day22/data.txt | 1540 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ day22/go.mod | 3 + day22/main.go | 80 +++ go.work | 1 + 4 files changed, 1624 insertions(+) create mode 100644 day22/data.txt create mode 100644 day22/go.mod create mode 100644 day22/main.go diff --git a/day22/data.txt b/day22/data.txt new file mode 100644 index 0000000..8b52446 --- /dev/null +++ b/day22/data.txt @@ -0,0 +1,1540 @@ +8651736 +10346214 +9575980 +5183003 +684973 +5894138 +8815899 +16512708 +740713 +2688774 +12368306 +15509663 +5317303 +3417624 +2163483 +2764100 +10248006 +4745199 +2859458 +16081810 +16071036 +14603940 +12907796 +5464058 +4235375 +7701083 +10265907 +12225553 +13810115 +15887463 +15079668 +2312694 +12244135 +9170465 +13195244 +6707532 +7444558 +9962890 +5219198 +5812723 +6134869 +8570223 +12391488 +6222373 +9008940 +10159430 +16096804 +1519424 +14748132 +14313276 +6388020 +13901849 +5228842 +10062629 +9451930 +5946010 +6737840 +9210879 +2311211 +11721262 +4421422 +12651905 +14737240 +12848775 +2707752 +14457090 +6174709 +4905029 +8708059 +7724646 +12802006 +3227718 +12458296 +14860354 +7636670 +760966 +11745647 +2988941 +10344109 +8490970 +14016415 +6802509 +3729369 +9293385 +2555160 +619415 +469349 +3814197 +1007176 +7960836 +11281881 +16736049 +15864495 +16237622 +3186985 +2086430 +6078268 +5630900 +15041807 +11714776 +9302839 +12246631 +13081368 +3911125 +10445659 +2506340 +4384193 +4419281 +16246762 +10925943 +14468724 +16078082 +6236517 +12329943 +16775486 +4734529 +6679371 +16709370 +8614764 +15739383 +7287930 +11758366 +13452334 +15876597 +15696122 +8792917 +15421625 +8363739 +3569831 +2988850 +11402282 +6004517 +8984771 +653343 +13699533 +5886149 +8653732 +1441909 +5050897 +7630017 +8011949 +969445 +2765518 +2543692 +9199445 +16078742 +10481176 +14591120 +16583033 +396443 +4643610 +740259 +5448498 +4571827 +8291855 +13322986 +3641429 +1695577 +12515981 +4374473 +626986 +10741555 +12093919 +1982303 +7839806 +6373766 +11385170 +1965015 +3433003 +12252221 +550321 +15443469 +3394765 +2287925 +1461602 +6985465 +2461145 +2679608 +2673856 +4163330 +2181089 +14046152 +9557129 +8322843 +3821724 +8029510 +4875094 +9051742 +918266 +15032210 +12528921 +8715236 +10730143 +6677014 +979431 +2450841 +10710177 +5197478 +2317070 +11527924 +15548890 +1510932 +2772689 +5544877 +15550910 +1330038 +12354272 +4878341 +4815043 +1437514 +16310192 +720744 +11258410 +13922674 +15265474 +4425969 +12395205 +4352483 +2635467 +11635912 +11536238 +15267155 +8711805 +2165546 +12216086 +3415759 +13624474 +11688857 +5676025 +2970181 +14921141 +10669495 +2021892 +12404822 +8984785 +6241068 +13168817 +15686284 +10901444 +8665139 +12418151 +7557663 +15671805 +1987689 +4931135 +12694495 +15076337 +16049389 +11905075 +12028812 +8076836 +8714520 +13831908 +2531615 +16269374 +6592933 +2959600 +6472913 +10322539 +16405659 +8146242 +328852 +6962304 +2081787 +1078794 +16107717 +6349625 +3108849 +13474798 +5455713 +10441485 +2210840 +5647546 +4093638 +1284565 +6678605 +12570921 +6618198 +2516906 +3626401 +10387075 +6275491 +12535802 +3331329 +7209362 +6163923 +6304004 +1883257 +11423995 +10619388 +11881825 +9676577 +12420169 +9261017 +1469546 +16597095 +2507501 +11611134 +8242870 +15551117 +1559091 +13302031 +1111804 +428071 +16364140 +9710060 +5546234 +8945092 +15253994 +8646345 +13396765 +2140651 +12400387 +8887896 +5902285 +7942980 +5886226 +13470161 +1604695 +5496042 +5819025 +9572999 +7112856 +16243905 +8858496 +13288220 +3725162 +4775161 +1184496 +16119519 +14166039 +2014725 +622602 +8845582 +4835276 +9350845 +14214660 +10767564 +14031679 +14996154 +15503966 +12674943 +3034969 +6633610 +9124178 +6230803 +1329146 +4419580 +4614330 +6489648 +9680985 +6691186 +9319854 +10696431 +6555064 +10983405 +8401889 +12765907 +7271858 +9719185 +9051954 +4271606 +1456455 +1700637 +1836845 +11683165 +5005429 +11502638 +3156222 +2453023 +3906305 +6983964 +2020883 +13776582 +16420227 +9933222 +14296055 +3324642 +12669371 +11529965 +7928827 +15211491 +1118593 +13442242 +13516563 +13086687 +1073268 +5197761 +16175814 +13807499 +14030058 +13536385 +575308 +4264684 +7055435 +5058987 +11832285 +1974449 +8885601 +1528017 +3603683 +14108927 +7893928 +12293544 +827174 +9511579 +10427667 +1173082 +4500226 +5950180 +9610014 +1896396 +14725820 +12457707 +8164443 +3959512 +14693978 +7317535 +16754694 +9429456 +12443077 +2448027 +10263915 +15088916 +16404201 +9635823 +8027199 +10837975 +9738301 +9779357 +1353002 +13826314 +11753578 +10562011 +12368414 +3574967 +4753694 +7286356 +2261010 +16655942 +5174435 +5679285 +8641288 +9664654 +16430007 +8324989 +2295106 +7545859 +14803483 +5158015 +8091305 +14285294 +15811726 +12247239 +6595964 +14435356 +760167 +14653732 +8659020 +11671412 +5205425 +8608197 +14710616 +695127 +10992272 +10697056 +14168911 +4056332 +5988810 +12789842 +3120469 +1692435 +14382025 +9447129 +8553260 +4412849 +429265 +2939184 +8537625 +6831604 +12096002 +7713220 +13924120 +14241788 +3975366 +10670836 +578191 +12162690 +13427567 +15182861 +9542829 +16404803 +5979195 +4368897 +6613276 +2106462 +10419125 +15445349 +11415713 +6953116 +6844443 +7830951 +11757751 +7768584 +5718208 +5465899 +11829254 +5714061 +391547 +5599276 +15419917 +2634439 +6385386 +3541137 +1857541 +16169911 +16585698 +12080336 +3311737 +15285706 +9009810 +16635126 +16776610 +960065 +3225555 +11757713 +3876876 +16177399 +2284730 +3203031 +3234422 +281435 +416003 +9130951 +9656665 +934797 +2027463 +6972230 +7089884 +13876122 +2033421 +12110930 +5150538 +16721426 +10619134 +5068631 +8727963 +7609983 +15780613 +9501052 +5269170 +8098469 +7434983 +7393892 +16377971 +12461813 +16223172 +9647171 +4463324 +11458103 +13128731 +1002404 +6711455 +5521419 +12689997 +16640047 +16100826 +5523647 +11855281 +15670003 +4141495 +14873792 +12293919 +15217258 +12474047 +7503855 +10494931 +15106622 +2834679 +9642794 +12075226 +16475710 +6165393 +12823933 +14834340 +5910141 +5463657 +2148540 +4992011 +317347 +12179489 +6129535 +7248139 +6713257 +16173282 +5284612 +14668667 +9516564 +11697814 +8904437 +3418752 +13068434 +13429085 +1211809 +606184 +6511439 +4125139 +6618631 +13615234 +15018259 +8932771 +6280134 +14493043 +10926888 +677252 +15338749 +2747325 +6686330 +5287368 +11299090 +8750256 +14392102 +12659460 +6034053 +388239 +3643293 +12989294 +1354500 +12465315 +14737938 +5021150 +1812819 +7649792 +4684682 +11509073 +395752 +3574424 +11446554 +3358244 +1981089 +13395398 +16155442 +4926740 +8390001 +13014049 +5751236 +11565651 +13988512 +3914622 +16578570 +14520528 +2713311 +2492195 +3218773 +15476231 +9615714 +9117856 +9276158 +929116 +11669495 +7416650 +6974416 +1001019 +12763215 +9065058 +8911027 +741837 +2810769 +1871798 +15950414 +1783619 +8432043 +9217559 +16425333 +14741540 +10787355 +1662801 +4776390 +12061778 +16708925 +16705573 +6632647 +10975924 +11915720 +12686745 +9875705 +4244411 +4862621 +10673469 +16654843 +8812841 +14571461 +996671 +14263731 +12555938 +11697986 +15646940 +15515841 +5065663 +13731126 +10482043 +9368327 +16402031 +1379273 +7922630 +3479067 +6186643 +628822 +621164 +2218927 +12178856 +11422098 +9487492 +4176796 +10097306 +10497907 +1035365 +11223369 +2790780 +16512825 +4826000 +3194976 +2192690 +15104286 +2916728 +5010056 +7265462 +7473139 +16428098 +5332146 +10175170 +4737630 +7746605 +2241569 +530516 +4740956 +14963484 +12845755 +1643642 +8788260 +2458031 +674177 +995715 +1261775 +16613785 +571444 +5430421 +5953239 +7350616 +5291026 +16023602 +12093117 +2985734 +15251079 +12019759 +8639560 +796399 +14076206 +13806848 +14580767 +1564064 +6164537 +6242590 +5912007 +11170940 +10598503 +16449730 +8591254 +6896241 +16288808 +10393039 +12782526 +614405 +6022500 +2927447 +13073703 +1431079 +15861861 +15798431 +3465610 +10555673 +2753002 +3639046 +8036674 +2806891 +3835963 +5880754 +16613860 +16251261 +261700 +13617454 +13954318 +3278555 +10129962 +8335811 +14208431 +8682464 +15081408 +12250221 +7815550 +10055755 +14922851 +7303135 +15847270 +8590059 +7575130 +6614041 +4283475 +10658906 +12380060 +14458777 +4436746 +15512196 +14048339 +11510822 +1341315 +6553350 +2431405 +9512096 +2947013 +6028468 +9458646 +8967245 +16056596 +16189258 +10447590 +12917825 +9309733 +3355377 +3108953 +10215592 +3636992 +10753914 +12491399 +16142536 +10855214 +11570243 +1721058 +7796094 +9377833 +12557660 +15188042 +14902855 +136712 +7784454 +7174638 +2994041 +1429730 +8317877 +6013530 +4176304 +12387248 +16020671 +2608903 +9426182 +1527589 +5090898 +16185542 +15273674 +2060628 +13464005 +2520528 +15927585 +9629689 +4954419 +10297521 +6208757 +3861445 +8630837 +813485 +8039219 +1645854 +9822964 +14885708 +5344839 +2092985 +1062647 +10940581 +14373728 +4073336 +8356365 +9061883 +7731171 +6429746 +13866299 +5985211 +11634139 +14053469 +8518658 +3349131 +12957226 +7278026 +2895437 +15148644 +5985178 +3957059 +12639532 +15464429 +10103454 +5721925 +4029707 +2326594 +10922523 +11179736 +2729760 +10675550 +6561041 +1018141 +2460918 +5785044 +10227570 +15579681 +12921709 +11121517 +14791940 +4392805 +7720469 +9504330 +13988703 +14272399 +13492146 +10387397 +3580870 +15846092 +16582830 +8457758 +2660779 +2619837 +15253434 +4264485 +4885312 +16754430 +5845772 +9836464 +7368075 +8073914 +10602934 +2253440 +11710707 +12414540 +3889991 +9993339 +12994869 +2397318 +11274276 +14887328 +4063264 +5298114 +10073700 +4256548 +7989366 +2424527 +9270424 +3579712 +1917331 +7711387 +13252002 +6864892 +10770554 +12344671 +7652843 +15301131 +14369561 +12764994 +6996565 +14272310 +8372869 +8591466 +10122232 +5433192 +16215053 +779204 +7827502 +3418468 +15690461 +7507246 +4776582 +8487554 +4517895 +15154918 +4756806 +1113218 +4499601 +1915645 +12041325 +3363699 +1405976 +14101187 +3065551 +8080673 +8189558 +4605502 +6426529 +14651652 +8097446 +7347505 +6895804 +10345713 +297206 +13113446 +15184441 +16597225 +12848459 +7008693 +12578379 +13307220 +2363396 +9124225 +13164556 +6874092 +12345283 +4863590 +8685756 +5443090 +3373031 +11994451 +2283521 +13835499 +4909671 +4242026 +15749412 +15778300 +14980886 +2331549 +6260657 +7385878 +4806176 +15671938 +15489446 +6542473 +14140143 +594056 +7015281 +880993 +10303329 +4588874 +15286773 +4338992 +1392749 +12769245 +16380014 +10827404 +16685336 +6815378 +3623558 +6198942 +14643635 +4451058 +16170462 +13437619 +16522263 +4408981 +7401785 +13805944 +16415893 +4640501 +9196028 +4276435 +5861107 +11315031 +14701028 +3707866 +848357 +4490904 +5838558 +12291110 +320970 +8923128 +7730329 +14000180 +13482169 +2174878 +6748862 +8422097 +9301244 +8942411 +12620544 +4343743 +6433905 +5952104 +16477916 +15157446 +2749765 +8182906 +13938085 +6788647 +14546858 +7612167 +1931151 +1838917 +16665408 +979454 +2132370 +486817 +3719655 +12155091 +9441182 +4634353 +14880707 +15322310 +6512146 +8940564 +5783845 +7038761 +10012807 +10630107 +3160599 +4110022 +13179387 +5708677 +4303895 +7997254 +764102 +4805750 +14495883 +2515400 +10172255 +2273646 +255305 +12902626 +6017210 +671194 +14554965 +9024712 +8819696 +649771 +3670755 +12280955 +6710860 +7426378 +15432004 +7025569 +9450503 +3311405 +13767241 +12963834 +306920 +12861539 +1663294 +3420766 +11744669 +3252257 +795219 +12450722 +5576430 +15390427 +12082944 +1401592 +15534103 +9326766 +3914331 +15875825 +9514288 +3830352 +4670763 +13425101 +16137535 +13981180 +11661272 +15630945 +7884955 +9257460 +5353984 +8282783 +3012425 +14608563 +9586641 +4892848 +390574 +7289254 +10069995 +5107036 +4855609 +6982040 +16415945 +4571050 +15007951 +12985663 +892465 +12253074 +5299859 +11964533 +16588156 +14867977 +4831776 +3570337 +5670366 +7939259 +13219485 +9115264 +443418 +7420272 +16602866 +6384217 +7750238 +7714127 +12468011 +15159000 +11362617 +2544919 +9239666 +4341845 +14223552 +10566087 +1746479 +13338981 +4112713 +11677483 +14972581 +1927047 +3210271 +9878656 +1874186 +8975784 +6491833 +16615537 +7906900 +14701807 +6893874 +15706787 +3465185 +9749682 +237191 +6145852 +2023434 +8470518 +132727 +9961990 +3334881 +4096764 +8900745 +12946487 +15015349 +5103488 +1470972 +12629805 +194757 +5598257 +5060626 +6083873 +1768458 +8086691 +7768376 +9626709 +4877700 +11932843 +5741894 +12877556 +459850 +13081969 +5184259 +12656579 +1748855 +9637326 +438987 +4136587 +12499591 +9800648 +14071569 +7558442 +8650969 +8397784 +13801236 +8256605 +1855483 +16174464 +15462908 +14330734 +7170819 +10255730 +14771208 +10192194 +3190931 +15135990 +5183577 +14966171 +1409072 +9715349 +9382722 +3160037 +3402323 +3957342 +13162189 +2095955 +14006332 +14309877 +15255701 +14547941 +6333590 +872374 +8626330 +14500477 +7660573 +4650407 +9236528 +3794217 +8750310 +15438563 +3461557 +3256716 +12735377 +1323300 +641269 +12561286 +3995246 +11934408 +1092804 +14290721 +14866372 +7746646 +11288426 +5280819 +6738093 +12082647 +13986078 +15757649 +7523673 +1456355 +5310679 +16723993 +7197065 +12046846 +8620072 +3394667 +13682598 +2930777 +7473653 +11544473 +15779415 +10229594 +13802799 +6340214 +8738450 +10425193 +12681154 +2904507 +431863 +9552041 +15308318 +1976897 +896985 +450530 +2155741 +12159599 +13970846 +1938904 +4089623 +16335436 +13419553 +8033425 +13113599 +8003794 +9923953 +14470818 +16694895 +4186450 +13268929 +1475510 +7064565 +10636309 +15602052 +13112485 +2759173 +359375 +10704513 +1572415 +12884147 +1170185 +9069915 +2956774 +8731244 +15373107 +14952771 +1774436 +4495572 +3033051 +9588628 +2712096 +15696873 +9462066 +3429357 +2861543 +4686903 +3833627 +11214525 +2870994 +7102659 +6581973 +14668134 +3582354 +7842815 +9698941 +12185622 +10186621 +8203228 +2750656 +7996169 +1676580 +14175141 +5797249 +4939570 +2212079 +12684814 +12934997 +10573940 +8932963 +3130974 +771959 +7763260 +13555740 +10914894 +7237402 +15406069 +2475881 +8286877 +11154415 +7112148 +2205275 +9553936 +7408417 +14163858 +5185011 +8818900 +9666609 +5033798 +13465217 +15902433 +1487044 +394727 +12388041 +4585030 +2638253 +13716249 +8339399 +2898362 +1337720 +9155024 +7571696 +12570654 +515847 +7480226 +13737177 +5296134 +1445138 +3184431 +5755356 +9219713 +16679622 +15514289 +6493967 +8463831 +11482173 +5133995 +11363650 +13943525 +8523809 +529659 +5900068 +9506887 +15329389 +12897729 +11211959 +14542936 +9580564 +16700753 +8752747 +9203324 +3734570 +316432 +10028245 +6596613 +10994217 +12237387 +2759913 +13039955 +4719593 +1746474 +5345019 +8583074 +15032861 +15517824 +7969332 +15486762 +10954067 +4861395 +6883443 +4123409 +6375640 +8778463 +3774611 +12799166 +9789498 +13825797 +286978 +2686437 +15373518 +9841239 +588613 +3172268 +10654215 +14004378 +1844412 +1373454 +457560 +6112594 +12200532 +5263991 +1524220 +16750312 +964125 +4564071 +1837575 +11675449 +8343536 +7386537 +1393153 +7542345 +5607218 +335712 +2520196 +980868 +11742379 +16006391 +10050905 +10900164 +11272687 +1312640 +4092169 +8720261 +315793 +4823792 +5090302 +6427101 +4606303 +771835 +5233402 +11046275 +14352512 +6191404 +372481 diff --git a/day22/go.mod b/day22/go.mod new file mode 100644 index 0000000..1d76001 --- /dev/null +++ b/day22/go.mod @@ -0,0 +1,3 @@ +module stevenlr.com/aoc2024/day22 + +go 1.23.3 diff --git a/day22/main.go b/day22/main.go new file mode 100644 index 0000000..992afd1 --- /dev/null +++ b/day22/main.go @@ -0,0 +1,80 @@ +package main + +import ( + "bufio" + "fmt" + "os" + "slices" + "strconv" +) + +func main() { + fmt.Println(part1([]int64{1, 10, 100, 2024}), 37327623) + fmt.Println(part1(readData("data.txt")), 13004408787) + fmt.Println(part2([]int64{1, 2, 3, 2024}), 23) + fmt.Println(part2(readData("data.txt"))) +} + +func part1(init []int64) (result int64) { + for _, n := range init { + for range 2000 { + n = next(n) + } + result += n + } + return +} + +func makeChangeId(memory [4]int, i int) (result int) { + for j := range 4 { + result = result*19 + memory[(i+j)%4] + 9 + } + return +} + +func part2(init []int64) int { + priceForChangeId := make([]int, 19*19*19*19) + for _, n := range init { + seenChange := make([]bool, 19*19*19*19) + prevPrice := n % 10 + memory := [4]int{0, 0, 0, 0} + for i := range 2000 { + n2 := next(n) + price := n2 % 10 + change := price - prevPrice + memory[i%4] = int(change) + if i >= 3 { + changeId := makeChangeId(memory, i) + if !seenChange[changeId] { + seenChange[changeId] = true + priceForChangeId[changeId] += int(price) + } + } + n, prevPrice = n2, price + } + } + return slices.Max(priceForChangeId) +} + +func prune(a int64) int64 { + return a % 16777216 +} + +func next(a int64) int64 { + a = prune((a << 6) ^ a) + a = prune((a >> 5) ^ a) + a = prune((a << 11) ^ a) + return a +} + +func readData(fileName string) (numbers []int64) { + fp, _ := os.Open(fileName) + scanner := bufio.NewScanner(fp) + + for scanner.Scan() { + n, _ := strconv.ParseInt(scanner.Text(), 10, 64) + numbers = append(numbers, n) + } + + return +} diff --git a/go.work b/go.work index 37b9da4..22aeaf2 100644 --- a/go.work +++ b/go.work @@ -14,6 +14,7 @@ use ( ./day19 ./day20 ./day21 + ./day22 ./day2 ./day3 ./day4 -- cgit