Advent of Crafted Code

Il y a plein de façons de jouer à l'Advent of Code. J'aime bien celle qui consiste à pratiquer l'écriture de code propre.

Le jour 7 donnait l'occasion d'expérimenter cela. Les ingénieurs ne peuvent plus réparer le pont de cordes car de jeunes éléphants ont volé les opérateurs de leurs équations : il faut leur venir en aide.

Après avoir écrit un code assez direct "qui fait le boulot" dans la 1ère partie, on pouvait profiter de la 2ème partie pour appliquer quelques principes de conception bien connus.

Chaque équation se présente sous la forme d'une liste de nombres entiers formant les opérandes et d'un autre nombre entier pour le résultat. On sait que l'évaluation se fait toujours de gauche à droite (sans règle de précédence) et qu'il n'y a que des additions et des multiplications.

Par exemple, avec 6, 2 et 5 comme opérandes et 40 comme résultat, on peut retrouver l'équation : \((6+2) \times 5=40\)

On pourrait naïvement essayer toutes les combinaisons mais ça peut être assez long, surtout que toutes certaines équations n'ont pas de solution. On peut toutefois facilement restreindre les possibilités. Puisque le résultat est construit de gauche à droite, on peut facilement le déconstruire de droite à gauche.

Imaginons le même problème où il n'y a que des additions. La déconstruction ne va rien nous faire gagner mais c'est pour l'exemple. On peut récursivement vérifier l'équation en soustrayant successivement les opérandes au résultat voulu.

1def is_solved_by_add(result: int, operands: List[int]) -> bool:
2  if len(operands) == 1:
3    return result == operands[0]
4  # r = n1+n2+n3 <=> r-n3 = n1+n2
5  return is_solved_by_add(result - operands[-1], operands[:-1])
6
7assert is_solved_by_add(13, [6, 2, 5])  # 13=6+2+5
8assert not is_solved_by_add(60, [6, 2, 5])

Dans un problème où il n'y aurait que des multiplications, on gagnerait beaucoup de temps : dès que le résultat courant n'est pas divisible par l'opérande le plus à droite, on peut s'arrêter car l'équation est impossible.

 1def is_solved_by_mul(result: int, operands: List[int]) -> bool:
 2  last_operand = operands[-1]
 3  if len(operands) == 1:
 4    return result == last_operand
 5  # r = n1.n2.n3 <=> r divisible par n3 et r/n3 = n1.n2
 6  return result % last_operand == 0 and is_solved_by_mul(result // last_operand, operands[:-1])
 7
 8assert not is_solved_by_mul(13, [6, 2, 5])
 9assert is_solved_by_mul(60, [6, 2, 5])  # 60=6*2*5
10assert not is_solved_by_mul(61, [6, 2, 5])

Donc pour résoudre notre problème où on peut, soit additionner, soit multiplier, il nous suffit de regrouper les deux. A chaque étape, on va d'abord, par exemple, tenter l'addition et, si elle n'aboutit pas, on va tenter la multiplication.

 1def is_solved_by_add_or_mul(result: int, operands: List[int]) -> bool:
 2  last_operand = operands[-1]
 3  if len(operands) == 1:
 4    return result == last_operand
 5  remaining_operands = operands[:-1]
 6  if is_solved_by_add_or_mul(result - last_operand, remaining_operands):
 7    return True
 8  if result % last_operand > 0:
 9    return False
10  return is_solved_by_add_or_mul(result // last_operand, remaining_operands)
11
12assert is_solved_by_add_or_mul(13, [6, 2, 5])  # 13=6+2+5
13assert is_solved_by_add_or_mul(60, [6, 2, 5])  # 60=6*2*5
14assert not is_solved_by_add_or_mul(61, [6, 2, 5])
15assert is_solved_by_add_or_mul(17, [6, 2, 5])  # 17=6*2+5
16assert is_solved_by_add_or_mul(40, [6, 2, 5])  # 40=(6+2)*5
17assert not is_solved_by_add_or_mul(16, [6, 2, 5])

Le code est un peu chargé mais ça passe. La partie 2 vient encore plus compliquer les choses : on rajoute un opérateur de concaténation qui vient simplement juxtaposer les deux nombres. Par exemple, \((6 \times 2) \enspace | \enspace 5=125\).

On est dans l'Advent of Code, donc on sait que ça n'ira pas plus loin que ça, mais si on était dans un autre contexte ?

En développement logiciel, il y a un règle de trois et ce n'est pas celle que vous avez peut être apprise à l'école. Notre règle de trois dit qu'il ne faut pas chercher à généraliser quand on rencontre deux choses similaires mais, à la troisième apparition, il faut remanier le code.

Three strikes and you refactor

Ici, ça veut dire qu'il y a un troisième opérateur mais on considère qu'il pourrait y en avoir 4 ou 5. On va donc généraliser la résolution.

Pour cela, on va appliquer le principe de responsabilité unique. Pour chaque essai d'opérateur, on va définir des éléments de code distincts, indépendants et focalisés sur leur sujet. Par exemple, comme ceci :

 1FollowUp: TypeAlias = Callable[[int], bool]
 2
 3def add(result: int, operand: int, follow: FollowUp) -> bool:
 4  return follow(result - operand)
 5
 6def mul(result: int, operand: int, follow: FollowUp) -> bool:
 7  return result % operand == 0 and follow(result // operand)
 8
 9def concat(result: int, operand: int, follow: FollowUp) -> bool:
10  power10 = 10 ** (int(math.log10(operand)) + 1)
11  return result % power10 == operand and follow(result // power10)

Et pour tester la résolution d'une équation, on écrit une fonction qui prend en paramètres les opérateurs que l'on veut utiliser.

 1Operator: TypeAlias = Callable[[int, int, FollowUp], bool]
 2
 3def is_solved(result: int, operands: List[int], *allowed_operators: Operator):
 4  last_operand = operands[-1]
 5  if len(operands) == 1:
 6    return result == last_operand
 7  remaining_operands = operands[:-1]
 8  for operator in allowed_operators:
 9    if operator(
10      result, last_operand,
11      lambda next_result: is_solved(next_result, remaining_operands, *allowed_operators)
12    ):
13      return True
14  return False

Cette fonction respecte un principe important : le principe ouvert/fermé. Contrairement à notre fonction précédente is_solved_by_add_or_mul, cette fonction is_solved a la capacité d'être étendue par les opérateurs qu'on lui donne. Considérant les besoins connus, elle est fermée à la modification mais ouverte aux extensions.

1assert is_solved(13, [6, 2, 5], add)  # 13=6+2+5
2assert is_solved(60, [6, 2, 5], mul)  # 60=6*2*5
3assert not is_solved(61, [6, 2, 5], add, mul)
4assert is_solved(17, [6, 2, 5], add, mul)  # 17=6*2+5
5assert is_solved(40, [6, 2, 5], add, mul)  # 40=(6+2)*5
6assert not is_solved(16, [6, 2, 5], add, mul)
7assert not is_solved(125, [6, 2, 5], add, mul)
8assert is_solved(125, [6, 2, 5], add, mul, concat)  # 125=(6*2)|5

Une petite remarque pour terminer. Les principes SOLID tels que la responsabilité unique ou l'ouvert/fermé sont généralement présentés comme de principes de programmation orientée objet. Or, ici, on n'a clairement pas fait de POO. Mais alors, quel paradigme de programmation a-t-on utilisé ?