|
I thought I was being clever reusing Day 10 for part1 of Day 18.
|
# ? Dec 18, 2023 12:05 |
|
|
# ? May 2, 2024 17:04 |
|
MrQueasy posted:I thought I was being clever reusing Day 10 for part1 of Day 18. I did the same. It was not too bad, because 18 A was quick. 18B was quick too, because even the test data pointed out that the result will be absurd, figure out a better way to calculate an area than flood filling it So I did not get stuck with it, instead I searched for "how to calculate an absurdly large area with math" instead, result was Shoelace formula. Day 17 was hell though and I could not figure it out until pointed that pathfinding crate is better for djisktra than petgraph, since pathfinding allows you to customize the parameters of the search easily enough. Ihmemies fucked around with this message at 12:27 on Dec 18, 2023 |
# ? Dec 18, 2023 12:23 |
|
Gonna have to throw out my part 1 solution and start over, I think.
|
# ? Dec 18, 2023 12:31 |
|
had to also throw out my second attempt but got it on the third try, which was more or less an extension of day 10. i should have done that from the start.
|
# ? Dec 18, 2023 14:36 |
|
Not hyped for this one because I ended up just googling "polygon formula" (and these formulas are magic, geometrists are wizards) for part 2 and I just couldn't figure out how to make a cute terminal animation for it.
|
# ? Dec 18, 2023 17:25 |
|
Vanadium posted:Not hyped for this one because I ended up just googling "polygon formula" (and these formulas are magic, geometrists are wizards) for part 2 and I just couldn't figure out how to make a cute terminal animation for it. this one was pretty personally satisfying because unlike a bunch of previous problems where it's like "remember algorithms class" or "remember this fact about number theory", the solution to this one was straight out of the surveying class I took in college so I was able to whip up a solution that worked for both parts on the first try while all the programmers I know had their flood fill solutions blow up in part 2
|
# ? Dec 18, 2023 17:59 |
|
I did not even think about trying my solution for A to B. I immediately thought there must be a better way to do it. If I can't see how many zeroes a number has from a quick glance, it has too many. And that was on test data
|
# ? Dec 18, 2023 18:04 |
|
Cybernetic Vermin posted: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/ I will add this to my list. I’ve just started reading Grokking Algorithms atm and while it’s super basic and assumes I’m a novice hobby coder that’s probably about the level I need for being properly introduced to big O and stuff I think. might start day 3 today
|
# ? Dec 19, 2023 15:48 |
|
I hosed up implementing shoelace algorithm for part B like 3 different times yesterday, along with a couple other approaches. Skill issue, but I really wasn't enthused about the second half yesterday at all and wasted too much time on it. I was hoping for something interesting around the colors, not another resolve the problem with a sparse representation followup. I'm finding the surprise second half more frustrating than anything at this point. Sometimes it's nice when the problem builds off itself. But when the second part can require an entirely different representation than the first, I just feel irritated that I need to start over. Day 17 was good about that, IMO: it was about generalizing your rules instead of finding an efficient representation
|
# ? Dec 19, 2023 16:03 |
|
Day 19 feels like day 5 multiple times at the same time, with extra parsing and light recursion. I had an obvious off-by-one error in part two, making me look at those ranges way to long and go "these basically describe a bunch of 4d hypercuboids and I'm trying to calculate the volume. Maybe my problem is that they overlap and I'm double-counting the intersections!" and then I messed up my check-for-overlap thing too and was confused until I looked back to what I was doing in the first place and realized that of course there's no overlap because we're only slicing up a volume. I'm definitely running out of steam a bit, but it'll be over soon, right?
|
# ? Dec 19, 2023 16:16 |
|
I finally managed to get my part process queue working, in day 19, only to get to part B. Now what am I going to do, I have no idea. I barely even understand what the task wants me to calculate. E: perhaps one way is to calculate which ranges of possible XMAS values are even accepted by the rules, and iterate those somehow instead of everything..? Ihmemies fucked around with this message at 18:34 on Dec 19, 2023 |
# ? Dec 19, 2023 18:30 |
|
Ihmemies posted:I finally managed to get my part process queue working, in day 19, only to get to part B. I know what to do for part 2 but I just haven't spent the brain power to implement it. Create a tree where descending down into a node creates a modified set of ranges for each param, then DFS my way into a list of acceptable ranges, then do the math Theoretically not too bad, my brain just didn't want to do it at 11pm last night.
|
# ? Dec 19, 2023 19:33 |
|
i've used up the last of my dumb luck of 2023: reading 19b i groaned so very deeply, but somehow my first attempt worked without revision or debugging. basic idea would be to write a recursive function do_the_thing(xmas_tuple, action), where xmas_tuple is of the form ((x_min, x_max), (m_min, m_max), (a_min, a_max), (s_min, s_max)), and action is the name of a "function", "A", or "R". then do_the_thing should return a *collection* of such 4-tuples-of-ranges which describe all that make it through the action. for 'A' it is just [xmas_tuple], for 'R' it is empty, and for a function it walks through it splitting the tuples according to conditionals. very finicky though. multiply up the max-min's of each tuple, sum those, and that's the answer. i don't like this one that much despite having made it through, i was real lucky and there's so much room to do an off by one or otherwise mess up a range somewhere, and it is then *extremely* tedious debugging
|
# ? Dec 19, 2023 23:38 |
|
Ugh, it took me forever to understand how a then b then ... n should work with the recursion.pre:class WorkflowHandler(private val workflows: Map<String, List<Rule>>) { private fun handleStandard( rule: Rule.Standard, sum: Long, rr: RatingRange, ): Ior<Long, RatingRange> { val (rrt, rrf) = rule.split(rr) val newSum: Long = sum + when (val o = rule.output) { RuleOutput.Accepted -> rrt.size() is RuleOutput.NextRule -> crop(rrt, o.name) else -> 0L } return (newSum to rrf).bothIor() } private fun handleAuto( rule: Rule.Automatic, sum: Long, rr: RatingRange, ): Ior<Long, RatingRange> { return ( sum + when (val o = rule.output) { RuleOutput.Accepted -> rr.size() is RuleOutput.NextRule -> crop(rr, o.name) else -> 0L } ).leftIor() } fun crop( ratingRange: RatingRange = RatingRange(), wfName: String = "in", ): Long { return workflows.getValue(wfName) .fold(ratingRange.rightIor() as Ior<Long, RatingRange>) { ior, rule -> ior.fold( fa = { it.leftIor() }, fb = { when (rule) { is Rule.Standard -> handleStandard(rule, 0L, it) is Rule.Automatic -> handleAuto(rule, 0L, it) } }, fab = { left, right -> when (rule) { is Rule.Standard -> handleStandard(rule, left, right) is Rule.Automatic -> handleAuto(rule, left, right) } }, ) }.leftOrNull() ?: 0L } }
|
# ? Dec 20, 2023 04:32 |
|
Huh, day 20 is another callback to a previous level.
|
# ? Dec 20, 2023 08:54 |
|
just getting started on 20, and already decided that this is one of those where i will commit hard to a complicated solution to a because i think i have a good guess at what b is. wish me luck. e: bah, i had the right *kind* of guess, but i still did not write it in a way that lets me reuse a to any great extent. e2: also having pondered a bit i suspect this is one of those which would be made a lot easier by being willing to analyze ones input a bit, but i am not really willing to do that, so this might get really tricky. as it stands it seems like a model checking problem that is likely PSPACE-hard, and the instance is large, so actually general solution is probably not a thing one can do Cybernetic Vermin fucked around with this message at 13:45 on Dec 20, 2023 |
# ? Dec 20, 2023 12:10 |
|
Jabor posted:Huh, day 20 is another callback to a previous level. obviously it’s because we’re falling back down through the islands day 20 part 2 is a reverse engineering question in disguise, just with Xilinx instead of assembly
|
# ? Dec 20, 2023 19:21 |
|
I wasted probably literally hours total on part 2 because I was inspecting and looking for cycles in the state of a bunch of modules rather than in the pulses they're sending. I did log [spoilers]all pulses instead for a while but not like per edge[/spoiler] so didn't get more out of it than "huh that sure is a sequence of strings of ones and zeroes".
|
# ? Dec 20, 2023 19:35 |
|
no real phone ins for me this year, having to work for every star i'm only up to day 7 and i'm considering career change
|
# ? Dec 21, 2023 01:10 |
|
Neslepaks posted:no real phone ins for me this year, having to work for every star puzzles are different than real world problems. do not give up, skeleton! learning how to solve silly puzzles is meant to be pleasurable in the doing, not something “useful”. there’s definitely a ramp up as you lean the “language” of the puzzles. Sudoku has x wings and jellyfish, American crosswords have an editor dependent way of writing clues, etc. And looking up hints is the best way to learn how to do these tricks.
|
# ? Dec 21, 2023 03:51 |
|
day 21 part 2 has me completely stumped rip ok maybe not completely but idk i guess the gimmick is that you can just draw a diamond and you probably have almost the right number and you only really need to look at those edges in detail, but i have no intuition how to extrapolate accurately edit: ok nm solved it, looks like the input was carefully generated so all the stuff i worried about wasn't an issue, which feels kinda cheap i'm getting a bit tired of this style of part 2 Vanadium fucked around with this message at 23:06 on Dec 21, 2023 |
# ? Dec 21, 2023 20:45 |
|
got discouraged by 20b and haven't checked the days since. but i think i at least have a solid idea. what annoys me is that it for sure doesn't work in general, but i think it'll cover most "easy" instances.
|
# ? Dec 22, 2023 11:14 |
|
I think that solving 20b generally would be roughly solving halting problem. the input format allows building a microprocessor and they kinda did
|
# ? Dec 22, 2023 16:22 |
|
betalarmannen posted:I think that solving 20b generally would be roughly solving halting problem. the input format allows building a microprocessor and they kinda did it is in pspace as there's an amount of state linear in the size of the input. i largely assume everyone's input is a slight perturbation of a binary adder or some such, they presumably have some schema to push the final bit exponentially many steps into the run. but I don't want to assume the details of that in implementation
|
# ? Dec 22, 2023 16:27 |
|
even though I cringed when I saw it was 3d, day 22 was a bit of a relief compared to the last two (which I still haven’t finished)
|
# ? Dec 22, 2023 16:33 |
|
Yeah day 22 was more relaxing. I eyeballed the size/dimensions of the input and figured I could get away with something stupid to begin with, and was positively surprised when I kept getting away with doing the stupid thing in part 2. I got a bit sidetracked actually defining a bunch of custom types with like utility methods and something approaching abstraction to represent individual bricks and the space with bricks in it because I figured I'd probably have to switch to some sparse representation for part 2 and it might be a fun exercise to try to do that without breaking the interface. Turns out I could just do part 2 by running the code from part 1 a ton of times with some extra record keeping and it was, like, not impressively fast, but done in a minute or two. I think I lost most time (outside of looking up to do basic poo poo in python) to off-by-one errors, fixing the off-by-one errors, and then trying to rewrite the code to be more reusable while reintroducing the off-by-one errors. Cybernetic Vermin posted:i largely assume everyone's input is a slight perturbation of a binary adder or some such, they presumably have some schema to push the final bit exponentially many steps into the run. but I don't want to assume the details of that in implementation Does Santa ever publish the input generation code after it's over?
|
# ? Dec 22, 2023 17:26 |
|
cool av posted:even though I cringed when I saw it was 3d, day 22 was a bit of a relief compared to the last two (which I still haven’t finished) problems like 22 are my favorite because they enable both a naive simulation that can take a minute and a more abstract solution that solves in under a second, but the input is reasonable enough that if you just want to do the simulation method you're not punished for it
|
# ? Dec 22, 2023 18:32 |
|
day 22 part 2… need pruning tips apparently the longest path reaches several spaces at times where the distance is smaller than on shorter paths
|
# ? Dec 23, 2023 18:35 |
|
MrQueasy posted:day 22 part 2… need pruning tips do the search depth-first instead of breadth-first
|
# ? Dec 23, 2023 19:00 |
|
The Chairman posted:do the search depth-first instead of breadth-first
|
# ? Dec 23, 2023 20:21 |
|
I tried a whole bunch of more or less clever pruning things and in the end I got the answer from a more or less brute force thing I left running on the other monitor for a few hours. I'm gonna have to sleep on this one I think.
|
# ? Dec 23, 2023 23:26 |
|
finally gave in and solved 20b and 21b by analyzing the inputs carefully, completing the year. must say, i think the problem quality was extremely good this year outside of 20b and possibly 21b. sometimes i come around on a problem once i've had a moment to think after solving, but 20b was as a description entirely hopeless (no real heuristics or optimizations possible for what is just general logic), and even admitting that input analysis is sometimes an intended part it was a real crude take in this instance. 21b might have a general solution, but i did not spot one i thought had good chances. even if it does though i think it was a pretty crude simplification to apply to the input. very subjective, but one can compare with day 23, which i think was a really nice problem. longest path is np-complete so a fully general solution does (likely) not exist, but i expect any number of approaches would solve it probably a clean dfs brute-force with tight enough code, there's probably some memoization possible, to make my own crude python reasonably quick i just contracted the graphs by replacing paths with no branches by a single weighted edge all-in-all a good year though. learned a few new tricks (mostly abusing the networkx library for various graph stuff).
|
# ? Dec 26, 2023 20:24 |
|
finished finally… 24 part 2 was the killer for me. I knew how I needed to solve it, but I couldn’t recall any of the language of linear algebra that I needed to find the specific algorithms to implement. its Gaussian elimination, and you only need 3 hailstones to solve it once you remember how cross products work well, that and fighting with how your particular language handles really large floating point variables this year was pretty good and fun IMO. but i have to give it a few demerits for not having a Game of Life simulation, as those are my favorites. MrQueasy fucked around with this message at 00:37 on Dec 30, 2023 |
# ? Dec 30, 2023 00:35 |
|
DrPossum posted:more like advent of chode
|
# ? Dec 31, 2023 05:26 |
|
wb
|
# ? Dec 31, 2023 09:14 |
|
DrPossum posted:more like advent of chode
|
# ? Feb 22, 2024 05:14 |
|
DrPossum posted:more like advent of chode
|
# ? Mar 1, 2024 05:58 |
|
|
# ? May 2, 2024 17:04 |
|
|
# ? Apr 16, 2024 01:34 |