Day 9: Rope Bridge

[simonw]

https://adventofcode.com/2022/day/9

Wow this one is a bit complicated. I'm modelling a rope with a head and tail. The head moves around - the tail follows.

Moves example:

R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2

H is rope head, T is rope tail, s is the starting position:

== 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.....

etc.

How many positions does the tail of the rope visit at least once?

For the example the answer is 13.

[simonw]

Example board is 6 wide, 5 high.

But... there are values in input.txt higher than that, so assume that there's no bounds on the board.

[simonw]

Movement rules:

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:

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:

[...]

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.

[simonw]

I need to model the state of the board, then loop through each move in turn applying it to the head. After each move is applied to the head I can run code which decides if the tail should be updated or not - and logs the co-ordinates that the tail has visited so I can count them at the end.

[simonw]

I got 14 against the example. I stopped counting the starting point as somewhere visited by the tail and got the expected answer 13.

Then I tried against input.txt and got the right answer, 6339.

CORRECTION: That's because I modified example.txt to add a 1 up 1 right as a test and forgot to remove that again. You actually SHOULD count the 0, 0 square.

[simonw]

Output against example.txt:

day_09 % cargo run
   Compiling day_09 v0.1.0 (/Users/simon/Dropbox/Development/advent-of-code-2022-in-rust/day_09)
    Finished dev [unoptimized + debuginfo] target(s) in 0.49s
     Running `target/debug/day_09`
X.........
..........
..........
..........
..........
..........
..........
..........
..........
..........
direction = R distance = 4
  head_pos = (1, 0)
  Touching, no need to move
TH........
..........
..........
..........
..........
..........
..........
..........
..........
..........
  head_pos = (2, 0)
  tail_pos = (1, 0)
.TH.......
..........
..........
..........
..........
..........
..........
..........
..........
..........
  head_pos = (3, 0)
  tail_pos = (2, 0)
..TH......
..........
..........
..........
..........
..........
..........
..........
..........
..........
  head_pos = (4, 0)
  tail_pos = (3, 0)
...TH.....
..........
..........
..........
..........
..........
..........
..........
..........
..........
direction = U distance = 4
  head_pos = (4, 1)
  Diagonally touching, no need to move
...T......
....H.....
..........
..........
..........
..........
..........
..........
..........
..........
  head_pos = (4, 2)
  tail_pos = (4, 1)
..........
....T.....
....H.....
..........
..........
..........
..........
..........
..........
..........
  head_pos = (4, 3)
  tail_pos = (4, 2)
..........
..........
....T.....
....H.....
..........
..........
..........
..........
..........
..........
  head_pos = (4, 4)
  tail_pos = (4, 3)
..........
..........
..........
....T.....
....H.....
..........
..........
..........
..........
..........
direction = L distance = 3
  head_pos = (3, 4)
  Diagonally touching, no need to move
..........
..........
..........
....T.....
...H......
..........
..........
..........
..........
..........
  head_pos = (2, 4)
  tail_pos = (3, 4)
..........
..........
..........
..........
..HT......
..........
..........
..........
..........
..........
  head_pos = (1, 4)
  tail_pos = (2, 4)
..........
..........
..........
..........
.HT.......
..........
..........
..........
..........
..........
direction = D distance = 1
  head_pos = (1, 3)
  Diagonally touching, no need to move
..........
..........
..........
.H........
..T.......
..........
..........
..........
..........
..........
direction = R distance = 4
  head_pos = (2, 3)
  Touching, no need to move
..........
..........
..........
..H.......
..T.......
..........
..........
..........
..........
..........
  head_pos = (3, 3)
  Diagonally touching, no need to move
..........
..........
..........
...H......
..T.......
..........
..........
..........
..........
..........
  head_pos = (4, 3)
  tail_pos = (3, 3)
..........
..........
..........
...TH.....
..........
..........
..........
..........
..........
..........
  head_pos = (5, 3)
  tail_pos = (4, 3)
..........
..........
..........
....TH....
..........
..........
..........
..........
..........
..........
direction = D distance = 1
  head_pos = (5, 2)
  Diagonally touching, no need to move
..........
..........
.....H....
....T.....
..........
..........
..........
..........
..........
..........
direction = L distance = 5
  head_pos = (4, 2)
  Touching, no need to move
..........
..........
....H.....
....T.....
..........
..........
..........
..........
..........
..........
  head_pos = (3, 2)
  Diagonally touching, no need to move
..........
..........
...H......
....T.....
..........
..........
..........
..........
..........
..........
  head_pos = (2, 2)
  tail_pos = (3, 2)
..........
..........
..HT......
..........
..........
..........
..........
..........
..........
..........
  head_pos = (1, 2)
  tail_pos = (2, 2)
..........
..........
.HT.......
..........
..........
..........
..........
..........
..........
..........
  head_pos = (0, 2)
  tail_pos = (1, 2)
..........
..........
HT........
..........
..........
..........
..........
..........
..........
..........
direction = R distance = 2
  head_pos = (1, 2)
  tail_pos = (1, 2)
..........
..........
.X........
..........
..........
..........
..........
..........
..........
..........
  head_pos = (2, 2)
  Touching, no need to move
..........
..........
.TH.......
..........
..........
..........
..........
..........
..........
..........
tail_visited = [(0, 0), (1, 0), (2, 0), (3, 0), (4, 1), (4, 2), (4, 3), (3, 4), (2, 4), (3, 3), (4, 3), (3, 2), (2, 2), (1, 2), (1, 2)]
Number of unique locations = 13

[simonw]

Part 2:

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.

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?

[simonw]

Got it to work against the larger example AND got the right result for my input - 2541.

I modified the original script without creating a backup, so now my solution to part 1 lives on in version control:

advent-of-code-2022-in-rust/day_09/src/main.rs

Lines 1 to 98 in b46f205

	use std::fs;
	fn main() {
	let file_contents = fs::read_to_string("input.txt").unwrap();
	let mut head_pos: (i32, i32) = (0, 0);
	let mut tail_pos: (i32, i32) = (0, 0);
	let mut tail_visited = Vec::new();
	tail_visited.push(tail_pos);
	print_board(&head_pos, &tail_pos);
	for line in file_contents.lines() {
	// Line is "R 4" - split into move, distance (integer)
	let mut parts = line.split(" ");
	let direction = parts.next().unwrap();
	let distance = parts.next().unwrap().parse::<i32>().unwrap();
	println!("direction = {} distance = {}", direction, distance);
	// First move the head
	for _ in 0..distance {
	match direction {
	"R" => head_pos.0 += 1,
	"L" => head_pos.0 -= 1,
	"U" => head_pos.1 += 1,
	"D" => head_pos.1 -= 1,
	_ => panic!("Unknown direction {}", direction),
	}
	println!(" head_pos = {:?}", head_pos);
	// Now move the tail, if it needs to be moved
	// Is tail within one of head in either direction?
	if (head_pos.0 == tail_pos.0 && (head_pos.1 - tail_pos.1).abs() == 1)
	|| (head_pos.1 == tail_pos.1 && (head_pos.0 - tail_pos.0).abs() == 1)
	{
	println!(" Touching, no need to move");
	}
	// Are tail and head diagonally touching?
	else if (head_pos.0 - tail_pos.0).abs() == 1 && (head_pos.1 - tail_pos.1).abs() == 1 {
	println!(" Diagonally touching, no need to move");
	} else {
	// Need to move the tail
	// If tail is not in same row AND column as head...
	if head_pos.0 != tail_pos.0 && head_pos.1 != tail_pos.1 {
	// Move it diagonally in the right direction
	tail_pos.0 += to_one(head_pos.0 - tail_pos.0);
	tail_pos.1 += to_one(head_pos.1 - tail_pos.1);
	} else {
	// Move it in the right direction
	if head_pos.0 == tail_pos.0 {
	tail_pos.1 += to_one(head_pos.1 - tail_pos.1);
	} else {
	tail_pos.0 += to_one(head_pos.0 - tail_pos.0);
	}
	}
	println!(" tail_pos = {:?}", tail_pos);
	tail_visited.push(tail_pos);
	}
	print_board(&head_pos, &tail_pos);
	}
	}
	println!("tail_visited = {:?}", tail_visited);
	// Count unique tuples in that
	let mut unique_tuples = Vec::new();
	for tuple in tail_visited {
	if !unique_tuples.contains(&tuple) {
	unique_tuples.push(tuple);
	}
	}
	println!("Number of unique locations = {:?}", unique_tuples.len());
	}
	fn print_board(head_pos: &(i32, i32), tail_pos: &(i32, i32)) {
	for y in 0..10 {
	for x in 0..10 {
	// If both in same spot do an X
	if x == head_pos.0 && y == head_pos.1 && x == tail_pos.0 && y == tail_pos.1 {
	print!("X");
	} else if x == head_pos.0 && y == head_pos.1 {
	print!("H");
	} else if x == tail_pos.0 && y == tail_pos.1 {
	print!("T");
	} else {
	print!(".");
	}
	}
	println!("");
	}
	}
	fn to_one(n: i32) -> i32 {
	if n > 0 {
	1
	} else if n < 0 {
	-1
	} else {
	0
	}
	}

Here's my part 2 solution:

advent-of-code-2022-in-rust/day_09/src/main.rs

Lines 1 to 108 in 58aae1d

	use std::fs;
	fn main() {
	let file_contents = fs::read_to_string("input.txt").unwrap();
	let mut knots: Vec<(i32, i32)> = Vec::new();
	for _ in 0..10 {
	knots.push((0, 0));
	}
	let mut tail_visited: Vec<(i32, i32)> = Vec::new();
	tail_visited.push((0, 0));
	// print_board(&knots);
	for line in file_contents.lines() {
	// Line is "R 4" - split into move, distance (integer)
	let mut parts = line.split(" ");
	let direction = parts.next().unwrap();
	let distance = parts.next().unwrap().parse::<i32>().unwrap();
	println!("direction = {} distance = {}", direction, distance);
	// First move the head
	for _ in 0..distance {
	match direction {
	"R" => knots[0].0 += 1,
	"L" => knots[0].0 -= 1,
	"U" => knots[0].1 += 1,
	"D" => knots[0].1 -= 1,
	_ => panic!("Unknown direction {}", direction),
	}
	println!(" head_pos = {:?}", knots[0]);
	// Now move each other knot in turn, if it needs to be moved
	for i in 1..knots.len() {
	// Is knot within one of head in either direction?
	let mut knot = knots[i];
	let prev = knots[i - 1];
	if (prev.0 == knot.0 && (prev.1 - knot.1).abs() == 1)
	|| (prev.1 == knot.1 && (prev.0 - knot.0).abs() == 1)
	{
	println!(" Touching, no need to move");
	}
	// Are tail and head diagonally touching?
	else if (prev.0 - knot.0).abs() == 1 && (prev.1 - knot.1).abs() == 1 {
	println!(" Diagonally touching, no need to move");
	} else {
	// Need to move the tail
	// If tail is not in same row AND column as head...
	if prev.0 != knot.0 && prev.1 != knot.1 {
	// Move it diagonally in the right direction
	knot.0 += to_one(prev.0 - knot.0);
	knot.1 += to_one(prev.1 - knot.1);
	} else {
	// Move it in the right direction
	if prev.0 == knot.0 {
	knot.1 += to_one(prev.1 - knot.1);
	} else {
	knot.0 += to_one(prev.0 - knot.0);
	}
	}
	knots[i] = knot;
	println!(" knot = {:?}", knot);
	if i == 9 {
	tail_visited.push(knot);
	}
	}
	}
	// print_board(&head_pos, &tail_pos);
	}
	}
	println!("tail_visited = {:?}", tail_visited);
	// Count unique tuples in that
	let mut unique_tuples = Vec::new();
	for tuple in tail_visited {
	if !unique_tuples.contains(&tuple) {
	unique_tuples.push(tuple);
	}
	}
	println!("Number of unique locations = {:?}", unique_tuples.len());
	}
	/*
	fn print_board(knots: &knot) {
	for y in 0..10 {
	for x in 0..10 {
	// If both in same spot do an X
	if x == head_pos.0 && y == head_pos.1 && x == tail_pos.0 && y == tail_pos.1 {
	print!("X");
	} else if x == head_pos.0 && y == head_pos.1 {
	print!("H");
	} else if x == tail_pos.0 && y == tail_pos.1 {
	print!("T");
	} else {
	print!(".");
	}
	}
	println!("");
	}
	}
	*/
	fn to_one(n: i32) -> i32 {
	if n > 0 {
	1
	} else if n < 0 {
	-1
	} else {
	0
	}
	}