Posts written by stef72

No, non hai capito. Sino al numero 8 vanno bene. Dopo il numero 8 ci sono il 24, il 36, il 44, ecc..
Se il 24 non va bene, prende il 36 al su posto....

Forse è ininfluente, ma il percorso lo immaginavo diverso.
Nel senso che se prova il 24 e determina che non va bene, facendo un passo indietro per seguire la strada alternativa, dovrebbe l'asciare l'8 e provare il successivo al 24. invece nella tua sequenza Ha tolto anche l'8, per mettere il 7 e il 15.
Guardando l'immagine si riesce a seguire meglio (però potrei aver sbagliato io..Come è già successo! Quindi, magari domattina ricontrollo ancora una volta).

Si vede che 1 2 3 7 e 8 sono in verde, il 24 lo sta per scegliere.
Ora sceglie il 24. Ma si accorgerà immediatamente che è una mossa che chiude tutte possibilità di proseguire...
Perciò deve fare un passo indietro. Allora toglierei il 24 e metterei il 36.
E al posto della tua "01 02 03 07 15" io proverei "01 02 03 07 08 36". Giusto?

Poi, per la velocità ti darei un consiglio: vedo che hai implementato le list box per l'output. Ma quando deve elencare 106.000 settine, le list box rallentano notevolmente. Credo che per le prove prima della versione beta potresti usare un file di testo che visionerai facendoci doppioclick, se serve (facendoglielo lasciare aperto in scrittura fino al termine dell'esecuzione e chiudere una volta solo alla fine).
Credo che la differenza di tempo sia proprio dovuta al fatto che deve perdere tempo a comunicare ogni output che nel caso delle settine porta via un sacco di tempo. Per le novine avviene solo tre volte.

Ciao, notte

Ho chiesto perché mi sa che hai preso una strada diversa.
Per esserne certo dovrei vedere le prime lunghette che prova (1,2,3,7...; 1,2,3,7,8,24. ecc...)

Come mai impiega di più a fare le settine e le ottine piuttosto che le novine, quando le novine sono di più?

m C(90,m)
7 7.471.375.560 ----> 11'08"
8 77.515.521.435 ----> 03'56"
9 706.252.528.630 ----> 01'28"

Forse stai applicando un altro algoritmo

Daccordo, puoi usare 10 computers, ma il paragone facciamolo con dei punti fermi.
Io userei 1 solo thread per fare tutte le prove. Questo mi permette di fare un confronto equilibrato.
Anche l'algoritmo che stiamo studiando qui puoi dividerlo in quanti threads ti pare. E il tempo naturalmente si dimezza ogni volta che aggiungi due threads.

Ciao Krypta,
se stai incontrando difficoltà a farlo girare con 4 punti e invece con 3 funziona bene è probabile che abbia interpretato diversamente la mia descrizione e chissà, magari stai portando avanti una variante.
Perché se hai scritto il codice che funziona con 3, davvero non dovrebbe essere difficile farlo funzionare con altri punteggi. cambia solo la procedura che stabilisce quali e quante colonne deve confrontare.

Due domande riferirete al primo screenshot:
Il valore "Tests" è riferito ai test che prevede di fare oppure a quelli che ha compiuto sino a quel momento?
In 01min e 28sec ha terminato l'esecuzione di tutti i cicli e quindi si è fermato oppure sta ancora cercando?

Rispondo a Silop2005 (che ringrazio per la segnalazione)


ho dato uno sguardo al programma che hai citato e a giudicare dalle impressioni che hanno gli utenti di quel forum sembrerebbe un lavoro ben fatto.
ma mi pare che la funzione di ricerca delle lunghette, nonostante il nome del software, sia solo una funzione marginale. Mi sembra orientato più alla statistica di ritardi di ambi, terni e frequenze di formazioni
che appunto al fine della ricerca descritta in questo post.
Dicevo ho provato il programma e se chiedo di cercare una novina vergine per tre punti (come stiamo facendo noi) a stima del tempo necessari è di circa 3 giorni.
Il proposito di questo algoritmo è appunto cercare di ridurre questi tempi fino a dei limiti più normali (come avrai letto, nei primi test la ricerca è stata portata a termine in meno di 2 minuti.)
Posto qui di seguito le immagini del mio collaudo del programma di terze parti e se avessi sbagliato qualcosa comunicatemelo.

(clicca sulle miniature per ingrandire)

fig.1 Carica Archivio -------------------- fig.2 Parametri di ricerca (novine per 3 pts) --------------- fig.3 Finestra dei risultati di ricerca ------------------- fig.4 Elaborazione in corso
-------------------------- ---------------------------------------------- ---------------------------------------

Questa comunque era un parentesi e anche se fa piacere confrontarsi con gli altri, dobbiamo proseguire per la nostra strada per tentare di progredire.
.

.

.

.

.

Rispondo qui anche a Sventra Papere (che ho un leggero sospetto di chi possa essereci dietro a questo nickname)


Credo la stessa utilità che ne traggono gli utenti dell'altro forum tanto entusiasti del programma citato da Silop2005.
Oppure, guardando il problema da un'altra prospettiva ci si rende conto che questo problema in fondo è equiparabile in altri problemi in cui spesso qui dentro ci si imbatte.
Puoi rigirare la minestra, ma la sostanza è sempre quella...Qui comunque tempo fa avevamo accennato alla trasformazione formale di un problema in un altro problema apparentemente distinto, ma le cui soluzioni possono essere adattate quelle dell'uno con l'altro. Se il lavoro necessario per questa sorta di "traduzione" delle soluzioni avviene in tempo accettabile (polinomiale), allora i due problemi si possono considerare "riducibili" e quindi cercare di risolvere quello che si preferisce con l’intento di fornire invece una soluzione all'altro problema equivalente:
<discussione sulla riduzione polinomiale>

.

.

.

.


Infine a Giovanni A. (a.k.a. krypta) rispondo che ci devo pensare un attimo. Però il meccanismo è identico anche se cambi i punti cercati da tre a quattro.

Cambia il fatto che, lavorando col foglio excel, se vuoi cercare le novine vergini per 4 punti, invece che applicare i filtri a coppie per vedere dove capitano i 'terzi' 1 nelle colonne bianche,


Dovrai, invece, applicare i filtri a tre a tre sulle colonne verdi (per vedere in quali colonne bianche capita il quarto 1....visto che se capitano 4 punti saltiamo oltre.
Certamente sarà leggermente più lento, ma davvero in maniera quasi ininfluente. perché questo parametro incide in maniera quasi lineare (per ogni passo invece che fare C(9,2)=36 scansioni dei 2093 concorsi ne farai C(9,3)=84 )
Ciò che incide di più sulla velocità è la lunghezza delle lunghette (se da novine chiedi decine, undicine, ecc) e poi è importante anche il range dei concorsi esaminati (noi ne abbiamo preso un campione di 2093, ma si spera di poter fare esperimenti su altri intervalli anche maggiori)



Poi vorrei anticiparti una domanda
Quando il software sarà più in ordine (e a meno che non provi pure io a fare qualcosa, per cui me lo faccio da solo) vorrei darti un file con un migliaio circa di sestine (Il file si chiama "sistema90060306=1093.txt"), perché tu possa usarlo al posto delle 2093 estrazioni.
E come parametri dovresti vedere se trovi delle lunghette, non di nove, ma di lunghezza sei (cioè sestine) che non hanno mai fatto 3 punti.
- Se le trovi sai anche dirmi quali?
- Però mi interesserebbe di più se invece non ne trovi neanche una

Hai ancora ragione, i numeri elencati sono quelli che hai indicato tu, sono 45 in totale quelli selezionabili dopo la terza scelta. Il resto del ragionamento mi pare non cambi.
Non so perché mi sia confuso così. È molto difficile mantenere la concentrazione quando selezioni le colonne, cambi il colore di sfondo delle celle, applichi i filtri e poi li togli…
Alla fine non ti ricordi neanche quello che stavi facendo.
Per questo sarebbe comodo avere un programma sul quale: a) selezioni il file delle estrazioni, b) imposti la lunghezza di ricerca (novine) e c) scegli il punteggio per il quale ne cerchi una (o più di una) vergine. Poi per il resto delle funzionalità ci sarebbe da sbizzarrirsi.

.
.
.

Ho provato a fare delle considerazioni sulla complessità di questo algoritmo.

Ho considerato i passi descritti sopra fino a completare manualmente le fasi di scelta (in questo primo passaggio, come abbiamo visto, ci si ferma a 6 numeri e non si arriva alla novina).
Ho quindi preso il nostro come caso medio, e non so se ho fatto bene, ma il range di estrazioni è certamente casuale, quindi se non è la quantità (2093) che trae in inganno, mi risulta che:
- nello scegliere il primo numero l'algoritmo ha 90 possibilità (non c'è nessun numero da escludere né in verde né in arancione);
- Per il secondo numero la scelta deve escludere il numero scelto in precedenza + i numeri in arancione (ma ancora non ce ne sono), quindi ne sceglierà uno su 89;
- Per il terzo numero può scegliere tra 90 - i due in verde già scelti - quelli in arancione coinvolti dai primi due in verde e in totale avrà 68 possibili numeri in bianco tra cui scegliere;
e così via...Come riporta questa tabellina:


Perciò la mia valutazione, (anche se la definirei davvero sommaria), mi fornisce i seguenti valori indicativi:

questo nuovo algoritmo effettuerà 90 * 89 * 68 * 45 * 18 * 6 = 2.647.144.800 (2 miliardi e 600 milioni circa) di tentativi
Che non sono certo una bazzecola, ma vista la natura del problema credo che sia assolutamente ragionevole.

Se, come termine di paragone, consideriamo gli altri algoritmi esaminati nei giorni scorsi vediamo che:
- Verificare tutte le possibili novine dell'integrale effettua C(90;9) = 706.252.528.630 (706 miliardi e 200 milioni) di tentativi
- Similmente abbiamo anche visto che seppure al massimo dell'efficienza (sia per l’hardware moderno, sia dal punto di vista del codice), verificare moltiplicando tutte le sestine vergini con tutti i terni vergini, per poi scartare quelli che non sono novine e controllando i punteggi di quelli rimanenti
costringe a effettuare (892.126 * 82.334) = 73.452.302.084 (73 miliardi e 400 milioni) di tentativi

Quindi sembrerebbe (ancora il condizionale è d'obbligo) che:
- se a questo algoritmo diamo indice di velocità pari a 1,
- allora provare tutte le C(90;9) novine: 706.252.528.630 / 2.647.144.800 = 266,7978452 più lento
- provare, invece, a moltiplicare sestine verg. per terni verg: 73.452.302.084 / 2.647.144.800 = 27,74774621 è più lento

Perciò, in termini di tempo potrebbe voler dire che se l'algoritmo della moltiplicazione ha impiegato 12 ore, questo nuovo dovrebbe terminare in circa 25 minuti

Naturalmente un calcolo preciso della complessità terrebbe conto del fatto che tra i tentativi di ogni algoritmo ci sono sotto procedure differenti. Ovvero:
Il primo genera tutte le novine e le controlla una per una fino trovare tre punti (con costo computazionale lineare pari alla lunghezza delle novine)
Il secondo genera 10 volte meno novine, ma aggiunge il controllo su ciascuna di queste sulla presenza di numeri ripetuti (con costo computazionale lineare pari alla lunghezza delle novine)
Questo nuovo effettua un numero veramente ridotto di tentativi, ma per ciascuno di essi deve verificare la presenza di concorsi che totalizzano tre punti con l'ultimo numero aggiunto (si applicano i filtri Excel a due a due col nuovo numero introdotto assieme ai precedenti)
e questo è un po' più complicato da calcolare e non dipende dalla lunghezza delle novine, ma dalla quantità dei concorsi e il costo, nel caso peggiore è pari alle possibili coppie tra 9 numeri C(9,2)=36, ma il caso medio è molto inferiore.

Infine, però, penso che anche se alla fine i due algoritmi trasformati in programma impegnassero la macchina allo stesso modo e quindi se impiegassero lo stesso tempo per terminare, è anche vero che il funzionamento interno è completamente differente. Quindi arriverebbero alla prima soluzione in tempi diversi
Per cui, se si lanciassero due istanze contemporaneamente, una basata sul un algoritmo e l'altra su questo, e se esiste una novina vergine per il tre, siccome seguono un percorso di ricerca diverso, allora uno dei due ci arriverebbe prima dell'altro e la ricerca potrebbe considerarsi conclusa.

Quindi la curiosità di vedere realizzato un software che applichi questo algoritmo non è ancora soddisfatta.

Esatto! Mi rendo conto di aver sbagliato a mettere i colori (sto lavorando con un monitor da 15" che sembra un orologio da polso! Lo so è vergognoso)
Infatti la corretta esecuzione dell'algoritmo il 4 lo esclude contrassegnandolo in arancione quando applichi i filtri.
Da una parte però mi fa piacere che il discorso sia chiaro. Altrimenti non avresti individuato l'errore, almeno credo

Lasciami modificare i conteggi e cambiare le relative immagini al mio post precedente in modo che si possa rileggere. Sempre però col beneficio del dubbio, perchè sono un po' stanco e sta diventanto tedioso dover fotografare qualsiasi microoperazione che devo fare a mano.

Ora il post sopra è tutto corretto.

Non voglio partire dagli ambi.

Inizia così
1 2 3
, scegliendo il numero 1, poi siccome non ci sono celle in arancione, sceglie il numero 2, così anche per il 3 va avanti liscio,
poi il quarto numero (e i successivi) saranno una scelta (molto ridotta) tra i numeri in bianco (7 8 12 13 14 15 16 17 18 20 22 24 25 26 28 29 31 32 36 37 40 43 44 45 46 47 48 50 51 52 53 58 59 63 65 66 68 71 72 77 80 81 86 87 89) della seguente immagine:

(clicca sulla miniatura per ingrandire)

Se un software euristico, che genera a ruota tutte le possibili combinazioni, per arrivare alla prima combinazione che dopo il 3 ha il numero 7 (1 2 3 7 8 9 10 11 12) deve prima esaminare 98.499.836 novine (indice lessicografico di questa) le quali daranno tutte almeno 3 punti (dalla 1 2 3 4 5 6 7 8 9 alla 1 2 3 7 8 9 10 11 12) quindi non ci interessano.
Noi invece, questo lo vediamo prima di metterci a costruire le novine e di verificarle! Lo vediamo perché abbiamo davanti i numeri in arancione e sappiamo che fanno male. Non si toccano! Pucci, cacca! Come ci diceva la mamma!
Come quinto numero sceglierà il numero 8… (i numeri in memoria saranno 1 2 3 7 8)

Più significativo è forse il passo successivo:
L’algoritmo euristico di forza bruta, continua a costruire le novine e le esamina ancora tutte, come se avesse i paraocchi, da quella successiva con la sequenza già selezionata: 1 2 3 7 8 9 10 11 12 di indice =98.499.836 a quella che, nell'ordine lessicografico ha il 24 come sesto numero; Ovvero questa: 1 2 3 7 8 24 25 26 27 di indice=99.482.416). perciò ne costruisce e esamina…inutilmente… 99.482.416- 98.499.836= 982.580
mentre con questo nuovo algoritmo esse vengono saltate (sempre grazie ai numeri in arancio, che noi guardiamo e passiamo, passiamo oltre).

Per concludere, è interessante che dopo questa sequenza di prova: dopo questa sequenza di prova: 1 2 3 7 8, la situazione dei colori farebbe tentare come prossimo il 24, ma contrassegnando in arancio le colonne coinvolte da questo, non rimerrebbe nessun numero libero in bianco da poter sceglieree così non si arriverebbe a completare la novina (ci si bloccherebbe a sei numeri 1 2 3 7 8 24, senza possibilità di procedere).
Quindi si dovrà tornare indietro dell’ultima mossa (il 24) e ripetere la scelta del sesto numero (che nel nostro caso sarà il 36)… (clicca sulla miniature per ingrandire)

Potrei anche sbagliarmi. Aver omesso di considerare qualche lato del lavoro che il PC dovrà fare e che si traduce in un rallentamento, perciò, alla fine dovremmo aspettare ore e ore sia col primo sia col questo di algoritmo.
Ma sono ancora convinto di non sbagliare.
Penso anche che qualcuno che ha letto le dritte (non necessariamente un utente affezionato del Forum) abbia già messo qualcosa in pentola e magari ha già quella preziosa informazione che ci incoraggerebbe oppure ci farebbe demordere dall’intento di mettersi lì a buttare una giornata di lavoro per cercare spiegare a una fredda macchina cosa vogliono dire le figure descritte nei post sopra.

Edited by stef72 - 1/1/2023, 10:09

Io non so se userei la ricorsione. Sarebbe anche più elegante, ma se mi dovessi anche avventurare con la ricorsione mi perderei per strada. Penso invece che inizierei con un grande ciclo While che si arresta quando i numeri scelti sono 9 oppure quando non ci sono più alternative da provare. Con un indicatore che permetta di seguire il progresso dei calcoli.
Si i calcoli son tanti, ma da quello che ho visto provando a mano mi pare che si riducano tantissimo. proprio perché arrivato a certi abbinamenti di numeri salta per intero grandi rami dell'albero delle possibili novine.
Se osservi questa immagine (che ho già usato nel post precedente) si vede bene che quando inserisci il 59 come settimo numero rimane una sola scelta possibile, cioè quella aggiungere il 70 e il 73. Mentre un algoritmo euristico si metterebbe a provare tutte le coppie di numeri, compresi quelli in arancione (che noi sappiamo che originerebbero un terno) e sono tante. Se non sbaglio C(90-7 ; 2)=3403. Questo avviene solo in questo momento dell'esecuzione, ma questi 'tagli' avvengono ripetutamente mentre ci si avvicina alla fine della ricerca.
Però no, non ho fatto nessun codice. Mi servirebbe una giornata di quelle che non hai niente da fare.

Cosa ti preoccupa degli ambi che non sono mai usciti? Non vedo il problema.

E' vero, grazie! E' una svista anche se non altera il contenuto dei post successivi.
Ho corretto comprendendo nella somma anche l'ultima riga e ho approfittato per inserire nel nuovo foglio anche i filtri (le freccette nere verso il basso) già pronti per poter essere manovrati.

Ok, ora cerco anche di concludere la descrizione
così eventualmente si potrà passare a qualche prova e qualche osservazione per migliorare ulteriormente il modo di procedere.

Prendiamo come esempio questi primi numeri scelti da una fase dell’algoritmo:
2 31 48 49 50 58 59 ,
in questa immagine si vede come questi 7 numeri scelti impongano solo altri due numeri come possibili componenti per arrivare a completare la novina. Sono le uniche due colonne rimaste in bianco...
(clicca sulla miniatura per ingrandire) (che poi ho usato per questo esempio, i numeri di una delle 4 novine del prof Di Guida che quindi sappiamo già essere una soluzioni valida)
I numeri che il computer ha già scelto in questo ciclo e dovrà provare ad abbinare ad altri due finire di per comporre la novina, sono le sette colonne in verde.
In arancione invece sono contrassegnati tutti i numeri che ciascuna delle sette scelte precedenti ha reso non utilizzabili. La scelta di un solo numero applica il contrassegno (in arancione) di diverse colonne, direi anche una decina. Perciò in certi casi, in poche mosse ci si rende subito conto di non poter proseguire e si può saltare al passo successivo.

Un altro algoritmo invece sarebbe andato avanti alla cieca sino a completare la novina per poi effettuare la verifica e vedere poi che totalizza magari, che so…, 8 punti 😊

Col foglio Excel dell’allegato al primo post potete provare manualmente come ho fatto io a iniziare a inventare i primi numeri di una vostra novina qualsiasi e, avendo cura di segnare in arancione tutte quelle colonne che, dopo aver regolato i due filtri, presentano un 1 su sfondo bianco . Vi renderete conto immediatamente se state seguendo una strada sbagliata.



Una cosa importante che stavo per tralasciare è che ogni volta che si aggiunge un numero, dopo aver contrassegnato la scelta in verde, si devono applicare i filtri a tutte le possibili coppie del nuovo numero appena aggiunto, a uno a uno per fare coppia appunto, a turno, con gli altri già in verde.

Cioè, per esempio, se sto inserendo il quarto numero della novina,
diciamo che siamo arrivati a provare 2 31 48 e voglio aggiungere il 49
devo subito provare se questo genera tre punti, prima mettendo il filtro Excel sulla prima colonna in verde con la nuova colonna in verde del quarto numero, poi filtro la seconda colonna verde con la quarta, infine la terza sempre con la quarta. Ogni volta che applico i filtri a una coppia di colonne, osservo gli 1 che sono nelle colonne ancora in bianco e queste diverranno arancioni.

In sostanza, per ogni n-esimo numero che aggiungo, devo fare (n-1) confronti applicando i filtri due a due sulle colonne verdi


A intuito mi pare che la complessità sia enormemente inferiore a quella della costruzione di tutte possibili le novine con un altro algoritmo.
La parte di codice che credo mi impegnerebbe maggiormente è forse la gestione del backup dell’ultimo passo corretto, ovvero mantenere traccia del punto in cui siamo arrivati per poter poi ripristinare i passi effettuati quando ci si accorge che il candidato non va bene; E poter poi seguire la strada successiva. Sino a esaurire tutte le possibilità…tra quelle ammissibili.
Cioè, nel mio post precedente abbiamo visto come dopo aver scelto il 2 e il 31 non possa essere scelto il 4, allora si procederebbe provare un altro numero candidato come terza scelta (scegliendo tra quelli rimasti ancora in bianco che non sono cioè contrassegnati in arancione). Se anche questo non può andare bene si passa a un altro numero più avanti e poi un altro ancora, e così sino al limite dei 90 numeri. Dopodiché avremmo stabilito che il 2 e il 31 non vanno bene con nessun numero. Quindi si dovrà fare un passo indietro e mutare uno dei primi due numeri scelti. Mantenendo cioè il 2 e procedendo col candidato successivo al 31. Per poi riiniziare la prova del terzo candidato, non più assieme a 2 e 31, ma per esempio assieme al 2 e al 32.

Mi pare che non resti che provare

Ma no, io la soluzione a 128 ce l'avevo già quando ho postato il 127 (-4)
Ma che ve ne fate?

I miei programmi in fase di sviluppo stanno raggiungendo un grado di sofisticazione mai visto prima sulla faccia della Terra
Se dovesse succedermi qualcosa dentro un tunnel (come a LadyD nel 1997 che era partita dall'aeroporto qui vicino), non crediate alla versione dell’incidente. Indagate piuttosto sulle ricerche della Multinazionale farmaceutica CryonicsPharmaSoft che sta portando avanti uno studio sui possibili abbinamenti delle molecole di un nuovo farmaco, le quali di norma non possono essere presenti contemporaneamente nello stesso medicinale. Vogliono produrre un nuovo siero che non avrà effetti collaterali. E poi chiedete di vedere se dentro il rotolo di carta igienica del mio bagno c’è ancora la pennetta USB o se qualcuno l’ha portata via.
O forse potrei fare la fine di Kennendy, centrato da un sicario mentre entro alle Poste per pagare la bolletta ella luce.
Forse conviene che distrugga tutto prima che entri nelle mani sbagliate!

Io sono arrivato qui:
Allego il 23,09,08,14=127 con -4 scoperte

Sto cercando di capire cosa intendi fare. Mi sembra sia un metodo totalmente differente da quelli provati sino a ora.
Ricapitolando quanto hai detto, prendiamo il 90,9,5,9=40290 e lo utilizziamo come se fosse un 90,9,6,16=40290
Ma non capisco perchè entrano in ballo le 16ine
Se vuoi però posso darti il 90,9,6,16 in modo, almeno, che possa utilizzare direttamente questo senza dover ricorrere a succedanei:

allego 90,09,06,16=35.478