11 ms·
As others have said, part 2 of today's was really difficult. I finally solved it using Python regex `overlapped=true`, but it was very tricky. The irritation of
by shever73 3y ago
As others have said, part 2 of today's was really difficult. I finally solved it using Python regex `overlapped=true`, but it was very tricky. The irritation of having all of the test cases passing, but it failing for my challenge input!
I hope it doesn't scare off newcomers, but I already know a few who have given up on part 2.
- jjice 3y agoSame here. I would've really like if the spec specifically mentioned the possibility of that one edge case ahead of time instead of having to sift through the 1000 lines of input. No hate on AOC though, I really respect all the hard work that goes into it.
- frantathefranta 3y agoYeah I was sort of lucky that my edge case was on the last line, still took a full hour of wondering why my solution was wrong though.
- wjholden 3y agoWhat was this edge case you encountered? My code worked...after I finally read the problem closely enough.
- shever73 3y agoFor me it was a lack of specific instructions on how to handle overlaps. The edge case that frustrated me for a while was "oneight" at the end of a line. My initial code made it look like this "1ight", when it should have been "18".
- WJW 3y agoWhen searching for the last number in the line I just reversed the line and scanned through it looking for the reversed strings for the number: one -> eno two -> owt three -> eerht etc It makes the entire solution extremely simple, though a little verbose.
- nucleardog 3y agoYeah I was a little confused about all the people saying they've already given up on day 1. Seems like everyone's just really overcomplicating this. Why is everyone jumping to "replace the word strings with the digits" instead of just doing exactly what the problem says and... finding the first and last occurrence? 1. Build a list of values with corresponding string matches: [ 0 => ['zero', '0'], 1 => ['one', '1'], ...] 2. Loop through that and find the index of each within the input string, maintaining the lowest seen index + associated value. 3. When done, return value. To find the last occurrence... just reverse the input string and all the search strings. I'm not even sure it's all that verbose. If you exclude the part where I hardcoded an array of ten digits, it was... 11 lines of code, a third of which are closing braces. I'm sure I could cut it in half if I used some builtins for mapping/reducing/etc.
- skydhash 3y ago> I'm not even sure it's all that verbose Mine is. But that's because I don't bother DRYing it and making it more clever (yanking and pasting is faster than thinking)
- skydhash 3y agoSame here. I'm using regex and I was wondering how to make it go backwards. After a moment of thought, that seems silly, so I just reversed the string and the regex and do the scan.
- cjauvin 3y agoI find some problems of AoC are sometimes on the thin line between "it's interesting and I might learn something new" vs "wasting my time with under-specified or ambiguous problem specs".. Part 2 of Day 1 lies dangerously in the latter, for me.
- shever73 3y ago> No hate on AOC though, I really respect all the hard work that goes into it. 100% with you on this. Last year was the first year I'd had time to complete it, and I always love the challenge.
- AdamH12113 3y agoUnless the question has been edited recently, it did. There are multiple lines in the second example input that show the overlap: > eightwothree > 4nineeightseven2 > zoneight234 I test my AoC solutions incrementally by printing output, so I found that I was failing to produce the correct list of numbers in a line right away. I suppose if you're taking a faster approach and just trying to extract the first and last numbers that it's easier to miss. It's always a good idea to look at the example input, though.
- tymscar 3y agoYes, same. I keep seeing people say this on discord and reddit, but that edge case was shown twice in the example.
- agoose77 3y agoIt shows an overlap, but it doesn't indicate how one should parse it.
- criddell 3y agoIt showed "eightwothree" to be 83. Or is that not what you are talking about?
- jacksontheel 3y agoIf it had shown "eightwo" as the last part of a string, then people with overlap would fail the example because they'd be finding "eight" where "two" would be correct. Having it at the beginning means it was overlooked, at least for me. Though, I have no problem with the "spec". This a code puzzle game, so figuring that out was part of the fun, in my opinion
- philomath_mn 3y agoSo are you saying that overlapped characters can be used for both numbers? Meaning: - eightwothree -> 823 (answer 83) - 4nineeightseven2 -> 49872 (answer 42) - zoneight234 -> z18234 (answer 14) I interpreted the instructions as saying to take the first match from the left and not count the overlaps. Unfortunately this gives the same answer as the overlap interpretation on the examples given in the problem statement: all the overlaps occurred in the middle where they didn't matter. If they had shown oneight -> answer: 18 then I would have understood the spec.
- mxsjoberg 3y agoI moved a pointer until match then moved back one step to cover overlap, probably not great but worked.
- femtozer 3y agoI agree, the first day is usually trivial, that wasn't the case here. I also tried using regex but ended up implementing a much simpler solution using index() and rindex().
- torbencarstens 3y agoAnother option when using regex would be to use the lookahead[0] operator (as long as supported, which is the case for the python re module) (?=(one|two|three|[...])) would return `["two", "one"]` for the input string `twone` since the lookahead operator doesn't consume the next character. [0] https://www.regular-expressions.info/lookaround.html https://www.regular-expressions.info/lookaround.html
- Huppie 3y agoAnother trick is you can put some regex engines in right-to-left mode, so my lazy (and admittedly relatively expensive cpu-wise) solution was to match ltr for first and rtl for last.
- dumbo-octopus 3y agoOr just tack a greedy anything-matcher to the front of the regex: .*(?: ... )
- nikanj 3y agoPeople who went with posh tools like regexpen were stumped, people with an C64 BASIC inspired for loop had little difficulty. The problem was optimized for the unga bunga
- frankjr 3y agoI 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 agoI 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 agoYeah, 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...
- 3y ago
- jetrink 3y ago> As others have said, part 2 of today's was really difficult. I suspect it was purpose-built to foil ChatGPT. I solved it on my own first and then went back and tried to help GPT4 write a solution. Even after carefully walking it through a strategy, discussing edge cases, and having it outline a solution in pseudocode, it still failed completely to translate our conversation into working code. (It didn't even work for non-tricky input.) It did anticipate the edge cases though, so that's something. Did anyone have any better luck with ChatGPT? I wonder if LLM-resistant puzzles and generally greater difficulty (at least for the second star) will be a theme this year.
- philomath_mn 3y agoYeah I had GPT4 take like 5 stabs at it with explicit test cases and explanations and none of them worked
- Maxion 3y agoI got it to work with ChatGPT, took around 5 attempts, but that was mainly me not understanding all the edge cases. Once I came up with a strategy that would work, ChatGPT gave me working code. My strategy was not efficient, but did work. I walked the string twice, first LTR and replaced all found strings with numbers, then walked right to left, and replaced all backwards strings to numbers. Then took the first digit from the left walked string, and the last from the right walked string.
- hypersoar 3y agoI heard the question was difficult before solving it, and then I was surprised when I didn't hit any speed bumps. The overlapping case didn't even occur to me. It turns out I stumbled upon a simple solution: use two regexes. One to match the first digit, and one to match the last. Then the overlapping is a total non-issue.
- abound 3y agoIf the whole numeric part of the string was something like "eightwo", I think that solution would fail.
- deleted 3y ago[deleted]
- stefandesu 3y agoYeah, that's what I did for part 2 and there were no issues. I did try to solve it with a single regex at first, but for some reason I wasn't able to figure out the right combination of lazy/greedy matches to make it work (so I didn't even get far enough to discover the overlap issue).
- kristjansson 3y agoI think it's tricky for those of us trying to be a bit too clever. Certainly it's designed to catch out the obvious replacement strategy. However the 'naive' solution still feels quite nice. Some python, at the risk of sharing spoilers: fixes = { "seven":"7", "two":"2", "one":"1", "nine":"9", "eight":"8", "three":"3", "four":"4", "five":"5", "six":"6" } cands = set(fixes.keys()) | set(fixes.values()) total = 0 for line in Path("input/1.txt").read_text().splitlines(): matches = list(filter(lambda k: k in line, cands)) first, *_ = sorted(matches, key=line.index) *_, last = sorted(matches, key=line.rindex) total += int(fixes.get(first, first) + fixes.get(last, last)) print(total)
- threatofrain 3y agoThe inputs are actually not as tough as they could be. It’s possible to beat this puzzle with brittle regex that would fail on something like oneightwone.