Advent of Code 2023, jour 1
Premier jour de l'année, on sait ce que ça veut dire : tous les compteurs sont à zéro et on a envie d'entamer plein de choses, de prendre des bonnes résolutions, ou de dépoussiérer des projets délaissés. Donc je dépoussière le blog et je dépoussière le compte GitHub (fuck Microsoft et fuck Copilot mais j'y garde une présence pour l'exacte même raison que je garde une présence sur l'autre endroit maudit de Microsoft qu'est LinkedIn).
Pour ce faire je vais (tenter de) compléter le calendrier Advent of Code de décembre dernier, en détaillant les obstacles intéressants pour que ça profite aux éventuels lecteurs, en JavaScript parce que pourquoi pas. Pas forcément un problème par jour par contre, j'ai une vie.
Premier jour : on demande de repérer dans chaque ligne de l'entrée le premier et le dernier chiffre, de les combiner afin d'obtenir un nombre à deux chiffre, et de renvoyer la somme des nombres ainsi formés.
L'exemple fourni met en évidence un piège possible, le premier et le dernier chiffre peuvent très bien être le meme :
1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet
On peut commencer par lire l'input et l'avoir à disposition sous forme de liste de lignes, un pattern qui sera répété dans les autres katas :
const fs = require('fs');
const STDIN = 0;
// STDIO → [string]
const input = () => fs
.readFileSync(STDIN, 'UTF-8)
.split('\n')
.filter(line => line.length > 0);
const inputData = input();
Ensuite le plan est simple (c'est le premier jour après tout), pour chaque ligne de l'input on va :
- extraire les caractères qui sont des chiffres
- en prendre le premier et le dernier (qui sont éventuellement le même)
- les concaténer
- convertir ce résultat en nombre
puis additioner le tout.
const part1 = inputData
.map(takeDigits)
.map(firstAndLast)
.map(combine)
.map(toInteger)
.reduce(add, 0);
console.log(part1);
Ça nous fait des fonctions plutôt triviale à implémenter :
// string → boolean
const isDigit = character => '0123456789'.includes(character);
// string → [string]
const takeDigits = line => Array.from(line).filter(isDigit);
// [string] → [string]
const firstAndLast = list => [list[0], list[list.length - 1]];
// [string] → string
const combine = list => list[0] + list[1];
// string → integer
const toInteger = item => parseInt(item, 10);
// (integer, integer) → integer
const add = (a, b) => a + b;
Effectivement ça marche sur l'input donné en exemple, et sur l'input réel le résultat est accepté comme réponse correcte.
La deuxième partie est une variation sur la première (c'est habituel dans Advent of Code). Cette fois-ci la différence est qu'il faut aussi prendre en compte les chiffres qui sont écris en toutes lettres (one, two, three…). Voici l'input donné en exemple :
two1nine
eightwothree
abcone2threexyz
xtwone3four
4nineeightseven2
zoneight234
7pqrstsixteen
En toute logique ça revient donc à trouver ces mots-chiffres et les remplacer par leur équivalent en chiffre, le reste du processus reste le même :
const part2 = inputData
.map(parseNumbers)
.map(takeDigits)
.map(firstAndLast)
.map(combine)
.map(toInteger)
.reduce(add, 0);
console.log(part2);
On voit dans l'exemple qu'il peut y avoir une intersection, dans eightwothree on a un eight comme premier mot-chiffre, un three comme dernier mot-chiffre, mais un two au milieu qui serait invisible si on remplaçait le eight par 8. Exemple qui serait plus embêtant : eighttwone où si on remplace les mots par des chiffres au fur et à mesure on se retrouve avec 82ne et on a loupé le one qui serait le dernier chiffre. Il faut donc parcourir à partir de la gauche et remplacer uniquement le premier mot-chiffre qu'on rencontre, et faire de même en parcourant depuis la droite. Parcourir depuis la droite revient à parcourir depuis la gauche sur la chaîne retournée, en y cherchant des mots également retournés (eno, owt, eerht…).
L'implémentation de parseNumbers est un peu verbeuse, mais reste simple à raisonner :
// (string, string) → string
const concatenate = (a,b) => `${a}${b}`;
// string → string
const reverse = word => Array.from(word)
.reverse()
.reduce(concatenate, '');
// string → string
const parseNumbers = word => {
const tokens = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'];
const findToken = word => token => ({
token: token,
position: word.indexOf(token)
});
const found = match => match.position !== -1;
const matches = tokens => word => tokens
.map(findToken(word))
.filter(found)
.sort((a,b) => a.position - b.position)
const parseFirstNumber = tokens => word => {
const tokenMatches = matches(tokens)(word);
if (tokenMatches.length === 0) {
return word;
}
const firstToken = tokenMatches[0].token;
return word.replace(firstToken, tokens.indexOf(firstToken));
};
const firstParsed = parseFirstNumber(tokens)(word);
const lastParsed = parseFirstNumber(tokens.map(reverse))(reverse(firstParsed));
return reverse(lastParsed);
}
Ça fonctionne sur l'input donné en test, mais le résultat sur l'input réel est refusé.
Le problème de cet input de test est qu'il montre le cas problématique où deux mots-chiffres se croisent, mais pas celui où un tel croisement est précédé ou suivi d'un chiffre. Par exemple dans 1twone le premier chiffre est 1 et le dernier chiffre est one mais l'algorithme ci-dessus consomme two et rend one invisible. Il faut donc le modifier pour repérer si un token trouvé est précédé d'un chiffre, et dans ce cas l'ignorer :
// string → string
const parseNumbers = word => {
const tokens = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'];
const digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
const findToken = word => token => {
token: token,
position: word.indexOf(token)
});
const found = match => match.position !== -1;
const matches = tokens => word => tokens
.map(findToken(word))
.filter(found)
.sort((a,b) => a.position - b.position)
const parseFirstNumber = tokens => word => {
const tokenMatches = matches(tokens)(word);
if (tokenMatches.length === 0) {
return word;
}
// ignore the matched token if there's a digit before
const digitMatches = matches(digits)(word);
if (digitMatches.length > 0
&& digitMatches[0].position < tokenMatches[0].position) {
return word;
}
const firstToken = tokenMatches[0].token;
return word.replace(firstToken, tokens.indexOf(firstToken));
};
const firstParsed = parseFirstNumber(tokens)(word);
const lastParsed = parseFirstNumber(tokens.map(reverse))(reverse(firstParsed));
return reverse(lastParsed);
}
Et là ça fonctionne ! Belle entrée en matière, c'est abordable mais pas non plus totalement trivial. Je ne sais pas si l'omission de ce cas "tricky" dans l'exemple est volontaire, mais si c'est le cas c'est bien joué.
Mis bout à bout on a donc ceci pour les deux parties :
// Advent of Code 2023 - Day 01
const fs = require('fs');
const STDIN = 0;
// STDIO → [string]
const input = () => fs
.readFileSync(STDIN, 'UTF-8')
.split('\n')
.filter(line => line.length > 0);
// string → boolean
const isDigit = character => '0123456789'.includes(character);
// string → [string]
const takeDigits = line => Array.from(line).filter(isDigit);
// [string] → [string]
const firstAndLast = list => [list[0], list[list.length - 1]];
// [string] → string
const combine = list => list[0] + list[1];
// string → integer
const toInteger = item => parseInt(item, 10);
// (integer, integer) → integer
const add = (a, b) => a + b;
const inputData = input();
const part1 = inputData
.map(takeDigits)
.map(firstAndLast)
.map(combine)
.map(toInteger)
.reduce(add, 0);
console.log(part1);
// (string, string) → string
const concatenate = (a,b) => `${a}${b}`;
// string → string
const reverse = word => Array.from(word)
.reverse()
.reduce(concatenate, '');
// string → string
const parseNumbers = word => {
const tokens = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'];
const digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
const findToken = word => token => ({
token: token,
position: word.indexOf(token)
});
const found = match => match.position !== -1;
const matches = tokens => word => tokens
.map(findToken(word))
.filter(found)
.sort((a,b) => a.position - b.position)
const parseFirstNumber = tokens => word => {
const tokenMatches = matches(tokens)(word);
if (tokenMatches.length === 0) {
return word;
}
// ignore the matched token if there's a digit before
const digitMatches = matches(digits)(word);
if (digitMatches.length > 0
&& digitMatches[0].position < tokenMatches[0].position) {
return word;
}
const firstToken = tokenMatches[0].token;
return word.replace(firstToken, tokens.indexOf(firstToken));
};
const firstParsed = parseFirstNumber(tokens)(word);
const lastParsed = parseFirstNumber(tokens.map(reverse))(reverse(firstParsed));
return reverse(lastParsed);
}
const part2 = inputData
.map(parseNumbers)
.map(takeDigits)
.map(firstAndLast)
.map(combine)
.map(toInteger)
.reduce(add, 0);
console.log(part2);
C'est disponible avec les inputs sur GitHub.