Llegamos casi al ecuador de este Advent of Code 2020 embarcando en el ferry que nos llevará a la isla tropical de nuestras soñadas vacaciones. La tormenta de la que habíamos obtenido algunos datos en nuestro hackeo del avión se acerca, y el barco debería comenzar a hacer algunas maniobras para evitarla, pero desgraciadamente el ordenador de navegación no funciona bien y está produciendo instrucciones sin sentido. Acudimos a la llamada del capitán para tratar de ayudar y….
Parte 1 – ¿babor es izquierda o derecha?
La primera parte del puzzle de hoy nos da una lista de movimientos para el barco. Este se puede desplazar al norte, sur, este u oeste un número de posiciones, pero ademas puede girar a izquierda y derecha los grados que nos indiquen o avanzar en la posición en la que esté orientado. El barco comienza en la posición (0,0) orientado hacia el este y la pregunta a contestar es, una vez ejecutados todos los movimientos, cual es la distancia Manhattan del barco a la posición de inicio.
Los movimientos hacia cualquiera dos cuatro puntos cardinales en un mapa bidimensional no tienen ningún misterio, así que me voy a centrar en los giros de orientación y el avance en esa dirección. Voy a crear una clase para representar nuestro barco, en la que mantendré la posición (position
) y orientación (heading
) del mismo:
export class Ship { public movements: string[]; private heading = 90; private position: IPoint = new Point(0, 0); private angles: Record<number, string> = { 0: "N", 90: "E", 180: "S", 270: "W", }; constructor(movementsFile: string) { this.movements = fs.readFileSync(movementsFile, "utf8").split("\r\n"); }
Para la posición hago uso de la clase auxiliar Point
que representa un punto en el espacio bidimensional y que ya utilicé en el problema de ayer. Además voy a utilizar un diccionario para traducir ángulos a nombres de puntos cardinales angles
mediante el uso del tipo Record
.
Lo primero que necesitamos es una función para ejecutar un movimiento dado:
/** * Ejecuta un movimiento sobre el barco * @param direction Nombre del movimiento a ejecutar * @param amount Cantidad */ private move = (direction: string, amount: number) => { if (direction == "F") direction = this.angles[this.heading]; switch (direction) { case "L": this.heading -= amount; if (this.heading < 0) this.heading = 360 + this.heading; break; case "R": this.heading += amount; if (this.heading >= 360) this.heading = this.heading - 360; break; case "N": this.position.y -= amount; break; case "E": this.position.x += amount; break; case "S": this.position.y += amount; break; case "W": this.position.x -= amount; break; } };
Si revisamos el juego de datos de entrada podemos ver que los giros son siempre de 90 grados a izquierda o derecha, por lo que los unicos movimientos posibles son N
, S
, E
o W.
Las instrucciones L
y R
varían la orientación del barco, asegurando que se encuentra siempre entre lo 0 y 359 grados del círculo. El resto de movimientos desplazan el barco en la dirección indicada.
La instrucción F
tiene un tratamiento especial ya que indica que se debe avanzar en la orientación actual, pero debemos traducir previamente esa orientación. Para eso utilizamos el diccionario angles
: antes de comprobar en qué dirección debemos movernos, traducimos heading
a uno de los cuatro puntos cardinales.
Para ejecutar la lista de instrucciones que hemos recibido creo una función que la recorra, pasando cada instrucción individual a nuestra función de movimiento:
/** * Ejecuta la lista de movimientos */ public executeMovements = (): void => this.movements.forEach((movement) => this.move(movement[0], parseInt(movement.substr(1))) );
Una vez ejecutados los movimientos nos falta conocer la distancia Manhattan o métrica del taxista desde la posición actual al origen de coordenadas. Para calcularla incluyo una propiedad en nuestra clase:
/** * Devuelve la distancia Manhattan de la posicion actual a 0,0 */ public get currentManhattanDistanceToStart(): number { return new Segment(new Point(0, 0), this.position).manhattanLength; }
Esta propiedad hace uso de otra clase auxiliar Segment mediante la que se define un segmento de linea desde un punto de inicio a un punto final. La propiedad manhattanLength
de esta clase nos devuelve la longitud Manhattan del segmento y está definida como:
/** * Devuelve la longitud Manhattan del segmento */ get manhattanLength(): number { return ( Math.abs(this.start.x - this.end.x) + Math.abs(this.start.y - this.end.y) ); }
Por último solo nos queda instanciar la clase para utilizarla:
const ship = new Ship("./movements.txt"); ship.executeMovements(); console.log("Answer:", ship.currentManhattanDistanceToStart);
Parte 2 – Grumete, siga ese waypoint
En la segunda parte hay un cambio de las reglas: la única instrucción que afecta al barco es la F
, que provoca que avance hacia un waypoint que está situado en una posición relativa respecto a la nave.
Al inicio el punto de ruta está situado en la posición E10 N1. El resto de instrucciones de la lista le afectan directamente, bien desplazándolo o bien, atención, rotándolo con respecto al barco. La instrucción R rota el punto en el sentido de las agujas del reloj mientras R lo hace en sentido contrario.
Incluyo en la clase una propiedad para almacenar la situación del waypoint:
private waypoint: IPoint = new Point(10, -1);
Para rotar un punto en nuestro espacio bidimensional lo más sencillo es utilizar una matriz de rotación. En mi clase auxiliar Point
añado un método que nos permita rotar el punto respecto del origen de coordenadas siguiendo la formula indicada por el álgebra lineal:
/** * Rota el punto respecto a 0,0 * @param degrees ángulo de rotación en grados */ public rotate = (degrees: number): void => { const rad = (degrees * Math.PI) / 180; const rotatedX = this.x * Math.cos(rad) - this.y * Math.sin(rad); this.y = this.x * Math.sin(rad) + this.y * Math.cos(rad); this.x = rotatedX; };
Ahora que ya podemos rotar el punto voy a modificar la funcion move
para que desplace el barco o el waypoint dependiendo de la instrucción:
/** * Ejecuta una instruccion sobre el barco * @param direction Nombre del movimiento a ejecutar * @param amount Cantidad */ private move = (direction: string, amount: number) => { switch (direction) { case "F": //Mover el barco de acuerdo a la posicion del waypoint this.position.x += this.waypoint.x * amount; this.position.y += this.waypoint.y * amount; break; case "L": this.waypoint.rotate(-amount); break; case "R": this.waypoint.rotate(amount); break; case "N": this.waypoint.y -= amount; break; case "E": this.waypoint.x += amount; break; case "S": this.waypoint.y += amount; break; case "W": this.waypoint.x -= amount; break; } };
Y el resto del programa es el mismo que en la primera parte. De hecho, en el código fuente de github encontrarás que he incluido, al igual que en el ejercicio de ayer, un parámetro part
en el constructor para indicar si queremos ejecutar las reglas de movimientos de la parte 1 o la 2, ya que el resto de código es reutilizable 100%.
Para invocar esta segunda parte:
const ship = new Ship("./movements.txt", 2); ship.executeMovements(); console.log("Answer:", Math.round(ship.currentManhattanDistanceToStart));
El uso de Math.round
se debe a la pérdida de precisión de javascript al calcular senos y cosenos. En vez de calcular cos(0) como 1 lo calcula como 0.99999999999.