Dés en séquences

Links: notebook, html, PDF, python, slides, slides(2), GitHub

Ce problème est issu de Google Jam : Dice Straight (2017). On dispose de N dès à six faces sur lesquelles sont écrits six nombres entiers quelconques. On cerche ) former une séquence de dés de telle sorte que deux dés consécutifs montre deux nombres entiers qui se ssuivent. Quel est la longueur de la plus grande séquence de dès qui vérifient ces contraintes ?

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Exemple

On considère l’exemple donné par l’énoncé. Sur les six faces de quatre dés sont écrits les nombres entiers suivants :

::

4 8 15 16 23 42 8 6 7 5 30 9 1 2 3 4 55 6 2 10 18 36 54 86

On peut trouver une séquence de quatre faces 2 3 4 5 qui se suivent comme suit :

::

2 10 18 36 54 86 1 2 3 4 55 6 4 8 15 16 23 42 8 6 7 5 30 9

La séquence la plus longue inclut tous les dés, soit 4 dés.

Indices

  1. L’énoncé propose un nombre de dés supérieur à 10. Cela veut souvent dire qu’il existe un algorithme de coût quadratique et non exponentiel.

  2. Serait-il possible de transformer ce problème comme un parcours de graphe d’abord cyclique puis acyclique ?

Solution

L’idée est de créer un graphe dans lequel chaque noeud est une face de dé et les arcs relient deux faces qui peuvent se suivre dans la même séquence.