Sudoku

se in uno schema, che ho riempito a tentativo, sia le righe
(orizzontali) che tutti e nove i riquadri 3x3 rispettano le regole,
posso essere sicuro che anche le colonne, e quindi l'intero schema
rispettino le regole?

A me (alla mia intelligenza naturale) sembra banale dare un
controesempio.
Riempi secondo le regole le prime tre righe (e i primi tre riquadri).
Poi copia le tre righe nelle successive e nelle ultime.
Debbo continuare?

--
Elio Fabri

danilob

2020-11-28 15:01:27 UTC

Post by Elio Fabri

E' vero, non avevo spiegato bene il problema. Io parto da una schema con
già qualche numero inserito, proprio come si trova nei giornaletti,
quindi è impossibile fare quello che dici tu. E a questo punto mi rimane
il dubbio sulla necessità di fare un test sulle colonne. Proverò a fare
senza, e a vedere quello che succede. Il problema è che facilmente i
tempi di calcolo diventano biblici, con milioni di combinazioni
possibili da analizzare.

--
E' la somma che fa la differenza.

Yoda

2020-11-28 17:15:08 UTC

Post by danilob
Il problema è che facilmente i
tempi di calcolo diventano biblici, con milioni di combinazioni
possibili da analizzare.

Prova questo vecchio schema d'un eclissato amico di ISM di piu'
d'una decina d'anni fa, secondo me a manina ci riesci.. a Pasqua!
Invece con un solutore velocissimo (compilato in c++) ci s'impiega
da me ben 5,5 minuti d'orologio ciao
(ma la macchina mia e' un po' vecchiotta assai.. bogomips 7200.00 x 4)

. . . | . 6 . | . 8 .
. 2 . | . . . | . . .
. . 1 | . . . | . . .
------|-------|------
. 7 . | . . . | 1 . 2
5 . . | . 3 . | . . .
. . . | . . . | 4 . .
------|-------|------
. . 4 | 2 . 1 | . . .
3 . . | 7 . . | 6 . .
. . . | . . . | . 5 .

--
Yoda

danilob

2020-11-28 17:40:29 UTC

Post by danilob
Il problema è che facilmente i
tempi di calcolo diventano biblici, con milioni di combinazioni
possibili da analizzare.

Prova questo vecchio schema d'un eclissato amico di ISM di piu'
d'una decina d'anni fa, secondo me a manina ci riesci.. a Pasqua!
Invece con un solutore velocissimo (compilato in c++) ci s'impiega
da me ben 5,5 minuti d'orologio ciao
(ma la macchina mia e' un po' vecchiotta assai.. bogomips 7200.00 x 4)
. . . | . 6 . | . 8 .
. 2 . | . . . | . . .
. . 1 | . . . | . . .
------|-------|------
. 7 . | . . . | 1 . 2
5 . . | . 3 . | . . .
. . . | . . . | 4 . .
------|-------|------
. . 4 | 2 . 1 | . . .
3 . . | 7 . . | 6 . .
. . . | . . . | . 5 .

Messaggio salvato. Devo ancora finire il codice, però. Uso Python, molto
più lento di C++, ma sufficiente per il 99.99% di quello che devo fare.

--
E' la somma che fa la differenza.

Yoda

2020-12-02 07:08:16 UTC

Post by danilob

Post by danilob
Il problema è che facilmente i
tempi di calcolo diventano biblici, con milioni di combinazioni
possibili da analizzare.

Prova questo vecchio schema d'un eclissato amico di ISM di piu'
d'una decina d'anni fa, secondo me a manina ci riesci.. a Pasqua!
Invece con un solutore velocissimo (compilato in c++) ci s'impiega
da me ben 5,5 minuti d'orologio ciao
(ma la macchina mia e' un po' vecchiotta assai.. bogomips 7200.00 x 4)
. . . | . 6 . | . 8 .
. 2 . | . . . | . . .
. . 1 | . . . | . . .
------|-------|------
. 7 . | . . . | 1 . 2
5 . . | . 3 . | . . .
. . . | . . . | 4 . .
------|-------|------
. . 4 | 2 . 1 | . . .
3 . . | 7 . . | 6 . .
. . . | . . . | . 5 .

Messaggio salvato. Devo ancora finire il codice, però. Uso Python, molto
più lento di C++, ma sufficiente per il 99.99% di quello che devo fare.

Aggiungo oggi una cosa curiosa. Ho nuovamente compilato il sudoku.c,
questa volta aggiungendo opzioni mie rispetto al comando di ieri:
$: gcc -o sudoku sudoku.c, indicato dall'autore stesso.
Ebbene, il tempo e' sceso a 1 min e 46 sec - incredibile eh ciao!

Postilla. Apropos di tempi, fattoriale di 30 mila, con funzione
ricorsiva (la piu' veloce), qui da me ci mette 8 secondi e 828/1000,
son 124.895 cifre ariciao.. e vorrei vedere il tuo Python ;^)

--
Yoda

Conte Floreski

2020-12-03 09:47:14 UTC

Post by danilob
Il problema è che facilmente i
tempi di calcolo diventano biblici, con milioni di combinazioni
possibili da analizzare.

Prova questo vecchio schema d'un eclissato amico di ISM di piu'
d'una decina d'anni fa, secondo me a manina ci riesci.. a Pasqua!
Invece con un solutore velocissimo (compilato in c++) ci s'impiega
da me ben 5,5 minuti d'orologio ciao
(ma la macchina mia e' un po' vecchiotta assai.. bogomips 7200.00 x 4)
. . . | . 6 . | . 8 .
. 2 . | . . . | . . .
. . 1 | . . . | . . .
------|-------|------
. 7 . | . . . | 1 . 2
5 . . | . 3 . | . . .
. . . | . . . | 4 . .
------|-------|------
. . 4 | 2 . 1 | . . .
3 . . | 7 . . | 6 . .
. . . | . . . | . 5 .

Messaggio salvato. Devo ancora finire il codice, però. Uso Python, molto
più lento di C++, ma sufficiente per il 99.99% di quello che devo fare.

Aggiungo oggi una cosa curiosa. Ho nuovamente compilato il sudoku.c,
$: gcc -o sudoku sudoku.c, indicato dall'autore stesso.
Ebbene, il tempo e' sceso a 1 min e 46 sec - incredibile eh ciao!
Postilla. Apropos di tempi, fattoriale di 30 mila, con funzione
ricorsiva (la piu' veloce), qui da me ci mette 8 secondi e 828/1000,
son 124.895 cifre ariciao.. e vorrei vedere il tuo Python ;^)
--
Yoda

Conte Floreski

2020-12-03 09:49:22 UTC

Post by danilob
Il problema è che facilmente i
tempi di calcolo diventano biblici, con milioni di combinazioni
possibili da analizzare.

Prova questo vecchio schema d'un eclissato amico di ISM di piu'
d'una decina d'anni fa, secondo me a manina ci riesci.. a Pasqua!
Invece con un solutore velocissimo (compilato in c++) ci s'impiega
da me ben 5,5 minuti d'orologio ciao
(ma la macchina mia e' un po' vecchiotta assai.. bogomips 7200.00 x 4)
. . . | . 6 . | . 8 .
. 2 . | . . . | . . .
. . 1 | . . . | . . .
------|-------|------
. 7 . | . . . | 1 . 2
5 . . | . 3 . | . . .
. . . | . . . | 4 . .
------|-------|------
. . 4 | 2 . 1 | . . .
3 . . | 7 . . | 6 . .
. . . | . . . | . 5 .

Messaggio salvato. Devo ancora finire il codice, però. Uso Python, molto
più lento di C++, ma sufficiente per il 99.99% di quello che devo fare.

1/4 di secondo (il codice non e` mio):

https://tio.run/##bY5BDoIwEEX3c4pZtmCChZ2RsxgixU5SZ8ikLjx9LdGIqH/XP837b76nINzlPPoJdeCLP80qo4myC2QPgCU0YZTa4REDPZslVxqxRxOojmKbpn0f1Keb8hes/***@6XFzbH46D/3puxxZgVuKEZsvs9iXW5vwA

Yoda

2020-12-03 10:03:45 UTC

Post by Yoda
Aggiungo oggi una cosa curiosa. Ho nuovamente compilato il sudoku.c,
$: gcc -o sudoku sudoku.c, indicato dall'autore stesso.
Ebbene, il tempo e' sceso a 1 min e 46 sec - incredibile eh ciao!
Postilla. Apropos di tempi, fattoriale di 30 mila, con funzione
ricorsiva (la piu' veloce), qui da me ci mette 8 secondi e 828/1000,
son 124.895 cifre ariciao.. e vorrei vedere il tuo Python ;^)

Cavoli! avranno un grappolo di pc?

Post by Conte Floreski
https://tio.run/##bY5BDoIwEEX3c4pZtmCChZ2RsxgixU5SZ8ikLjx9LdGIqH/XP837b7
6nINzlPPoJdeCLP80qo4myC2QPgCU0YZTa4REDPZslVxqxRxOojmKbpn0f1Keb8hes/LZYfZa

Per cosa? per il sudoku o per il fattoriale ciao?

--
Yoda

Conte Floreski

2020-12-03 10:52:27 UTC

Cavoli! avranno un grappolo di pc?

Post by Conte Floreski
https://tio.run/##bY5BDoIwEEX3c4pZtmCChZ2RsxgixU5SZ8ikLjx9LdGIqH/XP837b7
6nINzlPPoJdeCLP80qo4myC2QPgCU0YZTa4REDPZslVxqxRxOojmKbpn0f1Keb8hes/LZYfZa

Per cosa? per il sudoku o per il fattoriale ciao?
--
Yoda

Per il fattoriale (dove trovo il codice del sudoku?).

E la maggior parte del tempo si perde nello scrivere il risultato; senza la stampa a schermo:

$ time python fattoriale.py

real 0m 0.09s
user 0m 0.09s
sys 0m 0.00s

$ cat /proc/cpuinfo | grep mips
bogomips : 6801.63
bogomips : 6801.63
bogomips : 6801.63
bogomips : 6801.63

$ cat fattoriale.py

def range_prod(lo,hi):
if lo+1 < hi:
mid = (hi+lo)//2
return range_prod(lo,mid) * range_prod(mid+1,hi)
if lo == hi:
return lo
return lo*hi

def treefactorial(n):
if n < 2:
return 1
return range_prod(1,n)

f=treefactorial(30000)

Yoda

2020-12-03 15:39:35 UTC

Post by Conte Floreski
https://tio.run/##bY5BDoIwEEX3c4pZtmCChZ2RsxgixU5SZ8ikLjx9LdGIqH/XP837b7
6nINzlPPoJdeCLP80qo4myC2QPgCU0YZTa4REDPZslVxqxRxOojmKbpn0f1Keb8hes/LZYfZa

Per cosa? per il sudoku o per il fattoriale ciao?

Per il fattoriale (dove trovo il codice del sudoku?).

Non so.. e' roba di piu' di 10 nni fa, comunque eccolo:

=-=-=-=-=-=-=-=- cut here -=-=-=-=-=-=-=-=-=
#include <stdio.h>

int s[81], m[82], k, i;

main() {
for (i=0;i<81;++i) {
scanf("%d",&s[i]);
m[i]=s[i];
}
for(;;) {
while (m[k]) k++;
if (k>=81) {
for (i=0;i<81;++i) {
printf("%d ",s[i]);
if (i%9>7) printf("\n");
}
return;
}
if (++s[k]>9) {
s[k--]=0;
for(;m[k];)
if (k--==0) return;
} else {
for (i=0;i<81;++i) {
if (i==k || s[i]==0) continue;
if (i%9==k%9 || i/9==k/9 ||
(i/3)%3==(k/3)%3 && i/3/9==k/3/9)
if (s[i]==s[k]) break;
}
if (i>=81)
k++;
}
}
}
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Post by Conte Floreski
E la maggior parte del tempo si perde nello scrivere il risultato;
$ time python fattoriale.py
real 0m 0.09s
user 0m 0.09s
sys 0m 0.00s

Anche da me pero' dieci volte di meno: circa .008s. Comunque lo
saprai tu cosa fa, io non lo so di certo, non ci capisco nulla di
python. Pero' non lo credo proprio che possa calcolarlo, prova a
dirgli di stampartelo su un file invece che a video, da me su file
o video l'output e' vuoto, dunque gli 8 millesimi di secondo sono
per aprire e chiudere il file.

Post by Conte Floreski
$ cat /proc/cpuinfo | grep mips
bogomips : 6801.63
bogomips : 6801.63
bogomips : 6801.63
bogomips : 6801.63

Be' siamo li':
bogomips : 7200.00
bogomips : 7200.00
bogomips : 7200.00
bogomips : 7200.00

ho un'intel i3, ma adesso credo che le amd siano meglio.

Post by Conte Floreski
$ cat fattoriale.py
mid = (hi+lo)//2
return range_prod(lo,mid) * range_prod(mid+1,hi)
return lo
return lo*hi
return 1
return range_prod(1,n)
f=treefactorial(30000)

Bah, secondo me manca qualche segmento di codice e cosi' com'e' non
fa nessuna cosa del tutto.. va be' ciao e fammi sapere

--
Yoda

Conte Floreski

2020-12-03 17:01:01 UTC

Post by Yoda
Bah, secondo me manca qualche segmento di codice e cosi' com'e' non
fa nessuna cosa del tutto.. va be' ciao e fammi sapere

Provo a calcolare 100000!%100019 (=81430):

https://www.wolframalpha.com/input/?i=100000%21%25100019

modifico il programma fattoriale.py:

print (treefactorial(100000) % 100019 )

time python fattoriale.py

81430

real 0m 0.34s
user 0m 0.33s
sys 0m 0.00s

Sembra funzionare bene (il codice non e` mio e non so cosa fa di preciso).

Yoda

2020-12-03 22:12:16 UTC

Post by Yoda
Bah, secondo me manca qualche segmento di codice e cosi' com'e' non
fa nessuna cosa del tutto.. va be' ciao e fammi sapere

https://www.wolframalpha.com/input/?i=100000%21%25100019

Si', interessante.

Post by Conte Floreski
print (treefactorial(100000) % 100019 )
time python fattoriale.py
81430
real 0m 0.34s
user 0m 0.33s
sys 0m 0.00s
Sembra funzionare bene (il codice non e` mio e non so cosa fa di preciso).

Si', funziona proprio benissimo, mi guardero' un po' questo python
che avevo finora sempre sottovalutato.
Il numero, di cui fare il !, vorrei darglielo in input da tastiera,
invece di doverglielo scrivere nel sorgente.

Comunque l'ho dato senza il "% 100019", lo scrive tutto su file. Con
python2 (altri precedenti non ne ho) ho sostituito la riga cosi':

f=treefactorial(30000) -> print treefactorial(100000)

la prende benissimo e ci mette:
real 0m2,765s
user 0m2,756s
sys 0m0,009s

Con python3 invece marca errore, devo metterla cosi':
print (treefactorial(100000))

e ci mette solo qualche millesimo di secondo in meno (2,676), ma
sai.. entra in gioco la cache, non sono attendibili i confronti
precisi, si devono considerare solo come ordine di grandezza, ci
sono troppe oscillazioni casuali di volta in volta ripetendolo.

Le righe sono ovviamente identiche. Ho anche controllato quello
di 30000 ed e' perfettamente uguale al mio di bc ciao
(chissa' il sudoku col python.. magari si trova pure in rete)

Postilla. Poi controllo con top, ma mi sa che l'enorme differenza
dei tempi, tra python e bc, facilmente dipende dal fatto che python
mi sa che usa tutt'e quattro le cpu (bc una sola).
Guarda con 30000 stampato su file ariciao
real 0m0,210s
user 0m0,205s
sys 0m0,006s

--
Yoda

Karma Explorer

2020-12-05 02:30:04 UTC

Post by danilob
Data la carenza di quella naturale, sto ricorrendo
all'intelligenza artificiale per risolvere i sudoku. Mi è venuto
il seguente dubbio : se in uno schema, che ho riempito a
tentativo, sia le righe (orizzontali) che tutti e nove i riquadri
3x3 rispettano le regole, posso essere sicuro che anche le
colonne, e quindi l'intero schema rispettino le regole?
Grazie.

Prolog!!!

https://swish.swi-prolog.org/p/sudoku_2.pl

Nella finestra in basso a destra inserisci:

problem(1, Rows), sudoku(Rows).

e poi premi CTRL+ENTER per eseguire. Questo risolve il problema 1

Allo stesso modo puoi inserire:

problem(2, Rows), sudoku(Rows).

Premi CTRL+ENTER.

Puoi inserire altri schemi nella finestra di sinistra e provare a
risolverli.

Oppure puoi generare tutti i possibili sudoku a partire da un certo
schema. Nella finestra in basso a destra inserisci:

problem(3, Rows),
sudoku(Rows),
maplist(label, Rows),
maplist(portray_clause, Rows).

e poi, di nuovo, premi CTRL+ENTER per eseguire.

Dourlinski

2020-12-06 17:12:16 UTC

Post by Karma Explorer
Prolog!!!
https://swish.swi-prolog.org/p/sudoku_2.pl

Ma sbaglio o non riesce a risolvere il sudoku

Post by Yoda
. . . | . 6 . | . 8 .
. 2 . | . . . | . . .
. . 1 | . . . | . . .
------|-------|------
. 7 . | . . . | 1 . 2
5 . . | . 3 . | . . .
. . . | . . . | 4 . .
------|-------|------
. . 4 | 2 . 1 | . . .
3 . . | 7 . . | 6 . .
. . . | . . . | . 5 .

piazzando solo un (corretto) 5 in 6^ riga 9^ colonna?
Comunque un programma Visual Prolog (orrendamente scritto, men che
meno ottimizzato) risolve -- su una macchina media -- questo sudoku in
15 secondi e dopo altri 20 secondi stabilisce che quella data e'
l'unica soluzione. Ciao

Yoda

2020-12-06 20:48:27 UTC

Post by Karma Explorer
Prolog!!!
https://swish.swi-prolog.org/p/sudoku_2.pl

Ma sbaglio o non riesce a risolvere il sudoku

Mi sembrava, ma non me ne intendo molto eh, impossibile battere il C
in velocita' [*], invece quel mostro di python m'ha fatto restare di
stucco con un tempo di 215 millesimi di secondo per il 30!, mentre
invece bc ci impiega ben quasi 9 secondi.

Anche questo tempo che dici del prolog per il sudoku, di 35 secondi
totali, mentre da me col c++ ci vogliono 55 e passa secondi. Pero',
dando la griglia col 5 in 6.9 che dici, impiega solo 37,40 sec ciao

---------
[*] Il C e' quasi 1 a 1 con l'assembly, che pero' quasi nessuno piu'
conosce e ancor meno usa. Pensavo che, per il fattoriale di 30 che
ho detto, python usasse due o piu' cpu, invece no: ho controllato
con top e ne usa una sola, anche se al 100% boh.. deve avere dei
moduli magici!

--
Yoda

Karma Explorer

2020-12-06 23:17:13 UTC

Post by Yoda
Mi sembrava, ma non me ne intendo molto eh, impossibile battere il C
in velocita' [*], invece quel mostro di python m'ha fatto restare di
stucco

Considera che Python... è scritto in C!

Con un algoritmo di backtracking (quindi con una strategia simile a
quella di Prolog), in go per risolvere quello schema ci si mettono 2s/3s
a seconda della CPU:

https://pastebin.com/kQr7qfkD

Pure go è scritto in C... dal tizio che ha scritto il C (Brian Kernighan).

Yoda

2020-12-07 00:10:09 UTC

Post by Yoda
Mi sembrava, ma non me ne intendo molto eh, impossibile battere il C
in velocita' [*], invece quel mostro di python m'ha fatto restare di
stucco

Considera che Python... è scritto in C!
Con un algoritmo di backtracking (quindi con una strategia simile a
quella di Prolog), in go per risolvere quello schema ci si mettono 2s/3s

Pensa che al tempo dei tempi per testare le cpu una rivista
consigliava di fare il fattoriale con "derive" (per DOS, Linux
era ancora in mente Dei-Torvalds). Con grande enfasi dicevano del
ridottissimo tempo del 486DX.

Post by Karma Explorer
https://pastebin.com/kQr7qfkD
Pure go è scritto in C... dal tizio che ha scritto il C (Brian Kernighan).

OK, pero' son capitato nel sito:
<https://onlinesudoku.it/sudoku-risolutore/>

dove m'ha risolto /istantaneamente/ la griglia difficile di cui
parliamo. "Istantaneamente" vuol dire meno di 2 centesimi di
secondo, che e' il refresh rate dell'occhio umano.

Per questo motivo, e vista anche la troppo grande differenza per
il 30! tra bc e python, penso che dipenda dal sorgente (algoritmo)
e specialmente dalle librerie in uso, piu' che dal linguaggio.

Anche la compilazione ha la sua parte, da me il vecchio sudoku.c
ha ridotto drasticamente i tempi quando l'ho compilato indicando
le librerie piu' la direttiva -O3 ciao

--
Yoda

Karma Explorer

2020-12-07 09:49:15 UTC

dove m'ha risolto/istantaneamente/ la griglia difficile di cui
parliamo. "Istantaneamente" vuol dire meno di 2 centesimi di
secondo, che e' il refresh rate dell'occhio umano.
Per questo motivo, e vista anche la troppo grande differenza per
il 30! tra bc e python, penso che dipenda dal sorgente (algoritmo)
e specialmente dalle librerie in uso, piu' che dal linguaggio.

Sicuramente. Per il fattoriale direi che dipende più dalle librerie che
dall'algoritmo (anche se trasformandolo da ricorsivo a iterativo
migliori abbastanza le prestazioni). Per il sudoku direi che l'algoritmo
è la parte determinante. Sicuramente col risolutore online che hai
trovato tu l'euristica sarà più raffinata di quella dei programmini che
ho postato io.

In ogni caso quel programmino prolog (che non ho fatto io, è un esempio
standard di swi-prolog) lanciato via command line su un mio server dà la
risposta del problema 5 in 0.332s, che non è male.

statistics(runtime,[Start|_]),
problem(5, Rows), sudoku(Rows), maplist(label, Rows),
maplist(portray_clause, Rows),
statistics(runtime,[Stop|_]),
Runtime is Stop - Start,
!.

Yoda

2020-12-07 01:15:05 UTC

Post by Yoda
---------
[*] Il C e' quasi 1 a 1 con l'assembly, che pero' quasi nessuno piu'
conosce e ancor meno usa. Pensavo che, per il fattoriale di 30 che
ho detto, python usasse due o piu' cpu, invece no: ho controllato
con top e ne usa una sola, anche se al 100% boh.. deve avere dei
moduli magici!

Ecco ad esempio vedo, adesso che sto aggiustando un film, che
l'ottimo ffmpeg usa tutt'e quattro le cpu (e al 100%!) per passare
al formato mov (h264, per il quale occorre fare calcoli astronomici).

--
Yoda

Conte Floreski

2020-12-10 09:36:56 UTC

Post by Yoda
Mi sembrava, ma non me ne intendo molto eh, impossibile battere il C
in velocita', invece quel mostro di python m'ha fatto restare di
stucco con un tempo di 215 millesimi di secondo per il 30!, mentre
invece bc ci impiega ben quasi 9 secondi.

Sei sicuro che bc non sia un linguaggio interpretato con sintassi pseudo C, e non C puro? credo anche che conti l`algoritmo che sminuzza i fattori prima di moltiplicarli (tu hai capito come funziona? io non l`ho analizzato).

Ho fatto una controprova per vendicare il C/C++, riscrivendo il suddetto algoritmo e usando l`estensione per interi con precisione arbitraria (gmp):

https://tio.run/##***@Vtgw7FvGpukVBeNj3UCJUhvV0P5EllrbD7fbW3ciZNQoWhC0b/RAWQPa1AUh/fB9YZxqDYqKtrkMStbxUuQyXZIOE/JDwBpeIeZyl0Ppi640PzhbBnqsoYK4wx2XSXYsHi2qMaMSIaUjwjqB7WoPrHd5ahkKsrmTTUANVfVgDgC5nDke6bbDgtxDmfZCzZUyIxVSHqMwIEJVwko6PuHmK9hgwzwViScgDqmnKMBjUtWyFFhHFWxt/***@hsSeiKzvQ1P4tF1WnZvBfy8qaiTGfiw/***@481@z8

per il fattoriale di un milione, e` esattamente 10 volte piu` rapido nel calcolo (1.37 secondi contro 13.7 della controparte in python).

Conte Floreski

2020-12-10 11:12:50 UTC

L`algoritmo raggruppa le moltiplicazioni in modo da ritardare, per quanto possibile, le operazioni con numeri enormi; ho riscritto il codice usando le iterazioni al posto della ricorrenza (per semplicita` funziona solo con un numero di fattori 2^x) :

https://tio.run/##***@6rKlvTcYYXhWLpKdH1txdhuv9dmIipd5LiB4w@oRCE5NRsCOjleMMj7WA6BlCgi1kFGvM2Wmx/***@I@Hnlr7Ag

Conte Floreski

2020-12-10 13:37:08 UTC

...

https://tio.run/##TZDxSsMwEMb/***@dHpsdoyN3mINqJzxvdIGfNhzxpjFAE5ZhOXUqaHWD6AbNcCK@***@yghTOhCWTavm1oiyEUKGzy5kpqpQE13@@61Z5Ty8loDnC36TEioBDN1CIzLkVyG2WpSxJVGkrabOC/yQ4iUQeG9uapSPgTIyT7mlD04T2Pw/36zGbrCSdmZtyLoxI3Y0BhABV5hXcQ5G/***@3z/***@zCYoyb/EsfWlX7uG7n/7vWbw

(collegamento corretto)

Conte Floreski

2020-12-10 13:35:00 UTC

Sei sicuro che bc non sia un linguaggio interpretato con sintassi pseudo C, e non C puro? credo anche che conti l`algoritmo che sminuzza i fattori prima di moltiplicarli (tu hai capito come funziona? io non l`ho analizzato).
...
per il fattoriale di un milione, e` esattamente 10 volte piu` rapido nel calcolo (1.37 secondi contro 13.7 della controparte in python).

meno di un secondo con la versione iterativa (calcola 2^20 ! % 1048583):

https://tio.run/##TZDxSsMwEMb/***@dHpsdoyN3mINqJzxvdIGfNhzxpjFAE5ZhOXUqaHWD6AbNcCK@***@yghTOhCWTavm1oiyEUKGzy5kpqpQE13@@61Z5Ty8loDnC36TEioBDN1CIzLkVyG2WpSxJVGkrabOC/yQ4iUQeG9uapSPgTIyT7mlD04T2Pw/36zGbrCSdmZtyLoxI3Y0BhABV5hXcQ5G/***@3z/***@zCYoyb/EsfWlX7uG7n/7vWbw

Yoda

2020-12-10 13:41:34 UTC

Sei sicuro che bc non sia un linguaggio interpretato con sintassi
pseudo C, e non C puro?

In realta' bc non ha il fattoriale come funzione interna. Pero' di
quello ricorsivo ne da' la funzione nella manpagina, eccola:
------------------
/* fattoriale recursivo da man bc */
define fr(x) {
if (x<=1) return (1);
return (x * fr(x-1));
}
-------------------------

In rete l'avevo gia' trovato un po' diverso:
----------------------
/* fattoriale recursivo rete */
define frr(x) {
if (x>1) {
return (x * frr(x-1));
}
return (1);
}
---------

Io avevo fatto invece questo diretto:
---------------------
/* fattoriale */
define f(n) {
a=1;
for (j=1; j<=n; j++) {
a=a*j;
}
return (a);
}
-------------

Dei tre il piu' veloce risulta quello di bc.

Post by Conte Floreski
credo anche che conti l`algoritmo che
sminuzza i fattori prima di moltiplicarli (tu hai capito come
funziona? io non l`ho analizzato).

Ottima idea! questa di spezzare il prodotto, mi sa che e' proprio
decisiva per la velocita'.. qualcosa come:

-------------------
/* fattoriale monco recursivo bai mi: mf(x,y) */
define mf(x,y) {
if (x<=y) return (1);
return (x * mf(x-1,y));
}
--------------

ed allora fai ad es.: fr(100) = fr(90) * mf(100,90)

Post by Conte Floreski
Ho fatto una controprova per vendicare il C/C++, riscrivendo il
suddetto algoritmo e usando l`estensione per interi con precisione

Estensione che non ho mai fatto e purtroppo ormai non ho tempo per
guardarmela (se e' complicata). Potresti postare il sorgente?

Post by Conte Floreski
https://tio.run/##ZVLbboMwDH1uvsJjL9DSUfoK9Ee2qsoCBUshQUmYqk39-snip-
per il fattoriale di un milione, e` esattamente 10 volte piu`
rapido nel calcolo (1.37 secondi contro 13.7 della controparte in
python).

Cavoli son proprio dei tempi impensabili! perche' il fattoriale d'un
milione mi sa che comincia ad avere l'etichetta dei grandi numeri.

Comunque guarda un esempio di cosa succede con l'idea tua del
"divide et impera":

$: time "echo fr(20000) * mf(30000,20000) | bc -l > /dev/null
real 5.134
user 5.122
sys 0.013

$: time "echo fr(30000) | bc -l > /dev/null
real 8.829
user 8.759
sys 0.072

Ed e' chiaro che si puo' spezzettare ancor di piu' ciao

Postilla. L'ho spezzato in tre ed e' gia' sceso a 3.915 :-)

--
Yoda

Conte Floreski

2020-12-10 18:12:23 UTC

Post by Yoda
Estensione che non ho mai fatto e purtroppo ormai non ho tempo per
guardarmela (se e' complicata). Potresti postare il sorgente?

Prova una compilazione a vuoto con il seguente comando:

$ g++ -lgmp -lgmpxx

se "ld" si lamenta che non riesce a trovarli, devi montare i pacchetti gmp e gmp-dev della tua distribuzione (i sorgenti si trovano qui: https://gmplib.org/).

Ho provato a scrivere il programma per sfruttare piu` di un processore alla volta:

https://tio.run/##***@bPsUliwkDp7Coi4P6IgtZamHskn6ldGpc9uriAdNNE9oev6/2mkrnFq2UfT9DI9WhbqBE2wXfCP3CLlir3cfH3f4a6kKN9i9ktRsAYGgCaIEG4qESvpW3IPfCQ0L126aCORwZiwYSi2k1PC9LESzGoySv5kRo97mVSnQdJB44mOYdfqFN/lQVjAHMnBetFkC7gxNeKNUogo80AMYtavISu22bsA176q3emoOOaYcfSS2CIBHWFyjYINSVkRxnc3ftfFVWSsvN/ai/***@AzOkyF3ZK4aEvxvO1NQdRburJ8uD3lWYDmRBabpnEWR2GDFMcUszUk@3Z/***@R9XEmrRHkmuu75eEExH9y9U/kWNmwmlONZ0hOlGs32BdEZRVBdChTjQ8/fBhgoTqvBr6pY/***@fR69vwsEbyAp2Yn3fLx@@5E6JtusXanxa09ovdtY1Rrtv

circa 11 secondi* per calcolare (2^24)! % 16777259 (=12526689 chi controlla se e` giusto?) con 2 processori impiegati.

* bisogna infatti dividere lo "user time" per il numero di processori

Conte Floreski

2020-12-10 18:26:25 UTC

... (collegamento sbagliato)

https://tio.run/##XVJbbtswEPwWT7FIUECPuLGMNkYisRdxBYOlZJkAX6CoJqjhq1ddkUoiVx/kcnZmuLsit3bTcz5N90JzObYd1MIM3nVM/SCfWK/s29vX8xoafCvMLWSUnQEgQntQTGhI54i5nj8APzMHOca/***@fNBFi3aYPfadP/***@eIbPqj9Hb7qJRsxBPxsVZCrqtRB2TlSiKjCQJO4iGikJsixLpcZyKLhySkOT1LGSXKuRekK6oetwhjonkP1/1bhk8c4probCG5Iq27iDaBqFtU80zvpKbskqUx56jhUMenRfIAZWxEXwzLy/cjB7qepkoBndgneHdMBgnYByYFz/***@5I0guH2B8mm/3@@@PwfpzCSB6jo/Og3bilzJNE27b3/***@mDYyvN64T5uTsZ1W9h8

Dourliski

2020-12-10 22:23:29 UTC

Post by Conte Floreski
circa 11 secondi* per calcolare (2^24)! % 16777259 (=12526689 chi controlla se e` giusto?)

Esatto. Ciao

Conte Floreski

2020-12-14 13:26:41 UTC

Post by Dourliski

Post by Conte Floreski
circa 11 secondi* per calcolare (2^24)! % 16777259 (=12526689 chi controlla se e` giusto?)

Esatto. Ciao

Sotto al minuto arrivo a calcolare (2^26)! % 67108879, che dovrebbe fare 32640434; puoi confermare?

Giskano

2020-12-14 16:41:47 UTC

Post by Conte Floreski
Sotto al minuto arrivo a calcolare (2^26)! % 67108879, che
dovrebbe fare 32640434; puoi confermare?

1:30 - 1:35

Hint: th. di Wilson. Per verificare che (p-n)! = x (mod p), basta
vedere se (n-1)!*x*(-1)^n = 1 (mod p). Quasi istantaneo per n piccolo
come in questi casi. Ciao

Karma Explorer

2020-12-06 22:37:22 UTC

Post by Karma Explorer
Prolog!!!
https://swish.swi-prolog.org/p/sudoku_2.pl

Ma sbaglio o non riesce a risolvere il sudoku

piazzando solo un (corretto) 5 in 6^ riga 9^ colonna?

Sì.

L'ho aggiunto (5).

Per risolverlo però non bastano le semplici regole di base e va fatta la
"ricerca completa", quindi lo devi lanciare con:

problem(5, Rows), sudoku(Rows), maplist(label, Rows),
maplist(portray_clause, Rows).

Ci mette 0.366 secondi.

Per comodità:

problem(5, [[_,_,_, _,6,_, _,8,_],
[_,2,_, _,_,_, _,_,_],
[_,_,1, _,_,_, _,_,_],

[_,7,_, _,_,_, 1,_,2],
[5,_,_, _,3,_, _,_,_],
[_,_,_, _,_,_, 4,_,_],

[_,_,4, 2,_,1, _,_,_],
[3,_,_, 7,_,_, 6,_,_],
[_,_,_, _,_,_, _,5,_]]).

Karma Explorer

2020-12-06 22:44:10 UTC

Post by Karma Explorer
Prolog!!!
https://swish.swi-prolog.org/p/sudoku_2.pl

Ma sbaglio o non riesce a risolvere il sudoku

   . . . | . 6 . | . 8 .
   . 2 . | . . . | . . .
   . . 1 | . . . | . . .
   ------|-------|------
   . 7 . | . . . | 1 . 2
   5 . . | . 3 . | . . .
   . . . | . . . | 4 . .
   ------|-------|------
   . . 4 | 2 . 1 | . . .
   3 . . | 7 . . | 6 . .
   . . . | . . . | . 5 .

piazzando solo un (corretto) 5 in 6^ riga 9^ colonna

Lo risolve correttamente col 5 in R6C9, senza 5 e se togli il 2
nell'ultima colonna ti genera tutti i possibili schemi corretti.

Per queste cose prolog è magico.

Dourlinski

2020-12-06 23:32:05 UTC

Post by Karma Explorer
Per risolverlo però non bastano le semplici regole di base e va fatta la
problem(5, Rows), sudoku(Rows), maplist(label, Rows),
maplist(portray_clause, Rows).

Ah, ecco, questo e' il vero solutore. Sapendo a malapena che il sudoku
e' un particolare quadrato latino, ignoravo che ci fossero due livelli
di regole. Le regole di base sono per quei puzzle per cui esiste un
percorso deterministico?

Post by Karma Explorer
Per queste cose prolog è magico.

Assolutamente si'. Ciao

Karma Explorer

2020-12-07 10:51:35 UTC

Post by Karma Explorer
Per risolverlo però non bastano le semplici regole di base e va fatta la
problem(5, Rows), sudoku(Rows), maplist(label, Rows),
maplist(portray_clause, Rows).

Vado a intuito perché non conosco quei predicati di swi-prolog e sono
almeno vent'anni che non uso prolog in generale.

A naso nella prima versione (quella con due soli predicati) si ferma a
"una passata".

Nella seconda va in backtracking su tutti i possibili "percorsi".

Yoda

2020-12-07 00:27:42 UTC

Post by Karma Explorer
problem(5, [[_,_,_, _,6,_, _,8,_],
[_,2,_, _,_,_, _,_,_],
[_,_,1, _,_,_, _,_,_],
[_,7,_, _,_,_, 1,_,2],
[5,_,_, _,3,_, _,_,_],
[_,_,_, _,_,_, 4,_,_],
[_,_,4, 2,_,1, _,_,_],
[3,_,_, 7,_,_, 6,_,_],
[_,_,_, _,_,_, _,5,_]]).

Ah ecco dove sbagliavo forse anche per il sorgente di python che ho
preso in rete e che non mi riesce di far andare! ognuno ha il suo
modo di scrivere la griglia.
Se io volessi farlo col prolog, dovrei installare prolog? penso di
si' perche' il comando prolog qui da me non esiste, ma te lo chiedo
perche' ad esempio per python non c'e' bisogno, perche' c'e' un
minimo installato gia' di default.

D'altra parte per installare il prolog completo qui da me (Debian)
mi installerebbe anche necessariamente altri 41 pacchetti e in
questo caso non me la sento proprio ciao

Postilla. Ma si puo' sapere per qual buon motivo non usano tutti la
griglia come semplice text ascii puro, con l'a capo fissato a 9 e
senza spazi o altri fronzoli e con lo 0 per numero assente?

--
Yoda

Karma Explorer

2020-12-07 10:25:50 UTC

Post by Yoda
Ah ecco dove sbagliavo forse anche per il sorgente di python che ho
preso in rete e che non mi riesce di far andare! ognuno ha il suo
modo di scrivere la griglia.
Se io volessi farlo col prolog, dovrei installare prolog? penso di
si' perche' il comando prolog qui da me non esiste, ma te lo chiedo
perche' ad esempio per python non c'e' bisogno, perche' c'e' un
minimo installato gia' di default.

Sui repo di Ubuntu (e di altri linux) c'è SWI-PROLOG che è lo stesso
usato dal playground online. Via command line, ovviamente, non avrai le
routine di grafica. Se dal sorgente togli "use_rendering(sudoku)."
funziona esattamente come la versione online.

Carichi il programma con:

prolog -s sorgente.pl

Poi dall'interfaccia testuale inserisci i predicati (quelli che
inserisci nella finestrella in basso a destra).

Per esempio:

problem(5, Rows), sudoku(Rows), maplist(label, Rows),
maplist(portray_clause, Rows), !.

Il punto esclamativo alla fine blocca il backtracking dopo il primo
risultato.

Sono almeno vent'anni che non uso più Prolog ma una volta mi ci
divertivo. Un esercizio classico era il programmino per calcolare le
derivate simboliche ... dove in pratica scrivi le regole di derivazione
pari pari! Tipo questo, che con swi prolog funziona perfettamente (a
parte un warning):

https://github.com/wjur/sym-diff-prolog/blob/master/sym-diff.pl

Una volta c'erano ambienti molto user friendly come Turbo Prolog,
Arity32 Prolog e tanta altra roba. C'era addirittura un Visual Prolog,
con tanto di compilatore (e questo vedo che c'è ancora: l'hanno reso
gratuito per uso personale, una volta era solo a pagamento).

Dourlinski

2020-12-07 11:34:49 UTC

Post by Karma Explorer
Sono almeno vent'anni che non uso più Prolog ma una volta mi ci
divertivo. Un esercizio classico era il programmino per calcolare le
derivate simboliche ... dove in pratica scrivi le regole di derivazione
pari pari!

E PC prove di Tony Dodd, il mitico dimostratore di teoremi del 1987?
Sugli 8086 dell'epoca era praticamente un giocattolo. Guasi Guasi lo
vorrei rivedere all'opera con la bodenza di calcolo di 30 anni dopo.
Ciao

Conte Floreski

2020-12-05 08:11:55 UTC

Post by danilob
Data la carenza di quella naturale, sto ricorrendo
all'intelligenza artificiale per risolvere i sudoku. Mi č venuto
il seguente dubbio : se in uno schema, che ho riempito a
tentativo, sia le righe (orizzontali) che tutti e nove i riquadri
3x3 rispettano le regole, posso essere sicuro che anche le
colonne, e quindi l'intero schema rispettino le regole?

Ho modificato il programma "sudoku.c" (allegato da Yoda) in modo da omettere il controllo delle colonne:

codice originale:
if (i%9==k%9 || i/9==k/9 || (i/3)%3==(k/3)%3 && i/3/9==k/3/9)

codice modificato
if ( i/9==k/9 || (i/3)%3==(k/3)%3 && i/3/9==k/3/9)

questo lo schema da risolvere (La settimana enigmistica 4627):

500 001 400
098 003 000
000 690 007

040 006 809
000 000 000
309 400 070

700 034 000
000 100 260
004 900 001

ecco il risultato (evidentemente errato)

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

alla domanda che hai posto, direi quindi no.

Continua a leggere su narkive:

Discussioni interessanti ma non correlate

Letture consigliate per la rinormalizzazione (non solo in QFT)

iniziato 2010-11-14 03:27:40 UTC

Qual è il modo più efficiente per distruggere l'universo?

iniziato 2010-11-14 21:29:35 UTC

iniziato 2010-11-14 22:54:56 UTC

Giove può essere acceso?