You manage to catch the airship right as it’s dropping someone else off on their all-expenses-paid trip to Desert Island! It even helpfully drops you off near the gardener and his massive farm.
“You got the sand flowing again! Great work! Now we just need to wait until we have enough sand to filter the water for Snow Island and we’ll have snow again in no time.”
While you wait, one of the Elves that works with the gardener heard how good you are at solving problems and would like your help. He needs to get his steps in for the day, and so he’d like to know which garden plots he can reach with exactly his remaining 64 steps.
He gives you an up-to-date map (your puzzle input) of his starting position (S), garden plots (.), and rocks (#). For example:
...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........
The Elf starts at the starting position (S) which also counts as a garden plot. Then, he can take one step north, south, east, or west, but only onto tiles that are garden plots. This would allow him to reach any of the tiles marked O:
...........
.....###.#.
.###.##..#.
..#.#...#..
....#O#....
.##.OS####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........
Then, he takes a second step. Since at this point he could be at either tile marked O, his second step would allow him to reach any garden plot that is one step north, south, east, or west of any tile that he could have reached after the first step:
...........
.....###.#.
.###.##..#.
..#.#O..#..
....#.#....
.##O.O####.
.##.O#...#.
.......##..
.##.#.####.
.##..##.##.
...........
After two steps, he could be at any of the tiles marked O above, including the starting position (either by going north-then-south or by going west-then-east).
A single third step leads to even more possibilities:
...........
.....###.#.
.###.##..#.
..#.#.O.#..
...O#O#....
.##.OS####.
.##O.#...#.
....O..##..
.##.#.####.
.##..##.##.
...........
He will continue like this until his steps for the day have been exhausted. After a total of 6 steps, he could reach any of the garden plots marked O:
...........
.....###.#.
.###.##.O#.
.O#O#O.O#..
O.O.#.#.O..
.##O.O####.
.##.O#O..#.
.O.O.O.##..
.##.#.####.
.##O.##.##.
...........
In this example, if the Elf’s goal was to get exactly 6 more steps today, he could use them to reach any of 16 garden plots.
However, the Elf actually needs to get 64 steps today, and the map he’s handed you is much larger than the example map.
Starting from the garden plot marked S on your map, how many garden plots could the Elf reach in exactly 64 steps?
type Point struct {
x, y int
}
type QueueItem struct {
pos Point
steps int
}
func readInput(filename string) ([][]byte, Point) {
file, err := os.Open(filename)
if err != nil {
fmt.Println(err.Error())
os.Exit(1)
}
defer file.Close()
var grid [][]byte
var start Point
scanner := bufio.NewScanner(file)
y := 0
for scanner.Scan() {
line := []byte(scanner.Text())
for x, ch := range line {
if ch == 'S' {
start = Point{x, y}
}
}
grid = append(grid, line)
y++
}
return grid, start
}
func countReachableGardens(grid [][]byte, start Point, targetSteps int) int {
rows, cols := len(grid), len(grid[0])
dirs := []Point{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} }
queue := []QueueItem{ {start, 0} }
visited := make(map[string]bool)
positions := make(map[Point]bool)
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
if current.steps == targetSteps {
positions[current.pos] = true
continue
}
if current.steps > targetSteps {
continue
}
for _, dir := range dirs {
newX, newY := current.pos.x+dir.x, current.pos.y+dir.y
if newX >= 0 && newX < cols && newY >= 0 && newY < rows && grid[newY][newX] != '#' {
newPos := Point{newX, newY}
key := fmt.Sprintf("%d,%d,%d", newX, newY, current.steps+1)
if !visited[key] {
visited[key] = true
queue = append(queue, QueueItem{newPos, current.steps + 1})
}
}
}
}
return len(positions)
}
func main() {
grid, start := readInput("input.txt")
result := countReachableGardens(grid, start, 64)
fmt.Printf("Number of reachable garden plots in 64 steps: %d\n", result)
}
The Elf seems confused by your answer until he realizes his mistake: he was reading from a list of his favorite numbers that are both perfect squares and perfect cubes, not his step counter.
The actual number of steps he needs to get today is exactly 26501365.
He also points out that the garden plots and rocks are set up so that the map repeats infinitely in every direction.
So, if you were to look one additional map-width or map-height out from the edge of the example map above, you would find that it keeps repeating:
.................................
.....###.#......###.#......###.#.
.###.##..#..###.##..#..###.##..#.
..#.#...#....#.#...#....#.#...#..
....#.#........#.#........#.#....
.##...####..##...####..##...####.
.##..#...#..##..#...#..##..#...#.
.......##.........##.........##..
.##.#.####..##.#.####..##.#.####.
.##..##.##..##..##.##..##..##.##.
.................................
.................................
.....###.#......###.#......###.#.
.###.##..#..###.##..#..###.##..#.
..#.#...#....#.#...#....#.#...#..
....#.#........#.#........#.#....
.##...####..##..S####..##...####.
.##..#...#..##..#...#..##..#...#.
.......##.........##.........##..
.##.#.####..##.#.####..##.#.####.
.##..##.##..##..##.##..##..##.##.
.................................
.................................
.....###.#......###.#......###.#.
.###.##..#..###.##..#..###.##..#.
..#.#...#....#.#...#....#.#...#..
....#.#........#.#........#.#....
.##...####..##...####..##...####.
.##..#...#..##..#...#..##..#...#.
.......##.........##.........##..
.##.#.####..##.#.####..##.#.####.
.##..##.##..##..##.##..##..##.##.
.................................
This is just a tiny three-map-by-three-map slice of the inexplicably-infinite farm layout; garden plots and rocks repeat as far as you can see. The Elf still starts on the one middle tile marked S, though - every other repeated S is replaced with a normal garden plot (.).
Here are the number of reachable garden plots in this new infinite version of the example map for different numbers of steps:
- In exactly
6steps, he can still reach16garden plots. - In exactly
10steps, he can reach any of50garden plots. - In exactly
50steps, he can reach1594garden plots. - In exactly
100steps, he can reach6536garden plots. - In exactly
500steps, he can reach167004garden plots. - In exactly
1000steps, he can reach668697garden plots. - In exactly
5000steps, he can reach16733044garden plots.
However, the step count the Elf needs is much larger! Starting from the garden plot marked S on your infinite map, how many garden plots could the Elf reach in exactly 26501365 steps?
type Point struct {
x, y int
}
func readInput(filename string) ([][]byte, Point) {
file, err := os.Open(filename)
if err != nil {
fmt.Println(err.Error())
os.Exit(1)
}
defer file.Close()
var grid [][]byte
var start Point
scanner := bufio.NewScanner(file)
y := 0
for scanner.Scan() {
line := []byte(scanner.Text())
for x, ch := range line {
if ch == 'S' {
start = Point{x, y}
}
}
grid = append(grid, line)
y++
}
return grid, start
}
func mod(a, b int) int {
return ((a % b) + b) % b
}
func getKey(p Point, steps int) string {
return fmt.Sprintf("%d,%d,%d", p.x, p.y, steps)
}
func countReachablePlotsInfinite(grid [][]byte, start Point, steps int) int {
rows, cols := len(grid), len(grid[0])
dirs := []Point{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} }
visited := make(map[string]bool)
positions := make(map[Point]bool)
queue := []struct {
pos Point
steps int
}{ {start, 0} }
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
if curr.steps == steps {
positions[curr.pos] = true
continue
}
if curr.steps > steps {
continue
}
for _, dir := range dirs {
newX := curr.pos.x + dir.x
newY := curr.pos.y + dir.y
wrappedX, wrappedY := mod(newX, cols), mod(newY, rows)
if grid[wrappedY][wrappedX] != '#' {
newPos := Point{newX, newY}
key := getKey(newPos, curr.steps+1)
if !visited[key] {
visited[key] = true
queue = append(queue, struct {
pos Point
steps int
}{newPos, curr.steps + 1})
}
}
}
}
return len(positions)
}
func solve(grid [][]byte, start Point, targetSteps int) int {
size := len(grid)
initialSteps := targetSteps % size
y0 := countReachablePlotsInfinite(grid, start, initialSteps)
y1 := countReachablePlotsInfinite(grid, start, initialSteps+size)
y2 := countReachablePlotsInfinite(grid, start, initialSteps+size*2)
a := (y2 - 2*y1 + y0) / 2
b := y1 - y0 - a
c := y0
n := targetSteps / size
result := a*n*n + b*n + c
return result
}
func main() {
grid, start := readInput("input.txt")
result := solve(grid, start, 26501365)
fmt.Printf("Number of reachable garden plots in 26501365 steps: %d\n", result)
}
Links
Click to show the input
................................................................................................................................... .......#.#.#.#.....#.#...##..........#........##....#......#...............##........#..#...##.......###....#.##........#.#....#... .###............#........#......#.....#...................................#............#..........#.....#..##.#.......#.....#...... .......#....#...##......#..............##.###....##......#..................#.....#..#.....#...#.#....#................#....#.##... ..............#................#..#.#...#......#.#..#....................##....#..#.#.....#.#..........#...#.#......#...#..#....... .....#.....#............##.#.....#......#..#...................................#......##..#.#..........#.#..##..#................#. .#....#......##.#...#..#.....#................##.#....#.............................##...#...#........#....#....................... ....#.....#................#.....##...............#...............#...........#..#...........#.........#.............#........#.... .........#.................#...........#......#...#...............#...........#....#....#..........#...#.#.##.................#.... .........#....#..#.....#..#..#.#....#...#......................#................####...#.....#..........#.......#..#........#...... ..............#.##...............#.#.#..........#..#............#.........................................#.#.#............#.#..... ..............#...#.....#...#....##.............##............##..#.................###........#....#.#.......................#..#. ......#.....##..#....#.#......#.#....#..#.#.....#............................................##.#.....#.#.......#......#.#.#....... ........#.............#.............#.....#................#.......#.....................#...#.........#..#...##..##...##..###..... .......#..........................#........................................#........###..##......#.#.....#....#....#....#.......#.. ...#......#.#..........#..#..........#..#.....#..........#........#.......................#....#.......#...##.............#.#...... ..#..##...#...........#.#.#.##........##..#...................#....##..##..##...............#....#...........#......##..#.......#.. ....................#.#...#.........##....................#.....#.....#..#....................................#.#.#........#.#..... ............##.#..#.#..#............#..#..#...........#.........#...#...............................#...............#...#........#. .......##......#..............###......#............#.....#..........#..#.#.....#............#.#.......#..#...............#.....#.. .......###.......#......#..#..#...#...#...........#......#.........#...........#...................#.....##..........#....#........ ..#...#.#..................##........................#..............##.....#.#.......................#...#..#...#.................. .........#.......#...#...#.....#......#..............##.......##....#.............##..............##.....#....................#.... ..#....#.....#.....#............................#.#.......#.............#.....................#.........#.......#....##.#.......... ...#.#...#........#....#........#.#...............#..##......#........#.........#...................#...#.......#...#......#...#... .......................#..#..#.....#............#.#...#..#...........#.......##....#.#................#...................#....#... .........#....#.#..........#.#....#..................#..............#...#...#..........#..........#.............##..#.......#..#... ...#......#.#......#.....#.##.#...#.....................#....##............#......#...#.........##...............#...............#. ........#.......#...................................#....#...............#....#.##..#............#...#........................#.... .......................#.......#..............#........#.#............#............................#...#......#..#..#.##.#......... ......#...#.##.............................##.#...................#..#......#.#...#...##..#.........##......#..#....#........#..#.. .........#.#............#................#...#.##......#..#.....#.##....##.#...........#....................#.............#........ .....#...#.........#...#.#...#.........#...#....#......#......##...#..#........#.....#.....#.............##.........#..........#... .....#.......#............#.#............###..#..#.#.....#.##.......#.#.............##..##.....................#.#.......#..##..... .#...#.....#...#.......................#...#.##...#....#........#.....#...#..................#............##..#...#....#.##.#...#.. ......##.............#...#.........#.....#.....#..#........#......#..#......#..##...#..##.....#.#.................#..#.........#... .........#..........#.#............###.................#..#.....#.....#..#...#..........#........#..........#.................#.... ..#..........#....................#.....#..#...#....#.....#..#............#....#..#.........##..##..........#....#......#.......... .........#..........#..#.......#............#...........#.......#..#...........#.......##.....................#.......#............ ...#...........................#..#.........#.#.....#.........#..........#........##.......#...#...............#....##.#.#....#.... ....##.....#...#.......................#..#...#......#....#.#.....#..##.......#.........##.....................................#... .#......#....##...#............#.....#..#........#......#...##.......#...#...#.#...#.#.....##..........................#..#........ .#.......##...................#..#......#..#..................##....#..#....#..##.......#..#.....###................#.#............ ..............#.............#..#....#.....#.......#..#....##.........#..#.#.....###.......#.....##...##..........#..........#...... ..#.#..#.................#......#...#.#...#......#...#.............#...#..##...............#........#............##.#.....#........ ........#.....#.................#.....##.....#.#...#..#...........#..............#...#........#........##..............#........... .#......#........................#..##.#........##......##....#...#........#..#...#..##.........#....#...............#............. ....#.....##..#............##.........#...#......#.#.....#.........#.#.#....###......................#...#......................... .........###............##..........#.#.#.....#.....#..###.....................##.....#.....#....#.#............................... ...#.#.#............#..#.........###.....####.......#.....#...................#..##..##.......#.................................... .#.#.....#.#...............................#..#.......##........................#...#....#...##.#...#....................##........ ...#.....................#...#...............#...#..#...#....#......##....#.#..#.#......#...#........#.....##.................##... .........#.........#..#...#.#.#...#...#..........#......####.#.......#................#.........###...#..#......................... ....##..........#.........#..................#....#....#........#...#.........#..##...#....##.....#.#..........#..#..........#..... ...#............#...#..#.#.#.....#..##.#..#.......................#..#.....#....#...#.....#.....#..........#...#...#............... .#..................................#..#..#..............#...#.....#...#................#.....#...#...........##..#................ ....##................#....#.......#..#....#....#............##..........##...#.......#.......#...........#....#................... ....#..........#..........#..##......#.......###...........#............#..........#...#.#.#........#.#.#.#.#.#......#..........#.. ............#...........................................#.......#.##.#.....................#..#..#..#.............#..............#. ...........#...#.........#.#....#................#.....#........#..#...#.#.....#..........#....................#...#..#............ ...........#.#...#....#.....#..#..........#...#.#..#..#.#.........#.#.##........#......#................#...........#.............. ................................................#..#..#....#.........#.............#....###..#...............#...#.......#......... ............................#...#..#......##......#...#........#....#.....#.....#...#..#...#..........................###.#........ ..............#............#...#.#...##.......##.....#.##..........#....#............#.......#......##.#....#.......#.............. ...........#.##.##..#.#.#.........###........#...#...#................#.#...............#..#.#........##........#.##.......#....... .................................................................S................................................................. .............#.#......#..##..#.............#...........#..........#..##.#...............#..###..............#...#.##.##....#....... ......#......##..#...............#..#............##.......#.#.......##..#...#.....##........#.................#....#......#........ ..........#..........#.#........#....#......#........#.....#.............#....#..............#.#..#...#.............#.............. ...........#........##.#.......#...#....#........#.#.....#........#..#..........#......##.....#...............#....#....#.......... ...........#............#.....#..#.............#..#....#.#.....##............#.......#.......#............#.#..##.................. ...........##..#...#.....##.........##.......#.......#.............#...#......#...##........#..#....#.......##..........#.......... .............#.......#......#..#...##..#.................................####...#......#.............#..#..#.......#............... ................#............#........#...##......##...................#..#...#.........#..#.........................#............. .........................#...##.#......#...........#........#........#...............###....#.#........#............#.............. ...#...........##........#..##.....#.....#.##......#....#..#........#.................#.#.........#........##..#..#................ ..#.............#.##....#......#...#.#.......#.......#.................#.....#.....#.............###......#...#............##...... ........................#.....#..##.........#.....#.....#..#........#...#.....#.....#....#......#...##..#...#.............#..#..... ......#........................#.....#..#...#....#......#....#..#.#.#...#.....#..#......#..#..#...#...#..#..#...............#...... ..........#...........#......##.#.#............#...................##.....#..#...##....#..........#........#.............#......... .#.......................#.....#..........#..##....#....#...............##......#.#..#.###..............................#..#..#.... .......................#........##......#.#......#......####..........#..#........#.#...........#..#.#..#.....#.................... ....##.....................#..#.......###.................##.......#...#..#.###..#...#..###........#....#.#.............##....#.... ........#..#............#...#.........#........#....#.##.......#...#.......#..#.#.......................................###........ .......##.....#..............#..#....#..#...............#......#................#................##......#.............#.#......... ....#......##...........###.....##................#...#....##.#......#....................#...##.#.......#............###...#...... .#...#.........#..........#..#.##.#.#...........#.#.........##....#.#......#........#.....#..#..........##.............#...#....##. .........#.#.#....#..........#.....#...#..#.#...............#..........#....................##........................#.##....#..#. ........###..#..................#...#.....#.................#.#....#........#................#...#...........................#...#. .....#.#..#........#.............#.........#.............#..###......#..#.#....#................##.....................##.......... .#......###....#....#........#.#..#...#.#..#.#...#........................#.........#...#.........#..........#.......#.........#... ..#.....#...........###........#.............#......#......#..........##.......#.#.#....#...#.................#...........#........ .....#........#..#..#................#......#....#.........#.##.......#...........#...........#.#............#.#....#......##...... .....#...##.#.....................#......................................#.#..#.#.....#.......#.#............####.#................ .......#...#......................####..#..#.............#..#.................#.....#...........#............#..#..........#....... .##.............#...#.#...........................#..........##............#.......#.#......#............#........#................ .......#.......#.......#................#......#.#.#...#.............#........#........#.....#.#..............#.................... .#....#......#.#....#.................#.................##..............................#...............#.....###....#......#....#. ........##...............................#........#.............................#.....#..####.............#...#..#.........##.##... .#.#............#..#..........#.......#......##.#.#..........#.........##.....#...........#..................#......##.......#..... .................##.....#.#..............#.#.#.###...#.............#.#....#.....##...#.##..#...........#.#.#....#.................. ..#.#..#..#................................#.#.......##.............#.#..........###................#.....##....#.................. ........#........#.##..#.....##.#........#.#...#..#..#.....#...#....#.#.......#...#.....#..............#.........#.#...#........... ........#.....##..#..#......................#................#...............#...#.#.#..........#.#.##......................#...... ........#......#.....#.#.......#............#...........##...............#............#...........#..........#.#..........#.#...... ......###.....#.................###................#......#........#...#.#.#...#....#.#.........#...#...##........#...#............ ..#.##..#..#....#.....##..........#............#................#.#..#.........................#.##..##..........##....#...#.....#. ....#............#.#..#...#......#..............#..#....##...#..#.....#.........#...#...........#..........#.#......#.#...##.###... ....#................#.........#...............##..#...........#.......#.#..#.......................#....#...##........#........... ....#....................##......#...#...........#.......#.#..#..............##.#....................#....#...................#.... ...#..............##......#..............#...........#.......#......#........##.............#.........#...#.#..##.................. ....#........#.#....#....#.#.....#........#..........................#..#.#.#.#.........#..........#.##...#.##..###.....#.......... .#.......#.#............#..#....#.......#.#............#..........#.#........##.............#...#..#....#..........#..........#.... ...#...#......#..............#...##.......#..........#.....#......##...#..............#................#..............#...##..##... ....#......#.##..##....#.....................#..........#....##......#................#.......#.#..................#......#.#...... ...#...............#..#..........#..#.....#..##............#.......###...........................##................#...#........... ........#....#........#.......#....#..#.#..................#.............##.............#..#.......##..........................#... .#....................#......#.#........#..................#.##.#..#.....#.........##................................#............. .......#....................#..#................#......................................##..........#.....#..##..#..........#.#..#.. ..#.....#..#....#.....#......#..##...#.........#.........................................#...#....#.........#...##.......#.#.....#. ...........#..........#..#.#...#...##..#.........#.#...........#....#..............#.............#.......##..#...#....##.......#... ..#.........#.#..#...#.....#......................#..........#........#.......#....................#...##......#.................#. .#......#...#.#.#......#.#........#.#......#....#....#............................#......####............#.......#..#..........##.. .#......##..........#...#...........#....#...#.#.................................#.##...#......................#..#..........#.#... .....#...#.......#...................##.#....#...##............#..##.........#..................#..#......#..........#....#.....##. .#..................#..........#.....................#.#.........................#...........#...##...#...#...##.#................. .#..#..#..#..#......#........#........#.......#.#...#.#..................#.......#.......#..#.#......#...#...............#.....#... .#........#......................#...##.......#..##......................###......#.....##....#..#................#................ .#...........#.............#..#.....##.........#.##........#.............#....#.#...........#...............#.........#........#... ......#....#.#...###................#....#......#..#........#.........................##.##...#..#..#.#......#..................... ...................................................................................................................................