Tras desembarcar del avión nos queda un último trayecto que debemos hacer para llegar a la isla donde pasaremos las vacaciones: un ferry. Llegamos a la sala de embarque del barco y descubrimos que estamos solos, ya que hemos llegado con mucho tiempo de adelanto y el resto de pasajeros no se ha presentado aún. Para matar el rato nos dedicamos a calcular donde se sentarán los pasajeros en el área de espera antes de embarcar. Este área tiene asientos dispuestos en filas y columnas, y los pasajeros que entran en las sala eligen su asiento en base a unas reglas sencillas. Vamos a ver si acertamos su disposición en este Advent of Code 2020.
Parte 1 – Pasajeros de culo inquieto
Los pasajeros que llegan al área de espera eligen su asiento en varios pasos, basándose en dos reglas que se aplican a todos asientos a la vez en cada paso:
- Si el asiento esta vacío y no hay asientos adyacentes ocupados, lo ocupan
- Si el asiento esta ocupado y cuatro o más asientos adyacentes están ocupados, lo dejan vacío.
Al comenzar todos los asientos están vacíos, así que en el primer paso se ocuparán todos ellos de acuerdo a la primera regla (recuerda que en cada paso se aplican las reglas a todos los asientos a la vez). A partir del siguiente paso la ocupación ira variando de acuerdo a las dos reglas indicadas. Se trata de ejecutar pasos hasta que no haya variaciones en los asientos ocupados, y en ese momento indicar cuantos pasajero sentados hay.
Voy a escribir una clase para representar nuestra área de espera, WaitingArea
:
export class WaitingArea { public seats: string[][]; private rows: number; private cols: number; /** * * @param seatsFile fichero con la definición de asientos de la sala * @param part parte del problema a resolver (1 o 2) */ constructor(seatsFile: string, private part: number) { this.seats = fs .readFileSync(seatsFile, "utf8") .split("\r\n") .map((row) => Array.from(row)); this.rows = this.seats.length; this.cols = this.seats[0].length; } }
Al crear instancias de esta clase le pasaremos la ruta al fichero con la definición de la distribución de los asientos. El constructor parte el fichero en un array bidimensional de caracteres que guarda en la variable this.seats
, donde cada posición contiene la definición de un asiento o espacio libre.
Para poder calcular los siguientes estados lo primero que necesitamos es poder calcular, para un asiento, cuantos asientos adyacentes tiene ocupados. Esta función se encarga de esa tarea:
/** * Calcula el numero de asientos ocupados adyacentes a unod dado * @param seat posicion del asiento */ private occupiedAround = (seat: IPoint) => { if (this.seats[seat.y][seat.x] == ".") return 0; let occupied = 0; for (let y = -1; y < 2; y++) for (let x = -1; x < 2; x++) { if (x != 0 || y != 0) { const check = new Point(seat.x + x, seat.y + y); if ( check.x > -1 && check.y > -1 && check.x < this.cols && check.y < this.rows && this.seats[check.y][check.x] == "#" ) occupied++; } } return occupied; };
Dado un asiento, identificado por sus coordenadas x e y (que paso mediante una instancia de la clase auxiliar Point
, clase que suelo utilizar en tratamientos de arrays bidimensionales) compruebo en un bucle si sus 8 posiciones adyacentes están dentro del array y, de ser así, si esa posición corresponde a un asiento ocupado, indicado por #. En caso positivo añado uno al acumulador que devolveré al salir del bucle.
Ahora ya podemos implementar la función que generará el estado siguiente siguiendo las reglas:
/** * Calcula el siguiente estado de los asientos dependiendo de las reglas */ public computeNextState = (): string[][] => this.seats.map((row, y) => row.map((seat, x) => { const occupiedAround = this.occupiedAround(new Point(x, y)); return seat == "L" && occupiedAround == 0 ? "#" : seat == "#" && occupiedAround > 3; ? "L" : seat; }) );
Esta función recorre todas las posiciones de nuestra sala de espera y para cada una de ellas calcula los asientos adyacentes ocupados. Dependiendo de si la posición actual corresponde a un asiento libre u ocupado y de la ocupación de los adyacentes cambia el estado de este asiento de acuerdo a las reglas o devuelve la posición sin modificar.
Solo nos falta dejar de generar estados una vez que ya no se estén produciendo cambios en la ocupación de los asientos. Para ello debemos contar cuantos asientos utilizados hay en un estado determinado, para lo que añado una propiedad a la clase:
/** * Devuelve el numero de asientos ocupados en la sala */ public get totalOccupiedSeats(): number { return this.seats.reduce( (a, row) => (a += row.reduce((as, seat) => (as += seat == "#" ? 1 : 0), 0)), 0 ); }
Mediante dos bucles implementados con Array.reduce
recorro todas las filas y columnas del array incrementando el acumulador si el asiento de la posición actual está ocupado, es decir, contiene #.
La solución a esta primera parte la resolvemos con un bucle que vaya generando estados hasta que un estado y su anterior tengan el mismo número de asientos ocupados:
const waitingArea = new WaitingArea("./seats.txt", 1); let lastOccupied = -1; // Mientras haya cambios en el numero de asientos ocupados computamos estados while (lastOccupied != waitingArea.totalOccupiedSeats) { lastOccupied = waitingArea.totalOccupiedSeats; waitingArea.seats = waitingArea.computeNextState(); } console.log("Answer:", lastOccupied);
La respuesta coincide con el número de asientos ocupados en el último estado generado en dicho bucle.
Parte 2 – ¡Ese no es su asiento!
En la parte 2 se nos propone una variación a las dos reglas iniciales:
- Si un asiento esta libre se ocupa si todos los asientos que se ven desde ese en cualquier dirección están libres
- Si un asiento esta ocupado, queda libre si al menos 5 asientos que se ven desde el mismo están ocupados.
Es decir, debemos incluir el concepto de línea de visión o line of sight en nuestro algoritmo de la parte 1 y modificar levemente el generador de estados. Puesto que el resto del código va a ser reutilizable, voy a incluir en el constructor de nuestra clase un segundo parámetro para indicar la parte del problema que estamos resolviendo:
constructor(seatsFile: string, private part: number) { .....
Lo primero que vamos a necesitar es una función para, dado un asiento y una de las ocho posibles direcciones desde ese, obtener el siguiente asiento visible:
/ /** * Devuelve el siguiente asiento en la linea de visión desde el asiento seat siguiendo la direccion (vector) dir */ private nextSeatInLOS = (seat: IPoint, dir: IPoint): IPoint => { const check = new Point(seat.x + dir.x, seat.y + dir.y); while ( check.x > -1 && check.y > -1 && check.x < this.cols && check.y < this.rows && this.seats[check.y][check.x] == "." ) { check.x += dir.x; check.y += dir.y; } return check; }; }
No es más que una ampliación de nuestra anterior función pero ahora en vez de limitarnos a comprobar la posición inmediatamente adyacente en una de las 8 direcciones posibles, seguimos avanzando en esa dirección hasta dar con un asiento o salirnos del array.
Modifico la función que devuelve el numero de asientos adyacentes ocupados para que calcule el asiento con este nuevo algoritmo en caso de que estemos resolviendo la parte 2:
/** * Calcula el numero de asientos ocupados adyacentes a uno dado * @param seat posicion del asiento */ private occupiedAround = (seat: IPoint) => { if (this.seats[seat.y][seat.x] == ".") return 0; let occupied = 0; for (let y = -1; y < 2; y++) for (let x = -1; x < 2; x++) { if (x != 0 || y != 0) { const check = this.part == 1 ? new Point(seat.x + x, seat.y + y) : this.nextSeatInLOS(seat, new Point(x, y)); if ( check.x > -1 && check.y > -1 && check.x < this.cols && check.y < this.rows && this.seats[check.y][check.x] == "#" ) occupied++; } } return occupied; };
Como ves la única parte que varía es la obtención del asiento adyacente a comprobar. En la parte 1 comprobábamos el inmediatamente adyacente y en la dos el siguiente visible en la dirección actual.
const check = this.part == 1 ? new Point(seat.x + x, seat.y + y) : this.nextSeatInLOS(seat, new Point(x, y));
Con esto hemos resuelto la modificación a la primera regla. Para modificar la segunda cambio ligeramente el código del generador de estados.
/** * Calcula el siguiente estado de los asientos dependiendo de las reglas */ public computeNextState = (): string[][] => this.seats.map((row, y) => row.map((seat, x) => { const occupiedAround = this.occupiedAround(new Point(x, y)); return seat == "L" && occupiedAround == 0 ? "#" : seat == "#" && occupiedAround > 2 + this.part //4 asientos en la parte 1 y 5 en la parte 2 ? "L" : seat; }) );
Y no son necesarios más cambios, ni siquiera al invocador para obtener la respuesta a esta segunda parte, que es exactamente igual al de la primera.
const waitingArea = new WaitingArea("./seats.txt", 2); let lastOccupied = -1; // Mientras haya cambios en el numero de asientos ocupados computamos estados while (lastOccupied != waitingArea.totalOccupiedSeats) { lastOccupied = waitingArea.totalOccupiedSeats; waitingArea.seats = waitingArea.computeNextState(); } console.log("Answer:", lastOccupied);
Si tienes alguna propuesta para resolver el problema de otra manera o mejorar el código anterior no dudes en dejarme un comentario.