piccola sfida

[lombardp]

Originariamente inviato da a2000
comunque tornando a bomba, nuovo record:

4000 x 4000 in 5.2 secondi !!!

Una domanda: ma programmi così veloci trovano sempre la soluzione per qualsiasi punto di partenza, oppure possono fallire?

[a2000]

Originariamente inviato da a2000
comunque tornando a bomba, nuovo record:

4000 x 4000 in 5.2 secondi !!!

con questo:

Program Quadrante

Parameter (iMax = 4000, jMax = 4000)
Integer(1), allocatable :: v( : , : )
Integer(1) vMin, h, Di(1 : 8), Dj(1 : 8)
Real(8) tm0, Dtm
Allocate (v(-2 : iMax + 3, -2 : jMax + 3))
 
 Di(1) = 3; Dj(2) = 3; Dj(3) = -3; Di(4) = -3
 Di(5) = 2; Dj(5) = 2
 Di(6) = 2; Dj(6) = -2
 Di(7) = -2; Dj(7) = 2
 Di(8) = -2; Dj(8) = -2
 
 !orlatura
 v = 0
 Do i = 1, Int(0.5 * iMax + 1); Do j = 1, Int(0.5 * jMax + 1)
  v(i, j) = 9 - (8 + (j < 4) + 2 * (j < 3) + (i < 4) + 2 * (i < 3) + (j < 3) * (i < 3))
  v(iMax + 1 - i, j) = v(i, j); v(i, jMax + 1 - j) = v(i, j); v(iMax + 1 - i, jMax + 1 - j) = v(i, j)
 End Do; End Do
 
 
 i = 1; j = 1
 Do k = 1, iMax * jMax
  v(i, j) = -hMin
  vMin = -100
  Do h = 1, 8
   ih = i + Di(h); jh = j + Dj(h)
   v(ih, jh) = v(ih, jh) - (v(ih, jh) > 0)
  If (v(ih, jh) > vMin) Then
   vMin = v(ih, jh); hMin = h
  End If
  End Do
  If (vMin < 1) Exit
  i = i + Di(hMin); j = j + Dj(hMin)
 End Do


End Program

[a2000]

Originariamente inviato da lombardp
Una domanda: ma programmi così veloci trovano sempre la soluzione per qualsiasi punto di partenza, oppure possono fallire?

posterò la versione Excel-VBA così potrai verificare

[lombardp]

Originariamente inviato da a2000
posterò la versione Excel-VBA così potrai verificare

Ok, ci conto!!

Intanto mi sono messo a vedere il tuo prog e volevo chiederti un parere su un'idea che mi è venuta (ammesso di non aver preso fischi per fiaschi ).

Sarebbe applicabile al tuo prog questo approccio?


1) Trasformare la matrice di un array monodimensionale lungo (IMAX+6)*(JMAX+6) con orlatura, inizializzato al solito modo ma tenendo conto della monodimensionalità:

 Do i = 4, iMax+3;  Do j = 4, jMax+3
  v(i*(iMax+6)+j) = 9 - (8 + (j < 7) + 2 * (j < 6) + (i < 7) + 2 * (i < 6) + (j < 6) * (i < 6))
 End Do; End Do

2) Trasformare la coppia di vettori degli spostamenti in un unico vettore di spostamento unidimensionale fatto dei seguenti valori (se IMAX è la lunghezza di una riga):

DD(1) = 3;
DD(2) = 2*(IMAX+6)+2
DD(3) = 3*(IMAX+6)
DD(4) = 2*(IMAX+6)-2
DD(5) = -3
DD(6) = -2*(IMAX+6)-2
DD(7) = -3*(IMAX+6)
DD(8) = -2*(IMAX+6)+2

che sono l'equivalente monodimensionale di quelli bidimensionali, però hanno senso solamente con l'orlatura di 3 celle, altrimenti ai bordi è come incrociare i flussi.


3) La trasformazione in unidimensionale fa si che l'orlatura si interallacci con i punti buoni, però a occhio non ci dovrebbero essere problemi, perché di fatto l'orlatura è come un'area di matrice già visitata (mi sbaglio?).
A parte eventuali errori più o meno così:

 i = (RIGAdiPARTENZA+3)*iMax + (COLONNAdiPARTENZA+3)
 Do k = 1, iMax * jMax
  v(i) = -hMin
  vMin = -100
  Do h = 1, 8
   ih = i + DD(h);
   v(ih) = v(ih) - (v(ih)>0)
  If (v(ih) > vMin) Then
   vMin = v(ih); hMin = h
  End If
  End Do
  If (vMin < 1) Exit
  i = i + DD(hMin);
 End Do

[a2000]

mi piace la tua idea !

If (sei ancora in fase formativa) Then
 sviluppala ! :cool:

ElseIf (non hai un c. di meglio da fare)
 sviluppala :O

Else
 ma sì, bisogna tenersi sempre in allenamento: sviluppala nei ritagli di tempo :)

End If

[lombardp]

Questo è il prog. ricorsivo che le trova tutte, nella versione unidimensionale:

#include <stdlib.h>
#define LATO 5

int p[(LATO+6)*(LATO+6)];
int dd[8] = {3,2*(LATO+6)+2,3*(LATO+6),2*(LATO+6)-2,-3,-2*(LATO+6)-2,-3*(LATO+6),-2*(LATO+6)+2};
int i,j;

void piazza(int pos,int n=1) {
   int k;
   if (p[pos]==0) {
      p[pos] = n;
      if (n==(LATO*LATO)) 
         for (i=3;i<(LATO+3);i++) {
            for (j=3;j<(LATO+3);j++) printf("%3i ",p[i*(LATO+6)+j]);
            printf("\n");
         }
         printf("\n");
      }
      else for (k=0;k<8;k++) piazza(pos+dd[k],n+1);
      p[pos] = 0;
   }
}

void main(int argc, char* argv[])
{
   for (i=0;i<(LATO+6);i++)
      for (j=0;j<(LATO+6);j++)
         if ((i<3)|(i>LATO+2)|(j<3)|(j>LATO+2)) p[i*(LATO+6)+j] = -1; else p[i*(LATO+6)+j] = 0;
   piazza((atoi(argv[1])+3)*(LATO+6)+atoi(argv[2])+3);
}

[a2000]

Originariamente inviato da lombardp
Questo è il prog. ricorsivo che le trova tutte, nella versione unidimensionale:
....

ma, come hai visto, tutte sono ... troppe.

[lombardp]

Originariamente inviato da a2000
ma, come hai visto, tutte sono ... troppe.

Ho provato ad introdurre nel prog. di cui sopra un criterio di esplorazione dell'albero simile a quello che usi nel tuo prog. per trovare la strada.

In pratica invece di esplorare le diramazioni in ordine (dalla prima all'ottava), calcolo i collegamenti residui su ciascuna delle celle 8 celle collegate, mi faccio una classifica e le esploro dalla migliore alla peggiore.

Il prog. trova ancora tutte le soluzioni e in un tempo un po' più lungo dati i maggiori calcoli, però mi aspettavo che le primissime uscissero quasi istantaneamente... e invece serve ancora un bel po'... avrò sbagliato qualcosa.

[cionci]

Originariamente inviato da a2000
comunque tornando a bomba, nuovo record:

4000 x 4000 in 5.2 secondi !!!

Però se sfrutta le SSE2 non vale !!!

[cionci]

Originariamente inviato da a2000

 Di(1) = 3; Dj(2) = 3; Dj(3) = -3; Di(4) = -3
 Di(5) = 2; Dj(5) = 2
 Di(6) = 2; Dj(6) = -2
 Di(7) = -2; Dj(7) = 2
 Di(8) = -2; Dj(8) = -2

Mi hai copiato

[a2000]

non copio mai nessuno.
non uso librerie.
non uso codice fatto da altri.
non uso software fatto da altri ad eccezione di: Win98SE, un compilatore Fortran, Office (as GUI)

diciamo che ho un'impostazione ... autistica alla programmazione.

[a2000]

Originariamente inviato da cionci
Azzz.non avevo pensato a memorizzare solamente gli spostamenti...

[a2000]

Originariamente inviato da a2000
non copio mai nessuno.
non uso librerie.
non uso codice fatto da altri.
non uso software fatto da altri ad eccezione di: Win98SE, un compilatore Fortran, Office (as GUI)

diciamo che ho un'impostazione ... autistica alla programmazione.

è sbagliato ! .... ma terribilmente romantico

romantico come Marconi nella sua soffitta:

[cionci]

Originariamente inviato da a2000
non copio mai nessuno.

Guarda il mio codice e vedrai che io avevo memorizzato i vari spostamenti da testare in due vettori

[a2000]

mi dispiace, non l'ho guardato e non so neanche come funziona.

[misterx]

Originariamente inviato da a2000
mi dispiace, non l'ho guardato e non so neanche come funziona.

male ragazzo, troppo male: non è leale e poco rispettoso

[a2000]

ma no, tranquillo.

massimo rispetto.

un atteggiamento cool.

[a2000]

anzi "milanese"

[a2000]

cionci ti sei offeso ?

[a2000]

non si è offeso.