Day 1: Trebuchet?!
by Keith Star
Today’s problem is pretty straightforward. We are given a string that contains lines of alphanumeric characters. The algorithm is to lexicographically concatenate the first and last numeric character on each line into a single number. Sum all the numbers from all the lines to get a total. Each line contains at least one number. So, for example, “two65ffd91four” becomes 61.
⚠️ Spoiler Alert!
Below is a solution to the puzzle.
Rust Solution
My plan was to implement the algorithm in Rust first, and then turn it into dwarf, which is straightforward. Rust is my language of choice, which clearly influenced dwarf. The reason that I’m not implementing it in dwarf first is that Rust works.
Below is my Rust implementation.
I saved my input into a file called input_1.txt, and then read it into a local variable.
For each line, we iterate over the characters looking for digits.
When we find one, we store it in second_digit.
If this is the first digit of the line, it’s also stored in first_digit.
When all of the characters are processed, we add the two digits together (don’t forget about your ten’s place) and add them to the total.
Note that the only tricky thing about this problem is that you need to account for when there is only one number in the line.
This is why we always update second_digit.
fn main() {
let input = include_str!("input_1.txt");
let mut total = 0;
for i in input.lines() {
let mut first = false;
let mut first_digit = 0;
let mut second_digit = 0;
for j in i.chars() {
if j.is_digit(10) {
if !first {
first_digit = j.to_digit(10).unwrap();
second_digit = first_digit;
first = true;
} else {
second_digit = j.to_digit(10).unwrap();
}
}
}
total += first_digit * 10 + second_digit;
}
println!("{}", total);
}
dwarf Solution
And below is the dwarf implementation.
Note that I punted on loading a file with the lines, since I don’t want to deal with that in dwarf yet.
Instead I inlined it as a single variable, input.
The example below only shows a few of the 1000 input lines.
As you can see, it’s very similar to the Rust version.
The main differences are that the mut keywords are missing, and that you can directly iterate over a string.
fn main() {
let input = "fivethreeonezblqnsfk1
two74119onebtqgnine
jrjh5vsrxbhsfour3
...
1rdtwofjvdllht5eightsixfourbl";
let total = 0;
for i in input.lines() {
let first = false;
let first_digit = 0;
let second_digit = 0;
for j in i {
if j.is_digit() {
if !first {
first_digit = j.to_digit();
second_digit = first_digit;
first = true;
} else {
second_digit = j.to_digit();
}
}
}
total = total + first_digit * 10 + second_digit;
}
print(total);
}
Fixing dwarf
Of course it didn’t work correctly the first time I tried to run it. This is the first error that cropped up (isn’t it pretty?):
I think the error could be better.
It’s saying that there is no lines method.
What’s it’s missing is that it’s looking at the String type.
I could have addressed this at the time, but it didn’t occur to me until writing, so I’ve created an issue.
Extruder
The fix is pretty simple.
There are two places that we need to update to support the lines method.
The first is in the extruder.
When dwarf parses the source, it creates an AST in memory.
The extruder turns the parser’s AST into dwarf’s AST, while doing type checking, and other checks.
Below is an excerpt of the code that handles a method call in the extruder.
pub(super) fn inter_expression(
expr: &RefType<ParserExpression>,
span: &Span,
block: &RefType<Block>,
context: &mut Context,
lu_dog: &mut LuDogStore,
) -> Result<(ExprSpan, RefType<ValueType>)> {
let expr = s_read!(expr).clone();
match expr {
...
ParserExpression::MethodCall(instance, (ref method, meth_span), args) => {
...
// We recursively call ourselves to evaluate the expression which is
// the thing we are evaluating the method upon.
let (instance, instance_ty) = inter_expression(instance, ...);
...
// Based on the type of the interred expression, we lookup the method name.
let ret_ty = match s_read!(instance_ty).subtype {
...
Ty::SString(_) => {
match method.as_str() {
...
LINES => {
// String is a primitive type, and it's defined in
// the sarzak model.
let string = Ty::new_s_string(context.sarzak);
// ValueType is from the dwarf model -- it wraps the
// String.
let string = ValueType::new_ty(&string, lu_dog);
// Finally, our ultimate return type is a list of strings.
// Again, wrapped in a ValueType, which is what we return.
let list = List::new(&string, lu_dog);
ValueType::new_list(&list, lu_dog)
}
...
}
}
...
}
...
}
}
}
Briefly, there is a function in the extruder called inter_expression.
It’s essentially a big switch statement that takes a bunch of inputs, including most importantly an expression from the parser AST.
It in turn returns an dwarf AST expression, and the dwarf type of the expression.
The code is perhaps a bit cluttered, and that’s because there is really a lot going on. The macros in the code allow me to change the type of pointer that dwarf uses for it’s AST and values. We are tracking spans from the source file, all the way through execution to produce nice errors. There are also two different “models” that I use in defining the dwarf AST. Perhaps more on models in a future post.
Interpreter
pub fn eval(
call_id: &SarzakStorePtr,
expression: &RefType<Expression>,
context: &mut Context,
vm: &mut VM,
) -> ValueResult {
...
Value::String(string) => match meth_name.as_str() {
...
LINES => {
let ty = Ty::new_s_string(&s_read!(sarzak));
let ty = ValueType::new_ty(&ty, &mut s_write!(lu_dog));
Ok(new_ref!(
Value,
Value::Vector {
ty,
inner: string
.lines()
.map(|line| new_ref!(Value, Value::String(line.to_owned())))
.collect()
}
))
}
...
}
...
}
Deep within the interpreter there is an eval function for the Call expression.
Above is a snippet of that code.
We are matching on Value::String, which is the type of the value that we are calling the method on.
Value is the value type that the interpreter and VM work with in order to abstract over types.
It’s fairly straightforward to build a list of strings from the lines method on String.
Note that we’re using the same Rust method as the Rust solution.
I needed to also add the to_digit and is_digit methods to the Char type in similar fashion.
I won’t belabor the details.
More dwarf Awesomeness
Below is a really useful feature of dwarf: --uber.
That flag turns on a breadcrumb in most error messages that points you back to the cause in the source.
This allows me to quickly figure out what part of the codebase I need to look at.
You can see an example below of running dwarf with, and without the flag.
Parting Thoughts
The problem wasn’t super hard to solve. I’m sure that there are much cooler solutions, but this isn’t about that. This is more about getting dwarf to a point where it can be used for real work.
The commit to the dwarf repository for this solution, and the necessary changes is located here on GitHub.
tags: dwarf, - adventofcode, - rust