Day 14: Docking Data

For the first part, the thing that got me that it wasn't actually a bitmask (not a traditional one anyway). You just had to compare each element in the value and the mask pairwise to produce the "masked" value. I took advantage of Python's nifty format and int functions to parse the data into and out of binary representation.

import re
import sys

# Constants

WORD_SIZE = 36
MASK_RE   = r'mask = (.*)'
MEMORY_RE = r'mem\[(\d+)\] = (\d+)'

# Functions

def mask_value(mask, value):
    return ''.join([
        v if m == 'X' else m for m, v in zip(mask, value)
    ])

def int_to_binary(i):
    return format(int(i), f'0{WORD_SIZE}b')

def process_instructions():
    memory = {}
    mask   = '0'*WORD_SIZE

    for line in sys.stdin:
        if line.startswith('mask'):
            mask = re.findall(MASK_RE, line)[0]
        else:
            address, value  = re.findall(MEMORY_RE, line)[0]
            memory[address] = mask_value(mask, int_to_binary(value))

    return memory

# Main Execution

def main():
    memory = process_instructions()
    total  = sum(int(v, 2) for v in memory.values())

    print(total)

if __name__ == '__main__':
    main()

For the second part, the main challenge was how to generate all the new addresses from the "masked" address (ie. how to expand those floating 'X's). What I did was a generated all the permutations of '01' with a length equal to the number of floating numbers, and then I replaced the X's in the address by the elements of each permutation (the code says product). For each of these new addresses, I yield from my generator function and then used that address to store the current value.

import itertools
import re
import sys

# Constants

WORD_SIZE = 36
MASK_RE   = r'mask = (.*)'
MEMORY_RE = r'mem\[(\d+)\] = (\d+)'

# Functions

def mask_address(mask, address):
    return ''.join([
        a if m == '0' else m for m, a in zip(mask, address)
    ])

def int_to_binary(i):
    return format(int(i), f'0{WORD_SIZE}b')

def expand_addresses(address):
    floats = address.count('X')

    for product in map(list, itertools.product('01', repeat=floats)):
        new_address = address[:]
        while 'X' in new_address:
            new_address = new_address.replace('X', product.pop(), 1)
        yield int(new_address, 2)

def process_instructions():
    memory = {}
    mask   = '0'*WORD_SIZE

    for line in sys.stdin:
        if line.startswith('mask'):
            mask = re.findall(MASK_RE, line)[0]
            continue

        address, value = re.findall(MEMORY_RE, line)[0]
        address_masked = mask_address(mask, int_to_binary(address))
        
        for address in expand_addresses(address_masked):
            memory[address] = value

    return memory

# Main Execution

def main():
    memory = process_instructions()
    total  = sum(int(v) for v in memory.values())

    print(total)

if __name__ == '__main__':
    main()

I made an alternative version of my expand_addresses function in the form of a recursive generator (and avoids using itertools). The idea here is that you scan across the address until you hit an X. Once you do, you recurse twice: first replacing the 'X' at the current index with a 0 and another by replacing the 'X' with a 1. If the current digit is not an X, you just recurse to the next index. The base case is simply when the index has reached the length of the string (ie. the WORD_SIZE or 36 for this problem).

def expand_addresses(address, index=0):
    ''' Alternative recursive solution '''
    if index == WORD_SIZE:
        yield address                                                                         
    elif address[index] == 'X':
        yield from expand_addresses(address[:index] + '0' + address[index+1:], index + 1)
        yield from expand_addresses(address[:index] + '1' + address[index+1:], index + 1)
    else:
        yield from expand_addresses(address, index + 1)

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::HashMap;

#[macro_use]
extern crate text_io;

fn build_mask(mask_str: &str) -> Vec<(usize,usize)> {
    let mut mask: Vec<(usize,usize)> = Vec::new();
    for (i,bit) in mask_str.chars().enumerate() {
        match bit {
            '0' | '1' => { mask.push((i,bit.to_digit(10).unwrap() as usize)); },
            'X' => {},
            other => panic!("Unknown character in bitmask: {}", other),
        }
    }
    mask
}

fn base10_to_binary_vec(base10: usize) -> Vec<usize> {
    format!("{:036b}", base10)
        .chars()
        .map(|c| c.to_digit(10).unwrap() as usize)
        .collect::<Vec<_>>()
}

fn apply_mask(mask_str: &str, addr_str: &str) -> String {
    let mask: Vec<_> = mask_str.chars().collect();
    let addr: Vec<_> = addr_str.chars().collect();
    let mut result = String::new();
    for i in 0..mask_str.len() {
        match &mask[i] {
            '0' => result.push_str(&addr[i].to_string()),
            '1' => result.push_str("1"),
            'X' => result.push_str("X"),
            other => panic!("Unknown character: {}", other),
        }
    }
    result
}

fn floating_addresses(mask_str: &str, start: usize) -> Vec<String> {
    let mask: Vec<_> = mask_str.chars().collect();
    let mut next: String = mask_str[0..std::cmp::min(start,mask.len())].to_string();
    let mut addrs: Vec<String> = Vec::new();
    for i in start..mask.len() {
        match &mask[i] {
            '0' | '1' => { next.push_str(&mask[i].to_string()) },
            'X' => {
                let mut next0 = next.clone(); next0.push_str("0");
                let mut next1 = next.clone(); next1.push_str("1");
                if i == mask.len() - 1 {
                    addrs.push(next0);
                    addrs.push(next1);
                } else {
                    next0.push_str(&mask_str[i+1..]);
                    next1.push_str(&mask_str[i+1..]);
                    for a in floating_addresses(&next0, i+1) {
                        addrs.push(a);
                    }
                    for a in floating_addresses(&next1, i+1){
                        addrs.push(a);
                    }
                }
            },
            other => panic!("Unknown character: {}", other),
        }
    }
    if next.len() == 36 { addrs.push(next); }
    addrs
        .iter()
        .filter(|x| &x.len() == &36usize)
        .filter(|x| x.chars().filter(|c| c == &'X').count() == 0)
        .map(|x| x.clone())
        .collect()
}

fn part1(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    let mut mem: HashMap<usize,usize> = HashMap::new();
    let mut mask: Vec<(usize,usize)> = Vec::new();
    for cmd in input {
        match &cmd[0..4] {
            "mask" => {
                mask.clear();
                mask = build_mask(cmd.split_ascii_whitespace().last().unwrap());
            },
            "mem[" => {
                let addr: usize;
                let value: usize;
                scan!(cmd.bytes() => "mem[{}] = {}", addr, value);
                let mut value_b = base10_to_binary_vec(value);
                // Apply mask
                for (i,b) in &mask { value_b[*i] = *b; }
                let value = value_b.iter().map(|x| x.to_string()).collect::<Vec<_>>().concat();
                let value = usize::from_str_radix(&value,2).unwrap();
                mem.insert(addr,value);
            },
            other => panic!("Invalid program command: {}", other),
        }
    }

    let part1: usize = mem.iter().map(|(_,v)| v).sum();
    println!("Part 1: {}", part1); // 6317049172545

    Ok(())
}

fn part2(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    let mut mem: HashMap<usize,usize> = HashMap::new();
    let mut mask = String::new();
    for cmd in input {
        match &cmd[0..4] {
            "mask" => {
                mask.clear();
                mask = cmd.split_ascii_whitespace().last().unwrap().to_string();
            },
            "mem[" => {
                let addr: usize;
                let value: usize;
                scan!(cmd.bytes() => "mem[{}] = {}", addr, value);
                let addr = format!("{:036b}", addr).chars().collect::<String>();
                let renderedmask = apply_mask(&mask,&addr);          
                for addr in floating_addresses(&renderedmask,0) {
                    let addr = usize::from_str_radix(&addr,2).unwrap();
                    mem.insert(addr,value);
                }
            },
            other => panic!("Invalid program command: {}", other),
        }
    }

    let part2: usize = mem.iter().map(|(_,v)| v).sum();
    println!("Part 2: {}", part2); // 3434009980379

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    part1(&filename).unwrap();
    part2(&filename).unwrap();
}

For this first one I pre-allocated some memory and then turned my value into a list of characters so that I could play with the digits and override them as necessary. The mask just stores which bits get replaced in a key, value pair. Then when I was done with the processing, just turn into an int and dump it into memory

I also googled a decimal to binary method, because I didn't feel like writing one myself.

I also padded my value all the way up to 36 bits, so that I wouldn't to worry about indexing and what-not. It would always be 36 bits long. I had originally though about reversing the order of the list instead, but I though the zero-padding was a more elegant solution for the index problem. Less of a headache too.

import re
data = test_data.split('\n')
#data = input_data.split('\n')
current_mask = None

pattern = re.compile('mem\[(\d+)\] = (\d+)')

memory = [None] * 1000000
mask_data = []

def decimalToBinary(n):  
    return bin(n).replace("0b", "") 

for row in data:
    if 'mask' in row:
        bitmask = row.split(' = ')[1]
        #bitmask = bitmask[::-1]
        mask_data = []
        for index,char in enumerate(bitmask):
            if char == '1' or char == '0':
                mask_data.append([index,char])
            
                #print(index, char)
        #print(mask_data)
    else:
        captured = pattern.search(row)
        address = int(captured.group(1))
        val = int(captured.group(2))
        val = str(decimalToBinary(val))
        val = list(val.zfill(36))
        #val = val[::-1]
        
        for mask_bit in mask_data:
            val[mask_bit[0]] = mask_bit[1]
        val = ''.join(val)
        memory[address] = int(val,2)
running_sum = 0
for val in memory:
    if val is not None:
        running_sum = running_sum + val
        
print(running_sum)

This one was a bit more complicated. My type conversion worked well enough, but I had to do it on the address, instead of the value. And I copied over the entire mask, instead of just the 0's and 1's. Also I switched memory over to a dict, because 2^36 is a LOT of addresses to try to hold in my RAM.

I decided to go with a recursive solution to split my addresses. It would walk through a given address. If it ever ran into an 'X' it would make 2 copies of the address, one with a 1 and the other with a 0. And it would call itself on both of them. The tricky part was making sure that I had my data storage correct when passing between levels of the recursion. Which is to say, the raw address vs a list containing multiple addresses

I realized later that another method that could work would be to generate a list of all X -> 0/1 combinations when you process the mask. Then apply that over each address the same way you did in part 1. It's probably slightly more efficient too.

import re
#data = test_data_2.split('\n')
data = input_data.split('\n')
current_mask = None

pattern = re.compile('mem\[(\d+)\] = (\d+)')

memory = {}
mask_data = []

def decimalToBinary(n):  
    return bin(n).replace("0b", "") 
def address_split(address):
    #print(f'Attempting to split: {"".join(address)}')
    addresses_to_return = []
    if 'X' not in address:
        #print(f'Splitting Not Necessary')
        return [address]
    for index,char in enumerate(address):
        if char == 'X':
            high = list(address)
            high[index] = '1'
            low = list(address)
            low[index] = '0'
            #print(f'Split into: {"".join(high)}')
            #print(f'Split into: {"".join(low)}')
            
            addresses_to_return = addresses_to_return + address_split(high) + address_split(low)
            return addresses_to_return
            

for row in data:
    if 'mask' in row:
        bitmask = row.split(' = ')[1]
        #bitmask = bitmask[::-1]
        mask_data = []
        for index,char in enumerate(bitmask):
            mask_data.append([index,char])
                #print(index, char)
        #print(mask_data)
    else:
        captured = pattern.search(row)
        address = int(captured.group(1))
        val = int(captured.group(2))
        address = str(decimalToBinary(address))
        address = list(address.zfill(36))
        
        for mask_bit in mask_data:
            if mask_bit[1] == '1':
                address[mask_bit[0]] = mask_bit[1]
            if mask_bit[1] == 'X':
                address[mask_bit[0]] = 'X'
        addresses = address_split(address)
        for address in addresses:
            memory[int(''.join(address))] = val
running_sum = 0
for val in memory.values():
    if val is not None:
        running_sum = running_sum + val
        
print(running_sum)

• I've mentioned regex a few times now, but I don't think I ever explained what it is. Regex is shorthand for 'regular expressions'. They're a way of searching for specific patterns within text. So for example, if you needed to find something formatted like a street address, you could use a regular expression to find that. They tend to look like a bunch of arcane symbols until you learn to read them, but they can be extremely useful. I highly recommend https://regexone.com/ for learning how to actually use regex. And https://regexr.com/ is great for testing them out. I probably should have mentioned that like a week ago

• When working with the mask, it's going to be important to know what index you're working with. Especially since some of your numbers will be shorter than the relevant digits in your mask. There are a number of ways to deal with this such as converting to binary and then left-padding it.

• I ended up using a lot of type conversion for this one. Some of the different component problems were much easier in different forms, so I swapped between them as was appropriate for the given task

• You're going to need to generate a bunch of addresses. There are a few ways to do it, for example, I used recursion. But interestingly, a given mask should always generate the same number of addresses and configuration of bits that need to be overwritten.

• The memory addresses get much bigger in Part B. Pre-allocating a fixed area works fine for part A, but don't try it for part B unless you're running doing AoC on a supercomputer.

def apply_mask_p1(mask, num)
  mask.reverse.chars.each_with_index do |c, i|
    case c
    when 'X'
      next
    when '0'
      num = num & ~(1 << i)
    when '1'
      num = num | (1 << i)
    end
  end
  return num
end

def compute_p1(input)
  prog = input.lines.map(&:strip)
  mem = Hash.new(0)
  mask = "";

  prog.each do |line|
    if line.start_with?("mask")
      mask = line.split(' ')[2]
    elsif line.start_with?('mem')
      c = line.match(/mem\[(\d+)\] = (\d+)/).captures
      mem[c[0].to_i] = apply_mask_p1(mask, c[1].to_i)
    end
  end

  return mem.values.reduce(:+)
end

def apply_mask_p2(mask, num)
  base = num | mask.tr("X","0").to_i(2)
  nums = []

  floating_bits = mask.reverse.chars.each_with_index.filter { |c, i| c == 'X' }.map { |c,i| i }
  (2 ** floating_bits.size).times do |i|
    num = base
    floating_bits.each_with_index do |b, j|
      bit = (i & (1 << j)) >> j
      case bit
      when 1
        num = num | (1 << b)
      when 0
        num = num & ~(1 << b)
      end
    end
    nums << num
  end

  return nums
end

def compute_p2(input)
  prog = input.lines.map(&:strip)
  mem = Hash.new(0)
  mask = "";

  prog.each_with_index do |line, i|
    if line.start_with?("mask")
      mask = line.split(' ')[2]
    elsif line.start_with?('mem')
      c = line.match(/mem\[(\d+)\] = (\d+)/).captures
      addrs = apply_mask_p2(mask, c[0].to_i)
      addrs.each do |a|
        mem[a] = c[1].to_i
      end
    end
  end

  return mem.values.reduce(:+)
end

import re

with open("input.txt") as inputFile:
    input = inputFile.read().split("\n")


def instruction(memoryString):
    address, value = re.findall(r'mem\[(\d+)\] = (\d+)', memoryString)[0]
    return int(address), int(value)


def maskV1(maskString):
    mask = re.findall(r'mask = ([X|0|1]+)', maskString)[0]
    andMask = int(mask.replace("X", "1"), 2)
    orMask = int(mask.replace("X", "0"), 2)
    return andMask, orMask


def processV1(input):
    andMask = 0
    orMask = 0
    memory = {}
    for line in input:
        if re.search(r'(mask)', line):
            andMask, orMask = maskV1(line)
        else:
            address, value = instruction(line)
            value = value & andMask | orMask
            memory[address] = value
    print("Sum of all memory values (v1):", sum(memory.values()))


def maskV2(maskString):
    mask = re.findall(r'mask = ([X|0|1]+)', maskString)[0]
    orMask = int(mask.replace("X", "0"), 2)
    bitFlips = []
    for pos in range(0, len(mask)):
        if mask[pos] == "X":
            # add value with a single bit at this position
            bitFlips.append(pow(2, len(mask) - 1 - pos))
    return orMask, bitFlips


def writeFlipped(memory, address, value, index, bitFlips):
    """
    Write value to every address by flipping the address bits
    in bitFlips to either 0 or 1
    """
    if index < len(bitFlips):
        writeFlipped(memory, address | bitFlips[index],
                     value, index + 1, bitFlips)
        writeFlipped(memory, address & ~ bitFlips[index],
                     value, index + 1, bitFlips)
    else:
        memory[address] = value


def processV2(input):
    orMask = 0
    bitFlips = []
    memory = {}
    for line in input:
        if re.search(r'(mask)', line):
            orMask, bitFlips = maskV2(line)
        else:
            address, value = instruction(line)
            address = address | orMask
            writeFlipped(memory, address, value, 0, bitFlips)
    print("Sum of all memory values (v2):", sum(memory.values()))


processV1(input)
processV2(input)

function main()

    input = []
    open("Day14/input.txt") do fp
        input = split.(readlines(fp), ' ')
    end

    lines = translate_lines(input)
    result_1 = map_memory_sum(lines)

    println(result_1)

end

function map_memory_sum(lines)

    memory = Dict()
    mask = nothing
    for line in lines
        if line[1] == 'm'
            mask = line[2]
        else
            value = apply_mask(line[3], mask)
            memory[line[2]] = parse(Int, reverse(value), base = 2)
        end
    end
    return sum(values(memory))
end


function translate_lines(lines)

    output = []
    for line in lines

        if line[1] == "mask"
            push!(output, ('m', translate_mask(line[3])))
        else
            location = parse(Int, line[1][5:end-1])
            value = reverse(bitstring(parse(Int, line[3])))
            push!(output, ('a', location, value))
        end
    end
    return output
end

function translate_mask(mask)
    mask = reverse(mask) # little endian time
    output = Dict()
    for (index, char) in enumerate(mask)
        if char == '1' || char == '0'
            output[index] = string(char)
        end
    end
    return output
end

function apply_mask(value, mask)
    for (location, mask_val) in mask
        value = value[1:location-1] * mask_val * value[location+1:end]
    end
    return value
end



main()

@@ -10,6 +10,11 @@ function main()
 
     println(result_1)
 
+    lines_2 = translate_lines2(input)
+    result_2 = map_memory_sum2(lines_2)
+
+    println(result_2)
+
 end
 
 function map_memory_sum(lines)
@@ -27,6 +32,24 @@ function map_memory_sum(lines)
     return sum(values(memory))
 end
 
+function map_memory_sum2(lines)
+
:...skipping...
diff --git a/Day14/main.jl b/Day14/main.jl
index ecdf018..de3c538 100644
--- a/Day14/main.jl
+++ b/Day14/main.jl
@@ -10,6 +10,11 @@ function main()
 
     println(result_1)
 
+    lines_2 = translate_lines2(input)
+    result_2 = map_memory_sum2(lines_2)
+
+    println(result_2)
+
 end
 
 function map_memory_sum(lines)
@@ -27,6 +32,24 @@ function map_memory_sum(lines)
     return sum(values(memory))
 end
 
+function map_memory_sum2(lines)
+
+    memory = Dict()
+    mask = nothing
+    for line in lines
+        if line[1] == 'm'
+            mask = line[2]
+        else
+            # TODO: Make this work
+            locations = location_mask(mask, line[2])
+            for location in locations
+                memory[location] = line[3]
+            end
+        end
+    end
+    return sum(values(memory))
+end
+
 
 function translate_lines(lines)
 
@@ -44,6 +67,36 @@ function translate_lines(lines)
     return output
 end
 
+function translate_lines2(lines)
+
+    output = []
+    for line in lines
+
+        if line[1] == "mask"
+            push!(output, ('m', reverse(line[3])))
+        else
+            location = reverse(bitstring(parse(Int, line[1][5:end-1])))
+            value = parse(Int, line[3])
+            push!(output, ('a', location, value))
+        end
+    end
+    return output
+end
+
+function location_mask(mask, location, trailing="")
+
+    if length(mask) == 0
+        return parse(Int, reverse(trailing * location), base = 2)
+    elseif mask[1] == '0'
+        return [location_mask(mask[2:end], location[2:end], trailing * location[1])...]
+    elseif mask[1] == '1'
+        return [location_mask(mask[2:end], location[2:end], trailing * "1")...]
+    elseif mask[1] == 'X'
+        return [location_mask(mask[2:end], location[2:end], trailing * "1")...,
+                location_mask(mask[2:end], location[2:end], trailing * "0")...]
+    end
+end
+
 function translate_mask(mask)
     mask = reverse(mask) # little endian time
     output = Dict()

#!/usr/bin/awk -f
{
        split($0, input, /(\[|\] = | = )/)
        if (input[1] == "mask") {
                mask = input[2]
                next
        }

        adr = input[2]
        dec = input[3]

        val = ""
        while (dec) {
                val = dec%2 val
                dec = int(dec/2)
        }

        while (length(val) < length(mask))
                val = 0 val

        for (i = 1; i <= length(mask); i = j) {
                if ((j = match(substr(mask, i), /[01]/)+i) == i)
                        break
                val = substr(val, 1, j-2) substr(mask, j-1, 1) substr(val, j)
        }

        mem[adr] = val
}

END {
        sum = 0
        for (adr in mem) {
                dec = 0

                for (i = 1; i <= length(mem[adr]); ++i) {
                        bit = substr(mem[adr], i, 1)
                        dec = (dec * 2)+bit
                }

                sum += dec
        }

        print sum
}

#!/usr/bin/awk -f
function bin2dec(bin,   i, bit, dec) {
        for (i = 1; i <= length(bin); ++i) {
                bit = substr(bin, i, 1)
                dec = (dec * 2)+bit
        }

        return dec
}

function dec2bin(dec,   bin) {
        while (dec) {
                bin = dec%2 bin
                dec = int(dec/2)
        }

        return bin
}

function float(mem, adr, val,   i, j) {
        for (i = 0; i <= 1; ++i) {
                j = adr
                sub("X", i, j)
                if (j ~ "X")
                        float(mem, j, val)
                else
                        mem[bin2dec(j)] = val
        }
}

{
        split($0, input, /(\[|\] = | = )/)
        if (input[1] == "mask") {
                mask = input[2]
                next
        }

        adr = dec2bin(input[2])
        val = input[3]

        while (length(adr) < length(mask))
                adr = 0 adr

        for (i = 1; i <= length(mask); i = j) {
                if ((j = match(substr(mask, i), /[1X]/)+i) == i)
                        break
                adr = substr(adr, 1, j-2) substr(mask, j-1, 1) substr(adr, j)
        }

        float(mem, adr, val)
}

END {
        for (adr in mem)
                sum += mem[adr]

        print sum
}