[Vari] Contest 5: Sottomatrici

[gugoXX]

Due prove sulle sottomatrici.

1.
Sia data una matrice quadrata NxN contenente valori interi positivi, negativi e
zeri. Gli zeri sono in maggioranza. Tale matrice e' una matrice "quasi" sparsa.
Si vuole cercare qual e' la piu' grande sottomatrice quadrata (contigua) composta solo ed esclusivamente di ZERI.

esempio (per semplicita' con soli valori positivi, ma non sara' cosi')

Codice:
23412
20003
10030
25007
12045

in questo caso il risultato è la sottomatrice da 2x2 "radicata" alle coordinate (1,1), supponendo che le coordinate siano zero-based.

L'input sara' la (sola) matrice gia' presente in memoria. Si supponga che arrivi da un passo precedente di calcolo.
L'output saranno le coordinate e la dimensione della sottomatrice ZERO trovata.

2.
Sia data una matrice quadrata NxN, contenente valori interi sia positivi che negativi.
Si considerino tutte le possibili sottomatrici quadrate (contigue).
Tra tutte le possibili sottomatrici quadrate si voglia trovare quella avente la somma massima di tutti i suoi elementi.
(Essendoci anche i valori negativi e' improbabile che sia la matrice completa)

L'output in questo caso saranno le coordinate di partenza della sottomatrice (zero based), la dimensione della sottomatrice e la somma contenuta.

_________

Iniziamo con questi file di test.
Il formato e' testuale
Il primo record contiene la dimensione della matrice di base
ciascuno dei record successivi sono una riga della matrice
i valori di ciascuna riga sono separati fra loro da uno spazio.
I valori negativi ovviamente iniziano con -

Non ho la piu' pallida idea se siano troppo semplici o gia' troppo complessi.
Rispettivamente sono un file per il primo esercizio e un file per il secondo esercizio
http://www.usaupload.net/d/ib45fiaaqc4

[VICIUS]

Primo tentativo al primo punto decisamente naïve.

require 'tools'

class SubMatrix
  def initialize(matrix, row, col)
    @matrix, @row, @col = matrix, row, col
    @row_num, @col_num = 0, 0
  end
  
  def add_row()
    @row_num += 1
  end
  
  def add_column()
    @col_num += 1
  end
  
  def try_add_column()
    return 0 if (@col+@col_num+1) > @matrix.size-1
    for i in @row..(@row+@row_num)
      return 0 if @matrix[i][@col+@col_num+1] != 0
    end
    (@row_num + 1) * (@col_num + 2)
  end
  
  def try_add_row()
    return 0 if (@row+@row_num+1) > @matrix.size-1
    for i in @col..(@col+@col_num)
      return 0 if @matrix[@row+@row_num+1][i] != 0
    end
    (@row_num + 2) * (@col_num + 1)
  end
  
  def size()
    (@row_num + 1) * (@col_num + 1)
  end
  
  def to_s()
    "Matrice row:#{@row}, col:#{@col}, row_num:#{@row_num+1}, col_num:#{@col_num+1}, size:#{size}"
  end
end

def contest5a(matrix)
  best = nil
  for row in 0...matrix.size
    for col in 0...matrix.size
      if matrix[row][col] == 0
        sub = SubMatrix.new(matrix, row, col)
        while (sub.try_add_column > 0) or (sub.try_add_row > 0)
          if sub.try_add_column >= sub.try_add_row
            sub.add_column
          else
            sub.add_row
          end
        end
        if best.nil? or sub.size > best.size
          best = sub
        end
      end
    end
  end
  best
end

test_function :contest5a, 'Matrix0.txt'

E l'output

Matrice row:110, col:257, row_num:10, col_num:10, size:100
Tempo impiegato: (408.270025 secondi)

Forse si può migliorare evitando di chiamare le funzioni try_add due volte per tentativo. Poi voglio provare a saltare a pie pari tutti gli zeri all'interno delle precedenti soluzioni migliori. Se non perde risultati poi provo a saltare anche tutte le precedenti sotto-matrici anche se forse in questo caso sono quasi sicuro che non troverà più molte soluzioni.

[VICIUS]

Originariamente inviato da VICIUS

Forse si può migliorare evitando di chiamare le funzioni try_add due volte per tentativo. Poi voglio provare a saltare a pie pari tutti gli zeri all'interno delle precedenti soluzioni migliori. Se non perde risultati poi provo a saltare anche tutte le precedenti sotto-matrici anche se forse in questo caso sono quasi sicuro che non troverà più molte soluzioni.

La modifica alle try_add non ha portato miglioramenti di alcun tipo.
L'idea di saltare gli zeri all'interno della precedente soluzione migliore ha migliorato di qualche decimo di secondo la media su 5 esecuzioni ma ha cambiato i risultati trovati e penso sia solo un caso che il risultato migliore sia trovato. L'idea di saltare tutti gli zeri della precedente sotto-matrice ha in effetti ridotto ad un quarto il tempo di esecuzione ma come pensavo i risultati sono tutti sballati e il massimo non viene più trovato.

[marco.r]

Non ho capito molto il tuo algoritmo, ma a naso mi sembra strano che ci metta cosi' tanto (forse e' colpa di ruby )
L'idea cmq e' simile alla mia.
Sostanzialmente, per ogni casella (x,y) della matrice, la dimensione massima e' 0 se il numero e' !=0, altrimenti e' 1 + min( A(x,y+1), A(x+1,y), A(x+1,y+1).

(defun solve (matrix rows cols )
  (loop for c from (- cols 1) downto 0 do
       (setf (aref matrix (- rows 1) c)
	     (if (= 0 (aref matrix (- rows 1) c)) 
		 1 
		 0)))
  (loop for r from (- rows 2) downto 0 do
       (setf (aref matrix r (- cols 1))
	     (if (= 0 (aref matrix r (- cols 1)))
		 1
		 0)))
  (loop for r from (- rows 2) downto 0 do
       (loop for c from (- cols 2) downto 0 do
	    (setf (aref matrix r c)
		  (if (= 0 (aref matrix r c))
		      (1+ (min (aref matrix (1+ r) c)
			       (aref matrix r (1+ c))
			       (aref matrix (1+ r) (1+ c))))
		      0)))))


(defun read-row (in size)
  (loop for n from 0 upto (- size 1) collecting (read in)))

(defun read-matrix (filename)
  (with-open-file (in filename :direction :input)
    (let ((size (read in)))
      (make-array `(,size ,size) 
		  :element-type 'fixnum 
		  :initial-contents (loop for n from 0 upto (- size 1)
					 collecting (read-row in size))))))

(defun best (matrix)
  (let ((best 0)
	(bestrow 0)
	(bestcol 0))
    (loop for r from (- (array-dimension matrix 0) 1) downto 0 do
	 (loop for c from (- (array-dimension matrix 1) 1) downto 0 do
	      (let ((x (aref matrix r c)))
		(if (> x best)
		    (progn (setf best x)
			   (setf bestrow r)
			   (setf bestcol c))))))
    (list best bestrow bestcol)))


	  
(defun contest5 (filename)
  (let* ((matrix (read-matrix filename))
	 (size (array-dimension matrix 0))
	 (result (clock-execution (solve matrix size size)))
	 (solution (clock-execution (best matrix))))
    (format t "the solution is at (~a,~a) with size ~a~%" 
	    (second solution)
	    (third solution)
	    (first solution))))

[marco.r]

Anche il secondo punto si puo' fare in modo analogo, anche se bisogna salvare alcune informazioni aggiuntive per ogni cella

[VICIUS]

Originariamente inviato da marco.r

Non ho capito molto il tuo algoritmo, ma a naso mi sembra strano che ci metta cosi' tanto (forse e' colpa di ruby )

Il pc su cui lo stavo provando non era proprio il massimo. Ora sul imac ci mette circa 170 secondi.

Originariamente inviato da marco.r

L'idea cmq e' simile alla mia.
Sostanzialmente, per ogni casella (x,y) della matrice, la dimensione massima e' 0 se il numero e' !=0, altrimenti e' 1 + min( A(x,y+1), A(x+1,y), A(x+1,y+1).

Se non ho capito male parti dall'angolo in basso a destra e calcoli la dimensione delle matrici. Poi percorri in senso inverso la matrice per trovare quella con dimensione maggiore? L'idea mi piace. Questa sera provo ad implementarla qui in ruby e faccio un piccolo confronto.

[71104]

per il punto 1 io direi un programmazione dinamica rapidissimo

detta m la matrice di input, la formula ricorsiva è:

OPT(x, y) = 1 + min{OPT(x+1, y), OPT(x, y+1), OPT(x+1, y+1)} se m[x,y] è uguale a 0

OPT(x, y) = 0 se m[x,y] è diverso da 0


in questo modo OPT(x, y) trova il lato della sottomatrice quadrata più grossa. in quest'ottica la matrice ausiliaria è a due dimensioni e contiene in ciascuna cella il lato della massima sottomatrice nulla "radicata" a quelle coordinate. per avere, oltre alla misura del lato, le coordinate d'origine della sottomatrice cercata si potrebbe fare una ricerca nella matrice ausiliaria, cosa che richiederebbe O(N*M) e che quindi non aumenterebbe la complessità dell'algoritmo, ma sarebbe ovviamente una sciocchezza dopo aver fatto tanto lavoro per cercare il lato
piuttosto sarebbe meglio pensare ad una modifica all'algoritmo risultante affinché restituisca le coordinate anziché il lato.

intanto, detta t la matrice ausiliaria che si suppone inizializzata interamente a -1, e dette N ed M le dimensioni della matrice di input, questo è l'algoritmo che restituisce il lato, in pseudocodice:

function f(x, y)
	if m[x, y] != 0
		t[x, y] <- 0
	else
		if x <= N
			if t[x+1, y] == -1
				t[x+1, y] <- f(x+1, y)
		if y <= M
			if t[x, y+1] == -1
				t[x, y+1] <- f(x, y+1)
		if (x <= N) and (y <= M)
			if t[x+1, y+1] == -1
				t[x+1, y+1] <- f(x+1, y+1)
		t[x, y] <- 1 + min{t[x+1, y], t[x, y+1], t[x+1, y+1]}
	return t[x, y]

e questo è l'algoritmo modificato che restituisce anche le coordinate, inventato or ora:

#bestX e bestY sono due variabili globali entrambe inizializzate a -1

function f(x, y)
	if m[x, y] != 0
		t[x, y] <- 0
	else
		if x <= N
			if t[x+1, y] == -1
				t[x+1, y] <- f(x+1, y)
		if y <= M
			if t[x, y+1] == -1
				t[x, y+1] <- f(x, y+1)
		if (x <= N) and (y <= M)
			if t[x+1, y+1] == -1
				t[x+1, y+1] <- f(x+1, y+1)
		t[x, y] <- 1 + min{t[x+1, y], t[x, y+1], t[x+1, y+1]}
		if t[x, y] > t[bestX, bestY]
			bestX <- x
			bestY <- y
	return t[x, y]

#se al termine dell'algoritmo bestX e bestY valgono ancora -1 e -1 significa che la matrice non contiene zeri

quando ho tempo provo a scriverne un'implementazione. comunque, per chiarezza, la complessità di questa versione dovrebbe essere O(N*M), cioè la funzione viene chiamata al massimo N per M volte.


edit - argh, preceduto da marco.r

[VICIUS]

Versione scopiazzata da marco.r ed implementata in ruby

EDIT: ho messo la versione che fa tutto in una singola passata

def contest5b(matrix)
  best = best_row = best_col = 0
  (matrix.size-1).downto(0) do |c|
    matrix[matrix.size-1][c] = matrix[matrix.size-1][c] == 0 ? 1 : 0
  end
  (matrix.size-1).downto(0) do |r|
    matrix[r][matrix.size-1] = matrix[r][matrix.size-1] == 0 ? 1 : 0
  end
  (matrix.size-2).downto(0) do |r|
    (matrix.size-2).downto(0) do |c|
      matrix[r][c] = matrix[r][c] == 0 ? 1 + min(matrix[r+1][c], matrix[r][c+1], matrix[r+1][c+1]) : 0
      if matrix[r][c] > best
        best, best_row, best_col = matrix[r][c], r, c
      end
    end
  end
  return "best: #{best}, best_row:#{best_row}, best_col:#{best_col}"
end

Il confronto è impietoso. La seconda soluzione impiega più tempo a caricare il file e a creare la matrice che ha trovare la soluzione.

mirco@Macintosh:Contest5> ruby contest-a.rb 
Matrice row:110, col:257, row_num:10, col_num:10, size:100
Tempo impiegato: (102.658109 secondi)
mirco@Macintosh:Contest5> ruby contest-b.rb 
best: 10, best_row:110, best_col:257]
Tempo impiegato: (2.076003 secondi)

[marco.r]

Originariamente inviato da VICIUS

Il pc su cui lo stavo provando non era proprio il massimo. Ora sul imac ci mette circa 170 secondi.


Se non ho capito male parti dall'angolo in basso a destra e calcoli la dimensione delle matrici. Poi percorri in senso inverso la matrice per trovare quella con dimensione maggiore? L'idea mi piace. Questa sera provo ad implementarla qui in ruby e faccio un piccolo confronto.

Si'. In realta' si puo' benissimo fare un'unica passata memorizzando man mano l'elemento migliore. Ma cosi' il codice mi sembrava un po' piu' chiaro.

[DanieleC88]

Un nuovo contest! Vedo di inventarmi qualcosa e poi provo a buttare giù qualche schifezza in C.

ciao

[gugoXX]

Per il punto 1 l'algoritmo che ho implementato e' identico alla soluzione di marco.r e 71104, ovvero O(N^2) con tempi sotto il secondo.

Per il punto 2, per ora sono ad uno schifosissimo O(N^2 * (N/2)(N/2))
ovvero O(N^4) ... pena...

[stdecden]

Ho risolto una cosa simile, che consisteva di cercare il cerchio con raggio piú ampio su una superfice dove sono presenti altri cerchi(senza sovrapposizioni) con un algoritmo genetico..., comunque la soluzione con questi algoritmi non é mai precisa al 100%, in alternativa si puó semplicemente usare la brute force...

[gugoXX]

Originariamente inviato da stdecden

Ho risolto una cosa simile, che consisteva di cercare il cerchio con raggio piú ampio su una superfice dove sono presenti altri cerchi(senza sovrapposizioni) con un algoritmo genetico..., comunque la soluzione con questi algoritmi non é mai precisa al 100%, in alternativa si puó semplicemente usare la brute force...

Pero' sono soluzioni che nella maggior parte dei casi sono piu' che sufficienti.

Se riuscissi a trovare un algoritmo greedy che dia risultati decenti in questo caso direi che sarebbe bene apprezzato.

[WarDuck]

Edit: scusate non avevo capito che c'erano i file di prova ora li scarico... è la prima volta che partecipo ad un contest

Edit2: faceva schifo l'ho tolto ghgh.

[DanieleC88]

Io ci provo. Ottengo questo risultato:

Lettura completata in 6430 millisecondi.
Inizio la ricerca...
Ricerca completata in 1760 millisecondi.

Sottomatrice quadrata di lato massimo:
	-> index: 110257
	-> side: 10

Devo stampare il sottoquadrato (257; 110)-(267; 120).
  0   0   0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0

Con il seguente codice C:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

typedef struct
{
	unsigned int index;
	size_t side;
}
coord_t;

int file_read(char *filename, int **matrix, size_t *side)
{
	size_t count = 0;
	FILE *fp = NULL;
	int rc = -1;

	fp = fopen(filename, "r");
	if (!fp)
	{
		return -1;
	}

	fscanf(fp, "--%u--\n", side);
	count = (*side);
	count *= count;
	(*matrix) = calloc(count, sizeof(int));

	if (*matrix)
	{
		int *matp = (*matrix);
		int x = 0;

		rc = 0;
		while (x++ < count)
		{
			fscanf(fp, "%d", matp++);
		}
	}

	fclose(fp);
	return rc;
}

coord_t *new_position(size_t index, size_t side)
{
	coord_t *ptr = (coord_t *) malloc(sizeof(coord_t));

	if (!ptr)
	{
		fprintf(stderr, " *** Chiamata a malloc() fallita! Mi arrendo.\n");
		exit(EXIT_FAILURE);
	}

	ptr->side = side;
	ptr->index = index;
	return ptr;
}

int check_column_and_row(int *column, int *row, size_t offset, size_t width)
{
	size_t off_y = 0;
	size_t off_x = 0;

	while (off_x < offset)
	{
		if ((column[off_y] != 0) || (row[off_x] != 0))
		{
			return -1;
		}

		off_y += width;
		++off_x;
	}
	return 0;
}

coord_t *test_submatrix(int *matrix, int x, int count, size_t max, size_t width)
{
	size_t col = (x % width);
	int *ptr = &matrix[x];
	size_t side = 1;

	if ((width - col) <= max)
	{
		return NULL;
	}

	while ((ptr[side] == 0) && (col + side <= width))
	{
		int *row = &ptr[side * width];
		int *column = &ptr[side];

		if ((row[side] != 0) || (check_column_and_row(column, row, side, width) != 0))
		{
			break;
		}

		++side;
	}

	if (side > max)
	{
		return new_position(x, side);
	}
	return NULL;
}

coord_t *find_submatrix(int *matrix, size_t side)
{
	size_t count = (side * side);
	coord_t *position = NULL;
	size_t max = 0;
	size_t x;

	for (x = 0; (x < count) && (max < (side - (x / side))); ++x)
	{
		coord_t *temp = NULL;

		if ((matrix[x] == 0) && (temp = test_submatrix(matrix, x, count, max, side)))
		{
			if (position)
			{
				free(position);
			}
			position = temp;

			max = position->side;
		}
	}
	return position;
}

int print_submatrix(int *matrix, size_t side, size_t x1, size_t x2, size_t y1, size_t y2)
{
	size_t x, y;

	printf("Devo stampare il sottoquadrato (%d; %d)-(%d; %d).\n", x1, y1, x2, y2);
	for (y = y1; y < y2; ++y)
	{
		int *row = &matrix[y * side];

		for (x = x1; x < x2; ++x)
		{
			if (x != x1)
			{
				printf(" ");
			}

			printf("%3d", row[x]);
		}
		printf("\n");
	}
	return 0;
}

int main(int argc, char *argv[])
{
	coord_t *position;
	size_t side;
	int *matrix;
	clock_t t1;
	clock_t t2;

	if (argc < 2)
	{
		fprintf(stderr, " *** Specifica il nome dei file, grazie. :)\n");
		return -1;
	}

	t1 = clock();
	if (file_read(argv[1], &matrix, &side) != 0)
	{
		fprintf(stderr, " *** Errore nella lettura di %s.\n", argv[1]);
		return -1;
	}
	t2 = clock();
	printf("Lettura completata in %d millisecondi.\n", (t2 - t1));

	printf("Inizio la ricerca...\n");
	t1 = clock();
	position = find_submatrix(matrix, side);
	t2 = clock();

	if (!position)
	{
		fprintf(stderr, " *** Sequenza non trovata.\n");
	}
	else
	{
		size_t x1, y1;
		size_t x2, y2;

		printf("Ricerca completata in %d millisecondi.\n", (t2 - t1));
		printf("\n");
		printf("Sottomatrice quadrata di lato massimo:\n");
		printf("\t-> index: %d\n", position->index);
		printf("\t-> side: %d\n", position->side);

		x1 = (position->index % side);
		x2 = (x1 + position->side);
		y1 = (position->index / side);
		y2 = (y1 + position->side);
		free(position);

		printf("\n");
		print_submatrix(matrix, side, x1, x2, y1, y2);
	}
	return 0;
}

So che la stampa del quadrato è superflua dal momento che sono tutti zeri, ma volevo la conferma della correttezza del codice. Il risultato mi pare buono, nonostante tutto: 1.7 secondi su questo catorcio che per il Contest 4 ci mette 13 minuti.

[VICIUS]

Ho fatto un po' di profiling sul codice e ho scoperto che la versione di ruby che sto usando non gradiva molto gli iteratori downto così ho riscritto il codice con dei normali cicli e sono riuscito a guadagnare tre decimi di secondo. A questo punto mi fermo qui con il primo pezzo.

mirco@Macintosh:Contest5> ruby contest-a.rb 
carico la matrice... fatto (1.136274 secondi)
trovo la sottomatrice... fatto (1.77516 secondi)
size:10  row:110  col:257

Per la seconda parte per ora ho provato solo con la forza bruta quindi algoritmo O(n^4). Ho anche qualche altra idea strana ma senza alcun fondamento che ha dato dei risultati piuttosto velocemente ma aspetto la conferma prima di postarli e fare un orrenda brutta figura

[VICIUS]

Originariamente inviato da DanieleC88

[...]
	t1 = clock();
	position = find_submatrix(matrix, side);
	t2 = clock();
[...]

Sei sicuro che il valore di ritorno di clock() sia in millisecondi? Perché sul mio pc il tuo programma dice di impiegarci 160.000 millisecondi mentre time è convinto che tutto termini in 0.220 secondi.

[Vincenzo1968]

Ho preso i tempi del codice di Daniele su questa macchina:

AMD Turion(tm) 64 X2 Mobile Technology TL-58 1.90 GHz
RAM: 3.00 GB
Sistema operativo: Windows Vista Home Premium - Service Pack 1

Ho modificato il codice in modo da fargli calcolare il tempo in secondi:

...
printf("Ricerca completata in %5.5f secondi.\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
...

Questi sono i risultati:

Lettura completata in 0.35100 secondi.
Inizio la ricerca...
Ricerca completata in 0.06400 secondi.

[DanieleC88]

Originariamente inviato da VICIUS

Sei sicuro che il valore di ritorno di clock() sia in millisecondi? Perché sul mio pc il tuo programma dice di impiegarci 160.000 millisecondi mentre time è convinto che tutto termini in 0.220 secondi.

In effetti ora mi metti il dubbio atroce. Ho appena controllato per sicurezza la pagina di manuale e, in effetti, leggo:

Originariamente inviato da http://linux.die.net/man/3/clock

Description
The clock() function returns an approximation of processor time used by the program.
Return Value
The value returned is the CPU time used so far as a clock_t; to get the number of seconds used, divide by CLOCKS_PER_SEC.

Quindi direi che il risultato più accurato è quello postato da Vincenzo.

[Vincenzo1968]

E il bello è che utilizzando un automa a stati finiti, al posto della scanf, si scende sotto il decimo di secondo anche per leggere la matrice dal file.
Se ti interessa, ti posto il codice(anche se i tempi di lettura dal file sono esclusi dall'esercizio).