[Vari] Contest 3: La somma

[gugoXX]

Forza, muoviamo sto clock, sia del cervello che del computer.

Sia data una lista di interi disordinata (vedi fondo del post)

Esempio: 1 13 10 22 5 7 5 3 1 7 3 7

A- Base
Trovare quanti sono gli elementi che sono ripetuti almeno 2 volte. Nell'esempio e' 4 (Ci sono 4 valori diversi che sono ripetuti almeno 2 volte).
(Punti 2)
Quel e' l'occorrenza massima delle ripetizioni.
(ovvero quante volte e' ripetuto il numero che e' ripetuto per piu' volte)
Nell'esempio e' 3, perche' il 7 e' ripetuto 3 volte
(Punti 2)

B- Avanzato
Si costruisca una funzione che, dato in ingresso un intero, dica:
a. se esistono 2 qualsiasi valori della lista tali per cui la loro somma sia il valore cercato, e le "coordinate" dei 2 valori trovati. (Punti 6)
b. Utilizzando la funzione del punto a, per ciascuno dei seguenti dire se sono la somma di 2 valori della lista, e in che posizione sono tali valori: (Punti 6)

217660
222940
9999999
11155123
18185748

Nella lista d'esempio Fn(11) doverebbe restituire
true, 0, 2 (perche' il primo e il terzo valore sono 1+10=11)

Fn(12)
true, 4, 5

Fn(9)
false

Casi particolari
Fn(20)
false. Anche se 10+10 = 20 Non e' ammesso utilizzare 2 volte lo stesso valore. Devono essere 2 valori presi in posizione diversa

Fn(2)
true, 0, 8 Questa volta 1+1 = 2 e' ammesso, perche' si tratta di due UNI diversi.


C- Esperto
Dire qual e' il piu' grande intero minore di 20.000.000 tale per cui
NON sia la somma di qualsiasi 2 valori presenti nella lista (Punti 14)
Da implementarsi eventualmente come esercizio a parte, usando oppure no la funzione di cui prima, a vostra discrezione.

La complessita', per ciascun esercizio, si calcola a partire dalla sola lista/array gia' costruita, che si intende data come input.


lista dei valori:
http://www.usaupload.net/d/d0x556iuxu4
La prima linea contiene il numero di interi in questo formato
//12345//
Le linee a seguire un record per ciascun intero.
PS: Gli interi sono 100.000 (e quindi la prima riga sara' //100000//)
Si sa che sono stati cercati in modo casuale e uniforme nel range 0 - 10.010.000
(il perche' di questo 10.000 e' solo per questioni di probabilita' relativa alla domanda del 3 esercizio)

[cdimauro]

Avast mi segnala questo:

"HTML:Agent-L [Expl]"

quando provo a scaricare il file.

P.S. Appena ho un po' di tempo e il file con la lista di numeri provo a cimentarmi.

[gugoXX]

Originariamente inviato da cdimauro

Avast mi segnala questo:

"HTML:Agent-L [Expl]"

quando provo a scaricare il file.

P.S. Appena ho un po' di tempo e il file con la lista di numeri provo a cimentarmi.

mmh. E' uno zip con un file di testo... Magari c'e' qualcosa nella pagina di quel server.

[shinya]

Uff... maledetto firewall aziendale! Non riesco a scaricare il file...

Va beh, ho qualche idea su come risolvere A e B, ma su C ancora non ho trovato niente di furbo...stasera provo qualcosa...

Ma usare strutture dati diverse per i vari punti è ammesso? Cioè, sono da intendersi come 3 esercizi separati o no?

[gugoXX]

Originariamente inviato da shinya

Uff... maledetto firewall aziendale! Non riesco a scaricare il file...

Va beh, ho qualche idea su come risolvere A e B, ma su C ancora non ho trovato niente di furbo...stasera provo qualcosa...

Ma usare strutture dati diverse per i vari punti è ammesso? Cioè, sono da intendersi come 3 esercizi separati o no?

Sisi', devono essere 3 esercizi separati, nel senso che ogni esercizio riparte dalla Lista di input. Poi se si vuole riutilizzare parte del codice scritto in precedenza non e' vietato.
Diciamo 3 funzioni che ricevono in input almeno una lista.
L'importante e' non barare, ovvero non fare assunzioni particolari sui dati in input.
E' stato dato come ordine di grandezze del dominio dei valori il range 0 - 10010000.
Ma se qualcuno volesse essere piu' preciso, e' possibile cercare il massimo valore della lista da utilizzare eventualmente per semplificare qualcosa, ma occorre inserire nel computo anche l'algoritmo per cercarlo.
(Ovvero non vale cercarlo a priori e poi utilizzarelo come costante).
Se tale valore massimo servisse in tutti e 3 gli esercizi, ciascun esercizio dovra' considerare la complessita' di tale ricerca.

[shinya]

Però scusa non ho capito una cosa...
Nella lista di esempio...con fn(20) perchè dovrebbe tornare "false" quando ci sono il 13 e il 7 che fanno 20?
O era solo per mostrare che non si può usare lo stesso valore? Scusa la domanda scema...

[Vincenzo1968]

Ciao,

per la lista dobbiamo usare un array o possiamo usare una struttura dati a piacere (array, liste concatenate, etc) ?

[gugoXX]

Originariamente inviato da Vincenzo1968

Ciao,

per la lista dobbiamo usare un array o possiamo usare una struttura dati a piacere (array, liste concatenate, etc) ?

Quello che vuoi, ma in input e' data una Lista/Array.
Ovvero devi accettarla come input, ma subito dopo puoi farne quello che vuoi.
(Il primo passo sara' quindi la costruzione di un array o lista a partire dal file)

[shinya]

Questa è la prima soluzione che mi è venuta in mente per il punto B.
Non l'ho provata con il file grande perchè dall'ufficio non riesco a scaricarlo... spero di non aver scritto troppe brutture.

Ho dovuto ordinare la lista, perchè cosi com'era al di là della forza bruta non mi veniva in mente niente di furbo... quindi c'è da aggiungere la complessità del merge sort che usa la classe Collections al suo interno, e l'inizializzazione di tutta la lista usando una class Term che racchiude il numero e la posizione originale. Sarebbe stato più semplice se i requisiti fossero stati i numeri e non le coordinate.

Il costruttore di Contest3 si prende il caso di test...

import java.util.*;

public class Contest3 {
  public static void main(String[] args) {
    new Contest3(2);
  }
  
  public Contest3(int term) {
    List<Term> numbers = initList(Arrays.asList(1,13,10,22,5,7,5,3,1,7,3,7));
    
    int[] result = findAddends(numbers, term);
    System.out.println(result[0] + " " + result[1]);
  }
  
  private List<Term> initList(List<Integer> numbers) {
    List<Term> result = new ArrayList<Term>();
    
    for (int i = 0; i < numbers.size(); ++i) {
      result.add(this.new Term(numbers.get(i), i));
    }
    return result;
  }
  
  private int[] findAddends(List<Term> numbers, int term) {
    int[] pair = new int[2];
    
    Collections.sort(numbers);
    int i = 0, j = numbers.size() - 1, sum = 0;
    while (i < j) {
      sum = numbers.get(i).number + numbers.get(j).number;
      
      while (sum <= term && i < j) {
        sum = numbers.get(i).number + numbers.get(j).number;
        if (sum == term) {
          pair[0] = numbers.get(i).originalPosition; 
          pair[1] = numbers.get(j).originalPosition;
          return pair;
        }
        i++;
      }
      j--;
    }
    
    return pair;
  }
  
  private class Term implements Comparable<Term> {
    public Integer number;
    public int originalPosition;
    
    public Term(int number, int originalPosition) {
      this.number = number;
      this.originalPosition = originalPosition;
    }
    
    public int compareTo(Term t) {
      return number.compareTo(t.number);
    }
  }
}

Stasera provo con il file grande...

[cdimauro]

La domanda sorge spontanea: a che serve questo contest?

[gugoXX]

Originariamente inviato da cdimauro

La domanda sorge spontanea: a che serve questo contest?

Boh? Dato un input e una domanda trovare i modi piu' efficienti per rispondere...
Direi provare un po' di alternative che non coinvolgano la forza bruta, altrimenti un sistema come quelli che abbiamo oggi non puo' trovare le risposte in tempi decenti.

[Albi89]

Beh ovviamente mi preparo a ricevere innumerevoli insulti (come saprete ho solo delle misere conoscenze da studentello del primo anno), ma ho affrontato la prima parte del problema così:

void MyList::check_occurrences() {
    map<unsigned,unsigned> occurrences;

    for (vector<unsigned>::const_iterator it = list.begin(); it != list.end(); ++it)
        ++occurrences[*it];

    map<unsigned, unsigned>::size_type count = 0;
    map<unsigned, unsigned>::const_iterator max = occurrences.begin();
    for (map<unsigned, unsigned>::const_iterator it = occurrences.begin(); it != occurrences.end(); ++it) {
        if (it->second >= 2)
	    count++;
        if (it->second > max->second)
	    max = it;
    }

    cout << "Numero elementi ripetuti almeno 2 volte: " << count << endl;
    cout << "Elemento piu' frequente: " << max->first << ' ' << max->second << endl; 
}

Dopo provo anche il punto B, ma già capisco che le mie soluzioni sono decisamente dispendiose

[gugoXX]

Originariamente inviato da shinya

Però scusa non ho capito una cosa...
Nella lista di esempio...con fn(20) perchè dovrebbe tornare "false" quando ci sono il 13 e il 7 che fanno 20?
O era solo per mostrare che non si può usare lo stesso valore? Scusa la domanda scema...

No, hai perfettamente ragione.
Nell'esempio avrebbe dovuto restutire true, proprio perche almeno 13+7= 20 (ma non perche' 10+10=20)
L'avevo fatto a mano e non me ne ero accorto...

[Albi89]

Purtroppo la mia versione dell'esercizio B è ancora assai lenta, non so se qualcuno ha provato un approccio "brute force" per compararlo, ma la mia (basata su un vector di coppie di possibili addendi) non è ancora propriamente "scattante".

Vi riporto un output di esempio del programma per confrontarlo coi vostri, appena migliorerò un po' il codice lo posterò

In quest'esecuzione ho testato tutti i valori proposti da gugoXX

Numero elementi ripetuti almeno 2 volte: 459
Elemento piu' frequente: 6361273 4

217660 non e' scomponibile in addendi presenti nella lista

222940 non e' scomponibile in addendi presenti nella lista

9999999 e' la somma dei numeri:
6388096 in posizione 425
3611903 in posizione 70532

11155123 e' la somma dei numeri:
7525320 in posizione 123
3629803 in posizione 70500

18185748 e' la somma dei numeri:
10012786 in posizione 2023
8172962 in posizione 94669

Tempo impiegato: 608.518s

Come potete vedere il tempo di esecuzione è di circa 10 minuti, una piccola infinità.

[ndakota]

per il tempo di esecuzione in java? c'è qualche classe utile? mi basta il package poi spulcio io le api..

[Giullo]

ho provato a cimentarmi col punto 2, questo è l'output che ricevo in console

Reading the file and building the list in 0.49909
Sorting the list in 2.415708
Looking for 217660
Looking for 222940
Looking for 9999999
9999999 found! values (7895, 9992104) at positions (3590, 37312) in 0.002228
Looking for 11155123
11155123 found! values (1078115, 10077008) at positions (38441, 92416) in 0.025468
Looking for 18185748
18185748 found! values (8099248, 10086500) at positions (64082, 60049) in 0.401179

qui il codice ruby, fondamentalmente non ho trovato al momento una soluzione migliore di quella di shinya, vediamo se stasera a mente un pò più fresca mi viene in mente qualcosa di diverso

#!/usr/bin/ruby -w

class Contest
  
  def initialize(file)
    start_time = Time.now
    file = File.new(file, "r")
    @list_original = []
    counter = 0
    first = false
    while (line = file.gets)
      first = true and next if !first
      @list_original.push(Item.new(line.to_i, counter))
      counter += 1
    end
    elapsed = Time.now
    puts "Reading the file and building the list in #{(elapsed-start_time).to_s}"  
    file.close
    start_time = Time.now
    @list_sorted = @list_original.sort {|x,y| x.value <=> y.value }
    elapsed = Time.now
    puts "Sorting the list in #{(elapsed-start_time).to_s}"  
  end
  
  
  def search_for(num)
    puts "Looking for "+num.to_s
    start_time = Time.now
    j = @list_sorted.length-1
    i = 0
    out = []
    while i < j do
      sum = @list_sorted[i].value + @list_sorted[j].value
      while (sum <= num && i < j) do
       ival = @list_sorted[i]
       jval = @list_sorted[j]
       sum =  ival.value + jval.value
       if (sum == num)
         elapsed = Time.now
         out[0] = ival
         out[1] = jval
         puts "#{num} found! values (#{out[0].value}, #{out[1].value}) at positions (#{out[0].position}, #{out[1].position}) in #{(elapsed-start_time).to_s}"
         return out
       end
       i += 1
      end
      j -= 1
    end
    return out
  end
  
end


class Item
  
  attr_accessor :value, :position
  
  def initialize(value, position)
    @value = value
    @position = position
  end
  
end




c = Contest.new("lista.txt")
c.search_for(217660)
c.search_for(222940)
c.search_for(9999999)
c.search_for(11155123)
c.search_for(18185748)

[nico159]

Sono riuscito a fare il mio primo programmino che fa qualcosa...e per di più in Python
Almeno quattro punti li ho fatti?
Dopo vedrò come implementare il resto

class Contest:
    numbers = []
    def __init__(self, file = None):
        if not file:
            file = 'lista.txt'
        self.__getNumbersFrom(file)
            
    def __getNumbersFrom(self, file):
        txt = open(file)
        for line in txt:
            self.numbers.append( int(line) )
        txt.close()
        
    def getRepetition(self):
        dictionaryOfAlexandria = { 'unique' : {}  }
        for number in self.numbers:
            if dictionaryOfAlexandria.has_key(number):
                dictionaryOfAlexandria[number] += 1
            else:
                if dictionaryOfAlexandria['unique'].has_key(number):
                    dictionaryOfAlexandria[number] = 2
                    del dictionaryOfAlexandria['unique'][number]
                else:
                    dictionaryOfAlexandria['unique'][number] = 1
        del dictionaryOfAlexandria['unique']
        return dictionaryOfAlexandria
                    
    def getKingOfRepetition(self):
        repetition = self.getRepetition()
        max = None
        num = None
        for number, repetition in repeated.items():
            if repetition > max:
                max = repetition
                num = number
        return (num, max)

Qualcuno ha consigli per eliminare tutti questi if?

[VICIUS]

Carina l'idea dei concorsi

Questo è il mio tentativo per i due punti della parte A.

def contest_a1(list)
  list.sort!
  
  last = nil
  last_dup = last
  count = 0
  
  list.each do |current|
    if current == last and last_dup != current then
      last_dup = current
      count += 1
    end
    last = current
  end

  return count
end

def contest_a2(list)
  list.sort!
  
  last = nil
  count = 0
  max = 0
  
  list.each do |current|
    if current == last then
      count+=1
    else
      if max < count then
        max = count
      end
      count = 0
    end
    last = current
  end
  
  return max + 1
end

[marco.r]

Esercizio B.
Mancando le closure in C++, fornisco una classe, non una funzione

void readFile( const string& filename,  vector<int>& numbers )
{
    ifstream in(filename.c_str());
    numbers.clear();
    copy( istream_iterator<int>( in ), istream_iterator<int>(),
          back_inserter( numbers ) );
}


class Finder
{
public:
    Finder(const string& filename )
    {
        vector<int> v;
        readFile( "lista.txt", v );
        for ( unsigned int i=0 ; i<v.size() ; ++i )
        {
            s.insert( v[i] );
            index[ v[i] ] = i;
        }
        
    }
    bool findNumber( int sum, pair<int,int>& p )
    {
        for ( set<int>::const_iterator i = s.begin() ; i != s.end() ; ++i )
        {
            set<int>::const_iterator j = s.find( sum - *i );
            if ( j != s.end() )
            {
                p.first = *i;
                p.second = *j;
                return true;
            }
        }
        return false;
    }
    unsigned indexOf( int n )
    {
        return index[n];
    }

private:
    set<int> s;
    map<int,unsigned int> index;
};

La complessita' dovrebbe essere n*logn. Sulla mia macchina ci mette circa 0.25 secondi compreso il caricamento delle tabelle.

[ndakota]

Originariamente inviato da ndakota

per il tempo di esecuzione in java? c'è qualche classe utile? mi basta il package poi spulcio io le api..

mi rispondo da solo.. System.currentTimeMillis() che restituisce un long..