Advent of Code 2020 day19
part1
0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"
ababbb
bababa
abbbab
aaabbb
aaaabbb
のような入力が与えられる。前半はメッセージが従うべきルール、後半は1行ごと送られてくるメッセージを表している。
rule 0に完全にmatchするメッセージは幾つあるか？という問題。上の例だとababbbとabbbabの2件だけがrule 0に完全にmatchする。
正規表現を組み立てるという方法もありそうだが、言語によって差異もありそうなので ここでは正規表現を一切使わない解答を考える。
part1は、完全にmatchする入力をすべて展開する力技でも一応解ける。文字の組み合わせで解釈できるものをHashMap<u8, HashSet<String>>に入れていって、各ruleがすべて展開できるものから次々に候補を展開して格納していく。最終的にすべてのruleが展開できたら0に該当するHashSet<String>が得られるので、各メッセージはそこに含まれるか否かだけで判定できる。自分の入力だとrule 0の候補は2,097,152個になったのでかなり厳しいが、、とりあえず答えは出せる。
impl Solution {
fn new(inputs: Vec<String>) -> Self {
Self { inputs }
}
fn solve_1(&self) -> usize {
let mut dict: HashMap<u8, HashSet<String>> = HashMap::new();
let mut rules: HashMap<u8, Vec<Vec<u8>>> = HashMap::new();
let mut messages: Vec<&String> = Vec::new();
for input in self.inputs.iter() {
if input.is_empty() {
continue;
}
if input.starts_with(|c: char| c.is_numeric()) {
let s: Vec<&str> = input.split(": ").collect();
if let Ok(key) = s[0].parse() {
if s[1].starts_with('"') {
let mut hs = HashSet::new();
hs.insert(s[1][1..2].to_string());
dict.insert(key, hs);
} else {
rules.insert(
key,
s[1].split(" | ")
.map(|s| s.split(' ').filter_map(|s| s.parse().ok()).collect())
.collect(),
);
}
}
} else {
messages.push(input);
}
}
while !rules.is_empty() {
let mut delete: Vec<u8> = Vec::new();
for (&k, v) in rules.iter() {
if v.iter().all(|v| v.iter().all(|i| dict.contains_key(i))) {
let mut entries = HashSet::new();
for v in v.iter() {
let mut vd: VecDeque<String> = VecDeque::new();
vd.push_back(String::new());
for &i in v.iter() {
if let Some(values) = dict.get(&i) {
for _ in 0..vd.len() {
if let Some(front) = vd.pop_front() {
for s in values.iter() {
vd.push_back(front.clone() + s);
}
}
}
}
}
entries.extend(vd.into_iter());
}
dict.insert(k, entries);
delete.push(k);
}
}
for i in delete.iter() {
rules.remove(i);
}
}
if let Some(valid) = dict.get(&0) {
messages.iter().filter(|&m| valid.contains(*m)).count()
} else {
0
}
}
}
part2
入力のruleに変更が生じ、再帰的なruleが登場。
8: 42 | 42 8
11: 42 31 | 42 11 31
再帰があるので上述のような全展開の力技は無限に候補が生成されてしまい通用しない。
冷静に読み解くと、42 42 31 という組み合わせだったものが左方向に42が複数と右方向に31が複数 増えるだけ、なので、rule 0を「rule 42にmatchする文字列m個と rule 31にmatchする文字列n個が連結されたものであり、m > nである」と解釈してやればその条件にmatchするかどうかを調べていくことで対応は出来る。
そうではなく、順次ruleにmatchさせていく方法でやってみる。
まずはruleをちゃんと定義
#[derive(Clone)]
enum Rule {
Ref(u8),
Char(char),
Sequence(Vec<Rule>),
Or(Box<Rule>, Box<Rule>),
}
別の単一のruleを参照するRef、文字を表すChar、連続したRuleの組み合わせであるSequence、複数(この問題では高々2個)のRuleのどちらか、を表すOrの4種類。Ruleの中でRuleを参照することになるのでBoxを使う。
入力のparse時にはこの定義に合うように入れていってHashMap<u8, Rule>を作る。
let mut rules: HashMap<u8, Rule> = HashMap::new();
let mut messages: Vec<String> = Vec::new();
for input in inputs.iter().filter(|&s| !s.is_empty()) {
if input.starts_with(|c: char| c.is_numeric()) {
let s: Vec<&str> = input.split(": ").collect();
if let Ok(key) = s[0].parse() {
rules.insert(
key,
if s[1].starts_with('"') {
Rule::Char(s[1].chars().nth(1).unwrap())
} else if s[1].contains(" | ") {
let v: Vec<&str> = s[1].split(" | ").collect();
Rule::Or(
Box::new(Rule::Sequence(
v[0].split(' ')
.filter_map(|s| s.parse().ok())
.map(|n| Rule::Ref(n))
.collect(),
)),
Box::new(Rule::Sequence(
v[1].split(' ')
.filter_map(|s| s.parse().ok())
.map(|n| Rule::Ref(n))
.collect(),
)),
)
} else {
Rule::Sequence(
s[1].split(' ')
.filter_map(|s| s.parse().ok())
.map(|n| Rule::Ref(n))
.collect(),
)
},
);
}
} else {
messages.push(input.to_string());
}
}
そしてRuleをmessage: &strにmatchさせるメソッドを用意する。ここで、このメソッドが返すのは「messageに対してこのRuleを適用させて 読み込み残った文字列として有り得るもの」の列。
"a"に該当するChar Ruleに"ab"というメッセージをmatchさせるとvec!["b"]が返る。"bb"のようにmatchしないメッセージだとvec![]と空の列を返す。
Sequence Ruleの場合は順番に matchさせた結果を繰り返し適用していく。Or は両方の場合が有り得るのでそれぞれの結果を合わせたものになる。
impl Rule {
fn matches<'a>(&self, message: &'a str, rules: &HashMap<u8, Rule>) -> Vec<&'a str> {
match self {
Rule::Ref(u) => {
if let Some(rule) = rules.get(u) {
rule.matches(message, rules)
} else {
Vec::new()
}
}
Rule::Char(c) => {
if Some(*c) == message.chars().next() {
vec![&message[1..]]
} else {
Vec::new()
}
}
Rule::Sequence(v) => {
let mut ret = vec![message];
for rule in v.iter() {
let mut messages = Vec::new();
for &m in ret.iter() {
messages.append(&mut rule.matches(m, rules));
}
ret = messages;
}
ret
}
Rule::Or(r1, r2) => {
let mut ret = Vec::new();
ret.append(&mut r1.as_ref().matches(message, rules));
ret.append(&mut r2.as_ref().matches(message, rules));
ret
}
}
}
}
こうして再帰的にmatchさせていくと、完全にmatchする場合は ""を含むものが返ってくる。まったくmatchしない場合は空のVecになり、前方はmatchするが後方に余計なものが含まれている場合は残った部分文字列が含まれることになる。
part2の場合は再帰のmatchのさせ方によってvec!["", "aaababaa", "aaaaaabaaaababaa"]のように複数の結果を得ることがある。なんにせよ""が含まれるのであれば完全にmatchさせるパターンが存在しているということなので、これはvalidとみなせる。
fn solve_1(&self) -> usize {
self.count_matches(&self.rules)
}
fn solve_2(&self) -> usize {
let mut rules = self.rules.clone();
rules.insert(
8,
Rule::Or(
Box::new(Rule::Ref(42)),
Box::new(Rule::Sequence(
[42, 8].iter().map(|&u| Rule::Ref(u)).collect(),
)),
),
);
rules.insert(
11,
Rule::Or(
Box::new(Rule::Sequence(
[42, 31].iter().map(|&u| Rule::Ref(u)).collect(),
)),
Box::new(Rule::Sequence(
[42, 11, 31].iter().map(|&u| Rule::Ref(u)).collect(),
)),
),
);
self.count_matches(&rules)
}
fn count_matches(&self, rules: &HashMap<u8, Rule>) -> usize {
if let Some(rule) = rules.get(&0) {
self.messages
.iter()
.filter(|&message| rule.matches(message, &rules).into_iter().any(str::is_empty))
.count()
} else {
0
}
}
Discussion