Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Advent of Code 2023 is nigh

adventofcode.com

Post reply on HN
Print view View original

251–260 of 319 posts

Re: Advent of Code 2023 is nigh

#251

Post by williamcotton »

epiccoleman wrote: post #155
wry_discontent wrote: post #87

Earlier quoted context omitted.

I especially enjoy using Clojure for these puzzles since the REPL makes interactively checking your ideas fast.

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!

Re: Advent of Code 2023 is nigh

#252

Post by berkes »

sebtron wrote: post #65
berkes wrote: post #24

Part two was exceptionally hard. 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.

Ok, I'll be that guy... what edge case? 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

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.

Re: Advent of Code 2023 is nigh

#253

Post by berkes »

zerr wrote: post #27
berkes wrote: post #24

Part two was exceptionally hard. 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.

Generally, such edge-cases usually make the solution ugly and the process unpleasant. The aim of such puzzles should be a pleasant process culminating with a beautiful solution.

I'm rather on the opposite end.

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.

Re: Advent of Code 2023 is nigh

#254

Post by DylanDmitri »

masklinn wrote: post #213
WJW wrote: post #179

Earlier quoted context omitted.

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 t…

> knowledge about `isPrefixOf` or `startsWith` or whatever the equivalent function is called in your language of choice. 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.

I looked at the slices from each position to the end. Now for every name (“one”, “1”, “two”, …) check slice.startswith(name).

After I pulled out first and last from results array.

Two nested for loops, program all included was under twenty lines.

Re: Advent of Code 2023 is nigh

#255

Post by masklinn »

dgacmu wrote: post #247
masklinn wrote: post #209

Earlier quoted context omitted.

I would assume you can also use RegexSet from the regex crate, as it > match(es) multiple, possibly overlapping, regexes in a single search.

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…

> 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.

Re: Advent of Code 2023 is nigh

#256

Post by 0x264 »

kif wrote: post #141

I don't know if I'll even bother this year. Their puzzles start feeling like chores by the 10th problem or so and I drop out. Maybe I'll learn a new language to spice it up this year.

> like chores by the 10th problem or so and I drop out

That they get so involved is the reason I participate (despite also working at the same time). I love the fact that the difficulty starts low and then goes up to levels where I feel really challenged. It's a month (well, 25 days) commitment which pays off the entire 11 other months for me :)

Re: Advent of Code 2023 is nigh

#257

Post by midwestcode »

frankjr wrote: post #157
shever73 wrote: post #92

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.

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

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!

Re: Advent of Code 2023 is nigh

#258

Post by uxp8u61q »

fsociety wrote: post #144
j1elo wrote: post #127

Earlier quoted context omitted.

> 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 me…

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.

You need to put a time limit on your regex execution no matter what, if you're parsing untrusted input.

Re: Advent of Code 2023 is nigh

#259

Post by kemyke »

bauble wrote: post #147
bradley13 wrote: post #99

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".

But a simple replace if you do it like this .Replace("one", "on1e") or .Replace("eight", "eig8ht")

Not elegant but still do the job.

Re: Advent of Code 2023 is nigh

#260

Post by dgacmu »

masklinn wrote: post #255
dgacmu wrote: post #247

Earlier quoted context omitted.

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…

> 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 a…

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:

https://github.com/dave-andersen/advent2023/blob/main/src/ma...

Post reply on HN