Day 21: Step
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Rust
https://github.com/Treeniks/advent-of-code/blob/master/2023/day21/rust/src/main.rs
I reused my Grid struct from day 17 for part 1, just to realize that I’ll need to expand the grid for part 2 so I awkwardly hacked it to be a
Vec>instead of a linearVec.I solved task 2 by reading through the reddit thread and trying to puzzle together what I was supposed to do. Took me a while to figure it out, even with literally looking at other people’s solutions. I wrote a lengthy comment about it for anyone that’s still struggling, but I honestly still don’t really understand why it works. I think I wouldn’t have solved it if I didn’t end up looking at other solutions. Not a fan of the “analyze the input and notice patterns in them” puzzles.
Agreed, i get annoyed when I can’t actually solve the problem. I would be ok if the inputs are trivial special cases, as long as feasible (but harder) generalized solutions still existed.
If you wonder why the function is a quadratic, I suggest drawing stuff on a piece of paper. Essentially, if there were no obstacles, the furthest reachable cells would form a large diamond, which is tiled by some copies of the diamond in the input and some copies of the corners. As these have constant size, and the large diamond will grow quadratically with steps, you need a quadratic number of copies (by drawing, you can see that if
steps = k * width + width/2, then there arefloor((2k + 1)^2/2)copies of the center diamond, andceil((2k + 1)^2/2)copies of each corner around).What complicates this somewhat is that you don’t just have to be able to reach a square in the number of steps, but that the parity has to match: By a chessboard argument, you can see any given square only every second step, as each step you move from a black tile to a white one or vice versa. And the parities flip each time you cross a boundary, as the input width is odd. So actually you have to either just guess the coefficients of a quadratic, as you and @hades@lemm.ee did, or do some more working out by hand, which will give you the explicit form, which I did and can’t really recommend.