yeah not that I know there aren't any odd requirements I'll refactor mine to be based around the full ordering. Having seen other aoc problems I was a bit nervous that I was missing some requirement that meant just sorting wouldn't work.
I did topological sort on p2 and worked around the cycle with a subgraph for each update(rules containing only relevant pages), since its implied that for each update there exists correct sorting, which means it must be a DAG and can be sorted.
I ended up with some pseudo-sort on part 2, then had a realization I could just use built-in sort, then went back and updated part 1 to use sorting too, works like a charm
I spent liek 20 horus trying to complete this. I dont crap about nom and am trying ot complete it with as minimal non-std crates as possible....i got the sample result but then the real input easnt correct. I bailed. My issue is definitely the custom sorter closure i used but iono im burnt out
I build a hashmap from the first part of the input and with the second part I did a kind of bubble sort where I compared each element's keyvalue to the other elements of the line. A confusing amount of for loops, but my actual logic only has like 15 lines of code.
its annoying because i know i could bang out the logic so easily in python. but with rust i spend like 3/4 of my time getting the parser with nom. i feel like nom is very powerfull but you do thigns in these videos with nom that are just super folded. like all i wanted to do with nom is get those 2 chunks of page rules and then updates. then handle each of those in thier own parser. spend so long trying to get that working did something like this: fn parse(input: &str) -> IResult { let (input, res) = take_until("
")(input)?; let (input, _) = tag("
")(input)?; // let (input, res) = take_until("
")(input)?; // let (input, _) = tag("
")(input)?; let (_, rules) = many1(parse_page_rule)(res)?; let (rest, updates) = many1(parse_update)(input)?; let result = (rules, updates); Ok((rest, result)) } fn parse_page_rule(input: &str) -> IResult { terminated( separated_pair(complete::u32, tag("|"), complete::u32), line_ending, )(input) } fn parse_update(input: &str) -> IResult { terminated(separated_list0(tag(","), complete::u32), line_ending)(input) } ... and then this doesnt work for the real input because this is
instead of . is it possible you could do like a day or 1 part or something where you break the parser down into smaller chunks or something. or maybe a video on nom specifically and how to handle that a parser may fail. how to return an error in a parser besided the ? syntax. why i can provide line_ending in terminated but not in take_untill? things like this? Great videos. keep it up. - Alan
I can definitely dive into nom more when we're doing the videos. There's a couple nom-related videos on the channel too. The way you're thinking of separating out parsers is correct, but the order in which you're trying to do it is giving you a bit of trouble. Your mental model is "let me split this in two first, then parse each section" right now. But a key insight is that nom has to parse all of the content from front to back *anyway*, so the whole first section you're trying to skip when doing that can "just be parsed" instead of skipped. Here's an example that shows the differences between trying to do newlines manually. It also shows one of the key aspects you're running into. The final parser uses line_ending and two other parsers (which could be rules/updates). You can still think of them as being separated by the line endings *and* being separate parsers, but instead of trying to skip directly to the separator and splitting, let the parser that has to parse the first section anyway do its work, *then* look for the separator. play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=59b44e78f76b4f2522c4fc6f6fbc762e
@chrisbiscardi yeah I hadn't thought about it like that. Try to get the input parsed rather than getting the split by parsing then parsing again. Makes sense. I did see you had some nom stuff after I posted. On my watch later list :). Thanks for your response. Look forward to tomorrow.
std iter and slice have `is_sorted_by`, which is very useful
Ohh, good to know :)
I used ordering for my solution of both parts, worked wonderfully
yeah not that I know there aren't any odd requirements I'll refactor mine to be based around the full ordering. Having seen other aoc problems I was a bit nervous that I was missing some requirement that meant just sorting wouldn't work.
Thanks, the explanation of `fold_many1` was very helpful!
Tried a topological sort of the rules and got my head handed to me in part 2 because of circular rules. Thats AoC.
I did topological sort on p2 and worked around the cycle with a subgraph for each update(rules containing only relevant pages), since its implied that for each update there exists correct sorting, which means it must be a DAG and can be sorted.
I ended up with some pseudo-sort on part 2, then had a realization I could just use built-in sort, then went back and updated part 1 to use sorting too, works like a charm
I need to learn how to use Nom; it's really nice to see how you parse the input using it.
I spent liek 20 horus trying to complete this. I dont crap about nom and am trying ot complete it with as minimal non-std crates as possible....i got the sample result but then the real input easnt correct. I bailed. My issue is definitely the custom sorter closure i used but iono im burnt out
I build a hashmap from the first part of the input and with the second part I did a kind of bubble sort where I compared each element's keyvalue to the other elements of the line. A confusing amount of for loops, but my actual logic only has like 15 lines of code.
its annoying because i know i could bang out the logic so easily in python. but with rust i spend like 3/4 of my time getting the parser with nom. i feel like nom is very powerfull but you do thigns in these videos with nom that are just super folded. like all i wanted to do with nom is get those 2 chunks of page rules and then updates. then handle each of those in thier own parser. spend so long trying to get that working did something like this:
fn parse(input: &str) -> IResult {
let (input, res) = take_until("
")(input)?;
let (input, _) = tag("
")(input)?;
// let (input, res) = take_until("
")(input)?;
// let (input, _) = tag("
")(input)?;
let (_, rules) = many1(parse_page_rule)(res)?;
let (rest, updates) = many1(parse_update)(input)?;
let result = (rules, updates);
Ok((rest, result))
}
fn parse_page_rule(input: &str) -> IResult {
terminated(
separated_pair(complete::u32, tag("|"), complete::u32),
line_ending,
)(input)
}
fn parse_update(input: &str) -> IResult {
terminated(separated_list0(tag(","), complete::u32), line_ending)(input)
}
...
and then this doesnt work for the real input because this is
instead of
.
is it possible you could do like a day or 1 part or something where you break the parser down into smaller chunks or something. or maybe a video on nom specifically and how to handle that a parser may fail. how to return an error in a parser besided the ? syntax. why i can provide line_ending in terminated but not in take_untill? things like this?
Great videos. keep it up.
- Alan
I can definitely dive into nom more when we're doing the videos. There's a couple nom-related videos on the channel too.
The way you're thinking of separating out parsers is correct, but the order in which you're trying to do it is giving you a bit of trouble. Your mental model is "let me split this in two first, then parse each section" right now. But a key insight is that nom has to parse all of the content from front to back *anyway*, so the whole first section you're trying to skip when doing that can "just be parsed" instead of skipped.
Here's an example that shows the differences between trying to do newlines manually. It also shows one of the key aspects you're running into. The final parser uses line_ending and two other parsers (which could be rules/updates). You can still think of them as being separated by the line endings *and* being separate parsers, but instead of trying to skip directly to the separator and splitting, let the parser that has to parse the first section anyway do its work, *then* look for the separator.
play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=59b44e78f76b4f2522c4fc6f6fbc762e
@chrisbiscardi yeah I hadn't thought about it like that. Try to get the input parsed rather than getting the split by parsing then parsing again. Makes sense. I did see you had some nom stuff after I posted. On my watch later list :). Thanks for your response. Look forward to tomorrow.
I just did input.lines() and parsed each line. Gets rid of most of your difficulties. .