🎄

Advent of Code 2020 day07

2020/12/14に公開

Rust

adventofcode

tech

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

part1

light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.

のような入力が与えられる。自然言語かよ……。
part1は、shiny gold bagがあったときにそれを入れるbagとして有り得るのは何通りか、というもの。

とりあえず入力のparseは正規表現使っても良いけど " bags contain " でsplitして後者の方をさらに ", " でsplitしていけば、bagとcontentsの関係は取得できる。
shiny gold bagを入れ得るものを探すので、contentsから逆に「自分を含み得る親のbag」を辿っていくためのHashMapを構築していく。contentsが"no other bags."のときは無視して良い。
それが構築できれば、目的のshiny gold bagをrootとして親として有り得るbagたちをどんどん辿っていけば良い。例のようにbright white bagやmuted yellow bagはlight red bagとdark orange bagの双方が含み得るといったことがあるので、重複は避けるため親のbagはHashSetに入れながらカウントすると良い。

use std::collections::{HashMap, HashSet};

struct Solution {
    inputs: Vec<String>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> usize {
        let mut hm: HashMap<&str, Vec<&str>> = HashMap::new();
        for line in self.inputs.iter() {
            let v: Vec<&str> = line.split(" bags contain ").collect();
            if v[1] != "no other bags." {
                for s in v[1].split(", ") {
                    let l = s.find(' ').unwrap();
                    let r = s.rfind(' ').unwrap();
                    hm.entry(&s[l + 1..r]).or_insert_with(Vec::new).push(v[0]);
                }
            }
        }
        let mut hs: HashSet<&str> = HashSet::new();
        let mut stack: Vec<&str> = vec!["shiny gold"];
        while let Some(last) = stack.pop() {
            if !hs.contains(last) {
                hs.insert(last);
                if let Some(set) = hm.get(last) {
                    for &s in set {
                        stack.push(s);
                    }
                }
            }
        }
        hs.len() - 1
    }
}

part2

part1では入力に含まれる数値は完全に無視していたが、今度はちゃんと使われる。書かれている数の通りにbagを詰めていくとすると、1つのshiny gold bagの中には幾つのbagが含まれることになるか、という問題。

今度はbagが持つべきcontentsの(個数, 色)、の関係を表すHashMap<&str, Vec<(usize, &str)>>を用意。"no other bags."のときは空のcontentsを持つ、とする。
あとは (1, "shiny gold") をrootとして、個数を掛けながら子を辿っていって全部足し合わせていけば良い。

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_2(&self) -> usize {
        let mut hm: HashMap<&str, Vec<(usize, &str)>> = HashMap::new();
        for line in self.inputs.iter() {
            let v: Vec<&str> = line.split(" bags contain ").collect();
            hm.insert(
                v[0],
                if v[1] == "no other bags." {
                    Vec::new()
                } else {
                    v[1].split(", ")
                        .map(|s| {
                            let l = s.find(' ').unwrap();
                            let r = s.rfind(' ').unwrap();
                            let n: usize = s[..l].parse().unwrap();
                            (n, &s[l + 1..r])
                        })
                        .collect()
                },
            );
        }
        let mut ret = 0;
        let mut stack: Vec<(usize, &str)> = vec![(1, "shiny gold")];
        while let Some(last) = stack.pop() {
            ret += last.0;
            if let Some(v) = hm.get(last.1) {
                for &e in v.iter() {
                    stack.push((last.0 * e.0, e.1));
                }
            }
        }
        ret - 1
    }
}

part1

part2

Discussion