- commit
- 3dd2203eea1c0fdaad4851a2b97ed0c2751da90a
- parent
- 8f5e43733370f9160873be464c3741cb426c627f
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2023-12-09 11:59
2023-12-09
Diffstat
| A | 2023/09/PROOFS | 53 | +++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/09/input.txt | 200 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/09/solution.py | 44 | ++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/09/solution.rs | 46 | ++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/09/test.txt | 3 | +++ |
5 files changed, 346 insertions, 0 deletions
diff --git a/2023/09/PROOFS b/2023/09/PROOFS
@@ -0,0 +1,53 @@ -1 1 # Definition -1 2 -1 3 def f(v, i): -1 4 if v == []: -1 5 return 0 -1 6 elif i == 0: -1 7 return v[0] -1 8 else: -1 9 return f(v, i - 1) + f(v[1:], i - 1) -1 10 -1 11 -1 12 # Thorem 1 -1 13 -1 14 f(v1 + v2, i) = f(v1, i) + f(v2, i) -1 15 -1 16 Proof by induction is trivial. -1 17 -1 18 # Theorem 2 -1 19 -1 20 Let vk be [0, 0, …, 1] with len(vk) = k + 1. Then: -1 21 -1 22 f(v0, i) = 1 -1 23 f(vk, i) = f(v(k-1), i) * (i - k + 1) / k -1 24 -1 25 examples: -1 26 f(v1, i) = i -1 27 f(v2, i) = i * (i - 1) / 2 -1 28 f(v3, i) = i * (i - 1) * (i - 2) / 6 -1 29 -1 30 Proof by induction: -1 31 -1 32 i=0 k=0: -1 33 f(v0, 0) = 1 -1 34 i>0 k=0: -1 35 f(v0, i) -1 36 = f(v0, i - 1) + f([], i - 1) -1 37 = 1 + 0 -1 38 i=0 k=1: -1 39 0 = v1[0] = f(v1, 0) = f(v0, 0) * (0 - 1 + 1) / 1 = 1 * 0 = 0 -1 40 i=0 k>1: -1 41 0 = vk[0] = f(vk, 0) = f(v(k - 1), 0) * (0 - k + 1) / k = 0 * (1 - k) / k = 0 -1 42 i>0 k>1: -1 43 f(vk, i) -1 44 = f(vk, i - 1) + f(v(k-1), i - 1) | definition -1 45 = f(v(k-1), i - 1) * ((i - 1) - k + 1) / k + f(v(k-1), i - 1) -1 46 = f(v(k-1), i - 1) * (i - k + 1) / k + f(v(k-1), i - 1) * (k - 1) / k | theorem 1 -1 47 = f(v(k-1), i - 1) * (i - k + 1) / k + f(v(k-2), i - 1) * ((i - 1) - (k - 1) + 1) / (k - 1) * (k - 1) / k -1 48 = (f(v(k-1), i - 1) + f(v(k-2), i - 1)) * (i - k + 1) / k | definition -1 49 = f(v(k-1), i) * (i - k + 1) / k -1 50 -1 51 # Conjectures -1 52 -1 53 f([a, b, …], i) = a * f(v0, i) + b * f(v1, i) + …
diff --git a/2023/09/input.txt b/2023/09/input.txt
@@ -0,0 +1,200 @@ -1 1 3 8 13 18 23 28 33 38 43 48 53 58 63 68 73 78 83 88 93 98 103 -1 2 -2 11 29 53 88 153 309 726 1835 4661 11532 27538 63421 141097 303903 635229 1292012 2564703 4984683 9517003 17906238 -1 3 18 37 70 125 217 371 619 998 1568 2495 4304 8537 19327 46991 116021 282572 672229 1560456 3541417 7876620 17202960 -1 4 5 3 9 41 127 305 637 1261 2529 5316 11643 25862 56858 122127 255336 520269 1036193 2023005 3879505 7315347 13567333 -1 5 19 32 62 124 231 392 614 915 1373 2277 4519 10482 25866 63234 148755 335092 726403 1527282 3138164 6338172 12626653 -1 6 -4 7 30 75 164 341 702 1470 3163 6933 15203 32824 69158 141826 283420 553362 1058418 1987279 3667264 6654765 11875748 -1 7 6 6 12 45 133 309 616 1125 1972 3420 5952 10401 18123 31219 52812 87385 141186 222706 343236 517509 764433 -1 8 5 18 47 115 252 489 849 1345 2011 3012 4904 9147 19016 41111 87742 180565 355977 672950 1224205 2151907 3669412 -1 9 13 26 52 100 176 283 421 587 775 976 1178 1366 1522 1625 1651 1573 1361 982 400 -424 -1532 -1 10 12 22 42 87 179 343 596 925 1249 1362 863 -890 -4670 -10732 -16647 -11320 39921 230074 787497 2239827 5750372 -1 11 20 28 36 44 52 60 68 76 84 92 100 108 116 124 132 140 148 156 164 172 180 -1 12 15 38 73 125 207 345 587 1011 1729 2895 4743 7694 12556 20768 34480 56008 85903 118700 135838 97466 -58121 -1 13 25 50 85 134 221 405 806 1655 3388 6813 13390 25677 48010 87502 155465 269380 455563 752700 1216451 1925352 2988275 -1 14 11 14 18 28 62 160 412 1032 2518 5951 13499 29205 60151 118103 221755 399703 694293 1166500 1902008 3018674 4675572 -1 15 17 29 61 142 322 679 1329 2444 4296 7368 12607 21937 39206 71843 133763 250796 471914 894574 1724356 3415191 6990661 -1 16 25 35 55 99 181 315 515 795 1169 1651 2255 2995 3885 4939 6171 7595 9225 11075 13159 15491 18085 -1 17 24 47 93 188 364 659 1130 1886 3161 5472 9957 19099 38284 79130 166433 352152 742469 1548260 3176638 6394607 12622203 -1 18 9 22 52 114 227 413 703 1168 2005 3720 7462 15574 32439 65711 128033 239356 429985 744490 1246632 2025466 3202795 -1 19 17 27 37 46 52 60 113 373 1304 4044 11098 27539 62969 134567 271636 522156 961955 1707225 2931235 4886228 7931634 -1 20 4 5 17 58 160 392 901 1977 4147 8305 15907 29341 52809 94620 173081 330962 669286 1422712 3120979 6922293 15279330 -1 21 12 33 59 89 137 250 534 1199 2643 5608 11478 22895 45125 89137 178349 362749 747214 1546674 3192438 6538615 13270431 -1 22 12 36 87 183 348 622 1080 1868 3286 5990 11464 23063 48210 102848 220185 467465 977593 2008142 4050784 8033459 15692497 -1 23 12 22 29 50 115 276 623 1305 2570 4882 9264 18179 37527 80743 176584 383112 811951 1670041 3333110 6481007 12360206 -1 24 2 15 42 84 153 288 575 1169 2319 4419 8172 15096 28881 58643 126167 281299 633708 1417003 3115486 6709092 14134989 -1 25 5 11 17 23 29 35 41 47 53 59 65 71 77 83 89 95 101 107 113 119 125 -1 26 12 15 12 15 46 139 352 803 1751 3752 7941 16540 33791 67690 133187 257958 492494 927141 1719922 3140541 5637980 -1 27 -2 5 22 63 152 320 609 1100 1995 3793 7607 15690 32330 65568 130939 260059 520048 1055477 2174152 4513505 9348176 -1 28 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 -1 29 23 49 91 162 284 491 839 1431 2470 4358 7864 14389 26361 47798 85082 147992 251049 415231 670121 1056556 1629850 -1 30 -7 -14 -27 -48 -70 -69 4 231 735 1688 3319 5922 9864 15593 23646 34657 49365 68622 93401 124804 164070 -1 31 -7 -6 0 28 110 293 639 1225 2143 3500 5418 8034 11500 15983 21665 28743 37429 47950 60548 75480 93018 -1 32 2 2 2 12 68 247 682 1577 3222 6008 10442 17162 26952 40757 59698 85087 118442 161502 216242 284888 369932 -1 33 4 14 35 66 109 180 338 744 1765 4141 9236 19397 38448 72349 130053 224597 374466 605272 951793 1460420 2192063 -1 34 15 11 7 4 -3 -32 -112 -259 -417 -351 521 3370 10285 24702 51946 99899 179807 307239 503211 795488 1220077 -1 35 12 36 80 154 282 521 988 1898 3619 6752 12256 21689 37790 66012 118465 223432 446794 937256 2016508 4350176 9258014 -1 36 13 26 63 134 255 454 789 1394 2581 5043 10231 21026 42911 86009 168696 324256 613664 1150811 2152430 4035081 7597366 -1 37 6 11 21 55 140 312 617 1124 1974 3493 6383 11962 22353 40458 69596 113039 174706 264543 416477 734489 1494950 -1 38 6 11 19 30 44 61 81 104 130 159 191 226 264 305 349 396 446 499 555 614 676 -1 39 4 17 39 87 186 374 727 1417 2824 5733 11667 23467 46404 90552 176171 346029 693035 1420320 2967758 6270574 13273721 -1 40 30 54 93 159 277 494 890 1591 2784 4734 7803 12471 19359 29254 43136 62207 87922 122022 166569 223983 297081 -1 41 4 -4 -8 13 97 314 794 1765 3606 6945 12894 23647 43930 84288 168140 346403 727291 1536690 3240269 6789559 14113690 -1 42 -3 11 45 103 185 297 479 854 1713 3678 8027 17322 36553 75098 149901 290387 545765 995517 1764033 3040529 5105577 -1 43 17 44 85 147 240 375 565 835 1260 2081 4024 9117 22651 57594 143928 347289 804275 1786258 3809999 7822431 15499370 -1 44 25 37 49 61 73 85 97 109 121 133 145 157 169 181 193 205 217 229 241 253 265 -1 45 2 11 30 61 123 271 625 1414 3057 6333 12732 25123 48924 94044 178098 332074 611499 1120917 2070835 3911665 7642856 -1 46 26 50 93 161 274 481 872 1581 2775 4628 7286 10839 15329 20839 27727 37091 51576 76662 122603 207221 359796 -1 47 6 8 14 27 58 141 363 915 2171 4804 9955 19492 36461 66021 117646 210498 386180 737432 1469012 3019809 6295620 -1 48 17 39 70 116 194 332 569 955 1551 2429 3672 5374 7640 10586 14339 19037 24829 31875 40346 50424 62302 -1 49 9 37 94 208 431 855 1629 2972 5177 8601 13636 20656 29935 41531 55131 69852 83993 94733 97770 86896 53503 -1 50 10 16 24 41 84 179 356 638 1019 1417 1577 898 -1810 -8530 -21862 -43681 -71068 -86690 -38846 196527 883820 -1 51 -1 6 35 105 235 451 805 1406 2463 4340 7623 13199 22347 36841 59065 92140 140063 207858 301739 429285 599627 -1 52 20 35 53 76 128 275 648 1466 3068 5986 11119 20091 35878 63752 112511 195891 334148 556413 906237 1456902 2351380 -1 53 15 16 19 23 29 44 85 183 387 768 1423 2479 4097 6476 9857 14527 20823 29136 39915 53671 70981 -1 54 14 30 61 112 181 268 405 713 1493 3368 7531 16252 34003 69942 143162 293275 601072 1228378 2495504 5034653 10100107 -1 55 3 6 17 42 91 183 368 778 1731 3937 8895 19639 42128 87872 179049 358833 712788 1413628 2814378 5639260 11366566 -1 56 11 21 33 51 76 101 110 102 181 776 3082 9859 26839 65288 147004 314711 654395 1343351 2751539 5649167 11617970 -1 57 0 0 10 47 137 320 664 1297 2462 4608 8568 15964 30143 58214 115154 231514 467020 933368 1830798 3504645 6530053 -1 58 11 21 49 107 213 393 690 1187 2050 3598 6410 11484 20470 36008 62213 105362 174853 284523 454431 713233 1101299 -1 59 14 28 46 76 140 288 627 1380 2997 6350 13063 26077 50692 96722 183394 350905 687364 1389288 2891252 6130858 13066480 -1 60 8 13 25 65 179 458 1060 2237 4378 8096 14427 25292 44525 80023 147966 280630 540124 1041479 1989965 3739379 6880407 -1 61 12 14 31 73 149 271 459 754 1267 2319 4755 10536 23722 51966 108690 216329 411670 755900 1355475 2407027 4293083 -1 62 9 6 11 42 132 336 742 1490 2815 5163 9499 18055 35986 74777 158921 338699 714554 1484041 3033588 6119909 12230097 -1 63 28 52 100 186 320 507 752 1083 1627 2814 5841 13613 32532 75827 169807 365835 763570 1556072 3116186 6158384 12034044 -1 64 7 10 23 70 194 464 982 1890 3377 5686 9121 14054 20932 30284 42728 58978 79851 106274 139291 180070 229910 -1 65 15 24 30 45 97 241 578 1278 2607 4980 9108 16389 29843 56177 110113 223138 460717 955393 1969144 4008502 8032483 -1 66 7 11 32 89 208 422 771 1302 2069 3133 4562 6431 8822 11824 15533 20052 25491 31967 39604 48533 58892 -1 67 7 8 11 32 109 321 827 1937 4230 8753 17398 33715 64779 125470 247957 501790 1034510 2150043 4453586 9108911 18279794 -1 68 4 7 14 48 154 412 964 2064 4162 8035 14982 27117 47861 82938 142684 247544 440636 814695 1566166 3097346 6198928 -1 69 0 5 17 36 62 95 135 182 236 297 365 440 522 611 707 810 920 1037 1161 1292 1430 -1 70 15 37 69 109 152 190 212 204 149 27 -185 -513 -986 -1636 -2498 -3610 -5013 -6751 -8871 -11423 -14460 -1 71 16 26 35 54 107 245 582 1364 3093 6750 14202 28955 57552 112141 215085 406987 760190 1400714 2542733 4541092 7969025 -1 72 24 36 43 43 48 101 313 930 2437 5716 12324 25093 49550 97213 192780 388793 793826 1624068 3294041 6571155 12832408 -1 73 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -1 74 14 37 73 127 202 300 423 575 772 1073 1651 2929 5812 12052 24789 49317 94130 172309 303317 515275 847798 -1 75 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20 -1 76 0 3 10 33 102 271 633 1353 2727 5279 9923 18258 33170 60172 110493 208157 405774 818567 1695124 3559555 7488074 -1 77 12 28 60 124 241 437 743 1195 1834 2706 3862 5358 7255 9619 12521 16037 20248 25240 31104 37936 45837 -1 78 16 32 62 123 256 546 1160 2421 4943 9861 19204 36488 67682 122895 219577 388930 688886 1229830 2223734 4074129 7534064 -1 79 1 -5 -1 23 82 221 553 1308 2895 5997 11756 22166 40884 74813 137078 252601 468828 877150 1656764 3164736 6117881 -1 80 0 0 9 39 116 283 602 1157 2059 3453 5526 8514 12705 18434 26065 35954 48386 63478 81039 100377 120042 -1 81 11 26 60 142 314 641 1245 2371 4495 8503 16031 30211 57420 111382 222529 458671 969268 2077784 4469941 9569418 20272551 -1 82 16 31 62 125 258 534 1079 2102 3944 7153 12592 21587 36122 59088 94593 148340 228080 344147 510082 743353 1066178 -1 83 2 11 22 35 58 125 326 850 2059 4642 9943 20616 41833 83358 162901 311281 580056 1052421 1858332 3194985 5353964 -1 84 20 28 36 46 60 88 172 439 1198 3100 7406 16496 34968 72120 147425 302004 621360 1278148 2609052 5247630 10346212 -1 85 24 44 67 100 160 274 479 822 1360 2160 3299 4864 6952 9670 13135 17474 22824 29332 37155 46460 57424 -1 86 16 25 42 78 146 278 557 1164 2440 4963 9640 17814 31386 52952 85955 134852 205296 304333 440614 624622 868914 -1 87 -6 -11 -14 -2 45 154 359 701 1228 1995 3064 4504 6391 8808 11845 15599 20174 25681 32238 39970 49009 -1 88 10 23 51 100 176 285 433 626 870 1171 1535 1968 2476 3065 3741 4510 5378 6351 7435 8636 9960 -1 89 -2 10 39 105 239 481 885 1539 2608 4408 7519 12945 22329 38231 64477 106587 172290 272134 420199 634921 940035 -1 90 14 29 59 130 293 634 1283 2427 4330 7354 11962 18682 28066 40912 59723 94205 177901 412436 1075133 2863466 7420460 -1 91 24 34 44 67 141 358 906 2118 4529 8961 16694 29865 52437 92541 167977 318592 632786 1301476 2722788 5696319 11769337 -1 92 4 13 35 79 170 360 746 1496 2883 5332 9513 16599 29008 52342 99931 202523 427402 913771 1934851 4002107 8033650 -1 93 13 34 64 103 151 208 274 349 433 526 628 739 859 988 1126 1273 1429 1594 1768 1951 2143 -1 94 -2 4 15 39 95 213 434 810 1404 2290 3553 5289 7605 10619 14460 19268 25194 32400 41059 51355 63483 -1 95 7 6 12 43 124 287 571 1022 1693 2644 3942 5661 7882 10693 14189 18472 23651 29842 37168 45759 55752 -1 96 24 33 48 78 135 243 462 936 1974 4173 8592 16986 32109 58095 100926 168996 273780 430617 659616 986694 1444755 -1 97 -4 -9 -14 -19 -24 -29 -34 -39 -44 -49 -54 -59 -64 -69 -74 -79 -84 -89 -94 -99 -104 -1 98 0 -4 -8 -12 -16 -20 -24 -28 -32 -36 -40 -44 -48 -52 -56 -60 -64 -68 -72 -76 -80 -1 99 9 31 79 159 272 414 576 744 899 1017 1069 1021 834 464 -138 -1026 -2259 -3901 -6021 -8693 -11996 -1 100 5 16 42 83 139 210 296 397 513 644 790 951 1127 1318 1524 1745 1981 2232 2498 2779 3075 -1 101 12 36 74 137 251 458 810 1364 2196 3459 5514 9164 16019 29015 53102 96105 169748 290814 482394 775155 1208531 -1 102 19 30 42 67 131 274 550 1027 1787 2926 4554 6795 9787 13682 18646 24859 32515 41822 53002 66291 81939 -1 103 7 8 8 6 0 -18 -63 -150 -275 -380 -298 326 2142 6234 14295 28842 53475 93184 154708 246950 381452 -1 104 6 13 28 66 157 365 822 1787 3762 7735 15690 31657 63817 128589 258284 514906 1014118 1965393 3737072 6958604 12676813 -1 105 -2 3 11 25 54 119 276 671 1640 3871 8672 18460 37729 75014 146827 285396 553788 1075877 2097463 4114657 8148210 -1 106 19 39 72 122 194 292 430 675 1245 2698 6294 14725 33632 74717 161876 342700 708999 1431793 2818588 5403828 10087310 -1 107 19 43 87 169 327 630 1202 2269 4242 7860 14451 26453 48519 89913 169718 328102 650441 1318097 2712767 5624741 11655403 -1 108 -4 -6 -8 -10 -12 -14 -16 -18 -20 -22 -24 -26 -28 -30 -32 -34 -36 -38 -40 -42 -44 -1 109 2 8 27 70 153 303 571 1054 1927 3504 6407 12052 23891 50208 109780 242399 527116 1112108 2261263 4423886 8335289 -1 110 20 46 94 175 302 486 741 1110 1724 2906 5332 10261 19846 37538 68595 120708 204756 335702 533642 825019 1244014 -1 111 8 17 28 58 132 275 501 802 1156 1615 2615 5792 15829 44258 116781 286663 658220 1426529 2942394 5815490 11073654 -1 112 -6 -11 -10 22 132 396 938 1976 3919 7555 14394 27263 51293 95492 175164 315513 556864 962041 1626566 2692484 4366778 -1 113 6 14 45 123 287 594 1122 1973 3276 5190 7907 11655 16701 23354 31968 42945 56738 73854 94857 120371 151083 -1 114 -2 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 -1 115 16 46 98 183 322 556 964 1706 3118 5901 11479 22685 45137 90106 180538 363435 734384 1484116 2983172 5929783 11598824 -1 116 28 38 49 63 91 176 442 1199 3164 7914 18776 42479 92028 191375 382498 735368 1360864 2425826 4167911 6905483 11034117 -1 117 8 9 15 28 51 93 179 370 798 1721 3603 7224 13825 25293 44391 75038 122644 194505 300263 452436 667023 -1 118 3 5 -1 -18 -44 -63 -33 121 503 1232 2439 4348 7631 14471 31276 75089 188191 470848 1154039 2759183 6443722 -1 119 22 47 80 117 151 181 238 445 1134 3043 7617 17454 36993 73667 139979 257350 463190 823519 1454686 2559379 4484275 -1 120 12 16 20 24 28 32 36 40 44 48 52 56 60 64 68 72 76 80 84 88 92 -1 121 1 17 51 114 230 452 887 1733 3331 6235 11303 19812 33600 55238 88235 137279 208517 309877 451435 645830 908730 -1 122 9 37 76 128 199 303 466 740 1258 2388 5077 11515 26294 58288 123537 249481 480959 888463 1579218 2711746 4514665 -1 123 16 30 54 91 144 216 310 429 576 754 966 1215 1504 1836 2214 2641 3120 3654 4246 4899 5616 -1 124 18 25 33 49 92 208 508 1253 3017 6968 15321 32035 63847 121770 223268 395552 680996 1146855 1903753 3141497 5197646 -1 125 21 33 47 64 92 156 318 711 1590 3409 6964 13727 26672 52201 104252 212335 436095 890005 1782857 3477686 6578384 -1 126 8 8 4 -4 -16 -32 -52 -76 -104 -136 -172 -212 -256 -304 -356 -412 -472 -536 -604 -676 -752 -1 127 6 12 18 35 85 207 480 1074 2347 5023 10528 21665 44041 89121 180621 367359 747912 1515794 3038762 5992739 11580265 -1 128 5 23 67 161 352 722 1400 2574 4503 7529 12089 18727 28106 41020 58406 81356 111129 149163 197087 256733 330148 -1 129 -1 -6 -8 1 29 90 236 631 1694 4372 10673 24704 54625 116136 238318 472758 906733 1680534 3007362 5191027 8631105 -1 130 6 16 30 39 35 30 84 347 1128 3025 7208 16076 34753 74301 158174 334390 697242 1424198 2836058 5491557 10331551 -1 131 8 12 26 58 116 218 423 895 2016 4569 10027 21030 42248 82085 156202 294835 557688 1063290 2044840 3952730 7636492 -1 132 -4 -5 7 53 162 374 756 1435 2661 4933 9252 17607 33853 65204 124639 234605 432498 778511 1366557 2339105 3906908 -1 133 21 42 76 126 201 340 653 1389 3046 6554 13618 27448 54386 107440 213541 427555 857827 1710442 3362608 6479762 12196351 -1 134 18 28 59 122 227 399 704 1292 2479 4923 10018 20767 43656 92526 196263 413485 859552 1754486 3505173 6842032 13039785 -1 135 9 17 47 118 271 585 1208 2432 4855 9683 19227 37646 72004 133830 241783 427099 745915 1307559 2337733 4314472 8250995 -1 136 18 29 40 51 62 73 84 95 106 117 128 139 150 161 172 183 194 205 216 227 238 -1 137 9 27 58 122 259 536 1053 1960 3510 6181 10909 19495 35294 64372 117430 212933 382023 675895 1176308 2009696 3364813 -1 138 10 26 49 97 197 387 734 1393 2760 5813 12789 28412 61967 130608 264394 513666 959510 1728196 3010641 5088115 8365593 -1 139 12 15 20 27 36 47 60 75 92 111 132 155 180 207 236 267 300 335 372 411 452 -1 140 -4 6 24 51 107 259 669 1682 3989 8927 19027 39005 77529 150314 285433 532230 975934 1761060 3128006 5468975 9411523 -1 141 23 46 88 160 277 476 843 1542 2850 5231 9534 17483 32755 63151 124758 249835 501986 1006051 2007833 3993101 7920462 -1 142 14 23 27 41 105 297 753 1712 3622 7368 14727 29238 57832 113877 222955 434195 843489 1642928 3228442 6434782 13041642 -1 143 8 30 78 160 287 489 836 1463 2609 4702 8568 15946 30734 61942 130500 284397 630992 1403191 3089971 6685690 14154213 -1 144 21 34 50 79 137 261 540 1163 2485 5112 10006 18611 33001 56051 91632 144831 222197 332014 484602 692647 971561 -1 145 7 15 28 48 79 145 334 897 2446 6322 15250 34467 73604 149737 292246 550576 1006993 1798573 3157000 5482970 9486677 -1 146 8 5 1 -4 -10 -17 -25 -34 -44 -55 -67 -80 -94 -109 -125 -142 -160 -179 -199 -220 -242 -1 147 22 44 85 165 324 646 1310 2688 5518 11188 22175 42691 79596 143646 251152 426134 703062 1130284 1774249 2724641 4100548 -1 148 19 28 36 55 118 303 772 1835 4071 8569 17397 34476 67136 128758 243038 450510 818032 1452159 2518459 4272986 7124211 -1 149 4 12 34 89 207 448 948 2004 4210 8656 17202 32839 60149 105876 179620 294666 468960 726244 1097362 1621749 2349115 -1 150 11 17 39 99 233 505 1036 2048 3919 7241 12869 21945 35877 56249 84634 122278 169619 225601 286739 345887 390657 -1 151 8 5 -2 -3 34 187 625 1680 3960 8546 17389 34180 66277 128873 253747 507179 1025906 2088101 4251314 8616261 17322742 -1 152 -2 -8 -15 -21 -24 -22 -13 5 34 76 133 207 300 414 551 713 902 1120 1369 1651 1968 -1 153 12 28 46 66 88 112 138 166 196 228 262 298 336 376 418 462 508 556 606 658 712 -1 154 24 42 64 90 120 154 192 234 280 330 384 442 504 570 640 714 792 874 960 1050 1144 -1 155 9 17 42 101 232 502 1010 1885 3279 5355 8270 12153 17078 23032 29878 37313 44821 51621 56610 58301 54756 -1 156 18 37 75 157 321 618 1112 1880 3012 4611 6793 9687 13435 18192 24126 31418 40262 50865 63447 78241 95493 -1 157 6 9 22 65 166 359 684 1201 2051 3632 7012 14785 32707 72650 157712 330755 668252 1302155 2453602 4483721 7968628 -1 158 22 39 64 91 108 101 64 15 18 211 840 2299 5176 10305 18824 32239 52494 82047 123952 181947 260548 -1 159 13 19 28 34 26 -16 -125 -351 -765 -1463 -2570 -4244 -6680 -10114 -14827 -21149 -29463 -40209 -53888 -71066 -92378 -1 160 13 30 57 95 149 234 384 674 1282 2653 5901 13721 32302 75049 169342 368074 768291 1539856 2967601 5510811 9883963 -1 161 14 21 40 89 194 384 687 1140 1846 3151 6091 13397 31582 75028 173639 386675 827046 1702921 3387390 6532613 12253026 -1 162 4 26 63 115 182 264 361 473 600 742 899 1071 1258 1460 1677 1909 2156 2418 2695 2987 3294 -1 163 18 21 22 22 37 109 314 760 1558 2736 4047 4598 2207 -7605 -33043 -87863 -193462 -381037 -693732 -1189230 -1944591 -1 164 10 21 45 85 136 195 286 513 1178 3047 7926 19832 47222 106987 231239 478328 950034 1817497 3359187 6015087 10462276 -1 165 11 30 54 77 96 121 198 458 1220 3203 7947 18630 41666 89931 189478 393654 812381 1671128 3425360 6974151 14044032 -1 166 16 23 37 67 127 233 405 695 1288 2762 6661 16659 40818 95848 215010 462659 961007 1939716 3828780 7434222 14272196 -1 167 14 10 -3 -23 -37 -9 138 548 1481 3426 7369 15396 31956 66327 137135 280198 561593 1098981 2096758 3906718 7140438 -1 168 -4 6 26 67 160 373 839 1796 3640 6992 12780 22337 37516 60823 95569 146042 217700 317386 453566 636591 878984 -1 169 5 18 42 78 127 190 268 362 473 602 750 918 1107 1318 1552 1810 2093 2402 2738 3102 3495 -1 170 -10 -18 -16 20 135 400 907 1751 2994 4598 6308 7495 7106 4241 684 8239 66346 279674 891836 2420818 5895093 -1 171 7 7 8 26 88 243 593 1346 2887 5868 11343 21038 37987 68052 123400 230047 443467 879621 1774586 3595814 7244270 -1 172 -5 -4 -3 -2 14 86 302 854 2174 5225 12089 27127 59264 126535 265203 547989 1119921 2266962 4543161 8998148 17570246 -1 173 10 14 24 47 98 218 515 1250 3001 6949 15343 32223 64534 123915 229858 415980 743652 1332844 2431966 4572531 8900754 -1 174 22 47 84 125 158 163 113 -2 -95 208 1946 7486 21564 52739 115142 230116 426916 741137 1209172 1857215 2684918 -1 175 9 12 11 6 -3 -16 -33 -54 -79 -108 -141 -178 -219 -264 -313 -366 -423 -484 -549 -618 -691 -1 176 26 51 84 116 134 133 148 311 935 2624 6405 13875 27353 50024 86059 140692 220232 331985 484058 685014 943344 -1 177 18 41 78 136 235 428 834 1684 3380 6567 12218 21732 37045 60754 96254 147888 221110 322661 460758 645296 888063 -1 178 19 22 25 43 115 328 859 2048 4536 9539 19389 38584 75814 147879 287254 556512 1075177 2068188 3950397 7468805 13933957 -1 179 14 37 83 165 307 561 1044 2008 3959 7847 15372 29517 55569 103191 190692 353782 663376 1261601 2434301 4756037 9376651 -1 180 -1 15 53 130 273 524 946 1628 2697 4364 7059 11747 20563 37959 72620 140479 269243 504933 921041 1631016 2804909 -1 181 4 27 60 97 127 142 154 227 538 1489 3900 9321 20509 42124 81706 151003 267728 457831 758380 1221153 1917051 -1 182 17 25 35 48 66 87 95 56 -59 -194 -33 1315 5822 17294 42431 92257 183985 343383 607707 1029266 1679682 -1 183 -6 -10 -16 -24 -30 -29 -14 38 204 701 2084 5721 14932 37626 92141 219698 510270 1155416 2554852 5528690 11733478 -1 184 -5 -10 -16 -9 35 143 344 684 1272 2383 4660 9473 19500 39580 77834 146936 265217 456972 750880 1174803 1744361 -1 185 4 6 10 16 39 125 373 963 2190 4504 8556 15250 25801 41799 65279 98797 145512 209274 294718 407364 553723 -1 186 -3 7 32 72 127 197 282 382 497 627 772 932 1107 1297 1502 1722 1957 2207 2472 2752 3047 -1 187 14 28 42 56 70 84 98 112 126 140 154 168 182 196 210 224 238 252 266 280 294 -1 188 11 16 26 48 99 223 525 1248 2932 6707 14785 31229 63090 122016 226450 404547 697953 1166602 1894700 2998078 4633109 -1 189 6 21 45 78 120 171 231 300 378 465 561 666 780 903 1035 1176 1326 1485 1653 1830 2016 -1 190 21 27 38 60 113 254 604 1369 2842 5378 9360 15248 23968 38224 65946 128371 278065 638577 1491799 3470409 7977899 -1 191 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 -1 192 13 16 25 38 63 140 370 960 2303 5122 10717 21364 40925 75738 135866 236794 401673 664220 1072393 1692970 2617171 -1 193 6 10 22 38 59 110 280 790 2095 5024 10965 22130 42036 76621 137108 247275 460964 901754 1847740 3903290 8330769 -1 194 20 23 28 40 73 158 357 789 1674 3401 6626 12406 22375 38968 65699 107499 171120 265611 402872 598292 871477 -1 195 10 13 13 10 4 -5 -17 -32 -50 -71 -95 -122 -152 -185 -221 -260 -302 -347 -395 -446 -500 -1 196 7 25 57 115 224 435 860 1753 3675 7802 16477 34195 69388 137730 268375 515881 983110 1865108 3532670 6690534 12676255 -1 197 -8 -9 -9 -5 24 132 426 1094 2444 4957 9357 16701 28492 46818 74520 115392 174416 258035 374467 534063 749712 -1 198 6 16 42 98 209 421 822 1580 3015 5745 10978 21060 40430 77174 145408 268752 485180 853542 1462050 2438998 3965943 -1 199 4 10 11 16 47 139 340 711 1326 2272 3649 5570 8161 11561 15922 21409 28200 36486 46471 58372 72419 -1 200 12 26 50 87 145 233 360 549 892 1695 3797 9194 22159 51150 112057 234074 471388 928280 1814436 3565001 7091909
diff --git a/2023/09/solution.py b/2023/09/solution.py
@@ -0,0 +1,44 @@
-1 1 import sys
-1 2
-1 3 def naive(v, i):
-1 4 if not v:
-1 5 return 0
-1 6 elif i == 0:
-1 7 return v[0]
-1 8 elif i > 0:
-1 9 return naive(v, i - 1) + naive(v[1:], i - 1)
-1 10 else:
-1 11 return naive(v, i + 1) - naive(v[1:], i)
-1 12
-1 13
-1 14 def closed(v, i):
-1 15 s = 0;
-1 16 base = 1
-1 17 for k, x in enumerate(v):
-1 18 if k > 0:
-1 19 base *= (i - k + 1) / k
-1 20 s += x * base
-1 21 return int(s)
-1 22
-1 23
-1 24 def get_start_values(numbers):
-1 25 diff = [numbers[i + 1] - numbers[i] for i in range(len(numbers) - 1)]
-1 26 if all(x == 0 for x in diff):
-1 27 return [numbers[0]]
-1 28 else:
-1 29 return [numbers[0], *get_start_values(diff)]
-1 30
-1 31
-1 32 with open(sys.argv[1]) as fh:
-1 33 sum1 = 0
-1 34 sum2 = 0
-1 35
-1 36 for line in fh:
-1 37 numbers = [int(s, 10) for s in line.split()]
-1 38 v = get_start_values(numbers)
-1 39 sum1 += closed(v, len(numbers))
-1 40 sum2 += closed(v, -1)
-1 41
-1 42 print(f'part1: {sum1}')
-1 43 print(f'part2: {sum2}')
-1 44 print(closed([0, 0, 0, 1], 5))
diff --git a/2023/09/solution.rs b/2023/09/solution.rs
@@ -0,0 +1,46 @@
-1 1 #[path = "../lib.rs"]
-1 2 mod lib;
-1 3
-1 4 fn get_start_values(numbers: &Vec<i64>) -> Vec<i64> {
-1 5 let mut tmp = numbers.clone();
-1 6 let mut start_values = vec![];
-1 7
-1 8 while tmp.iter().any(|x| *x != 0) {
-1 9 for i in (1..tmp.len()).rev() {
-1 10 tmp[i] -= tmp[i - 1];
-1 11 }
-1 12 start_values.push(tmp.remove(0));
-1 13 }
-1 14
-1 15 return start_values;
-1 16 }
-1 17
-1 18 fn get_value(v: &Vec<i64>, i: i64) -> i64 {
-1 19 let mut sum = 0;
-1 20 let mut base = 1;
-1 21 for (k, x) in v.iter().enumerate() {
-1 22 if k > 0 {
-1 23 base = base * (i - (k as i64) + 1) / (k as i64);
-1 24 }
-1 25 sum += x * base;
-1 26 }
-1 27 return sum;
-1 28 }
-1 29
-1 30 fn main() {
-1 31 let mut sum1 = 0;
-1 32 let mut sum2 = 0;
-1 33
-1 34 for line in lib::iter_input() {
-1 35 let numbers = line
-1 36 .split_whitespace()
-1 37 .map(|s| s.parse().unwrap())
-1 38 .collect();
-1 39 let v = get_start_values(&numbers);
-1 40 sum1 += get_value(&v, numbers.len() as i64);
-1 41 sum2 += get_value(&v, -1);
-1 42 }
-1 43
-1 44 println!("part1: {}", sum1);
-1 45 println!("part2: {}", sum2);
-1 46 }
diff --git a/2023/09/test.txt b/2023/09/test.txt
@@ -0,0 +1,3 @@ -1 1 0 3 6 9 12 15 -1 2 1 3 6 10 15 21 -1 3 10 13 16 21 30 45