Part 1
Task
This rope bridge creaks as you walk along it. You aren't sure how old it is, or whether it can even support your weight.
It seems to support the Elves just fine, though. The bridge spans a gorge which was carved out by the massive river far below you.
You step carefully; as you do, the ropes stretch and twist. You decide to distract yourself by modeling rope physics; maybe you can even figure out where not to step.
Consider a rope with a knot at each end; these knots mark the head and the tail of the rope. If the head moves far enough away from the tail, the tail is pulled toward the head.
Due to nebulous reasoning involving Planck lengths, you should be able to model the positions of the knots on a two-dimensional grid. Then, by following a hypothetical series of motions (your puzzle input) for the head, you can determine how the tail will move.
Due to the aforementioned Planck lengths, the rope must be quite short; in fact, the head (
H) and tail (T) must always be touching (diagonally adjacent and even overlapping both count as touching):.... .TH. .... .... .H.. ..T. .... ... .H. (H covers T) ...If the head is ever two steps directly up, down, left, or right from the tail, the tail must also move one step in that direction so it remains close enough:
..... ..... ..... .TH.. -> .T.H. -> ..TH. ..... ..... ..... ... ... ... .T. .T. ... .H. -> ... -> .T. ... .H. .H. ... ... ...Otherwise, if the head and tail aren't touching and aren't in the same row or column, the tail always moves one step diagonally to keep up:
..... ..... ..... ..... ..H.. ..H.. ..H.. -> ..... -> ..T.. .T... .T... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..H.. -> ...H. -> ..TH. .T... .T... ..... ..... ..... .....You just need to work out where the tail goes as the head follows a series of motions. Assume the head and the tail both start at the same position, overlapping.
For example:
R 4 U 4 L 3 D 1 R 4 D 1 L 5 R 2This series of motions moves the head right four steps, then up four steps, then left three steps, then down one step, and so on. After each step, you'll need to update the position of the tail if the step means the head is no longer adjacent to the tail. Visually, these motions occur as follows (
smarks the starting position as a reference point):== Initial State == ...... ...... ...... ...... H..... (H covers T, s) == R 4 == ...... ...... ...... ...... TH.... (T covers s) ...... ...... ...... ...... sTH... ...... ...... ...... ...... s.TH.. ...... ...... ...... ...... s..TH. == U 4 == ...... ...... ...... ....H. s..T.. ...... ...... ....H. ....T. s..... ...... ....H. ....T. ...... s..... ....H. ....T. ...... ...... s..... == L 3 == ...H.. ....T. ...... ...... s..... ..HT.. ...... ...... ...... s..... .HT... ...... ...... ...... s..... == D 1 == ..T... .H.... ...... ...... s..... == R 4 == ..T... ..H... ...... ...... s..... ..T... ...H.. ...... ...... s..... ...... ...TH. ...... ...... s..... ...... ....TH ...... ...... s..... == D 1 == ...... ....T. .....H ...... s..... == L 5 == ...... ....T. ....H. ...... s..... ...... ....T. ...H.. ...... s..... ...... ...... ..HT.. ...... s..... ...... ...... .HT... ...... s..... ...... ...... HT.... ...... s..... == R 2 == ...... ...... .H.... (H covers T) ...... s..... ...... ...... .TH... ...... s.....After simulating the rope, you can count up all of the positions the tail visited at least once. In this diagram,
sagain marks the starting position (which the tail also visited) and#marks other positions the tail visited:..##.. ...##. .####. ....#. s###..So, there are
13positions the tail visited at least once.Simulate your complete hypothetical series of motions. How many positions does the tail of the rope visit at least once?
Solution
We will use the
Directionenum andPositionclass from the day 8 solution.We will convert our instructions into a list of
DirectionandIntegerpairs.We will use the
foldfunction to iterate over our input and calculate our steps.For each instruction, we will run a loop that will move the head, and check if the tail needs to be moved.
At the end of each iteration, the tail location would be updated on our map.
finally, we will count the number of keys on our map. Those keys represent the number of locations the tails have visited at least once.
We have a lot to do, so let's start!
Parsing the input
To parse our input, we first define the helper function that will convert our input letter (R, L, U, and D) to a Direction value:
enum class Direction(val dx: Int, val dy: Int) {
Up(dx = 0, dy = -1),
Right(dx = 1, dy = 0),
Down(dx = 0, dy = 1),
Left(dx = -1, dy = 0);
companion object {
fun fromChar(dir: Char): Direction =
when (dir.uppercaseChar()) {
'R' -> Right
'U' -> Up
'L' -> Left
'D' -> Down
else -> throw IllegalArgumentException("Unknown direction: $dir")
}
}
}
Now, we will take each like in the code, and split it using the empty space character (" "). We will then take the list of 2 parts, and build a pair of Direction to Integer that represents the number of steps:
private fun List<String>.toDirection(): Pair<Direction, Int> {
require(this.size == 2) { "Instructions should include exactly 2 parts, but was: $this" }
return Direction.fromChar(this[0].first()) to this[1].toInt()
}
fun solvePart1(): Int {
input
.filter { it.isNotBlank() }
.map { it.split(" ").toDirection() }
// ... the rest of our code
}
Solution business logic
Now the main part of this challenge. the fold function. This function will go over our input list and accumulate it according to the function we will provide it. It will receive an initialized value and use that for the accumulation.
As mentioned before, our initializer would be a pair of HashMap and MutableList. The HashMap would map Position to a Char. We will mark a place that the tail visited with s for the start point or # for the visit. While the list will contain the latest state of our chain. As the list represents the entire bridge, we will initialize it with 2 elements in the position (0, 0).
private val initializer = HashMap<Position, Char>()
.apply {
this[Position.POSITION_ZERO] = 's'
} to MutableList(2) { Position.POSITION_ZERO }
Our fold function will now use this initializer. It would take the Direction and steps to make from each command, and calculate the new positions of the tail:
fun solvePart1(): Int {
input
.filter { it.isNotBlank() }
.map { it.split(" ").toDirection() }
.fold(initializer) { acc, pair ->
val (direction, steps) = pair
updateNewPositions(
direction = direction,
steps = steps,
positions = acc.first,
partsOfChain = acc.second
)
}
// ... the rest of our code
}
Let's now look at the updateNewPositions() function, and how it works.
The function takes 4 arguments:
The direction of the head.
The number of steps to move the head.
Map of all positions of the tail to update.
list of the current state of the rope to update for the next iteration.
private fun updateNewPositions1(
direction: Direction,
steps: Int,
positions: HashMap<Position, Char>,
partsOfChain: MutableList<Position>,
): Pair<HashMap<Position, Char>, MutableList<Position>> {
repeat(steps) {
val head = partsOfChain.first()
val tail = partsOfChain.last()
partsOfChain[0] = head.move(direction)
partsOfChain[1] = getNewPartPosition(tail, head)
positions[partsOfChain.last()] = '#'
}
return positions to partsOfChain
}
Let's now have a deeper look at the function getNewPartPosition(). This function decides whether our tail needs to move or not.
The function would check if the
headandtailare in the same position, or if thetailis one of thehead's neighbors. In such a case, it would return thetailwithout changing its location.Otherwise, it will calculate the delta on the
XandYaxis between theheadandtail. It will then move the tail 1 step diagonally in that direction. That means that both theXandYaxis can change in the range of-1 to 1.
private fun getNewPartPosition(tail: Position, head: Position) =
if (head == tail || tail in Position.allNeighbors(head, includeDiagonals = true)) tail
else Position(
x = tail.x + (head.x - tail.x).sign,
y = tail.y + (head.y - tail.y).sign
)
The allNeighbors() method is a companion method of the Position class. It collects all the delta's for the near neighbors of a position, and build a list of the given position neighbors:
data class Position(val x: Int, val y: Int) {
// ... same code as in day 8 solution
companion object {
val POSITION_ZERO = Position(x = 0, y = 0)
fun allDeltas(includeDiagonals: Boolean = false): List<Position> {
val results = mutableListOf<Position>()
for (dy in -1..1) {
for (dx in -1..1) {
if (dy == 0 && dx == 0) continue
if (includeDiagonals || dy == 0 || dx == 0) {
results.add(Position(dx, dy))
}
}
}
return results
}
fun allNeighbors(position: Position, includeDiagonals: Boolean = false): List<Position> =
allDeltas(includeDiagonals)
.map { delta ->
Position(position.x + delta.x, position.y + delta.y)
}
}
}
Finally, we can take all of the keys in the HashMap, count them, and that's our answer!
Our final pipeline would look like that:
fun solvePart1() : Int =
input
.filter { it.isNotBlank() }
.map { it.split(" ").toDirection() }
.fold(initializer(size)) { acc, pair ->
val (direction, steps) = pair
updateNewPositions(
direction = direction,
steps = steps,
positions = acc.first,
partsOfChain = acc.second,
)
}
.first.keys.size
Let's run our test cases:
@Test
fun `Part 1 - Example`() {
val day09 = Day09(exampleInput1)
assertEquals(13, day09.solvePart1())
}
@Test
fun `Part 1 - Real Input`() {
val day09 = Day09(resourceAsList("2022/day09.txt"))
assertEquals(5960, day09.solvePart1())
}
Part 2
Task
A rope snaps! Suddenly, the river is getting a lot closer than you remember. The bridge is still there, but some of the ropes that broke are now whipping toward you as you fall through the air!
The ropes are moving too quickly to grab; you only have a few seconds to choose how to arch your body to avoid being hit. Fortunately, your simulation can be extended to support longer ropes.
Rather than two knots, you now must simulate a rope consisting of ten knots. One knot is still the head of the rope and moves according to the series of motions. Each knot further down the rope follows the knot in front of it using the same rules as before.
Using the same series of motions as the above example, but with the knots marked
H,1,2, ...,9, the motions now occur as follows:== Initial State == ...... ...... ...... ...... H..... (H covers 1, 2, 3, 4, 5, 6, 7, 8, 9, s) == R 4 == ...... ...... ...... ...... 1H.... (1 covers 2, 3, 4, 5, 6, 7, 8, 9, s) ...... ...... ...... ...... 21H... (2 covers 3, 4, 5, 6, 7, 8, 9, s) ...... ...... ...... ...... 321H.. (3 covers 4, 5, 6, 7, 8, 9, s) ...... ...... ...... ...... 4321H. (4 covers 5, 6, 7, 8, 9, s) == U 4 == ...... ...... ...... ....H. 4321.. (4 covers 5, 6, 7, 8, 9, s) ...... ...... ....H. .4321. 5..... (5 covers 6, 7, 8, 9, s) ...... ....H. ....1. .432.. 5..... (5 covers 6, 7, 8, 9, s) ....H. ....1. ..432. .5.... 6..... (6 covers 7, 8, 9, s) == L 3 == ...H.. ....1. ..432. .5.... 6..... (6 covers 7, 8, 9, s) ..H1.. ...2.. ..43.. .5.... 6..... (6 covers 7, 8, 9, s) .H1... ...2.. ..43.. .5.... 6..... (6 covers 7, 8, 9, s) == D 1 == ..1... .H.2.. ..43.. .5.... 6..... (6 covers 7, 8, 9, s) == R 4 == ..1... ..H2.. ..43.. .5.... 6..... (6 covers 7, 8, 9, s) ..1... ...H.. (H covers 2) ..43.. .5.... 6..... (6 covers 7, 8, 9, s) ...... ...1H. (1 covers 2) ..43.. .5.... 6..... (6 covers 7, 8, 9, s) ...... ...21H ..43.. .5.... 6..... (6 covers 7, 8, 9, s) == D 1 == ...... ...21. ..43.H .5.... 6..... (6 covers 7, 8, 9, s) == L 5 == ...... ...21. ..43H. .5.... 6..... (6 covers 7, 8, 9, s) ...... ...21. ..4H.. (H covers 3) .5.... 6..... (6 covers 7, 8, 9, s) ...... ...2.. ..H1.. (H covers 4; 1 covers 3) .5.... 6..... (6 covers 7, 8, 9, s) ...... ...2.. .H13.. (1 covers 4) .5.... 6..... (6 covers 7, 8, 9, s) ...... ...... H123.. (2 covers 4) .5.... 6..... (6 covers 7, 8, 9, s) == R 2 == ...... ...... .H23.. (H covers 1; 2 covers 4) .5.... 6..... (6 covers 7, 8, 9, s) ...... ...... .1H3.. (H covers 2, 4) .5.... 6..... (6 covers 7, 8, 9, s)Now, you need to keep track of the positions the new tail,
9, visits. In this example, the tail never moves, and so it only visits1position. However, be careful: more types of motion are possible than before, so you might want to visually compare your simulated rope to the one above.Here's a larger example:
R 5 U 8 L 8 D 3 R 17 D 10 L 25 U 20These motions occur as follows (individual steps are not shown):
== Initial State == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ...........H.............. (H covers 1, 2, 3, 4, 5, 6, 7, 8, 9, s) .......................... .......................... .......................... .......................... .......................... == R 5 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ...........54321H......... (5 covers 6, 7, 8, 9, s) .......................... .......................... .......................... .......................... .......................... == U 8 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... ................H......... ................1......... ................2......... ................3......... ...............54......... ..............6........... .............7............ ............8............. ...........9.............. (9 covers s) .......................... .......................... .......................... .......................... .......................... == L 8 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... ........H1234............. ............5............. ............6............. ............7............. ............8............. ............9............. .......................... .......................... ...........s.............. .......................... .......................... .......................... .......................... .......................... == D 3 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .........2345............. ........1...6............. ........H...7............. ............8............. ............9............. .......................... .......................... ...........s.............. .......................... .......................... .......................... .......................... .......................... == R 17 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ................987654321H .......................... .......................... .......................... .......................... ...........s.............. .......................... .......................... .......................... .......................... .......................... == D 10 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ...........s.........98765 .........................4 .........................3 .........................2 .........................1 .........................H == L 25 == .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ...........s.............. .......................... .......................... .......................... .......................... H123456789................ == U 20 == H......................... 1......................... 2......................... 3......................... 4......................... 5......................... 6......................... 7......................... 8......................... 9......................... .......................... .......................... .......................... .......................... .......................... ...........s.............. .......................... .......................... .......................... .......................... ..........................Now, the tail (
9) visits36positions (includings) at least once:.......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... #......................... #.............###......... #............#...#........ .#..........#.....#....... ..#..........#.....#...... ...#........#.......#..... ....#......s.........#.... .....#..............#..... ......#............#...... .......#..........#....... ........#........#........ .........########.........Simulate your complete series of motions on a larger rope with ten knots. How many positions does the tail of the rope visit at least once?
Solution
Our current solution is almost a perfect match. We just need to refactor it a bit. Let's have a look at the refactoring we need to make:
Our initializer should now get the size of the rope, instead of hard coding it to the value of
2.The
updateNewPositions()would need to update the entire rope, and not only theheadandtail.
Let's start with the refactoring. Our new initializer is now a function, that receives the rope length:
private fun initializer(size: Int) = HashMap<Position, Char>()
.apply {
this[Position.POSITION_ZERO] = 's'
} to MutableList(size) { Position.POSITION_ZERO }
Our updateNewPositions() will now start by moving the head of the rope, and for each part of the rope get the new position of this part. After all parts have been moved, we will update the location of the tail just like before.
private fun updateNewPositions(
steps: Int,
positions: HashMap<Position, Char>,
partsOfChain: MutableList<Position>,
direction: Direction
): Pair<HashMap<Position, Char>, MutableList<Position>> {
repeat(steps) {
// Moving the head
partsOfChain[0] = partsOfChain.first().move(direction)
for (i in 1 until partsOfChain.size) {
// Moving rest of parts
partsOfChain[i] = getNewPartPosition(
tail = partsOfChain[i],
head = partsOfChain[i - 1]
)
}
positions[partsOfChain.last()] = '#'
}
return positions to partsOfChain
}
We can now extract the implementation of solvePart1() into a shared function that could be used by both part 1 and part 2 of the question:
private fun simulateRope(size: Int) =
input
.filter { it.isNotBlank() }
.map { it.split(" ").toDirection() }
.fold(initializer(size)) { acc, pair ->
val (direction, steps) = pair
updateNewPositions(
direction = direction,
steps = steps,
positions = acc.first,
partsOfChain = acc.second,
)
}
.first.keys.size
fun solvePart1() = simulateRope(2)
fun solvePart2() = simulateRope(10)
That's it. We're done!
Let's run our tests 🎉
@Test
fun `Part 2 - Example1`() {
val day09 = Day09(exampleInput1)
assertEquals(1, day09.solvePart2())
}
@Test
fun `Part 2 - Example2`() {
val day09 = Day09(exampleInput2)
assertEquals(36, day09.solvePart2())
}
@Test
fun `Part 2 - Real Input`() {
val day09 = Day09(resourceAsList("2022/day09.txt"))
assertEquals(2327, day09.solvePart2())
}
All of the code that was presented in the article, along with the utility classes that are used are available in my GitHub account.
See you on the next challenge!
Links
- The code of this post is available here.
Top comments (0)