Un démineur en python pour la NumWorks

[Bisam]

Je pense clairement que ce qui plombe le script est l'utilisation répétée de p.append(...) et del p[0].
La gestion de la mémoire pour les listes Python est telle que lorsque l'on ne cesse de les faire changer de taille, la taille de stockage augmente.
En utilisant à la place 3 couples de coordonnées (actual, new, old), on y gagne forcément car les couples d'entiers ont une taille mémoire fixe.

Cet après-midi, je prendrai un peu de temps pour essayer de faire les modifications en ce sens.

[critor]

J'ai un script qui marche avec les 16K de tas de la NumWorks, mais je n'ose pas le présenter encore parce que c'est du saccage.

Effectivement, sur NumWorks, à chaque fois que l'on a envie d'utiliser une liste/tuple ou pire comme ici liste de listes, il faut se demander si il n'y aurait pas moyen de s'en passer.

[Extra44]

Je pense clairement que ce qui plombe le script est l'utilisation répétée de p.append(...) et del p[0].
La gestion de la mémoire pour les listes Python est telle que lorsque l'on ne cesse de les faire changer de taille, la taille de stockage augmente.
En utilisant à la place 3 couples de coordonnées (actual, new, old), on y gagne forcément car les couples d'entiers ont une taille mémoire fixe.

Je dirais que ...
C'est bien vu !


Donc
+1

[critor]

Je pense clairement que ce qui plombe le script est l'utilisation répétée de p.append(...) et del p[0].
La gestion de la mémoire pour les listes Python est telle que lorsque l'on ne cesse de les faire changer de taille, la taille de stockage augmente.
En utilisant à la place 3 couples de coordonnées (actual, new, old), on y gagne forcément car les couples d'entiers ont une taille mémoire fixe.

Je dirais que ...
C'est bien vu !


Donc
+1

Non, ça ça ne joue pas, ou du moins pas pour l'instant.
L'erreur de mémoire étant immédiate au chargement du script, c'est-à-dire avec la simple création des fonctions et variables globales en mémoire.

Donc ce sont les fonctions ainsi que les structures de données choisies pour les variables globales qui seraient à optimiser.

Après, on pourra voir si une erreur de mémoire peut effectivement se déclencher en cours de partie.

[critor]

Voici une version propre déjà nettement optimisée. Elle marche sous Omega, mais pas encore sous Epsilon.

Elle n'est pas loin de passer; si on commente les 8 dernières lignes de code l'erreur de mémoire au chargement disparaît (alors qu'avec la version d'origine il fallait commenter bien plus que ça).

Code: Tout sélectionner

from ion import keydown
from kandinsky import *
from random import randint
from time import sleep

# couleurs
def c(i):
  f,h,n = 255,127,0
  l=(f<<16|f<<8|f, 45<<16|125<<8|210, 151<<16|204<<8|4, 238<<16|185<<8|2, 244<<16|93<<8|1, 215<<16|65<<8|167, n<<16|n<<8|n, n<<16|n<<8|n, n<<16|n<<8|n,h<<16|h<<8|h,192<<16|192<<8|192,96<<16|96<<8|96,253<<16|236<<8|185)
  return (l[i]>>16,(l[i]>>8)&((1<<8)-1),l[i]&((1<<8)-1))
nb0,nb1,nb2=17,0,0

# init
p=[[6,5],[7,5]]
m = []

def deminage():
  draw_string(str(nb1),12,2,c(2));draw_string("/"+str(150-nb0),42,2,c(1));
  draw_string("Demineur",120,2)
  draw_string("mines:"+str(nb0),220,2,c(5))
  if nb1+nb0>=150:draw_string("Gagné ! ",120,2)

def decouvre(x,y):
  i=1
  while i:
    chiffre(x,y)
    for p in range(x-(x>0),x+(x<14)+1):
      for q in range(y-(y>0),y+(y<9)+1):
        if m[p][q]>=100:chiffre(p,q)
        else:m[p][q]+=m[p][q]==0;
    i=0
    for p in range(15):
      for q in range(10):
        if m[p][q]%100==1:i=1;x=p;y=q;p=14;q=9

def terrain():
  fill_rect(8,21,300,200,c(9))
  for y in range(21,243,20):fill_rect(8,y,302,1,c(10))
  for x in range(8,320,20):fill_rect(x,21,1,202,c(10))

def chiffre(x,y):
  global nb1
  cl(x,y)
  nb1+=m[x][y]%100!=42
  i=m[x][y]//100
  m[x][y]=i*100+42
  if i>=1:draw_string(str(i),13+20*x,23+20*y,c(i),c(0))
  deminage()

def minage(b=nb0):
  global nb1,nb2
  if nb2==0:start()
  nb2+=1;terrain();m.clear();draw_string(" "*28,12,2)
  for x in range(15):m.append([0 for y in range(10)])
  nb1=0
  while b:
    x, y = randint(0,14),randint(0,9)
    if m[x][y]!=999:
      m[x][y]=999;b-=1
      for p in range(max(0,x-1),min(15,x+2)):
        for q in range(max(0,y-1),min(10,y+2)):
          m[p][q]+=(m[p][q]!=999) and 100
  deminage();drone()

def start():
  fill_rect(8,21,300,200,c(9))
  # Message d'accueil, crédit, touches, etc ...
  # while not keydown(4) or not keydown(52):
  #  pass


def explose():
  draw_string("perdu ! ",120,2)
  for x in range(15):
    for y in range(10):
      if m[x][y]==999:mine(x,y)

def marche(x,y):
  if m[x][y]>=999:explose()
  elif m[x][y]>=100:chiffre(x,y)
  else:decouvre(x,y)

def survol():
  [x, y] = p[1]
  #v = m[x][y]
  gps(x,y)
  # draw_string(str(int(v/100)),20,2)
  [x, y] = p[0]
  v = m[x][y]
  if p[1]!=[x,y]:gps(x,y,(v-42)%100 and 9)
  del p[0]

def gps(x,y,i=6):
  fill_rect(9+20*x,22+20*y,19,2,c(i));fill_rect(26+20*x,22+20*y,2,19,c(i));fill_rect(9+20*x,22+20*y,2,19,c(i));fill_rect(9+20*x,39+20*y,19,2,c(i))

def drone():
  while not keydown(6):
    if keydown(0) or keydown(3) or keydown(1) or keydown(2):p.append([min(max(p[0][0]-keydown(0)+keydown(3),0),14),min(max(p[0][1]-keydown(1)+keydown(2),0),9)])
    if keydown(4):marche(p[0][0],p[0][1])
    if keydown(17) or keydown(16):drapeau(p[0][0],p[0][1])
    if keydown(52):nb2=0;nb0=22;minage(nb0);sleep(1)
    if keydown(45) or keydown(46):nb0=min(max(nb0+5*(keydown(46)-keydown(45)),10),90);minage(nb0);sleep(1)
    if len(p)>1:survol();sleep(0.120)

def drapeau(x,y):
  fill_rect(17+20*x,26+20*y,3,9,c(12)),fill_rect(17+20*x,36+20*y,3,3,c(12))

def mine(x,y):
  cl(x,y);fill_rect(12+20*x,36+20*y,13,4,c(9));fill_rect(14+20*x,34+20*y,9,2,c(11));fill_rect(17+20*x,32+20*y,3,2,c(5))

def cl(x,y):
  fill_rect(9+20*x,22+20*y,19,19,c(0))

minage(nb0)

[cent20]

Quelques commentaires sur le script :

1. Pourquoi utiliser

   Code: Tout sélectionner

   int(i/100)

   au lieu de

   Code: Tout sélectionner

   i//100

   ?
   Le deuxième est plus précis, puisque ne passant pas par les nombres réels et demande probablement moins de mémoire également (car les entiers considérés dans le script sont petits) !
2. On peut avantageusement remplacer
   

   Code: Tout sélectionner

     i = m[x][y] - m[x][y]%100
  m[x][y] = i + 42
  if i >= 100: v = int(i/100); t(str(v),13+20*(x),23+20*(y),c[v],c[0])

   
   par

   Code: Tout sélectionner

     v=m[x][y]//100
  m[x][y] = 100*v + 42
  if v: t(str(v),13+20*(x),23+20*(y),c[v],c[0])

3. Plus loin, on trouve

   Code: Tout sélectionner

   if (v-42)%100 == 0: gps(x,y,0)
    else: gps(x,y,9)

   . J'aurais plutôt écrit :

   Code: Tout sélectionner

   gps(x,y, 0 if v%100 == 42 else 9)

   à la place de ces deux lignes.
4. Tu peux utiliser la fonction d'unpacking de Python pour simplifier certaines lignes. Combiné avec les remarques ci-dessus,
   

   Code: Tout sélectionner

   def survol():
  x, y = p[1][0], p[1][1]
  v = m[x][y]
  gps(x,y)
  # t(str(int(v/100)),20,2)
  x, y = p[0][0], p[0][1]
  v = m[x][y]
  if p[1][0]!=x or p[1][1]!=y:
    if (v-42)%100==0:gps(x,y,0)
    else:gps(x,y,9)
  del p[0]

   
   deviendrait
   

   Code: Tout sélectionner

   def survol():
  x, y = p[1]
  v = m[x][y]
  gps(x,y)
  # t(str(v//100),20,2)
  x, y = p[0]
  v = m[x][y]
  if p[1]!=(x,y):
    gps(x,y,0 if v%100==42 else 9)
  del p[0]

5. On peut certainement remplacer la liste p de positions par deux ou trois couples de nombres : cela prendrait BEAUCOUP moins de place en mémoire.

Voilà, c'est tout pour les remarques qui ne témoignent que du fait que tu ne penses pas à utiliser le "sucre syntaxique" de Python... mais absolument pas de la réflexion et du boulot formidable qu'il y a derrière ce script.
Par ailleurs, l'explication sur ton site est plutôt remarquable et très pédagogique.

1. Parce que je n'ai jamais utilisé l'opérateur // jusqu'à maintenant, mais oui il est évident que c'est plus propre.
2. Jolie astuce

Code: Tout sélectionner

if v:

qui traite v comme un booléen !
3.

Code: Tout sélectionner

0 if v%100 == 42 else 9

ça m'impressionne toujours cette souplesse que permet python.
4. là encore, je ne connaissais pas cette fonction d'unpacking faute de l'avoir exploité précédemment.
5. Vu que ma liste ne contient jamais plus de 2 élément, je pensais que c'était neutre en utilisation mémoire mais au vu de la discussion qui a suivi je comprend qu'ajouter / enlever des élèments dans une liste est une mauvaise idée.

Bref j'intègre toutes ses modifications dans quelques minutes.

Merci de tes explications pointues et précise !

[cent20]

Vous venez de le briser moralement et psychologiquement

Mais non, ne t'inquiète pas.

J'espère juste que ça ne servira pas d'excuse aux core développeur de Epsilon pour conclure que finalement, 16ko pour python ça suffit !

[critor]

Léger progrès, il n'y a plus que les 7 dernières lignes de code à commenter pour que ça passe :

Code: Tout sélectionner

from ion import keydown
from kandinsky import *
from random import randint
from time import sleep

# couleurs
def c(i):
  f,h,n = 255,127,0
  l=(f<<16|f<<8|f, 45<<16|125<<8|210, 151<<16|204<<8|4, 238<<16|185<<8|2, 244<<16|93<<8|1, 215<<16|65<<8|167, n<<16|n<<8|n, n<<16|n<<8|n, n<<16|n<<8|n,h<<16|h<<8|h,192<<16|192<<8|192,96<<16|96<<8|96,253<<16|236<<8|185)
  return (l[i]>>16,(l[i]>>8)&((1<<8)-1),l[i]&((1<<8)-1))
nb0,nb1,nb2=17,0,0

# init
p=[[6,5],[7,5]]
m = []

def deminage():
  draw_string(str(nb1),12,2,c(2));draw_string("/"+str(150-nb0),42,2,c(1));
  draw_string("Demineur",120,2)
  draw_string("mines:"+str(nb0),220,2,c(5))
  if nb1+nb0>=150:draw_string("Gagné ! ",120,2)

def decouvre(x,y):
  i=1
  while i:
    chiffre(x,y)
    for p in range(x-(x>0),x+(x<14)+1):
      for q in range(y-(y>0),y+(y<9)+1):
        if m[p][q]>=100:chiffre(p,q)
        else:m[p][q]+=m[p][q]==0;
    i=0
    for p in range(15):
      for q in range(10):
        if m[p][q]%100==1:i=1;x=p;y=q;p=14;q=9

def terrain():
  fill_rect(8,21,300,200,c(9))
  for y in range(21,243,20):fill_rect(8,y,302,1,c(10))
  for x in range(8,320,20):fill_rect(x,21,1,202,c(10))

def chiffre(x,y):
  global nb1
  cl(x,y)
  nb1+=m[x][y]%100!=42
  i=m[x][y]//100
  m[x][y]=i*100+42
  if i>=1:draw_string(str(i),13+20*x,23+20*y,c(i),c(0))
  deminage()

def minage(b=nb0):
  global nb1,nb2
  if nb2==0:start()
  nb2+=1;terrain();m.clear();draw_string(" "*28,12,2)
  for x in range(15):m.append([0 for y in range(10)])
  nb1=0
  while b:
    x, y = randint(0,14),randint(0,9)
    if m[x][y]!=999:
      m[x][y]=999;b-=1
      for p in range(x-(x>0),x+(x<14)+1):
        for q in range(y-(y>0),y+(y<9)+1):
          m[p][q]+=(m[p][q]!=999) and 100
  deminage();drone()

def start():
  fill_rect(8,21,300,200,c(9))
  # Message d'accueil, crédit, touches, etc ...
  # while not keydown(4) or not keydown(52):
  #  pass


def explose():
  draw_string("perdu ! ",120,2)
  for x in range(15):
    for y in range(10):
      if m[x][y]==999:mine(x,y)

def marche(x,y):
  if m[x][y]>=999:explose()
  elif m[x][y]>=100:chiffre(x,y)
  else:decouvre(x,y)

def survol():
  [x, y] = p[1]
  #v = m[x][y]
  gps(x,y)
  # draw_string(str(int(v/100)),20,2)
  [x, y] = p[0]
  v = m[x][y]
  if p[1]!=[x,y]:gps(x,y,(v-42)%100 and 9)
  del p[0]

def gps(x,y,i=6):
  fill_rect(9+20*x,22+20*y,19,2,c(i));fill_rect(26+20*x,22+20*y,2,19,c(i));fill_rect(9+20*x,22+20*y,2,19,c(i));fill_rect(9+20*x,39+20*y,19,2,c(i))

def drone():
  while not keydown(6):
    if keydown(0) or keydown(3) or keydown(1) or keydown(2):p.append([min(max(p[0][0]-keydown(0)+keydown(3),0),14),min(max(p[0][1]-keydown(1)+keydown(2),0),9)])
    if keydown(4):marche(p[0][0],p[0][1])
    if keydown(17) or keydown(16):drapeau(p[0][0],p[0][1])
    if keydown(52):nb2=0;nb0=22;minage(nb0);sleep(1)
    if keydown(45) or keydown(46):nb0=min(max(nb0+5*(keydown(46)-keydown(45)),10),90);minage(nb0);sleep(1)
    if len(p)>1:survol();sleep(0.120)

def drapeau(x,y):
  fill_rect(17+20*x,26+20*y,3,9,c(12)),fill_rect(17+20*x,36+20*y,3,3,c(12))

def mine(x,y):
  cl(x,y);fill_rect(12+20*x,36+20*y,13,4,c(9));fill_rect(14+20*x,34+20*y,9,2,c(11));fill_rect(17+20*x,32+20*y,3,2,c(5))

def cl(x,y):
  fill_rect(9+20*x,22+20*y,19,19,c(0))

minage(nb0)

[cent20]

Effectivement, sur NumWorks, à chaque fois que l'on a envie d'utiliser une liste/tuple ou pire comme ici liste de listes, il faut se demander si il n'y aurait pas moyen de s'en passer.

Ma matrice (liste de liste) de 150 cases contenant 150 entiers et ne changeant jamais de taille occupe tant de place en mémoire que ça ? J'y suis suis attaché un peu quand même car m[x][y] est facilement compréhensible, interprétable, et facilite, il me semble, grandement la lecture du code.

[cent20]

Code: Tout sélectionner

# couleurs
def c(i):
  f,h,n = 255,127,0
  l=(f<<16|f<<8|f, 45<<16|125<<8|210, 151<<16|204<<8|4, 238<<16|185<<8|2, 244<<16|93<<8|1, 215<<16|65<<8|167, n<<16|n<<8|n, n<<16|n<<8|n, n<<16|n<<8|n,h<<16|h<<8|h,192<<16|192<<8|192,96<<16|96<<8|96,253<<16|236<<8|185)
  return (l[i]>>16,(l[i]>>8)&((1<<8)-1),l[i]&((1<<8)-1))


Là je suis en train de me faire un noeud dans le cerveau.
ça me parait beaucoup plus complexe que mon gentil tableau statique.

Code: Tout sélectionner

# couleurs
f,h,n = 255,127,0
c=[co(f,f,f), co(45,125,210), co(151,204,4), co(238,185,2), co(244,93,1), co(215,65,167), co(n,n,n), co(n,n,n), co(n,n,n),
   co(h,h,h),co(192,192,192),co(96,96,96),co(253,236,185)]


Cette fonction coûte de la mémoire non ? Le code f<<16|f<<8|f me laisse de marbre.

| : ou logique, ok admettons.
<< : décalage à droite. De quoi ? de qui ?

Je comprend que return renvoie un triplet, là dessus aucun doute.
Mais alors le reste c'est de la sorcellerie pour moi.