Day14_Part2.py

from collections import defaultdict
from itertools import combinations
import re, math

# input="""mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
# mem[8] = 11
# mem[7] = 101
# mem[8] = 0"""

# input="""mask = 000000000000000000000000000000X1001X
# mem[42] = 100
# mask = 00000000000000000000000000000000X0XX
# mem[26] = 1"""

# input="""mask = 000000000000000000000000000001XX0X0X
# mem[8] = 11
# mem[7] = 101
# mem[8] = 0"""

input="""mask = X00X0X0110010001010X0000000010001111
mem[36604] = 2508973
mem[14290] = 80919
mem[6865] = 15237
mem[45983] = 393572789
mask = X101001X0XX00111000110X0010000110110
mem[300] = 253232
mem[5315] = 56368
mem[64425] = 18227
mem[20919] = 4682858
mem[39194] = 54595
mem[32891] = 32798017
mask = X1X00101XX00000111X11X0000100000010X
mem[22572] = 2370
mem[61212] = 13199
mem[15537] = 15245
mem[29581] = 9182
mem[38437] = 15367
mem[62023] = 300695
mem[63267] = 7104850
mask = 0X0000X0X000001X0001100X01X10010X111
mem[3086] = 5701228
mem[36874] = 37361919
mem[32535] = 70063
mem[9250] = 118850
mem[34568] = 40417332
mem[17679] = 1524672
mask = 0001XX011XX000101001111X11X00X0010XX
mem[25707] = 3970805
mem[60089] = 23470
mem[3743] = 102952
mask = X0X001X11001X00001X1100000101000X100
mem[8520] = 616
mem[56700] = 25286
mem[38562] = 17113080
mem[12983] = 95219576
mem[55881] = 1319
mask = X01XX1X01X010X001000001X0000001100X0
mem[11461] = 705
mem[53581] = 671301430
mem[30698] = 23265744
mem[43949] = 52479060
mem[63713] = 5944
mem[16514] = 29828
mask = 000X00111101000000X10X011X0X00011000
mem[13056] = 51737402
mem[32968] = 443
mem[9359] = 787521168
mask = 111101011000001X00XX1XXX10001X10XX10
mem[15175] = 66121143
mem[28608] = 51465130
mem[37437] = 417303
mem[48362] = 45976
mem[25538] = 725
mem[56823] = 149265
mask = 11110XX1100X001100X011101XX11X100101
mem[57430] = 54546802
mem[37498] = 59833242
mem[50782] = 64840
mem[15682] = 42
mask = 000000X11X0X0000X001X0101X1X10X000X1
mem[65444] = 437004931
mem[5101] = 621794630
mem[38430] = 7936
mem[44607] = 537
mask = X111X000100X0010X001X0011010X1X0X001
mem[36207] = 503
mem[22125] = 117936
mem[60610] = 3038
mask = 00000X01X0000000100XX00011X0X0X1X001
mem[19151] = 47782
mem[43398] = 392732
mem[95] = 42278134
mem[4818] = 169770
mem[30878] = 616488
mem[12676] = 776
mask = 000000X01X0000101001X01001XXX100XX0X
mem[32652] = 29160
mem[8726] = 1607
mem[24875] = 13649776
mem[46342] = 237422222
mask = 000000110X0X00X0001X01X001X001001X01
mem[3208] = 62807
mem[39153] = 155184045
mem[22551] = 207105
mem[46967] = 14502
mem[22381] = 770
mask = X00000X1100100X0100100111000X0X111X0
mem[54548] = 29990952
mem[61467] = 26032494
mem[12945] = 9185
mem[51491] = 1260601
mem[9271] = 3790612
mem[4788] = 6755464
mask = 10X101011X00011000010010111110X01XX0
mem[59309] = 5377498
mem[52392] = 137238
mem[18787] = 976
mem[23189] = 131566
mem[52264] = 21
mem[58149] = 1752629
mask = 1XX1010110XX0X1XX0010100100010X000X0
mem[42762] = 78593584
mem[56852] = 131055404
mem[41490] = 8594
mem[55167] = 146
mem[45930] = 32132474
mem[1492] = 488276568
mask = 010X001X1X0X00000011010000X000X1X001
mem[39661] = 2007038
mem[17687] = 369773
mem[45856] = 8176
mem[26201] = 3981925
mask = 0XX100X01XXX001100011000X10001100110
mem[58961] = 18686391
mem[9741] = 25417
mask = 0111100XX00XX1100XX111X0111000X00100
mem[35588] = 4312609
mem[64593] = 20356076
mem[55330] = 5015
mem[61597] = 328414
mem[31791] = 1676
mem[17345] = 799040493
mem[14693] = 96199961
mask = X0000000X00000100X0110000000XX01100X
mem[11679] = 11507170
mem[52094] = 690
mem[35099] = 27306
mem[43398] = 966
mem[34575] = 1534093
mem[38562] = 210
mask = 00X000001X010100X0X11101X1X1010010X0
mem[8360] = 478086
mem[34057] = 444
mem[50343] = 1871239
mem[31196] = 462153738
mask = 00000X10100X00110001XX1X0110XX01010X
mem[51437] = 1324
mem[31425] = 26441
mem[62650] = 16505822
mem[9471] = 15329
mask = 0XX00101XX0000X1X10100X0001000001000
mem[31388] = 271
mem[63713] = 764
mem[39561] = 20515724
mem[32340] = 942731200
mask = 000000010X0000X0100101X01110X1111110
mem[30296] = 96490803
mem[57542] = 387
mem[17581] = 60702
mem[53621] = 119633
mask = 000X0101000100X01001X10X1111011X110X
mem[47602] = 362302052
mem[45165] = 2235
mask = 0XXX0000X000001X0001100X01100XXX1110
mem[32340] = 239496
mem[8515] = 4421
mem[789] = 4757
mem[42007] = 26560
mask = 000X0010XX0000X10X011110011XX0110X11
mem[37951] = 153334
mem[9994] = 920
mem[41432] = 14141494
mem[51882] = 5283
mem[42014] = 33237
mask = 00X0X00X1000001X00011X001011X00X10X1
mem[15351] = 14927547
mem[48174] = 166296
mem[2816] = 81493
mem[24468] = 3388
mem[5315] = 63737805
mem[1806] = 1772436
mem[4365] = 10496
mask = 0X010X100X0011110001001X010010010000
mem[53612] = 398
mem[22551] = 14771384
mem[59630] = 1758147
mem[33557] = 58149
mem[61583] = 7151
mem[57526] = 29224
mask = 0000001X11010000000XXX001011X0000010
mem[59714] = 399
mem[14500] = 171446119
mem[13047] = 144258
mem[44426] = 1072845322
mem[3743] = 828
mem[16342] = 92699585
mem[27960] = 3569
mask = 101X0101101000101001XXX01X0110100X00
mem[34280] = 15537902
mem[59471] = 917
mem[43487] = 2084
mem[44810] = 6278270
mask = 011100X0000XXX1X0001001X00000X000101
mem[64098] = 153760274
mem[8515] = 88022
mem[37392] = 3714494
mem[22904] = 24215775
mem[38430] = 2181
mem[32906] = 15929
mask = 010000X10001XX000010100XX0000X1110X1
mem[38562] = 145845
mem[29094] = 321326129
mem[25681] = 741610
mem[21073] = 11181845
mem[2287] = 1904555
mem[58854] = 7213611
mask = 00X000111X0100X00001X00X1XX010X0001X
mem[25949] = 154
mem[45994] = 553041
mem[31476] = 1239288
mem[8990] = 4130730
mask = 0X0000001X0000101001100001011XX11010
mem[41349] = 13700059
mem[9682] = 208485
mask = X01101X11010X110X0010010X0X010X100X0
mem[63586] = 3162312
mem[41864] = 52333
mem[60032] = 136729499
mem[64618] = 5604
mask = 000000X0X1X00010X0X1101001X100011010
mem[41032] = 219719
mem[52967] = 9957392
mem[47402] = 104156962
mem[47167] = 9809
mem[363] = 79577
mem[54862] = 908627539
mask = 000001X11001X000100000001XXX0XX101XX
mem[21062] = 25438
mem[49623] = 9679
mem[22513] = 550
mem[34523] = 1740
mask = 0111X00X10000X10X00110XXX111X1100101
mem[23521] = 1847
mem[890] = 767247
mem[7754] = 418458
mask = 000X0011X0010000100XX0101010X0010100
mem[53141] = 1033941
mem[2697] = 272988563
mem[46342] = 327691
mem[35351] = 9007
mask = 101101X110110110XX01X10X1XX00001X100
mem[48875] = 7271153
mem[46815] = 6662226
mem[27690] = 126869823
mem[24240] = 116483292
mem[8818] = 58691045
mem[18715] = 466
mask = 00X000X11001X00010010011X0001X100001
mem[19346] = 64918109
mem[35328] = 17779
mem[16765] = 5551856
mem[19204] = 517392152
mem[42112] = 24978619
mask = 000X000X10010X001X01101010011XX11100
mem[8396] = 76504
mem[18811] = 685873
mem[23612] = 2185
mem[6324] = 3578866
mem[38456] = 44018
mask = 000000XX1X0X0X1100010111011X0X110000
mem[31633] = 10638148
mem[789] = 6164866
mem[1183] = 690014
mem[65260] = 3760
mask = 00X000111001000000XX1010X0110X0X1X10
mem[38864] = 1515635
mem[7741] = 655
mask = 110000101000X0010101X0110X0X10010X01
mem[33199] = 95711
mem[279] = 15468095
mem[2163] = 851
mask = 0000001X0000000X001101111X000011100X
mem[32652] = 63092
mem[64746] = 4487
mem[50405] = 6759832
mem[14787] = 1693270
mem[36666] = 1015
mem[28924] = 37055
mask = 00X00101X0XX000010X1X10011X0111100X1
mem[59090] = 325795
mem[46540] = 893
mask = X01000000000XX110X0110100111001X0111
mem[23521] = 7655879
mem[4223] = 33054
mem[64098] = 2018828
mem[55944] = 338654692
mem[5314] = 3058
mask = 011101X11000X100X1X1X10X11000X011001
mem[12837] = 4029513
mem[53824] = 2434
mem[9609] = 32428
mem[15351] = 30670823
mask = 0000000X100000X0X0011000X11100X0X110
mem[11163] = 1742371
mem[9590] = 4927443
mem[41243] = 2682579
mem[26001] = 3017
mem[3824] = 9602
mem[46398] = 1619558
mask = X01000X1100X0X1X00X10X1010X1X0000000
mem[11018] = 4496
mem[43791] = 75
mem[23499] = 916490368
mem[37719] = 5018412
mask = 011X0000100X0111000X01X0000100101010
mem[17447] = 175144
mem[8396] = 3122
mem[23189] = 1421
mem[11947] = 4686
mem[62695] = 11318
mem[4223] = 3021
mem[15375] = 8378
mask = 0X000X00110000101X0101X0110XX100X00X
mem[19005] = 427
mem[5377] = 44821
mem[51916] = 33665096
mask = X0000011000000X0X01100X010000X000100
mem[18133] = 1062303553
mem[64271] = 331
mem[26096] = 121034814
mask = 0101001X1101000X0XX10X000111X0X1X111
mem[19930] = 22437206
mem[55934] = 1690223
mem[59471] = 14194445
mem[1983] = 15474
mem[12232] = 16491
mem[291] = 1788458
mask = 0000001111X10X1X000101101000X1110110
mem[59072] = 573926
mem[14500] = 833
mem[24512] = 1717
mask = 010X0X100000011100X101101100010000X1
mem[60619] = 817958
mem[2863] = 15508
mem[35328] = 72332355
mem[22904] = 2469185
mem[51930] = 58719042
mask = 0X000101X00X000XX10100X11010XXX01001
mem[37000] = 894
mem[13047] = 46778
mem[59396] = 3752
mask = 0101001XX0X00X01XX011X10X00100000X01
mem[275] = 644055
mem[32340] = 222079154
mem[36974] = 3445
mask = 100X01XX100X001X1001XX10100100111111
mem[42243] = 33884
mem[43868] = 23455
mem[11320] = 253636
mem[40511] = 5492
mask = 00X0X11X10X1000010000000000000000X00
mem[28854] = 6101526
mem[4781] = 122851
mem[57703] = 1610
mem[43942] = 6770
mem[53040] = 1686863
mem[52405] = 49109
mem[17020] = 26300
mask = X101001011010000X101XX001XX101000111
mem[36253] = 1611693
mem[9748] = 860957
mem[20000] = 987129
mem[16179] = 4444988
mem[22381] = 1903952
mask = 000000X0X000001100X10111XX10XX011110
mem[55330] = 35238
mem[39998] = 1571478
mem[17505] = 99381
mask = X10X0010100000XX0X01101X000XX000011X
mem[34085] = 402079130
mem[16698] = 24680
mem[4374] = 7328106
mask = 000000101X00011100X1X11X110001101100
mem[8520] = 414
mem[58007] = 67798800
mem[10896] = 1234522
mask = X111XX00100000101001100001XXX1000001
mem[15502] = 3610723
mem[29003] = 25442
mem[60005] = 35673
mem[54815] = 9564511
mem[39998] = 17758
mem[24892] = 34015406
mask = X00X0101100000X010011X000100X0010X10
mem[7828] = 36746
mem[10665] = 2607
mem[22125] = 1363
mem[11947] = 7704
mem[43623] = 38532
mem[62246] = 1245
mask = 00000011000X00XX00X10100010X1001XXX0
mem[6536] = 1008
mem[2356] = 208187005
mem[35497] = 17679606
mem[20293] = 393500248
mem[32019] = 884561264
mem[36012] = 644365
mask = 0X0X0010X000XX11000X000X00100100X011
mem[65027] = 523
mem[54119] = 46440696
mask = 10000000000000XX0101X000100111101X01
mem[37938] = 1261
mem[51930] = 250264316
mem[21896] = 808
mask = 001000X1X001X000XXXX001000X1000X0000
mem[30508] = 1749
mem[21893] = 44368050
mem[49672] = 230127
mem[54757] = 127691
mem[8726] = 236342
mem[10891] = 98801391
mem[10605] = 71342
mask = 010000X010000011000X1X000XX101101010
mem[4365] = 6290
mem[8515] = 954
mem[20937] = 161026
mem[65023] = 51216972
mask = 00000011X001000000X1000X010010XX1XXX
mem[45915] = 17602992
mem[23256] = 2419994
mem[51634] = 48875590
mem[63449] = 2008
mem[47263] = 23026
mem[49054] = 6414652
mask = 00XX000X10010000000110101XX010011X11
mem[36345] = 871178
mem[10665] = 416518
mem[45745] = 60800516
mask = 0111000010000XXX0001000X0001001011X1
mem[42762] = 10241
mem[17679] = 20507
mem[31476] = 437501635
mem[34905] = 52676
mem[11679] = 15344328
mem[8515] = 2181832
mask = 0000001111X0X00X1X010011110101101101
mem[26711] = 8112
mem[57703] = 793119
mem[8055] = 4568928
mem[32906] = 297039
mem[32019] = 206284
mem[865] = 30027
mem[11213] = 30386634
mask = 000000110X01001000X1010011X000X1X111
mem[14824] = 309750
mem[37522] = 9384
mem[55385] = 2687
mem[95] = 9945999
mem[50337] = 750
mem[4487] = 12151822
mask = 0111X0X1100001100X0110000X00X1XX1XX1
mem[51624] = 2660594
mem[37260] = 14245
mem[2790] = 38434236
mem[4295] = 15847
mem[36771] = 4011724
mem[11019] = 688
mask = 0X000011X0010000001XX10001XXX10X100X
mem[58961] = 11992472
mem[42161] = 101428848
mem[2265] = 400253009
mask = 0111000010000X11X00X1000010000X1X010
mem[57447] = 7460627
mem[37719] = 146281
mask = 0000001X10000000X0X100X0100X10001111
mem[58557] = 2672367
mem[671] = 1217
mask = 000X0X10000001X1X0011100X10101X0XX11
mem[38270] = 235496
mem[4056] = 1253323
mem[23514] = 101143901
mem[20782] = 5915
mem[24468] = 831
mem[35] = 21814820
mask = 0110X0X0100000110001100110X00X011X10
mem[30226] = 9453
mem[24706] = 701
mem[36] = 1205
mask = 000000111001000000X1XX100100111X0X0X
mem[11741] = 737
mem[46243] = 547704969
mem[22513] = 5088809
mem[58552] = 19055
mem[22987] = 670175054
mask = 0XX100100000X111000110X001XXX0X0110X
mem[55651] = 392724207
mem[34323] = 756
mem[45585] = 315548658
mem[53778] = 1498995
mem[49054] = 918982
mask = 0111XX00000010X1000110100X1000010011
mem[24405] = 16030842
mem[34723] = 2408
mem[16592] = 975
mem[26711] = 4667
mem[23842] = 8398
mem[4111] = 298
mem[65351] = 454611
mask = 0X010011X1010000000101001X011X000111
mem[59072] = 28621
mem[7680] = 404630
mem[2357] = 127254
mem[31124] = 75455625
mem[14751] = 10538495
mem[48174] = 17626696
mask = 00000X0110010000XX01001110101XX00XX1
mem[35535] = 25635
mem[61335] = 1936957
mem[2308] = 541663
mem[27552] = 30889127
mem[45608] = 119986172
mask = 0X0000011000X1X1X0010111X0100110010X
mem[39563] = 86230066
mem[9269] = 960248441
mem[3] = 12493517
mem[15540] = 370505
mem[39081] = 2958057
mem[40837] = 15462669
mask = X101X01X1X01000X00011XX011X10100111X
mem[31849] = 781106
mem[47318] = 35160612
mem[44434] = 601207
mem[53778] = 161349954
mem[51037] = 470805462
mem[2888] = 504314
mem[59994] = 25845
mask = 00000X1110010X00100000X11110X001X000
mem[4374] = 36122
mem[35006] = 247433
mem[6590] = 56517812
mem[57869] = 15324660
mem[44590] = 97397
mem[19151] = 32935825
mask = 0111XXX1100001X0X1X110000X10X1000001
mem[15474] = 2106
mem[55385] = 195234980
mem[2760] = 3966382
mem[32191] = 290323274
mem[11542] = 13639
mask = 0X00X01X1101000000010X11X00X000111X0
mem[62426] = 929
mem[37938] = 21768260
mem[19648] = 991
mem[11683] = 102189
mem[15537] = 5667
mem[41906] = 361913048
mask = 0XX11000X0XX001X10010101110X01X000X1
mem[27451] = 28234893
mem[29283] = 938
mem[5816] = 31962
mem[13441] = 30702211
mem[39686] = 22756467
mem[46224] = 55086
mask = 0X0001011X0X0000100X1001110X00X10X01
mem[45569] = 40004
mem[32504] = 467685234
mem[14454] = 706605
mem[34290] = 432808
mem[4111] = 3388805
mem[17870] = 904
mem[51132] = 12723
mask = 0X000X0X000000X010000X0X0010000X0000
mem[6365] = 14592
mem[7251] = 1597900
mask = 0X00001110010X00X0XXX0X10100X0100000
mem[47402] = 21704434
mem[58466] = 93570
mem[10281] = 107593039"""

parsed_input=input.splitlines()

reg1=re.compile(r"""
                mask\s=\s(.*)$
                """,re.VERBOSE)

reg2=re.compile(r"""
                ^mem.(\d+).
                \s=\s(\d+)$
                """,re.VERBOSE)


def binary_to_base10(s):
    ans=0
    for i in range(1,len(s)+1):
        if s[-i]=='1':
            ans+=2**(i-1)
    return ans

def base10_to_binary(x):
    exps=[0 for a in range(36)]
    remainder=x
    while remainder>0:
        exp = int(math.log(remainder,2))
        nearest_num = 2**exp
        exps[-exp-1]=1
        remainder-=nearest_num
    return ''.join([str(b) for b in exps])

mask=''
wildcards=[]
mems=defaultdict()

for line in parsed_input:
    if line[0:4]=='mask':
        binary_string=re.split(reg1,line)
        mask=binary_string[1]
        wildcards = [x.start() for x in re.finditer('X',mask)]
    else:
        parsed_line = re.split(reg2,line)
        mem_address = int(parsed_line[1])
        raw_value = int(parsed_line[2])
        binary_str = base10_to_binary(mem_address)
        masked_binary_str = ['0' for a in range(36)]
        for i in range(1,len(mask)+1):
            if mask[-i]=='X':
                masked_binary_str[-i]='0'
            elif mask[-i]=='1':
                masked_binary_str[-i]='1'
            else:
                masked_binary_str[-i]=binary_str[-i]
        masked_binary_str = ''.join(masked_binary_str)
        masked_value=binary_to_base10(masked_binary_str)
        mems[masked_value]=raw_value
        for r in range(1,len(wildcards)+1):
            for c in combinations(wildcards,r):
                mem_clone=list(masked_binary_str)
                for j in c:
                    mem_clone[j]='1'
                alt_masked_value=binary_to_base10(''.join(mem_clone))
                mems[alt_masked_value]=raw_value

ans=0
for el in mems.items():
    ans+=el[1]

print(ans)