[Vari] Contest 7: Il Lotto

[gugoXX]

1. Sia dato un file contentente un inseme di estrazioni del lotto.
Il formato del file e' il seguente:

Ruote 6
Valori 5
12/10/1999 Roma 1,4,2,10,12
12/10/1999 Torino 5,7,4,6,8
12/10/1999 Milano 3,7,5,4,7
12/10/1999 Napoli 66,9,54,55,4
12/10/1999 Venezia 33,9,45,4,55
12/10/1999 Bari 3,87,65,43,21

13/11/1999 Roma 1,6,4,7,2
13/11/1999 Torino 9,4,1,55,5
13/11/1999 Milano 3,34,33,36,37
13/11/1999 Napoli 4,47,45,44,48
13/11/1999 Venezia 5,9,55,4,58
13/11/1999 Bari 66,35,25,4,90

Dove il primo record enuncia il numero delle Ruote possibili (in questo esempio e' 6, ovvero 6 diverse citta')
Il secondo record enuncia quanti valori vengono estratti per ciascuna ruota (tipicamente nel lotto vero e' 5, ovvero 5 valori diversi estratti per ciascuna ruota)
Seguono una serie di estrazioni con questo formato
Data dell'estrazione - Ruota di estrazione - elenco dei valori estratti separati da virgola
E' ammessa l'esistenza di record completamente vuoti (tipicamente tra ogni estrazione) che saranno da ignorarsi
I 3 campi sono separati da uno spazio, e non sono presenti altri spazi nei 3 campi
Ogni estrazione verra' partecipanti tutte le ruote possibili, il cui numero e' enunciato nel primo record
I valori estratti per ciascuna ruota/estrazione saranno unici (estrazione senza reinserimento, come nel lotto vero)
I valori sono sempre nel range 1-90 estremi compresi (come il lotto vero)

2. Sia dato un insieme di valori target di ricerca

Find 4
1,4,3
2,4
1,7,5
55,4,9

Dove il primo record enuncia il numero di record successivi
Mentre ciascun record dei successivi e' una combinazione da ricercarsi in modo esaustivo tra le estrazioni precedentemente caricate.
Il numero di valori per ciascuna combinazione e' variabile, ma sara' sicuramente inferiore o uguale al numero di valori possibili di una estrazione.
2,4 significa che si conta di cercare l'ambo 2,4 all'interno delle estrazioni precedenti.

Il risultato per 2,4 sarebbe pertanto:
12/10/1999 Roma 1,4,2,10,12
13/11/1999 Roma 1,6,4,7,2
In quanto in entrambe le estrazioni sia il numero 2 che il numero 4 sono stati estratti.

Output desiderato:
Per ciascun insieme dei valori target di ricerca presente ALMENO UNA VOLTA nelle estrazioni del primo file, stampare
I valori target di ricerca stessi
E tutte le estrazioni che soddisfano tali valori target di ricerca.

L'output dell'esempio sarebbe pertanto:

-- 2,4 --
12/10/1999 Roma 1,4,2,10,12
13/11/1999 Roma 1,6,4,7,2
-- 55,4,9 --
12/10/1999 Napoli 66,9,54,55,4
13/11/1999 Torino 9,4,1,55,5
13/11/1999 Venezia 5,9,55,4,58

Nulla verrebbe quindi riportato per sia per i valori 1,4,3 che per i valori 1,7,5, in quanto non presenti in modo completo nemmeno una volta tra le estrazioni a disposizione.

Seguono 2 coppie di file di test.
Facile, Difficile
Provate anche solo prima con il test, ovvero le 12 estrazioni di esempio e le 4 combinazioni da ricercare gia' qui pronte.
http://www.usaupload.net/d/mhk196q7wok

[Vincenzo1968]

E il contest 6 che fine ha fatto? Me lo sono perso?

[gugoXX]

Originariamente inviato da Vincenzo1968

E il contest 6 che fine ha fatto? Me lo sono perso?

Nono, e' pronto in canna, un piccolo raffinamento e parte.
E' solo che per motivi storici ho pubblicato prima il 7 (il motivo storico e' che le soluzioni si chiamano rispettivamente Contest6.sln e Contest7.sln )

[wingman87]

Volevo fare una domanda, forse stupida: nel risolvere il contest tutto ciò che conta è la velocità del programma risolutivo?

[gugoXX]

Originariamente inviato da wingman87

Volevo fare una domanda, forse stupida: nel risolvere il contest tutto ciò che conta è la velocità del programma risolutivo?

Diciamo che conta il metodo, ovvero l'algoritmo.
Un buon algoritmo spesso si traduce in una migliore leggibilita' del codice e in una migliore performance.

Anche perche' se contasse solo la velocita' ci metteremmo tutti a farlo in assembly, impiegando grandi risorse per avere poco vantaggio (e soprattutto tanti svantaggi)

[VICIUS]

Primo tentativo con forza bruta. Riporto solo il codice della soluzione.

def benchmark(label)
  print "#{label}..."
  start_time = Time.now
  result = yield
  puts " completato. (#{(Time.now - start_time).to_s} secondi)"
  result
end

def load_data(file_name)
  estrazioni = Array.new
  File.open(file_name, 'r') do |f|
    f.gets;	f.gets # ignora le prime due righe
    while line = f.gets
      data, ruota, valori = line.chop.split
      estrazioni << { data: data, ruota: ruota, valori: valori.split(',').map { |x| x.to_i} }
    end
  end
  estrazioni
end

def load_find(file_name)
  ricerche = Array.new
  File.open(file_name, 'r') do |f|
    f.gets # ignora la prima riga
    while line = f.gets
      ricerche << line.chop.split(',').map { |x| x.to_i }
    end
  end
  ricerche
end

def contains(e, r)
  r.each do |v|
    return false if !e.include? v
  end
  true
end

def search(estrazioni, ricerche)
  ricerche.each do |r|
    puts "-- #{r.inspect} --"
    estrazioni.each do |e|
      puts "#{e[:data]} #{e[:ruota]} #{e[:valori].inspect}" if contains(e[:valori], r)
    end
  end
end

estrazioni = benchmark('Caricamento delle estrazioni') { load_data('LottoDataDifficile.txt') }
ricerche = benchmark('Caricamento delle ricerche') { load_find('LottoFindDifficile.txt') }
benchmark('Ricerca dei valori') { search(estrazioni, ricerche) }

Ovviamente è lento da far paura. Circa 190 secondi per la soluzione difficile.

[Vincenzo1968]

Originariamente inviato da VICIUS

Primo tentativo con forza bruta. Riporto solo il codice della soluzione.

Ciao Vicius,

puoi postare il codice per intero? (anzi, ti sarei grato se mi dessi qualche informazione sul funzionamento di Python. Dopo l'installazione per eseguire il tuo programma che devo fare? c'è qualche ide? riga di comando? Grazie )

x Gugo: come dobbiamo strutturare il programma? I dati vanno interamente caricati in memoria prima di prendere i tempi di esecuzione dell'algoritmo?

[gugoXX]

Originariamente inviato da Vincenzo1968

Ciao Vicius,

puoi postare il codice per intero? (anzi, ti sarei grato se mi dessi qualche informazione sul funzionamento di Python. Dopo l'installazione per eseguire il tuo programma che devo fare? c'è qualche ide? riga di comando? Grazie )

x Gugo: come dobbiamo strutturare il programma? I dati vanno interamente caricati in memoria prima di prendere i tempi di esecuzione dell'algoritmo?

Ciao Vincenzo.
Diciamo che stavolta facciamo tutto insieme, dato che tenere in memoria liste lunghe che magari non vengono effettivamente sfruttate puo' essere scomodo.
Per conto mio comunque separero' sempre la fase di input da quella di preparazione strutture dati e poi elaborazione.
Con la speranza che su tempi mediamente alti l'input/output non pesi piu' di tanto.

[Mesh89]

Purtroppo non ho tempo (ne voglia :P) di scrivere il codice, però un appunto che mi viene da fare (se ho capito bene il codice di vicius, non conosco il python) è che la tua ricerca è qualcosa di simile:

f = vettore find
r = vettore risultati

per ogni i in f
se i è contenuto in r, allora bene, altrimenti questa ruota è da scartare

le prestazioni (di una verifica ruota-find) sono quindi O(f*r)

penso che si possa trasformare in O(f+r) usando, per esempio, una bitmask sui 90 valori possibili (banalmente un array di 90 booleani), e una prima passata ad r per settare la bitmask, e una seconda a f per vedere se ogni valore è contenuto

[shinya]

Scusate eh, ma il codice di vicius era ruby, non python.
Non per fare il pedante, ma...

[VICIUS]

Originariamente inviato da Vincenzo1968

Ciao Vicius,

puoi postare il codice per intero? (anzi, ti sarei grato se mi dessi qualche informazione sul funzionamento di Python. Dopo l'installazione per eseguire il tuo programma che devo fare? c'è qualche ide? riga di comando? Grazie )

Installa Ruby 1.9 poi metti il codice in un file e da linea di comando basta dare ruby file.rb. I File txt con i dati devono essere nella stessa cartella del file rb da cui lanci il programma.

[cionci]

Gugo: è questo il risultato "semplice" ?

 --74,47,67
 --86,16
23/06/2007 Cagliari 86,58,64,72,16
19/05/2007 Torino 24,43,16,86,50
10/02/2007 Bari 21,16,7,86,52
07/10/2006 Venezia 16,86,23,73,78
07/01/2006 Genova 45,86,16,77,13
03/12/2005 Milano 55,17,86,68,16
21/06/2003 Firenze 16,56,25,86,43
12/04/2003 Roma 16,28,5,22,86
18/05/2002 Napoli 19,16,61,28,86
14/04/2001 Venezia 42,86,16,77,14
10/02/2001 Torino 68,90,16,86,10
29/07/2000 Genova 48,86,75,16,40
15/05/1999 Torino 86,62,26,16,4
 --89,57
17/09/2005 Palermo 89,14,27,17,57
09/07/2005 Genova 19,57,79,25,89
21/05/2005 Torino 89,78,44,1,57
26/02/2005 Firenze 20,56,57,89,67
29/05/2004 Bari 82,4,16,89,57
21/02/2004 Torino 89,32,60,73,57
07/06/2003 Milano 41,57,63,89,17
12/04/2003 Palermo 72,46,15,89,57
18/01/2003 Torino 34,77,89,57,74
09/11/2002 Napoli 57,89,10,31,11
29/06/2002 Firenze 71,46,89,83,57
04/05/2002 Bari 6,89,59,61,57
19/05/2001 Firenze 58,8,89,57,5
29/07/2000 Palermo 7,80,57,32,89
22/01/2000 Bari 57,18,89,44,15
 --71,29,58
 --73,16,30
23/08/2008 Venezia 30,53,73,16,66
 --59,47,60
 --46,67
06/09/2008 Napoli 6,39,67,78,46
05/04/2008 Roma 46,10,34,37,67
16/02/2008 Torino 46,38,51,80,67
31/03/2007 Torino 5,67,46,37,58
18/11/2006 Napoli 67,46,7,42,16
02/09/2006 Milano 41,30,6,67,46
10/06/2006 Palermo 67,39,4,11,46
03/07/2004 Cagliari 46,67,72,52,58
13/09/2003 Milano 55,46,67,45,51
13/09/2003 Napoli 46,67,18,90,32
24/05/2003 Palermo 30,67,66,39,46
15/06/2002 Torino 67,37,27,1,46
05/08/2000 Genova 89,30,67,46,5
11/03/2000 Milano 84,67,46,15,19
11/12/1999 Roma 46,89,31,82,67
15/05/1999 Venezia 52,44,46,13,67
 --75,41,72
 --80,6,22
 --15,67,80
19/06/2004 Genova 80,89,15,67,70
 --81,88
04/10/2008 Milano 32,22,88,75,81
21/04/2007 Venezia 32,43,88,46,81
28/10/2006 Napoli 19,81,88,55,27
12/06/2004 Napoli 81,88,48,8,13
17/05/2003 Bari 88,81,83,47,22
25/01/2003 Palermo 81,26,88,71,77
23/11/2002 Palermo 81,69,59,88,49
28/09/2002 Torino 30,78,18,88,81
29/06/2002 Napoli 81,2,32,88,44
20/10/2001 Cagliari 38,80,81,52,88
25/03/2000 Bari 81,15,52,88,2
11/03/2000 Cagliari 7,30,81,88,61
 --45,11,41
 --32,47
05/05/2007 Cagliari 24,47,1,38,32
14/04/2007 Torino 42,47,32,79,30
19/08/2006 Roma 47,52,36,24,32
22/04/2006 Cagliari 6,47,3,32,43
05/02/2005 Milano 32,84,47,25,21
17/07/2004 Genova 8,85,47,32,7
05/10/2002 Torino 47,77,1,32,84
08/12/2001 Firenze 32,47,49,8,38
18/08/2001 Roma 31,44,47,82,32
14/04/2001 Genova 32,5,21,47,58
16/12/2000 Milano 75,47,40,63,32
12/08/2000 Cagliari 47,20,30,32,31
13/05/2000 Genova 47,3,31,32,55
23/10/1999 Roma 29,32,24,86,47
23/10/1999 Venezia 47,32,41,16,69
18/09/1999 Milano 47,58,32,41,63
18/09/1999 Venezia 47,32,85,83,2
 --17,57,70
 --32,64,59
 --70,2
19/07/2008 Bari 2,88,70,50,5
14/06/2008 Torino 4,2,70,8,21
03/05/2008 Firenze 2,70,35,28,20
26/05/2007 Firenze 2,70,88,1,24
28/04/2007 Venezia 60,2,36,70,21
31/03/2007 Firenze 7,57,71,70,2
17/03/2007 Genova 12,70,42,58,2
21/08/2004 Roma 36,22,28,2,70
08/05/2004 Venezia 63,2,70,20,49
22/02/2003 Genova 50,36,54,2,70
23/02/2002 Palermo 53,70,23,13,2
09/09/2000 Genova 59,42,2,70,8
28/08/1999 Genova 46,2,21,70,51
22/05/1999 Roma 70,13,2,47,78
 --56,11,66
 --32,68,85
 --34,44,77
 --8,40,75

Se è corretta, la soluzione difficile la trovo in:

real 0m2.446s
user 0m2.304s
sys 0m0.112s

[VICIUS]

Originariamente inviato da cionci

Gugo: è questo il risultato "semplice" ?
[code] --74,47,67
--86,16
23/06/2007 Cagliari 86,58,64,72,16
19/05/2007 Torino 24,43,16,86,50[...]

L'output è identico alla mia versione quindi spero che sia quello corretto.

[Mesh89]

Penso ci sia un errore nell'output di esempio, esistono due Venezia che soddisfano 55,4,9

[cionci]

Originariamente inviato da VICIUS

L'output è identico alla mia versione quindi spero che sia quello corretto.

Ok

[gugoXX]

Originariamente inviato da Mesh89

Penso ci sia un errore nell'output di esempio, esistono due Venezia che soddisfano 55,4,9

Indubbiamente.
Ma possibile che neppure con 3 record in croce non riesca mai a fare il lavoro di un computer?

[cionci]

Originariamente inviato da gugoXX

Indubbiamente.
Ma possibile che neppure con 3 record in croce non riesca mai a fare il lavoro di un computer?

Mi sono reso conto solo ora di una cosa, perché sono stati inseriti 6 numeri per riga in quello difficile ?
Avevo fatto il conto a 5 e mi salta tutto l'algoritmo Era un ricerca O(1)

[gugoXX]

Originariamente inviato da cionci

Mi sono reso conto solo ora di una cosa, perché sono stati inseriti 6 numeri per riga in quello difficile ?
Avevo fatto il conto a 5 e mi salta tutto l'algoritmo Era un ricerca O(1)

I valori per riga sono un parametro di input.
Ma dai, non penso che se al posto di 5 diventano 6 salti proprio tutto...

[Mesh89]

cionci: non vorrei risultare pedante, ma:

Per ciascun insieme dei valori target di ricerca presente ALMENO UNA VOLTA nelle estrazioni del primo file, stampare
I valori target di ricerca stessi

:P

[cionci]

Si parlava di lotto e credevo che fossero <= 5.

Originariamente inviato da gugoXX

Ma dai, non penso che se al posto di 5 diventano 6 salti proprio tutto...

L'accesso alla lista di ruote non mi salta (uso un map con i double):

drawings[sortedNumbers[0] + sortedNumbers[1] * 100 + sortedNumbers[2] * 10000 + sortedNumbers[3] * 1000000 + sortedNumbers[4] * 100000000]

Però mi salta il calcolo delle disposizioni da inserire nel map, mi toccherebbe implementare un algoritmo per calcolare le combinazioni semplici