Advent of Code 2023 is nigh(adventofcode.com) |
Advent of Code 2023 is nigh(adventofcode.com) |
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")])Have Fun!
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).
https://github.com/epiccoleman/advent_of_code_ex/blob/master...
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).
https://github.com/emiruz/adventofcode2023/blob/main/day01/p...
Or should I take the plunge and do it in rust?
(If only I was unemployed and could do this in agda/idris/lean…)
And I definitely only used a tiny subset of either language because I wanted to get the solution as quickly as possible.
[1] https://github.com/xdavidliu/advent-of-code/tree/main/2016 [2] https://github.com/xdavidliu/advent-of-code/tree/main/2018
was so strange to see absolutely empty page until I thought of scrolling down
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.
One year I'll actually finish!
https://blog.carolina.codes/p/advent-of-carolina-code-ticket...
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.
> Consider your entire calibration document. What is the sum of all of the calibration values?
Where is the document? Where do I download it?
> To play, please identify yourself via one of these services:
Ok got it.
Turns out I am too stupid.
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)
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.
|> 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)
|> 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)
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.
That's a bit like you are holding the phone wrong kind of statement. These are just coding exercises, not actual business problems.
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'm guessing you're talking about something more C#-specific like LINQ?
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'; var bestFirstValue = possibleValues
.Where(x => currentLine.IndexOf(x.searchString) != -1)
.OrderBy(x => currentLine.IndexOf(x.searchString))
.First()
.intValue;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.
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.
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.
https://github.com/williamcotton/fs_playground/blob/ffbc57ac...
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.
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.
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.
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.
Anyway, don’t hold your breath.
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.
I admire the ability to brute force problems using the most convenient features available as much as anyone, especially professionally.
But to me, this is about evolving as a programmer; I do enough duct taping at work.
impl fully showing the trick: https://github.com/rileymichael/aoc-2023/blob/master/src/mai...
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?".
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.
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?
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.
cat 1.txt | sed -E 's/(one)/\11\1/g; s/(two)/\12\1/g; s/(three)/\13\1/g; s/(four)/\14\1/g; s/(five)/\15\1/g; s/(six)/\16\1/g; s/(seven)/\17\1/g; s/(eight)/\18\1/g; s/(nine)/\19\1/g;' | sed -e 's/[^0-9]//g' | awk '{print substr($0,1,1) substr($0,length,1)}' | tr '\n' '+' | sed 's/\(.*\)+/\1\n/' | bcIs bash required.
For example, this also works in dash, NetBSD sh, pdksh, tcsh, etc.
I hope it doesn't scare off newcomers, but I already know a few who have given up on part 2.
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.
(?=(one|two|three|[...]))
No hate on AOC though, I really respect all the hard work that goes into it.
> 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.
100% with you on this. Last year was the first year I'd had time to complete it, and I always love the challenge.
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.
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!
However the 'naive' solution still feels quite nice. Some python, at the risk of sharing spoilers:
fixes = { "seven":"7", "two":"2", "one":"1", "nine":"9", "eight":"8", "three":"3", "four":"4", "five":"5", "six":"6" }
cands = set(fixes.keys()) | set(fixes.values())
total = 0
for line in Path("input/1.txt").read_text().splitlines():
matches = list(filter(lambda k: k in line, cands))
first, *_ = sorted(matches, key=line.index)
*_, last = sorted(matches, key=line.rindex)
total += int(fixes.get(first, first) + fixes.get(last, last))
print(total)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.
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.
[1] https://git.sr.ht/~bsprague/advent-of-code/tree/main/item/20...
Once I get a line back from that, it's the same problem as part A.
https://github.com/xdavidliu/advent-of-code/blob/main/2023/d...
Not elegant but still do the job.
two1nine eightwothree abcone2threexyz xtwone3four 4nineeightseven2 zoneight234 7pqrstsixteen eighthree sevenine oneight xtwone3four three7one7 eightwothree oooneeone eight7eight
https://github.com/codr7/swift-interpreter/blob/main/part10/...
https://gist.github.com/joedavis/3d6f2b87bae4809ef8a062caff7...
C++'s .rbegin() / .rend() reverse iterators made the search fairly trivial.
Oh so THAT is what is causing people problems.
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.
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.
https://github.com/drola/AdventOfCode2023/blob/main/src/bin/...
https://github.com/woile/adventofcode/blob/main/2023/day1/sr...
It's quite clear the small sample data was chosen intentionally to not cover them.
"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.
I wonder how long the global leaderboard will stay up before it gets hidden due to people solving with ChatGPT?
I'm using this year's to dust off my Rust skills in advance of a new job using that language, so that's nice too.
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 :)
Advent of chore ? :)
..though I agree - never went past 10th day or so.
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.
[1] https://github.com/mikewarot/Advent_of_Code_in_Pascal
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).
He's done it with R, Julia, Rust and this year Kotlin.
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 could never do it in one of my work languages.
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
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.
[1] https://kreya.app/blog/solving-advent-of-code-with-kreya/
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.
* 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
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 still prefer to do it manually since casually tackling it is a great way to learn a new language or refresh past knowledge!
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.
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).
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.
Most often I end up with some enormous one-liner that I then break down into functions again.
Hope it's just a temporary issue!
failed to authenticate. (access_token request returned 429 Too Many Requests)
I used Rust and match_indices to get the answer.
https://github.com/deafpolygon/advent-of-code/blob/main/2023...
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.
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!
> match(es) multiple, possibly overlapping, regexes in a single search.
"necessary" is a strong word. :-)
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.
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.
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.
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.
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.
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
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.
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.
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:
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.
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!
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!
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.
My solution in Kotlin https://github.com/kolonialno/adventofcode/commit/686cbebb07...
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.
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.
After I pulled out first and last from results array.
Two nested for loops, program all included was under twenty lines.
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.
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.
first = line.match( /(?:(0|zero)|(1|one) ... (9|nine))/)
last = line.match(/.*(?:(0|zero)|(1|one) ... (9|nine))/)
indexOfGroupMatched =
([_, ...groups]) => groups.findIndex(x => x != undefined)
num = +[first, last].map(indexOfGroupMatched).join('')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...
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...
pbpaste | bash -c '
tt=0
while read x; do
y=$(( 10 *
$(echo $x |
egrep -o "[0-9]|one|two|three|four|five|six|seven|eight|nine" |
head -1 |
sed -E "s/one/1/; s/two/2/; s/three/3/; s/four/4/; s/five/5/; s/six/6/; s/seven/7/; s/eight/8/; s/nine/9/")
+ $(echo $x |
rev |
egrep -o "[0-9]|eno|owt|eerht|ruof|evif|xis|neves|thgie|enin" |
head -1 |
rev |
sed -E "s/one/1/; s/two/2/; s/three/3/; s/four/4/; s/five/5/; s/six/6/; s/seven/7/; s/eight/8/; s/nine/9/")))
tt=$((tt+y))
done
echo $tt'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
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
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
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...
one -> eno
two -> owt
three -> eerht
etc
It makes the entire solution extremely simple, though a little verbose.
You don't need to be all things to all people. Embrace the fact that there are other choices!
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.
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)
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.
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