undefined | Better HN

0 pointsmasklinn2y ago0 comments

I first brute-forced the solve (on each line, find and rfind every digit, keep the smallest find and the largest rfind), that worked fine out of the box as that's not sensible to overlap.

I then figured I'd use aho-corasick because that was an opportunity to, and there's no kill like overkill.

I then proceeded to waste half an hour because I didn't read the documentation, so I didn't see that `find_iter` finds non-overlapping occurrences. I assumed it found overlapping occurrences since that's what the algorithm does out of the box.

0 comments

burntsushi2y ago

Yeah, the overlapping case is the less common case in my experience. And even in the non-overlapping case, the "standard" approach is often not what you might expect. For example, if one were to use the Aho-Corasick algorithm to implement a regex like `samwise|sam`, the standard algorithm would yield incorrect results if you expect it to behave like, say, Perl or Javascript regexes. That's what led me to develop `MatchKind`[1], which I believe is a novel re-formulation of the standard algorithm. At least, I'm not aware of others providing it. (Some try to, usually by trying to stitch together the right match after searching using the standard algorithm, but I don't believe it works in all cases. And introduces overhead.)

In particular, the SIMD optimizations in the aho-corasick crate only apply when MatchKind::LeftmostFirst or MatchKind::LeftmostLongest are used.

[1]: https://docs.rs/aho-corasick/latest/aho_corasick/enum.MatchK...

masklinnOP2y ago

Oh yeah no, the issue was not with the API, it’s just that I got to the first example, figured “seems easy enough” making a bunch of assumption I did not validate in any way in the process, then when that didn’t work rather than check I was using the API correctly I made a bunch more assumptions (completely nonsensical too) of where the error might be. When I finally got to reading the docstring for `find_iter` the error was obvious and it took seconds to get the correct result again.

burntsushi2y ago

Yup. Same kind of thing has happened to me many times. :-)

j / k navigate · click thread line to collapse

0 pointsmasklinn2y ago0 comments

I first brute-forced the solve (on each line, find and rfind every digit, keep the smallest find and the largest rfind), that worked fine out of the box as that's not sensible to overlap.

I then figured I'd use aho-corasick because that was an opportunity to, and there's no kill like overkill.

0 comments

burntsushi2y ago

In particular, the SIMD optimizations in the aho-corasick crate only apply when MatchKind::LeftmostFirst or MatchKind::LeftmostLongest are used.

[1]: https://docs.rs/aho-corasick/latest/aho_corasick/enum.MatchK...

masklinnOP2y ago

burntsushi2y ago

Yup. Same kind of thing has happened to me many times. :-)

j / k navigate · click thread line to collapse