Recuperer plus grand produit

**Neolex** · 20/09/2013, 18h16

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

**VinsS** · 20/09/2013, 20h03

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 ?

**Neolex** · 20/09/2013, 20h09

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 !

**Neolex** · 22/09/2013, 17h37

UP , si quelqu'un aurait une idée du problème de mon code , je suis toujours bloqué dessus ....

**VinsS** · 22/09/2013, 18h29

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.

**dividee** · 22/09/2013, 23h00

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.

**Neolex** · 23/09/2013, 16h15

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")

**Neolex** · 23/09/2013, 18h25

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")

**Clodion** · 23/09/2013, 21h17

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

**Neolex** · 23/09/2013, 21h24

Merci beaucoup , c'est complètement normal que ça marchait pas alors... j'y avais pas pensé ...

merci à tous !

**Clodion** · 23/09/2013, 21h42

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

**Neolex** · 23/09/2013, 21h46

Finalement , j'ai abandonné numpy .
Effectivement vraiment très propre comme solution je trouve aussi ,
merci pour le partage .

**dividee** · 23/09/2013, 22h41

Envoyé par Clodion

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

**Clodion** · 23/09/2013, 23h21

Envoyé par dividee

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

**dividee** · 24/09/2013, 00h14

Envoyé par Clodion

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.

**Neolex** · 24/09/2013, 00h20

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 !

Recuperer plus grand produit

Python

Discussions similaires

Partager

Partager