commit 53f744f628cd0de8424875a410804a1918619ee9
parent 9d92871af1797dda61aa987ae63596e0d568a77b
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Wed, 9 Dec 2020 19:14:52 -0600
Add 2020 day 09
Diffstat:
| A | 2020/day09/input.txt | | | 1000 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2020/day09/main.go | | | 82 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 1082 insertions(+), 0 deletions(-)
diff --git a/2020/day09/input.txt b/2020/day09/input.txt
@@ -0,0 +1,1000 @@
+30
+16
+33
+40
+41
+25
+2
+29
+37
+4
+11
+1
+42
+10
+21
+13
+48
+28
+19
+5
+46
+49
+24
+8
+34
+3
+6
+30
+7
+22
+9
+12
+14
+15
+16
+27
+4
+11
+60
+10
+17
+56
+13
+18
+19
+20
+21
+23
+29
+24
+25
+39
+47
+71
+34
+22
+26
+28
+30
+14
+15
+27
+31
+32
+35
+38
+37
+48
+33
+36
+40
+64
+41
+66
+49
+42
+58
+45
+83
+29
+75
+60
+44
+51
+53
+46
+68
+69
+70
+62
+113
+65
+71
+76
+95
+73
+74
+78
+139
+86
+106
+80
+82
+89
+119
+112
+90
+133
+159
+99
+127
+140
+147
+169
+135
+136
+212
+144
+149
+160
+208
+188
+222
+162
+166
+170
+179
+181
+292
+189
+268
+358
+226
+393
+243
+284
+271
+337
+302
+332
+280
+304
+293
+309
+322
+328
+336
+341
+349
+345
+415
+471
+370
+711
+432
+469
+762
+497
+514
+523
+608
+573
+582
+584
+589
+597
+602
+615
+658
+650
+669
+677
+719
+863
+954
+1179
+802
+1369
+1890
+1344
+1216
+1239
+1308
+1037
+1181
+1756
+1266
+1569
+1173
+1186
+1604
+1612
+1695
+1319
+1327
+1623
+1396
+1521
+1665
+1839
+2547
+2041
+2210
+2253
+2420
+2835
+2218
+2356
+2364
+2359
+2965
+2868
+2492
+3733
+3537
+2646
+2984
+4765
+2715
+2723
+5343
+2917
+3186
+3918
+3880
+4251
+4405
+4428
+5481
+4720
+7455
+4715
+5591
+4856
+8833
+5138
+5207
+5901
+9128
+7699
+5361
+5909
+5632
+7128
+5640
+11046
+8278
+7066
+8131
+13600
+8966
+9120
+9143
+20012
+14179
+15902
+13681
+9994
+10063
+10345
+26247
+15052
+10993
+11001
+11270
+11272
+11541
+16209
+12706
+13771
+15197
+15344
+26885
+17097
+21604
+21615
+18263
+21333
+20987
+20057
+27091
+20339
+23051
+20408
+21338
+21994
+43982
+22263
+22271
+39591
+25043
+25312
+35401
+44389
+28968
+35605
+32441
+35360
+37154
+56739
+42320
+38320
+40465
+42679
+40396
+43601
+42402
+42671
+41746
+57631
+57484
+60917
+44534
+47314
+78785
+114145
+54280
+69364
+100155
+61409
+80640
+95059
+92991
+75474
+82211
+78716
+80066
+80861
+82142
+82798
+96951
+84148
+84417
+122326
+115197
+91848
+125395
+98814
+101594
+173844
+145557
+115689
+140125
+156335
+142049
+154190
+155540
+214174
+158272
+166946
+158782
+162208
+181612
+198487
+167215
+183231
+238607
+186011
+190662
+214503
+207537
+200408
+302333
+241719
+257738
+346997
+408934
+352957
+356759
+300321
+350177
+313812
+558059
+317054
+320990
+369745
+393548
+348827
+557167
+440969
+619387
+376673
+908236
+514220
+502741
+617375
+499457
+542040
+983009
+604735
+614133
+671167
+649148
+621311
+763293
+630866
+998283
+697663
+638044
+878157
+742375
+940426
+1152264
+1041497
+943710
+1013677
+1148605
+1130323
+1002198
+1044781
+1104192
+1113590
+1146775
+1320315
+1259355
+1633064
+1252177
+1287192
+1268910
+1335707
+1328529
+1380419
+1581754
+1516201
+1620532
+1686085
+2411619
+2057300
+2576774
+1945908
+2015875
+3462109
+2106390
+2158371
+2425200
+2217782
+2372945
+2595062
+2528265
+2511532
+3631993
+2521087
+3486809
+2597439
+2664236
+4457440
+4003208
+3639054
+6059548
+5252525
+4613314
+4578387
+5544109
+5887309
+4233657
+6143525
+4583571
+4264761
+4738869
+4590727
+5261675
+4884477
+5032619
+5039797
+6153080
+6897893
+10882394
+6084248
+6236493
+10820064
+7903815
+7642262
+7872711
+8498418
+8812044
+8817228
+8972526
+8824384
+8848332
+8855488
+9630524
+9003630
+12526739
+9623346
+11116867
+10294294
+9917096
+16907445
+14012323
+13726510
+12320741
+14582666
+15546077
+13878755
+15514973
+15776526
+18889622
+22157263
+17315646
+17784570
+18626976
+17672716
+17703820
+17851962
+14144619
+19253870
+29655281
+19540442
+19917640
+23929419
+24499762
+26047251
+33628488
+36926586
+26465360
+26199496
+28023374
+29393728
+29921145
+29659592
+36330796
+31460265
+31817335
+35636532
+31848439
+31996581
+33398489
+33685061
+56844226
+34062259
+38794312
+48429181
+44417402
+50965122
+49976670
+56496343
+52246747
+52664856
+54222870
+56120641
+55593224
+63277600
+59053320
+63058081
+68148131
+63308704
+69321593
+107475483
+63845020
+65395070
+67460748
+67083550
+111706781
+72856571
+78479661
+87223493
+92846583
+111500952
+100941792
+124644474
+104911603
+117500470
+106887726
+109816094
+217291577
+136165275
+184961218
+122898340
+152618563
+127153724
+174559033
+166336862
+184563352
+129240090
+239193433
+134544298
+151336232
+179421453
+165703154
+171326244
+180070076
+197758186
+205853395
+207829518
+302502137
+263318999
+232714434
+216703820
+388030064
+259063615
+285880530
+470443882
+250052064
+263784388
+404896587
+437216762
+280576322
+294943244
+300247452
+305870542
+337029398
+604733884
+345124607
+486429717
+351396320
+377828262
+456821801
+625700929
+424533338
+449418254
+466755884
+475767435
+1092456813
+509115679
+789692001
+657266862
+544995308
+513836452
+714857660
+631972642
+575519566
+580823774
+595190696
+637276850
+932220094
+786447652
+696520927
+953185601
+1067253491
+729224582
+970658253
+942523319
+900300773
+873951592
+975871563
+980592336
+1141088321
+1022952131
+1243061034
+1058831760
+1218100624
+1310048356
+1212796416
+1844609845
+1277344701
+1156343340
+1176014470
+1232467546
+1333797777
+1425745509
+1639044246
+1603176174
+1752176713
+1671747901
+1629525355
+1774252365
+1896903723
+2703090210
+2448697640
+1956463899
+2003544467
+2081783891
+2215175100
+2234846230
+2551898401
+2445263962
+2332357810
+3727912871
+3000953185
+2433688041
+2388810886
+2658213055
+2566265323
+2936973951
+3028921683
+3232701529
+4345601363
+3381702068
+4106610175
+4131749953
+4414141701
+4316630121
+3960008366
+4038247790
+4085328358
+4218719567
+4781440423
+6029874868
+4801111553
+7782393608
+7367376876
+5417732569
+7086281543
+4999953364
+4822498927
+4955076209
+13116156411
+7114250041
+7022302309
+6261623212
+8452389491
+7341710434
+7419949858
+7998256156
+9414095065
+8401958479
+8045336724
+8123576148
+8839359343
+8304047925
+9218672931
+9582551976
+9623610480
+16709892023
+12782346972
+12114203405
+14578686689
+15872339349
+9777575136
+11084122139
+11216699421
+19486080618
+17241317822
+13283925521
+13603333646
+30313225669
+14761660292
+17620631410
+16168912872
+16884696067
+16349384649
+25568057580
+20666674115
+17143407268
+26292443999
+18801224907
+19206162456
+19401185616
+20861697275
+20994274557
+36349569724
+22300821560
+23061500657
+24539235428
+24368047660
+30702780039
+29772246518
+32382291702
+28045585813
+33970016059
+30930573164
+31111044941
+32518297521
+33053608939
+41660948672
+40262882891
+35944632175
+36544592884
+38005104543
+43162518835
+38007387363
+43923197932
+47600736085
+41855971832
+43295096117
+45362322217
+46668869220
+48907283088
+70523402064
+52413633473
+57817832331
+58976158977
+63984182103
+59156630754
+62041618105
+73316491830
+85451875972
+76012491906
+89170165979
+73949736718
+105964816037
+149962228624
+74549697427
+79861076375
+79863359195
+81930585295
+85151067949
+88524841052
+239132394603
+92031191437
+122960341080
+110948901193
+101320916561
+119859450436
+137865509445
+121017777082
+159100804667
+180514513464
+121198248859
+135358109935
+260825850525
+177333408467
+148499434145
+307600238812
+195747946286
+154410773802
+154413056622
+300293749547
+313513861289
+161793944490
+268358884581
+467926917911
+250318785542
+193352107998
+202980092630
+350161002908
+380313501097
+221180366997
+240877227518
+242216025941
+256375887017
+415476691684
+373866621462
+256556358794
+316204718292
+445692293048
+537385085289
+302912490767
+410969415416
+355146052488
+543789718285
+443670893540
+364774037120
+382974311487
+913619210959
+601493868094
+396332200628
+414532474995
+819558914510
+585954404117
+462057594515
+497253114535
+463396392938
+658058543255
+702248651842
+905728488055
+559468849561
+572761077086
+611702411282
+619117209059
+667686527887
+685886802254
+699244691395
+719920089608
+738120363975
+747748348607
+761106237748
+779306512115
+880227426022
+858389795143
+955801050189
+810864675623
+1033649684054
+1056721964096
+925453987453
+1178586058620
+1075098804220
+1149283195192
+1132229926647
+1171171260843
+1184463488368
+1286803736946
+1191878286145
+1230819620341
+1305004011313
+1353573330141
+1433635150861
+1619496032891
+1540412749863
+1558613024230
+1508854586355
+1590171187738
+1637696307258
+3023806338599
+1943094602270
+1982035936466
+2476175272156
+2380102815533
+1982175951549
+2000552791673
+2310815985267
+3610922435874
+2281513121839
+2303401187490
+2457974997789
+2422697906486
+4285437123956
+4964495766015
+2535823631654
+2658577341454
+2787208481002
+2942489737216
+4282065913512
+3619732243724
+3148784211968
+3099025774093
+4839224819144
+3619872258807
+4292991936816
+3925130538736
+3964211888015
+4661615937372
+3982728743222
+4817336753493
+4303953979163
+4584914309329
+4704211028325
+8210567662692
+4726099093976
+6091273949184
+4958521538140
+5194400973108
+5601067078670
+5323032112656
+8942764356380
+13246718335543
+6562221980940
+10559588616810
+8437209012300
+6247809986061
+6718898032900
+8651229632712
+9779315282437
+14083269261600
+8922733426155
+7946940631237
+8286682722385
+18065998004822
+8888868288492
+11570842098717
+9289125337654
+12914778691017
+14523800504825
+9684620632116
+10152922511248
+18177993626146
+10517433085764
+13974261745368
+11885254093596
+26889040436385
+13281120013840
+14509162612177
+32149267266422
+18954642098064
+40972309697985
+14665838664137
+16233623353622
+17631561263353
+16835808919729
+22402687179360
+32140723875530
+17175551010877
+18573488920608
+19041790799740
+18973745969770
+19442047848902
+19837543143364
+32155361768178
+20202053717880
+34807112274230
+33620480762201
+44025977969126
+26394416705773
+25166374107436
+31344971531906
+27790282626017
+29175001276314
+30899462017759
+44023905979639
+31501647583866
+33639584633907
+38811289113134
+34011359930606
+48520522542783
+35749039931485
+65141232217773
+36149296980647
+37547234890378
+46764028595787
+38415793818672
+69192352076562
+83327634817013
+55569417982087
+55009165992110
+63941651596151
+52956656733453
+51560790813209
+54184699331790
+54341375383750
+62244433549665
diff --git a/2020/day09/main.go b/2020/day09/main.go
@@ -0,0 +1,82 @@
+package main
+
+import (
+ "bufio"
+ "fmt"
+ "os"
+ "strconv"
+)
+
+func readInput(filename string) (res []int64) {
+ file, _ := os.Open(filename)
+ defer file.Close()
+
+ scanner := bufio.NewScanner(file)
+ for scanner.Scan() {
+ num, _ := strconv.ParseInt(scanner.Text(), 10, 64)
+ res = append(res, num)
+ }
+ return
+}
+
+func main() {
+ input := readInput("./input.txt")
+ // 14144619
+ fmt.Println(part1(input))
+ // 1766397
+ fmt.Println(part2(input))
+}
+
+func part1(input []int64) (int64, bool) {
+ preambleLen := 25
+ window := make(map[int64]int)
+ for i := 0; i < preambleLen; i++ {
+ window[input[i]] += 1
+ }
+ for i := preambleLen; i < len(input); i++ {
+ found := false
+ for j := i - preambleLen; j < i; j++ {
+ if (input[i] != 2*input[j] && window[input[i]-input[j]] >= 1) ||
+ (input[i] == 2*input[j] && window[input[j]] >= 2) {
+ found = true
+ break
+ }
+ }
+ if !found {
+ return input[i], true
+ }
+ window[input[i-preambleLen]] -= 1
+ window[input[i]] += 1
+ }
+ return 0, false
+}
+
+func minMax(input []int64) (min int64, max int64) {
+ min, max = input[0], input[0]
+ for _, v := range input {
+ if v < min {
+ min = v
+ }
+ if v > max {
+ max = v
+ }
+ }
+ return
+}
+
+func part2(input []int64) (int64, bool) {
+ target, _ := part1(input)
+ cumsum := []int64{0}
+ for _, v := range input {
+ cumsum = append(cumsum, cumsum[len(cumsum)-1]+v)
+ }
+ for i := 0; i < len(cumsum); i++ {
+ for j := i + 1; j < len(cumsum); j++ {
+ if cumsum[j]-cumsum[i] == target {
+ min, max := minMax(input[i:j])
+ return min + max, true
+ }
+ }
+ }
+ return 0, false
+}