Cette semaine, c'est Thomas qui vous propose un #KataOfTheWeek : Pas en reste les chinois

Briefing du Kata : Je vous propose ici une traduction du kata en question. Il a été publié le 13 décembre 2021 et vous pouvez retrouver l'original ici : https://adventofcode.com/2020/day/13.

Première partie :

Voici l'entrée que vous aurez pour résoudre ce problème :

1001612
19,x,x,x,x,x,x,x,x,41,x,x,x,37,x,x,x,x,x,821,x,x,x,x,x,x,x,x,x,x,x,x,13,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,29,x,463,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,23

Vous devez prendre le bus pour rejoindre l'aéroport. Chaque bus a un numéro qui indique également à quelle fréquence il part pour l'aéroport.

Le départ des bus est basé sur un timestamp qui mesure le nombre de minutes depuis un point arbitraire dans le temps. Au temps 0, tous les bus partent de la gare routière en même temps. Après ça chaque bus suit son itinéraire jusqu'à l'aéroport et revient en gare pour recommencer une boucle et ce à l'infini.

Le temps que le bus met à faire une boucle correspond au numéro de ce bus. C'est à dire que le bus n°5 part de la gare au timestamp 0, 5, 10, 15 etc. Le bus n°11 partira à 0, 11, 22, 33 etc. Si vous êtes présent au moment où le bus part, vous pouvez le prendre !

Vos notes (les entrées du puzzle) sont composées de 2 lignes. La première ligne correspond à votre estimation d'à partir de quel timestamp vous serez disponible pour prendre le bus. La seconde ligne correspond aux identifiants des bus qui sont en service aujourd'hui ; les entrées qui sont marquées d'un X sont des bus qui ne sont pas en service aujourd'hui, vous les ignorerez.

Afin de gagner du temps votre objectif est de savoir quel est le premier bus que vous pouvez prendre pour arriver à l'aéroport (il n'y en a exactement qu'un seul).

Par exemple, imaginez que vous ayez comme entrée :

939
7,13,x,x,59,x,31,19

Ici le timestamp à partir duquel vous êtes disponible est 939, et les numéros de bus en services sont 7, 13, 59, 31 et 19. Sur le schéma suivant, à partir du timestamp 929 les bus qui partent sont notés avec un D :

time   bus 7   bus 13  bus 59  bus 31  bus 19
929      .       .       .       .       .
930      .       .       .       D       .
931      D       .       .       .       D
932      .       .       .       .       .
933      .       .       .       .       .
934      .       .       .       .       .
935      .       .       .       .       .
936      .       D       .       .       .
937      .       .       .       .       .
938      D       .       .       .       .
939      .       .       .       .       .
940      .       .       .       .       .
941      .       .       .       .       .
942      .       .       .       .       .
943      .       .       .       .       .
944      .       .       D       .       .
945      D       .       .       .       .
946      .       .       .       .       .
947      .       .       .       .       .
948      .       .       .       .       .
949      .       D       .       .       .

Le premier bus que vous pouvez prendre est le bus n°59, qui ne part pas avant le timestamp 944. Donc vous devrez attendre 944 - 939 = 5 minutes avant votre départ. Si vous multipliez ce temps d'attente par le numéro du bus que vous prendrez vous obtenez 295.

Quel est le n° du premier bus que vous pouvez prendre multiplié par le temps d'attente de ce bus ?

Seconde partie :

La compagnie de bus organise un concours pour quiconque pourra trouver le premier timestamp T à partir duquel le premier bus part au temps T, et chaque bus suivant part avec T + N minutes de décalage, N correspondant à la position du bus dans la liste donnée en entrée. (la première ligne de l'entrée ne sert plus à rien)

Par exemple, reprenons l'entrée précédente :

7,13,x,x,59,x,31,19

Pour une entrée de type x, il n'y a aucune contrainte de temps de départ.

Ça signifie que l'on doit trouver le premier timestamp T tel que :

• Le bus n°7 parte au temps T
• Le bus n°13 parte une minute après le temps T (soit T + 1)
• Il n'y a aucune restriction à 2 ou 3 minutes du temps T puisqu'on a une entrée "x"
• Le bus n°59 parte 4 minutes après le temps T (soit T + 4)
• Il n'y a aucune restriction non plus à la minute 5
• Le bus n°31 parte 6 minutes après le temps T (soit T + 6)
• Le bus n°19 parte 7 minutes après le temps T (soit T + 7)

Dans cet exemple le départ le plus tôt sera à 1068781 :

time     bus 7   bus 13  bus 59  bus 31  bus 19
1068773    .       .       .       .       .
1068774    D       .       .       .       .
1068775    .       .       .       .       .
1068776    .       .       .       .       .
1068777    .       .       .       .       .
1068778    .       .       .       .       .
1068779    .       .       .       .       .
1068780    .       .       .       .       .
1068781    D       .       .       .       .
1068782    .       D       .       .       .
1068783    .       .       .       .       .
1068784    .       .       .       .       .
1068785    .       .       D       .       .
1068786    .       .       .       .       .
1068787    .       .       .       D       .
1068788    D       .       .       .       D
1068789    .       .       .       .       .
1068790    .       .       .       .       .
1068791    .       .       .       .       .
1068792    .       .       .       .       .
1068793    .       .       .       .       .
1068794    .       .       .       .       .
1068795    D       D       .       .       .
1068796    .       .       .       .       .
1068797    .       .       .       .       .

Ce n'est pas grave si après qu'un bus soit parti à partir de T, il réapparaisse alors que d'autre ne sont pas encore partis. Dans l'exemple ci-dessus, le bus n°7 part au timestamp 1068788, soit 7 minutes après T. Il n'y a aucun problème ; la seule contrainte par rapport à ce timestamp c'est que le bus n°19 parte également (et c'est le cas).

Voici quelques exemples :

• Le premier timestamp qui correspond à la liste 17,x,13,19 est 3417.
• 67,7,59,61 aura pour premier timestamp 754018.
• 67,x,7,59,61 aura pour premier timestamp 779210.
• 67,7,x,59,61 aura pour premier timestamp 1261476.
• 1789,37,47,1889 aura pour premier timestamp 1202161486.

Quoi qu'il arrive, et quelque soit la liste des numéros de bus, vous pouvez être sûr que le timestamp ne sera pas plus grand que 100000000000000 !

Quel est le premier timestamp étant donné votre entrée, qui correspond aux contraintes décrites précédemment ?

Saurez-vous résoudre le problème ?

Bon courage !

Et voici une solution proposée par l'auteur :

Pour la première partie, la réponse est 6568. Pour la seconde partie, la réponse est 554865447501099.

Pour la première, la solution est assez simple. Il suffit de déterminer par combien il faut multiplier le numéro du bus pour obtenir le nombre qui est après notre timestamp. On cherche donc à diviser le timestamp par le numéro du bus. Puisqu'on travaille avec des nombres entiers, le résultat de la division, si elle ne tombe pas juste, sera en dessous du timestamp. Dans ce cas il faut rajouter 1 au quotient, avant de le remultiplier par le numéro de bus pour obtenir le timestamp que l'on cherche. Autrement, si la division tombe juste, ce numéro de bus sera la base de notre solution. Il faut ensuite récupérer le plus petit des timestamps et enfin appliquer la formule de l'énoncé pour avoir le résultat final.

Par contre, pour la seconde, itérer jusqu'au nombre attendu n'est pas raisonnable, et risque de prendre beaucoup de temps de calcul. En étudiant les entrées on remarque que tous les numéros de bus sont premiers.

On comprend également que l'on cherche la solution au système d'équations pour l'entrée 7,13,x,x,59,x,31,19 tel que :

(n + 0) % 7  = 0
(n + 1) % 13 = 0
(n + 4) % 59 = 0
(n + 6) % 31 = 0
(n + 7) % 19 = 0

Ou noté de façon mathématique :

    n ≡ 0 [mod  7]
n + 1 ≡ 0 [mod 13]
n + 4 ≡ 0 [mod 59]
n + 6 ≡ 0 [mod 31]
n + 7 ≡ 0 [mod 19]

Donc

n ≡ 0 [mod  7]
n ≡ -1 [mod 13]
n ≡ -4 [mod 59]
n ≡ -6 [mod 31]
n ≡ -7 [mod 19]

Soit

n ≡  0 [mod  7]
n ≡ 12 [mod 13]
n ≡ 55 [mod 59]
n ≡ 25 [mod 31]
n ≡ 12 [mod 19]

Ou encore

n % 7  = 0
n % 13 = 12
n % 59 = 55
n % 31 = 25
n % 19 = 12

On se retrouve dans le cas typique du problème des restes chinois tel qu'il peut être exposé ici : https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8medesrestes_chinois#Exemple

Voici une solution proposée en kotlin :

package org.grorg.aoc

class NotFoundSolutionException: Exception("No solution has been found")

fun solveDay13p1(input: List<String>): Int {
    val start = input[0].toInt()
    return input[1]
        .split(",")
        .asSequence()
        .filter { it != "x" }
        .map { it.toInt() }
        .map { Pair(it, if (start % it == 0) start else it * (start / it + 1)) }
        .minByOrNull { (_, b) -> b }
        ?.let { (a, b) -> (b - start) * a }
        ?: throw NotFoundSolutionException()
}

fun findModulus1(x: Long, modulus: Long) = generateSequence(0) { it + 1 }
    .filter { (x * it % modulus) == 1L }
    .first()

fun solveDay13p2(input: List<String>): Long {
    val elements = input[1]
        .split(",")
        .asSequence()
        .zip(generateSequence(0) { it + 1 })
        .filter { (a, _) -> a != "x" }
        .map { (a, b) ->
            val al = a.toLong()
            Pair(al, (al - b) % al)
        }
        .toMap()
    val m = elements.keys.reduce(Long::times)
    val mn = elements.map { (a, _) -> Pair(a, findModulus1(m / a, a)) }.toMap()
    return elements.keys
        .map { elements[it]!! * (m / it) * mn[it]!! }
        .reduce(Long::plus) % m
}

Votre équipe TakiVeille