Day09_Part2.py

from itertools import combinations
# input="""35
# 20
# 15
# 25
# 47
# 40
# 62
# 55
# 65
# 95
# 102
# 117
# 150
# 182
# 127
# 219
# 299
# 277
# 309
# 576"""

input="""2
32
10
49
28
42
18
29
17
46
27
24
14
31
21
13
48
1
30
23
50
8
36
6
7
3
11
19
4
40
5
9
10
12
15
16
17
20
14
88
18
66
13
21
25
22
23
26
28
83
29
24
31
19
34
27
30
33
32
35
38
44
37
50
36
39
40
60
59
56
52
43
46
47
48
71
64
49
51
82
89
62
108
123
72
73
79
153
75
85
94
83
95
90
91
93
109
99
97
148
100
111
113
124
170
161
169
160
162
147
152
178
158
238
182
212
173
181
183
213
190
196
197
338
211
299
224
237
271
305
307
344
355
325
386
340
331
418
354
356
364
363
371
373
409
387
407
408
568
435
624
659
508
576
612
632
656
665
671
685
744
1034
764
717
729
727
734
758
794
1031
1058
815
843
1067
1570
1084
1792
1321
1188
1283
1288
1493
1538
1405
1402
1444
1446
1552
1451
2041
1461
1573
1601
3034
1873
2416
1658
2509
2734
2272
2367
4272
2471
2590
2978
2944
2898
3062
2846
3102
3474
2897
2912
3024
3119
3259
3174
3531
3930
4025
4074
5264
4639
6031
4743
5730
6080
5061
6283
5743
5744
5758
5936
5809
5921
8738
9818
8592
6650
6293
8235
10575
7461
7955
8713
8817
12092
9382
9804
11745
14156
10804
10805
11487
11664
17409
11567
11730
12102
12214
12943
13754
16053
26858
14248
19685
15416
16174
18621
19621
24316
32564
19186
21291
27630
38807
21609
22292
33393
23297
23669
23944
23832
31787
29807
26697
37423
44055
29664
30422
34602
55893
37783
37807
62986
54366
40477
42483
42900
43901
44906
60099
45589
46966
47129
47613
47776
68738
56361
64409
78035
75590
74323
112639
65024
72385
78260
82713
78284
91030
143061
128302
90259
86801
121936
112153
92555
182814
111375
94742
95389
112800
120770
121385
129433
137409
139347
143308
173673
143284
268415
156544
168543
165085
177060
218561
179356
181543
182190
187297
279852
187944
277579
240808
232151
208189
233570
242155
264693
266842
280693
282631
286592
299828
308369
321629
325087
345603
397917
356416
367300
368840
363733
651471
420867
396133
420095
440340
441759
450344
472882
475725
506848
531535
547535
742496
569223
664785
898835
804073
646716
670690
741736
723716
720149
731033
1466212
1388501
1349179
816228
923226
973294
1004417
1122441
948607
979730
1398951
1038383
1079070
1116758
1215939
1289372
1769157
2052364
1317406
1366865
2656237
1454749
1451182
2087014
2387562
1896520
1739454
1764835
1789522
1921901
1928337
1953024
2295009
1986990
2018113
2117453
3319889
2195828
2332697
2505311
4552757
2684271
2768588
2772155
2821614
2905931
3667791
3807635
3528976
4285721
3504289
3757567
3554357
4148852
3850238
5238628
4725179
7631110
6003463
4135566
4313281
5515717
4528525
6301131
5189582
7081869
5452859
6410220
5593769
6579181
6434907
9039820
7033265
7286543
7261856
7906419
7311924
7404595
11987035
8163519
12998364
8448847
8664091
10531988
11717876
8841806
10044242
11490713
12905693
13814815
11046628
11863079
12627034
13696763
13014088
13468172
14319808
14691138
14548399
15925947
14716519
22997246
15568114
17112938
16612366
18886048
17290653
24490113
24117747
19888434
31328885
34534355
22537341
22909707
23673662
18272118
24877167
25641122
26482260
27333896
27787980
54270240
31494061
30116513
30284633
31829457
37179087
32180480
33725304
33903019
36176701
52806473
38160552
40809459
41181825
45447048
41945780
64855487
43149285
44754378
88596333
50518289
53816156
55121876
57450409
72230413
60401146
61610574
61945970
102515046
71885856
65905784
113039872
74534763
76986160
141841647
126466061
116480543
81991284
83127605
114217302
85095065
119396379
129656639
196167477
104334445
105640165
171602419
112572285
133831826
122011720
122347116
123556544
138932130
137791640
140440547
142891944
182626325
151520923
158977444
242126085
165118889
167086349
222059735
263488465
204491444
272726514
218212450
209974610
262452267
216906730
227651885
234584005
255843546
244358836
309978293
261348184
262488674
279372677
278232187
307526896
294412867
421466118
377060959
324096333
385298799
421398174
371577793
426551179
414466054
745562451
426881340
513956682
451490735
444558615
472750276
462235890
478942841
500202382
505707020
734078075
632925977
655293146
557604864
572645054
748638752
1084416712
1047392031
750977673
1318207505
786043847
798459133
816136408
859024669
871439955
878372075
1546652602
896049350
941178731
906794505
934986166
979145223
984649861
1005909402
1205571031
1288219123
1130249918
1212898010
1306243616
1557294915
1499616425
1614595541
2332696449
1712185758
1802843855
1584502980
1657483802
2065236084
1843674530
1749812030
1774421425
1847973236
2436493534
2593740764
1912703907
2541944776
1963795084
2962710040
2136159320
2335820949
2805860041
2343147928
2712514435
2863538531
4942019361
3084119405
3296688738
3927650908
5140363268
3760677143
4729900084
3431905227
3618095955
4368162189
5055662363
6521391672
4048863227
7378512895
3876498991
4306943012
4299616033
6740037522
4848673755
4479307248
5427267333
7345551965
5206686459
8373924588
6912401758
7452281594
7173187729
15547112317
8244661180
7050001182
7192582370
10996608850
8097403203
7494594946
11728078131
8176115024
7925362218
12167304855
8606559045
14667782675
8778923281
9148289788
9327981003
9685993707
9906574581
10633953792
12119088217
19592568288
14085589487
13962402940
14365770099
15117944588
14544596128
14687177316
14242583552
15670709970
23446705956
16101477242
18810068816
35694045530
16531921263
16704285499
32202631233
17385482326
17927213069
19234555584
18476270791
19013974710
23868977521
20540528373
22753042009
26081491157
28047992427
30946869051
28787179680
30215306098
28929760868
54708020240
29913293522
30344060794
31772187212
54815846572
32633398505
45319100943
48734552496
33236206762
61987493310
46524263218
35312695395
36403483860
52968348107
37490245501
39554503083
56425551951
50453821895
65635994240
101541996393
58392053221
57716940548
60257354316
58843054390
103422170002
61685480734
108991906812
72187901588
68548902157
79760469980
72790709845
69639690622
70726452263
120093512517
89371831967
71716179255
96660838176
113225702423
116559994938
90008324978
122641723483
106879373846
108170762443
116108993769
137477410528
117235107611
117974294864
121942835050
162799034823
130234382891
131325171356
138188592779
139275354420
140265081412
177605826109
140366142885
141355869877
229636913379
207982619842
161088011222
161724504233
186669163154
196887698824
255423700390
198179087421
426524612203
215050136289
233344101380
234083288633
324857755933
257601250496
261559554247
260131427829
301989585645
268422975670
337253841709
422647565469
279540435832
280631224297
494214716462
281722012762
339534957298
537714044719
706065048035
420013264534
358612203057
455780337917
448394237669
413229223710
431523188801
818345269016
449133424922
621256970060
502506264303
517732678325
562121013474
521690982076
528554403499
547963411502
627035178727
560171660129
694951236472
638152638889
562353237059
640334215819
698147160355
979869173117
771841426767
778625467591
880656613723
814392540974
861623461379
844752412511
949255867126
1071857404620
997096836424
1766808641092
1020238942628
1065696089827
1392715824013
1088726063628
1050245385575
1076517815001
1108135071631
1122524897188
1198324299018
1556574697851
2248569684593
1758494640708
1578803774078
1946352703550
2012716839992
1988791685354
1593018008565
1659144953485
1676016002353
2142763839816
2211250960816
1969494809754
2667529837706
2105231908055
2070484328203
2085935032455
2115941475402
2126763200576
2196861135259
2158380457206
2199042712189
3605734848557
2320849196206
3284259331473
4200042646170
4304274620244
3664807687707
3171821782643
3252162962050
3663502336768
3628639763239
3775086428887
5691669881012
3746500330556
4039979137957
4055429842209
4323624335835
4175716236258
4156419360658
6155920613359
4201876507857
5449024097309
4285143657782
4395903847448
4357423169395
5492670978849
5573012158256
5605108527679
6423984744693
6800461545882
6835324119411
6836629470350
6880802725289
6915665298818
7703481474725
7375140093795
8031643988338
7786479468513
10479414586902
8095408980166
8412853011604
8358295868515
8487020165639
8681047505230
8642566827177
9734167755091
8753327016843
11996996902949
14060032323895
13796468024107
11065683137105
11178120685935
16056187599025
13260614215043
13716126844700
13671953589761
18376734582268
16444496999942
15011074278984
15078621568520
24894247530635
16144775337028
15881888448679
16737975807343
20484017068588
23450294599791
17129586992816
17168067670869
17323614332407
27130061599111
18487494771934
31120082356514
22243803823040
24326297352148
28683027868745
28307707678751
24438734900978
26932567804804
28271688494027
47889029500769
39449809179962
30089695847504
46534192847446
65018616493585
44453675931518
33312843007897
34632270108962
41494365023017
42727820891628
34297654663685
34453201325223
41455884344964
34491682003276
49373865422151
40731298594974
67945113116859
68892410832496
56541458486725
58772723716249
51371302705782
52710423395005
54528430748482
61564837913766
87342693503967
92101686313779
63402538855401
"""

parsed_input=[int(a) for a in input.splitlines()]
window=25
solved=False
i=0
invalid=0
while not solved and i<(len(parsed_input)-window):
    nums = [v for v in parsed_input[i:i+window]]
    next_num=parsed_input[i+window]
    sums=[]
    for el in combinations(nums,2):
        sums.append(el[0]+el[1])
    if next_num not in sums:
        invalid=next_num
        solved=True
    else:
        i+=1

contiguous_set_size=2
j=0
solved_part_2=False
while not solved_part_2:
    if j>=i:
        contiguous_set_size+=1
        j=0
    else:
        num_set = [n for n in parsed_input[j:j+contiguous_set_size]]
        sum_set = sum(num_set)
        if sum_set==invalid:
            print(num_set)
            print(min(num_set))
            print(max(num_set))
            print(min(num_set)+max(num_set))
            solved_part_2=True
        else:
            j+=1

print(invalid)
# print(i)
# print(sum([1,2,3]))