DEV Community

loading...
Cover image for Advent of Code 2020 Solution Megathread - Day 14: Docking Data

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

rpalo profile image Ryan Palo ・1 min read

OK, yesterday's part 2 was one of the first times I would personally say I hit a wall where I had to get algorithmically sneaky to get something fast enough. I don't know if that's because I'm using C, so even if my code is garbage, it's fast enough for most things, or because we're in the second half of AoC and $@!# just got real. We'll have to see.

The Puzzle

In today’s puzzle, we are un-done with boats. I thought we were off the boat yesterday, but we're back on the boat today and fiddling with bits to fix the ships docking computer. Also, the memory locations are 36 bits wide because, "Ho ho ho."

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19
Enter fullscreen mode Exit fullscreen mode

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 10:06AM 12/14/2020 PST.

Language Count
Rust 3
Ruby 1
C 1
JavaScript 1
Haskell 1
COBOL 1
Python 1

Merry Coding!

Discussion (8)

pic
Editor guide
Collapse
kudostoy0u profile image
Kudos Beluga

Part 1 JS solution, Part 2 coming soon. I am angry with myself because I got stuck for 30 minutes on why my code wasn't giving the correct solution when I forgot to reset the bitmask when a new one is declared -_-

function bin(dec) {
    return (dec >>> 0).toString(2);
}

function pad(n, width, z) {
    z = z || '0';
    n = n + '';
    return n.length >= width ? n : new Array(width - n.length + 1).join(z) + n;
}
const fs = require("fs")
let data = fs.readFileSync("sinput.txt", "utf8").split("\n");
let memslots = {};
let mymask = {};
data.forEach(e => {
    if (e.split(" = ")[0] == "mask") {
        let amask = e.split(" = ")[1]
        mymask = {}
        for (let i = 0; i < amask.length; i++) {
            if (amask[i] != "X") {
                mymask[i] = amask[i];
            }
        }
    } else {
        let memtype = e.split("mem[")[1].split("]")[0];
        let integr = pad(bin(e.split(" = ")[1]), 36).split("")
        for (const [idx, val] of Object.entries(mymask)) {
            integr[Number(idx)] = val;
        }
        memslots[memtype] = integr.join("")
    }
})
let total = 0;
for (let num of Object.values(memslots)) {
    total += parseInt(num, 2)
}
console.log(total)
Enter fullscreen mode Exit fullscreen mode
Collapse
galoisgirl profile image
Anna

Only part 1 for now, it's 5 to midnight and recursion in COBOL is a bit too hard.


       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.
Enter fullscreen mode Exit fullscreen mode
Collapse
neilgall profile image
Neil Gall

Bit twiddling. Rust proves just as adept as C.

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);
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
cappe987 profile image
Casper

My Haskell solution
Github repo available here github.com/cappe987/aoc-2020

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
Enter fullscreen mode Exit fullscreen mode
Collapse
benwtrent profile image
Benjamin Trent

Instead of figuring out how to do this purely with bitmasking + bit math, I brute forced utilizing bitvec. Not pretty :)

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()
}

Enter fullscreen mode Exit fullscreen mode
Collapse
bgaster profile image
Benedict Gaster

My Haskell soloution, have to save I've never used bitwise operations in Haskell very much, so had to look all that up. And during that search I realised that foldl', which I defined on day 8, is actually implemented in Data.List, oops.. :-)

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)
Enter fullscreen mode Exit fullscreen mode
Collapse
rpalo profile image
Ryan Palo Author

Rough one today. Don't know if I was tired or what, but I had to resort to Python to get it done in time.

"""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))
Enter fullscreen mode Exit fullscreen mode
Collapse
thibpat profile image
Thibaut Patel

My JavaScript walkthrough: