Glouton : Chemin dans une grille

Présentation

On se donne une grille de nombre. Par exemple :

17	7	21	71	40	77	58	42	67	48
1	40	70	54	43	60	19	49	32	6
58	91	69	75	1	27	89	50	74	77
96	28	89	18	9	67	30	32	14	52
24	77	44	83	2	51	20	16	50	69
53	75	52	3	21	46	59	68	86	24
52	45	80	82	19	47	18	68	16	92
14	65	43	16	4	79	61	43	72	88

On veut suivre un chemin dans cette grille allant de la case en haut à gauche à la case en bas à droite,
on ne peut se déplacer que d'une case, vers la droite ou vers le bas,
pour chaque case, on cumule le chiffre écrit dans la case.

Le but est d'obtenir le plus grand score.

Réprésentation Python de la grille

grid = [
  [17, 7, 21, 71, 40, 77, 58, 42, 67, 48],
  [1, 40, 70, 54, 43, 60, 19, 49, 32, 6],
  [58, 91, 69, 75, 1, 27, 89, 50, 74, 77],
  [96, 28, 89, 18, 9, 67, 30, 32, 14, 52],
  [24, 77, 44, 83, 2, 51, 20, 16, 50, 69],
  [53, 75, 52, 3, 21, 46, 59, 68, 86, 24],
  [52, 45, 80, 82, 19, 47, 18, 68, 16, 92],
  [14, 65, 43, 16, 4, 79, 61, 43, 72, 88]
]
LIGNES = len(grid)      # nombre de lignes
COLONNES = len(grid[0]) # nombre de colonnes

Exemple

17	7	21	71	40	77	58	42	67	48
1	40	70	54	43	60	19	49	32	6
58	91	69	75	1	27	89	50	74	77
96	28	89	18	9	67	30	32	14	52
24	77	44	83	2	51	20	16	50	69
53	75	52	3	21	46	59	68	86	24
52	45	80	82	19	47	18	68	16	92
14	65	43	16	4	79	61	43	72	88

Le parcours marqué en gras totalise un score de : $$17 + 7 + 21 + \cdots + 92 + 88 = 702$$

Approche gloutonne

À chaque pas, on se dirige vers la case (à droite ou en bas) contenant le score maximal.

Avec un fichier

On pourrait aussi stocker le contenu de la grille dans un fichier csv comme celui-ci : grid.csv

Il faudrait alors charger le fichier pour lire la grille avant de pouvoir chercher le parcours.

À faire

Un module

# glouton.py

def glouton(grid) -> str:
    """
    grid: tableau 2D contenant des entiers
    renvoie le parcours fait de mouvements H, B, G, D
    donnant le parcours glouton de coin supérieur gauche
    au coin inférieur droit
    """
 
def load_grid(filename:str):
    """
    filename: nom de fichier
    renvoie la grille contenu dans le fichier
    """

Une première démo :

# demo1.py

from glouton import glouton

grid = [
  [17, 7, 21, 71, 40, 77, 58, 42, 67, 48],
  [1, 40, 70, 54, 43, 60, 19, 49, 32, 6],
  [58, 91, 69, 75, 1, 27, 89, 50, 74, 77],
  [96, 28, 89, 18, 9, 67, 30, 32, 14, 52],
  [24, 77, 44, 83, 2, 51, 20, 16, 50, 69],
  [53, 75, 52, 3, 21, 46, 59, 68, 86, 24],
  [52, 45, 80, 82, 19, 47, 18, 68, 16, 92],
  [14, 65, 43, 16, 4, 79, 61, 43, 72, 88]
]
LIGNES = len(grid)      # nombre de lignes
COLONNES = len(grid[0]) # nombre de colonnes

# utilisation de la fonction et affichage de la réponse

et une deuxième démonstration

#demo2.py

import glouton

glouton.load_grid("grid.csv")

# utilisation de la fonction et affichage de la réponse

17	7	21	71	40	77	58	42	67	48
1	40	70	54	43	60	19	49	32	6
58	91	69	75	1	27	89	50	74	77
96	28	89	18	9	67	30	32	14	52
24	77	44	83	2	51	20	16	50	69
53	75	52	3	21	46	59	68	86	24
52	45	80	82	19	47	18	68	16	92
14	65	43	16	4	79	61	43	72	88

17	7	21	71	40	77	58	42	67	48
1	40	70	54	43	60	19	49	32	6
58	91	69	75	1	27	89	50	74	77
96	28	89	18	9	67	30	32	14	52
24	77	44	83	2	51	20	16	50	69
53	75	52	3	21	46	59	68	86	24
52	45	80	82	19	47	18	68	16	92
14	65	43	16	4	79	61	43	72	88

17	7	21	71	40	77	58	42	67	48
1	40	70	54	43	60	19	49	32	6
58	91	69	75	1	27	89	50	74	77
96	28	89	18	9	67	30	32	14	52
24	77	44	83	2	51	20	16	50	69
53	75	52	3	21	46	59	68	86	24
52	45	80	82	19	47	18	68	16	92
14	65	43	16	4	79	61	43	72	88

17	7	21	71	40	77	58	42	67	48
1	40	70	54	43	60	19	49	32	6
58	91	69	75	1	27	89	50	74	77
96	28	89	18	9	67	30	32	14	52
24	77	44	83	2	51	20	16	50	69
53	75	52	3	21	46	59	68	86	24
52	45	80	82	19	47	18	68	16	92
14	65	43	16	4	79	61	43	72	88

17	7	21	71	40	77	58	42	67	48
1	40	70	54	43	60	19	49	32	6
58	91	69	75	1	27	89	50	74	77
96	28	89	18	9	67	30	32	14	52
24	77	44	83	2	51	20	16	50	69
53	75	52	3	21	46	59	68	86	24
52	45	80	82	19	47	18	68	16	92
14	65	43	16	4	79	61	43	72	88

17	7	21	71	40	77	58	42	67	48
1	40	70	54	43	60	19	49	32	6
58	91	69	75	1	27	89	50	74	77
96	28	89	18	9	67	30	32	14	52
24	77	44	83	2	51	20	16	50	69
53	75	52	3	21	46	59	68	86	24
52	45	80	82	19	47	18	68	16	92
14	65	43	16	4	79	61	43	72	88