Pas en reste les chinois

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 ! Retrouvez la solution dans cet article 😉

TakiVeille

TakiVeille