-
Notifications
You must be signed in to change notification settings - Fork 0
/
day09.test.ts
1104 lines (1081 loc) · 10.6 KB
/
day09.test.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/* === TYPES === */
/* === PREPARE INPUT === */
export const prepareInput = ([input]: TemplateStringsArray) =>
input.split("\n").map(Number);
/* === UTILS === */
const includesSum = (sum: number, xs: number[]) =>
xs.some((x, i) => xs.some((y, j) => i !== j && x + y === sum));
const extremesInRange = (
from: number = 0,
to: number = 0,
xs: number[]
): [number, number] => {
const range = xs.slice(from, to);
return [Math.min(...range), Math.max(...range)];
};
/* === IMPLEMENTATION === */
const findInvalid = (preambleSize: number, xs: number[]) =>
xs.find(
(value, i) =>
i >= preambleSize && !includesSum(value, xs.slice(i - preambleSize, i))
);
const findContiguousSum = (
targetSum: number,
xs: number[],
from: number = 0,
to: number = 0,
sum: number = xs[from]
): [number, number] => {
if (sum === targetSum) {
return [from, to];
}
if (sum < targetSum) {
return findContiguousSum(targetSum, xs, from, to + 1, sum + xs[to + 1]);
} else {
return findContiguousSum(targetSum, xs, from + 1, to, sum - xs[from]);
}
};
/* === TESTS === */
test("Day 9a - test", () => {
const result = findInvalid(5, testInput);
expect(result).toBe(127);
});
test("Day 9a - prod", () => {
const result = findInvalid(25, prodInput);
expect(result).toBe(2089807806);
});
test("Day 9b - test", () => {
const invalid = findInvalid(5, testInput) as number;
const [from, to] = findContiguousSum(invalid, testInput);
expect(from).toBe(2);
expect(to).toBe(5);
const [min, max] = extremesInRange(from, to, testInput);
expect(min + max).toBe(62);
});
test("Day 9b - prod", () => {
const invalid = findInvalid(25, prodInput) as number;
const [from, to] = findContiguousSum(invalid, prodInput);
const [min, max] = extremesInRange(from, to, prodInput);
expect(min + max).toBe(245848639);
});
/* === INPUTS === */
const testInput = prepareInput`35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576`;
const prodInput = prepareInput`16
45
42
47
31
38
4
7
44
10
18
24
48
28
19
23
32
1
37
9
36
8
41
49
13
15
11
27
5
6
12
45
14
7
34
10
21
50
29
16
17
18
19
20
31
52
22
23
26
42
13
24
28
46
25
30
58
27
53
49
35
91
47
54
74
51
98
55
33
40
59
36
76
37
38
100
52
107
57
60
67
81
62
68
69
73
117
132
70
71
143
77
74
105
122
75
88
196
89
145
114
146
155
119
127
142
148
130
137
160
237
141
207
147
229
219
152
162
365
163
164
253
288
203
233
241
246
269
249
257
267
271
278
284
325
423
293
299
309
549
314
526
326
512
396
653
436
444
449
562
575
495
506
634
524
566
804
952
583
758
613
763
608
623
640
762
1145
722
1305
1010
1263
939
1019
955
1370
1001
1191
1768
1090
1107
1149
1853
1223
1196
1221
1231
1248
1772
1362
1723
1907
2311
2109
1894
1940
1956
2187
2419
2091
2960
2150
3046
5379
2321
2355
2469
3142
2427
2417
4373
2479
2610
3085
3471
3630
3801
3834
3850
3896
4031
4047
5233
4836
6277
4471
8269
8101
8502
7556
4772
6365
4906
6510
4896
5564
11282
6240
6556
7367
10541
7635
8305
7897
12148
8078
14443
11598
22521
11146
12541
12120
9802
9668
9678
10336
12531
10460
11136
11452
11804
12796
13607
13923
21242
15713
17699
16202
15975
17746
28882
19346
25515
19470
21922
23572
20004
19480
20014
22264
32142
21596
26403
22940
44995
24600
26719
27530
29898
31688
36206
32177
35455
46417
37760
38816
49912
38950
39474
39484
49975
62414
56777
41610
54441
44536
47540
53122
49659
86618
51319
54249
57428
61586
63865
67632
88027
73215
136277
76576
97199
78424
78434
100662
224304
111405
86146
142923
96051
126337
92076
98859
100978
118114
125060
105568
134004
223682
131497
137080
140847
223226
173877
156858
155000
164570
197644
186808
212067
178222
182197
194910
188127
221111
193054
256557
259064
289630
239572
298622
324551
309719
467852
268577
277927
328877
348054
464735
343666
319570
392554
360419
394264
366349
370324
383037
555329
381181
432626
710015
496129
498636
559142
517499
664971
546504
578296
743456
588147
721431
1086783
663236
685919
679989
689894
726768
730743
1401420
736673
751505
813807
877310
879817
1598741
1013628
1353130
1329801
1452174
2325509
1211475
1124800
3046940
1268136
1251383
1343225
1393979
1349155
1365908
1740396
2215227
1457511
2145446
1631322
1488178
1565312
1691117
2207111
2392936
2138428
2281764
2817979
2336275
2582311
2376183
2462858
3179295
2519519
3573019
3644319
2831403
2715063
2806666
2823419
2945689
3633624
3850447
4720739
3053490
4319581
3256429
3829545
4657947
5326185
4420192
5949202
5641398
4799133
4839041
4895702
4982377
5234582
7630536
5630085
7150984
5538482
6652964
5752355
8725247
5999179
6309919
10419371
6883035
11579287
7085974
7676621
9470943
13986540
9219325
9259233
9878079
9694835
16418550
9734743
18420082
12283049
12652143
11290837
11168567
11537661
11751534
12062274
22346978
17847580
16004754
21911376
13969009
14559656
14762595
16305299
16895946
18478558
18914160
32883169
31646119
19429578
36325524
26824869
24345323
22706228
33637815
22459404
36407597
22920101
23289195
37265884
45626329
39107918
57586476
37682696
28528665
28731604
29322251
31067894
33201245
45379505
48161182
38343738
42349679
41888982
42718773
66839060
45165632
57260269
67838909
45748599
46209296
51448766
71247438
51817860
57850916
58053855
62523496
61729910
99412606
61932849
99979042
60390145
88467372
71544983
81062511
103618892
80232720
84238661
84607755
87884405
106599441
133274893
91957895
97197365
104060212
142165569
113972262
109668776
109871715
115904771
149614315
122120055
153890744
122322994
131935128
140622865
144628806
164471381
151777703
161295231
236586701
172492160
188298873
286794375
194483846
189155260
236295256
353626641
206866141
301918096
231991770
219540491
292400568
225776486
238227765
244443049
254258122
274100697
262945859
355779077
309100187
332927679
313072934
480966838
333787391
425450516
360791033
493660516
383639106
552468170
396021401
432642627
426406632
438857911
445316977
889681917
499877183
464004251
470219535
482670814
498701171
517203981
537046556
572046046
622173121
948489571
646860325
673863967
890410883
694578424
744430139
968920706
1391290464
779660507
1139377102
822428033
982363533
865264543
902862162
909321228
934223786
998578354
946675065
1159219677
981371985
1015905152
1089250027
1512584004
1728150078
1556181553
1712838916
1537271208
1368442391
1474238931
1439008563
1524090646
1602088540
2292244511
1644925050
1687692576
1725290195
1907899582
2804144727
2881026395
2420913996
1880898851
3633189777
1928047050
2105155179
2457692418
2539995798
3833305257
5435393797
2089807806
2924623944
3119163981
3076327471
3013367441
7540548976
2963099209
3568591427
3970706657
4658292491
4108606572
4420894649
3830445374
3808945901
3986054030
4033202229
4017854856
6132531422
4194962985
4385739468
4562847597
4547500224
6581958868
5014431750
6984074098
5052907015
8251340023
5976466650
7399106909
6531690636
6772045110
6793544583
7377537328
7639391275
8194685369
11594069894
7794999931
7816499404
7826800757
10726653621
18971607222
15194036732
8580702453
9438646483
8933239692
15979809362
9561931974
21775995600
10990898400
11029373665
12847906946
14171081911
25161980311
13303735746
13325235219
13565589693
14432935858
15016928603
15455890679
17388732731
15611499335
15621800688
21717552021
31156198504
19000578457
34593407910
24913049054
17513942145
18371886175
22258474911
24354608884
40776574057
24316133619
25423834258
27736671604
26151642692
33433514315
26628970965
26869325439
26890824912
27998525551
29888826537
36514520602
49127800350
31233300023
33125441480
33135742833
44383267584
67729150743
41868551029
42937776403
35885828320
39772417056
40630361086
57788123199
49739967877
50467776311
51185459058
78823604723
62776653232
52780613657
53498296404
57862270988
92065576753
58124124935
57887352088
136710956811
64358741503
90240193367
82875710710
66261184313
102245538572
75658245376
89512384933
86353604631
80402778142
155026152229
110642884645
131588237200
100207744188
100925426935
101653235369
110667965745
106278910061
110904738592
148102464355
166756382773
115749623076
133545597464
259007202947
144761519645
168506722885
185121249282
149136895023
141919429689
146663962455
202578662304
156061023518
197258343223
210850628833
180610522330
211112482780
322817406291
217183648653
201133171123
211593392680
207932145430
303537253284
222028533137
244450336056
332933271729
329882768927
249295220540
275465027153
286680949334
334258144305
288583392144
455562818836
410510807734
349851575119
302724985973
403711833427
336671545848
377868865553
699094199878
492648675806
640208799132
562145976487
412726563803
409065316553
508709482471
579002280437
737099011862
466478869193
1261240176365
618466161071
1034565099273
524760247693
933825564246
575264341478
925115916597
864870962460
711790302526
639396531821
706436819400
898817522335
1355565172933
714540411401
1223854447571
821791880356
1331349831653
875544185746
879205432996
1033469730164
917774799024
1084945030264
991239116886
1143226408764
1041743210671
1333006572472
1100024589171
1811814891697
1164156779514
1214660873299
1287054644004
1345833351221
1353936943222
1697336066102
2002719829288
1909013915910
1536332291757
1906736910620
1590084597147
3252570261841
1700997313352
1796980232020
1754749618742
2184969619435
1951244529188
2141767799842
2032982327557
2091263706057
2205899990185
3610011229262
2264181368685
2314685462470
4112636900805
3703717142640
3472024263439