blairfrandeen / 2022-AoC

Wherein I pretend I learned anythign at all about programming int he last year
0 stars 1 forks source link

Day 13 #12

Open blairfrandeen opened 1 year ago

blairfrandeen commented 1 year ago

I'm stuck on day 13. I found a beautiful solution. I think I need to let go of the ego idea that I can solve day 13 by myself and instead make use of my time by studying this one as deeply as I can, and then see if I can replicate it once I've really grokked it.

I have been struggling to get nom to work for me. I'm convinced one needs to study a course in nom for at least a month before it can be made usable. But this solution is so functional, I really like it.

The first thing I notice that I've been missing is the following block:

enum Item {
    Scalar(u32),
    List(Vec<Item>),
}

So this isn't the Rc<T> that I suspected I need---and it's a part of Rust that I really don't know how to use yet.

blairfrandeen commented 1 year ago

I'm going to use this as an exercise to systematically dig through the code and make sure that I understand every bit of it. The first thing I need to drill through my head for nom is IResult. I copy code here from the nom documentation to help me understand it.

pub type IResult<I, O, E=(I, ErrorKind)> = Result<(I,O) Err<E>>;

First off I is for Input and O is for Output. This means that the results I get from a parser will always return what remains of the input (I), followed by what the parser found (O). This is a type alias. If no Error (E) is specified, then the error returned will be of type I, and an ErrorKind specified by the parser function.


I'm also starting to understand the form in which parsers are written, and that they rely heavily on the ? operator, which as I understand it returns Ok if it passes and otherwise lets the function throw an error. A typical short parser is written as:

use nom::{bytes::complete::tag, IResult};

fn main() {
    println!("{:?}", abc_tag("abcdef"));
}

fn abc_tag(input: &str) -> IResult<&str, &str> {
    let y1 = tag("abc");
    let (input, output) = y1(input)?;
    Ok((input, output))
}

Running this program prints

Ok(("def", "abc"))

The remaining input "def" is returned along with the tag that was matched "abc". Calling instead abc_tag("defglol") yields:

Err(Error(Error { input: "defglol" code: Tag }))

Kind of cryptic, and I don't understand why it's all so deeply nested.

Let me back up just a second and see if I can't understand why I'm so reliant on the ? operator. Let me try keeping it all in main():

fn main() {
    let p1 = tag("abc");
    let r = p1("abcdef");
    println!("{:?}", r);
}

Running this gives the following error:

error[E0283]: type annotations needed
  --> src/main.rs:4:14
   |
4  |     let p1 = tag("abc");
   |              ^^^ cannot infer type of the type parameter `Error` declared on the function `tag`
   |
   = note: multiple `impl`s satisfying `_: ParseError<&str>` found in the `nom` crate:
           - impl<I> ParseError<I> for ();
           - impl<I> ParseError<I> for (I, nom::error::ErrorKind);
           - impl<I> ParseError<I> for VerboseError<I>;
           - impl<I> ParseError<I> for nom::error::Error<I>;
note: required by a bound in `nom::bytes::complete::tag`
  --> /home/blair/.cargo/registry/src/github.com-1ecc6299db9ec823/nom-7.1.1/src/bytes/complete.rs:32:29
   |
32 | pub fn tag<T, Input, Error: ParseError<Input>>(
   |                             ^^^^^^^^^^^^^^^^^ required by this bound in `nom::bytes::complete::tag`
help: consider specifying the type arguments in the function call
   |
4  |     let p1 = tag::<T, Input, Error>("abc");
   |                 +++++++++++++++++++

I find that I always freeze up and go looking for another solution when I run into this. However, I think this is because Rust doesn't know that I have the secret IResult weapon in my pocket. Changing the errant line to

let r: IResult<&str, &str> = p1("abcdef");

fixes the problem and gives me the same result I had before.

I like this better, but it's actually not what the compiler suggested. Another way to fix the problem is

let p1 = tag::<&str, &str, nom::error::Error<&str>>("abc");

Although I prefer the first method.

blairfrandeen commented 1 year ago

Looking again at the code from the link above, I find this worthy picking apart and trying to understand.

fn parse_scalar(input: &str) -> IResult<&str, u32> {
    map_res(
        recognize(
            many1(
                one_of("0123456789")
            )
        ),
        |out: &str| {
            out.parse()
        }
    )(input)
}

I keep running into the following with nom: How to parse a string of digits into a number? It seems like it should be easy. In regular Rust it's "123".parse::<i32>().unwrap() and it tends to work fine--so why so many lines for the section above?

It seems that the same function could just as well be written

use nom::character::complete::i32;
i32("123")

What bothers me the most about the implementation above is that it doesn't handle negative numbers, and it's not clear to me from the puzzle input the negative numbers aren't allowed. Both this and the other solution I've looked at seem to have hard-coded the digits 0 through 9, which makes me wonder if I'm really missing something.