You land in an airport surrounded by dense forest. As you walk to your high-speed train, the Elves at the Mythical Information Bureau contact you again. They think their satellite has collected an image of a sea monster! Unfortunately, the connection to the satellite is having problems, and many of the messages sent back from the satellite have been corrupted.
They sent you a list of the rules valid messages should obey and a list of received messages they've collected so far (your puzzle input).
The rules for valid messages (the top part of your puzzle input) are numbered and build upon each other. For example:
0: 1 2
1: "a"
2: 1 3 | 3 1
3: "b"
Some rules, like 3: "b", simply match a single character (in this case, b).
The remaining rules list the sub-rules that must be followed; for example, the rule 0: 1 2 means that to match rule 0, the text being checked must match rule 1, and the text after the part that matched rule 1 must then match rule 2.
Some of the rules have multiple lists of sub-rules separated by a pipe (|). This means that at least one list of sub-rules must match. (The ones that match might be different each time the rule is encountered.) For example, the rule 2: 1 3 | 3 1 means that to match rule 2, the text being checked must match rule 1 followed by rule 3 or it must match rule 3 followed by rule 1.
Fortunately, there are no loops in the rules, so the list of possible matches will be finite. Since rule 1 matches a and rule 3 matches b, rule 2 matches either ab or ba. Therefore, rule 0 matches aab or aba.
Here's a more interesting example:
0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"
Here, because rule 4 matches a and rule 5 matches b, rule 2 matches two letters that are the same (aa or bb), and rule 3 matches two letters that are different (ab or ba).
Since rule 1 matches rules 2 and 3 once each in either order, it must match two pairs of letters, one pair with matching letters and one pair with different letters. This leaves eight possibilities: aaab, aaba, bbab, bbba, abaa, abbb, baaa, or babb.
Rule 0, therefore, matches a (rule 4), then any of the eight options from rule 1, then b (rule 5): aaaabb, aaabab, abbabb, abbbab, aabaab, aabbbb, abaaab, or ababbb.
The received messages (the bottom part of your puzzle input) need to be checked against the rules so you can determine which are valid and which are corrupted. Including the rules and the messages together, this might look like:
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
Your goal is to determine the number of messages that completely match rule 0. In the above example, ababbb and abbbab match, but bababa, aaabbb, and aaaabbb do not, producing the answer 2. The whole message must match all of rule 0; there can't be extra unmatched characters in the message. (For example, aaaabbb might appear to match rule 0 above, but it has an extra unmatched b on the end.)
How many messages completely match rule 0?
You need to maek some changes to the rules. Update rule 8 and rule 11 to the
following:
8: 42 | 42 8
11: 42 31 | 42 11 31
This small change has a big impact: now, the rules do contain loops, and the list of messages they could hypothetically match is infinite. You'll need to determine how these changes affect which messages are valid.
Fortunately, many of the rules are unaffected by this change; it might help to start by looking at which rules always match the same set of values and how those rules (especially rules 42 and 31) are used by the new versions of rules 8 and 11.
(Remember, you only need to handle the rules you have; building a solution that could handle any hypothetical combination of rules would be significantly more difficult.)
For example:
42: 9 14 | 10 1
9: 14 27 | 1 26
10: 23 14 | 28 1
1: "a"
11: 42 31
5: 1 14 | 15 1
19: 14 1 | 14 14
12: 24 14 | 19 1
16: 15 1 | 14 14
31: 14 17 | 1 13
6: 14 14 | 1 14
2: 1 24 | 14 4
0: 8 11
13: 14 3 | 1 12
15: 1 | 14
17: 14 2 | 1 7
23: 25 1 | 22 14
28: 16 1
4: 1 1
20: 14 14 | 1 15
3: 5 14 | 16 1
27: 1 6 | 14 18
14: "b"
21: 14 1 | 1 14
25: 1 1 | 1 14
22: 14 14
8: 42
26: 14 22 | 1 20
18: 15 15
7: 14 5 | 1 21
24: 14 1
abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa
bbabbbbaabaabba
babbbbaabbbbbabbbbbbaabaaabaaa
aaabbbbbbaaaabaababaabababbabaaabbababababaaa
bbbbbbbaaaabbbbaaabbabaaa
bbbababbbbaaaaaaaabbababaaababaabab
ababaaaaaabaaab
ababaaaaabbbaba
baabbaaaabbaaaababbaababb
abbbbabbbbaaaababbbbbbaaaababb
aaaaabbaabaaaaababaa
aaaabbaaaabbaaa
aaaabbaabbaaaaaaabbbabbbaaabbaabaaa
babaaabbbaaabaababbaabababaaab
aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba
Without updating rules 8 and 11, these rules only match three messages: bbabbbbaabaabba, ababaaaaaabaaab, and ababaaaaabbbaba.
However, after updating rules 8 and 11, a total of 12 messages match:
bbabbbbaabaabba
babbbbaabbbbbabbbbbbaabaaabaaa
aaabbbbbbaaaabaababaabababbabaaabbababababaaa
bbbbbbbaaaabbbbaaabbabaaa
bbbababbbbaaaaaaaabbababaaababaabab
ababaaaaaabaaab
ababaaaaabbbaba
baabbaaaabbaaaababbaababb
abbbbabbbbaaaababbbbbbaaaababb
aaaaabbaabaaaaababaa
aaaabbaabbaaaaaaabbbabbbaaabbaabaaa
aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba
After updating rules 8 and 11, how many messages completely match rule 0?
I leaned on my solution from day 4, and created generic rules like
AndRule and OrRule and ExactRule, and used those to build the tree of
rules.
Base interfaces:
export interface Rule {
isValid(msg: string, startAtIdx: number): RuleResponse;
}
export interface RuleResponse {
valid: boolean;
// When invalid, the field below is meaningless.
// Otherwise, it indicates to which index in the message it evaluated the
// rule. E.g., for AndRule, every rule in it uses the previous rule's
// nextStartIdx.
nextStartAtIdx: number;
}The core rules implementing the interface above:
export class AndRule implements Rule {
constructor(private readonly rules: Rule[]) {}
isValid(msg: string, startAtIdx: number) {
let nextStartAtIdx = startAtIdx;
for (const rule of this.rules) {
const response = rule.isValid(msg, nextStartAtIdx);
if (response.valid) {
nextStartAtIdx = response.nextStartAtIdx;
} else {
return {
valid: false,
nextStartAtIdx,
};
}
}
return {
valid: true,
nextStartAtIdx,
};
}
}
export class OrRule implements Rule {
constructor(private readonly rules: Rule[]) {}
isValid(msg: string, startAtIdx: number) {
const responses = this.rules.map((r) => r.isValid(msg, startAtIdx));
const validResponses = responses.filter((res) => res.valid);
if (validResponses.length > 0) {
const nextStartAtIdx = validResponses[0].nextStartAtIdx;
assert(
validResponses.every((res) => res.nextStartAtIdx === nextStartAtIdx),
`All valid rules in this OR rule don't have the same nextStartAtIdx: ${validResponses} for msg ${msg}.`
);
return {
valid: true,
nextStartAtIdx,
};
} else {
return {
valid: false,
nextStartAtIdx: startAtIdx,
};
}
}
}
export class ExactRule implements Rule {
constructor(private readonly msg: string) {}
isValid(msg: string, startAtIdx: number) {
const size = this.msg.length;
const nextStartAtIdx = startAtIdx + size;
const valid = msg.slice(startAtIdx, nextStartAtIdx) === this.msg;
return {
valid,
nextStartAtIdx,
};
}
}Finally, building the rules from the input:
export function buildRule(rules: string[]): Rule {
const helper = (rule: string): Rule => {
if (/^"[a-zA-Z]+"$/.test(rule)) {
return new ExactRule(assert(rule.match(/^"(\w+)"$/)?.[1]));
} else if (rule.includes('|')) {
return new OrRule(rule.split(' | ').map(helper));
} else if (!isNaN(Number(rule))) {
return helper(rules[Number(rule)]);
} else if (/^\d+( \d+)+$/.test(rule)) {
return new AndRule(rule.split(' ').map(helper));
} else {
throw new Error(`Unknown rule ${rule}.`);
}
};
return helper(rules[0]);
}
function validate({ rules, messages }: Simulation) {
const rule = buildRule(rules);
let validCount = 0;
for (const msg of messages) {
const response = rule.isValid(msg, 0);
const valid = response.valid && response.nextStartAtIdx === msg.length;
if (valid) {
validCount++;
}
}
return validCount;
}For Part Two, we create another implementation of Rule. What helped is how
rule 8 and rule 11 are being used. They're being used in rule 0 as 8 11,
which allows us to do something like this:
const RULE_8 = '42 | 42 8';
const RULE_11 = '42 31 | 42 11 31';
const RULE_0 = '8 11';
/* Implementing rule 8 and 11 independently is difficult, because any of these
* scenarios are valid:
* 42 42 31
* 42 42 42 31
* 42 42 42 31 31
* 42 42 42 42 31
* ...etc.
*
* Notice that 31 must be valid at least once, and at most 42ValidCount-1.
*
* If we try to build those two rules independently, rule 8 would just keep
* running rule 42 until it no longer could, but rule 11 wouldn't know how many
* 31s to expect.
*
* If we do them together though, we would just need to confirm 42 and 31 appear
* at least once, and 31 is at most one fewer than the number of times 42
* appears.
*/
class Rule0 implements Rule {
constructor(private readonly rule42: Rule, private readonly rule31: Rule) {}
isValid(msg: string, startAtIdx: number) {
let rule42ValidCount = 0;
let rule31ValidCount = 0;
let nextStartAtIdx = startAtIdx;
let res = this.rule42.isValid(msg, nextStartAtIdx);
// get a count of how many times rule42 is valid.
while (res.valid) {
rule42ValidCount++;
nextStartAtIdx = res.nextStartAtIdx;
res = this.rule42.isValid(msg, nextStartAtIdx);
}
// now confirm that rule31 is valid for at most this many times.
// rule42 count must be at least 1 greater.
for (; rule31ValidCount < rule42ValidCount - 1; rule31ValidCount++) {
res = this.rule31.isValid(msg, nextStartAtIdx);
// if rule 31 is invalid for counts less than rule42ValidCount, we can
// stop counting.
if (!res.valid) {
break;
}
nextStartAtIdx = res.nextStartAtIdx;
}
// both can't be zero, and rule42 must be at least 1 greater.
if (rule42ValidCount === 0 || rule31ValidCount === 0) {
return {
valid: false,
nextStartAtIdx: -1,
};
}
return {
valid: true,
nextStartAtIdx,
};
}
}Instead of building a tree of Rule interfaces, you can just build a regex
string! Check this out:
- A rule of
4: "a"and5: "b"becomes just/a/and/b/regex strings. - A rule of
6: 4 5becomes/ab/,7: 4 4 5 5becomes/aabb/. - A rule of
8: 7 6 | 6becomes/(aabbab|ab)/. - A rule of
9: 5 8 6becomes/b(aabbab|ab)ab/.
And so on.
Once you have your regex string regex, you can just do new RegExp('^'+regex+'$')and then do regExp.test(msg). This also allows you to
visualize the pattern.
For Part Two, rule 8 is just ${helper('42')+, and rule 11 uses
something called regex
subroutines:
const RULE_8 = '42 | 42 8';
const RULE_11 = '42 31 | 42 11 31';
function addRegex(sim: Simulation): RegexRule {
const { rules } = sim;
const cache: { [rule: string]: string } = {};
const helper = (rule: string): string => {
if (cache[rule]) {
return cache[rule];
} else if (rule === RULE_8) {
return helper('42') + '+';
} else if (rule === RULE_11) {
// this is using regex subroutines, which isn't supported in Javascript
// natively. You'll have to use PCRE flavor regex, whcih can be done via
// @stephen-riley/pcre2-wasm.
return `(?'rule11'${helper('42')}(?&rule11)?${helper('31')})`;
} else if (/^"[a-zA-Z]+"$/.test(rule)) {
return (cache[rule] = assert(rule.match(/^"(\w+)"$/)?.[1]));
} else if (!isNaN(Number(rule))) {
return (cache[rule] = helper(rules[Number(rule)]));
} else if (rule.includes('|')) {
return (cache[rule] =
'(' + rule.split(' | ').map(helper).join('|') + ')');
} else if (/^\d+( \d+)+$/.test(rule)) {
return (cache[rule] = rule.split(' ').map(helper).join(''));
} else {
throw new Error(`Unknown rule ${rule}.`);
}
};
return { ...sim, regex: helper(rules[0]) };
}Here's a good video describing the algorithm.
The grammar, or the language, is the set of rules in your input. And each sample
message is an input where you test for membership in the language. Note that S
usually indicates the starting rule.
There's a great library that does all of this for you: instaparse, which is based on some GLL Algorithm.