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).
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.
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.)
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.
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.
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.
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.
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.
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.
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.
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 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)
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 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.
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.
> 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 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.
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 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.
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.
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.
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 ;)
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.
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.
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.
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?".
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!
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';
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 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.
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.
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?
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!
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!
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:
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.
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.
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 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.
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.
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 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.
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.
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.
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'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…
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.
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.
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)
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.
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.
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.
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 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.
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.
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 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!
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.
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!
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
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, 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.
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)
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!
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:
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.
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.
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.
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.
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 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.
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.
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
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.
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().
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
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!
> 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.
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).
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.
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.
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.
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.
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.
> 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.
318 comments
[ 4.6 ms ] story [ 268 ms ] threadI still prefer to do it manually since casually tackling it is a great way to learn a new language or refresh past knowledge!
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).
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.
I wonder how long the global leaderboard will stay up before it gets hidden due to people solving with ChatGPT?
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.
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.
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.
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'm interested in how well it goes this year.
Please reply if you are trying yourself or can link to public attempts by others
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.
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.
If you're interested: https://epiccoleman.com/posts/2022-12-03-chatgpt-aoc
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)
Anyway, don’t hold your breath.
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.
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.
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.
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've been looking for some nice Perl solutions, I imagine it's pretty much the optimal language for many of these problems.
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.
[0] https://hanukkah.bluebird.sh/about/
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.
The aim of such puzzles should be a pleasant process culminating with a beautiful solution.
The lesson is to read the puzzle instructions carefully and avoid solving more general problems.
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.
https://github.com/williamcotton/fs_playground/blob/ffbc57ac...
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.
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 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.
Once I diffed it against a working output it was clear and solved within minutes.
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.
That let me keep the problem in the filter/map/first-last/reduce space, which was the shape of my solution to part 1.
impl fully showing the trick: https://github.com/rileymichael/aoc-2023/blob/master/src/mai...
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.
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...
I mean, who said you had to use a regex to begin with?
That's a bit like you are holding the phone wrong kind of statement. These are just coding exercises, not actual business problems.
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?".
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...
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.
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.
I'm guessing you're talking about something more C#-specific like LINQ?
https://github.com/Sixstring982/tanenbaum
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.
This year my initial desire is to do it in raku, which seems suited to the first task at least (although I haven't managed to get to it).
I did another year in common lisp.
All in all I really can recommend doing them in non-typical languages, it expands your mind.
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.
If you're interested: https://github.com/epiccoleman/advent_of_code_ex
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.
You can go for one query solution or use views/tables for multiple steps.
It's an acquired taste for sure, but I kinda like it!
https://beyondloom.com/tools/trylil.html
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:
https://beyondloom.com/decker/index.html
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.
https://github.com/fspoettel/advent-of-code-rust
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.
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.
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).
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.
He's done it with R, Julia, Rust and this year Kotlin.
I could never do it in one of my work languages.
One year I'll actually finish!
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.
was so strange to see absolutely empty page until I thought of scrolling down
https://blog.carolina.codes/p/advent-of-carolina-code-ticket...
Looking forward to read your write-ups!
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.
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.
Usually each day there is a mega thread with people sharing their solutions
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.
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.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.
Last year, betaveros topped the leaderboards with a bespoke language they designed for the task (https://github.com/betaveros/noulith).
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.
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.
FWIW AoC is great and anything that keeps the core CS spirit going seems like a good thing!
fancy-regex is built on top of the regex crate and supports look-around.
The regex crate doesn't support arbitrary look-around because it isn't known how to implement efficiently.
See: https://swtch.com/~rsc/regexp/regexp1.html
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!
One of the key advantages of a regex engine based on finite automata is that it lets you make guarantees about the runtime performance of a search.
You don't need to be all things to all people. Embrace the fact that there are other choices!
> match(es) multiple, possibly overlapping, regexes in a single search.
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, ...].
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.
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:
https://github.com/dave-andersen/advent2023/blob/main/src/ma...
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.
[1]: https://docs.rs/regex-automata/latest/regex_automata/meta/in...
[2]: https://docs.rs/regex-automata/latest/regex_automata/meta/st...
[3]: https://github.com/rust-lang/regex/blob/837fd85e79fac2a4ea64...
"necessary" is a strong word. :-)
I hope it doesn't scare off newcomers, but I already know a few who have given up on part 2.
No hate on AOC though, I really respect all the hard work that goes into it.
one -> eno
two -> owt
three -> eerht
etc
It makes the entire solution extremely simple, though a little verbose.
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.
Mine is. But that's because I don't bother DRYing it and making it more clever (yanking and pasting is faster than thinking)
100% with you on this. Last year was the first year I'd had time to complete it, and I always love the challenge.
> 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.
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
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.
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.
[0] https://www.regular-expressions.info/lookaround.html
https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
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.
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...
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 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.
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.
https://mutraction.dev/link/c3
However the 'naive' solution still feels quite nice. Some python, at the risk of sharing spoilers:
Not elegant but still do the job.
https://github.com/xdavidliu/advent-of-code/blob/main/2023/d...
It's quite clear the small sample data was chosen intentionally to not cover them.
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.
"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.
There's no guarantee the digits are the first or last, so it's more `find` and `rfind`, unless you try every subslice of the line by hand.
Although thinking about it assuming the lines are not too long I guess that also works.
After I pulled out first and last from results array.
Two nested for loops, program all included was under twenty lines.
I wonder if it is because of ChatGPT and friends.
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.
Hope it's just a temporary issue!
failed to authenticate. (access_token request returned 429 Too Many Requests)