Der Advent of Code steht vor der Tür. Das ist ein Adventskalender aus Programmieraufgaben, deren Lösung aus Spaß an der Freude als Zeitvertreib herhalten kann. Nach erfolgreichem Bearbeiten einer Aufgabe erhält man einen goldenen Stern. Das erste Mal bin ich 2020 darüber gestolpert. Ich dachte seinerzeit, ich versuche das direkt in der Programmiersprache Rust, die ich bis dahin noch nicht verwendet hatte. Übrigens soll dieser Artikel nicht nur eine interessante Advent-of-Code-Aufgabe beleuchten, sondern auch die Flexibilität meiner Rust-Bibliothek Exmex hervorheben, die weiter unten als Teil der Lösung diskutiert wird.
Aufgabenstellung
Wir betrachten die Aufgabe des 19. Tages von Advent of Code 2020. Die Eingabedaten des Programms sind ein Regelwerk und mehrere Testzeichenketten, die nur aus as und bs bestehen. Das Programm soll bestimmen, welche der Testzeichenketten das Regelwerk erfüllen. Ein Regelwerk ist von folgender Bauart.
0: 1 2
1: "a"
2: 1 3 | 3 1
3: "b"
Jede Zeile repräsentiert eine Regel. Links des Doppelpunkts befindet sich der Index der Regel, über den sie repräsentiert wird. Rechts des Doppelpunkts steht die eigentliche Regel. Zahlen bezeichnen Indizes anderer Regeln. Die Regel 3: "b" bedeutet beispielsweise, dass ein "b" erwartet wird. Die Regel 0: 1 2 bedeutet dagegen, dass die Regeln 1 und 2 erfüllt sein müssen. Die senkrechten Linien sind nicht-exklusive Veroderungen. Also 2: 1 3 | 3 1 ist erfüllt, wenn 1 3 und/oder 3 1 erfüllt sind. Die Frage ist jetzt, welche Zeichenketten Regel 0 exakt erfüllen. Für das kleine Regelwerk von oben kann man sich das aufschreiben.
1 2
| \
"a" (1 3) | (3 1)
| | | or | |
"a" ("a" "b") or ("b" "a")
In diesem Fall sind das also die Zeichenketten aab und aba. Eine ausführlichere Erklärung findet sich auf der Advent-of-Code-Seite*, der ich das Beispiel entnommen habe. Das Regelwerk und die Testzeichenketten um den virtuellen Erfolgsstern zu erhalten, sind deutlich komplexer.
Operatorensicht
Die Aufgabe hat mich mit ihren Veroderungen an eine Aufgabe aus meinem 2ten Semester an der Uni erinnert. Damals haben wir einen Interpreter für Bewegungen des Roboters Karel geschrieben. In meiner Erinnerung besteht dieser Interpreter aus ganz vielen verschiedenen Expressions, Nodes, Expression-Nodes und Vererbungsbäumen und ist furchtbar*Der Leser sei ermutigt, negative Konotationen gegenüber Vererbung zu bemerken. Sie ist die einzige Daseinsberechtigung der ansonsten überflüssigen Einleitung dieses Abschnitts. Ob eine Erbschaftssteuer hilfreich wäre? objektorientiert oder eher klassenorientiert. Ich brauche jedenfalls einen Parser, der aus der Zeichenkette einen Ausdruck erstellt, den man evaluieren kann. Dementsprechend habe ich den Crate*So heißen Rust-Bibliotheken, die man mit dem Standardpaketverwalter installieren kann. Exmex erstellt, der Funktionalität zum Parsen mathematischer Ausdrücke bestehend aus Zahlen und Operatoren bereit stellt. Ja, ich programmiere mehrere Monate an einem Crate, nur um eine Aufgabe von Advent of Code lösen zu können😜.
Credits an David W. für das Ausgraben dieses Comics, https://imgs.xkcd.com/comics/automation.png
Jedenfalls kann man mit Exmex die Funktion $(x, y) \mapsto 2x^3-4/y$ durch das Rust-Snippet
use exmex::prelude::*;
let expr = exmex::parse::<f64>("2*x^3-4/y")?;
expr.eval(&[0.5, 2.5])
an der Stelle x=0.5 und y=2.5 auswerten.
Exmex ist so flexibel gestaltet, dass man selbst definieren kann was eine Zahl und was ein Operator ist. Eine Zahl muss keine Zahl sein. Daher nennen wir sie jetzt etwas allgemeiner Operand. Um die Advent-of-Code-Aufgabe des 19ten Tages zu lösen, definieren wir als Operanden Regel-Operatoren und als Operatoren Operatoren die auf Regel-Operatoren arbeiten. Für den Regel-Operator, den wir ab jetzt nur noch Regel nennen, brauchen wir einen Typen, der die Trait-Bounds von Exmex-Operanden Clone, FromStr und Debug implementiert. Des Weiteren
- repräsentieren Regeln entweder den Index einer anderen Regel,
- einen der Buchstaben
aoderb, - die Komposition mehrerer Regeln wie in
0: 4 1 5 - oder die Veroderung mehrerer Regeln gekennzeichnet durch
|wie in2: 1 3 | 3 1.
Den 4 Fällen entsprechend definieren wir unseren Typen als enum.
#[derive(Clone, Debug)]
enum RuleOp {
Idx(usize),
Char(char),
Concatenate(Vec<Op>),
Union(Vec<Op>),
}
Damit eine Regel bestimmen kann, ob sie von gewissen Zeichenketten erfüllt wird, implementieren wir die Methode eval. Die Methode überprüft für eine Liste von Eingangszeichenketten welcher Teil beginnend am Anfang mit der Regel übereinstimmt. Für jeden Treffer wird eine Zeichenkette zurückgegeben, die aus dem restlichen Teil besteht.
impl RuleOp {
pub fn eval<'a>(
&self,
msgs: &Vec<&'a str>,
rules: &Vec<RuleOp>
) -> Vec<&'a str> {
if msgs.len() == 0 {
return msgs.clone();
}
match self {
RuleOp::Idx(idx) => rules[*idx].eval(msgs, rules),
RuleOp::Char(c) => msgs
.iter()
.filter(|msg| msg.chars().nth(0) == Some(*c))
.map(|msg| &msg[1..]) // a match at the
// beginning is cut
.collect::<Vec<_>>(),
RuleOp::Concatenate(ops) => {
let mut res = msgs.clone();
for op in ops {
res = op.eval(&res, rules);
}
res
}
RuleOp::Union(ops) => ops
.iter()
.flat_map(|op| op.eval(msgs, rules))
.collect::<Vec<_>>(),
}
}
}
Um Literale wie a oder 4 aus der Zeichenkette in Instanzen des Structs RuleOps umwandeln zu können, implementieren wir FromStr.
impl FromStr for RuleOp {
type Err = ParseIntError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
Ok(match s.chars().nth(1) {
Some(letter)
if letter == 'a'
|| letter == 'b' => RuleOp::Char(letter),
_ => RuleOp::Idx(s.parse::<usize>()?),
})
}
}
Als nächstes betrachten wir die Operatoren, die Regeln auf neue Regeln abbilden. Exmex stellt erfreulicherweise ein Macro zur Verfügung um eine Operatorfabrik zu erstellen. Wir repräsentieren wie oben durch "|" den Veroderungsoperator. Der Kompositionsoperator wird durch "o" repräsentiert. Dazu wandeln wir die Eingangszeichenketten vor dem Parsen entsprechend um. Z.B. wird dann aus 1 3 | 3 1 die Zeichenkette 1o3|3o1. Aus zwei Eingangsoperatoren erstellt der Veroderungsoperator einen neuen Operator in der Variante Union und der Kompositionsoperator eine neuen Operator in der Variante Concatenate.
ops_factory!(
OpsOpsFactory,
RuleOp,
Operator::make_bin(
"|",
BinOp {
apply: |op1, op2| {
RuleOp::Union(vec![op1, op2])
},
prio: 0, // note that or has a lower
// priority than composition
is_commutative: true
}
),
Operator::make_bin(
"o",
BinOp {
apply: |op1, op2| {
RuleOp::Concatenate(vec![op1, op2])
},
prio: 1,
is_commutative: false
}
)
);
Regeln überprüfen
Um zu überprüfen ob eine Zeichenkette ein Regelwerk erfüllt wird, verwenden wir als ersten Schritt Exmex zum Parsen. Wir können Exmex einen regulären Ausdruck übergeben, der den Literalen am Anfag der Zeichenkette entspricht. In unserem Fall verwenden wir den regulären Ausdruck ^([0-9]+|\"a\"|\"b\"), der den Zahlen 0-9 und den Buchstaben "a" und "b" entspricht*Der reguläre Ausdruck muss in einem Typ hinterlegt werden, der im folgenden Code `OpsMatcher` heißt. Dabei hilft uns das Macro `literal_matcher_from_pattern`. So stellt Exmex im allgemeinen sicher, dass die Serialisierung funktioniert, auch wenn wir sie hier nicht brauchen.. Wir können nun für jede Zeile der Form 0: 4 1 5 die rechte Seite des Doppelpunkts nach 4o1o5 transformieren und mit Exmex parsen und evaluieren. Das Ergebnis ist ein Operator, der überprüft ob eine gegebene Zeichenkette die Regel erfüllt. Dem entsprechend erstellt der folgende Code-Schnipsel für jede Zeichenkettenkette eine Regel.
const LITERAL_PATTERN: &str = "^([0-9]+|\"a\"|\"b\")";
literal_matcher_from_pattern!(OpsMatcher, LITERAL_PATTERN);
type FlatExOps = FlatEx::<RuleOp, OpsOpsFactory, OpsMatcher>;
let rules = rules_strs
.iter()
.map(|s| -> ExResult<_> {
let flatex = FlatExOps::from_str(s)?;
flatex.eval(&[])
})
.collect::<ExResult<Vec<_>>>()
.ok()?;
Im letzten Schritt werten wir für alle Zeichenketten, die sich in messages im folgenden Schnipsel verbergen, die Regel 0 aus und verdienen uns einen goldenen Stern.
messages
.iter()
.filter(|msg| {
// evaluate rule 0 for each string
let res = rules[0].eval(&vec![msg.as_str()], &rules);
// we consider an evaluation a match if all letters have
// been consumed and precisely the empty string is left
// in the result vector.
res.iter().filter(|s| s.len() == 0).count() == 1
})
Der komplette Code befindet sich auf Github.