🎄

Advent of Code 2020 day14

7 min read

https://adventofcode.com/2020/day/14

part1

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0

のような入力が与えられる。memory address, value ともに 36-bit unsigned integer として動作している。
36-bit それぞれに適用される mask が指定され、それ以降のmemoryへ書き込まれる値がそのmaskによって書き換えられる。
maskは

  • 0 はその位置のbitを常に0に上書きする
  • 1 はその位置のbitを常に1に上書きする
  • X は何も変更しない

というルールで各値を書き換えるらしい。(memoryはすべて0で初期化されている状態から開始し)一連の操作を行った後に書き込まれている値の合計値は幾つか、という問題。
上の例だと maskされた結果 mem[7]には101 が、mem[8]には64が書き込まれることになり、合計値165が答えになる。

書かれている通りに値を書き換えていくだけだが、毎回36bitすべて見ながら書き換えるのも面倒なので、1回の操作で書き換えられるよう 「0で上書きするためのmask」と「1で上書きするためのmask」を別々に用意する。前者は0b111....111、後者は0b000...000で初期値を用意し、maskを指定された際に ある位置の値が0なら前者を、1なら後者を変更してやる。Xは無視。
実際に書き込む値に適用する際には value & mask.0 | mask.1 を計算することで仕様通りの書き換えが出来る。

memoryはaddressが大きな値になる可能性もあるのでVecではなくHashMapで持っておく。keyもvalueも36-bit unsigned integerがおさまるようにu64を使っておく。

use std::collections::HashMap;

struct Solution {
    inputs: Vec<String>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> u64 {
        let re = Regex::new(r"^mem\[(\d+)\] = (\d+)$").unwrap();
        let mut masks: (u64, u64) = ((1 << 36) - 1, 0);
        let mut mem: HashMap<u64, u64> = HashMap::new();
        for input in self.inputs.iter() {
            if let Some(mask) = input.strip_prefix("mask = ") {
                masks = ((1 << 36) - 1, 0);
                for (i, c) in mask.chars().rev().enumerate() {
                    match c {
                        '0' => masks.0 &= !(1 << i),
                        '1' => masks.1 |= 1 << i,
                        _ => {}
                    }
                }
            } else if let Some(cap) = re.captures(input) {
                if let (Ok(address), Ok(value)) = (cap[1].parse::<u64>(), cap[2].parse::<u64>()) {
                    mem.insert(address, value & masks.0 | masks.1);
                }
            }
        }
        mem.values().sum()
    }
}

part2

別versionのprogramとして動かす必要があったらしい。今度はvalueではなくaddressの方を書き換える動作をするようだ。maskの動作も変わる。

  • 0 は何も変更しない
  • 1 はその位置のbitを常に1に上書きする
  • X はその位置のbitをfloating bitとして扱う

floating bitは有り得るすべての値の組み合わせを生じ、それらのaddressすべてに値を書き込むことになる。

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

という例では、mem[42]42がmaskによって26, 27, 58, 59になり、その4つの addressすべてに100が書き込まれる。
mem[26]26がmaskによって 16, 17, 18, 19, 24, 25, 26, 27になり、その8つのaddressすべてに1が書き込まれる。
結果としてすべての値の合計は208となる。

今度はmaskの0を無視して、1のときはpart1と同様の操作に。問題はXのときだが、後で展開するためにとりあえず出現する位置だけを記録しておく。

    let mut masks = (Vec::new(), 0);
    for input in self.inputs.iter() {
        if let Some(m) = input.strip_prefix("mask = ") {
            masks.0.clear();
            masks.1 = 0;
            for (i, c) in m.chars().rev().enumerate() {
                match c {
                    '1' => masks.1 |= 1 << i,
                    'X' => masks.0.push(i),
                    _ => {}
                }
            }
        }
        ...
    }

で、1で上書きした値から開始し、Xが出現する位置が「0の場合の値」と「1の場合の値」をそれぞれ計算し追加していくことで すべての組み合わせを生成していく。VecDequeを使うとやりやすい。

    if let (Ok(address), Ok(value)) = (cap[1].parse::<u64>(), cap[2].parse::<u64>()) {
        let mut addresses: VecDeque<u64> = VecDeque::new();
        addresses.push_back(address | masks.1);
        for &i in masks.0.iter() {
            for _ in 0..addresses.len() {
                if let Some(front) = addresses.pop_front() {
                    addresses.push_back(front | 1 << i);
                    addresses.push_back(front & !(1 << i));
                }
            }
        }
	...
    }

あとはこうして生成されたすべてのaddressに対してvalueを入れていって合計値を計算するだけ。

code

use regex::Regex;
use std::collections::{HashMap, VecDeque};
use std::io::{BufRead, BufReader};

struct Solution {
    inputs: Vec<String>,
    re: Regex,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self {
            inputs,
            re: Regex::new(r"^mem\[(\d+)\] = (\d+)$").unwrap(),
        }
    }
    fn solve_1(&self) -> u64 {
        let mut mask: (u64, u64) = ((1 << 36) - 1, 0);
        let mut mem: HashMap<u64, u64> = HashMap::new();
        for input in self.inputs.iter() {
            if let Some(m) = input.strip_prefix("mask = ") {
                mask = ((1 << 36) - 1, 0);
                for (i, c) in m.chars().rev().enumerate() {
                    match c {
                        '0' => mask.0 &= !(1 << i),
                        '1' => mask.1 |= 1 << i,
                        _ => {}
                    }
                }
            } else if let Some(cap) = self.re.captures(input) {
                if let (Ok(address), Ok(value)) = (cap[1].parse::<u64>(), cap[2].parse::<u64>()) {
                    mem.insert(address, value & mask.0 | mask.1);
                }
            }
        }
        mem.values().sum()
    }
    fn solve_2(&self) -> u64 {
        let mut mem: HashMap<u64, u64> = HashMap::new();
        let mut masks = (Vec::new(), 0);
        for input in self.inputs.iter() {
            if let Some(m) = input.strip_prefix("mask = ") {
                masks.0.clear();
                masks.1 = 0;
                for (i, c) in m.chars().rev().enumerate() {
                    match c {
                        '1' => masks.1 |= 1 << i,
                        'X' => masks.0.push(i),
                        _ => {}
                    }
                }
            } else if let Some(cap) = self.re.captures(input) {
                if let (Ok(address), Ok(value)) = (cap[1].parse::<u64>(), cap[2].parse::<u64>()) {
                    let mut addresses: VecDeque<u64> = VecDeque::new();
                    addresses.push_back(address | masks.1);
                    for &i in masks.0.iter() {
                        for _ in 0..addresses.len() {
                            if let Some(front) = addresses.pop_front() {
                                addresses.push_back(front | 1 << i);
                                addresses.push_back(front & !(1 << i));
                            }
                        }
                    }
                    for &address in addresses.iter() {
                        mem.insert(address, value);
                    }
                }
            }
        }
        mem.values().sum()
    }
}

fn main() {
    let solution = Solution::new(
        BufReader::new(std::io::stdin().lock())
            .lines()
            .filter_map(|line| line.ok())
            .collect(),
    );
    println!("{}", solution.solve_1());
    println!("{}", solution.solve_2());
}

Discussion

ログインするとコメントできます