Advent of Code 2020 Solution Megathread - Day 14: Docking Data

module Main where import Data.Bits import qualified Data.Map as Map type Bitflip = Int -> Int type FloatAddress = Int -> [Int] type Mask = ([Bitflip], [FloatAddress]) type MaskParser = Int -> String -> Mask -> Mask type Memory = Map.Map Int Int data Op = Asn Int Int | Mask Mask ------------------ Part 1 -------------------- parseMask :: MaskParser parseMask _ [] mask = mask parseMask pow ('0':xs) (a,b) = parseMask (pow+1) xs ((complement (2^pow) .&.):a,b) parseMask pow ('1':xs) (a,b) = parseMask (pow+1) xs (((2^pow) .|.):a,b) parseMask pow ('X':xs) (a,b) = parseMask (pow+1) xs (a,b) solve_1 :: [Op] -> [Bitflip] -> Memory -> Int solve_1 [] _ mem = sum $ map snd $ Map.toList mem solve_1 (Mask (bflips,_) : xs) _ mem = solve_1 xs bflips mem solve_1 (Asn a b : xs) mask mem = solve_1 xs mask (Map.insert a (foldl (flip ($)) b mask) mem) ------------------ Part 2 -------------------- writeFloating :: Int -> Int -> [Int] writeFloating pow i = [complement (2^pow) .&. i, (2^pow) .|. i] parseMask2 :: MaskParser parseMask2 _ [] mask = mask parseMask2 pow ('0':xs) mask = parseMask2 (pow+1) xs mask parseMask2 pow ('1':xs) (a,b) = parseMask2 (pow+1) xs (((2^pow) .|.):a, b) parseMask2 pow ('X':xs) (a,b) = parseMask2 (pow+1) xs (a, writeFloating pow : b) solve_2 :: [Op] -> Mask -> Memory -> Int solve_2 [] _ mem = sum $ map snd $ Map.toList mem solve_2 (Mask mask : xs) _ mem = solve_2 xs mask mem solve_2 (Asn a b : xs) (bflips, floats) memory = solve_2 xs (bflips, floats) $ foldl (flip (`Map.insert` b)) memory addrs where addr = foldl (flip ($)) a bflips addrs = foldl (>>=) [addr] floats ------------------ Main -------------------- parseOp :: MaskParser -> String -> Op parseOp parser s = if head ws == "mask" then Mask $ parser 0 (reverse $ ws !! 2) ([],[]) else Asn (read $ takeWhile (/= ']') $ drop 4 (head ws)) (read (ws !! 2)) where ws = words s main :: IO () main = do input <- lines <$> readFile "input.txt" let ops1 = map (parseOp parseMask ) input ops2 = map (parseOp parseMask2) input print $ solve_1 (tail ops1) ((\(Mask m) -> fst m) $ head ops1) Map.empty print $ solve_2 (tail ops2) ((\(Mask m) -> m ) $ head ops2) Map.empty 

use std::collections::HashMap; use std::fs::File; use std::io::prelude::*; use parser::*; // --- file read fn read_file(filename: &str) -> std::io::Result<String> { let mut file = File::open(filename)?; let mut contents = String::new(); file.read_to_string(&mut contents)?; Ok(contents) } // -- model type Address = u64; type Word = u64; #[derive(Debug, Eq, PartialEq)] enum Instruction { Mask { zeros: Word, ones: Word }, Write { address: Address, value: Word } } type Program = Vec<Instruction>; struct Machine { memory: HashMap<Address, Word>, mask_zeros: Word, mask_ones: Word, mask_floating: Word } impl Machine { fn new() -> Self { Machine { memory: HashMap::new(), mask_zeros: 0, mask_ones: 0, mask_floating: 0 } } fn run(&mut self, program: &Program) { program.iter().for_each(|instruction| match instruction { Instruction::Mask { zeros, ones } => { self.mask_zeros = *zeros; self.mask_ones = *ones; } Instruction::Write { address, value } => { self.memory.insert(*address, value & (!self.mask_zeros) | self.mask_ones); } }); } fn run_v2(&mut self, program: &Program) { program.iter().for_each(|instruction| match instruction { Instruction::Mask { zeros, ones } => { self.mask_zeros = *zeros; self.mask_ones = *ones; self.mask_floating = !(zeros | ones) & 0xfffffffff; } Instruction::Write { address, value } => { let address = address & !(self.mask_floating) | self.mask_ones; self.write_floating_address(&address, value, 0); } }); } fn write_floating_address(&mut self, address: &Address, value: &Word, bit_index: usize) { let bit_mask = 1 << bit_index; if self.mask_floating & bit_mask != 0 { [address & !bit_mask, address | bit_mask].iter().for_each(|address| { self.memory.insert(*address, *value); self.write_floating_address(address, value, bit_index + 1); }); } else if self.mask_floating >> bit_index != 0 { self.write_floating_address(address, value, bit_index + 1) } } fn sum_of_all_memory_words(&self) -> Word { self.memory.values().sum() } } // -- parser fn parse_input(input: &str) -> ParseResult<Program> { #[derive(Copy,Clone)] enum MaskBit { Zero, One, Unchanged } let mask_bit = match_literal("X").means(MaskBit::Unchanged) .or(match_literal("0").means(MaskBit::Zero)) .or(match_literal("1").means(MaskBit::One)); let mask = right(match_literal("mask = "), one_or_more(mask_bit)) .map(|bits| { let (zeros, ones) = bits.iter().rev().enumerate().fold( (0, 0), |(zeros, ones), (bit_index, mask_bit)| match mask_bit { MaskBit::Zero => (zeros | 1 << bit_index, ones), MaskBit::One => (zeros, ones | 1 << bit_index), MaskBit::Unchanged => (zeros, ones), } ); Instruction::Mask { zeros, ones } }); let write = pair( right(match_literal("mem["), integer), right(match_literal("] = "), integer), |address, value| Instruction::Write { address: address as Address, value: value as Word } ); let program = zero_or_more(whitespace_wrap( either(mask, write) )); program.parse(input) } // --- problems fn part1(program: &Program) -> Word { let mut machine = Machine::new(); machine.run(&program); machine.sum_of_all_memory_words() } fn part2(program: &Program) -> Word { let mut machine = Machine::new(); machine.run_v2(&program); machine.sum_of_all_memory_words() } fn main() { let input = read_file("./input.txt").unwrap(); let program = parse_input(&input).unwrap().1; println!("part 1 {:?}", part1(&program)); println!("part 2 {:?}", part2(&program)); } #[cfg(test)] mod tests { use super::*; fn sample_program() -> &'static str { "mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X mem[8] = 11 mem[7] = 101 mem[8] = 0" } #[test] fn test_parser() { let program = parse_input(sample_program()); assert_eq!(program, Ok(("", vec![ Instruction::Mask { zeros: 2, ones: 64 }, Instruction::Write { address: 8, value: 11 }, Instruction::Write { address: 7, value: 101 }, Instruction::Write { address: 8, value: 0 } ]))); } #[test] fn test_part1() { let program = parse_input(sample_program()).unwrap().1; assert_eq!(part1(&program), 165); } #[test] fn test_part2() { let program = parse_input(" mask = 000000000000000000000000000000X1001X mem[42] = 100 mask = 00000000000000000000000000000000X0XX mem[26] = 1 ").unwrap().1; assert_eq!(part2(&program), 208); } } 

data Inst = Mask Integer Integer -- mask with off bits and mask with on bits | Mem Integer Integer deriving (Show, Eq) type Program = [Inst] parse :: [String] -> Program parse = map aux where aux ('m':'a':'s':'k':' ':'=':' ':mask) = let (off, ""):_ = readInt 2 (const True) (fromEnum . (== '1')) mask (on, ""):_ = readInt 2 (const True) (fromEnum . (/= '0')) mask in Mask on off aux xs = let idx = read (takeWhile isDigit (drop 4 xs)) :: Integer n = read (drop 2 (dropWhile (/= '=') xs)) :: Integer in Mem idx n task1 :: [Inst] -> Integer task1 = M.foldr (+) 0 . snd . foldl' (uncurry aux) ((0, 0), M.empty) where aux _ mem (Mask on off) = ((on, off), mem) aux (on, off) mem (Mem idx value) = ((on,off), M.insert idx (value .&. on .|. off) mem) task2 :: [Inst] -> Integer task2 = M.foldr (+) 0 . snd . foldl' (uncurry aux) ((0, 0), M.empty) where aux _ mem (Mask on off) = ((on, off), mem) aux (on,off) mem (Mem idx value) = ((on, off), let idxs = map (xor (idx .|. off)) (bitPowerSet (off `xor` on)) in foldl' (\mem idx -> M.insert idx value mem) mem idxs) -- function from reddit bitPowerSet:: Integer -> [Integer] bitPowerSet bits = chooseBits <$> [0..1 `shiftL` popCount bits - 1] where chooseBits i = fst $ foldl' (f i) (0, bits) [0..popCount bits - 1] f i (x, k) j = (x `xor` bits .&. (k `xor` (k - i `shiftR` j .&. 1)), k .&. (k - 1)) main :: IO () main = do insts <- readFile "day14_input" <&> lines <&> parse print (task1 insts) print (task2 insts) 

 IDENTIFICATION DIVISION. PROGRAM-ID. AOC-2020-14-1. AUTHOR ANNA KOSIERADZKA. ENVIRONMENT DIVISION. INPUT-OUTPUT SECTION. FILE-CONTROL. SELECT INPUTFILE ASSIGN TO "d14.input" ORGANIZATION IS LINE SEQUENTIAL. DATA DIVISION. FILE SECTION. FD INPUTFILE RECORD IS VARYING IN SIZE FROM 1 to 99 DEPENDING ON REC-LEN. 01 INPUTRECORD PIC X(99). WORKING-STORAGE SECTION. 01 FILE-STATUS PIC 9 VALUE 0. 01 REC-LEN PIC 9(2) COMP. 01 WS-MASK PIC X(36). 01 WS-ADDR PIC 9(12). 01 WS-VAL PIC 9(12). 01 WS-VAL-DEC PIC 9(12) VALUE 0. 01 WS-VAL-BIN PIC X(36) VALUE SPACE. 01 WS-MEM PIC 9(12) VALUE 0 OCCURS 65536 TIMES. 01 RESULT PIC 9(16) VALUE 0. 77 WS-D PIC 9. LOCAL-STORAGE SECTION. 01 I UNSIGNED-INT VALUE 0. PROCEDURE DIVISION. 001-MAIN. OPEN INPUT INPUTFILE. PERFORM 002-READ UNTIL FILE-STATUS = 1. CLOSE INPUTFILE. PERFORM SUM-MEMORY. DISPLAY RESULT. STOP RUN. 002-READ. READ INPUTFILE AT END MOVE 1 TO FILE-STATUS NOT AT END PERFORM 003-PROCESS-RECORD END-READ. 003-PROCESS-RECORD. IF INPUTRECORD(1:4) = "mask" THEN MOVE INPUTRECORD(8:36) TO WS-MASK ELSE UNSTRING INPUTRECORD(5:36) DELIMITED BY "=" INTO WS-ADDR WS-VAL MOVE WS-VAL TO WS-VAL-DEC PERFORM DEC-TO-BIN PERFORM APPLY-MASK PERFORM BIN-TO-DEC MOVE WS-VAL-DEC TO WS-MEM(WS-ADDR) END-IF. APPLY-MASK. PERFORM VARYING I FROM 1 BY 1 UNTIL I > 36 IF NOT WS-MASK(I:1) = 'X' THEN MOVE WS-MASK(I:1) TO WS-VAL-BIN (I:1) END-IF END-PERFORM. DEC-TO-BIN. MOVE SPACE TO WS-VAL-BIN. PERFORM VARYING I FROM 36 BY -1 UNTIL I = 0 DIVIDE WS-VAL-DEC BY 2 GIVING WS-VAL-DEC REMAINDER WS-D MOVE WS-D TO WS-VAL-BIN(I:1) END-PERFORM. BIN-TO-DEC. MOVE 0 TO WS-VAL-DEC. PERFORM VARYING I FROM 1 BY 1 UNTIL I > 36 COMPUTE WS-VAL-DEC = WS-VAL-DEC * 2 IF WS-VAL-BIN(I:1) = 1 THEN COMPUTE WS-VAL-DEC = WS-VAL-DEC + 1 END-IF END-PERFORM. SUM-MEMORY. PERFORM VARYING I FROM 1 BY 1 UNTIL I > 65536 ADD WS-MEM(I) TO RESULT END-PERFORM. 

struct MaskAndValues { mask: HashMap<u8, u8>, values: Vec<(usize, usize)>, } impl MaskAndValues { fn add_values(&self, totals: &mut HashMap<usize, usize>) { for (key, value) in &self.values { totals.insert(*key, self.masked_value(value)); } } fn add_values_multiple_places(&self, totals: &mut HashMap<usize, usize>) { for (key, value) in &self.values { let keys = self.get_keys(key); for k in keys { totals.insert(k, *value); } } } fn get_keys(&self, key: &usize) -> Vec<usize> { let bits = key.view_bits::<Lsb0>(); let mut bits = BitVec::from_bitslice(bits); for (pos, val) in &self.mask { if *val == 0 { continue; } bits.set(*pos as usize, true); } let new_key = bits.load::<usize>(); let mut values = HashSet::new(); for bit in 0..36usize { if !self.mask.contains_key(&(bit as u8)) { bits.set(bit, false); } } values.insert(bits.load::<usize>()); MaskAndValues::masking_recur( &self.mask.keys().map(|v| *v).collect(), &mut bits, 0, &mut values, ); values.iter().map(|v| *v).collect() } fn masking_recur( mask: &HashSet<u8>, bits: &mut BitVec, curr_bit: u8, values: &mut HashSet<usize>, ) { if curr_bit > 35 { return; } let mut curr_bit = curr_bit; while mask.contains(&(curr_bit as u8)) { curr_bit += 1; } if curr_bit > 35 { return; } bits.set(curr_bit as usize, true); values.insert(bits.load::<usize>()); MaskAndValues::masking_recur(mask, bits, curr_bit + 1, values); bits.set(curr_bit as usize, false); values.insert(bits.load::<usize>()); MaskAndValues::masking_recur(mask, bits, curr_bit + 1, values); } fn masked_value(&self, value: &usize) -> usize { let bits = value.view_bits::<Lsb0>(); let mut bits = BitVec::from_bitslice(bits); for (pos, val) in &self.mask { bits.set(*pos as usize, *val == 1); } bits.load::<usize>() } } #[aoc(day14, part1)] fn masked_bit_sums(input: &Vec<MaskAndValues>) -> usize { let mut vals: HashMap<usize, usize> = HashMap::new(); for v in input { v.add_values(&mut vals); } vals.values().sum() } #[aoc(day14, part2)] fn data_mask_sums(input: &Vec<MaskAndValues>) -> usize { let mut vals: HashMap<usize, usize> = HashMap::new(); for v in input { v.add_values_multiple_places(&mut vals); } vals.values().sum() } 

"""Day 14: Docking Data Interface with a docking computer doing bit masking to store values in memory. """ from itertools import product from typing import Generator, Union, List class MaskCommand: """A command that parses and sets the mask for subsequent memory setting commands to be filtered through. Properties: bits (list(int)): The original bit-string of 1's, 0's, and X's. and_ (int): A value to be `&`-ed with memory values to set some bits to 0 no matter what or_ (int): A value to be `|`-ed with memory values to set some bits to 1 no matter what floating (list(int)): Indices where X's live, to help with generating floating bits. """ def __init__(self, s: str): self.bits = s self.and_ = 0 self.or_ = 0 self.floating: list(int) = [] for i, c in enumerate(s): if c == '0': self.and_ |= (1 << (35 - i)) elif c == '1': self.or_ |= (1 << (35 - i)) elif c == 'X': self.floating.append(i) self.and_ = (~self.and_) & 0xFFFFFFFFF @staticmethod def generate_binary(digits: int) -> Generator[str, None, None]: """Generates strings of binary digits for all values between 0 and 2**(digits)-1 (i.e. all possible sequences of 1's and 0's.) """ for i in range(1 << digits): yield f"{i:0{digits}b}" def v2_addresses(self, command: Union['MaskCommand', 'SetCommand']) -> Generator[List[str], None, None]: """Generates addresses following V2 guidelines. Performs an OR between the command's address and the mask, and then generates every possible string made up of 1's and 0's in place of all the floating bits (X's). The OR assumes X's take precedence. e.g. 110X0X (after the OR) would yield 110000, 110001, 110100, and 110101. """ merged = [c_bit if m_bit == '0' else m_bit for (m_bit, c_bit) in zip(self.bits, command.bits)] for comb in MaskCommand.generate_binary(len(self.floating)): for index, bit in zip(self.floating, comb): merged[index] = bit yield merged class SetCommand: """A command to set memory to some value. Stores the address and value to be stored there. Used for both V1 and V2, so includes both and integer version of the address and the bits for compatability. Properties: value (int): The value to be stored. address (int): The location in memory to store the value. bits (str): A string representation of the 0's and 1's that make up the binary value for the address. (36 bits wide). """ def __init__(self, address: str, value: str): self.value = int(value) self.address = int(address) self.bits = f"{self.address:036b}" def parse(filename: str) -> List[Union[MaskCommand, SetCommand]]: """Parse the input file into a list of commands.""" commands = [] with open(filename, "r") as f: for line in f: if line.startswith("mask"): commands.append(MaskCommand(line[7:])) else: parts = line.split() commands.append(SetCommand(parts[0][4:-1], parts[-1])) return commands def part1(commands: List[Union[MaskCommand, SetCommand]]) -> int: """Find the sum of all values in memory after running all commands following the V1 spec. """ memory = dict() mask = None for command in commands: if isinstance(command, MaskCommand): mask = command else: new_value = (command.value & mask.and_) | mask.or_ memory[command.address] = new_value return sum(memory.values()) def part2(commands: List[Union[MaskCommand, SetCommand]]) -> int: """Find the sum of all values in memory after running all commands following the V2 spec. """ memory = dict() mask = None for command in commands: if isinstance(command, MaskCommand): mask = command else: for address in mask.v2_addresses(command): memory["".join(address)] = command.value return sum(memory.values()) if __name__ == "__main__": assert 165 == part1(parse("data/day14_test.txt")) assert 208 == part2(parse("data/day14_test2.txt")) print("All tests passed.") commands = parse("data/day14.txt") print(part1(commands)) print(part2(commands)) 

use std::collections::HashMap; use std::str::FromStr; #[derive(Debug)] enum Instr<'a> { Mask(&'a str), Mem(u64, u64), } impl<'a> From<&'a str> for Instr<'a> { fn from(s: &'a str) -> Self { if s.starts_with("mask") { Instr::Mask(&s[7..]) } else if s.starts_with("mem") { let addr_value = &mut s[4..].split("] = "); let addr: u64 = addr_value.next().unwrap().parse().unwrap(); let value: u64 = addr_value.next().unwrap().parse().unwrap(); Instr::Mem(addr, value) } else { panic!("Invalid line found: {}", s) } } } struct MaskParts { or_mask: u64, and_mask: u64, floating_bits: Vec<usize>, } impl FromStr for MaskParts { type Err = (); fn from_str(mask: &str) -> Result<Self, Self::Err> { let mut and_mask = 0; let mut or_mask = 0; let mut floating_bits: Vec<usize> = Vec::with_capacity(36); mask.chars().enumerate().for_each(|(i, c)| { and_mask <<= 1; or_mask <<= 1; if c == '1' { or_mask |= 1; } if c != '0' { and_mask |= 1; } if c == 'X' { floating_bits.push(35 - i) } }); Ok(MaskParts { or_mask, and_mask, floating_bits, }) } } pub fn part1(input: &str) -> u64 { let instr = input.lines().map(|x| x.into()); let mut mem: HashMap<u64, u64> = HashMap::new(); let mut mask_parts: MaskParts = "X".repeat(36).parse().unwrap(); for instruction in instr { match instruction { Instr::Mask(mask) => { mask_parts = mask.parse().unwrap(); } Instr::Mem(key, val) => { mem.insert(key, val & mask_parts.and_mask | mask_parts.or_mask); } } } mem.values().sum() } pub fn part2(input: &str) -> u64 { let instr = input.lines().map(|x| x.into()); let mut mem: HashMap<u64, u64> = HashMap::new(); let mut mask_parts: MaskParts = "X".repeat(36).parse().unwrap(); for instruction in instr { match instruction { Instr::Mask(mask) => { mask_parts = mask.parse().unwrap(); } Instr::Mem(addr, val) => { let base_addr = addr | mask_parts.or_mask; // Now we have to do n inserts where n = 2.pow(numX) for i in 0..2_u64.pow(mask_parts.floating_bits.len() as u32) { let mut final_addr = base_addr; for (from_bit, to_bit) in mask_parts.floating_bits.iter().enumerate() { if i & (1 << from_bit) != 0 { final_addr |= 1 << to_bit; } else { final_addr &= !(1 << to_bit); } } mem.insert(final_addr, val); } } } } mem.values().sum() }