Advent of Code 2023, jour 2
Deuxième jour du calendrier Advent of Code de décembre dernier : une liste de séries de tirages avec remise, dans le cas présent des cubes de couleur qu'on tire d'un sac. Il faut déterminer lesquelles de ces séries sont possibles étant donné une répartition donnée de cubes dans le sac duquel on fait les tirages, et additioner les numéros des séries possibles.
C'est plus simple à comprendre avec un exemple :
Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green
Dans cet exemple et avec la contrainte {red: 12, green: 13, blue: 14} seules les séries 1, 2, et 5 sont possibles.
Comme pour le premier jour on va commencer par lire les données du problème depuis l'entrée standard, la contrainte quant à elle est indiquée en dur :
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();
const constraint = {
red: 12,
green: 13,
blue: 14
};
Et établissons les étapes de traitement :
- parser chaque ligne de texte en une structure simple
- filtrer pour ne garder que les jeux qui répondent à la contrainte
- prendre l'identifiant de ces jeux
- en retourner la somme
// Part 1
const part1 = inputData
.map(parseGameLine)
.filter(isGamePossibleUsing(constraint))
.map(property('id'))
.reduce(add, 0);
console.log(part1);
Les données du problème sont de la forme suivante :
Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
On va les parser vers cette forme :
{
id: 1,
sets: [
{red: 4, green: 0, blue: 3},
{red: 1, green: 2, blue: 6},
{red: 0, green: 2, blue: 0}
]
}
Prenons le temps de préciser un peu de vocabulaire pour tout le code. Chaque ligne représente une partie ("game") qui porte un numéro ("id") et comporte un certain nombre de tirages ("set") chacun comprenant un certain nombre de mains ("hand") qui sont chacune un certain nombre de cubes d'une même couleur.
Niveau implémentation on y va à grands coups de split parce que c'est simple et ça fonctionne. Pour chaque partie on sépare l'identifiant des tirages, et pour chaque tirage on va normaliser les valeurs pour que la suite soit plus simple :
// string → integer
const toInteger = item => parseInt(item, 10);
// string → set
// set := {red: integer, green: integer, blue: integer}
const parseSet = set => {
const hands = set
.split(', ')
.map(hand => hand.trim().split(' '));
const parsed = {
red: 0,
green: 0,
blue: 0
}
let color, count;
for (hand of hands) {
[count, color] = hand;
parsed[color] = toInteger(count);
}
return parsed;
};
// string → game
// game := {id: integer, sets: [{red: integer, green: integer, blue: integer}]
const parseGameLine = line => {
const [idPart, setsPart] = line.split(': ');
return {
id: toInteger(idPart.slice(5)),
sets: setsPart.split(';').map(parseSet)
};
};
Maintenant qu'on a les données sous une forme traitable, passons au filtrage. On a une contrainte {red: 12, green: 13, blue: 14} qui représente l'ensemble duquel on est censé effectuer les tirages. Une partie n'est possible que si chacun de ses tirages est possible, et un tirage n'est possible que si aucune couleur n'est tirée en plus grand nombre que ce qui est présent dans l'ensemble de départ. Concrètement :
// constraint → set → boolean
// constraint := {red: integer, green: integer, blue: integer}
// set := {red: integer, green: integer, blue: integer}
const isSetPossibleUsing = constraint => set =>
set.red <= constraint.red
&& set.green <= constraint.green
&& set.blue <= constraint.blue;
// constraint → game → boolean
// constraint := {red: integer, green: integer, blue: integer}
// game := {id: integer, sets: [{red: integer, green: integer, blue: integer}]
const isGamePossibleUsing = constraint => game =>
game.sets.every(isSetPossibleUsing(constraint));
Ensuite il faut prendre uniquement l'identifiant de chaque partie, et c'est le genre de chose qui sera certainement réutilisé dans d'autres problèmes :
// string → object → any
const property = name => object => object.hasOwnProperty(name)
? object[name]
: undefined;
D'ailleurs pour l'étape finale on réutilise une fonction définie pour le jour 1 :
// (integer, integer) → integer
const add = (a, b) => a + b;
Sur l'exemple cité plus haut le programme donne bien 8 comme valeur de sortie, et son résultat sur l'entrée grandeur nature (une centaine de parties) est accepté. C'est bon pour la première partie.
La deuxième partie nous demande de faire l'exercice inverse : pour chaque partie donnée, déterminer la contrainte minimale satisfaite par tous les tirages. Ensuite on doit multiplier ensemble les valeurs de contrainte minimale de chaque partie, et retourner la somme de ces produits. La séquence est claire :
- parser l'entrée exactement comme pour la première partie
- pour chaque partie en entrée, déterminer la contrainte minimale
- calculer le produit des valeurs de chaque contrainte (l'énoncé appelle ça "power")
- en retourner la somme
// Part 2
const part2 = inputData
.map(parseGameLine)
.map(getMinimalConstraint)
.map(constraintPower)
.reduce(add, 0);
console.log(part2);
Pour obtenir la contrainte minimale il faut déterminer pour chaque couleur la plus grande valeur tirée :
// [integer] → integer
const max = list => list.reduce((a,b) => a > b ? a : b, 0);
// game → constraint
// game := {id: integer, sets: [{red: integer, green: integer, blue: integer}]
// constraint := {red: integer, green: integer, blue: integer}
const getMinimalConstraint = game => ({
red: max(game.sets.map(property('red'))),
green: max(game.sets.map(property('green'))),
blue: max(game.sets.map(property('blue'))),
});
Je n'aurais pas cru réutiliser property dans le même problème, merci moi du passé.
Comme on travaille ici uniquement avec des entiers positifs la fonction max fait sa réduction à partir de zéro. Si ça devait fonctionner aussi avec des nombres négatifs il suffirait de partir de -Infinity :
// [integer] → integer
const max = list => list.reduce((a,b) => a > b ? a : b, -Infinity);
Maintenant qu'on a la contrainte minimale pour chaque partie, il faut en calculer la "puissance" en multipliant ses termes ensemble :
// constraint → integer
// constraint := {red: integer, green: integer, blue: integer}
const constraintPower = constraint =>
constraint.red * constraint.green * constraint.blue;
Les données de l'énoncé ne donnent aucune partie pour laquelle une couleur serait totalement absente et aurait donc sa contrainte à zéro, si ce n'était pas le cas on devrait s'en protéger :
// constraint → integer
// constraint := {red: integer, green: integer, blue: integer}
const constraintPower = constraint =>
(constraint.red > 0 ? constraint.red : 1)
* (constraint.green > 0 ? constraint.green : 1)
* (constraint.blue > 0 ? constraint.blue : 1);
C'est accepté sur les données de test, c'est accepté sur les données réelles, voilà qui est fait.
Pour récapituler, le programme entier :
// Advent of Code 2023 - Day 2
const fs = require('fs');
const STDIN = 0;
// STDIO → [string]
const input = () => fs
.readFileSync(STDIN, 'UTF-8')
.split('\n')
.filter(line => line.length > 0);
// string → integer
const toInteger = item => parseInt(item, 10);
// string → set
// set := {red: integer, green: integer, blue: integer}
const parseSet = set => {
const hands = set
.split(', ')
.map(hand => hand.trim().split(' '));
const parsed = {
red: 0,
green: 0,
blue: 0
}
let color, count;
for (hand of hands) {
[count, color] = hand;
parsed[color] = toInteger(count);
}
return parsed;
};
// string → game
// game := {id: integer, sets: [{red: integer, green: integer, blue: integer}]
const parseGameLine = line => {
const [idPart, setsPart] = line.split(': ');
return {
id: toInteger(idPart.slice(5)),
sets: setsPart.split(';').map(parseSet)
};
};
// constraint → set → boolean
// constraint := {red: integer, green: integer, blue: integer}
// set := {red: integer, green: integer, blue: integer}
const isSetPossibleUsing = constraint => set =>
set.red <= constraint.red
&& set.green <= constraint.green
&& set.blue <= constraint.blue;
// constraint → game → boolean
// constraint := {red: integer, green: integer, blue: integer}
// game := {id: integer, sets: [{red: integer, green: integer, blue: integer}]
const isGamePossibleUsing = constraint => game =>
game.sets.every(isSetPossibleUsing(constraint));
// string → object → any
const property = name => object => object.hasOwnProperty(name)
? object[name]
: undefined;
// (integer, integer) → integer
const add = (a, b) => a + b;
const inputData = input();
const constraint = {
red: 12,
green: 13,
blue: 14
};
// Part 1
const part1 = inputData
.map(parseGameLine)
.filter(isGamePossibleUsing(constraint))
.map(property('id'))
.reduce(add, 0);
console.log(part1);
// ---
// [integer] → integer
const max = list => list.reduce((a,b) => a > b ? a : b, 0);
// game → constraint
// game := {id: integer, sets: [{red: integer, green: integer, blue: integer}]
// constraint := {red: integer, green: integer, blue: integer}
const getMinimalConstraint = game => ({
red: max(game.sets.map(property('red'))),
green: max(game.sets.map(property('green'))),
blue: max(game.sets.map(property('blue'))),
});
// constraint → integer
// constraint := {red: integer, green: integer, blue: integer}
const constraintPower = constraint =>
constraint.red * constraint.green * constraint.blue;
// Part 2
const part2 = inputData
.map(parseGameLine)
.map(getMinimalConstraint)
.map(constraintPower)
.reduce(add, 0);
console.log(part2);
C'est disponible avec les entrées sur GitHub.