[Vari] Context 2: Ricerca

[^TiGeRShArK^]

ecco il mio algoritmo in C# con qualche bug fix rispetto allo pseudo-codice di cui sopra

class Prova
    {
        int x = 10;

        public Prova()
        {
            string notFound = string.Format("Il numero {0} non è stato trovato.", x);
            string found = string.Format("Trovato il numero {0}.", x);
            int[,] matrix = { {1, 4, 7, 8, 9, 11, 12},
                              {2, 5, 8, 18, 22, 23, 25},
                              {5, 6, 9, 19, 25, 25, 26},
                              {8, 13, 13, 20, 27, 28, 29},
                              {10, 15, 18, 22, 29, 20, 35}};
            int m = matrix.GetLength(0) - 1;
            int n = matrix.GetLength(1) - 1;
            int i = 0;
            int j = 0;

            while (matrix[i, j] <= x && i < m && j < n)
            {
                i++;
                j++;
            }
            i--;
            j--;
            if (matrix[i, j] == x)
            {
                exit(found);
            }

            int a = i;
            int b = j;
            while (matrix[m, j] >= x || matrix[i, n] >= x || i > 0)
            {
                for (int u = m; u > a; u--)
                {
                    if (matrix[u, j] == x)
                        exit(found);
                }

                for (int v = n; v > b; v--)
                {
                    if (matrix[i, v] == x)
                        exit(found);
                }
                i--;
                j--;
            }

            exit(notFound);
        }

        private static void exit(string message)
        {
            Console.WriteLine(message);
            Console.ReadLine();
            Environment.Exit(0);
        }

        static void Main(string[] args)
        {
            new Prova();
        }
    }

con il secondo caso funziona trovando i numeri 10 e 12 e non trovando il 24.
Ma nel secondo caso c'è una peculiarità che non era presente nel primo requisito, o che almeno mi era sfuggito, ovvero che la cella a destra o la cella inferiore possa avere un valore uguale alla cella corrente, mentre io avevo capito che dovessero essere strettamente crescenti

[71104]

scusate, non ho minimamente letto il thread, ma affascinato dal problema voglio provare la mia soluzione

se non vi spiace la scrivo in C#

    class MatrixTest
    {
        static int[,] Matrix =
        {
            {1, 4, 7, 8, 9, 11},
            {2, 5, 8, 10, 11, 12},
            {5, 6, 9, 12, 14, 15},
            {7, 8, 12, 15, 17, 20},
            {8, 9, 17, 18, 19, 20},
        };

        static bool[,] Auxiliary = new bool[Matrix.GetLength(0), Matrix.GetLength(1)];

        static void Initialize()
        {
            for (int i = 0; i < Auxiliary.GetLength(0); i++)
            {
                for (int j = 0; j < Auxiliary.GetLength(1); j++)
                {
                    Auxiliary[i, j] = true;
                }
            }
        }

        static bool Exists(int Value, int x, int y)
        {
            if (!Auxiliary[y, x])
            {
                return false;
            }

            if (Matrix[y, x] == Value)
            {
                return true;
            }

            if (x + 1 < Matrix.GetLength(1))
            {
                if (Matrix[y, x + 1] <= Value)
                {
                    if (Exists(Value, x + 1, y))
                    {
                        return true;
                    }
                }
            }

            if (y + 1 < Matrix.GetLength(0))
            {
                if (Matrix[y + 1, x] <= Value)
                {
                    if (Exists(Value, x, y + 1))
                    {
                        return true;
                    }
                }
            }

            Auxiliary[y, x] = false;
            return false;
        }

        static bool Exists(int Value)
        {
            Initialize();
            return Exists(Value, 0, 0);
        }

        static void Main(string[] Arguments)
        {
            for (int i = 1; i <= 20; i++)
            {
                if (Exists(i))
                {
                    System.Console.WriteLine(i + " is present");
                }
                else
                {
                    System.Console.WriteLine(i + " isn\'t present");
                }
            }
        }
    }

[71104]

ho provato il mio programma usando la matrice di TigerShark, funziona.

[gugoXX]

Posso gentilmente chiedervi se potete adoperare una classe matrice tipo questa
Oppure se comunque potete tenere il conto di tutte le volte che leggete un valore dalla matrice (anche per confronti, in qualsiasi caso)
cosi' possiamo poi confrontare i numeri di letture e in qualche modo dedurne la complessita' anche senza valutare l'algoritmo.

Sto preparando 2 belle matricione, una 250x200, l'altra 8.000x10.000.
sara' un file di testo comma separated.
prima riga: numero colonne,numero righe
righe successive: 5,6,90,150,...
i valori sono da intendersi interi positivi.

La set dei valori l'ho piazzata solo nel caso in cui la usassimo per caricare i dati dall'esterno.

// Modificate pure a piacere, l'importante e' il conteggio dei get.
public class Matrix
{        
    int[,] matrix = { {1, 4, 7, 8, 9, 11, 12},
                      {2, 5, 8, 18, 22, 23, 25},
                      {5, 6, 9, 19, 25, 25, 26},
                      {8, 13, 13, 20, 27, 28, 29},
                      {10, 15, 18, 22, 29, 20, 35}};

    public int GetCount = 0;  
          
    public int this[int y,int x]
    {
        get
        {
            GetCount++;
            return matrix[y,x];
        }
        set
        {
            matrix[y, x] = value;
        }
    }
}

[^TiGeRShArK^]

Originariamente inviato da 71104

ho provato il mio programma usando la matrice di TigerShark, funziona.

mmm..
ma non c'è un modo per inizializzare la matrice di booleani direttamente a true?
in quel modo hai complessità O(m*n) solo per l'inizializzazione di Auxiliary

[gugoXX]

Per i pigroncelli, in C# la classe Matrice potrebbe essere qualcosa tipo questa
compresa la lettura da file.

public class Matrix
{        
    int[,] matrix = null;
    public Matrix(int y, int x)
    {
        matrix = new int[y, x];
    }

    public Matrix(StreamReader sr)
    {
        string dimrow = sr.ReadLine();
        string[] dimstrings = dimrow.Split(',');
        if (dimstrings.Length != 2) throw new Exception("Head Error");
        int dx = int.Parse(dimstrings[0]);
        int dy = int.Parse(dimstrings[1]);
        matrix = new int[dy, dx];
        for (int row = 0; row < dy; row++)
        {
            string rowstring = sr.ReadLine();
            string[] valoristringa = rowstring.Split(',');
            if (valoristringa.Length != dx) throw new Exception(string.Format("Record Error: {0}", row));
            var convertiti = valoristringa.Select((t,index) => new{ index=index, val=int.Parse(t)} );
            convertiti.ToList().ForEach(t => matrix[row,t.index]=t.val );                
        }
    }                

    public int GetCount = 0;

    public int GetLength(int dimension)
    {
        return matrix.GetLength(dimension);
    }
          
    public int this[int y,int x]
    {
        get
        {
            GetCount++;
            return matrix[y,x];
        }
    }        
}

e questo il contenuto del file di prova di base

7,5
1, 4, 7, 8, 9, 11, 12
2, 5, 8, 18, 22, 23, 25
5, 6, 9, 19, 25, 25, 26
8, 13, 13, 20, 27, 28, 29
10, 15, 18, 22, 29, 30, 35

[shinya]

Originariamente inviato da gugoXX

Non ho ancora letto le soluzioni, e mi paiono promettenti.
Forse c'e' ancora qualcosina da aggiustare.
Provate ad applicare gli algoritmi anche a questo esempio



In cui ci sia da trovare il 10, il 12 oppure il 24

Con l'ultima matrice che hai dato il mio codice con l'heap funziona... l'ho snellito un attimo...

import java.util.*;

public class Contest2 {
  public static void main(String[] args) {
    List<Integer> values = Arrays.asList(1, 4, 7, 8, 9, 11, 12,
                                         2, 5, 8, 18, 22, 23, 25,
                                         5, 6, 9, 19, 25, 25, 26,
                                         8, 13, 13, 20, 27, 28, 29,
                                         10, 15, 18, 22, 29, 30, 35);
    
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(values);
    int [] tests = {10, 12, 24};
    for (int i : tests) search(pq, i);
  }
  
  private static void search(PriorityQueue<Integer> pq, int guess) {
    int elem;
    do {
      elem = pq.poll();
      if (elem == guess) {
        System.out.println("Found " + guess);
        return;
      }
    } while (elem < guess);
    
    System.out.println(guess + " not found! :(");
  }
}

Output:
Found 10
Found 12
24 not found! :(

Probabilmente la soluzione proposta da tigershark però è più efficiente, sto cercando di capirla rileggendo i post

[gugoXX]

Originariamente inviato da shinya

Con l'ultima matrice che hai dato il mio codice con l'heap funziona... l'ho snellito un attimo...

La complessita' di questo algoritmo e' quadratica non e' vero?
E' una O(N*M).
Diciamo triangolare
O(N*M/2)
Anzi, mediamente meno, O(N*M/4)

vero?

Riesci a calcolare quante celle leggi prima di dire il risultato?

[^TiGeRShArK^]

per il numero 10 ho 21 letture, per il numero 12 24 letture e per il 24 26 letture.
Questo perchè avevo fatto un paio di cappellate e facevo delle letture inutili tanto perchè ero masochista
Ora ho 18 letture per i numeri trovati e 19 per quello non trovato.
Tutto questo utilizzando la ricerca lineare e non quella binaria
e secondo me ancora faccio ancora una lettura inutile perchè contando a mano dovrei metterci 17 passi per trovare il 10, mentre ce ne metto 18 con l'implementazione attuale
EDIT: ora vedo di implementare la ricerca binaria

[shinya]

Originariamente inviato da gugoXX

Riesci a calcolare quante celle leggi prima di dire il risultato?

Edit: no scusate scusate, avevo sbagliato tutto...
Questo è l'output corretto:

Found 10 in 13 steps.
Found 12 in 15 steps.
24 not found in 26 steps.

e questo il codice...quello di prima era sbagliato, funzionava per caso. Rimuovevo elementi dall'heap e usavo il resto per calcolare gli altri test.

import java.util.*;

public class Contest2 {
  public static void main(String[] args) {
    List<Integer> values = Arrays.asList(1, 4, 7, 8, 9, 11, 12,
                                         2, 5, 8, 18, 22, 23, 25,
                                         5, 6, 9, 19, 25, 25, 26,
                                         8, 13, 13, 20, 27, 28, 29,
                                         10, 15, 18, 22, 29, 30, 35);
    
    int [] tests = {10, 12, 24};
    for (int i : tests) search(values, i);
  }
  
  private static void search(List<Integer> values, int guess) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(values);
    int elem;
    int guessing = 0;
    do {
      elem = pq.poll();
      guessing++;
      if (elem == guess) {
        System.out.println("Found " + guess + " in " + guessing + " steps.");
        return;
      }
    } while (elem < guess);
    
    System.out.println(guess + " not found in " + guessing + " steps.");
  }
}

[gugoXX]

Originariamente inviato da shinya

Edit: no scusate scusate, avevo sbagliato tutto...
Questo è l'output corretto:

Found 10 in 13 steps.
Found 12 in 15 steps.
24 not found in 26 steps.

Shinya scusa, ma la priority queue nel costruttore non ordina tutta l'enumerazione?
Se la ordina tutta significa che leggi tutti gli elementi almeno una volta.
Per leggerla tutta ti fermi li'... cerchi se c'e' il valore.

[shinya]

Si hai ragione, li legge tutti per forza...fa cagare cosi...

[morskott]

Aggiunta una piccola interfaccetta grafica, la matrice si puo sia scrivere nell'interfaccetta che caricare da file, il formato deve essere per esempio

matrice
numero da cercare

,per esempio

1 4 7
2 5 8
5 6 9
6

l'ho provato scrivendo a mano i valori ma non caricando il file (ma dovrebbe funzionare anche in questo caso), il codice è

import java.util.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.io.*;

public class CercaNumero extends JFrame{
	private JTextArea matriceJTA;
	private JLabel risJL;
	private JLabel numValutatoJL;

	public CercaNumero(){
		Container cpain=this.getContentPane();
		matriceJTA=new JTextArea();
		JScrollPane jsp=new JScrollPane();
		JPanel jpa=new JPanel();
		jpa.add(matriceJTA);
		jsp.add(jpa);
		this.setLayout(new BorderLayout());
		JButton caricaDaFileJB=new JButton("Valuta da File");
		caricaDaFileJB.addActionListener(new ActionListener(){
			public void actionPerformed(ActionEvent e){
				caricaDaFile();
			}
		});
		cpain.add(matriceJTA,BorderLayout.CENTER);
		JPanel buttonsJP=new JPanel();
		buttonsJP.add(caricaDaFileJB);
		JButton caricaDaTextJB=new JButton("Valuta matrice scritta");
		caricaDaTextJB.addActionListener(new ActionListener(){
			public void actionPerformed(ActionEvent e){
				caricaDaText();
			}
		});
		buttonsJP.add(caricaDaTextJB);
		risJL=new JLabel();
		cpain.add(buttonsJP,BorderLayout.NORTH);
		JPanel south=new JPanel();
		numValutatoJL=new JLabel();
		south.add(new JLabel("Numero valutato:"));
		south.add(numValutatoJL);
		south.add(new JLabel("Risultato:"));
		south.add(risJL);
		cpain.add(south,BorderLayout.SOUTH);
		this.setSize(300,200);
		this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	}
	
	private void caricaDaFile(){
		String nomeFile=JOptionPane.showInputDialog("Inserisci il nome del file");
		try{
			FileInputStream fis=new FileInputStream(nomeFile);
			InputStreamReader isr=new InputStreamReader(fis);
			BufferedReader br=new BufferedReader(isr);
			
			String matrix=br.readLine();
			String input;
			while((input=br.readLine())!=null) matrix+="\n"+input;
			boolean ris=calcola(matrix);
			risJL.setText(String.valueOf(ris));
			
			br.close();
			isr.close();
			fis.close();
		}catch(Exception ex){}
	}
	
	private void caricaDaText(){
		boolean ris=calcola(matriceJTA.getText());
		risJL.setText(String.valueOf(ris));
	}
	
	private boolean calcola(String mat){
		StringTokenizer st=new StringTokenizer(mat,"\n");
		java.util.List<String> righe=new LinkedList<String>();
		while(st.hasMoreTokens()){
			String tmp=st.nextToken();
			righe.add(tmp);
		}
		int[][] matrix=new int[righe.size()-1][];
		for (int i=0;i<matrix.length;i++){
			String intRiga=righe.get(i);
			StringTokenizer st1=new StringTokenizer(intRiga);
			matrix[i]=new int[st1.countTokens()];
			for (int j=0;j<matrix[i].length;j++){
				matrix[i][j]=Integer.parseInt(st1.nextToken());
			}
		}
		int numero=Integer.parseInt(righe.get(righe.size()-1));
		numValutatoJL.setText(String.valueOf(numero));
		stampaMatrice(matrix);
		return isInConAStar(matrix,numero);
	}
	
	private static int h(int curr,int numero){
		return numero-curr;
	}
	
	private static void stampaMatrice(int[][] matrix){
		for (int i=0;i<matrix.length;i++){
			System.out.println(Arrays.toString(matrix[i]));
		}
	}

	public static boolean isInConAStar(int[][] matrice,int numero){
		class Coppia implements Comparable<Coppia>{
			int i,j;
			int goodness;
		
			Coppia(int i,int j,int goodness){
				this.i=i;
				this.j=j;
				this.goodness=goodness;
			}
			
			public int compareTo(Coppia c){
				return this.goodness-c.goodness;
			}
			
			public boolean equals(Object o){
				if (o!=null && this.getClass().equals(o.getClass())){
					Coppia c=(Coppia)o;
					return this.i==c.i && this.j==c.j;
				}else
					return false;
			}
			
			public int hashCode(){
				return this.i+31*this.j;
			}
		}
		SortedSet<Coppia> frontiera=new TreeSet<Coppia>();
		frontiera.add(new Coppia(0,0,h(matrice[0][0],numero)));
		while(!frontiera.isEmpty()){
			Coppia current=frontiera.first();
			if (matrice[current.i][current.j]==numero) return true;
				System.out.println("Visistato il numero:"+String.valueOf(matrice[current.i][current.j]));
			frontiera.remove(current);
			int goodness_i=-1;
			int goodness_j=-1;
			try{
				goodness_i=h(matrice[current.i+1][current.j],numero);
			} catch(ArrayIndexOutOfBoundsException ex){};
			try{
				goodness_j=h(matrice[current.i][current.j+1],numero);
			} catch(ArrayIndexOutOfBoundsException ex){};
			if (goodness_i>=0){
				if (goodness_j>=0){
					frontiera.add(new Coppia(current.i,current.j+1,goodness_j));
					frontiera.add(new Coppia(current.i+1,current.j,goodness_i));
				}else{
					frontiera.add(new Coppia(current.i+1,current.j,goodness_i));
				}
			}else{
				if (goodness_j>=0){
					frontiera.add(new Coppia(current.i,current.j+1,goodness_j));
				}
			}
		}
		return false;
	}
	
	public static void main(String[] args){
		int[][] matrice=new int[3][3];
		matrice[0][0]=1;
		matrice[0][1]=4;
		matrice[0][2]=7;
		matrice[1][0]=2;
		matrice[1][1]=5;
		matrice[1][2]=8;
		matrice[2][0]=5;
		matrice[2][1]=6;
		matrice[2][2]=9;
		
		int numeroEsistente=6;
		int numeroMinoreNonEsistente=3;
		int numeroMaggioreNonEsistente=19;
		
		boolean conNumeroEsistente=isInConAStar(matrice,numeroEsistente);
		System.out.println("Finita prima ricerca");
		boolean conNumeroNonEsistenteMinore=isInConAStar(matrice,numeroMinoreNonEsistente);
		System.out.println("Finita seconda ricerca");
		boolean conNumeroNonEsistenteMaggiore=isInConAStar(matrice,numeroMaggioreNonEsistente);
		System.out.println("Finita terza ricerca");
		
		System.out.println("A* - Con numero esistente:"+String.valueOf(conNumeroEsistente)+" - con numero non esistente minore:"+String.valueOf(conNumeroNonEsistenteMinore)+" - con numero non esistente maggiore:"+String.valueOf(conNumeroNonEsistenteMaggiore));
		CercaNumero cn=new CercaNumero();
		cn.setVisible(true);
	}
}

fa prima una prova con una matrice standard e numeri già fissati e poi inizializza la grafica, quando si carica la matrice sia da file che scrivendola on the fly la stampa su console e stampa sempre su console ogni numero che visita. Tutte quelle righe son piu per scrivere la GUI e per passare da una rappresentazione stringa ad una matriciale che per l'algoritmo vero e proprio.

Ho preso in prestito un metodo utilizzato in intelligenza artificiale!! (Albero A*)

[gugoXX]

Ho messo sul primo post un collegamento ad una matrice 250 x 200
Sto gettando giu' l'algoritmo anche io. Per ora ho fatto il contorno, che mi e' servito per creare la mattrice e per trovare i valori di test, anch'essi nel primo post.

-----------------------------------------------
- Matrix Dimensions: 250, 200
- MinimumValue: 26
- MaximumValue: 32539
- CheckIpothesis: True
- Minimo non esistente 0
- Massimo non esistente 32538
- Mediana non esistente 20985
-----------------------------------------------

[gugoXX]

Azz stiamo andando anche sui metodi AI?
Pensavo di introdurre stimoli per algortmi Greedy in qualche Contest piu' avanti, eventualmente risolvibile con tecniche di AI (Scritto giusto stavolta, che vergogna)
Penso che per questo mi limitero' ad una ricerca normale.

[shinya]

Si credo che A* in questo contesto dovrebbe essere illegale...

Credo che la soluzione postata da marco sia la migliore (e la più elegante anche...).

[morskott]

Azz, ho provato con i primi numeri esistenti e me li trovava abbastanza velocemente, appena ho messo su 11672 entravo in un ciclo infinito!!! (che ad occhio è impossibile, l'algoritmo che uso deve (ha la caratteristica di) terminare sempre!!!! (e non venitemi a dire che il problema della terminazione è indecidibile )) Domani faccio un po di debug ragionato (la funzione core è "isInConAStar").

Per spiegare l'algoritmo in 3 parole ho un Set di indici che voglio considerare, all'inizio lo inizializzo con solo l'elemento a posizione (0,0), controllo se quell'elemento è quello cercato (se si torno subito true) sennò lo rimuovo e applico una funzione di goodness all'elemento appena sotto e a quello appena a destra (una banale distanza tra il numero cercato e il valore considerato), se l'indice è negativo (ho sforato la matrice o l'elemento è maggiore) non faccio niente sennò inserisco le coordinate nel set di indici e continuo il ciclo finchè il set non mi si svuota. Non considero mai 2 volte lo stesso elemento (anzi, quelli piu grandi non li tocco proprio) e ad ogni iterazione tolgo un elemento dal set, quindi come mai non termina???? Misteri della programmazione!!!

[morskott]

Originariamente inviato da shinya

Si credo che A* in questo contesto dovrebbe essere illegale...

Credo che la soluzione postata da marco sia la migliore (e la più elegante anche...).

Perchè illegale? è sempre un algoritmo che sfrutta l'ordine della matrice e che (credo, non l'ho dimostrato formalmente) ad intuito sia sublineare di costo, se solo terminasse la mia implementazione.......(vedi post sopra)

[shinya]

Originariamente inviato da morskott

Perchè illegale?

Dai era per fare una battuta

[gugoXX]

Ecco, ci sono, per ora posto un output castrato.
Forse riesco a migliorare ancora un pochino, ma non sono convinto
Non metto il numero di letture da matrice per ora, per non svelare le carte.

Quella di Marco mi piace. Mi piacerebbe vederla all'opera sul matricione.
Quella di morskott dovrei vederla con piu' calma, vediamo anche i risultati e il numero di letture da matrice.
Consiglio anche a te di fare in Java la classe matrice, per far contare a lei il numero di volte che si fa una get di una cella.
Anche Tiger e 71104 mi piacerebbe vedere i risultati sul matricione.

0 : Not Found

100 : Not Found

32538 : Not Found

20984 : Not Found

32767 : Not Found

32539 : Found - Coords 248,199

26 : Found - Coords 0,0

11672 : Found - Coords 248,0

9790 : Found - Coords 0,199

14089 : Found - Coords 87,110