|
Cybernetic Vermin posted:pretty sure a fast language would do b brute-force pretty easy. my crude python it would have been a couple of hours. My solution must be kinda poo poo. It'd have taken months.
|
#
?
Dec 15, 2023 00:36
|
|
|
|
| # ? May 3, 2024 03:13 |
|
|
Hmm, day 15 is another surprisingly straightforward one. I'm going to redo it tomorrow in a more FP/immutable style, but the procedural array and mutable object method was so dead simple.
|
|
#
?
Dec 15, 2023 07:28
|
|
|
No difficult math.. just parse and massage data... The 15A solution was quite nice: Rust code:
|
|
#
?
Dec 15, 2023 11:29
|
|
|
Peewi posted:My solution must be kinda poo poo. It'd have taken months. seeing how this seems the prevailing reaction i might have measured incorrectly (rough progress count to get an idea of where i was, but could have been wrong). otoh my field manipulation is pretty pure numpy, so perhaps my assessment of "crude python" is wrong and it is actually pretty close to optimal already. by accident in that case.
|
|
#
?
Dec 15, 2023 13:38
|
|
|
Cybernetic Vermin posted:seeing how this seems the prevailing reaction i might have measured incorrectly (rough progress count to get an idea of where i was, but could have been wrong). otoh my field manipulation is pretty pure numpy, so perhaps my assessment of "crude python" is wrong and it is actually pretty close to optimal already. by accident in that case. even if you assume one cpu instruction per ball movement, that's still going to be in the several minutes range to do every ball in the grid a billion times each. and you're probably not accomplishing it in one cpu instruction per ball movement unless you've been really incredibly clever.
|
|
#
?
Dec 15, 2023 13:48
|
|
|
Jabor posted:even if you assume one cpu instruction per ball movement, that's still going to be in the several minutes range to do every ball in the grid a billion times each. with my estimate being in the a-bunch-of-hours range i do still have quite a few instructions per rock touch, but, yeah, as noted i no longer find that estimate that plausible. not so far away that it can be obviously rejected out of hand for something very carefully tuned, but it seems optimistic. Cybernetic Vermin fucked around with this message at 14:04 on Dec 15, 2023 |
|
#
?
Dec 15, 2023 13:58
|
|
|
the description for day 15 part 2 is way more involved than the solution. i just used a hashmap of label => (timestamp that increases when i add a new entry, focal length) then dumped it into a vector at the end and sorted by (box index of label, timestamp) and if you had a hashmap that preserved insertion order (like python dictionaries now i think), you wouldn't even need the timestamp
Lime fucked around with this message at 14:59 on Dec 15, 2023 |
|
#
?
Dec 15, 2023 14:56
|
|
|
15b was mostly a bit tedious, interestingly i assumed the test case would punish doing an extra O(n) just rebuilding arrays each time a delete happens (but coded it up that way anyway to just sanity-check my reading), but turns out the input is much too tiny so you're in fractions of seconds no matter how badly you abuse data structures
|
|
#
?
Dec 15, 2023 15:13
|
|
|
Cybernetic Vermin posted:15b was mostly a bit tedious, interestingly i assumed the test case would punish doing an extra O(n) just rebuilding arrays each time a delete happens (but coded it up that way anyway to just sanity-check my reading), but turns out the input is much too tiny so you're in fractions of seconds no matter how badly you abuse data structures Yeah they'd probably have to have a ton of huge inputs to punish not using a linked list like uh google tells me real hashmaps do chaining, also kind of disappointed I got away with this.
|
|
#
?
Dec 15, 2023 15:44
|
|
|
Lime posted:the description for day 15 part 2 is way more involved than the solution. i just used a hashmap of label => (timestamp that increases when i add a new entry, focal length) then dumped it into a vector at the end and sorted by (box index of label, timestamp) and if you had a hashmap that preserved insertion order (like python dictionaries now i think), you wouldn't even need the timestamp With rust I used a vector with Lens structs (fl, label, deleted), I marked the "removed" entries as deleted: true and skipped them while counting score.. it had some extra iteration but since one box didn't hold that many Lenses, it was not a problem really. So I ended up only adding data to data structures, not deleting anything. I wish Rust would some day add the experimental LinkedList features like "remove" to stable. I can't be arsed to implement my own LinkedList, and the existing one is not very good. Maybe LinkedLists should just not ever be used so they want to people to dissuade from using them by providing a lacking implementation. Ihmemies fucked around with this message at 18:03 on Dec 15, 2023 |
|
#
?
Dec 15, 2023 17:58
|
|
|
Ihmemies posted:With rust I used a vector with Lens structs (fl, label, deleted), I marked the "removed" entries as deleted: true and skipped them while counting score.. The removed field is interesting, I didn't do that but otherwise was pretty similar. I'm pretty new to Rust, but if you chain a filter and a map, does the compiler reduce it to a single pass? I guess you'd have to enumerate the input to the map though, so maybe you have to materialize the filter first
|
|
#
?
Dec 15, 2023 21:54
|
|
|
I just got a bit stuck with selecting a good data structure so it was “a solution”, probably not a very good one. I really don’t know enough about rust’s performance aspects yet either, so I can’t commment on the filter/map..
|
|
#
?
Dec 15, 2023 22:05
|
|
|
If you're using a vec for each box, you need to iterate the vec to find the entry that you're supposed to delete. So using a linked list doesn't really help - on average you might halve the number of steps involved in finding + removing the target element, but that's more than outweighed by the fact that stepping through a linked list is more than twice as expensive as stepping through an array. (And you have to pay the stepping cost on inserts too, when you're checking if there's already a lens with that label in the box). If these boxes became truly enormous then you'd want something akin to Java's LinkedHashSet (which you can look up by hash, but iterate based on insertion order) - which afaik doesn't exist in core rust but you might find a crate for.
|
|
#
?
Dec 16, 2023 00:39
|
|
|
Another relatively straightforward part 1 and a not as crazy as it could have been part 2. And now my calendar is on fire! 
|
|
#
?
Dec 16, 2023 07:37
|
|
|
16B was really easy luckily. I used the exact same get_energized() algorithm as in part A, I just called it again for each starting coordinate and printed the highest result. Now Im wondering if there are better solutions, that one took ~700ms with rust.
|
|
#
?
Dec 16, 2023 14:46
|
|
|
Ihmemies posted:16B was really easy luckily. I used the exact same get_energized() algorithm as in part A, I just called it again for each starting coordinate and printed the highest result. pretty much every comment I see on the subreddit is "brute forced p2 but I bet there's a better solution" so I am thinking there probably isn't a better solution
|
|
#
?
Dec 16, 2023 18:43
|
|
|
I read spoilers and someone said that you can save the squares where light exits the map, and not run those simulations.. I have yet to test that out, but I think it makes sense.
|
|
#
?
Dec 16, 2023 19:53
|
|
|
Ihmemies posted:I read spoilers and someone said that you can save the squares where light exits the map, and not run those simulations.. that's pretty smart, i tried it on my solution and it dropped from 38ms to 25ms. out of the 440 edge cells, 199 had beams escape by the end, and 184 of those happened early enough to let it skip a whole simulator run
|
|
#
?
Dec 16, 2023 20:37
|
|
|
Part 2 was actually slow for me in Rust (relatively speaking) with a handful of seconds to run in total. I think a big part of it is that I didn't find lengths that illuminate, I only stepped a single space at a time. Could've cut down on number of iterations dramatically if I solved from bounce to bounce instead
|
|
#
?
Dec 16, 2023 20:45
|
|
|
I asumme you did not compile rust with —release switch. It drops execution time to 1/10th. I did the same though, iterated over the array one square at a time. Could probably save just the non-empty coordinates and do some kind of lookups on what’s next in line. No idea really, but the empty space is not relevant to the result, so in theory you could just calculate how many empty space you travelled with coordinate calculations.
|
|
#
?
Dec 16, 2023 20:52
|
|
|
I guess I have a gimmick now: I'd never have thought of that optimization for part 2, I guess my part 1 was fast enough in python.  looks like it takes about 1.2 seconds total. Do you stop following a ray when it runs into a square that already had a ray go in the same direction? I assumed that's basically required, and I don't think I do anything clever otherwise.vvvvv No I think you're right, but I guess you could do something like exit if we haven't visited a new square in 1000 iterations or something. Vanadium fucked around with this message at 23:33 on Dec 16, 2023 |
|
#
?
Dec 16, 2023 22:38
|
|
|
Vanadium posted:Do you stop following a ray when it runs into a square that already had a ray go in the same direction? I assumed that's basically required, and I don't think I do anything clever otherwise. i kind of assumed failing to do so would cause an endless cycle on most inputs, e.g. something like this in there ..-..\ ..\../ but aoc has actually been rather unusually friendly this year, so perhaps the inputs at least don't go out of their way to cause that.
|
|
#
?
Dec 16, 2023 23:16
|
|
|
woof, our good buddy Path Optimization has shown up on day 17. My answer is a REALLY ugly djikstra where there are four copies of every point. Each copy is essentially just the one point from a single direction. I guess put in graphy terms, the nodes are defined as "POINT + DIRECTION" and the edges out all point to the legal endpoints. So for example in part 1, (1,1)+Right would have edges to (1,0)+Up, (1,2)+Down, (1,3)+Down, (1,4)+Down. Each edge would have a weight of the sum of the heat loss to that point in the original diagram. Off by 1 errors added like an hour of work. MrQueasy fucked around with this message at 08:36 on Dec 17, 2023 |
|
#
?
Dec 17, 2023 08:32
|
|
|
I have been massaging the 17A for some time, and while at it, I forgot the drat turn restriction.code: I remember day 10 being horrible spaghetti, hmm, coincidentally it was exactly last week's sunday...
|
|
#
?
Dec 17, 2023 18:58
|
|
|
I was stuck on this for a while lol I pretty much copied this A* thing I remembered people making Zelda clones talking about 20 years ago from the wikipedia page, each unique (x, y, direction, steps already taken in this direction) being a separate node, and edges existing in directions where the step restriction is met. However it ran slow as poo poo because I didn't understand how I'd maintain a min-heap ordered by the their f-score thing when I thought the f-score for a given node could change as we discover better paths to it, so I just used a list and sorted it each iteration, and later a set and scanned the whole set each iteration. That was just barely fast enough for part 1, but for part 2 I was hosed and wasted a lot of time trying to cut out redundant work in stupid ways that didn't really make sense. In the end I figured I'd maintain a heap AND a set AND another set to track stuff I'd like to have removed from the heap but couldn't because I don't know how to do that with heaps, but it turned out that didn't matter at all and it would have worked just fine if I'd stuck to the original thing. and looking at my cool animation I think I should just have used a regular dijkstra in the first place.  Also I pre-emptively tried to avoid an off-by-one error adding up all the costs, but then I got the wrong result, so I put back the off-by-one error and then it was right but I still don't understand why.
Vanadium fucked around with this message at 19:21 on Dec 17, 2023 |
|
#
?
Dec 17, 2023 19:11
|
|
|
genuinely enjoyed this one, easily the hardest so far this year i think, and i hosed up for a little bit, but i think it's a well-stated problem without really tedious aspects. i'd argue in favor of just making it the graph with nodes ((position_x, position_y), (last_step_dx, last_step_dy, num_consecutive_steps_in_that_dir)), it is then not too much hassle (though i did gently caress up a couple of times) to compute neighbors for that to do a normal dijkstra's
|
|
#
?
Dec 17, 2023 19:16
|
|
|
I vaguely remembered getting super lost the last time I tried to do a for-real dijkstra instead of just yoloing a floodfill or something, so I figured I'd have to look something up either way, but, yeah, looking at other people's solutions now, that wasn't the right call  (Edit: Mine definitely runs a lot slower than those other python solutions too.) Vanadium fucked around with this message at 19:34 on Dec 17, 2023 |
|
#
?
Dec 17, 2023 19:30
|
|
|
Cybernetic Vermin posted:i kind of assumed failing to do so would cause an endless cycle on most inputs, e.g. something like this in there I got an infinite loop initially, and avoided it by keeping track of what splitters I had already used and only using each once. I was really expecting part 2 to make me hit a part like code:
|
|
#
?
Dec 17, 2023 19:47
|
|
|
Peewi posted:I got an infinite loop initially, and avoided it by keeping track of what splitters I had already used and only using each once. ah, that's a nice nefarious widget they for sure should have added!
|
|
#
?
Dec 17, 2023 19:49
|
|
|
for 17 i had my nodes be (position, direction), and when it processed a node it adds to the checklist three nodes in each of the two directions orthogonal to the previous direction, so if it were going to the right it would check (x,y+1) (x,y-1), (x,y+2) etc. to (x,y-3) it was not fast but it does work
|
|
#
?
Dec 17, 2023 22:10
|
|
|
Day 17, Spent like an hour and a half trying to be clever about today. I really wanted to do something like Project Euler 67 where you just work from the end backwards, choosing the best option at every step That was intractable, so when I saw someone mention Dinkstra (didnt mean for that typo but I'm leaving it) I coded that up and got it immediately. Part 2 was failing for no discernible reason, except I realized I needed to seed my min-heap with the two possible starting moves because of how the minimum-move requirement was implemented Also the extra test case for part 2 was really important, I didn't understand that you had to reach the end at a valid stopping time at first
|
|
#
?
Dec 17, 2023 22:17
|
|
|
Its a Rolex posted:
it also implies (but does not state) that you’re also not allowed to make a move that would slam you into an outer wall
|
|
#
?
Dec 17, 2023 22:54
|
|
|
Its a Rolex posted:Also the extra test case for part 2 was really important, I didn't understand that you had to reach the end at a valid stopping time at first Huh, this didn't come up in my test data apparently.
|
|
#
?
Dec 17, 2023 23:06
|
|
|
how do you learn to get good at this stuff? I’m a decent dev when it comes to business stuff but anything more algorithm based I feel like an idiot.
|
|
#
?
Dec 17, 2023 23:28
|
|
|
Surprise T Rex posted:how do you learn to get good at this stuff? I’m a decent dev when it comes to business stuff but anything more algorithm based I feel like an idiot. it is mostly a matter of practice. it is a lot less about knowing a billion different data structures and algorithms than is sometimes implied, rather a pretty heavy focus on modelling the problem coupled with a handful of techniques (memoization under various different names, a couple of flavors of search, a sense for how to do a good exhaustive enumeration, and the art of googling the occasional stray mathematics fact). depends a bit on what you mean by "this stuff" as well of course, but i teach a course pretty squarely in this area and that's my pitch for that anyway.
|
|
#
?
Dec 17, 2023 23:41
|
|
|
A lot of us spent months in a "data structures and algorithms" university course having ways of thinking about this sort of problem being etched into our brains through repetition. For the self-taught programmer, I think you've got to have some focused practice over time that covers similar ground. You can't learn it all in a weekend and expect to remember it when it's later useful - spaced repetition is key for actually retaining and being able to apply that knowledge.
|
|
#
?
Dec 17, 2023 23:52
|
|
|
To add on, there's a few "classic" algorithms that these problems like to play with. The big ones: (yes, I'm repeating what others have said) common: - memoization of recursive functions (the canonical learning example is fibbonaci) - DFS/tree construction and traversal - BFS/shortest path and their pruning - least common multiple - hash maps - priority queues - flood fill/disjoint subsets Less common but fun to learn about: - the mathematical properties of iterative sequences. (e.g. the sum of 1..n is n*(n+1)*0.5, the sum of 1^2, 2^2 .. n^2 is (1/6)*n*(n+1)*(2n+1) ) as well as being able to identify them - modulo arithmetic and the existence of reverse modulo arithmetic - converting assembly language to higher level language constructs - obscure math puzzles (the Josephus problem) - cryptography concepts My general tips: - Learn to be able to identify what big O something you wrote is. N^2 is usually the upper limit of what can be accomplished in a couple minutes. - Learn to enjoy the joy of solving puzzles in general. Sudoku, nonogram, crosswords, etc. The more comfortable you are at thinking about things for fun that have no real benefit other than the solve, the more comfortable you will be sitting down and solving problems. - Watch a lot of numberphile and 3blue1brown and mathologer - Don't get down about not knowing the solution. If I can't solve it in 24 hours, I have no shame looking at hints and other people's solutions to learn new approaches. Especially in languages other than the one you're solving in, as IMO learning how other languages handle things is valuable in general. - Learn a functional focused language like lisp, haskell, or ocaml or whatever. Being able to think in terms of recursion is more valuable than it appears. - Search wikipedia for things like "shortest path" and such. They have pseudocode examples of a LOT of algorithms. - Don't be ashamed about brute forcing a solution! - Don't get competitive. There's literally nothing to gain by being "fast" other than smug self-satisfaction. (Which while a good feeling usually means you finished the fun part, which is learning cool tricks) - Talk about things with friends. Make them explain how they solved something. - (if you're a masochist) read Cnuth's algorithm books.
|
|
#
?
Dec 18, 2023 00:31
|
|
|
Jabor posted:Huh, this didn't come up in my test data apparently. The example they give with a bunch of 9s and then an outer edge of 1s implies it. It goes through more nines than would be necessary if you were able to stop in less than 4 moves in a single direciton
|
|
#
?
Dec 18, 2023 04:50
|
|
|
thanks for the tips - yeah that’s the kind of thing I meant by “this stuff”. as a self taught dude this CS stuff is just not something I have any exposure to, and honestly I’m not sure what term to use for this kind of skill to look up ways to improve it - general problem solving skills? computational thinking? algorithms and data structures? my day job exercises domain modelling and designing applications and abstractions and things of that nature stuff but I’ve never had to traverse a graph for anything. big O is also a bit of a mystery to me beyond “nesting a loop (on the same list) is O(n^2)” basics. I’m learning F# (because I’m a dotnet guy in my day job) via advent of code and it’s v good. I maybe need to allow myself to look at other people’s solutions more for this too, rather than forcing myself to finish it before I look for other better ways to do it (not like there are many solutions for F# tho)
|
|
#
?
Dec 18, 2023 11:34
|
|
|
|
| # ? May 3, 2024 03:13 |
|
|
a book i highly recommend for anyone wanting to self-study a bit with a fairly proper focus on "real" problems is "the algorithm design manual": https://www.amazon.com/Algorithm-Design-Manual-Computer-Science/dp/3030542580/ very practical-minded, gentle introduction to each part, but has enough depth that i don't think there's a meaningful level between it and just committing to taocp and/or research papers.
|
|
#
?
Dec 18, 2023 12:02
|
|