From be26f6cb3526757e089e879c0c3b53db5d1d363e Mon Sep 17 00:00:00 2001 From: Steven Le Rouzic Date: Fri, 13 Dec 2024 23:07:39 +0100 Subject: Fucking day 13 --- day13/data.txt | 1279 +++++++++++++++++++++++++++++++++++++++++++++++++++++ day13/example.txt | 15 + day13/go.mod | 3 + day13/main.go | 241 ++++++++++ 4 files changed, 1538 insertions(+) create mode 100644 day13/data.txt create mode 100644 day13/example.txt create mode 100644 day13/go.mod create mode 100644 day13/main.go (limited to 'day13') diff --git a/day13/data.txt b/day13/data.txt new file mode 100644 index 0000000..b9c64d5 --- /dev/null +++ b/day13/data.txt @@ -0,0 +1,1279 @@ +Button A: X+65, Y+11 +Button B: X+56, Y+64 +Prize: X=7499, Y=5849 + +Button A: X+23, Y+55 +Button B: X+37, Y+13 +Prize: X=10808, Y=4864 + +Button A: X+62, Y+48 +Button B: X+38, Y+93 +Prize: X=6578, Y=10497 + +Button A: X+48, Y+42 +Button B: X+18, Y+72 +Prize: X=3534, Y=7536 + +Button A: X+11, Y+75 +Button B: X+74, Y+18 +Prize: X=14353, Y=1985 + +Button A: X+51, Y+21 +Button B: X+44, Y+75 +Prize: X=8260, Y=12662 + +Button A: X+20, Y+68 +Button B: X+59, Y+11 +Prize: X=15354, Y=9546 + +Button A: X+43, Y+70 +Button B: X+48, Y+23 +Prize: X=654, Y=9559 + +Button A: X+73, Y+28 +Button B: X+21, Y+66 +Prize: X=15091, Y=376 + +Button A: X+46, Y+14 +Button B: X+38, Y+78 +Prize: X=12952, Y=13720 + +Button A: X+16, Y+47 +Button B: X+61, Y+38 +Prize: X=18507, Y=9391 + +Button A: X+65, Y+33 +Button B: X+22, Y+52 +Prize: X=5703, Y=13797 + +Button A: X+69, Y+27 +Button B: X+15, Y+65 +Prize: X=8429, Y=4387 + +Button A: X+46, Y+20 +Button B: X+36, Y+54 +Prize: X=4962, Y=8890 + +Button A: X+56, Y+26 +Button B: X+18, Y+42 +Prize: X=18784, Y=17542 + +Button A: X+55, Y+17 +Button B: X+20, Y+74 +Prize: X=14260, Y=11446 + +Button A: X+66, Y+33 +Button B: X+25, Y+55 +Prize: X=13229, Y=13817 + +Button A: X+58, Y+95 +Button B: X+51, Y+24 +Prize: X=4556, Y=3295 + +Button A: X+37, Y+61 +Button B: X+46, Y+20 +Prize: X=6685, Y=8581 + +Button A: X+73, Y+19 +Button B: X+25, Y+89 +Prize: X=2780, Y=7488 + +Button A: X+63, Y+13 +Button B: X+27, Y+27 +Prize: X=1998, Y=798 + +Button A: X+80, Y+50 +Button B: X+38, Y+97 +Prize: X=4414, Y=6641 + +Button A: X+27, Y+53 +Button B: X+94, Y+13 +Prize: X=8287, Y=1688 + +Button A: X+26, Y+55 +Button B: X+48, Y+11 +Prize: X=3626, Y=16534 + +Button A: X+49, Y+11 +Button B: X+47, Y+61 +Prize: X=4153, Y=3707 + +Button A: X+49, Y+23 +Button B: X+14, Y+51 +Prize: X=15229, Y=3795 + +Button A: X+15, Y+47 +Button B: X+57, Y+27 +Prize: X=12098, Y=3974 + +Button A: X+17, Y+53 +Button B: X+30, Y+14 +Prize: X=11717, Y=273 + +Button A: X+14, Y+41 +Button B: X+53, Y+32 +Prize: X=19403, Y=15107 + +Button A: X+26, Y+95 +Button B: X+34, Y+14 +Prize: X=1010, Y=3029 + +Button A: X+75, Y+13 +Button B: X+14, Y+84 +Prize: X=2992, Y=1582 + +Button A: X+48, Y+14 +Button B: X+36, Y+68 +Prize: X=11432, Y=6146 + +Button A: X+19, Y+57 +Button B: X+69, Y+18 +Prize: X=3370, Y=3117 + +Button A: X+13, Y+42 +Button B: X+37, Y+14 +Prize: X=4810, Y=1152 + +Button A: X+25, Y+56 +Button B: X+65, Y+26 +Prize: X=19610, Y=19036 + +Button A: X+14, Y+56 +Button B: X+45, Y+13 +Prize: X=10538, Y=19252 + +Button A: X+28, Y+74 +Button B: X+59, Y+16 +Prize: X=8310, Y=7774 + +Button A: X+61, Y+84 +Button B: X+36, Y+11 +Prize: X=3138, Y=3704 + +Button A: X+79, Y+14 +Button B: X+18, Y+83 +Prize: X=5686, Y=4906 + +Button A: X+92, Y+38 +Button B: X+45, Y+88 +Prize: X=5513, Y=5956 + +Button A: X+72, Y+12 +Button B: X+16, Y+78 +Prize: X=416, Y=13814 + +Button A: X+41, Y+73 +Button B: X+45, Y+13 +Prize: X=11555, Y=2883 + +Button A: X+16, Y+44 +Button B: X+72, Y+28 +Prize: X=5392, Y=15268 + +Button A: X+17, Y+84 +Button B: X+48, Y+43 +Prize: X=3110, Y=7600 + +Button A: X+19, Y+17 +Button B: X+82, Y+16 +Prize: X=2596, Y=1118 + +Button A: X+69, Y+37 +Button B: X+22, Y+52 +Prize: X=8521, Y=1711 + +Button A: X+46, Y+12 +Button B: X+12, Y+56 +Prize: X=860, Y=1496 + +Button A: X+54, Y+23 +Button B: X+17, Y+35 +Prize: X=11701, Y=11297 + +Button A: X+13, Y+84 +Button B: X+60, Y+56 +Prize: X=3936, Y=8848 + +Button A: X+31, Y+68 +Button B: X+29, Y+19 +Prize: X=5822, Y=8488 + +Button A: X+91, Y+48 +Button B: X+22, Y+83 +Prize: X=5021, Y=3291 + +Button A: X+49, Y+13 +Button B: X+28, Y+76 +Prize: X=15754, Y=1378 + +Button A: X+11, Y+68 +Button B: X+39, Y+39 +Prize: X=1130, Y=5975 + +Button A: X+70, Y+30 +Button B: X+22, Y+59 +Prize: X=16330, Y=17600 + +Button A: X+29, Y+13 +Button B: X+35, Y+66 +Prize: X=581, Y=7766 + +Button A: X+25, Y+58 +Button B: X+56, Y+22 +Prize: X=847, Y=13006 + +Button A: X+47, Y+21 +Button B: X+12, Y+26 +Prize: X=16543, Y=2719 + +Button A: X+18, Y+77 +Button B: X+66, Y+37 +Prize: X=2082, Y=3509 + +Button A: X+76, Y+50 +Button B: X+19, Y+41 +Prize: X=15168, Y=10738 + +Button A: X+23, Y+40 +Button B: X+42, Y+20 +Prize: X=10244, Y=19040 + +Button A: X+12, Y+67 +Button B: X+78, Y+11 +Prize: X=17054, Y=8066 + +Button A: X+80, Y+58 +Button B: X+14, Y+41 +Prize: X=7014, Y=6967 + +Button A: X+54, Y+18 +Button B: X+15, Y+20 +Prize: X=4743, Y=1626 + +Button A: X+91, Y+25 +Button B: X+81, Y+88 +Prize: X=10754, Y=6439 + +Button A: X+11, Y+74 +Button B: X+41, Y+12 +Prize: X=1259, Y=5040 + +Button A: X+21, Y+34 +Button B: X+91, Y+14 +Prize: X=8659, Y=3086 + +Button A: X+59, Y+26 +Button B: X+18, Y+63 +Prize: X=17224, Y=7696 + +Button A: X+42, Y+78 +Button B: X+88, Y+22 +Prize: X=7890, Y=4470 + +Button A: X+21, Y+63 +Button B: X+59, Y+15 +Prize: X=421, Y=1823 + +Button A: X+42, Y+73 +Button B: X+68, Y+25 +Prize: X=7174, Y=7530 + +Button A: X+61, Y+22 +Button B: X+12, Y+39 +Prize: X=3112, Y=964 + +Button A: X+46, Y+24 +Button B: X+29, Y+54 +Prize: X=19299, Y=13418 + +Button A: X+61, Y+22 +Button B: X+15, Y+41 +Prize: X=11402, Y=14509 + +Button A: X+80, Y+71 +Button B: X+24, Y+84 +Prize: X=1944, Y=4296 + +Button A: X+51, Y+21 +Button B: X+17, Y+50 +Prize: X=9764, Y=4160 + +Button A: X+58, Y+11 +Button B: X+15, Y+74 +Prize: X=4511, Y=2880 + +Button A: X+65, Y+53 +Button B: X+25, Y+73 +Prize: X=5865, Y=7413 + +Button A: X+87, Y+25 +Button B: X+27, Y+60 +Prize: X=6945, Y=6175 + +Button A: X+90, Y+67 +Button B: X+19, Y+66 +Prize: X=2002, Y=4498 + +Button A: X+50, Y+53 +Button B: X+17, Y+77 +Prize: X=2358, Y=6864 + +Button A: X+46, Y+30 +Button B: X+18, Y+75 +Prize: X=2092, Y=2250 + +Button A: X+15, Y+58 +Button B: X+30, Y+13 +Prize: X=12770, Y=13076 + +Button A: X+17, Y+33 +Button B: X+55, Y+18 +Prize: X=18287, Y=266 + +Button A: X+68, Y+12 +Button B: X+22, Y+21 +Prize: X=3752, Y=2100 + +Button A: X+48, Y+22 +Button B: X+26, Y+56 +Prize: X=9942, Y=13694 + +Button A: X+34, Y+94 +Button B: X+87, Y+71 +Prize: X=4917, Y=4609 + +Button A: X+20, Y+59 +Button B: X+38, Y+16 +Prize: X=16936, Y=3037 + +Button A: X+79, Y+49 +Button B: X+15, Y+43 +Prize: X=19101, Y=19657 + +Button A: X+62, Y+96 +Button B: X+47, Y+15 +Prize: X=4970, Y=2958 + +Button A: X+83, Y+26 +Button B: X+30, Y+91 +Prize: X=1559, Y=1794 + +Button A: X+92, Y+17 +Button B: X+42, Y+71 +Prize: X=3950, Y=1552 + +Button A: X+56, Y+16 +Button B: X+72, Y+95 +Prize: X=8160, Y=5904 + +Button A: X+20, Y+51 +Button B: X+42, Y+27 +Prize: X=2532, Y=2772 + +Button A: X+63, Y+29 +Button B: X+27, Y+65 +Prize: X=7127, Y=14325 + +Button A: X+95, Y+38 +Button B: X+46, Y+84 +Prize: X=9192, Y=6760 + +Button A: X+70, Y+45 +Button B: X+17, Y+45 +Prize: X=3574, Y=9350 + +Button A: X+69, Y+45 +Button B: X+32, Y+91 +Prize: X=2204, Y=4453 + +Button A: X+51, Y+94 +Button B: X+51, Y+15 +Prize: X=7803, Y=9563 + +Button A: X+82, Y+41 +Button B: X+42, Y+93 +Prize: X=7578, Y=6237 + +Button A: X+19, Y+43 +Button B: X+51, Y+32 +Prize: X=10788, Y=1526 + +Button A: X+39, Y+11 +Button B: X+17, Y+62 +Prize: X=15087, Y=2700 + +Button A: X+61, Y+47 +Button B: X+96, Y+11 +Prize: X=4524, Y=2919 + +Button A: X+18, Y+88 +Button B: X+58, Y+12 +Prize: X=4614, Y=1376 + +Button A: X+65, Y+27 +Button B: X+24, Y+83 +Prize: X=3782, Y=3981 + +Button A: X+34, Y+48 +Button B: X+90, Y+12 +Prize: X=10272, Y=5412 + +Button A: X+32, Y+14 +Button B: X+15, Y+39 +Prize: X=11748, Y=8634 + +Button A: X+20, Y+62 +Button B: X+65, Y+28 +Prize: X=16435, Y=2012 + +Button A: X+25, Y+63 +Button B: X+88, Y+43 +Prize: X=5619, Y=7367 + +Button A: X+89, Y+12 +Button B: X+69, Y+55 +Prize: X=10472, Y=3514 + +Button A: X+36, Y+21 +Button B: X+34, Y+72 +Prize: X=5454, Y=8346 + +Button A: X+29, Y+88 +Button B: X+81, Y+13 +Prize: X=3216, Y=6267 + +Button A: X+82, Y+38 +Button B: X+50, Y+84 +Prize: X=7660, Y=4888 + +Button A: X+21, Y+47 +Button B: X+50, Y+22 +Prize: X=18140, Y=5876 + +Button A: X+19, Y+48 +Button B: X+63, Y+37 +Prize: X=5417, Y=2995 + +Button A: X+77, Y+25 +Button B: X+14, Y+62 +Prize: X=18764, Y=3108 + +Button A: X+44, Y+12 +Button B: X+13, Y+26 +Prize: X=10895, Y=11030 + +Button A: X+66, Y+21 +Button B: X+20, Y+53 +Prize: X=19086, Y=1719 + +Button A: X+20, Y+78 +Button B: X+96, Y+14 +Prize: X=4192, Y=3014 + +Button A: X+20, Y+84 +Button B: X+35, Y+18 +Prize: X=2260, Y=3300 + +Button A: X+91, Y+18 +Button B: X+93, Y+99 +Prize: X=10497, Y=3366 + +Button A: X+20, Y+39 +Button B: X+67, Y+41 +Prize: X=16598, Y=14967 + +Button A: X+54, Y+25 +Button B: X+33, Y+68 +Prize: X=9179, Y=13849 + +Button A: X+37, Y+14 +Button B: X+32, Y+59 +Prize: X=400, Y=11895 + +Button A: X+29, Y+67 +Button B: X+74, Y+14 +Prize: X=4035, Y=1317 + +Button A: X+88, Y+19 +Button B: X+12, Y+18 +Prize: X=5640, Y=2358 + +Button A: X+63, Y+60 +Button B: X+75, Y+17 +Prize: X=11406, Y=6563 + +Button A: X+15, Y+78 +Button B: X+78, Y+11 +Prize: X=7022, Y=7189 + +Button A: X+78, Y+42 +Button B: X+28, Y+71 +Prize: X=6084, Y=7638 + +Button A: X+38, Y+11 +Button B: X+53, Y+89 +Prize: X=2440, Y=3358 + +Button A: X+42, Y+83 +Button B: X+56, Y+28 +Prize: X=3626, Y=3115 + +Button A: X+99, Y+35 +Button B: X+13, Y+25 +Prize: X=1592, Y=2440 + +Button A: X+54, Y+80 +Button B: X+74, Y+36 +Prize: X=6156, Y=7132 + +Button A: X+49, Y+34 +Button B: X+25, Y+81 +Prize: X=5927, Y=10096 + +Button A: X+61, Y+32 +Button B: X+24, Y+44 +Prize: X=17067, Y=1008 + +Button A: X+13, Y+37 +Button B: X+46, Y+36 +Prize: X=2288, Y=2810 + +Button A: X+21, Y+43 +Button B: X+58, Y+39 +Prize: X=15775, Y=15000 + +Button A: X+57, Y+15 +Button B: X+28, Y+80 +Prize: X=8136, Y=12940 + +Button A: X+13, Y+76 +Button B: X+61, Y+14 +Prize: X=2940, Y=11580 + +Button A: X+48, Y+12 +Button B: X+57, Y+56 +Prize: X=4671, Y=1460 + +Button A: X+66, Y+80 +Button B: X+91, Y+24 +Prize: X=10639, Y=5560 + +Button A: X+33, Y+59 +Button B: X+38, Y+18 +Prize: X=4027, Y=4553 + +Button A: X+80, Y+35 +Button B: X+29, Y+98 +Prize: X=4186, Y=4732 + +Button A: X+47, Y+28 +Button B: X+13, Y+39 +Prize: X=12079, Y=6233 + +Button A: X+82, Y+90 +Button B: X+19, Y+92 +Prize: X=4313, Y=9216 + +Button A: X+23, Y+85 +Button B: X+62, Y+11 +Prize: X=19620, Y=18809 + +Button A: X+27, Y+16 +Button B: X+12, Y+38 +Prize: X=18758, Y=16198 + +Button A: X+12, Y+29 +Button B: X+70, Y+37 +Prize: X=13932, Y=9501 + +Button A: X+20, Y+63 +Button B: X+73, Y+22 +Prize: X=3544, Y=5341 + +Button A: X+86, Y+15 +Button B: X+48, Y+69 +Prize: X=7982, Y=2241 + +Button A: X+65, Y+31 +Button B: X+20, Y+43 +Prize: X=1440, Y=15796 + +Button A: X+76, Y+39 +Button B: X+23, Y+64 +Prize: X=6561, Y=7908 + +Button A: X+21, Y+51 +Button B: X+49, Y+23 +Prize: X=16216, Y=5256 + +Button A: X+42, Y+22 +Button B: X+11, Y+23 +Prize: X=542, Y=16442 + +Button A: X+44, Y+29 +Button B: X+16, Y+79 +Prize: X=596, Y=872 + +Button A: X+51, Y+27 +Button B: X+19, Y+36 +Prize: X=10188, Y=11474 + +Button A: X+68, Y+30 +Button B: X+36, Y+96 +Prize: X=6200, Y=3216 + +Button A: X+28, Y+14 +Button B: X+13, Y+42 +Prize: X=8248, Y=200 + +Button A: X+23, Y+54 +Button B: X+45, Y+20 +Prize: X=11718, Y=1334 + +Button A: X+35, Y+15 +Button B: X+23, Y+48 +Prize: X=11861, Y=3161 + +Button A: X+39, Y+18 +Button B: X+12, Y+59 +Prize: X=13319, Y=9118 + +Button A: X+41, Y+24 +Button B: X+13, Y+23 +Prize: X=1502, Y=7573 + +Button A: X+55, Y+23 +Button B: X+11, Y+37 +Prize: X=10748, Y=9716 + +Button A: X+23, Y+38 +Button B: X+74, Y+26 +Prize: X=5502, Y=4566 + +Button A: X+55, Y+30 +Button B: X+12, Y+31 +Prize: X=1767, Y=2211 + +Button A: X+44, Y+89 +Button B: X+53, Y+31 +Prize: X=7402, Y=7809 + +Button A: X+45, Y+29 +Button B: X+14, Y+38 +Prize: X=15109, Y=549 + +Button A: X+47, Y+26 +Button B: X+13, Y+26 +Prize: X=16618, Y=1576 + +Button A: X+16, Y+58 +Button B: X+99, Y+83 +Prize: X=7523, Y=9339 + +Button A: X+42, Y+69 +Button B: X+34, Y+14 +Prize: X=2114, Y=19439 + +Button A: X+32, Y+71 +Button B: X+54, Y+16 +Prize: X=1370, Y=10437 + +Button A: X+89, Y+95 +Button B: X+77, Y+14 +Prize: X=13932, Y=9075 + +Button A: X+22, Y+96 +Button B: X+78, Y+34 +Prize: X=9368, Y=11774 + +Button A: X+66, Y+20 +Button B: X+31, Y+75 +Prize: X=13542, Y=570 + +Button A: X+17, Y+48 +Button B: X+68, Y+32 +Prize: X=17074, Y=7776 + +Button A: X+13, Y+58 +Button B: X+55, Y+17 +Prize: X=800, Y=1583 + +Button A: X+33, Y+13 +Button B: X+18, Y+88 +Prize: X=3429, Y=6529 + +Button A: X+11, Y+31 +Button B: X+46, Y+12 +Prize: X=15085, Y=3055 + +Button A: X+72, Y+89 +Button B: X+91, Y+14 +Prize: X=2748, Y=2215 + +Button A: X+43, Y+13 +Button B: X+36, Y+63 +Prize: X=18750, Y=17676 + +Button A: X+18, Y+59 +Button B: X+72, Y+24 +Prize: X=10214, Y=2397 + +Button A: X+83, Y+24 +Button B: X+16, Y+49 +Prize: X=3381, Y=1377 + +Button A: X+86, Y+14 +Button B: X+49, Y+46 +Prize: X=6390, Y=3930 + +Button A: X+56, Y+17 +Button B: X+37, Y+64 +Prize: X=4711, Y=3277 + +Button A: X+18, Y+72 +Button B: X+57, Y+15 +Prize: X=341, Y=13193 + +Button A: X+58, Y+30 +Button B: X+19, Y+94 +Prize: X=4378, Y=4958 + +Button A: X+11, Y+84 +Button B: X+88, Y+11 +Prize: X=17986, Y=4237 + +Button A: X+76, Y+23 +Button B: X+57, Y+86 +Prize: X=9899, Y=7052 + +Button A: X+23, Y+79 +Button B: X+32, Y+28 +Prize: X=1742, Y=5410 + +Button A: X+49, Y+20 +Button B: X+20, Y+53 +Prize: X=11294, Y=11808 + +Button A: X+33, Y+32 +Button B: X+13, Y+53 +Prize: X=2657, Y=4475 + +Button A: X+31, Y+20 +Button B: X+25, Y+49 +Prize: X=9663, Y=18363 + +Button A: X+66, Y+17 +Button B: X+17, Y+68 +Prize: X=19741, Y=12161 + +Button A: X+13, Y+46 +Button B: X+64, Y+30 +Prize: X=13866, Y=368 + +Button A: X+33, Y+64 +Button B: X+47, Y+21 +Prize: X=5441, Y=3958 + +Button A: X+28, Y+73 +Button B: X+59, Y+46 +Prize: X=3216, Y=7522 + +Button A: X+26, Y+51 +Button B: X+49, Y+12 +Prize: X=820, Y=2021 + +Button A: X+21, Y+45 +Button B: X+61, Y+23 +Prize: X=437, Y=9227 + +Button A: X+11, Y+42 +Button B: X+32, Y+11 +Prize: X=11657, Y=2661 + +Button A: X+36, Y+95 +Button B: X+86, Y+33 +Prize: X=8870, Y=9249 + +Button A: X+77, Y+57 +Button B: X+29, Y+78 +Prize: X=5460, Y=9582 + +Button A: X+63, Y+19 +Button B: X+29, Y+69 +Prize: X=17023, Y=11551 + +Button A: X+39, Y+30 +Button B: X+11, Y+30 +Prize: X=5398, Y=6740 + +Button A: X+33, Y+12 +Button B: X+59, Y+77 +Prize: X=3506, Y=1997 + +Button A: X+38, Y+14 +Button B: X+32, Y+48 +Prize: X=6484, Y=19764 + +Button A: X+77, Y+20 +Button B: X+15, Y+57 +Prize: X=6208, Y=5254 + +Button A: X+63, Y+28 +Button B: X+19, Y+47 +Prize: X=7319, Y=14543 + +Button A: X+25, Y+85 +Button B: X+52, Y+48 +Prize: X=6818, Y=12362 + +Button A: X+32, Y+44 +Button B: X+60, Y+22 +Prize: X=6048, Y=2992 + +Button A: X+18, Y+94 +Button B: X+26, Y+14 +Prize: X=3306, Y=7766 + +Button A: X+80, Y+13 +Button B: X+11, Y+28 +Prize: X=7989, Y=3369 + +Button A: X+19, Y+85 +Button B: X+44, Y+14 +Prize: X=3791, Y=1601 + +Button A: X+49, Y+13 +Button B: X+31, Y+73 +Prize: X=16175, Y=10541 + +Button A: X+31, Y+92 +Button B: X+37, Y+29 +Prize: X=2464, Y=5858 + +Button A: X+80, Y+11 +Button B: X+47, Y+96 +Prize: X=1669, Y=2647 + +Button A: X+49, Y+18 +Button B: X+43, Y+74 +Prize: X=6626, Y=6688 + +Button A: X+71, Y+21 +Button B: X+14, Y+68 +Prize: X=11861, Y=15017 + +Button A: X+79, Y+35 +Button B: X+12, Y+59 +Prize: X=7877, Y=506 + +Button A: X+59, Y+89 +Button B: X+57, Y+16 +Prize: X=2755, Y=3526 + +Button A: X+76, Y+20 +Button B: X+14, Y+68 +Prize: X=2396, Y=18700 + +Button A: X+38, Y+75 +Button B: X+84, Y+34 +Prize: X=5344, Y=7648 + +Button A: X+49, Y+73 +Button B: X+40, Y+16 +Prize: X=14423, Y=10319 + +Button A: X+22, Y+72 +Button B: X+56, Y+33 +Prize: X=2726, Y=5916 + +Button A: X+20, Y+49 +Button B: X+63, Y+41 +Prize: X=1505, Y=1987 + +Button A: X+14, Y+49 +Button B: X+53, Y+13 +Prize: X=15505, Y=5430 + +Button A: X+76, Y+41 +Button B: X+20, Y+88 +Prize: X=4920, Y=5511 + +Button A: X+31, Y+11 +Button B: X+16, Y+64 +Prize: X=7053, Y=9761 + +Button A: X+96, Y+30 +Button B: X+29, Y+98 +Prize: X=5200, Y=8740 + +Button A: X+25, Y+53 +Button B: X+43, Y+12 +Prize: X=4281, Y=1793 + +Button A: X+29, Y+11 +Button B: X+30, Y+47 +Prize: X=5250, Y=515 + +Button A: X+15, Y+81 +Button B: X+27, Y+25 +Prize: X=1506, Y=5958 + +Button A: X+11, Y+35 +Button B: X+86, Y+56 +Prize: X=3486, Y=1824 + +Button A: X+54, Y+20 +Button B: X+13, Y+23 +Prize: X=3187, Y=13345 + +Button A: X+90, Y+18 +Button B: X+34, Y+95 +Prize: X=10346, Y=8596 + +Button A: X+99, Y+18 +Button B: X+66, Y+82 +Prize: X=15939, Y=9828 + +Button A: X+37, Y+98 +Button B: X+70, Y+37 +Prize: X=3970, Y=6805 + +Button A: X+79, Y+36 +Button B: X+19, Y+97 +Prize: X=3091, Y=2557 + +Button A: X+30, Y+89 +Button B: X+25, Y+18 +Prize: X=3465, Y=5056 + +Button A: X+51, Y+12 +Button B: X+37, Y+71 +Prize: X=810, Y=17836 + +Button A: X+89, Y+69 +Button B: X+23, Y+65 +Prize: X=7438, Y=8974 + +Button A: X+45, Y+20 +Button B: X+47, Y+76 +Prize: X=13281, Y=13348 + +Button A: X+58, Y+24 +Button B: X+21, Y+43 +Prize: X=18794, Y=18592 + +Button A: X+63, Y+31 +Button B: X+11, Y+47 +Prize: X=17679, Y=12103 + +Button A: X+18, Y+65 +Button B: X+66, Y+22 +Prize: X=19790, Y=10462 + +Button A: X+39, Y+19 +Button B: X+28, Y+47 +Prize: X=11826, Y=7558 + +Button A: X+28, Y+47 +Button B: X+99, Y+11 +Prize: X=7943, Y=3867 + +Button A: X+65, Y+21 +Button B: X+17, Y+66 +Prize: X=498, Y=1008 + +Button A: X+28, Y+68 +Button B: X+88, Y+65 +Prize: X=576, Y=804 + +Button A: X+31, Y+49 +Button B: X+78, Y+15 +Prize: X=5801, Y=4946 + +Button A: X+49, Y+64 +Button B: X+34, Y+14 +Prize: X=13149, Y=8374 + +Button A: X+54, Y+18 +Button B: X+17, Y+46 +Prize: X=12795, Y=12358 + +Button A: X+53, Y+16 +Button B: X+19, Y+36 +Prize: X=7713, Y=10856 + +Button A: X+72, Y+97 +Button B: X+49, Y+18 +Prize: X=4715, Y=5824 + +Button A: X+11, Y+89 +Button B: X+99, Y+55 +Prize: X=9196, Y=12486 + +Button A: X+35, Y+72 +Button B: X+68, Y+23 +Prize: X=4413, Y=7208 + +Button A: X+39, Y+67 +Button B: X+55, Y+24 +Prize: X=5674, Y=19054 + +Button A: X+42, Y+46 +Button B: X+99, Y+16 +Prize: X=6948, Y=4652 + +Button A: X+82, Y+24 +Button B: X+11, Y+69 +Prize: X=13453, Y=5159 + +Button A: X+14, Y+37 +Button B: X+68, Y+42 +Prize: X=17046, Y=13669 + +Button A: X+81, Y+11 +Button B: X+79, Y+82 +Prize: X=2007, Y=914 + +Button A: X+21, Y+12 +Button B: X+17, Y+31 +Prize: X=13812, Y=13891 + +Button A: X+11, Y+51 +Button B: X+74, Y+32 +Prize: X=14739, Y=5115 + +Button A: X+42, Y+13 +Button B: X+36, Y+59 +Prize: X=3936, Y=3659 + +Button A: X+11, Y+37 +Button B: X+55, Y+12 +Prize: X=14048, Y=3647 + +Button A: X+16, Y+45 +Button B: X+69, Y+33 +Prize: X=623, Y=6797 + +Button A: X+17, Y+22 +Button B: X+99, Y+32 +Prize: X=7072, Y=2616 + +Button A: X+71, Y+37 +Button B: X+12, Y+30 +Prize: X=2792, Y=278 + +Button A: X+38, Y+53 +Button B: X+36, Y+15 +Prize: X=13908, Y=10116 + +Button A: X+16, Y+43 +Button B: X+68, Y+20 +Prize: X=17748, Y=2730 + +Button A: X+65, Y+31 +Button B: X+22, Y+55 +Prize: X=6333, Y=14733 + +Button A: X+36, Y+56 +Button B: X+42, Y+15 +Prize: X=9596, Y=14534 + +Button A: X+83, Y+13 +Button B: X+12, Y+86 +Prize: X=6035, Y=7759 + +Button A: X+12, Y+66 +Button B: X+86, Y+28 +Prize: X=13896, Y=1498 + +Button A: X+14, Y+48 +Button B: X+34, Y+16 +Prize: X=2704, Y=2560 + +Button A: X+16, Y+41 +Button B: X+43, Y+25 +Prize: X=11212, Y=18973 + +Button A: X+21, Y+48 +Button B: X+45, Y+24 +Prize: X=14579, Y=3032 + +Button A: X+12, Y+56 +Button B: X+48, Y+23 +Prize: X=16412, Y=8922 + +Button A: X+30, Y+84 +Button B: X+70, Y+21 +Prize: X=1810, Y=4368 + +Button A: X+29, Y+14 +Button B: X+26, Y+54 +Prize: X=13602, Y=8840 + +Button A: X+31, Y+62 +Button B: X+77, Y+38 +Prize: X=4651, Y=5938 + +Button A: X+94, Y+36 +Button B: X+35, Y+44 +Prize: X=7089, Y=5132 + +Button A: X+75, Y+24 +Button B: X+13, Y+46 +Prize: X=19016, Y=2252 + +Button A: X+49, Y+78 +Button B: X+32, Y+12 +Prize: X=8606, Y=15092 + +Button A: X+28, Y+80 +Button B: X+51, Y+11 +Prize: X=12634, Y=2706 + +Button A: X+86, Y+47 +Button B: X+11, Y+43 +Prize: X=10609, Y=598 + +Button A: X+50, Y+22 +Button B: X+35, Y+56 +Prize: X=2690, Y=10978 + +Button A: X+69, Y+38 +Button B: X+13, Y+30 +Prize: X=16218, Y=1732 + +Button A: X+56, Y+18 +Button B: X+35, Y+66 +Prize: X=5184, Y=14276 + +Button A: X+26, Y+61 +Button B: X+59, Y+44 +Prize: X=4533, Y=5253 + +Button A: X+42, Y+16 +Button B: X+13, Y+33 +Prize: X=6870, Y=7018 + +Button A: X+18, Y+42 +Button B: X+22, Y+12 +Prize: X=14170, Y=3542 + +Button A: X+73, Y+29 +Button B: X+59, Y+85 +Prize: X=4948, Y=3320 + +Button A: X+14, Y+70 +Button B: X+88, Y+92 +Prize: X=3388, Y=4760 + +Button A: X+56, Y+86 +Button B: X+47, Y+22 +Prize: X=4717, Y=6692 + +Button A: X+67, Y+16 +Button B: X+30, Y+81 +Prize: X=4016, Y=7076 + +Button A: X+69, Y+32 +Button B: X+11, Y+28 +Prize: X=3650, Y=2540 + +Button A: X+54, Y+26 +Button B: X+14, Y+23 +Prize: X=1144, Y=14411 + +Button A: X+50, Y+17 +Button B: X+26, Y+78 +Prize: X=2468, Y=3813 + +Button A: X+40, Y+79 +Button B: X+56, Y+15 +Prize: X=11032, Y=5225 + +Button A: X+28, Y+11 +Button B: X+32, Y+65 +Prize: X=13684, Y=14399 + +Button A: X+90, Y+18 +Button B: X+25, Y+53 +Prize: X=4300, Y=2204 + +Button A: X+23, Y+41 +Button B: X+32, Y+16 +Prize: X=12422, Y=5098 + +Button A: X+49, Y+15 +Button B: X+40, Y+80 +Prize: X=16351, Y=12105 + +Button A: X+39, Y+17 +Button B: X+54, Y+76 +Prize: X=6056, Y=19300 + +Button A: X+20, Y+94 +Button B: X+31, Y+22 +Prize: X=2112, Y=8442 + +Button A: X+14, Y+77 +Button B: X+81, Y+19 +Prize: X=12411, Y=10688 + +Button A: X+53, Y+64 +Button B: X+80, Y+21 +Prize: X=7653, Y=6066 + +Button A: X+48, Y+89 +Button B: X+42, Y+14 +Prize: X=4104, Y=6332 + +Button A: X+52, Y+18 +Button B: X+28, Y+45 +Prize: X=7364, Y=5868 + +Button A: X+94, Y+36 +Button B: X+28, Y+48 +Prize: X=3352, Y=1992 + +Button A: X+17, Y+73 +Button B: X+85, Y+22 +Prize: X=2890, Y=6236 + +Button A: X+51, Y+11 +Button B: X+39, Y+75 +Prize: X=6357, Y=7697 + +Button A: X+21, Y+76 +Button B: X+60, Y+14 +Prize: X=18023, Y=3304 + +Button A: X+14, Y+52 +Button B: X+32, Y+25 +Prize: X=1378, Y=3335 + +Button A: X+18, Y+43 +Button B: X+90, Y+41 +Prize: X=9072, Y=4794 + +Button A: X+19, Y+45 +Button B: X+30, Y+13 +Prize: X=4150, Y=4372 + +Button A: X+28, Y+59 +Button B: X+57, Y+25 +Prize: X=5038, Y=10975 + +Button A: X+35, Y+71 +Button B: X+39, Y+15 +Prize: X=11189, Y=6389 + +Button A: X+44, Y+57 +Button B: X+36, Y+12 +Prize: X=2960, Y=2553 + +Button A: X+15, Y+62 +Button B: X+88, Y+75 +Prize: X=5980, Y=8837 + +Button A: X+53, Y+27 +Button B: X+43, Y+77 +Prize: X=7288, Y=9112 diff --git a/day13/example.txt b/day13/example.txt new file mode 100644 index 0000000..022b0dc --- /dev/null +++ b/day13/example.txt @@ -0,0 +1,15 @@ +Button A: X+94, Y+34 +Button B: X+22, Y+67 +Prize: X=8400, Y=5400 + +Button A: X+26, Y+66 +Button B: X+67, Y+21 +Prize: X=12748, Y=12176 + +Button A: X+17, Y+86 +Button B: X+84, Y+37 +Prize: X=7870, Y=6450 + +Button A: X+69, Y+23 +Button B: X+27, Y+71 +Prize: X=18641, Y=10279 diff --git a/day13/go.mod b/day13/go.mod new file mode 100644 index 0000000..2c8c7b8 --- /dev/null +++ b/day13/go.mod @@ -0,0 +1,3 @@ +module stevenlr.com/aoc2024/day13 + +go 1.23.3 diff --git a/day13/main.go b/day13/main.go new file mode 100644 index 0000000..c4261c3 --- /dev/null +++ b/day13/main.go @@ -0,0 +1,241 @@ +package main + +import ( + "bufio" + "container/heap" + "fmt" + "math" + "os" + "strconv" + "strings" +) + +func main() { + // fmt.Println(part1(readData("example.txt", 0)), 480) + // fmt.Println(part1(readData("data.txt", 0))) + fmt.Println(part2(readData("example.txt", 0)), 480) + fmt.Println(part2(readData("data.txt", 0)), 31623) + fmt.Println(part2(readData("example.txt", 10000000000000))) + fmt.Println(part2(readData("data.txt", 10000000000000))) +} + +type Machine struct { + PrizeX, PrizeY int64 + DxA, DyA int64 + DxB, DyB int64 +} + +type Position struct { + X, Y int64 +} + +type Candidate struct { + Pos Position + EstimateCost int64 +} + +type CandidateItem struct { + Cnd *Candidate + Index int +} + +type CandidateQueue struct { + elements []*CandidateItem + index map[Position]*CandidateItem +} + +func MakeCandidateQueue() *CandidateQueue { + queue := new(CandidateQueue) + queue.index = make(map[Position]*CandidateItem) + return queue +} + +func (queue *CandidateQueue) Len() int { + return len(queue.elements) +} + +func (queue *CandidateQueue) Less(i, j int) bool { + return queue.elements[i].Cnd.EstimateCost < queue.elements[i].Cnd.EstimateCost +} + +func (queue *CandidateQueue) Swap(i, j int) { + queue.elements[i], queue.elements[j] = queue.elements[j], queue.elements[i] + queue.elements[i].Index = i + queue.elements[j].Index = j +} + +func (queue *CandidateQueue) Push(x any) { + candidate := x.(Candidate) + item := &CandidateItem{&candidate, len(queue.elements)} + queue.elements = append(queue.elements, item) + queue.index[candidate.Pos] = item +} + +func (queue *CandidateQueue) AddElement(candidate Candidate) { + item, alreadyIn := queue.index[candidate.Pos] + if alreadyIn { + item.Cnd = &candidate + heap.Fix(queue, item.Index) + } else { + heap.Push(queue, candidate) + } +} + +func (queue *CandidateQueue) Pop() any { + if len(queue.elements) == 0 { + return nil + } else { + elmt := queue.elements[len(queue.elements)-1] + queue.elements = queue.elements[:len(queue.elements)-1] + delete(queue.index, elmt.Cnd.Pos) + return elmt.Cnd + } +} + +func part1(machines []Machine) (totalPrice int64) { + for _, m := range machines { + sol := part1Machine(m) + if sol >= 0 { + totalPrice += sol + } + } + return +} + +func part1Machine(machine Machine) (price int64) { + fmt.Println(machine) + + maxStepX := max(machine.DxA, machine.DxB) + maxStepY := max(machine.DyA, machine.DyB) + + estimateCost := func(x, y int64) int64 { + distX := machine.PrizeX - x + distY := machine.PrizeY - y + return int64(math.Floor(min(float64(distX)/float64(maxStepX), float64(distY)/float64(maxStepY)))) + } + + realCost := make([][]int64, machine.PrizeY+1) + for y := range machine.PrizeY + 1 { + realCost[y] = make([]int64, machine.PrizeX+1) + for x := range machine.PrizeX + 1 { + realCost[y][x] = math.MaxInt + } + } + + realCost[0][0] = 0 + + queue := MakeCandidateQueue() + queue.AddElement(Candidate{Position{0, 0}, estimateCost(0, 0)}) + + for queue.Len() > 0 { + candidate := heap.Pop(queue).(*Candidate) + + xa := candidate.Pos.X + machine.DxA + ya := candidate.Pos.Y + machine.DyA + realCostA := realCost[candidate.Pos.Y][candidate.Pos.X] + 3 + if xa == machine.PrizeX && ya == machine.PrizeY { + return realCostA + } else if xa <= machine.PrizeX && ya <= machine.PrizeY && realCostA < realCost[ya][xa] { + realCost[ya][xa] = realCostA + queue.AddElement(Candidate{Position{xa, ya}, realCostA + estimateCost(xa, ya)}) + } + + xb := candidate.Pos.X + machine.DxB + yb := candidate.Pos.Y + machine.DyB + realCostB := realCost[candidate.Pos.Y][candidate.Pos.X] + 1 + if xb == machine.PrizeX && yb == machine.PrizeY { + return realCostB + } else if xb <= machine.PrizeX && yb <= machine.PrizeY && realCostB < realCost[yb][xb] { + realCost[yb][xb] = realCostB + queue.AddElement(Candidate{Position{xb, yb}, realCostB + estimateCost(xb, yb)}) + } + } + + return -1 +} + +func part2(machines []Machine) (totalPrice int64) { + for _, m := range machines { + sol := part2Machine(m) + if sol >= 0 { + totalPrice += sol + } + } + return +} + +func part2Machine(machine Machine) (price int64) { + // This is fucking dumb. + // The general problem uses annoying math with diophantine stuff and shit. + // But they constructed the dataset so that we can do the dumb thing of + // solving the equations like dumb fucks and it so happens that the real solutions + // minimize the cost metric. So fucking useless and stupid. + + // ax a + bx b = tx + // ay a + by b = ty + // + // (ax bx) * (a) = (tx) + // (ay by) (b) (ty) + // + // (a) = ( by -bx) * (tx) + // (b) (-ay ax) (ty) / (ax by - ay bx) + + det := machine.DxA*machine.DyB - machine.DyA*machine.DxB + if det == 0 { + return -1 + } + + a := int64(float64(machine.DyB*machine.PrizeX-machine.DxB*machine.PrizeY) / float64(det)) + b := int64(float64(machine.DxA*machine.PrizeY-machine.DyA*machine.PrizeX) / float64(det)) + + if machine.DxA*a+machine.DxB*b == machine.PrizeX && machine.DyA*a+machine.DyB*b == machine.PrizeY { + return a*3 + b + } else { + return -1 + } +} + +func trimAll(strs []string) { + for i, s := range strs { + strs[i] = strings.TrimSpace(s) + } +} + +func parseCoordinateValue(s string) (value int) { + value, _ = strconv.Atoi(s[2:]) + return +} + +func parsePair(s string) (x, y int64) { + parts := strings.Split(strings.Split(s, ":")[1], ",") + trimAll(parts) + + x = int64(parseCoordinateValue(parts[0])) + y = int64(parseCoordinateValue(parts[1])) + + return +} + +func readData(fileName string, offset int64) (machines []Machine) { + fp, _ := os.Open(fileName) + scanner := bufio.NewScanner(fp) + + var machine Machine + + for line := 0; scanner.Scan(); line++ { + switch line % 4 { + case 0: + machine = Machine{} + machine.DxA, machine.DyA = parsePair(scanner.Text()) + case 1: + machine.DxB, machine.DyB = parsePair(scanner.Text()) + case 2: + machine.PrizeX, machine.PrizeY = parsePair(scanner.Text()) + machine.PrizeX += offset + machine.PrizeY += offset + machines = append(machines, machine) + } + } + + return +} -- cgit