IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Recuperer plus grand produit


Sujet :

Python

  1. #1
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut Recuperer plus grand produit
    j'essaye de faire un exercice d'un site , voici la consigne :

    What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
    J'ai beau vérifier et re vérifier , je ne vois pas où est le problème dans mon code ...

    le voici :

    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    #!/usr/local/bin/python3.3 
    # -*-coding:utf-8 -*
     
    def GreatestProduct():
    	grid = [[8,2,22,97,38,15,00,40,00,75,4,5,7,78,52,12,50,77,91,8],
    [49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,00],
    [81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65],
    [52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,36,91],
    [22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],
    [24,47,32,60,99,3,45,2,44,75,33,53,78,36,84,20,35,17,12,50],
    [32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],
    [67,26,20,68,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],
    [24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],
    [21,36,23,9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95],
    [78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92],
    [16,39,5,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57],
    [86,56,00,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58],
    [19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40],
    [4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66],
    [88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69],
    [4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36],
    [20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16],
    [20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54],
    [1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48]]
     
     
    	max = 0 
     
    	#Boucle de haut en bas
    	i=0
    	j=0
    	while i<17:
    		while j<20:
    			num = grid[i][j]*grid[i+1][j]*grid[i+2][j]*grid[i+3][j]
    			if num >max:
    				max = num
    			j+=1
    		i+=1
    	# Boucle de bas en haut
    	i=3
    	j=0
    	while i<20:
    		while j<20:
    			num = grid[i][j]*grid[i-1][j]*grid[i-2][j]*grid[i-3][j]
    			if num > max:
    				max = num
    			j+=1
    		i+=1
     
    	#boucle de gauche à droite
    	i=0
    	j=0
    	while i<20:
    		while j<17:
    			num = grid[i][j]*grid[i][j+1]*grid[i][j+2]*grid[i][j+3]
    			if num > max :
    				max = num
    			j+=1
    		i+=1
     
    	#boucle de droite à gauche
    	i=0
    	j=3
    	while i<20:
    		while j<20:
    			num = grid[i][j]*grid[i][j-1]*grid[i][j-2]*grid[i][j-3]
    			if num > max:
    				max =num
    			j+=1
    		i+=1
     
    	#boucle diagonale bas droite
    	i = 0
    	j = 0
    	while i<17:
    		while j<17:
    			num = grid[i][j]*grid[i+1][j+1]*grid[i+2][j+2]*grid[i+3][j+3]
    			if num > max :
    				max = num
    			j+=1
    		i+=1
     
    	#boucle diagonale bas gauche
    	i=0
    	j=3
    	while i<17:
    		while j<20:
    			num = grid[i][j]*grid[i+1][j-1]*grid[i+2][j-2]*grid[i+3][j-3]
    			if num > max:
    				max =num
    			j+=1
    		i+=1
     
     
    	print(str(max))
     
     
    GreatestProduct();

    Je trouve un max inférieur à ce que je devrais trouver , j'ai pourtant l'impression de tester toutes les possibilités ...

  2. #2
    Expert confirmé

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    4 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 4 307
    Par défaut
    Salut,

    Je me pose une question, pourquoi en lisant une ligne de gauche à droite aurait-tu un résultat différent qu'en la lisant en sens inverse ?

    Exemple avec ta première ligne:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
     
    n = [8,2,22,97,38,15,00,40,00,75,4,5,7,78,52,12,50,77,91,8]
     
    def find_max(l):
        mx = 0
        for i in range(len(l)-3):
            tt = l[i]
            for j in range(i+1, i+4):
                tt *= l[j]
     
            if tt > mx:
                mx = tt
                pos = i
     
        print ">>", pos, mx
     
    find_max(n)
    n.reverse()
    find_max(n)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    >> 15 4204200
    >> 1 4204200
    Pareil pour la lecture verticale et diagonale, non ?

  3. #3
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut
    Oui je viens de me rendre compte de ça il y a environ 15 minutes .
    J'ai donc retiré quelques parties de mon code .
    Par contre je n'ai toujours pas trouvé le problème dans mon code , je crois que je vais arrêter de chercher pour aujourd'hui , je m'y remettrais à tête reposée demain.

    Merci en tout cas !

  4. #4
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut
    UP , si quelqu'un aurait une idée du problème de mon code , je suis toujours bloqué dessus ....

  5. #5
    Expert confirmé

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    4 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 4 307
    Par défaut
    Si tu sépares tes opérations, tu verras plus clair, et au moyen de divers print judicieusement placés tu pourras voir évoluer le résultat

    Quelque chose comme ceci:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
     
    GRID = [[8,2,22,97,38,15,00,40,00,75,4,5,7,78,52,12,50,77,91,8],
    [49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,00],
    ...
    [1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48]]
     
    def greatest_product():
        direction = 'horizontal'
        line, column, greatest = get_horizontal_max()
     
        ln, cl, gt = get_vertical_max()
        if gt > greatest:
            direction = 'vertical'
            line, column, greatest = ln, cl, gt
     
        ln, cl, gt = get_diagonal_from_left_max()
        if gt > greatest:
            direction = 'diagonal_from_left'
            line, column, greatest = ln, cl, gt
     
        ln, cl, gt = get_diagonal_from_right_max()
        if gt > greatest:
            direction = 'diagonal_from_right'
            line, column, greatest = ln, cl, gt
     
        return greatest, column, line, direction
     
    def get_horizontal_max():
        mx = 0
        for idx, line in enumerate(GRID):
            for i in range(17):
                tt = l[i]
                for j in range(i+1, i+4):
                    tt *= l[j]
     
                if tt > mx:
                    mx = tt
                    col = i
                    ln = idx
     
        return ln, col, mx
     
    def get_vertical_max():
        mx = 0
        for col in range(20):
            for ln range(17):
     
                ...
     
    def get_diagonal_from_left_max():
        mx =0
     
        ...
     
    def get_diagonal_from_right_max():
        mx = 0
     
        ...
     
    sum_max, posX, posY, direction = greatest_product()
    # sum_max est le produit maximal
    # posX, posY sont les coordonnées du premier nombre de quatre dans la grille
    # direction est le sens dans lequel on a trouvé le nombre
    print "Le nombre maximum %s blabla ..."
    Je te laisse remplir les vides.

  6. #6
    Membre Expert
    Homme Profil pro
    Inscrit en
    Mars 2007
    Messages
    941
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2007
    Messages : 941
    Par défaut
    Ca me semble être une bonne occasion d'utiliser numpy, ça.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    grid = [[...]]
    import numpy as np
     
    grid = np.array(grid)
     
    prod2 = grid[:,:-1] * grid[:,1:]
    prod4 = prod2[:,:-2] * prod2[:,2:]
    hmax = np.max(prod4)
    Ca permet de trouver le produit max. en horizontal. Le code pour les 3 autres directions (verticale, diagonale descendante et diagonale montante) est très similaire.

    Remarquez que dans le code ci-dessus, il n'y a que 2 multiplications par élément au lieu de 3 avec la solution naïve.

  7. #7
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut
    Merci à vous deux , je vais essayer de suivre le conseil de VinsS en séparant mes opérations , puis une fois réussi j'essayerais d'apprendre à utiliser numpy.
    Je vous tiens au courant ,

    Merci beaucoup pour votre aide .


    EDIT : j'ai essayer de le faire en separant les opérations , je trouve toujours pas le bon nombre , je devrais le trouver dans la fonction qui va de haut en bas vers la gauche ...
    Voici mon code :
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    #!/usr/local/bin/python3.3 
    # -*-coding:utf-8 -*
     
    GRID = [
    [ 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8],
    [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0],
    [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65],
    [52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 36, 91],
    [22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80],
    [24, 47, 32, 60, 99,  3, 45,  2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50],
    [32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70],
    [67, 26, 20, 68,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21],
    [24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
    [21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95],
    [78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92],
    [16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57],
    [86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
    [19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40],
    [ 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
    [88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
    [ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36],
    [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16],
    [20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54],
    [ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48],
    ]
     
     
     
     
     
     
     
     
    def greatest_product():
        direction = 'horizontal'
        line, column, greatest = get_horizontal_max()
     
        ln, cl, gt = get_vertical_max()
        if gt > greatest:
            direction = 'vertical'
            line, column, greatest = ln, cl, gt
     
        ln, cl, gt = get_diagonal_from_left_max()
        if gt > greatest:
            direction = 'diagonal_from_left'
            line, column, greatest = ln, cl, gt
     
        ln, cl, gt = get_diagonal_from_right_max()
        if gt > greatest:
            direction = 'diagonal_from_right'
            line, column, greatest = ln, cl, gt
     
        return greatest, column, line, direction
     
    def get_horizontal_max():
        mx = 0
        for idx, line in enumerate(GRID):
            for i in range(17):
                tt = line[i]
                for j in range(i+1, i+4):
                    tt *= line[j]
     
                if tt > mx:
                    mx = tt
                    col = i
                    ln = idx
     
        print("horizontal : " + str(mx))
        return ln, col, mx
     
    def get_vertical_max():
        mx = 0
        for col in range(20):
            for ln in range(17):  
                prod = GRID[ln][col]*GRID[ln+1][col]*GRID[ln+2][col]*GRID[ln+3][col]
                if prod>mx:
                    mx = prod
                    col = col
                    ln = ln
        print("vertical : " + str(mx))
        return ln,col,mx
     
     
    def get_diagonal_from_left_max():
        mx =0
        for ln in range(17):
            for col in range(17):
                prod = GRID[ln][col]*GRID[ln+1][col+1]*GRID[ln+2][col+2]*GRID[ln+3][col+3]
                if prod>mx:
                    mx = prod
                    col = col
                    ln = ln
        print("diagonal left : " + str(mx))
        return ln,col,mx
     
    def get_diagonal_from_right_max():
        mx = 0
        for ln in range(17):
            for col in range(3,20):
                    prod=GRID[ln][col]*GRID[ln+1][col-1]*GRID[ln+2][col-2]*GRID[ln+3][col-2]
                    if prod>mx:
                        mx = prod
                        col = col
                        ln = ln
        print("diagonal right : " + str(mx))
        return ln,col,mx
     
     
    sum_max, posX, posY, direction = greatest_product()
    # sum_max est le produit maximal
    # posX, posY sont les coordonnées du premier nombre de quatre dans la grille
    # direction est le sens dans lequel on a trouvé le nombre
    print("\nLe nombre maximum :"+str(sum_max));
    print("\n pos["+str(posX)+"]["+str(posY)+"] = "+str(GRID[posX][posY])+"\n direction :" + direction + "\n")

  8. #8
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut
    Désolé du double post mais j'ai enfin réussi en modifiant la derniere fonction :

    Je vais essayer d'apprendre à utiliser numpy maintenant .

    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    #!/usr/local/bin/python3.3 
    # -*-coding:utf-8 -*
     
    GRID = [
    [ 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8],
    [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0],
    [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65],
    [52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 36, 91],
    [22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80],
    [24, 47, 32, 60, 99,  3, 45,  2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50],
    [32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70],
    [67, 26, 20, 68,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21],
    [24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
    [21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95],
    [78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92],
    [16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57],
    [86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
    [19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40],
    [ 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
    [88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
    [ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36],
    [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16],
    [20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54],
    [ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48],
    ]
     
     
     
     
     
     
     
     
    def greatest_product():
        direction = 'horizontal'
        line, column, greatest = get_horizontal_max()
     
        ln, cl, gt = get_vertical_max()
        if gt > greatest:
            direction = 'vertical'
            line, column, greatest = ln, cl, gt
     
        ln, cl, gt = get_diagonal_from_left_max()
        if gt > greatest:
            direction = 'diagonal_from_left'
            line, column, greatest = ln, cl, gt
     
        ln, cl, gt = get_diagonal_from_right_max()
        if gt > greatest:
            direction = 'diagonal_from_right'
            line, column, greatest = ln, cl, gt
     
        return greatest, column, line, direction
     
    def get_horizontal_max():
        mx = 0
        for idx, line in enumerate(GRID):
            for i in range(17):
                tt = line[i]
                for j in range(i+1, i+4):
                    tt *= line[j]
     
                if tt > mx:
                    mx = tt
                    col = i
                    ln = idx
     
        print("horizontal : " + str(mx))
        return ln, col, mx
     
    def get_vertical_max():
        mx = 0
        for ln in range(17):
            for col in range(20):  
                prod = GRID[ln][col]*GRID[ln+1][col]*GRID[ln+2][col]*GRID[ln+3][col]
                if prod>mx:
                    mx = prod
                    col = col
                    ln = ln
        print("vertical : " + str(mx))
        return ln,col,mx
     
     
    def get_diagonal_from_left_max():
        mx =0
        for ln in range(17):
            for col in range(17):
                prod = GRID[ln][col]*GRID[ln-1][col-1]*GRID[ln-2][col-2]*GRID[ln-3][col-3]
                if prod>mx:
                    mx = prod
                    col = col
                    ln = ln
        print("diagonal left : " + str(mx))
        return ln,col,mx
     
    def get_diagonal_from_right_max():
        mx = 0
        for ln in range(0,17):
            for col in range(3,20):
                    prod=GRID[ln][col]*GRID[ln+1][col-1]*GRID[ln+2][col-2]*GRID[ln+3][col-3]
                    if prod>mx:
                        mx = prod
                        col = col
                        ln = ln
        print("diagonal right : " + str(mx))
        return ln,col,mx
     
     
    sum_max, posX, posY, direction = greatest_product()
    # sum_max est le produit maximal
    # posX, posY sont les coordonnées du premier nombre de quatre dans la grille
    # direction est le sens dans lequel on a trouvé le nombre
    print("\nLe nombre maximum :"+str(sum_max));
    print("\n pos["+str(posX)+"]["+str(posY)+"] = "+str(GRID[posX][posY])+"\n direction :" + direction + "\n")

  9. #9
    Membre émérite
    Homme Profil pro
    Aucune activité
    Inscrit en
    Novembre 2011
    Messages
    505
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Aucune activité

    Informations forums :
    Inscription : Novembre 2011
    Messages : 505
    Par défaut
    Coucou,
    Dans le premier message, il y une erreur de logique sur les while:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    	i=0
    	j=0
    	while i<17:
    		while j<20:
    			num = grid[i][j]*grid[i+1][j]*grid[i+2][j]*grid[i+3][j]
    			if num >max:
    				max = num
    			j+=1
    		i+=1
    La boucle interne parcours 0->19 puis c'est la boucle externe qui entre en action. Mais entre les deux, la variable j n'est pas remise à zéro.
    En conséquence, la boucle interne est parcourue une seule et unique fois.

    PS: ceci est valable pour l'ensemble des boucles while imbriquées.

    Ce qui est dans le code original:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    >>> i, j = 0, 0
    >>> while i<17:
    	while j<20:
    		print(i,j, sep=":", end=" ")
    		j+=1
    	i+=1
     
     
    0:0 0:1 0:2 0:3 0:4 0:5 0:6 0:7 0:8 0:9 0:10 0:11 0:12 0:13 0:14 0:15 0:16 0:17 0:18 0:19
    En insérant la réinitialisation de la boucle interne à l'intérieur de la boucle externe:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    >>> i, j = 0, 0
    >>> while i<17:
    	j= 0
    	while j<20:
    		print(i, j, sep=":", end=" ")
    		j+= 1
    	print(end="\n")
    	i+= 1
     
     
    0:0 0:1 0:2 0:3 0:4 0:5 0:6 0:7 0:8 0:9 0:10 0:11 0:12 0:13 0:14 0:15 0:16 0:17 0:18 0:19 
    1:0 1:1 1:2 1:3 1:4 1:5 1:6 1:7 1:8 1:9 1:10 1:11 1:12 1:13 1:14 1:15 1:16 1:17 1:18 1:19 
    2:0 2:1 2:2 2:3 2:4 2:5 2:6 2:7 2:8 2:9 2:10 2:11 2:12 2:13 2:14 2:15 2:16 2:17 2:18 2:19 
    3:0 3:1 3:2 3:3 3:4 3:5 3:6 3:7 3:8 3:9 3:10 3:11 3:12 3:13 3:14 3:15 3:16 3:17 3:18 3:19 
    4:0 4:1 4:2 4:3 4:4 4:5 4:6 4:7 4:8 4:9 4:10 4:11 4:12 4:13 4:14 4:15 4:16 4:17 4:18 4:19 
    5:0 5:1 5:2 5:3 5:4 5:5 5:6 5:7 5:8 5:9 5:10 5:11 5:12 5:13 5:14 5:15 5:16 5:17 5:18 5:19 
    6:0 6:1 6:2 6:3 6:4 6:5 6:6 6:7 6:8 6:9 6:10 6:11 6:12 6:13 6:14 6:15 6:16 6:17 6:18 6:19 
    7:0 7:1 7:2 7:3 7:4 7:5 7:6 7:7 7:8 7:9 7:10 7:11 7:12 7:13 7:14 7:15 7:16 7:17 7:18 7:19 
    8:0 8:1 8:2 8:3 8:4 8:5 8:6 8:7 8:8 8:9 8:10 8:11 8:12 8:13 8:14 8:15 8:16 8:17 8:18 8:19 
    9:0 9:1 9:2 9:3 9:4 9:5 9:6 9:7 9:8 9:9 9:10 9:11 9:12 9:13 9:14 9:15 9:16 9:17 9:18 9:19 
    10:0 10:1 10:2 10:3 10:4 10:5 10:6 10:7 10:8 10:9 10:10 10:11 10:12 10:13 10:14 10:15 10:16 10:17 10:18 10:19 
    11:0 11:1 11:2 11:3 11:4 11:5 11:6 11:7 11:8 11:9 11:10 11:11 11:12 11:13 11:14 11:15 11:16 11:17 11:18 11:19 
    12:0 12:1 12:2 12:3 12:4 12:5 12:6 12:7 12:8 12:9 12:10 12:11 12:12 12:13 12:14 12:15 12:16 12:17 12:18 12:19 
    13:0 13:1 13:2 13:3 13:4 13:5 13:6 13:7 13:8 13:9 13:10 13:11 13:12 13:13 13:14 13:15 13:16 13:17 13:18 13:19 
    14:0 14:1 14:2 14:3 14:4 14:5 14:6 14:7 14:8 14:9 14:10 14:11 14:12 14:13 14:14 14:15 14:16 14:17 14:18 14:19 
    15:0 15:1 15:2 15:3 15:4 15:5 15:6 15:7 15:8 15:9 15:10 15:11 15:12 15:13 15:14 15:15 15:16 15:17 15:18 15:19 
    16:0 16:1 16:2 16:3 16:4 16:5 16:6 16:7 16:8 16:9 16:10 16:11 16:12 16:13 16:14 16:15 16:16 16:17 16:18 16:19 
    >>>
    Avec ces modifications, ce code semble donner le bon résultat terminal, mais les résultats intermédiaire ne me semblent pas tous au point.

    Numpy n'évitera pas les erreurs de boucles ;-)

    Clodion

  10. #10
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut
    Merci beaucoup , c'est complètement normal que ça marchait pas alors... j'y avais pas pensé ...

    merci à tous !

  11. #11
    Membre émérite
    Homme Profil pro
    Aucune activité
    Inscrit en
    Novembre 2011
    Messages
    505
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Aucune activité

    Informations forums :
    Inscription : Novembre 2011
    Messages : 505
    Par défaut
    Coucou,
    Sur ce même problème, il y a une solution que, personnellement, je trouve vraiment très "classe"…
    (en tous cas, nettement plus concise que celle que j'ai pu produire)

    Utiliser Numpy ici, ressemble à écraser une mouche au marteau…

    Clodion

  12. #12
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut
    Finalement , j'ai abandonné numpy .
    Effectivement vraiment très propre comme solution je trouve aussi ,
    merci pour le partage .

  13. #13
    Membre Expert
    Homme Profil pro
    Inscrit en
    Mars 2007
    Messages
    941
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2007
    Messages : 941
    Par défaut
    Citation Envoyé par Clodion Voir le message
    Utiliser Numpy ici, ressemble à écraser une mouche au marteau…
    Oui enfin, ça se discute. Ecraser une mouche au marteau, c'est pas efficace.
    La solution avec numpy est élégante et rapide, quand on a pigé le truc:

    Plus rapides de 3 runs:
    code "classe": 3.55 ms
    numpy: 0.88 ms

    Sur un tableau de 1000x1000 (au lieu de 20x20):
    code "classe": 4.43 s
    numpy : 0.23 s

  14. #14
    Membre émérite
    Homme Profil pro
    Aucune activité
    Inscrit en
    Novembre 2011
    Messages
    505
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Aucune activité

    Informations forums :
    Inscription : Novembre 2011
    Messages : 505
    Par défaut
    Citation Envoyé par dividee Voir le message
    Oui enfin, ça se discute. Ecraser une mouche au marteau, c'est pas efficace.
    La solution avec numpy est élégante et rapide, quand on a pigé le truc:

    Plus rapides de 3 runs:
    code "classe": 3.55 ms
    numpy: 0.88 ms

    Sur un tableau de 1000x1000 (au lieu de 20x20):
    code "classe": 4.43 s
    numpy : 0.23 s
    Bonsoir,
    Oui, tout à fait d'accord quand à Numpy.

    Et si j'ai trouvé que la solution en lien était "classe", c'est que j'avoue ne pas y avoir pensé et avoir pondu un script quelque peu plus lourd! :-D

    Il s'agit ici, cependant, d'un exercice connu (la matrice et la question apparaissent beaucoup sur le réseau)… J'ai donc supposé que la résolution avec les outils connus par Neolex était préférable.
    Sa première demande était la correction de problèmes de code (en particulier les boucles while). Le diriger vers des outils nettement plus compliqués était-elle souhaitable?

    Clodion

  15. #15
    Membre Expert
    Homme Profil pro
    Inscrit en
    Mars 2007
    Messages
    941
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2007
    Messages : 941
    Par défaut
    Citation Envoyé par Clodion Voir le message
    Sa première demande était la correction de problèmes de code (en particulier les boucles while). Le diriger vers des outils nettement plus compliqués était-elle souhaitable?
    D'accord, j'avoue que je me suis un peu emballé. Mais je me suis dit que ça valait la peine de présenter un algo qui se généralise en O(N^2*log(M)) au lieu de O(N^2*M) (N=20 et M=4 ici). Il peut être écrit sans passer par numpy, bien sûr, mais ça devient nettement plus complexe à écrire.

  16. #16
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut
    Merci pour la réponse , je repasserais dessus en utilisant numpy pour l'optimiser quand j'aurais le temps et la motivation .

    Merci à tout le monde pour votre aide !

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [2008R2] Recuperer la valeur avec la plus grande date
    Par guigui69 dans le forum Développement
    Réponses: 1
    Dernier message: 01/08/2013, 12h47
  2. [WD14] recuperer le plus grand nombre dans une table
    Par devalender dans le forum WinDev
    Réponses: 6
    Dernier message: 03/11/2010, 20h16
  3. Réponses: 6
    Dernier message: 01/11/2010, 18h40
  4. Recuperer le plus grand, le plus petit et la moyenne !
    Par ksper92 dans le forum Langage SQL
    Réponses: 2
    Dernier message: 05/04/2007, 16h24
  5. [Tableaux] Recuperer le plus grand indice d'un tableau
    Par schnito dans le forum Langage
    Réponses: 4
    Dernier message: 31/01/2006, 20h01

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo