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()
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.
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.