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.
Python
The data today has a special property, which allows for a fast solution. This won’t work on other data, including the example data in the problem description.
1645 line-seconds.
import collections import math from .solver import Solver class Day21(Solver): first_star_steps: int second_star_steps: int lines: list[str] def __init__(self): super().__init__(21) self.first_star_steps = 64 self.second_star_steps = 26501365 def presolve(self, input: str): self.lines = input.splitlines() def solve_first_star(self) -> int | str: positions = {(i, j) for i, line in enumerate(self.lines) for j, c in enumerate(line) if c == 'S'} for _ in range(self.first_star_steps): next_positions = set() for i, j in positions: for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)): if not 0 <= i + di < len(self.lines): continue if not 0 <= j + dj < len(self.lines[i]): continue if self.lines[i + di][j + dj] == '#': continue next_positions.add((i + di, j + dj)) positions = next_positions return len(positions) def solve_second_star(self) -> int: positions = {(i, j) for i, line in enumerate(self.lines) for j, c in enumerate(line) if c == 'S'} modulus = self.second_star_steps % len(self.lines) points_to_extrapolate = (modulus, modulus + len(self.lines), modulus + len(self.lines) * 2) values = [] for step_count in range(modulus + len(self.lines) * 2 + 1): if step_count in points_to_extrapolate: values.append(len(positions)) next_positions = set() for i, j in positions: for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)): ni = i + di nj = j + dj if self.lines[ni % len(self.lines)][nj % len(self.lines)] == '#': continue next_positions.add((ni, nj)) positions = next_positions a = (values[2] - values[1] *2 + values[0]) // 2 b = values[1] - values[0] - 3 * a c = values[0] - b - a cycles = math.ceil(self.second_star_steps / len(self.lines)) return a * cycles * cycles + b * cycles + c
Scala3
task2 is extremely disgusting code, but I was drawing an ugly picture of the situation and just wrote it down. Somehow, this worked first try.
import day10._ import day10.Dir._ import day11.Grid extension (p: Pos) def parity = (p.x + p.y) % 2 def connect(p: Pos, d: Dir, g: Grid[Char]) = val to = walk(p, d) Option.when(g.inBounds(to) && g.inBounds(p) && g(to) != '#' && g(p) != '#')(DiEdge(p, to)) def parseGrid(a: List[List[Char]]) = val g = Grid(a) Graph() ++ g.indices.flatMap(p => Dir.all.flatMap(d => connect(p, d, g))) def reachableIn(n: Int, g: Graph[Pos, DiEdge[Pos]], start: g.NodeT) = @tailrec def go(q: List[(Int, g.NodeT)], depths: Map[Pos, Int]): Map[Pos, Int] = q match case (d, n) :: t => if depths.contains(n) then go(t, depths) else val successors = n.outNeighbors.map(d + 1 -> _) go(t ++ successors, depths + (n.outer -> d)) case _ => depths go(List(0 -> start), Map()).filter((_, d) => d <= n).keys.toList def compute(a: List[String], n: Int): Long = val grid = Grid(a.map(_.toList)) val g = parseGrid(a.map(_.toList)) val start = g.get(grid.indexWhere(_ == 'S').head) reachableIn(n, g, start).filter(_.parity == start.parity).size def task1(a: List[String]): Long = compute(a, 64) def task2(a: List[String]): Long = // this only works for inputs where the following assertions holds val steps = 26501365 assert((steps - a.size/2) % a.size == 0) assert(steps % 2 == 1 && a.size % 2 == 1) val d = steps/a.size val k = (2 * d + 1) val k1 = k*k/2 def sq(x: Long) = x * x val grid = Grid(a.map(_.toList)) val g = parseGrid(a.map(_.toList)) val start = g.get(grid.indexWhere(_ == 'S').head) val center = reachableIn(a.size/2, g, start) // If you stare at the input enough, one can see that // for certain values of steps, the total area is covered // by some copies of the center diamond, and some copies // of the remaining triangle shapes. // // In some repetitions, the parity of the location of S is // the same as the parity of the original S. // d0 counts the cells reachable in a center diamond where // this holds, dn0 counts the cells reachable in a center diamond // where the parity is flipped. // The triangular shapes are counted by dr and dnr, respectively. // // The weird naming scheme is taken directly from the weird diagram // I drew in order to avoid further confusing myself. val d0 = center.count(_.parity != start.parity) val dr = g.nodes.count(_.parity != start.parity) - d0 val dn0 = center.size - d0 val dnr = dr + d0 - dn0 // these are the counts of how often each type of area appears val r = sq(2 * d + 1) / 2 val (rplus, rminus) = (r/2, r/2) val z = sq(2 * d + 1) / 2 + 1 val zplus = sq(1 + 2*(d/2)) val zminus = z - zplus // calc result zplus * d0 + zminus * dn0 + rplus * dr + rminus * dnr
This has a line-second score of of about 100 (including the comments - I don’t know what counts as code and what doesn’t so I figured I just include everything); translating this 1:1 into c++ (https://pastebin.com/fPhfm7Bs) yields a line-second score of 2.9.
Nim
My part 2 solution assumes the input has an unimpeded shortest path from the center of each garden section to its corner, and to the center of its neighbor. The possible destinations will form a diamond pattern, with “radius” equal to the number of steps. I broke down the possible section permutations:
-
Sections that are completely within the interior of the diamond
- Even number of sections away from the starting section
- Odd number of sections away from the starting section
-
Sections containing the points of the diamond
-
Depending on the number of steps, there may be sections adjacent to the point sections, that have two corners outside of the diamond
-
Edge sections. These will form a zig-zag pattern to cover the diamond boundary.
- “Near” edge sections. These are the parts of the zig-zag nearer to the center of the diamond.
- “Far” edge sections. These won’t occur if the edge of the diamond passes perfectly through the corners of the near edge sections.
I determined how many of each of these should be present based on the number of steps, used my code from part 1 to get a destination count for each type, and then added them all up.
-