[Vari] Contest 7: Il Lotto

[Vincenzo1968]

Prima di andare a nanna ho preso i tempi con i file grossi indicati da repne. Mi sa che sarà dura batterla:

2.687 secondi contro i 125.765 secondi della versione di Mesh.

[VICIUS]

Non riesco a prendere sonno così mi sono messo a fare qualche modifica. La nuova versione è circa il 39% più veloce.

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

def compress(values)
  c = 0
  values.each do |x|
    c |= 1 << x
  end
  c
end

def load_data(file_name)
  data = Array.new
  File.open(file_name, 'r') do |file|
    file.gets; file.gets # ignora le prime due righe
    while line = file.gets
      date, wheel, values = line.chop.split
      values = values.split(',').map { |x| x.to_i }
      data << { date: date, wheel: wheel, values: values, c: compress(values) }
    end
  end
  data
end

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

def search(data, find)
  find.each do |r|
    puts "-- #{r[:values].inspect} --"
    data.each do |e|
      puts "#{e[:date]} #{e[:wheel]} #{e[:values].inspect}" if (e[:c] & r[:c]) == r[:c]
    end
  end
end

data = benchmark('Caricamento delle estrazioni') { load_data('LottoDataSemplice.txt') }
find = benchmark('Caricamento delle ricerche') { load_find('LottoFindSemplice.txt') }
benchmark('Ricerca dei valori') { search(data, find) }

Molto semplicemente ho sostituito il ciclo che cercava se i valori erano contenuti nelle estrazioni con un confronto tra due integer.

[^TiGeRShArK^]

Originariamente inviato da Vincenzo1968

Prima di andare a nanna ho preso i tempi con i file grossi indicati da repne. Mi sa che sarà dura batterla:

2.687 secondi contro i 125.765 secondi della versione di Mesh.

io sto ancora cercando un'operazione commutativa che dato un insieme di numeri restituisca un risultato univoco..che immagino sia la cosa + efficiente da fare..
..però ho potuto dedicarci solo un pò di tempo stasera prima di uscire e non ho trovato niente che faccia al caso mio..
ah..
ovviamente il mio primo algoritmo da 8 secondi sotto macchina virtuale non faceva altro che creare un'hashmap usando come chiave l'estratto e inserendo la lista di ruote come valore e facendo le intersezioni tra i vari insiemi ottenuti..
Ma ovviamente è un ordine di grandezza + lento di quello che sto cercando di tirare fuori...
(anche se c'è da dire che in 25-30 minuti avevo risolto in quel modo il difficile di gugoxx in 11 secondi dato che c'erano un pò di ridondanze )

[rеpne scasb]

■

[k0nt3]

@rеpne scasb
scusa la domanda ma.. il tuo algoritmo funziona se il numero di valori per ogni estrazione è diverso da 6?

[rеpne scasb]

■

[Mesh89]

Originariamente inviato da rеpne scasb

Brutto segno. I nuovi due file sono circa 100 volte piu' pesanti, cio' indica che la versione di mesh ha una complessita' rispetto al tempo poco meno che lineare (probabilmente lineare), la complessita' del mio algoritmo e' decisamente piu' bassa si muove probabilmente con l'inverso del quadrato. Per fare un esempio, se utilizzassimo due nuovi file ancora 100 volte piu' pesanti, la mia versione impiegherebbe una 30 di secondi, quella di mesh, probabilmente, oltre 10.000.

Si, la mia soluzione dovrebbe essere a occhio lineare in f*r
Cmq sono ancora allibito dai tempi della tua soluzione, sembra una magia, che complessità ha?

[Vincenzo1968]

Classifica aggiornata:



Ho escluso per il momento k0nt3. Aspettiamo che aggiusti l'output.

Magix, per quel problema con Eclipse che ti avevo segnalato, sai dirmi niente?

[Vincenzo1968]

Originariamente inviato da VICIUS

Non riesco a prendere sonno così mi sono messo a fare qualche modifica. La nuova versione è circa il 39% più veloce.
...
Molto semplicemente ho sostituito il ciclo che cercava se i valori erano contenuti nelle estrazioni con un confronto tra due integer.

Vicius ehm...

so che ti sto scassando i cabasisi ma mi da errore. Puoi azzizzarmelo per la versione 1.8.7?

Questo è il codice(non mi cambiare i percorsi dei file):

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

def compress(values)
  c = 0
  values.each do |x|
    c |= 1 << x
  end
  c
end

def load_data(file_name)
  data = Array.new
  File.open(file_name, 'r') do |file|
    file.gets; file.gets # ignora le prime due righe
    while line = file.gets
      date, wheel, values = line.chop.split
      values = values.split(',').map { |x| x.to_i }
      data << { date: date, wheel: wheel, values: values, c: compress(values) }
    end
  end
  data
end

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

def search(data, find)
  find.each do |r|
    puts "-- #{r[:values].inspect} --"
    data.each do |e|
      puts "#{e[:date]} #{e[:wheel]} #{e[:values].inspect}" if (e[:c] & r[:c]) == r[:c]
    end
  end
end

#data = benchmark('Caricamento delle estrazioni') { load_data('C:\Scaricamenti\Temp\Gugo\Contest 07 - Il Lotto\LottoPiccolo\LOTTO.D1') }
#find = benchmark('Caricamento delle ricerche') { load_find('C:\Scaricamenti\Temp\Gugo\Contest 07 - Il Lotto\LottoPiccolo\LOTTO.D2') }

data = benchmark('Caricamento delle estrazioni') { load_data('C:\Scaricamenti\Temp\Gugo\Contest 07 - Il Lotto\LottoGrosso\LOTTO.D1') }
find = benchmark('Caricamento delle ricerche') { load_find('C:\Scaricamenti\Temp\Gugo\Contest 07 - Il Lotto\LottoGrosso\LOTTO.D2') }

benchmark('Ricerca dei valori') { search(data, find) }

[rеpne scasb]

■

[Mesh89]

Originariamente inviato da rеpne scasb

La complessita' dovrebbe essere 1*r, ossia non dipende da Find, o meglio dipende pochissimo da f. Ad esempio, nei nuovi due file se invece di aumentare per 10 sia le estrazioni totali che Find, avessi aumentato di 100 volte solo find, il tuo algoritmo avrebbe fatto ugualmente 125 secondi, il mio sarebbe rimasto fermo a 0.2 secondi.

Un altra osservazione: il mio algoritmo e' praticamente indipendente (o meglio leggermente dipendente), da "valori", ossia dai numero degli estratti che nel nostro caso e' 6. Se i valori fossero stati 7,8,9, e il numero dei valori da testare 3,4,5,6,7 non ci sarebbero state praticamente differenze sui tempi misurati*.

* Non e' propriamente cosi', ma nel nostro caso, operando con piccole quantita' di dati, e praticamente vero.

Wow... Mi sembra abbastanza incredibile che non dipenda dal numero di find, a contest finito sarebbe carina una spiegazioncina
Ho buttato giù di un po' i tempi, anche se non dovrei arrivare nemmeno vicino a repne

#include <iostream>
#include <bitset>
#include <string>
#include <vector>
#include <ctime>

using namespace std;


struct Ruota {
	bitset<96> bitmask;
	string* data,* luogo;
	char* numeri;
};
vector<Ruota> ruote;
vector<int> indexed[91];
int lens[91];


int main() {
	FILE* fin = fopen("fin.txt", "r");
	FILE* rin = fopen("rin.txt", "r");
	FILE* out = fopen("out.out", "w");
	int r, v, f, daCercare[9], index=0;
	char s[100];
	clock_t start = clock();

	fscanf(rin, "%s %d\n", s, &r);
	fscanf(rin, "%s %d\n", s, &v);
	fscanf(fin, "%s %d\n", s, &f);

	//Lettura ruote
	ruote.reserve(100010);
	lens[0] = 2000000000;
	while (!feof(rin)) {
		Ruota ruota; int n;
		ruota.numeri = new char[v];
		
		fscanf(rin, "%s", s);
		ruota.data = new string(s);
		fscanf(rin, "%s", s);
		ruota.luogo = new string(s);
		
		for (int i = 0; i < v-1; i++) {
			fscanf(rin, "%d,", &n);
			ruota.bitmask[n] = 1;
			ruota.numeri[i] = (char)n;
			
			indexed[n].push_back(index);
		} fscanf(rin, "%d\n", &n);
		ruota.bitmask[n] = 1;
		ruota.numeri[v-1] = (char)n;
		
		indexed[n].push_back(index);
		
		ruote.push_back(ruota);
		index++;
	}
	for (int i = 1; i <= 90; i++)
	   lens[i] = indexed[i].size();
	   
	cout << "Lettura input: " << (clock()-start)/1000.0 << " secondi" << endl;
	start = clock();
	
	//Risoluzione
	for (int i = 0; i < f; i++) {
		int k = 1, luckyNumber = 0;
		char c;
	
		//Lettura find
		fscanf(fin, "%d", daCercare);
		while (true) {
			fscanf(fin, "%c", &c);
			
			if (c == ',') {
				fscanf(fin, "%d", daCercare+k);
				if (lens[luckyNumber] > lens[daCercare[k]])
				    luckyNumber = daCercare[k];
				k++;
			}
			else break;
		}

		//Ricerca delle ruote vincenti
		bool first = true;
		for (int j = 0; j < lens[luckyNumber]; j++) {
            int n = indexed[luckyNumber][j];
            
			bool OK = true;
			for (int h = 0; h < k; h++) {
				if (!ruote[n].bitmask[daCercare[h]]) {
					OK = false; break;
				}
            }

			if (first && OK) {
				fprintf(out, "-- ");
				for (int h = 0; h < k-1; h++)
					fprintf(out, "%d,", daCercare[h]);
				fprintf(out, "%d --\n", daCercare[k-1]);
				
				first = false;
			}
			if (OK) {
				fprintf(out, "%s %s ", ruote[n].data->c_str(), ruote[n].luogo->c_str());
				for (int h = 0; h < v-1; h++)
					fprintf(out, "%d,", ruote[n].numeri[h]);
				fprintf(out, "%d\n", ruote[n].numeri[v-1]);
			}
		}
	}
	
	cout << "Tempo per la ricerca: " << (clock()-start)/1000.0 << " secondi" << endl;
}

[Vincenzo1968]

Originariamente inviato da Vincenzo1968

Vicius ehm...

so che ti sto scassando i cabasisi ma mi da errore. Puoi azzizzarmelo per la versione 1.8.7?
...

Come non detto. Ho scaricato la versione 1.9. Fra un po' posto la classifica aggiornata(tenendo conto anche della nuova versione di Mesh89).

[ercand]

Io ottengo questi valori

LottoFindDifficile 0.185443 secondi
LOTTO.D2 18.48295 secondi

Nella prova con lotto.d2 ottento 30041 valori trovati, mii confermate se è giusto?

[Vincenzo1968]

Classifica aggiornata:



Purtroppo non ho potuto inserire Vicius perchè, sul file grosso, dopo un po' se ne esce con questo messaggio:

[rеpne scasb]

■

[rеpne scasb]

■

[rеpne scasb]

■

[Vincenzo1968]

Originariamente inviato da ercand

Io ottengo questi valori

LottoFindDifficile 0.185443 secondi
LOTTO.D2 18.48295 secondi

Nella prova con lotto.d2 ottento 30041 valori trovati, mii confermate se è giusto?

non so se siano 30041. Ti posto la parte finale dei risultati di Mesh e Repne:

mesh:

-- 86,62,45,38,88 --
14/05/1983 HXXZLVFGBQTQVXVH 86,38,88,62,65,45
-- 35,56,68,81,20 --
01/12/2013 OSEFHKQANUTVSGPM 68,35,69,20,56,81
-- 38,71,27,78 --
18/08/1989 ZLLBLMMKFAENJGGB 4,78,38,65,71,27
31/04/2019 PZKWKBDJISNDKDLI 27,31,71,78,90,38
22/03/1991 MWRLGZILPWGPNEHH 27,71,89,38,74,78
31/09/1988 ZIKUSRGGSEJTEHLG 71,78,38,27,36,56
13/04/2009 PBHXPVPWOZZGDOBP 27,78,4,63,38,71
25/11/2015 LGPCLZZFOFOGIUSM 36,27,28,71,38,78

repne:

-- 38,45,62,86,88 --
14/05/1983 HXXZLVFGBQTQVXVH 38,45,62,65,86,88
-- 20,35,56,68,81 --
01/12/2013 OSEFHKQANUTVSGPM 20,35,56,68,69,81
-- 27,38,71,78 --
25/11/2015 LGPCLZZFOFOGIUSM 27,28,36,38,71,78
13/04/2009 PBHXPVPWOZZGDOBP 4,27,38,63,71,78
31/09/1988 ZIKUSRGGSEJTEHLG 27,36,38,56,71,78
22/03/1991 MWRLGZILPWGPNEHH 27,38,71,74,78,89
31/04/2019 PZKWKBDJISNDKDLI 27,31,38,71,78,90
18/08/1989 ZLLBLMMKFAENJGGB 4,27,38,65,71,78

[Vincenzo1968]

Qualcuno che s'intende di Eclipse/Java?
Con i file postati da magix2003 ho questo problema:

[cionci]

Posto ormai il mio, fa cacare, lo so, ma ormai l'avevo fatto con un'altra idea in testa (che il numero di estratti per ruota non potesse variare). Comunque l'ho adattato al numero variabile di estratto ed ho trovato un modo molto carino (grazie al C++) per generare le combinazioni semplici dei numeri, spero interessi a qualcuno

#include <iostream>
#include <fstream>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <iomanip>

using namespace std;

#define DATAFILENAME    "LottoDataDifficile.txt"
#define SEARCHFILENAME  "LottoFindDifficile.txt"


void parseNumberString(const string &numbers, vector<int> &unsortedNumbers)
{
    unsigned int i = 0;
    int items = 0;
    while(i < numbers.size())
    {
        if(numbers[i] >= '0' && numbers[i] <= '9')
        {
            unsortedNumbers.push_back(numbers[i] - '0');
            if(numbers[i+1] >= '0' && numbers[i+1] <= '9')
            {
                ++i;
                unsortedNumbers.at(items) = unsortedNumbers.at(items) * 10 + (numbers[i] - '0');
            }
            ++items;
        }
        ++i;
    }
}

class Drawing
{
    vector<int> sortedNumbers;
    const string city;
    const string date;
    const string numbers;


public:
    Drawing(const string &city, const string &date, const string &numbers): city(city), date(date), numbers(numbers)
    {
        parseNumberString(numbers, sortedNumbers);

        sort(sortedNumbers.begin(), sortedNumbers.end());
    }

    const string & getCity()
    {
        return city;
    }

    const string & getDate()
    {
        return date;
    }

    const string & getNumbersString()
    {
        return numbers;
    }

    const vector<int> & getNumbersVector()
    {
        return sortedNumbers;
    }
};


class SimpleCombination
{
    unsigned int count;
    vector<int> markers;
    vector<int> values;
    bool hasNextCombination;

public:
    SimpleCombination(const vector<int> &values, unsigned int count): count(count), values(values)
    {
        for(unsigned int i = 0; i < values.size(); ++i)
        {
            markers.push_back((i < count) ? 1 : 0);
        }

        next_permutation(markers.begin(), markers.end());
        hasNextCombination = true;
    }

    bool hasNext()
    {
        return hasNextCombination;
    }

    void nextCombination(vector<int> & combination)
    {
        combination.resize(values.size());
        for(unsigned int i = 0; i < values.size(); i++)
        {
            combination.at(i) = values.at(i) * markers.at(i);
        }
        hasNextCombination = next_permutation(markers.begin(), markers.end());
    }
};

//#define INDEXTYPE long
#define INDEXTYPE double


class Database
{
    map<INDEXTYPE, list<Drawing *> > drawings;
    int numberCount;

    INDEXTYPE computeIndex(const vector<int> v)
    {
        INDEXTYPE index = 0;
        INDEXTYPE multiplier = 1;
        for(unsigned int i = 0; i < v.size(); i++)
        {
            if(v.at(i) > 0)
            {
                index += v.at(i) * multiplier;
                multiplier *= 100;
            }
        }

        return index;
    }

public:
    Database(int numberCount): numberCount(numberCount)
    {
    }

    void insertDrawing(Drawing *drawing)
    {
        for(int i = 1; i <= numberCount; ++i)
        {
            SimpleCombination sc(drawing->getNumbersVector(), i);
            do
            {
                vector<int> combination;
                sc.nextCombination(combination);
                drawings[computeIndex(combination)].push_back(drawing);
            }
            while(sc.hasNext());
        }
    }

    list<Drawing *> & findDrawing(const string &numbers)
    {
        vector<int> sortedNumbers;
        parseNumberString(numbers, sortedNumbers);

        sort(sortedNumbers.begin(), sortedNumbers.end());

        return drawings[computeIndex(sortedNumbers)];
    }
};


int main()
{
    ifstream f(DATAFILENAME);

    string date, city, numbers;

    if(f.fail()) return 1;

    getline(f, numbers);
    getline(f, numbers, ' ');

    int numberCount;
    f >> numberCount;

    if(f.fail()) return 1;
    Database db(numberCount);

    getline(f, numbers);

    while(1)
    {
        getline(f, date, ' ');
        if(f.eof() || f.fail()) break;
        getline(f, city, ' ');
        getline(f, numbers);
        Drawing * d = new Drawing(city, date, numbers);
        db.insertDrawing(d);
    }

    f.close();

    f.open(SEARCHFILENAME);

    if(f.fail()) return 1;

    int count;
    getline(f, date, ' ');
    f >> count;
    getline(f, numbers);
    for(int i = 0; i < count; ++i)
    {
        getline(f, numbers);
        list<Drawing *> &l = db.findDrawing(numbers);

        if(l.size() <= 0) continue;

        cout << "-- " << numbers << " --" << endl;

        for(list<Drawing *>::iterator it = l.begin(); it != l.end(); it++)
        {
            cout  << (*it)->getDate() << " " << (*it)->getCity() << " " <<  (*it)->getNumbersString() << endl;
        }
    }
    return 0;
}