|
It turns out that the ancestors of the input value you provide are just a linear chain, with no situations where multiple nodes depend on a single node. Which I think means that the output value is a linear function of the input, making it very easy to solve numerically. But it's also tractable to solve analytically, since you can just walk down the tree saying "this tree node must evaluate to this constant value".
|
# ? Dec 21, 2022 11:47 |
|
|
# ? Jun 7, 2024 03:14 |
|
I did part 2 like 50% by hand, I wrote a function to find the difference between the two sides of the tree, plugged in test values to get an idea of the shape of the function and narrowed down the interval where the difference flipped from positive to negative, and then did a naive search in that area
|
# ? Dec 21, 2022 14:51 |
|
first go i did some regexing by hand, but fixing this up this is then my second laziest takecode:
|
# ? Dec 21, 2022 15:54 |
|
i just did binary search with the root comparison changed to a subtraction operation for p2
|
# ? Dec 21, 2022 20:29 |
|
the talent deficit posted:i just did binary search with the root comparison changed to a subtraction operation for p2 despite my crude everything-is-a-nail solution i still avoid doing this kind of thing, i.e. using that the equation is linear, which is not part of the problem statement, but happens to be the case in the input. but that's a weird hangup on my part, very much in aoc spirit to observe properties of the input.
|
# ? Dec 21, 2022 20:49 |
|
Cybernetic Vermin posted:despite my crude everything-is-a-nail solution i still avoid doing this kind of thing, i.e. using that the equation is linear, which is not part of the problem statement, but happens to be the case in the input. I don't feel especially bad about it, especially this year where there's already been a bunch of pathfinding/tree-crawling problems I've had to flail through or give up on; if I can find an easier-for-me if less clever way of solving it that doesn't involve traversing recursive data structures, I'll take it
|
# ? Dec 21, 2022 21:07 |
|
The Chairman posted:I don't feel especially bad about it, especially this year where there's already been a bunch of pathfinding/tree-crawling problems I've had to flail through or give up on; if I can find an easier-for-me if less clever way of solving it that doesn't involve traversing recursive data structures, I'll take it yeah, absolutely do not mean anything bad about it, i've written so much garbage this and past years that i have no legs to stand on whining about generality. let me instead turn this into what i originally had in mind: man smt solvers are great, so much power from an often very friendly library. don't miss out on poking at z3 at some point. great thing to have in the toolbox.
|
# ? Dec 21, 2022 21:11 |
|
I just built an AST and then played it back and forth it until only humn was on the left.code:
|
# ? Dec 21, 2022 22:02 |
|
my favorite aoc puzzles are the dfs/bfs/astar/djikstra puzzles. the solve a system of linear equations are probably my least favorite (apart from the '90% of the problem is parsing the input' days which i mostly skip)
|
# ? Dec 22, 2022 04:11 |
|
the talent deficit posted:my favorite aoc puzzles are the dfs/bfs/astar/djikstra puzzles. the solve a system of linear equations are probably my least favorite (apart from the '90% of the problem is parsing the input' days which i mostly skip) I'm fairly certain day 21 was designed as a (Stacks + RPN + Tree) manipulation problem, not something that should be binsearched or stuffed into an equation solver. The fact that you get non-unique answers when you use floor division is the best evidence for this
|
# ? Dec 22, 2022 05:15 |
|
Did you cut out an example cube to help you visualize?
|
# ? Dec 22, 2022 08:54 |
|
I didn't, but I definitely hard-coded the specific shape of my input instead of writing something to work for an arbitrary net.
|
# ? Dec 22, 2022 11:49 |
|
had fun spending way too long figuring out how to fold any input into a cube and not hardcode anything ultimately, each face stores the basis of its local coordinate system. start by picking an arbitrary face then recursively walk to whatever faces are already known to be adjacent from the input. because each edge has to fold 90 degrees, it's easy to keep rotating the basis as you walk, depending on which side you left through. then to actually "fold" the cube, for each face's missing neighbors, look at what the normal of the neighbor would have to be and then find the face that has that normal. when actually moving along the path in the problem, whenever i cross an edge, i just do some matching between the old basis and the new to figure out the new local coordinates from the old. i think this part would have been cleaner if i would have been explicit about the origin of each face and then just written a 4x4 matrix transform for the change in coordinates, but it wasn't too bad.
|
# ? Dec 22, 2022 13:46 |
|
extremely invested in this year *not* figuring out the cube motions, will make *some* other functionality do the work for me. but wound up being a day of holiday cleaning and gift wrapping, so i think i'm putting it off until tomorrow. i am generally really pleased with aoc this year. one can always debate whether it would be nicer if it was friendlier/less effort so you don't have to be a weirdo to stick all the way through, but there's usually a couple of days i really hate by this point past years. i guess one criticism i'd give is that relatively few of the recent days have been of the sort that's delightful in motion. Cybernetic Vermin fucked around with this message at 17:32 on Dec 22, 2022 |
# ? Dec 22, 2022 17:29 |
|
I had the hubris to think I could learn assembly by doing advent of code this year...in Z80 assembly. Day 1, Part 1 is complete, although just browsing this thread and looking at the rest of the problems - I don't have much hope I'll complete more than a few days: https://github.com/coat/advent2022
|
# ? Dec 22, 2022 21:54 |
|
thought today's would look cooler in motion being a cellular automaton but it mostly looks like noise. the sparks at the edges are neat though
|
# ? Dec 23, 2022 20:49 |
|
today definitely felt like a freebie at this point
|
# ? Dec 24, 2022 03:40 |
|
the Game of Life puzzle is always my favorite. It seemed a little late this year.
|
# ? Dec 24, 2022 04:16 |
|
Phew. Day 24 was ANOTHER bfs. But there were several "tricks" to reduce your overhead this time I think. The ones I used for tree trimming: The blizzards are at fixed positions at a given time modulo the column or row width. You should never re-enter a square at the same modulo pair with a longer distance. (My reasoning: if it's the same modulo pair, all paths to the solution could have gotten there wiithout looping.
|
# ? Dec 24, 2022 08:52 |
|
Since you don't need to know the actual path, you can solve it the same way you'd evaluate an NFA on a string - compute the full set of positions you can possibly reach at t=1, use that to compute the full set at t=2, etc. The only "trimming" needed is deduping positions that get reached in multiple ways.
|
# ? Dec 24, 2022 09:24 |
|
the talent deficit posted:my favorite aoc puzzles are the dfs/bfs/astar/djikstra puzzles. the solve a system of linear equations are probably my least favorite (apart from the '90% of the problem is parsing the input' days which i mostly skip) well, has for the most part been your year Jabor posted:Since you don't need to know the actual path, you can solve it the same way you'd evaluate an NFA on a string - compute the full set of positions you can possibly reach at t=1, use that to compute the full set at t=2, etc. i too have been pretty lucky this year in that this is kind of my search default anyway, and has worked for all but the robot building one, where i cut the search space in very unprincipled ways. today i predicted that there'd be more to it during part 1, so went through and did more pruning during part 1, but turns out part 2 does not really need it (though there's a bit of patience needed with the crude way i hacked it up). Cybernetic Vermin fucked around with this message at 10:32 on Dec 24, 2022 |
# ? Dec 24, 2022 10:28 |
|
Today's was absolutely delightful. I particularly enjoyed that the wind state for iteration i can be computed as a closed form of the initial state, and that the problem can be seen as a shortest-path through a cylinder, where the depth represents time. Probably my favourite pathfinding puzzle this year.
|
# ? Dec 24, 2022 12:23 |
|
Athas posted:Today's was absolutely delightful. I particularly enjoyed that the wind state for iteration i can be computed as a closed form of the initial state, and that the problem can be seen as a shortest-path through a cylinder, where the depth represents time. Probably my favourite pathfinding puzzle this year. yeah same tbh. note too that instead of having your loop time being lcm(w,h), or worse w*h, you can have two different lookup tables, one of which loops in w steps and checks only horizontal blizzards, and one of which loops in h steps and checks only vertical blizzards
|
# ? Dec 25, 2022 02:01 |
|
gonadic io posted:yeah same tbh. note too that instead of having your loop time being lcm(w,h), or worse w*h, you can have two different lookup tables, one of which loops in w steps and checks only horizontal blizzards, and one of which loops in h steps and checks only vertical blizzards cool, didn't think of that. what approach would the lcm runtime come from? only thing I could think of is caching lcm(w,h) states each of which with w*h data but that seems quite different than what you're describing
|
# ? Dec 25, 2022 08:03 |
|
cool av posted:cool, didn't think of that. if you keep with just one lookup table that does both vertical and horizontal blizzards, it repeats after LCM(w,h) time steps, not (just) w*h. gonadic io fucked around with this message at 10:40 on Dec 25, 2022 |
# ? Dec 25, 2022 10:32 |
|
https://futhark-lang.org/blog/2022-12-25-reflections-on-advent-of-code.html
|
# ? Dec 25, 2022 12:25 |
|
final one was pretty neat, i did encode it in a dumb way recursively in order of significance setting digits to the one that minimizes the distance to the intended number, which works, but after having had my coffee i realize that nothing prevents you from computing the final number of digits, then computing the base-5 representation in the usual modulo-and-shift way, only on the number x+22...2 good problems this year, only ones i didn't like too much was 19 where i still don't know how it can be done really fast without making assumptions that could be unsound in general, and 22 where i just refused to go through with tedious hand-coding, but eventually arrived with a 2d stitching approach that was only a little better. Cybernetic Vermin fucked around with this message at 14:05 on Dec 25, 2022 |
# ? Dec 25, 2022 14:02 |
|
You can also work it out in the regular modulo-and-divide way, but adding 1 to the number after dividing when the digit you just emitted was actually 5 below what it would have been in a normal place-value system.
|
# ? Dec 25, 2022 14:20 |
|
Cybernetic Vermin posted:final one was pretty neat, i did encode it in a dumb way recursively in order of significance setting digits to the one that minimizes the distance to the intended number, which works, but after having had my coffee i realize that nothing prevents you from computing the final number of digits, then computing the base-5 representation in the usual modulo-and-shift way, only on the number x+22...2 agreed on 19 that one single handedly took out 3 days for me and I was playing catch-up for the rest Jabor posted:You can also work it out in the regular modulo-and-divide way, but adding 1 to the number after dividing when the digit you just emitted was actually 5 below what it would have been in a normal place-value system. yeah I had a delightful moment realizing the way forward was basically implementing base-5 ToString with an adder carry-bit algorithm when you see a 3 or 4 digit
|
# ? Dec 25, 2022 17:55 |
|
also lol at the day 25 part 2 best times being 30 seconds slower than part 1
|
# ? Dec 25, 2022 17:57 |
|
I did a little writeup about how AOC went for me too: https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/2022/commentary.md
|
# ? Dec 26, 2022 02:36 |
|
DrPossum posted:more like advent of chode
|
# ? Dec 29, 2022 02:54 |
|
DrPossum posted:more like advent of chode
|
# ? Jan 8, 2023 02:35 |
|
Got my 50 stars! I had to look up tips and this thread was also a big help for some of the domains I didn't have much experience in (DFS pruning, modulo arithmetic). I also did it in rust this year so it gave me a chance to learn a bit more about structuring structs based on the borrowing rules involved. Overall I really liked this year. If anyone's got recommendations for good algorithm / dynamic programming books though I'm all ears. I've got no formal education in those and wouldn't mind going deeper.
|
# ? Jan 8, 2023 03:09 |
|
I still have the factory day left. It gets the right answer for the examples in part 1, but not for my input. Haven't had the time to really sit down and learn why.
|
# ? Jan 8, 2023 03:23 |
|
it is the kind of problem where in the real world you probably *should* use a solver, for robustness if nothing else. likely also the best bet for getting leaderboard in aoc if one cares about such things (one should not). i went for a dumber solution at the time, but the z3 solution is reasonably straightforward (input premassaged a bit):Python code:
at any rate it is the sort of thing that's well worth learning, lot of toolbox utility for fairly limited effort. and for a lot of brute-force search problems it will likely be faster than what one invents.
|
# ? Jan 9, 2023 13:01 |
|
MrQueasy posted:I still have the factory day left. It gets the right answer for the examples in part 1, but not for my input. Haven't had the time to really sit down and learn why. when i had that problem it was my code allowing buying 2 different bots in one turn
|
# ? Jan 9, 2023 15:35 |
|
cool av posted:when i had that problem it was my code allowing buying 2 different bots in one turn It was because I used a min instead of a max for limiting the number of ore robots to make! Just plain ol' graph traversal for me, thank you. Kotlin code:
Advent of Code 2022 is now done and dusted for me. (anonymous user #2347253)
|
# ? Jan 9, 2023 19:58 |
|
DrPossum posted:more like advent of chode
|
# ? Jan 16, 2023 08:38 |
|
|
# ? Jun 7, 2024 03:14 |
|
Day 19 was a hoot, along with 16. Thanks for the tip to look at solvers. My solution DFS with pruning got the following times: Part 1 7.40ms Part 2 439.31ms So I was pretty pleased with that. It's by far the slowest solution, the next-worst was Day 23 at ~214ms. The entire year runs in 1.7s or so.
|
# ? Jan 16, 2023 14:29 |