Advent of Code 2020 day14
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