Nos dirigimos a tomar un tren para alcanzar un nuevo vuelo cuando nos damos cuenta de que el ticket del mismo está escrito en un lenguaje que no entendemos. Este día 16 del advent of code 2020 nos propone que, a a partir de los números de nuestro ticket y del contenido de los tickets de los pasajeros cercanos, así como la reglas que debe cumplir cada valor, identifiquemos los campos en el ticket .
Parte 1 – Ese ticket no parece válido….
La primera tarea se trata de localizar campos en los tickets que conocemos que no sean válidos. Para ello contamos con tres entradas de datos:
- Una lista de campos con las reglas que deben cumplir sus valores. Por ejemplo, sabremos que el campo
asiento
puede tener como valores desde el0 al 7
y desde el15 al 30
. - La información de los valores de nuestro ticket, una lista de números separados por comas
- La información de los valores de los tickets del resto de pasajeros, con el mismo formato que el nuestro.
Lo primero que necesitamos es representar estos conceptos en nuestro programa. Como son sencillos creo tres interfaces simples (podrían haber sido tipos):
interface ITicket { fields: number[]; } interface ILimit { from: number; to: number; } interface IFieldRule { name: string; limits: ILimit[]; }
ITicket
representa un ticket, una serie de valores correspondientes a los campos del billete. IFieldRule
representa la definición de un campo, con su nombre y límites de valores. El parseo del fichero es hoy más largo de lo habitual:
export class TicketsChecker { private rules: IFieldRule[]; private ownTicket: ITicket = { fields: [] }; private nearbyTickets: ITicket[]; // Cachea toda la coleccion de limites de todas las reglas private allLimits: ILimit[]; constructor(ticketsFile: string) { //Lee el fichero de entrada y genera las colecciones de objetos que representan cada parte const sections = fs.readFileSync(ticketsFile, "utf8").split("\r\n\r\n"); const reLimits = /(\d+)-(\d+)/g; this.rules = sections[0].split("\r\n").map((line) => { const parts = line.split(": "); const rule: IFieldRule = { name: parts[0], limits: [], matchingPositions: [], }; let match = reLimits.exec(parts[1]); while (match) { rule.limits.push({ from: parseInt(match[1]), to: parseInt(match[2]) }); match = reLimits.exec(parts[1]); } return rule; }); this.ownTicket.fields = sections[1] .split("\r\n")[1] .split(",") .map((n) => parseInt(n)); this.nearbyTickets = sections[2] .split("\r\n") .slice(1) .map((ticket) => ({ fields: ticket.split(",").map((n) => parseInt(n)) })); this.allLimits = this.rules.flatMap((rule) => rule.limits); }
Adicionalmente a los objetos leidos del fichero , almaceno en la propiedad allLimits la colección
de todos los limites de todos los campos posibles. Encontrar los campos que no cumplen ninguna regla supone verificar dichos campos contra todas las posibles reglas, por lo que cachear esta información va a ser útil para la función que comprueba si un determinado valor de campo es válido:
/** * Indica si el campo es invalido (no cumple NINGUNA regla) * @param field Valor del campo */ isFieldInvalid = (field: number): boolean => !this.allLimits.some((limit) => field >= limit.from && field <= limit.to);
Haciendo uso de esta función encontrar la lista de campos inválidos es tan sencillo como filtra la lista de todos los campos de todos los tickets:
/** * Encuentra los valores que son invalidos para cualquier regla en los tickets cercanos */ public findInvalidFields = (): number[] => this.nearbyTickets .flatMap((ticket) => ticket.fields) .filter((field) => this.isFieldInvalid(field));
Y para finalizar la primera parte solo hay que devolver la suma de los valores de los campos inválidos:
const ticketsChecker = new TicketsChecker("./tickets.txt"); const invalidFields = ticketsChecker.findInvalidFields(); console.log( "Answer:", invalidFields.reduce((a, b) => (a += b), 0) );
Parte 2 – ¿Esto es la fila o el asiento?
Una vez eliminados los tickets que contienen campos inválidos debemos averiguar qué valores corresponden a qué campos, teniendo en cuenta que en todos los billetes los campos aparecen en la misma posición.
Lo primero es eliminar los tickets inválidos de nuestra lista,lo que podemos hacer usando la función de la primera parte, ya que un billete no es válido si cualquiera de sus campos no lo es:
/** * Indica si el ticket pasado es inválido segun el valor de sus campos * @param ticket ticket a comporbar */ private isTicketInvalid = (ticket: ITicket): boolean => ticket.fields.some((field) => this.isFieldInvalid(field));
Ahora debemos ver cuales son las posiciones posibles de cada campo. Para ello añado un campo al interface IFieldRule
donde almacenaré dichas posibilidades:
interface IFieldRule { name: string; limits: ILimit[]; matchingPositions: number[]; }
Un campo puede ocupar una posición si todos los valores de los tickets en esa posición cumplen las reglas del campo. Añado una función auxiliar que verifique un valor de campo contra una regla, y la utilizo para todos los valores de los billetes de una posición determinada y todas las reglas existentes:
/** * Indica si el valor de un campo cumple con la regla indicada */ isFieldValidForRule = (field: number, rule: IFieldRule): boolean => rule.limits.some((limit) => field >= limit.from && field <= limit.to); /** * Encuentra las columnas a las que pertenece cada regla */ private findFieldsPosition = (): void => { const validTickets = this.nearbyTickets.filter( (ticket) => !this.isTicketInvalid(ticket) ); // Encontrar todas las posiciones de las columnas que cuadran con cada regla this.rules.forEach((_f, columnIndex) => { const fieldsInColumn = validTickets.map( (ticket) => ticket.fields[columnIndex] ); this.rules.forEach((rule) => { if ( fieldsInColumn.every((field) => this.isFieldValidForRule(field, rule)) ) rule.matchingPositions.push(columnIndex); }); }); ......
Tras ejecutar esta parte de la función cada campo tendrá en su array matchingPositions todos las posibles posiciones que puede ocupar. Como varios campos pueden cumplir con varias posiciones debemos eliminar las combinaciones no válidas. Para que el problema tenga solución uno de los campos debe cumplir con una única posición, y a partir de ese podemos decidir las posiciones de los demás:
//Ordenar las reglas por numero de columnas que cumplen sus reglas //la primera regla solo se cumple para una columna de valores this.rules = this.rules.sort( (a, b) => a.matchingPositions.length - b.matchingPositions.length ); //Dejar en cada regla unicamente las columnas que no estan repetidas en otras anteriores this.rules.forEach((rule, index) => { for (let i = index + 1; i < this.rules.length; i++) { const ruleIndex = this.rules[i].matchingPositions.findIndex( (r) => r == rule.matchingPositions[0] ); this.rules[i].matchingPositions.splice(ruleIndex, 1); } }); };
Con esto ya tenemos identificada la posición de cada campo. El problema nos pide como respuesta la multiplicación de los valores de aquellos campos que comiencen por departure. Para obtenerlos en primer lugar filtro los campos que comiencen por dicha palabra y luego obtengo sus posiciones. Para cada ticket extraigo los valores de esas posiciones:
/** * Devuelve los valores de los campos que comienzan por "departure" */ public getDeparture = (): number[] => { this.findFieldsPosition(); const positions = this.rules .filter((r) => r.name.startsWith("departure")) .flatMap((r) => r.matchingPositions); return this.ownTicket.fields.filter((_f, i) => positions.includes(i)); };
Solo queda invocar a esta función y multiplicar el resultado:
const ticketsChecker = new TicketsChecker("./tickets.txt"); const values = ticketsChecker.getDeparture(); console.log( "Answer:", values.reduce((a, b) => (a *= b), 1) );