does it deal with cases like "twone", "nineight" and so on? it doesn't appear so to me because of the leading sed statements would commit the interpretation regardless of what happens next, but perhaps there is something subtle im not seeing.
It uses capture groups and puts them back in the replacement (the \1 ), so a match of "one" is replaced with (thematch)1(thematch). So eightwo would replace the two with two2two and end up like eightwo2two, so then the t is preserved and eight is found in a later step and then you end up with eight8eightwo2two, and can solve that using part1 only looking for numbers.
For my own I did the same, but without capture groups. So replaced "one" with "one1one" naively without regex and did that for all numbers.
While it maybe is post-hoc clever, I think most of us ended up there because we tried naively to just replace "one" with "1", which broke on things like twone. So when down that path one had to amend it instead of going somewhere else.
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.
> 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.
I 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.
Another 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.
People 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
Same 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.
Unless 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.
So 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.
It could have been more clear. The wording from the problem is "the last digit on each line". To me, that pretty clearly implies "the rightmost substring containing a digit", but I guess I can see how someone could question that interpretation.
Right, but we read the word "eight" from left to right -- to me it is non-obvious that "eightwo" should be counted as two digits when (a) there aren't enough characters to actually make both digits and (b) there wasn't a single example showing this overlap expanded
But I suppose can see the other side as well: the wording makes it sound like any spellings of those digits _counts_ as a digit rather than should be _replaced_ by a digit.
However I think the ambiguity here made the puzzle more difficult in a non-fun way.
Those examples contain overlap, but not in the first or last digit that is given as the solution. So from the instructions you can't tell that the intermediate list of numbers should be 8, 2, 3, you only know that the final answer is 83.
If 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
I 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.
For 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".
Yeah 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.
Same 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.
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.
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.
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.
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.
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!
I 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.
Yeah, 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).
I 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().
The 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.
Without going into spoilers, its interesting that people jumped to regex to solve this. For me that was a fairly non intuitive when I first saw the problem(both parts).
What jumped to me is the problem statement indicated a finite number of states and I crafted a solution based on that information. But its really cool to see how we all jump to different implementations.
While I didn't go with regexes per se, I did go with I think a fairly "standard" solution of iterating the string and finding matches, and got caught in the trap that a lot of people are mentioning.
In the end, I figured out a manual way around that, but then afterwards I realised that the iteration isn't really necessary given the problem at hand, and ended up going a completely different route that was a lot faster.
What surprised me is that I'd thought of the alternative at the start while reading the description, and then dismissed it because iteration is typically so convenient for these sorts of things.
I took one look at the overlaps, decided I had things I'd theoretically like to accomplish today that didn't involve tracking overlapping subsets of strings, and hardcoded the nine possible overlaps, i.e. [1]
Not OP, but I too first thought of a state machine. As soon as I started to write it I realized I was over-solving a day-1 problem. So I switched to brute force
I made use of the fact that "egrep -o [some regex]" will print the first (going left-to-right) match for the regex. So I ran egrep -o, and several other programs, once per line of input. (And to go from right to left, I used "rev" and an egrep on the reversed string.) My computer wept, but it worked.
Sorry all, I misused the word finite state. I meant it more from a combinatorics viewpoint(e.g. we only have X amount of operations per Y interval). You could consider my solution to be brute force code.
Abstractly I do this:
read_file()
lines = read_lines()
sum = 0
while lines:
left = get_first_num_forwards(line)
right = get_first_num_backwards(line)
sum += integer(left+right)
return sum
I define get_first_num() something like this:
get_first_num(line):
lowest_index_pair = None
for key,val in dict.values():
get_index_of_key_if_exists()
if_exists: update_lowest_index_pair()
index,num find_first_instance_num() //just gets the first num that appears
update_lowest_index_pair()
return lowest_index_pair[1]//just returns the number
Basically the idea is very similar to yours. We parse each line 11 times in both direction(10 per the word_vals dict and once more to find the index of the first numerical) which is only 22 parses. Then we grab the minimum index from this list and concat with the opposite side.
I just don't do any replacements at the cost of a longer run time. But I figure the cost of 11 parses was low enough that it wouldnt impact the run time significantly for this exercise.
The key point is that overlaps are not an issue because we check for string comparisons in the methods
Seems to me that people made part 2 harder than it us. Just define an array containing the digits: "one", "two", and so forth. Then check for substring matches, position by position. Maybe not elegant, but effective.
I think the issue is that they tried to separate the input into a list of tokens, like ["5", "nine"], and work from there, which doesn't work on something like "oneight".
I didn't have that issue at all; I just looped through the 20 different tokens and found first and last instances of all of them, and compared the very first and very last of all instances.
I just placed digits in the middle of the words instead of replacing them. This way I didn't "break" any overlapping words, and the order of digits is still the same.
The main difficulty of part 2 is that there are edge cases that are not covered by the examples. I have appended the example list with some edge cases, so use this list instead:
I don't get the amount of effort people out into the replacement-strategy, I did perfectly fine without it and the code is about as complex as the examples I've seen.
Yeah, all the talk of replacement seems like people masively overthinking or abstracting a day one problem. My C++ solution was a simple search using the <algorithm> header. It's a little less neatly abstracted out as yours, and could be cleaned up a fair bit, as I wasn't bothered to deduplicate the code after getting it working (and I will if this turns out to be useful tomorrow), but the essence is the same:
I disagree on it being "overthinking". I just did replacement without really thinking. Saw that it failed on the "eightwo" case since "two" got replaced first, so just replaced "two" with "two2two" instead, then passed it through solver for part1. To me that's simpler and more naive than correctly writing a search or backwards-forwards regex :)
Ahh, people are trying to do a replacement before finding tokens. I wondered why so many people were saying this was difficult.
My head went straight to token parsing, which given the limited set of tokens made it trivial. Thought I was missing something
Day one part 2 was relatively rough. Things I learned from it: rust regex crate doesn't support look-ahead, rust onig crate is currently broken in many ways and shouldn't be used (the version in crates.io doesn't compile and the version on GitHub is failing tests and look-ahead isn't working). It was a very frustrating time for me. After 2 hours of troubleshooting the above I used the same approach in python and it took 2 minutes to write. So annoying.
> The regex crate doesn't support arbitrary look-around because it isn't known how to implement efficiently.
A bit of a philosophical question:
If how to write an efficient implementation is yet not known to man, ie. not a matter of the library's author time or skills, but literally a limit on human knowledge: why not at least provide the functionality with a good enough implementation? (with caveats just possibly mentioned in documentation)
IMHO that'd be arguably a good thing for everybody, at a minimum better than just not offering the possibility at all. Which drives users to frustration, or leaves them having to discover a more pragmatic alternative lib that opted to add it.
This is no complaint or feature request... I just want to learn from some insight behind the thought process of "if it's not efficient, better not have it at all"
PS. Thanks for the link. Now I have a good read for the weekend, for sure!
ReDoS is one answer. Another answer is that it would effectively require supporting another regex engine with very different semantics internally. That's a tall order, and with the existence of fancy-regex (and other engines), there's no real compelling reason to do it.
You don't need to be all things to all people. Embrace the fact that there are other choices!
Because it is a mechanism for ReDOS, and the standard library should not be introducing vulnerabilities into users. Other libraries can implement it for folks who decide they really need it.
Okay, let me amend my comment. If you have a degree in CS, you're absolutely sure that you've understood all the caveats of the libraries you're using, and you limit your inputs so that the expected running time is under your target execution time, then you can avoid putting a timeout on your regex executions. In any other case, add a timeout.
Ah jeez I totally missed this crate! Thanks!! I had originally gone with Onig because of a SO post you made years ago. Fancy-regex substituted right in and worked immediately. Much appreciation for all you do
It's a Regular Language, in the mathematical sense. All you need is the greedy match anything sequence, I don't know why so many people jumped to non-Regular regex extensions.
Oh I understand. That's a good idea. Honestly I only ever use regex for AOC so I never would've thought of using it like that. I'll keep it in mind. Thanks!
Easy mode for this use-case is to match on a reversed version of the regex on a reversed version of the string, but yeah, negative lookahead would be great.
Yeah I mean I did think of that but after spending all that time figuring out Regex I was decided to commit as fully as I could until it was 3am and I had to go to bed. There were lots of alternative solutions I thought of but chose to ignore out of stubborness. I'm admit, a good bit of the frustration was my own fault (but also c'mon this was way harder than any day 1 we've had before)
Yeah, that was exactly was I was doing. For the left number do everything as normal, while walking through the string. For the reverse part, just walk through the reverse of the string and match the reversed keywords.
I'm not familiar with the AoC problem. You might be able to. But RegexSet doesn't give you match offsets.
You can drop down to regex-automata, which does let you do multi-regex search and it will tell you which patterns match[1]. The docs have an example of a simple lexer[2]. But... that will only give you non-overlapping matches.
You can drop down to an even lower level of abstraction and get multi-pattern overlapping matches[3], but it's awkward. The comment there explains that I had initially tried to provide a higher level API for it, but was unsure of what the semantics should be. Getting the starting position in particular is a bit of a wrinkle.
It's kind of awkward with that one, because you still have to check the individual patterns; it doesn't give you a multi-match on each pattern.
With the Aho-Corasick implementation you can just map the string -> {ordered list of matches} -> numbers associated with the match, and then you've got a little vec of digits you can grab the first and last entries of. Ended up being just a few lines of code, together with a hard-coded list of ["0", "one", "1", "two", ...] and the numbers they mapped to [0, 1, 1, 2, 2, ...].
> With the Aho-Corasick implementation you can just map the string -> {ordered list of matches} -> numbers associated with the match, and then you've got a little vec of digits you can grab the first and last entries of.
My solution was to shove it through `Itertools::minmax_by_key(|m| m.start()).into_option()`, which returns the lowest and highest matches (or a duplicate of a single match). Then to map to digits I actually ordered the patterns differently: I went 1, 2, 3, ..., one, two, three, ...
That way:
- for part 1 I could slice out the first 9 elements and it works uniformly
- mapping a "digit" to an actual digit is taking the index (match.as_pattern().as_usize()) modulo 9 to shift the textual versions to the numerical, then add one.
0/zero is not a valid digit so you can just ignore it, although you could always include it, use mod 10, and not increment the result, so same diff.
Ah, that's a nice observation about zero, that would have saved me some typing. :-)
I did the same thing with my actual solution in terms of order (but I went 0, 1, 2, 3), but mostly so I could truncate the matching array to solve part 1. Notably, that was a ret-con of my actual solution to part 1, which I originally did by just mapping the characters through .is_ascii_digit(), but I wanted to consolidate the code a little. I ended up with:
Definitely not but it was the most elegant solution that I could think of right away, so I committed to it. In hindsight, it would've been relatively easy to solve with some loops and no dependencies but hey, I wouldn't have learned so much about the rust regex ecosystem that way.
Advent of Code means a lot to me. The problems are fun, sure, but something about it really boosts my winter. I've noticed that I get a lot more productive with my hobbies in the weeks following AoC.
I think maybe it's as simple as living on the west coast and getting used to getting amped and doing some big, adrenaline-filled, social, fun activity at 9 PM every night. It gets me used to being PRODUCTIVE in the evening and not just settling down to watch TV.
Anyway, whatever the cause, I care a lot about AoC. It makes my Decembers a whole lot happier.
For me it's the same, but opposite. It forces me out of bed and ready by the computer at 6 in the morning, haha. Which of course also means that I can end early and suddenly have so much evening time.
I ended up using parser combinator library nom. It's not something I use daily, therefore parsing became a puzzle on its own.
Nom already has a parser for numbers. However, I didn't find an elegant way to take at most one digit. In the end I used take_while_m_n, and mapped it with u64::from_str().
Another challenge was absence of something such as find_all, that would repeatedly try to parse beginning from each character and then return all matches. I ended up writing my own combinator.
I think the edge cases were entirely unclear in day 1, part 2. I had to redo it in a "dumb"/brute-force way to avoid using fancy regex tricks I don't know.
It's quite clear the small sample data was chosen intentionally to not cover them.
The problem statement was super clear though. "Find the first occurrence of any one of these strings in a longer string" doesn't require any fancy regex tricks, just a for loop and knowledge about `isPrefixOf` or `startsWith` or whatever the equivalent function is called in your language of choice.
"Find the last occurrence of any one of these strings in a longer string" is just the first problem again but with all the strings reversed.
Disagree that it's clear. If the text is "oneight", there is a legitimate philosophical question about whether the string contains two numbers. I feel like most people would say no, because the only way to answer yes is by re-using letters between different words, and that's not how language works.
my example data did include the edge case that caught me out in part two, but didn't include it in a way that broke my first pass at a solution.
funny piece is it didn't click until i submitted a wrong answer, read my code for a few minutes, added a bunch of logging, and then saw the trick. i looked back at the given example and it was right there the whole time, just not called out explicitly.
> It's quite clear the small sample data was chosen intentionally to not cover them.
That is very common in AOC, the edge cases are often not called out.
Although the results vary a lot, sometimes the edge cases matter, sometimes they only matter for some data sets (so you can have a solve for your dataset but it fails for others), and sometimes the edge cases don’t matter at all, so you might spend a while unnecessarily considering and handling them all.
The edge cases are fine tho, it’s a normal thing which happens. The not fun ones are when ordering comes into play to resolve ambiguities and is not called out, it’s quite rare but when it happens it’s infuriating because it’s very hard to debug as you don’t really have a debugging basis.
It's a tough day 1, I hope it doesn't scare off too many people. Normally day 1 is just some variation of "add numbers in a list", but this year has a mean pt 2 and a few traps for people to fall into.
I wonder how long the global leaderboard will stay up before it gets hidden due to people solving with ChatGPT?
I'd actually welcome it if the leaderboard was abolished. I never really played for placement, but something about the fact that the board was full of people who routinely solve every problem in about the same time it takes me to even READ the description was a bit demotivating. I always felt this racing aspect to be somewhat at odds with the idea that this is a challenge that you can complete in your own time, maybe even on weekends, and at the end be proud that you even made it.
I tend to agree with this. The leaderboard for many programmers is a source of stress and is another type of internet "comparison" like seeing someone who appears "better" than you on social media. Advent of Code, to me, is a celebration of all the hard work of the year by getting a chance to show off any new skills or abilities you might have picked up.
Advent of Code should be about the solve and the sharing of a good problem together, not how fast can you cook a plate of spaghetti.
To add to this, AoC release its puzzles at midnight ET, so the west coast folks who are still up at 9pm PT will almost always complete the puzzles before someone on the east coast who actually sleeps a regular schedule.
It’s also the middle if the day in east Asia, and in Europe it require being ready to rumble at 5-6AM.
But that’s just how it is. Some folks are really invested and update their lives based on AoC drops, I’d assume most neither care nor even try. If you don’t look at the leaderboards there’s nothing telling you there are leaderboards.
Some people care about the leaderboard, but that's not mandatory. I don't see how the fact of its existence diminishes the experience of someone who never looks at it.
I get that some people don’t want to participate in the competition, but how is that a reason to take the feature away from others who enjoy the competition?
In the context of the larger discussion about how to save the leaderboard in the face of rampant and cheap cheating options, my point was simply that maybe it didn't need to be saved in the first place. Heck, I can't imagine it's actually possible to save it while keeping the event running as it has been.
Obviously, there are many people who do enjoy the competition, especially if you're someone who is in the top 10 consistently. But to emphasize it again: arguably, the leaderboard is not as real as you think it is. It's not me who's advocating for taking your achievements from you, it's the state of technological progress that has already done that.
According to several reports, chatgpt can't be made to solve day 1. It's strongly hypothesised that Eric increased the difficulty of the problem specifically to thwart them.
Last year they fucked the global leaderboard early, then completely dropped off during week 2, so I can't say I don't welcome it. I didn't find part 2 an issue, but I completely grug-brained it and that was not sensible to the overlap issue.
I don't know if I'll even bother this year. Their puzzles start feeling like chores by the 10th problem or so and I drop out. Maybe I'll learn a new language to spice it up this year.
I tried AoC for the first time last year, and that was pretty much my experience. A week or so of easy problems, then 1 or 2 that were still pretty straightforward but a bit more tedious, then 1 that was a lot more work because you were supposed to derive some of the rules from the example. I don't think it would've been too hard, but like you said, it was starting to feel like a chore at that point, so I stopped.
> like chores by the 10th problem or so and I drop out
That they get so involved is the reason I participate (despite also working at the same time). I love the fact that the difficulty starts low and then goes up to levels where I feel really challenged. It's a month (well, 25 days) commitment which pays off the entire 11 other months for me :)
In times past, it was Pascal that was my language of choice[1]. This year, I'm going to use a virtual BitGrid[2]. Here's the repo[3] Hopefully I can finish the 2023 problems before next November, I have nothing but the simulator. Nothing to convert text to code, do I/O, etc.
Oh boy.... Day 1 A... and I have to figure out how to feed text into a bitgrid, and get it out the other side... before I can even think about parsing it, making integers, and adding them, then converting back to text.
BitGrid - a sea of LUTs with latches, completely parallel down to the bit processing. Each LUT has 4 bits of input, and 4 independent bits out to each cardinal direction. Clocking in 2 phases, like colors on a chess board, to eliminate undefined behavior or timing issues.
Every year I want to love this. Every year I get four days in before it feels like work.
I think I’m just the wrong audience, but I really do want something this well-produced but with perhaps a very shallow diff little curve, bordering on just effortless fun.
> Every year I get four days in before it feels like work.
Same for me, but I don't think it's exactly about difficulty for me - I've done harder problems on Project Euler, SPOJ, etc., and very much enjoyed them, but somehow Advent of Code doesn't click for me. I think the difference is that there's a lot more "chore" work in AoC problems, compared to Euler or SPOJ where it's mainly about an "Aha" moment figuring out a solution (possibly getting it wrong, going back on it, and getting a different "Aha" moment exercising a different area of your knowledge space).
I interviewed somebody recently for a podcast who is a big AoC fan. His biggest reason is that, if you're learning a new language it's a great way to put it through its paces. He tries to learn a new language every year doing AoC.
He's done it with R, Julia, Rust and this year Kotlin.
I had a similar realization a while back with Factorio. I caught myself watching Youtube videos on how various systems worked and how to optimize things and solve problems, and I just thought... "man, think what I could build if I put this same energy into my programming projects."
Still, I like Factorio and similar games, and I'm excited about the upcoming expansion, but it is just kind of funny to notice that it basically feeds on the same kind of drive that I use to build little apps and whatnot, and with those projects, I end up with something a bit more tangible than an elaborate virtual factory.
Out of curiosity after finishing my solution, I tried it with chatgpt 4.0
Part1 worked after me explaining a tiny bug.
Part2 however never worked. Even after explaining exactly where the bug was in the python solution got came up with, it couldn’t fix it.
It was quite fascinating watching it try over and over with different approaches, but it couldn’t even get the example working.
This just goes to show how good of a puzzle maker Eric is if it stumped gpt4 on day1 when last year gpt3.5 did the first 5 days.
Last year, I used ChatGPT on one of the first puzzles, and ended up writing a blog post about it, where I sort of do commentary on the conversation.
It's funny to read this a year later, and filter it through my experiences with ChatGPT over the last year. Some of it still rings true, some of it would probably be much improved with GPT-4. But the places where the LLM fell down in my examples are still the same kinds of issues you get using GPT as an assistant today.
Part two of today's problem makes me wonder if they're trying to come up with puzzles that aren't easy for LLMs to complete but might end up making things that also discourage humans from playing.
This looks really cool, but they should make it clearer that you only get one submission per day, and they're not going to check that your answer is valid before submitting.
I submitted this (wrong) answer
1. e3 Na6 2. Bxa6 Nf6 3. Bf1 Ne4 4. d4
but only realised afterwards that it has to be _exactly_ 4 moves, less than 4 moves is not good enough.
I think I’d like to try this year’s in a language I haven’t touched before. What languages should I consider if I want something paradigmatically different from Go, Python, etc?
The only problem with these kinds of languages is finding the place where the experts publish their solutions, if they do. I'd love to see what an expert can do and what I can learn from them.
I do them in Elixir and I find it to be a great language for this kind of thing.
I'm not a very sophisticated Elixir programmer, but I think my solutions are decent enough (and readable, for the most part!). I have a repo which has solutions for quite a few of the puzzles, along with some nifty little mix tasks to help set up a skeleton for each day's puzzle and automatically fetch the input file.
Ah, Kino looks awesome, that's exactly the kind of automation I set up in my own repo. I slightly prefer my own way because it lets me do the dev locally, but that is still a totally sweet setup!
Someone put together a very nice template in Rust that automatically downloads tests, solutions, creates a scaffold for the binaries, etc and submits solutions through CLI. I used this template last year to learn Rust and it got me "up and running" quickly and easily.
Creating your own can be fun tho. My version uses a procedural macro (was a good excuse to finally implement one) to automatically fetch the data set and cache it, and provide a few common helpers.
Absolutely - this is one of the things I like so much about doing them with Elixir. Between the built in testing framework and the REPL it's so easy to work through the problems iteratively.
I wish Elixir's REPL / editor integration was half as awesome as SLIME / Emacs, but it's still leaps and bounds beyond what you get in most non-functional langs.
F#'s REPL is pretty great as well for these kinds of puzzles. Send Selection lets you highlight up to a certain part midway through a pipeline. This makes debugging without breakpoints very easy, on top of everything else offered by an interactive REPL session!
APL, BQN, and Uiua all make me feel dumb, until you get something working. Suddenly I expect to find my phd in the mail.
Prolog is pretty different from the mainstream.
I would also like to try to be way too fancy about parsing aoc data at some point. That example of a CSV parser in four lines blows my mind. Not really because of the number of lines, but just the whole type system.
I'm doing it in uiua, and I don't expect to last long to be honest.
Lil is a synthesis between ideas from functional languages, array-oriented languages like APL, and relational languages like SQL. For example, it has a first-class database-style "table" type, a query syntax that generalizes across lists, dictionaries, and tables, and arithmetic operators automatically "spread" between scalar and listy values.
Lil is available as a standalone CLI or browser-based interpreter, but it is also distributed as part of Decker, a graphical rapid prototyping environment:
People have mentioned different languages, but I'd say I'd rather try to solve them in a different paradigm. So choose a language that works well for that.
For me, it's functional coding. I find it fun to write as much as possible as filter/map/reduce operations with no mutations. I end up solving problems in a different way than I would in a non-functional language, which I think is good learning.
For me the language of choice is Kotlin, which strictly isn't functional. But it has a good stdlib and syntax for functional coding, so I just restrain myself and use escape hatches when needed. But any functional language would be nice, like Haskell or Clojure etc.
As every year, I stumbled upon the Advent of Code, but this year was a bit different as I found a way to solve the puzzle using our API client.
The other years I got demotivated very quickly as I had to create some I/O functions, copy the files, etc. So I came up with the idea to solve it using Kreya's scripting feature and it was a joy.
Created a blog post [1] as maybe other people feel the same way :)
I've never done AoC before. It seems like the success criteria is primarily about getting the correct answer, and secondarily about submitting a solution as quickly as possible if you want to be on the leaderboard. Is that right?
Is there any centralized place for seeing other people's solutions? I'd like to be able to learn from how others approach the problem, and what more elegant or performant solutions exist than the one I came up with.
A really cool thing about the subreddit is they archive all the megathreads so if you want to do the old advents you can still find some discussion / hints / …
Sadly not the various help or complaint threads, or the mad lads playing up the ante, but…
The the success criteria is whatever you want it to be.
* Learn a new language
* Practice a language you already know
* Try to solve things in a small number of lines
* Try to solve things where the solutions run as fast as possible
* ... any number of other personal goals
* Try to make the leaderboard
I've been solving the older years and learning rust in the process. I made it a secondary goal that all 49 solutions should be able to run in under 1s total. 2015 was easy, 2016 less so.
> secondarily about submitting a solution as quickly as possible if you want to be on the leaderboard. Is that right?
That's probably closer to #10, as it requires being available right as the problem drops (midnight EST and 6AM in europe, IIRC), and generally mid-cycle puzzles require being very good at solving these kinds of puzzles.
submitting as quickly as possible is very much not a success criteria. Each problem becomes available midnight EST so unless you're a competitive weirdo you won't even see the problem until the leaderboard is full.
I decided to give it a go both ways and I found GPT a huge impediment with day one. It did a terrible job and I found it far easier to do myself. I think it's possible to finesse but it'll take more effort than simply "solve this." It didn't help that part two of day one is a fantastic example of a spec causing ambiguity through a lack of detail – I actually wonder if this was deliberate to throw LLM-based approaches off. (Note: There is zero threat of me ever being on the leaderboard as I will never be awake at 5am in December.)
And I wouldn't say day 1 leaderboard is surprisingly fast compared to other years. Time will tell, but I think LLMs will fall apart on hard problems. Typing speed will not be a limiting factor there.
The “learn a new language” is how I used it casually for a handful of years (and it’s great for that).
Last year is the first year I put serious effort into completing all of it (driven by a private leaderboard which made the accomplishments more personally rewarding).
If you’ve got a group of friends/colleagues who could use a little competitive motivation, consider making and joining a private leaderboard (free as in beer).
Most solutions I see are just blobs of code, which makes me wonder what their process looks like.
I like to solve these kinds of problems in Lisp, which means I'm working in a REPL and dividing and conquering the problem to be able to test one piece of the solution at a time.
The result is that my code tends to be mainly independent functions that I finally string together to solve the problem.
Some folks on the subreddit will stream and then post their solutions so you can see their process. I usually enjoy watching Jonathon Paulson solve a problem after I’ve got my solution submitted. He features quite high on the leaderboard each year.
I solved the 2nd part pretty neatly in javascript today... I'm not a great programmer by any stretch but, maybe someone can take a peek and tell me what I can improve? This is my first time with JS-- I dislike the idea of it, but I know I should program in it before I write it off.
A few reasons I like them:
1. The goal is to come up with a workable solution - not to try to fold your brain inside out to optimize them like leetcode. They feel a little more "real-world" (though still firmly in the domain of programming puzzle)
2. There is a community that all solve them at once. At my company, we have a leaderboard and a Slack channel discussing them every day. And then there is the Reddit and everything else that makes it feel more "fun"
3. They are bound (only 1 problem a day). Some days are longer, but I don't get overwhelmed like I do with leetcode where you can lose hours just churning through problems.
IMO, they are a fun community programming puzzle tradition. I would still turn to leetcode for interview practice. But AoC is awesome for me when I don't want to grind leetcode for some interview I don't want right now.
We do something similar at work. We have a Slack channel and a private leaderboard, but we also have prizes for getting a certain number of stars, and also do "challenges" like most unique languages or using an esolang for a day. We also had some non-software engineering people take part and they had fun too. Last year was the first year we did it and it was well received.
At least for me, it's like... infinitely more fun than leetcode. The problems are bite-sized enough that I can usually get something done in less than an hour (although usually there's at least a few in the mix that take a long time to finish). There's a lot of personality in the website and text of the events that add to the fun factor. I like how the problems are broken up into two phases and how the second phase often throws a wrench in my previous solution or forces me to learn some tricky thing to get by.
cute stories, whimiscal ascii art reveal over time, problems of various difficulty, and the cool (to me) idea that many people are working and "struggling" with the same idea/problem over time. I'm also in awe at the work that goes into it. It's like watching a master craftsman to consider Eric making 25 unique puzzles, testing them, crafting many inputs that all work with the same rules, writing hints and stories to go for each puzzle. It boggles the mind.
It's more whimsical. There's a clear end with less pressure and an excited community to discuss with. At least that's what it's like for me (though I do also enjoy leetcode occasionally to be fair)
I wonder if there is a more productive form of it that helps learn/practice difficult technologies in a short amount of time. Say a combo of Ray tracing in a weekend, a game with reinforcement learning etc that helps people learn disparate technologies that they may not be familiar with while staying grounded on practical yet difficult problems.
FWIW AoC is great and anything that keeps the core CS spirit going seems like a good thing!
Advent of Cyber is that for infosec. It covers a broad range of security topics but is designed primarily to teach the basics of each topic rather than to be a test of advanced skills.
When it was done in a private leaderboard in a traditional in-person team working in the same office it was a great watercooler talk topic and code-golf team building topic.
I tried to do it in a remote work team with weaker personal links, and it felt like a chore, so this year I'm not doing it at all. No fun without the in-person code reviews and pair-programming code golfing.
Also many of us tried new languages of paradigms every year.
I find nothing wrong with Leetcode. I've been avoiding it forever, and finally started to practice it 2 months ago. I can say I learned quite a lot. Thus far in carrier I've primarily relied on `List` when it comes to data structures, now I realize how wrong I was.
I'm only into it because I know other people who are into it and it's fun to talk to them about it. It's actually my least favorite kind of programming problem, and the christmas elves conceit is very irritating to me
Day 1 part 2 was harder than is common for the first day.
I ended up using parser combinators (attoparsec for Haskell), which morally feels like the "right" way to do this (so you don't have to manually keep track of how much you've read or somehow abuse regex lookaheads), but I don't know the library well and it took me some time to implement it correctly.
First time trying a code golf solution, managed to do Part 2 in 231 characters.
p="one two three four five six seven eight nine".split();sum(int(x[0]+x[-1])for x in["".join([["",s[0]][s[0].isdigit()],str(p.index(w)+1)][s.startswith(w)]for s in[l[i:]for i in range(len(l))]for w in p)for l in open("input.txt")])
Advice from 7 years of doing (and sometimes completing!) the Advent of Code:
1. Look at the example input.
2. Run your code on the example input.
3. Seriously -- make extra super 100% sure your code works on the example input. Write some boilerplate code to make it easy to switch between your input and the example input.
4. Think about possible edge cases in the input -- there will probably be some. Looking at your input in a text editor can help uncover them.
5. If part 1 is simple, it's just there to test your input processing, and part 2 will be the real puzzle.
6. If part 1 is solvable with brute force, part 2 probably won't be. But sometimes it's helpful to brute-force part 1 just to see what the question is.
7. Many problems that involve the word "shortest" or "fastest" are good candidates for a breadth-first search. Make sure you know how to do that.
8. Test your code as you go. Printing the output of intermediate steps to the console is a great way of catching bugs.
9. There's going to be some hideous puzzle, probably involving a maze, which is too hard for a simple BFS and requires heavy pruning of alternatives. If you know how to do this kind of puzzle, please tell me how; they get me every time. :-(
10. Don't even look at the leaderboard times. Those people are nuts.
> Seriously -- make extra super 100% sure your code works on the example input. Write some boilerplate code to make it easy to switch between your input and the example input.
> Test your code as you go. Printing the output of intermediate steps to the console is a great way of catching bugs.
Honestly, just set up whatever you need to be able to write unit tests in your lang of choice. These problems are _so_ amenable to a piecewise approach driven by tests. I'm not like a big TDD advocate or anything, but these problems are great practice for that style of coding - it's just so damn useful to know each of your small pieces of code work.
Parameterized tests are amazing for AoC, because you can get a handful of test cases basically for free from the puzzle description. If your code doesn't work once you've got all the samples working, you either have some weird edge case that you didn't consider, or you've got one of the brute-force killer puzzles.
Even for today's, I wound up with 43 different test cases. The vast majority of those are from the puzzle text, and adding them didn't really make the puzzle take that much longer. (Obviously, if you're optimizing for solve speed, you probably wouldn't bother with this approach, but I'm not).
Another thing of note is that every puzzle basically operates on a list of strings, so it's pretty easy to genericize certain parts of the work of solving puzzles. I have a script which generates a module for the solution in my repo, with separate functions for each part that receive the input, and a test file that has tests for part 1 and part 2. The tests read the input file and pass it as a list of strings (lines) to the part_1 and part_2 functions, so that all the boilerplate is already done, and I get to just focus on writing the guts of the part_1 and part_2 functions (which usually get broken down into several other functions, which can also be tested individually).
Gosh I'm feeling extra special this morning as an absolute infant beginner tinkerer that figured solution in powershell to part II after a few minutes of closing my eyes, but I highly doubt I'll be able to say that about the next one if they get harder. The example was so excellently written though, which helped a ton.
Sure, but I'm gonna try and finish 2015's challenges first, something always comes up while I'm working on it, it'd be nice to get it all over and done with.
I did 2016 in Haskell and 2018 in Rust. Haskell was kind of a pain since I had to do a ton of tail recursion. Rust would be a lot easier since it allows you to be imperative when you need to.
And I definitely only used a tiny subset of either language because I wanted to get the solution as quickly as possible.
Many people on reddit reporting they were hit by one edge case that's not covered in the examples. But my implementation passed these edge cases too. I was hit by another edge case. So there are at least two edge-cases (which are in the actual data) that aren't covered in the examples or the description.
It was a little frustrating that the main edge case that caught everyone didn't blow up my implementation, and going row by row of the 1000 line input it wasn't immediately obvious where it was going wrong (I'm not sure how far down I would've had to go to find the first time it hits this edge case, I just ended up checking the reddit for hints).
I really do think things like this should at least be hinted in the text to save a little frustration; I'm not trying to be the best on the leaderboard, I'm just doing these in the morning before work for a little fun.
I only found my edge case (and dumb implementation mistake, I guess) by forking a "working solution" from someone else, outputting their solution for each line, then diffing that with a similar output from mine. It took me a lot of debugging and troubleshooting.
Once I diffed it against a working output it was clear and solved within minutes.
Warning: post contains spoilers, HN doesn't support spoiler text so continue reading at your peril.
These edge cases are triggered by fundamentally approaching the problem incorrectly.
In some ways it's excellent to bring that up early in a way that's relatively easy to debug and diagnose.
Like many others I started with the wrong solution, and I was hit by the same problematic cases, but what I found interesting was that some developers went further down a rabbit hole of trying to force replacement to work (e.g. replacing "one" with "one1one", etc) rather than taking a step back and re-thinking the approach entirely and thinking about the problem as a searching problem.
Further spoiler: I replaced "one" with "o1e", "two" with "t2o", etc. which is hacky as hell, but works for throwaway contest code. (Replacing as suggested above also works, but is more typing.)
That let me keep the problem in the filter/map/first-last/reduce space, which was the shape of my solution to part 1.
That’s exactly what I pivoted to once I realized my naive replace wouldn’t work. That sort of moment is what makes AoC feel so rewarding in my opinion.
Here's a snippet of a first attempt, which does not work:
|> Array.map (fun s -> Regex(@"(one|two|three|four|five|six|seven|eight|nine|\d)").Matches(s))
|> Array.map (fun m -> m |> Seq.map (fun g -> g.Value) |> Seq.toList)
And here's the correct code:
|> Array.map (fun s -> Regex(@"(?=(one|two|three|four|five|six|seven|eight|nine|\d))").Matches(s))
|> Array.map (fun m -> m |> Seq.map (fun g -> g.Groups.[1].Value) |> Seq.toList)
There's no "fundamental" difference between the two, rather, one uses a regex with positive lookahead and the other doesn't. The first approach was not operating under the assumption that there would be strings like "oneighth" at the end of a line. That's a detail and it only applies to one part of a functional pipeline!
I agree that one should take a step back at that point but how exactly is this the fundamentally wrong approach to the problem?
Re-using the existing code where possible is the fundamentally right approach to the problem. It just so happens that in this case, there were edge cases that prevented this, so another approach had to be taken.
> Re-using the existing code where possible is the fundamentally right approach to the problem.
Reusing code does not make something "fundamentally right approach". An implementation that actually does what the problem asks is a "fundamentally right approach". If you can reuse existing code in that implementation then that's a bonus.
The problem is very clearly specified, so if you choose to implement something else hoping that it's "close enough" then that's on you...
In my experience they are very much "actual business problems"-alike situations.
There's never been a customer that asked me "I have some elves that need to make snow and here's a trebuchet", sure. But they ask me stuff, I intepret that as well as I can. Go back for questions. Apply DDD, event-storming or whatever if I'm lucky.
But there always is an interpretation issue somewhere, that makes that some "bug" is really "but I spend 5 hours implementing that exception and now you tell me it's a bug?".
Yeah, part two was really something. I got part one in 2:40, and then spent half an hour trying to figure out what the hell was going wrong with part two, lol.
Maybe it was actually done on purpose to foil ChatGPT, because when I get desperate and tried to let GPT4 solve it, it also couldn't figure it out.
I found the problems straightforward to code in Haskell. The first part ran correctly right after I got it to compile. The second initially gave bogus results. Turns out I needed to invert a test and then it ran correctly too.
15 lines of code including 3 imports and 3 type declarations;
1 line to comment out to do the easier problem.
I just created a list of string-value pairs and found first index of and last index of for each of them keeping track of the best first and best last. C# is pretty freaking amazing like that.
My part 2 was 4-line addition to part 1 (see code below, if inappropriate let me know and I'll remove it), and it worked first try. On the other hand, I made a mistake in part one and got it right only on a second attempt...
(definition of nums[] omitted)
for (j = 1; j < 10; j++)
if (!strncmp(&buf[i], nums[j], strlen(nums[j])))
buf[i] = j + '0';
The most obvious edge-case was mentioned by other siblings.
My "edge case" is probably not really even an edge-case though.
SPOILER ALERT ---
My implementation stopped looking when it found a number. So "one2one" or "1twone" and so on, would find the numbers "1,2" and not "1,2,1". There were no examples where a number appeared multiple times in a line AND this affected the first-last pair. So e.g. abc1ninexyz841 would result in 14 in my case but should've been 11.
Again: it's rather implied and quite obvious if you interpret the description as human, but I worked at it from TDD, and the example missed this situation and the actual input had only a relative few of them, so debugging was hard.
Thanks! I thought I had the most straight-forward code there is and there were no edge cases that I hit. But I didn't use regex or something, just manual pattern matching like gp.
Imho regexes are overused for such stuff, precisely because they might do a lot of things you don't think about and are usually a lot slower than manually implementing what you want.
If they have functions that for example reads from forward then backward or vice versa while changing the structure of the row, one test will pass but the other won't. It's a lot of rows in the input and it took a lot of time for me personally to debug to understand what went wrong
The potential for overlapping numbers was the thing that tripped up many developers. But a simple “find the first number searching from each end, just like the puzzle instructions asked” implementation just worked.
The lesson is to read the puzzle instructions carefully and avoid solving more general problems.
I did not use regexes, so as said, the most common edge case did not hit me.
What hit me was stupid, but also not covered in the example. It was rather implied and obvious from the example, though.
SPOILER ALERT
In my mistaken implementation `one2three1` would find "1, 2, 3" but not the second case of 1. Now, while the description never explicitly mentioned this, it's still obvious that it should be "11" and not `13`. Though my example, derived by TDD-ing from the example, gave `11`.
Only after I diffed my output with that of a known working solution did I find a few lines (there were several of them, though not that much) that made my issue clear: I missed the second case of a number appearing. So "one1one1one" in my solution would only find the first one.
The real world is ugly and full of edge-cases and noise and ever-changing-requirements.
So encoding that, and keeping a solution elegant and "beautiful" is what I strive for.
Finding elegance in mathematically pure setups, is, I guess, very rewarding too for many. But not for me. I find pleasure in abstractions, algorithms and architecture that embraces the ugliness and inconsistency of "The Real World" to make it workable (over decades). I hardly ever manage in this though. Most code somehow still ends up in deeply nested if-elses-foreaches and whatnots.
For part 2 there is an elegant and very simple solution that doesn't use regex and doesn't need to work around edge cases... you just have to find it ;)
It's really the worst time of the year for something like this. I hardly remember a time when I wasn't completely swamped with tasks before Christmas. A summer puzzle would be much more doable...
The puzzles are up year round. You can go back and do prior year puzzles any time. There just won't be any of the community from doing it during the event.
The real problem for me is that once the last few days of the puzzle roll around, I'm too busy running around to different Christmas events to have time to squeeze them in.
I completed it in 2020 and felt extremely accomplished. I doubt I'll get through all of them this year before losing interest, got too many other projects going, but I always have fun with them.
Shameless Plug: If anybody is doing Advent of Code and wants to win tickets to the 2024 Carolina Code Conference (Greenville, SC in August) we're doing a ticket challenge. 22 tickets up for grabs with lots of ways to win. Entry details here.
I suspect they tested their problems against ChatGPT while working on them.
ChatGPT doesn’t magically solve everything. There are a lot of cases where it will choke or lead people astray. If I was building a challenge like this in 2023 I’d test the problems against ChatGPT and put the ones where ChatGPT fails at the beginning to weed out the ChatGPT players.
I am looking at advent of code for years but never tried.
Why? As they would like to force you to login with GitHub, Google, Twitter or Reddit account.
I will wait for the next year, maybe 2024 Advent of Code will be less intrusive.
If not... I can live without it.
A hint to the authors for simple load/save, far simpler than what you have now, without use of intrusive 3rd party providers:
use Digest::SHA qw(hmac_sha256_hex);
$digest=hmac_sha256_hex("levelX:true,...", $key);
(And no, I wont workaround them. This is why we got into such situation - as we were still using intrusive services instead boycotting them, it is matter of principle not of technical workaround)
What is your problem with that? They don't request any unreasonable personal information/permissions, if I recall correctly they only use minimal info only: the unique user identifier (email address), and name.
They don't need to work with transactional emails, password resets, etc. Lots of failure modes and corner cases to support, for a minority. Lot of work and inconveniences saved for a free project that surely takes some effort to organize every year.
Not saying I agree with the login requirement, but ... why not just create a throwaway account just for this purpose? This seems like a silly reason to miss out on something you might enjoy.
I logged in with my Reddit account in a previous edition. This year I deleted my Reddit account in protest. Therefore, goodbye AoC history.
It put a stark ~~contrast~~ focus on why I don't use those signups options: because the two times I've used it it came back to bite me (the other one being when Google blocked my account for months).
I deleted my Reddit account because I don't want to support Reddit any longer, so I lose access to anything I used "Sign in with Reddit" for - it's subtle lock in that tends to only hit issues months later.
It's why I never use social media logins for anything that gives me the choice not to.
> Why? As they would like to force you to login with GitHub, Google, Twitter or Reddit account.
So take 30 seconds to create a throwaway Reddit account with a throwaway 10 minute email account and use that?
I guarantee you’ll be spending 100X more time on the problems than you would in creating a throwaway login if that’s your concern.
Using 3rd party login providers is just a simple way to run a website without having to build, run, and maintain your own user accounts and login system. You can see that the permissions they ask from GitHub are minimal.
I agree that using an auth provider is unnecessary for the problem faced. A bit ironic considering how AoC is all about programming challenges. Funny seeing the problem solved in 4 lines of Perl.
If there were a trustworthy auth provider it wouldn't be as bad, but I don't really know of any... maybe something in the Fediverse?
I would hardly call it intrusive. The premise of the game involves tracking stats over days and years, so they need a login system. Using external trusted identity providers is a lot safer for their users than if they tried to implement their own login system.
