Un démineur en python pour la NumWorks

[critor]

Si une liste n'est jamais modifiée, autant utiliser un tuple comme je l'ai fait pour tes couleurs, ça coûte moins cher en mémoire.

Mais sinon oui, ta liste de 10 listes de 15 entiers chacune coûte cher, c'est un ajout significatif au reste.
J'estime :

• 64 octets pour la création de chaque liste, soit 64*11=704 octets
• 8 octets pour chaque ajout d'élément à ces listes, soit 150*8+10*8=1280 octets
• 28 octets pour la création de chaque entier associé à ces éléments, soit 150*28=4200 octets

Nous en sommes à 6184 octets, soit déjà 37,74% de la capacité du tas de la NumWorks rien que pour ta structure de données.
Donc rien d'étonnant aux erreurs de mémoire que tu rencontres en rajoutant des fonctions travaillant sur cette structure.

[Larwive]

Depuis quand le but d'un programme est d'être lu par des humains ?
Tu peux aussi proposer plusieurs versions de ton démineur, un complètement optimisé, et un autre plus facile à comprendre.

[critor]

Code: Select all

# 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: Select all

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

Complexe en code et occupation mémoire sont deux choses différentes. Sur NumWorks, à date nous n'avons pas trop le choix.

La structure que tu utilises pour tes couleurs coûte également très cher en mémoire.
Je remplace les tuples codant les couleurs par des entiers, comme c'était le cas avec les précédentes versions NumWorks

Un tuple (r,g,b), c'est 48+3*8+3*28=156 octets.
Alors que l'entier hexadécimal 0xRRGGBB c'est juste 28 octets.

Ta liste de tuples de couleurs occupait alors 64+13*8+13*156=2196 octets.
Mon tuple de codes couleurs n'occupe plus que 48+13*8+13*28=516 octets.

[cent20]

En utilisant les conseils de Bisam et Critor je suis en train de virer p=[[6,5],[7,5]].

Avant :

Code: Select all

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:
    gps(x,y, 0 if v%100 == 42 else 9)
  del p[0]


Après

Code: Select all

def survol():
  global x0,y0,x1,y1
  gps(x1,y1)
  if x1!=x0 or y1!=y0:
    gps(x0,y0, 0 if m[x0][y0]%100 == 42 else 9)
  x0, y0 = x1,y1


Je me demande même à quoi sert la boucle if vu que la fonction survol() n'est censé être appelée que si on bouge ...

et du coup la fonction drone() je simplifie singulièrement :

Avant :

Code: Select all

def drone():
  global nb0
  while not k(5):
    if k(0):p.append([max(p[0][0]-1,0),p[0][1]])
    if k(3):p.append([min(p[0][0]+1,14),p[0][1]])
    if k(1):p.append([p[0][0],max(p[0][1]-1,0)])
    if k(2):p.append([p[0][0],min(p[0][1]+1,9)])
    if k(4):marche(p[0][0],p[0][1])
    if k(17) or k(16):drapeau(p[0][0],p[0][1])
    if k(52):nb0=19;minage(nb0)
    if k(45):nb0=min(nb0+3,42);minage(nb0)
    if k(46):nb0=max(nb0-3,11);minage(nb0)
    if len(p)>1:survol();s(0.120)
  print("A bientot !")


après :

Code: Select all

def drone():
  global nb0,x0,y0,x1,y1
  while not k(5):
    if k(0) or k(3) or k(1) or k(2):
      x1,y1=min(max(x0-k(0)+k(3),0),14),min(max(y0-k(1)+k(2),0),9)
      survol();s(0.120)
    if k(4):marche(x0,y0)
    if k(17) or k(16):drapeau(x0,y0)
    if k(52):nb0=19;minage(nb0)
    if keydown(45) or keydown(46):nb0=min(max(nb0+5*(k(46)-k(45)),10),90);minage(nb0)
  print("A bientot !")


J'en ai profité pour y intégrer ceci : min(max(x0-k(0)+k(3),0),14),min(max(y0-k(1)+k(2),0),9) , proposé par critor, cela permet de se déplacer en diagonal directement. J'étais certain que critor me fusionnerait les 4 déplacements en un !

Grace à toutes ses modifications, et en y intégrant les astuces de Bizam la taille passe de 3.09ko à 2.91ko

[cent20]

Après intégration des diverses améliorations de Bisam et Critor (les plus faciles à comprendre), le script mis à jour est désormais (https://workshop.numworks.com/python/cent20/demine) :

Code: Select all

#v1.1 28/02/2020
from ion import keydown
from kandinsky import *
from random import randint
from time import sleep

# cut
co=color
a,r,t,l,k,s=set_pixel,fill_rect,draw_string,range,keydown,sleep

# 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)]
nb0,nb1=19,0

# init
x0,y0,x1,y1=6,5,7,5
m = []

def deminage():
  global nb0,nb1
  t(str(nb1),12,2,c[2]);
  if nb1+nb0>=150:t("Gagné ! ",120,2)

def decouvre(x,y):
  i=1
  while i>0:
    chiffre(x,y)
    for p in l(max(0,x-1),min(15,x+2)):
      for q in l(max(0,y-1),min(10,y+2)):
        if m[p][q]>=100:chiffre(p,q)
        elif m[p][q]==0:m[p][q]+=1
    i=0
    for p in l(15):
      for q in l(10):
        if m[p][q]%100==1:i=1;x=p;y=q;p=14;q=9
 
def terrain():
  r(8,21,300,200,c[9])
  for y in l(21,243,20):
    for x in l(8,309):
      a(x,y,c[10])
  for x in l(8,320,20):
    for y in l(21,222):
      a(x,y,c[10])

def chiffre(x,y):
  global nb1
  cl(x,y)
  nb1+=(m[x][y]%100!=42)
  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])
  deminage()

def minage(b=nb0,g=0):
  if g:start()
  t(" "*28,12,2)
  t("/"+str(150-nb0),42,2,c[1]);
  t("Demineur",120,2)
  t("mines:"+str(nb0),220,2,c[5])
  terrain();m.clear();
  for x in range(15):m.append([0 for y in range(10)])
  nb1=0
  while b>0:
    x, y = randint(0,14),randint(0,9)
    if m[x][y]!=999:
      m[x][y]=999;b-=1
      for p in l(max(0,x-1),min(15,x+2)):
        for q in l(max(0,y-1),min(10,y+2)):
          if m[p][q]!=999:m[p][q]+=100
  deminage();s(0.5)

def start():
  t("Demineur",120,42,c[4])
  t("par cent20",110,62,c[1])
  t("https://nsi.xyz/demine",42,82,c[6])
  t("[OK] [Clear] [+] [-] [EXE]",32,122,c[2])
  s(4)

def explose():
  t("perdu ! ",120,2)
  for x in l(15):
    for y in l(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():
  global x0,y0,x1,y1
  gps(x1,y1)
  if x1!=x0 or y1!=y0:
    gps(x0,y0, 0 if m[x0][y0]%100 == 42 else 9)
  x0, y0 = x1,y1 
 
def gps(x,y,i=6):
  r(9+20*x,22+20*y,19,2,c[i]);r(26+20*x,22+20*y,2,19,c[i]);r(9+20*x,22+20*y,2,19,c[i]);r(9+20*x,39+20*y,19,2,c[i])

def drone():
  global nb0,x0,y0,x1,y1
  while not k(5):
    if k(0) or k(3) or k(1) or k(2):
      x1,y1=min(max(x0-k(0)+k(3),0),14),min(max(y0-k(1)+k(2),0),9)
      survol();s(0.120)
    if k(4):marche(x0,y0)
    if k(17) or k(16):drapeau(x0,y0)
    if k(52):nb0=19;minage(nb0)
    if keydown(45) or keydown(46):nb0=min(max(nb0+3*(k(45)-k(46)),11),42);minage(nb0)
  print("A bientot !")

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

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

minage(g=1);drone()

En poussant beaucoup plus loin, en supprimant l'écran d'accueil, en supprimant le codage des couleurs dans un tableau, en fusionnant toutes les fonctions appelées une unique fois (au détriment de la lisibilité du code) on arrive à ceci https://workshop.numworks.com/python/cent20/demine2

Code: Select all

#v1.1lite 28/02/2020
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=19,0

# init
x0,y0,x1,y1=6,5,7,5
m = []

def deminage():
  global nb0,nb1
  draw_string(str(nb1),12,2,c(2));
  if nb1+nb0>=150:draw_string("Gagné ! ",120,2)

def decouvre(x,y):
  i=1
  while i>0:
    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 chiffre(x,y):
  global nb1
  fill_rect(9+20*x,22+20*y,19,19,c(0))
  nb1+=(m[x][y]%100!=42)
  v=m[x][y]//100
  m[x][y] = 100*v + 42
  if v: draw_string(str(v),13+20*(x),23+20*(y),c(v),c(0))
  deminage()

def minage(b=nb0):
  draw_string(" "*28,12,2)
  draw_string("/"+str(150-nb0),42,2,c(1));
  draw_string("Demineur",120,2)
  draw_string("mines:"+str(nb0),220,2,c(5))
  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))
  m.clear();
  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();sleep(0.5)

def marche(x,y):
  if m[x][y]>=999:
    draw_string("perdu ! ",120,2)
    for x in range(15):
      for y in range(10):
        if m[x][y]==999:
          fill_rect(9+20*x,22+20*y,19,19,c(0));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))
  elif m[x][y]>=100:chiffre(x,y)
  else:decouvre(x,y)

def survol():
  global x0,y0,x1,y1
  gps(x1,y1)
  if x1!=x0 or y1!=y0:
    gps(x0,y0, 0 if m[x0][y0]%100 == 42 else 9)
  x0, y0 = x1,y1 

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():
  global nb0,x0,y0,x1,y1
  while not keydown(5):
    if keydown(0) or keydown(3) or keydown(1) or keydown(2):
      x1,y1=min(max(x0-keydown(0)+keydown(3),0),14),min(max(y0-keydown(1)+keydown(2),0),9)
      survol();sleep(0.120)
    if keydown(4):marche(x0,y0)
    if keydown(17):fill_rect(17+20*x0,26+20*y0,3,9,c(12));fill_rect(17+20*x0,36+20*y0,3,3,c(12))
    if keydown(52):nb0=19;minage(nb0)
    if keydown(45) or keydown(46):nb0=min(max(nb0+3*(keydown(45)-keydown(46)),11),42);minage(nb0)

minage()
survol()
drone()

Et cette version tourne sur une NumWorks stock, c'est à dire animé par l'OS Epsilon et son tas python ridicule de 16ko.

Comme précisé dans le chat de TI-Planet, espérons que ce recodage ne servira pas de justification à l'équipe des dev de NumWorks de ne rien faire concernant ces 16ko.

Les utilisateurs de l'OS stock de la NumWorks peuvent louer le travail remarquable de recodage de ce script, et je me joint à eux car d'une part je n'y croyais pas, et d'autre part je trouve ces astuces (notamment celle sur le codage des couleurs) impressionnantes.

L'analyse de l'utilisation en mémoire python d'une matrice de 150 cases (6ko) calculée précédemment par Critor est effrayante, sidérante, déconcertante.

Des problèmes demeurent :

- la version "lite" utilise au maximum les 16ko disponibles, et il ne reste donc plus aucune place pour des dev ultérieurs, comme par exemple une vrai gestion de la victoire / défaite, car pour l'instant il est possible de continuer à jouer quand on a perdu / gagné.
- le code de la version lite est pédagogiquement moins pertinent pour un utilisateur débutant en python (mais un délice pour un codeur avancé), sans compter que l'on a du renoncer au format PEP8 depuis longtemps

Abstraction

Il est possible de faire un démineur autrement, de stocker les positions dans une unique liste de 11-42 cases, donc cela consommerait uniquement entre 64+11*(8+28)=460 octets et 64+42*(8+28)=1576 octets mais il faudrait coder des fonctions qui déterminent en temps réel (et pas au début du programme) le nombre de bombes dans l'environnement proche en parcourant à chaque fois cette liste de 11 à 42 cases. C'est cette méthode que j'utilisais dans mon antique démineur sur Casion 9960GT, mais cela passait par l'utilisation d'une autre liste de case à traiter, liste dont la taille est difficilement estimable à l'avance (notamment s'il y a peu de bombes).

En résumé

un grand bravo à Critor et Bisam, de sincères remerciement pour leur aide précieuse, le reste dépendra du NumWorks.

[Lionel Debroux]

Bien joué pour ces optimisations

Le sucre syntaxique peut nuire à la lisibilité, mais l'optimisation y nuit encore davantage, ça se voit.

[cent20]

Bien joué pour ces optimisations

Le sucre syntaxique peut nuire à la lisibilité, mais l'optimisation y nuit encore davantage, ça se voit.

Au fait je t'ai cité dans mon article de présentation
Si cela te dérange je peux te mettre un pseudo

[Lionel Debroux]

Pas de problème, ça fait environ 18 ans que j'utilise mon vrai nom dans la communauté calculatrices graphiques TI

[critor]

Merci, un article de bonne facture à la lecture fort intéressante et agréable, de quoi passionner tes meilleurs éléments et au-delà.
https://nsi.xyz/demine

Tout petit détail qui m'a fait trébucher et m'a sorti un moment de ma lecture, reverrait → rêverait.
N'hésite pas à donner trois baffes de ma part à ton nègre esclave, d'une façon ou d'une autre je suis sûr que c'est de sa faute.

Et n'oublie pas de pointer la version finale de l'article à NumWorks.

[Extra44]

https://nsi.xyz/demine

Tout petit détail qui m'a fait trébucher et m'a sorti un moment de ma lecture, reverrait → rêverait.

Et aussi tiplanetE.org