Recently, I've been observing the problem to see if it's troublesome before deciding whether to start writing. I should change this bad habit.
Part1
After reading the problem description, the challenging part is how to determine the movement of the tail and check for adjacency. I directly wrote a simple 2D vector for this.
function isNeighbor(a, b) {
return (
(a.x === b.x ||
a.x - 1 === b.x ||
a.x + 1 === b.x) &&
(a.y === b.y || a.y - 1 === b.y || a.y + 1 === b.y)
);
}Note: After finishing, I realized that I could directly calculate the distance between two points instead of comparing them one by one.
Input Processing
The input is relatively simple. Basically, we map the movements in different directions to vectors:
U: (0, 1)
D: (0, -1)
R: (1, 0)
L: (-1, 0)Logic for Tail Movement
When the head of the rope moves, the tail also moves if they are not adjacent. We can calculate the movement of the tail by finding the angle using dot product. By finding the angle between the unit vectors of x and y, we can determine how the tail should move.
if (!this.head.isNeighbor(this.tail)) {
const vec = this.head.vector(this.tail);
const degree = vec.product(new Point(1, 0)) / vec.length();
const degree2 = vec.product(new Point(0, 1)) / vec.length();
if (degree === 0) {
if (degree2 > 0) {
this.tail.add(0, 1);
} else {
this.tail.add(0, -1);
}
} else if (Math.abs(degree) === 1) {
if (degree === 1) {
this.tail.add(1, 0);
} else {
this.tail.add(-1, 0);
}
} else {
this.tail.add(degree > 0 ? 1 : -1, degree2 > 0 ? 1 : -1);
}
}The problem asks which points the tail has passed through. We can use a Set to achieve this. The complete implementation of the code is as follows:
class Point {
constructor(x, y) {
this.x = x;
this.y = y;
}
isNeighbor(point) {
const vec = new Point(point.x - this.x, point.y - this.y);
return vec.length() <= 1;
}
add(x, y) {
this.x += x;
this.y += y;
}
vector(point) {
return new Point(this.x - point.x, this.y - point.y);
}
length() {
return Math.sqrt(this.x * this.x + this.y * this.y);
}
product(point) {
return point.x * this.x + point.y * this.y;
}
}
class Rope {
constructor(isFirst = false) {
this.isFirst = isFirst;
this.head = new Point(0, 0);
this.tail = new Point(0, 0);
}
move(direction) {
if (this.isFirst) {
switch (direction) {
case "U":
this.head.add(0, 1);
break;
case "D":
this.head.add(0, -1);
break;
case "L":
this.head.add(-1, 0);
break;
case "R":
this.head.add(1, 0);
break;
}
}
if (!this.head.isNeighbor(this.tail)) {
// calculate vector
// move to direction
const vec = this.head.vector(this.tail);
const degree = vec.product(new Point(1, 0)) / vec.length();
const degree2 = vec.product(new Point(0, 1)) / vec.length();
if (degree === 0) {
// horizontal, vertial
if (degree2 > 0) {
this.tail.add(0, 1);
} else {
this.tail.add(0, -1);
}
} else if (Math.abs(degree) === 1) {
if (degree === 1) {
this.tail.add(1, 0);
} else {
this.tail.add(-1, 0);
}
} else {
this.tail.add(degree > 0 ? 1 : -1, degree2 > 0 ? 1 : -1);
}
}
}
}I thought there might be an easter egg in the problem, so I also plotted the coordinates of the rope.
But it seems there's nothing special about it.
Part2
Originally, we only needed to consider the head and tail, but now the rope has a length of 10, so the movement is different. However, the overall logic is still similar. By connecting the head and tail of the rope, we can achieve the desired result.
const ropes = [
new Rope(true),
new Rope(),
new Rope(),
new Rope(),
new Rope(),
new Rope(),
new Rope(),
new Rope(),
new Rope(),
];
const set = new Set();
direction.forEach((dir, ii) => {
const [d, step] = dir.split(" ");
for (let i = 0; i < Number(step); i++) {
ropes.forEach((rope, j) => {
if (j === 0) {
rope.move(d);
} else {
rope.head = ropes[j - 1].tail;
rope.move(d);
}
});
set.add(
`${ropes[ropes.length - 1].tail.x} ${ropes[ropes.length - 1].tail.y}`
);
}
});