2 ms·

I used BurntSushi's excelent aho-corasick, which unsurprisingly implements the Aho–Corasick algorithm (overkill I know). It did take me a while to realize thoug

I used BurntSushi's excelent aho-corasick, which unsurprisingly implements the Aho–Corasick algorithm (overkill I know). It did take me a while to realize though that there are overlaps which meant that my code worked on the example input but not on the real input (fortunately the library has you covered in both cases). I have the code on my GitHub but solve it yourself first, it's fun. https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

masklinn 3y ago
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.
- burntsushi 3y 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.MatchKind.html https://docs.rs/aho-corasick/latest/aho_corasick/enum.MatchK...
  - masklinn 3y 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.
    - burntsushi 3y ago
      Yup. Same kind of thing has happened to me many times. :-)
midwestcode 3y ago
I also thought to use a Trie for part two, thinking of it similarly to a typeahead problem, but I hadn't heard of Aho-Corasick. I thought it was over-complicating a day one solution, so I ended up brute-forcing similar to above solutions. Still, it is nice to learn about this algorithm. I may come back to give it a shot and compare runtimes later. Thanks!

masklinn 3y ago

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.

burntsushi 3y 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.MatchKind.html https://docs.rs/aho-corasick/latest/aho_corasick/enum.MatchK...
- masklinn 3y 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.
  - burntsushi 3y ago
    Yup. Same kind of thing has happened to me many times. :-)

midwestcode 3y ago

I also thought to use a Trie for part two, thinking of it similarly to a typeahead problem, but I hadn't heard of Aho-Corasick. I thought it was over-complicating a day one solution, so I ended up brute-forcing similar to above solutions. Still, it is nice to learn about this algorithm. I may come back to give it a shot and compare runtimes later. Thanks!