[Vari] Contest 15 - Pagina 5

~FullSyst3m~ · 15-06-2009, 10:38

Quote:

Originariamente inviato da rеpne scasb

Ho corretto il bug del precedente codice. In seguito alla correzione il sudoku di DanieleC88 non era ancora risolvibile. Ho quindi aggiunto un altro metodo risolutivo basato sull'analisi del legame di 4 segni su 4 posizioni univoche. Adesso viene risolto anche il sudoku di DanieleC88. I tempi di risoluzione si sono allungati e sono sull'ordine dei 60 milionesimi di secondo.

Codice:

#include <stdio.h>
#include <time.h>

#define N_CLK 2
#define INPUT_FILE_NAME "SUDOKU.DAT"
#define SIZE 9
#define CELL (SIZE/3)
#define ANY_VAL ((1<<SIZE)-1)
#define C9 126

int main(void)

{
    clock_t clk[N_CLK];
    FILE *input_file_handle;
    int b,c1,c2,c3,i,j,k,l,m,n,o,p,q,sp,sw,sv=SIZE*SIZE,sk[SIZE][SIZE],ts[SIZE][SIZE],va[SIZE],vb[SIZE],vc[SIZE],vd[SIZE];
    int cc[C9]={0x000F,0x0017,0x0027,0x0047,0x0087,0x0107,0x001B,0x002B,0x004B,0x008B,0x010B,0x0033,0x0053,0x0093,0x0113,0x0063,0x00A3,0x0123,0x00C3,0x0143,0x0183,0x001D,0x002D,0x004D,0x008D,0x010D,0x0035,0x0055,0x0095,0x0115,0x0065,0x00A5,0x0125,0x00C5,0x0145,0x0185,0x0039,0x0059,0x0099,0x0119,0x0069,0x00A9,0x0129,0x00C9,0x0149,0x0189,0x0071,0x00B1,0x0131,0x00D1,0x0151,0x0191,0x00E1,0x0161,0x01A1,0x01C1,0x001E,0x002E,0x004E,0x008E,0x010E,0x0036,0x0056,0x0096,0x0116,0x0066,0x00A6,0x0126,0x00C6,0x0146,0x0186,0x003A,0x005A,0x009A,0x011A,0x006A,0x00AA,0x012A,0x00CA,0x014A,0x018A,0x0072,0x00B2,0x0132,0x00D2,0x0152,0x0192,0x00E2,0x0162,0x01A2,0x01C2,0x003C,0x005C,0x009C,0x011C,0x006C,0x00AC,0x012C,0x00CC,0x014C,0x018C,0x0074,0x00B4,0x0134,0x00D4,0x0154,0x0194,0x00E4,0x0164,0x01A4,0x01C4,0x0078,0x00B8,0x0138,0x00D0,0x0158,0x0198,0x00E8,0x0168,0x01A8,0x01C8,0x00F0,0x0170,0x01B0,0x01D0,0x01E0};

    if((input_file_handle=fopen(INPUT_FILE_NAME,"rt"))==NULL)
    {
	fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME "\n");
	return 1;
    }

    for(sw=sv,i=0;i<SIZE;i++)
    {
	for(j=0;j<SIZE;j++)
	{
	    fscanf(input_file_handle,"%d,",&sk[i][j]);
	    if(sk[i][j])
		sv--;
	}
    }

    if(fclose(input_file_handle))
    {
	fprintf(stderr,"Errore durante fclose\n");
	return 1;
    }

    printf("*** Input ***\n\n");

    for(i=0;i<SIZE;i++)
    {
	for(j=0;j<SIZE;j++)
	    printf("%d ",sk[i][j]);
	printf("\n");
    }

    clk[0]=clock();

    for(i=0;i<SIZE;i++)
    {
	for(j=0;j<SIZE;j++)
	    ts[i][j]=ANY_VAL;
    }

    for(i=0;i<SIZE;i++)
    {
        for(j=0;j<SIZE;j++)
	{
	    if(sk[i][j])
	    {
	        for(k=0;k<SIZE;k++)
		{
		    ts[k][j]&=ANY_VAL-(1<<(sk[i][j]-1));
		    ts[i][k]&=ANY_VAL-(1<<(sk[i][j]-1));
		}
 	        for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
		{
		    for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
		        ts[k][l]&=ANY_VAL-(1<<(sk[i][j]-1));
		}
	    }
	}
    }

    do
    {
	for(b=0;b<SIZE;b++)
	{
	    for(i=0;i<SIZE;i++)
	    {
	        for(l=j=0;j<SIZE;j++)
		{
		    if(sk[i][j]==0)
		    {
		        if(ts[i][j]&(1<<b))
			{
			    l++;
			    m=j;
			}
		    }
		}
		if(l==1)
		{
		    sk[i][m]=b+1;
		    sv--;
		    for(k=0;k<SIZE;k++)
		    {
			ts[k][m]&=ANY_VAL-(1<<b);
			ts[i][k]&=ANY_VAL-(1<<b);
		    }
		    for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
		    {
		        for(l=(m/CELL)*CELL;l<((m/CELL)*CELL+CELL);l++)
		            ts[k][l]&=ANY_VAL-(1<<b);
		    }
		}
	    }
	    for(j=0;j<SIZE;j++)
	    {
	        for(l=i=0;i<SIZE;i++)
	        {
	    	    if(sk[i][j]==0)
		    {
		        if(ts[i][j]&(1<<b))
			{
			    l++;
			    m=i;
			}
		    }
		}
	        if(l==1)
		{
		    sk[m][j]=b+1;
		    sv--;
		    for(k=0;k<SIZE;k++)
		    {
			ts[k][j]&=ANY_VAL-(1<<b);
			ts[m][k]&=ANY_VAL-(1<<b);
		    }
		    for(k=(m/CELL)*CELL;k<((m/CELL)*CELL+CELL);k++)
		    {
		        for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
		            ts[k][l]&=ANY_VAL-(1<<b);
		    }
		}
	    }
	    for(i=0;i<SIZE;i+=CELL)
	    {
		for(j=0;j<SIZE;j+=CELL)
		{
		    for(n=0,k=i;k<(i+CELL);k++)
		    {
			for(l=j;l<(j+CELL);l++)
			{
	    	    	    if(sk[k][l]==0)
		    	    {
		                if(ts[k][l]&(1<<b))
			        {
			    	    n++;
			    	    m=k;
				    o=l;
			  	}
			    }
			}
		    }			
	            if(n==1)
		    {
		        sk[m][o]=b+1;
		        sv--;
		        for(k=0;k<SIZE;k++)
			{
			    ts[k][o]&=ANY_VAL-(1<<b);
			    ts[m][k]&=ANY_VAL-(1<<b);
			}
		        for(k=(m/CELL)*CELL;k<((m/CELL)*CELL+CELL);k++)
		        {
		            for(l=(o/CELL)*CELL;l<((o/CELL)*CELL+CELL);l++)
		                ts[k][l]&=ANY_VAL-(1<<b);
		        }
		    }
		}
	    }
	}
        
	for(i=0;i<SIZE;i++)
        {
	    for(j=0;j<SIZE;j++)
	    {
	        if(sk[i][j]==0)
	        {
		    for(k=b=0;b<SIZE;b++)
		    {
			if(ts[i][j]&(1<<b))
			{
			    k++;
			    n=b;
			}
		    }
		    if(k==1)
		    {
		        sk[i][j]=n+1;
			sv--;
		        for(k=0;k<SIZE;k++)
		        {
			    ts[k][j]&=ANY_VAL-(1<<n);
			    ts[i][k]&=ANY_VAL-(1<<n);
		        }
		        for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
		        {
		            for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
		                ts[k][l]&=ANY_VAL-(1<<n);
		        }
		    }
		}
	    }
	}

	for(sp=i=0;i<SIZE;i++)
	{
	    for(j=0;j<(SIZE-1);j++)
	    {
		if(sk[i][j]==0)
		{
		    for(n=b=0;b<SIZE;b++)
		    {
			if(ts[i][j]&(1<<b))
			    n++;
		    }
		    if(n==2)
		    {
			for(k=j+1;k<SIZE;k++)
			{
			    if(sk[i][k]==0)
			    {
			        if(ts[i][j]==ts[i][k])
			        {
				    for(l=0;l<SIZE;l++)
				    {
				        if((l!=k)&&(l!=j)&&(sk[i][l]==0))
					{
					    o=ts[i][l];
					    ts[i][l]&=~ts[i][j];
					    if(ts[i][l]!=o)
						sp=1;
					}
				    }
				    break;
			        }
			    }
			}
		    }
		}
	    }
	}

	for(j=0;j<SIZE;j++)
	{
	    for(i=0;i<(SIZE-1);i++)
	    {
		if(sk[i][j]==0)
		{
		    for(n=b=0;b<SIZE;b++)
		    {
			if(ts[i][j]&(1<<b))
			    n++;
		    }
		    if(n==2)
		    {
			for(k=i+1;k<SIZE;k++)
			{
			    if(sk[k][j]==0)
			    {
			        if(ts[i][j]==ts[k][j])
			        {
				    for(l=0;l<SIZE;l++)
				    {
				        if((l!=k)&&(l!=i)&&(sk[l][j]==0))
					{
					    o=ts[l][j];
					    ts[l][j]&=~ts[i][j];
					    if(ts[l][j]!=o)
						sp=1;
					}
				    }
				    break;
			        }
			    }
			}
		    }
		}
	    }
	}

        for(i=0;i<SIZE;i+=CELL)
	{
	    for(j=0;j<SIZE;j+=CELL)
	    {
	        for(k=i;k<(i+CELL);k++)
	        {
		    for(l=j;l<(j+CELL);l++)
		    {
	    	        if(sk[k][l]==0)
		        {
		    	    for(m=b=0;b<SIZE;b++)
		    	    {
			        if(ts[k][l]&(1<<b))
			    	    m++;
		    	    }
		    	    if(m==2)
		    	    {
				for(m=k;m<(i+CELL);m++)
				{
				    for(n=l+1;n<(j+CELL);n++)
				    {
				        if(sk[m][n]==0)
			                {
			        	    if(ts[k][l]==ts[m][n])
			        	    {
					        for(o=i;o<(i+CELL);o++)
					        {
						    for(p=j;p<(j+CELL);p++)
						    {
							c1=k*SIZE+l;
							c2=m*SIZE+n;
							c3=o*SIZE+p;
						        if((c3!=c1)&&(c3!=c2)&&(sk[o][p]==0))
							{
							    q=ts[o][p];
					    		    ts[o][p]&=~ts[k][l];
					    		    if(ts[o][p]!=q)
								sp=1;
							}
				    		    }
						}
				    		break;
					    }
			        	}
			    	    }
				}
			    }
			}
		    }
		}
	    }
	}

	for(i=0;i<SIZE;i++)
	{
	    for(b=0;b<SIZE;b++)
	    {
	        for(va[b]=vb[b]=j=0;j<SIZE;j++)
	        {
		    if(sk[i][j]==0)
		    {
			if(ts[i][j]&(1<<b))
			{
			    va[b]|=1<<j;
			    vb[b]++;
			}
		    }		    
		}
	    }
	    for(j=0;j<(SIZE-1);j++)
	    {
		if(vb[j]==2)
		{
		    for(k=j+1;k<SIZE;k++)
		    {
			if(vb[k]==2)
			{
			    if(va[j]==va[k])
			    {
				l=(1<<j)|(1<<k);
				for(m=0;m<SIZE;m++)
				{
				    if(va[j]&(1<<m))
				    {
					if(ts[i][m]!=l)
					    sp=1;
					ts[i][m]=l;
				    }
				}
			    }
			}
		    }
		}
	    }
	}

	for(j=0;j<SIZE;j++)
	{
	    for(b=0;b<SIZE;b++)
	    {
	        for(va[b]=vb[b]=i=0;i<SIZE;i++)
	        {
		    if(sk[i][j]==0)
		    {
			if(ts[i][j]&(1<<b))
			{
			    va[b]|=1<<i;
			    vb[b]++;
			}
		    }		    
		}
	    }
	    for(i=0;i<(SIZE-1);i++)
	    {
		if(vb[i]==2)
		{
		    for(k=i+1;k<SIZE;k++)
		    {
			if(vb[k]==2)
			{
			    if(va[i]==va[k])
			    {
				l=(1<<i)|(1<<k);
				for(m=0;m<SIZE;m++)
				{
				    if(va[i]&(1<<m))
				    {
					if(ts[m][j]!=l)
					    sp=1;
					ts[m][j]=l;
				    }
				}
			    }
			}
		    }
		}
	    }
	}

        for(i=0;i<SIZE;i+=CELL)
	{
	    for(j=0;j<SIZE;j+=CELL)
	    {
	        for(q=0,k=i;k<(i+CELL);k++)
	        {
	            for(l=j;l<(j+CELL);l++,q++)
		    {
			vc[q]=ts[k][l];
			vd[q]=sk[k][l];
		    }
		}
	        for(b=0;b<SIZE;b++)
	        {
	            for(va[b]=vb[b]=k=0;k<SIZE;k++)
	            {
		        if(vd[k]==0)
		        {
			    if(vc[k]&(1<<b))
			    {
			        va[b]|=1<<k;
			        vb[b]++;
			    }
		        }
		    }
	        }
	        for(k=0;k<(SIZE-1);k++)
	        {
		    if(vb[k]==2)
		    {
		        for(l=k+1;l<SIZE;l++)
		        {
			    if(vb[l]==2)
			    {
			        if(va[k]==va[l])
			        {
			    	    m=(1<<k)|(1<<l);
			            for(n=0;n<SIZE;n++)
			            {
			        	if(va[k]&(1<<n))
			        	{
			  	    	    if(vc[n]!=m)
				            	sp=1;
				    	    vc[n]=m;
					}
		 	    	    }
				}
		    	    }
			}
		    }
		}
	        for(q=0,k=i;k<(i+CELL);k++)
	        {
	            for(l=j;l<(j+CELL);l++,q++)
			ts[k][l]=vc[q];
		}
	    }
	}

        for(i=0;i<SIZE;i+=CELL)
        {
	    for(j=0;j<SIZE;j+=CELL)
	    {
	        for(b=0;b<SIZE;b++)
	        {
	            for(m=0,k=i;k<(i+CELL);k++)
	            {
	                for(l=j;l<(j+CELL);l++)
	                {
	   	            if(sk[k][l]==0)
		            {
		                if(ts[k][l]&(1<<b))
		                {
		  	            va[m]=k-i;
			            vb[m]=l-j;
			            m++;
			        }
			    }
			}
		    }
		    if(m==2)
		    {
		        if(va[0]==va[1])
		        {
		            for(k=0;k<SIZE;k++)
			    {
			        if((k<j)||(k>(j+CELL)))
			        {
			            q=ts[va[0]+i][k];
				    ts[va[0]+i][k]&=~(1<<b);
				    if(q!=ts[va[0]+i][k])
				        sp=1;
			        }
			    }
			}
			if(vb[0]==vb[1])
			{
		    	    for(k=0;k<SIZE;k++)
			    {
			        if((k<i)||(k>(i+CELL)))
			        {
			            q=ts[k][vb[0]+j];
			            ts[k][vb[0]+j]&=~(1<<b);
			            if(q!=ts[k][vb[0]+j])
			 	        sp=1;
			        }
			    }
			}
		    }
		    if(m==3)
		    {
		        if((va[0]==va[1])&&(va[0]==va[2]))
		        {
		            for(k=0;k<SIZE;k++)
			    {
			        if((k<j)||(k>(j+CELL)))
			        {
				    q=ts[va[0]+i][k];
				    ts[va[0]+i][k]&=~(1<<b);
				    if(q!=ts[va[0]+i][k])
				        sp=1;
			        }
			    }
		        }
		        if((vb[0]==vb[1])&&(vb[0]==vb[2]))
		        {
		    	    for(k=0;k<SIZE;k++)
			    {
			        if((k<i)||(k>(i+CELL)))
			        {
			            q=ts[k][vb[0]+j];
			            ts[k][vb[0]+j]&=~(1<<b);
				    if(q!=ts[k][vb[0]+j])
				        sp=1;
			        }
			    }
		        }
		    }
		}
	    }
        }

	if((sv==sw)&&(sp==0))
	{
	    for(i=0;i<SIZE;i++)
	    {
	        for(q=0;q<C9;q++)
	        {
	            for(k=j=0;j<SIZE;j++)
	            {
		        if(sk[i][j]==0)
		        {
			    if((ts[i][j]|cc[q])==cc[q])
			        k++;
		        }
	            }
		    if(k==4)
		    {
	                for(j=0;j<SIZE;j++)
	                {
			    if(sk[i][j]==0)
			    {
			        if((ts[i][j]|cc[q])!=cc[q])
			        {
				    p=ts[i][j];
				    ts[i][j]&=~cc[q];
				    if(p!=ts[i][j])
				        sp=1;
			        }
			    }
		        }
		    }
	    	    if(sp==1)
			break;
	        }
	        if(sp==1)
		    break;
	    }

	    if(sp==0)
	    {	
	        for(j=0;j<SIZE;j++)
	        {
	            for(q=0;q<C9;q++)
	            {
	                for(k=i=0;i<SIZE;i++)
	                {
		            if(sk[i][j]==0)
		            {
			        if((ts[i][j]|cc[q])==cc[q])
			            k++;
		            }
	                }
		        if(k==4)
		        {
	                    for(i=0;i<SIZE;i++)
	                    {
			        if(sk[i][j]==0)
			        {
			            if((ts[i][j]|cc[q])!=cc[q])
			            {
				        p=ts[i][j];
				        ts[i][j]&=~cc[q];
				        if(p!=ts[i][j])
				            sp=1;
			            }
			        }
		            }
		        }
	    	        if(sp==1)
			    break;
	            }
	            if(sp==1)
		        break;
	        }
	    }
	}

	if((sv==sw)&&(sp==0))
	{
	    printf("\n*** Soluzione parziale (%d) ***\n\n",sv);

	    for(i=0;i<SIZE;i++)
    	    {
		for(j=0;j<SIZE;j++)
		{
		    if(sk[i][j])
	    	        printf("%d      ",sk[i][j]);
		    else
		    {
		        for(k=b=0;b<SIZE;b++)
		        {
			    if(ts[i][j]&(1<<b))
			    {
				printf("%d",b+1);
				k++;
			    }
			}
			for(l=0;l<(SIZE-k-2);l++)
			    printf(" ");
		    }
		}
		printf("\n");
	    }
	    return 1;
	}
	else
	    sw=sv;
    } while (sv);

    clk[1]=clock();

    printf("\n*** Soluzione ***\n\n");

    for(i=0;i<SIZE;i++)
    {
	for(j=0;j<SIZE;j++)
	    printf("%d ",sk[i][j]);
	printf("\n");
    }

    printf("\nTempo per ricercare la soluzione: %7.3f secondi\n",(double)(clk[1]-clk[0])/CLK_TCK);

    return 0;
}

Che casino, mi sembra arabo

malocchio · 15-06-2009, 10:42

Quote:

Originariamente inviato da rеpne scasb

Ho corretto il bug del precedente codice. In seguito alla correzione il sudoku di DanieleC88 non era ancora risolvibile. Ho quindi aggiunto un altro metodo risolutivo basato sull'analisi del legame di 4 segni su 4 posizioni univoche. Adesso viene risolto anche il sudoku di DanieleC88. I tempi di risoluzione si sono allungati e sono sull'ordine dei 60 milionesimi di secondo.

Codice:

[CUT]

Ho due domande:

1. utilizzando questo metodo di procedimento, ovvero inserendo metodi di eliminazione/inserimento/ottimizzazione, come fa ad avere la certezza che il programma riesca a risolvere qualsiasi istanza di Sudoku?

2. perdonami ma non riesco a leggere il tuo codice, ma ho una domandina facile: hai per caso implementato una qualche sorta di stack?

rеpne scasb · 15-06-2009, 10:51

■

Kralizek · 15-09-2009, 17:21

resuscito questo topic per linkare questo video quanto mai azzeccato!

http://www.youtube.com/watch?v=Mp8Y2yjV4fU

skeleton · 15-09-2009, 18:38

salve a tutti,
è possibile risolvere questo sudoku in batch???
Non importa quanto tempo impiega, mi interesserebbe solo sapere il codice per farlo.

Grazie in anticipo per il vostro sicuro aiuto.

skeleton · 21-09-2009, 13:47

up

gugoXX · 07-12-2009, 17:20

Ecco.

Dato questo input

Una soluzione SQL, sotto Oracle che permette le query ricorsive, e' questa

Codice:

with x( s, ind ) as
( select sud, instr( sud, ' ' )
  from ( select '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79' sud from dual )
  union all
  select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
       , instr( s, ' ', ind + 1 )
  from x
     , ( select to_char( rownum ) z
         from dual
         connect by rownum <= 9
       ) z
  where ind > 0
  and not exists ( select null
                   from ( select rownum lp
                          from dual
                          connect by rownum <= 9
                        )
                   where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
                   or    z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
                   or    z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
                                      + trunc( ( ind - 1 ) / 27 ) * 27 + lp
                                      + trunc( ( lp - 1 ) / 3 ) * 6
                                   , 1 )
                 )
)
select s
from x
where ind = 0

Come si puo' vedere, la sanita' mentale tende e a zero molto velocemente.
Il risultato eseguito:

Ed eventualmente riprocessato

http://technology.amis.nl/blog/6404/...uery-factoring

malocchio · 07-12-2009, 21:33

Quote:

Originariamente inviato da gugoXX

Ecco.

Dato questo input

Una soluzione SQL, sotto Oracle che permette le query ricorsive, e' questa

Codice:

with x( s, ind ) as
( select sud, instr( sud, ' ' )
  from ( select '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79' sud from dual )
  union all
  select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
       , instr( s, ' ', ind + 1 )
  from x
     , ( select to_char( rownum ) z
         from dual
         connect by rownum <= 9
       ) z
  where ind > 0
  and not exists ( select null
                   from ( select rownum lp
                          from dual
                          connect by rownum <= 9
                        )
                   where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
                   or    z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
                   or    z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
                                      + trunc( ( ind - 1 ) / 27 ) * 27 + lp
                                      + trunc( ( lp - 1 ) / 3 ) * 6
                                   , 1 )
                 )
)
select s
from x
where ind = 0

Come si puo' vedere, la sanita' mentale tende e a zero molto velocemente.
Il risultato eseguito:

Ed eventualmente riprocessato

http://technology.amis.nl/blog/6404/...uery-factoring

La devo presentare alla mia prof di informatica, che crede di interndersene di db

VICIUS · 08-12-2009, 00:42

Quote:

Originariamente inviato da gugoXX

Ecco.

Dato questo input

Una soluzione SQL, sotto Oracle che permette le query ricorsive, e' questa
...

Come è messo a prestazioni? I tempi sono paragonabili ad altre soluzioni scritte con sistemi più "normali"?

gugoXX · 08-12-2009, 01:01

Quote:

Originariamente inviato da VICIUS

Come è messo a prestazioni? I tempi sono paragonabili ad altre soluzioni scritte con sistemi più "normali"?

Nono, lenta. Piu' lenta di quella in C# di almeno 10 volte.

shinya · 08-12-2009, 11:13

Quote:

Originariamente inviato da gugoXX

Nono, lenta. Piu' lenta di quella in C# di almeno 10 volte.

Sarei curioso di vedere l'execution plan... riesci a postarlo?

Purtroppo non ho un 11g sotto mano...

gugoXX · 08-12-2009, 13:28

Quote:

Originariamente inviato da shinya

Sarei curioso di vedere l'execution plan... riesci a postarlo?

Purtroppo non ho un 11g sotto mano...

Niente Toad per ora, e un execution plan sotto SqlPlus non lo consiglio.
Vedo cosa posso fare.
Comunque dovrebbe funzionare anche su una 8i

shinya · 08-12-2009, 14:48

Quote:

Originariamente inviato da gugoXX

Niente Toad per ora, e un execution plan sotto SqlPlus non lo consiglio.
Vedo cosa posso fare.
Comunque dovrebbe funzionare anche su una 8i

Eh no, purtroppo il 'recursive subquery factoring' come l'hanno chiamato è una feature dell'11gR2... intendo quel "with x ... as ... select ... from x..." dove fai il 'from x' della 'x' che dichiare nella 'with'. Forse mi sono ingarbugliato con le parole..

gugoXX · 08-12-2009, 15:49

SI', hai ragione. Non posso richiamare la With all'interno della With stessa sotto 10g.
Mi sa che dovremo aspettare per il piano d'esecuzione allora.
Immagino tante belle "Connect By Pump".

^TiGeRShArK^ · 08-12-2009, 22:00

Spettacolo!

Io averi preferito un calcio nei coglioni piuttosto che anche solo provare a scrivere qualcosa di simile in SQL.

flx2000 · 10-12-2009, 11:22

Mi aggiungo al coro di complimenti per rеpne scasb. Fa veramente piacere sentir parlare in italiano una persona tanto abile con gli algoritmi (e con l'offuscamento artistico del codice).
Complimenti davvero, ho visto tardi questo topic per poter partecipare al contest, ma sono felice di esserci comunque approdato per averci trovato numerose menti brillanti.

gugoXX · 10-12-2009, 11:27

Quote:

Originariamente inviato da flx2000

Mi aggiungo al coro di complimenti per rеpne scasb. Fa veramente piacere sentir parlare in italiano una persona tanto abile con gli algoritmi (e con l'offuscamento artistico del codice).
Complimenti davvero, ho visto tardi questo topic per poter partecipare al contest, ma sono felice di esserci comunque approdato per averci trovato numerose menti brillanti.

Comunque i contest non sono scaduti

Puoi sempre provare questo e anche gli altri. Sono esercizi penso interessanti, un po' al di la' anche di alcuni test universitari necessariamente focalizzati su qualche punto invece che cosi' aperti.

Qui gli altri, secondo cortese lista offerta da Vincenzo1968, il nostro segretario nonche' boia (strano accoppiamento)

Quote:

Contest 1: Bitmap

Contest 2: Ricerca

Contest 3: La somma

Contest 4: DNA

Contest 5: Sottomatrici

Contest 6: Parsing

Contest 7: Il lotto

Proposta

Contest 8: Compattamento Barionico

Contest 9: Divisori dei numeri triangolari

Contest 10: Numeri palindormi (Semplice)

Contest 11: Change. NP-Hard.

Contest 12: Il muro

Contest 13: Date

Contest 14: Corsa delle macchine

Contest 15: sudoku

Contest 16: Intervalli

Contest 17: Compilatori e interpreti. Parte I: interpreti.

Edit: Vincenzo1968 ci tiene a fare sapere che non si ritiene un boia, ma "solo" un inquisitore.

marco.r · 25-12-2009, 23:08

Come attivita' natalizia mi sono dedicato alla stesura di una versione in common lisp.
Backtracking con pruning dell'albero semplice semplice.
Unica furbizia la rappresentazione dei dati e un po' di ottimizzazioni sparse.

Volevo fare un po' di paragoni con gli esempi presenti su
http://en.wikipedia.org/wiki/Algorithmics_of_sudoku
ma ho avuto qualche difficolta' a far funzionare il codice degli altri.

in particolare il codice di vincenzo mi riporta uno schema diverso a quello che gli do in pasto... forse devo usare una notazione diversa ?
esempio:

Codice:

# cat input4.txt
0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 0 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
0 0 0 0 4 0 0 0 9



# ./vincenzo input4.txt
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
| 3 |   |   |   | 8 |   | 5 |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   | 1 |   |   |   | 2 |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | 5 |   |   |
+---+---+---+---+---+---+---+---+---+
| 7 |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   | 4 |   |   |   |   |
+---+---+---+---+---+---+---+---+---+

repne: la maggio parte degli esempi postati in quella pagina non vengono risolti
esempio:

Codice:

*** Input ***

0 0 0 0 0 0 0 3 9
0 0 0 0 0 1 0 0 5
0 0 3 0 5 0 8 0 0
0 0 8 0 9 0 0 0 6
0 7 0 0 0 2 0 0 0
1 0 0 4 0 0 0 0 0
0 0 9 0 8 0 0 5 0
0 2 0 0 0 0 6 0 0
4 0 0 7 0 0 0 0 0

*** Soluzione parziale (60) ***

25678  14568  124567 268    2467   4678   1247   3      9
26789  4689   2467   23689  23467  1      247    2467   5
2679   1469   3      269    5      4679   8      12467  1247
235    345    8      135    9      357    123457 1247   6
3569   7      456    13568  136    2      13459  1489   1348
1      3569   256    4      367    35678  23579  2789   2378
367    136    9      1236   8      346    12347  5      12347
3578   2      157    1359   134    3459   6      14789  13478
4      13568  156    7      1236   3569   1239   1289   1238

Ally: non ho capito come formattare l'input al programma...

Vicious: non viene trovato il Modulo matrix... e' una qualche libreria disponibile ?

Sono sotto linux e non ho potuto provare la versione F# e quella Oracle. Vedo citata una versione C#, ma non trovo il codice

Se mi spiegate come far andare gli esempi provo a compilare una tabellina,intanto questi sono i miei risultati coi problemi indicati in quella pagina.
I tempi sono il tempo medio su mille esecuzioni

Codice:

processor       : 1
vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 Duo CPU     T7250  @ 2.00GHz
stepping        : 13
cpu MHz         : 2001.000
cache size      : 2048 KB
physical id     : 0
siblings        : 2
core id         : 1
cpu cores       : 2
apicid          : 1
initial apicid  : 1
fpu             : yes
fpu_exception   : yes
cpuid level     : 10
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm lahf_lm ida tpr_shadow vnmi flexpriority
bogomips        : 3990.00
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

Codice:

0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 0 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
0 0 0 0 4 0 0 0 9

Tempo : 18.53 ms

1 0 0 0 0 0 0 0 2 
0 9 0 4 0 0 0 5 0 
0 0 6 0 0 0 7 0 0 
0 5 0 9 0 3 0 0 0 
0 0 0 0 7 0 0 0 0 
0 0 0 8 5 0 0 4 0 
7 0 0 0 0 0 6 0 0 
0 3 0 0 0 9 0 8 0
0 0 2 0 0 0 0 0 1

Tempo: 25.55 ms

0 0 1 0 0 4 0 0 0
0 0 0 0 6 0 3 0 5
0 0 0 9 0 0 0 0 0
8 0 0 0 0 0 7 0 3
0 0 0 0 0 0 0 2 8
5 0 0 0 7 0 6 0 0
3 0 0 0 8 0 0 0 6
0 0 9 2 0 0 0 0 0
0 4 0 0 0 1 0 0 0

Tempo: 9.13 ms

9 0 0 1 0 4 0 0 2 
0 8 0 0 6 0 0 7 0 
0 0 0 0 0 0 0 0 0 
4 0 0 0 0 0 0 0 1 
0 7 0 0 0 0 0 3 0 
3 0 0 0 0 0 0 0 7 
0 0 0 0 0 0 0 0 0 
0 3 0 0 7 0 0 8 0 
1 0 0 2 0 9 0 0 4 

Tempo: 3.72 ms

0 0 1 0 0 4 0 0 0
0 0 0 0 6 0 3 0 5
0 0 0 9 0 0 0 0 0
8 0 0 0 0 0 7 0 3
0 0 0 0 0 0 0 2 8
5 0 0 0 7 0 6 0 0
3 0 0 0 8 0 0 0 6
0 0 9 2 0 0 0 0 0
0 4 0 0 0 1 0 0 0

Tempo: 9.04 ms

0 0 0 0 0 0 0 3 9
0 0 0 0 0 1 0 0 5
0 0 3 0 5 0 8 0 0
0 0 8 0 9 0 0 0 6
0 7 0 0 0 2 0 0 0
1 0 0 4 0 0 0 0 0
0 0 9 0 8 0 0 5 0
0 2 0 0 0 0 6 0 0
4 0 0 7 0 0 0 0 0

Tempo: 50.37 ms

0 2 0 4 0 3 7 0 0
0 0 0 0 0 0 0 3 2
0 0 0 0 0 0 0 0 4
0 4 0 2 0 0 0 7 0
8 0 0 0 5 0 0 0 0
0 0 0 0 0 1 0 0 0
5 0 0 0 0 0 9 0 0
0 3 0 9 0 0 0 0 7
0 0 1 0 0 8 6 0 0

Tempo: 67.96 ms

0 0 1 0 8 0 6 0 4 
0 3 7 6 0 0 0 0 0 
5 0 0 0 0 0 0 0 0 
0 0 0 0 0 5 0 0 0 
0 0 6 0 1 0 8 0 0 
0 0 0 4 0 0 0 0 0 
0 0 0 0 0 0 0 0 3 
0 0 0 0 0 7 5 2 0 
8 0 2 0 9 0 7 0 0

Tempo: 2.04 ms

E infine il codice :P

Codice:

(declaim (optimize (speed 3) (debug 0) (safety 0)))

(deftype choices-length () '(integer 0 9))
(deftype choice () '(integer 1 9))
(deftype cell-pos () '(mod 81))
(deftype choices () '(cons list choices-length))
(deftype cell () '(cons choices cell-pos))
(deftype row () '(integer 0 8))
(deftype col () '(integer 0 8))
(deftype bblock () '(integer 0 8))

;;; Position related code
(defun make-pos (row col)
  (+ (* row 9) col))

(defun row-of-orig (pos)
  (floor pos 9))

(defparameter *row-of-table*
  (make-array 81 :element-type 'row :initial-contents (loop for n below 81 collect (row-of-orig n))))

(defun row-of (pos)
  (declare (type cell-pos pos)
	   (type (simple-array row (81)) *row-of-table*))
  (the fixnum (aref *row-of-table* pos)))


(defun col-of-orig (pos)
  (mod pos 9))

(defparameter *col-of-table*
  (make-array 81 :element-type 'col :initial-contents (loop for n below 81 collect (col-of-orig n))))

(defun col-of (pos)
  (declare (type cell-pos pos)
	   (type (simple-array col (81)) *col-of-table*))
  (the fixnum (aref *col-of-table* pos)))


(defun block-of-orig (pos)
  (let ((brow (floor (row-of pos) 3))
	(bcol (floor (col-of pos) 3)))
    (+ (* 3 brow) bcol)))

(defparameter *block-of-table*
  (make-array 81 :element-type 'bblock :initial-contents (loop for n below 81 collect (block-of-orig n))))

(defun block-of (pos)
  (declare (type cell-pos pos)
	   (type (simple-array bblock (81)) *block-of-table*))
  (the fixnum (aref *block-of-table* pos)))


(defun same-row (pos1 pos2)
  (declare (type cell-pos pos1)
	   (type cell-pos pos2))
  (= (row-of pos1) (row-of pos2)))

(defun same-col (pos1 pos2)
  (= (col-of pos1) (col-of pos2)))

(defun same-block (pos1 pos2)
  (= (block-of pos1) (block-of pos2)))

(defun remove-first-choice (elem list)
  (declare (type choice elem)
	   (type choices list))
  (loop for x in (car list)
       when (/= x elem)
       sum 1 into n
       and
       collecting x into xs
       finally (return (cons xs n))))

(defun remove-first-cell (elem list)
  (declare (type cell elem)
	   (type list list))
  (loop for x in (car list)
     when (not (eql elem x))
     collect x))


(defun values-of (x)
;  (declare (type cell x)
;	   (optimize (speed 3) (debug 0) (safety 0)))
  (car x))

(defun position-of (x)
  (declare (type cell x))
  (cdr x))

(defun insert-number (board pos new-value)
  (declare (type cell-pos pos)
	   (type choice new-value))
  (loop for x in board
     for p  = (position-of x)
     for values  = (values-of x)
     for new-list = (cond ((eql p pos) (cons (list new-value) 1))
			  ((same-row p pos) (remove-first-choice new-value values))
			  ((same-col p pos) (remove-first-choice new-value values))
			  ((same-block p pos) (remove-first-choice new-value values))
			  (t values))
     collecting (cons new-list p)))


(defun empty-board ()
  (loop for x below 81 collect (cons (cons '(1 2 3 4 5 6 7 8 9) 9) x)))

(defun read-board (filename)
  (with-open-file (stream filename :direction :input)
    (let ((board (empty-board)))
      (loop for row from 0 below 9 do
	   (loop for col from 0 below 9 
	      for number fixnum = (read stream) 
	      when (> number 0) do
		(setf board (insert-number board (make-pos row col) number))))
      board)))

(defun n-of-values (x)
  (declare (type cell x))
  (cdr (car x)))

(defun pick-next (board)
  (loop for cell in (cdr board)
     with best = (first board)
     and best-length = (n-of-values (first board))
     and rest = ()
     if (< (n-of-values cell) best-length)
     do 
       (push best rest)
       (setf best cell)
       (setf best-length (n-of-values cell))
     else do (push cell rest)
     finally (return (list best rest))))

(defun rec-solve (count solution board)
  (if (eql 81 count)
      solution
      (destructuring-bind (best remaining) (pick-next board)
	(loop 
	   for value in (values-of (car best))
	   for position = (position-of best)  then (position-of best)
	   for sol = (rec-solve (1+ count) 
				(cons (list position value) solution)
				(insert-number remaining position value))
	   do
	     (when sol
		(return sol))))))
		     
(defun solve (board)
  (rec-solve 0 () board))

(defun print-solution (solution)
  (labels ((cmp (x y) (< (first x) (first y))))
    (let ((sorted (sort solution #'cmp)))
      (loop for cell in sorted 
	 do (if (= 0 (mod (1+ (first cell)) 9))
		(format t "~a~%"(second cell))
		(format t "~a " (second cell)))))))
  

(defun main (filename)
  (let* ((board (read-board filename))
	 (solution (solve board)))
    (print-solution solution)))

DanieleC88 · 26-12-2009, 00:24

Io proprio stasera ho incontrato questo...

http://scottkirkwood.blogspot.com/20...in-python.html

Questo si chiama "Obfuscated Python", vero cdimauro?

cdimauro · 26-12-2009, 00:34

Mai visto codice Python così brutto.

15-06-2009, 10:51	#83
rеpne scasb Senior Member Iscritto dal: May 2008 Messaggi: 533	■ Ultima modifica di rеpne scasb : 18-06-2012 alle 16:38.

07-12-2009, 17:20	#87
gugoXX Senior Member Iscritto dal: May 2004 Città: Londra (Torino) Messaggi: 3692	Ecco. Dato questo input Una soluzione SQL, sotto Oracle che permette le query ricorsive, e' questa Codice: with x( s, ind ) as ( select sud, instr( sud, ' ' ) from ( select '53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419 5 8 79' sud from dual ) union all select substr( s, 1, ind - 1 ) \|\| z \|\| substr( s, ind + 1 ) , instr( s, ' ', ind + 1 ) from x , ( select to_char( rownum ) z from dual connect by rownum <= 9 ) z where ind > 0 and not exists ( select null from ( select rownum lp from dual connect by rownum <= 9 ) where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 ) or z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 ) or z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3 + trunc( ( ind - 1 ) / 27 ) * 27 + lp + trunc( ( lp - 1 ) / 3 ) * 6 , 1 ) ) ) select s from x where ind = 0 Come si puo' vedere, la sanita' mentale tende e a zero molto velocemente. Il risultato eseguito: Ed eventualmente riprocessato http://technology.amis.nl/blog/6404/...uery-factoring __________________ Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. Ultima modifica di gugoXX : 07-12-2009 alle 18:12.

08-12-2009, 15:49	#94
gugoXX Senior Member Iscritto dal: May 2004 Città: Londra (Torino) Messaggi: 3692	SI', hai ragione. Non posso richiamare la With all'interno della With stessa sotto 10g. Mi sa che dovremo aspettare per il piano d'esecuzione allora. Immagino tante belle "Connect By Pump". __________________ Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test.

08-12-2009, 22:00	#95
^TiGeRShArK^ Senior Member Iscritto dal: Jul 2002 Città: Reggio Calabria -> London Messaggi: 12112	Spettacolo! Io averi preferito un calcio nei coglioni piuttosto che anche solo provare a scrivere qualcosa di simile in SQL. __________________

26-12-2009, 00:24	#99
DanieleC88 Senior Member Iscritto dal: Jun 2002 Città: Dublin Messaggi: 5989	Io proprio stasera ho incontrato questo... http://scottkirkwood.blogspot.com/20...in-python.html Questo si chiama "Obfuscated Python", vero cdimauro? __________________ C'ho certi cazzi Mafa' che manco tu che sei pratica li hai visti mai!

15-09-2009, 17:21	#84
Kralizek Senior Member Iscritto dal: Feb 2003 Città: Stockholm (SE) Messaggi: 1343	resuscito questo topic per linkare questo video quanto mai azzeccato! http://www.youtube.com/watch?v=Mp8Y2yjV4fU

15-09-2009, 18:38	#85
skeleton Member Iscritto dal: Jul 2009 Messaggi: 81	salve a tutti, è possibile risolvere questo sudoku in batch??? Non importa quanto tempo impiega, mi interesserebbe solo sapere il codice per farlo. Grazie in anticipo per il vostro sicuro aiuto.

21-09-2009, 13:47	#86
skeleton Member Iscritto dal: Jul 2009 Messaggi: 81	up

10-12-2009, 11:22	#96
flx2000 Bannato Iscritto dal: Nov 2002 Città: Roma Messaggi: 810	Mi aggiungo al coro di complimenti per rеpne scasb. Fa veramente piacere sentir parlare in italiano una persona tanto abile con gli algoritmi (e con l'offuscamento artistico del codice). Complimenti davvero, ho visto tardi questo topic per poter partecipare al contest, ma sono felice di esserci comunque approdato per averci trovato numerose menti brillanti.

26-12-2009, 00:34	#100
cdimauro Senior Member Iscritto dal: Jan 2002 Città: Germania Messaggi: 26110	Mai visto codice Python così brutto. __________________ Per iniziare a programmare c'è solo Python con questo o quest'altro (più avanzato) libro @LinkedIn Non parlo in alcun modo a nome dell'azienda per la quale lavoro Ho poco tempo per frequentare il forum; eventualmente, contattatemi in PVT o nel mio sito. Fanboys

Strumenti
Mostra una versione stampabile Invia questa pagina per email