If you have any questions or feedback, pleasefill out this form
Table of Contents
This post is translated by ChatGPT and originally written in Mandarin, so there may be some inaccuracies or mistakes.
Recently, I've been observing problems to see if they look too complicated before deciding whether to start coding. I really need to change this bad habit QQ.
Part 1
After reading the problem description, the more challenging part is determining how to move the tail and whether the tail is adjacent. I opted to use 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 implementing this, I realized I could just calculate the distance between the two points, eliminating the need for individual comparisons.
Input Handling
The input is relatively straightforward, essentially mapping movements in each direction to vectors:
U: (0, 1)
D: (0, -1)
R: (1, 0)
L: (-1, 0)Tail Movement Logic
When the head of the rope moves, the tail will also move if it is not adjacent. We can use the dot product to calculate the angle and determine how the tail should move. By calculating the angle with the x unit vector and the y unit vector, we can ascertain the tail's movement direction.
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 task asks which points the tail has visited, which can be easily accomplished using a Set. The complete implementation 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, vertical
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 was curious if there might be any hidden surprises in the problem, specifically if the shape created by the tail would form any specific image, so I plotted the rope's coordinates as well.
However, it seems there isn’t anything particularly special.
Part 2
Initially, we only needed to consider the head and the tail, but now that the length of the rope is 10, the movement dynamics will change a bit. Nevertheless, the overall logic remains quite similar; we can achieve this by connecting the original Rope's head and tail together.
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}`
);
}
});If you found this article helpful, please consider buying me a coffee ☕ It'll make my ordinary day shine ✨
☕Buy me a coffee