[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]

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 :mbe: (forse e' colpa di ruby :p)
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]

Non ho capito molto il tuo algoritmo, ma a naso mi sembra strano che ci metta cosi' tanto :mbe: (forse e' colpa di ruby :p)
Il pc su cui lo stavo provando non era proprio il massimo. Ora sul imac ci mette circa 170 secondi.

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 :D

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 :D
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. :D
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]

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. :asd:

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]

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 :D

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. :D

[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 :D

[VICIUS]

[...]
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]

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:
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).

[DanieleC88]

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. ;)
:eek:
Cioè circa 3 volte più veloce? Cavoli, non pensavo che la scanf() avesse un tale impatto. :)

Come no, posta pure che è interessante. ;)

[DanieleC88]

Tra l'altro ho appena escogitato una possibile soluzione al secondo punto del problema, ma ho ancora un po' di dubbi sulla sua efficienza. Appena posso butto giù del codice e incrocio le dita. :D

[cdimauro]

:eek:
Cioè circa 3 volte più veloce? Cavoli, non pensavo che la scanf() avesse un tale impatto. :)
Mi sembra normale: scanf è una soluzione "generica", mentre l'automa a stati finiti è una soluzione "custom". ;)

[Vincenzo1968]

In ritardo(causa condivisione dell'unico portatile tra parenti e amici :cry: ) ma ecco il codice.

Nella macchina menzionata nel post precedente, impiega 0.02400 secondi.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1
} Stati;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, int **a, int array_size)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
num = 0;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
c = *(buffer + k++);
if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
c = *(buffer + k++);
x++;
}
else if ( c < '0' || c > '9' )
{
printf("Automa: Stato S0 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
num = (c - '0') * -1;
stato = S1;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= array_size)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' )
{
a[riga][colonna] = num;
num = 0;
colonna++;
stato = S0;
}
else if ( c == '-' )
{
k--;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int main()
{
clock_t c_start, c_end;

int x;
int **m;
int array_size;
Stati stato;

c_start = clock();

array_size = GetArraySize("matrix1.txt");
if ( array_size <= 0 )
return;

m = (int**)malloc(sizeof(int*)*array_size);
if ( m != NULL )
{
for ( x = 0; x < array_size; x++ )
{
m[x] = (int*)malloc(sizeof(int)*array_size);
if ( m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

stato = DFA("matrix1.txt", m, array_size);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return -1;
}

c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

printf("\ngli ultimi dieci elementi della matrice:\n");
for ( x = 989; x < 1000; x++ )
printf("m[999][%d] -> %d\n", x, m[999][x]);
printf("\n");

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return 0;
}


:)

[Vincenzo1968]

Tra l'altro ho appena escogitato una possibile soluzione al secondo punto del problema, ma ho ancora un po' di dubbi sulla sua efficienza. Appena posso butto giù del codice e incrocio le dita. :D

E io, non avendo intenzione di passare il resto delle ferie a programmare, vi leggo e faccio il tifo per te(e per il linguaggio C ;) ).

[cdimauro]

Tra l'altro ho appena escogitato una possibile soluzione al secondo punto del problema, ma ho ancora un po' di dubbi sulla sua efficienza. Appena posso butto giù del codice e incrocio le dita. :D
Puoi sempre modellare velocemente la soluzione, testarne la consistenza, e poi pensare a velocizzarla. :fiufiu:

[ercand]

Mi sembra normale: scanf è una soluzione "generica", mentre l'automa a stati finiti è una soluzione "custom". ;)

Salve a tutti, volevo partecipare ( o almeno provare:fagiano: ) ma vedo che voi siete anni luce avanti a me, ad esempio questo "automa a stati finiti" in cosa consiste?

Grazie.

[ndakota]

Salve a tutti, volevo partecipare ( o almeno provare:fagiano: ) ma vedo che voi siete anni luce avanti a me, ad esempio questo "automa a stati finiti" in cosa consiste?

Grazie.

lo stesso per me.. io in java mi sono bloccato al caricamento della matrice da file :D

[DanieleC88]

Mi sembra normale: scanf è una soluzione "generica", mentre l'automa a stati finiti è una soluzione "custom". ;)
Questo lo so, e infatti mi aspettavo che la lettura "manuale" fosse più rapida, però la scanf(), a parte l'interpretazione della stringa di formato, un cast e poco altro, cosa fa in più oltre a leggere il numero? Non mi aspettavo che ci impiegasse 3 volte (anzi, anche di più a vedere dal risultato che ha postato ora Vincenzo :D) il tempo normalmente necessario. :D
In ritardo(causa condivisione dell'unico portatile tra parenti e amici :cry: ) ma ecco il codice.

Nella macchina menzionata nel post precedente, impiega 0.02400 secondi.

[...]

:)
Mamma mia, sia per il risultato che per la quantità di codice: gugoXX ha ragione, devi essere un amanuense. :D
E io, non avendo intenzione di passare il resto delle ferie a programmare, vi leggo e faccio il tifo per te(e per il linguaggio C ;) ).
Grazie, proverò a fare del mio meglio ;)
Puoi sempre modellare velocemente la soluzione, testarne la consistenza, e poi pensare a velocizzarla. :fiufiu:
Ovvero... provarla in Python? :D
Be' sì, perché no? :)
Salve a tutti, volevo partecipare ( o almeno provare:fagiano: ) ma vedo che voi siete anni luce avanti a me, ad esempio questo "automa a stati finiti" in cosa consiste?

Grazie.
Tranquillo, posta la soluzione senza problemi (l'ultima soluzione che ho postato io ci metteva 13 minuti :D).

Un automa a stati finiti è un modello di macchina che reagisce a degli input portandosi da uno stato iniziale ad uno stato finale e dando determinati output (diversi a seconda degli stati di destinazione o delle transizioni effettuate). Almeno io è così che la conosco per quel poco che ho fatto, se vuoi maggiori dettagli su come implementarle in C rivolgiti a Vincenzo che saprà consigliarti letture utili. ;)

[Vincenzo1968]

Salve a tutti, volevo partecipare ( o almeno provare:fagiano: ) ma vedo che voi siete anni luce avanti a me, ad esempio questo "automa a stati finiti" in cosa consiste?

Grazie.

Ciao ercand,

come prima cosa volevo incoraggiarti(anzi, incoraggiarvi; l'invito è rivolto anche a ndakota) a partecipare ugualmente. L'accento è posto sugli algoritmi e non sulla velocità di esecuzione; non è detto quindi che il tuo algoritmo non possa risultare interessante.

Per quanto riguarda gli automi a stati finiti puoi vedere questo mio articolo (http://www.guidealgoritmi.it/ShowArticle.aspx?ID=6) e, se sei particolarmente interessato, ti consiglio caldamente questo libro:


John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
Automi, linguaggi e calcolabilità
ADDISON-WESLEY


Non lasciarti impressionare dalle definizioni matematiche. È più facile a farsi che a dirsi. Nel senso che, anche non possedendo elevate nozioni matematiche, l'implementazione di un automa a stati finiti è davvero molto semplice(se ci sono riuscito io col mio misero diploma di ragioniere...).

P.S.
ndakota, c,è un accenno agli automi a stati finiti anche sul Cormen(capitolo 32, 'string matching') ;)

[grigor91]

E' interessante notare come il mio futuro libro di sistemi riesca a trattare la macchina di Touring senza citare gli automi a stati finiti:rolleyes: :O

[NickerX]

La prima riga di ogni file indica la dimensione della matrice giusto?? :confused:
Quindi per il primo esercizio la matrice è 1000 * 1000 vero?? :confused:

Scusate le domande banali!! :fagiano:

[Vincenzo1968]

La prima riga di ogni file indica la dimensione della matrice giusto?? :confused:
Quindi per il primo esercizio la matrice è 1000 * 1000 vero?? :confused:
...


Ciao Nicher,

giusto, si. Si tratta di una matrice 1000x1000.


E' interessante notare come il mio futuro libro di sistemi riesca a trattare la macchina di Touring senza citare gli automi a stati finiti


Ciao Grigor,
si, è decisamente interessante!
Fammi sapere il titolo del libro quando esce(che evito di comprarlo).
Ho postato quel codice non perché voglia dimostrare chissà cosa, ma perché lo ritengo interessante. Anche se l'esercizio specifica che i tempi di lettura dal file non debbono rientrare nel computo, nella vita reale uno non si può presentare dal cliente e dirgli: "l'algoritmo di ricerca è velocissimo; tuttavia, il programma impiega mezz'ora di tempo a causa della lettura del file". :)

[ercand]

Per ho scritto il codice per memorizzare la matrice, questo è il codice

// Contest5.cpp : Defines the entry point for the console application.
//

#include <Windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <ctime>



#define SRCFILE "Matrix1.txt"
#define FILEBUFER 4096

int matrixSize = 1000;
char matrix[1000][1000];

bool OpenContestFile(char* pFileName)
{
char buffer[FILEBUFER + 1];

std::ifstream inputFile;
inputFile.open(pFileName);

if (inputFile.fail())
{
printf("Impossibile aprire il file %s", pFileName);
return false;
}


inputFile.getline(buffer, FILEBUFER, '\n');

/* int lenghtFirstLine = inputFile.tellg();

std::string textRecord;
textRecord.insert(0, buffer + 2, lenghtFirstLine - 4);
matrixSize = atoi(textRecord.c_str());*/
matrixSize = atoi(buffer+1);


// Legge tutti i valori della matrice
int Row = 0;
char* tempBuffer;

while (inputFile.eof() == false)
{
inputFile.getline(buffer, FILEBUFER, '\n');
tempBuffer = buffer;


for (int i = 0; i < matrixSize; i++)
{
matrix[Row][i] = atoi(tempBuffer);

while ((*tempBuffer >= '0' && *tempBuffer <= '9') || *tempBuffer == '-')
{
++tempBuffer;
}
// if (*tempBuffer == ' ' && *tempBuffer != '\n' && *tempBuffer != '\r')
{
++tempBuffer;
}
}
++Row;
}

inputFile.clear();
inputFile.close();

return true;
}
int main()
{
clock_t t1;
clock_t t2;

// Lettura file
t1 = clock();
bool staus = OpenContestFile(SRCFILE);
t2 = clock();

char text[512];
sprintf(text, "Lettura file completata in %5.5f secondi", float(t2-t1) / CLOCKS_PER_SEC);
OutputDebugStr(text);

return 0;
}



E' scritto con visual studio 2008, compilato in modalità release impiega tra i 0.04300 e i 0.05200 secondi a caricare la matrice.
Pensavo peggio:stordita: , son soddisfatto.

[gugoXX]

Provo a gettare una prima soluzione per il punto 2.
Completamente funzionale


Coordinate: 94,60 - Dimensione 55 - Somma 3185
Time: 8529ms
Test: 3185


Ho evidenziato in BLU il cuore, l'algoritmo di ricerca vero e proprio.


class Program
{
static void Main(string[] args)
{
Matrix mat = new Matrix("Matrix2.txt");
Stopwatch sw = new Stopwatch();
sw.Start();
var toprint = mat.Ex2();
sw.Stop();
Console.WriteLine("Coordinate: {0},{1} - Dimensione {2} - Somma {3}", toprint.Coords.x, toprint.Coords.y, toprint.Coords.z, toprint.val);
Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);

int x=toprint.Coords.x;
int y=toprint.Coords.y;
int z=toprint.Coords.z;

int test = (from yy in Enumerable.Range(y, z+1)
from xx in Enumerable.Range(x, z+1)
select mat.Mat[xx, yy]).Sum();
Console.WriteLine("Test: {0}", test);

Console.ReadKey();
}
}

public class Matrix
{
public int Dim;
public int[,] Mat;

public void Save(string fname)
{
StreamWriter sw = new StreamWriter(@"C:\temp\" + fname);
sw.WriteLine("--{0}--", Dim);
for (int y = 0; y < Dim; y++)
{
for (int x = 0; x < Dim; x++)
{
sw.Write("{0} ", Mat[x, y].ToString());
}
sw.WriteLine();
}
sw.Close();
}

public Matrix(string fname)
{
Load(fname);
}

public Matrix(int[,] vals)
{
Mat = vals;
Dim = vals.GetLength(0);
}

public void Load(string fname)
{
StreamReader sr = new StreamReader(@"C:\temp\" + fname);
string fline = sr.ReadLine();
string mds = fline.Substring(2, fline.Length - 4);
Dim = int.Parse(mds);
Mat = new int[Dim, Dim];
for (int y = 0; y < Dim; y++)
{
string line = sr.ReadLine();
string[] valss = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
var valis = valss.Select(t => int.Parse(t)).ToArray();
Enumerable.Range(0, Dim).ForAll(x => Mat[x, y] = valis[x]);
}
sr.Close();
}

public struct CoordsStruct
{
public int x;
public int y;
public int z;
public CoordsStruct(int ix, int iy, int iz)
{
x = ix;
y = iy;
z = iz;
}
}

public struct Ex2Result
{
public CoordsStruct Coords;
public int val;

public Ex2Result(CoordsStruct ics,int ival)
{
Coords = ics;
val = ival;
}
}

public Ex2Result Ex2()
{
int parsum = 0;
var domgrp = from y in Enumerable.Range(0, Dim)
from x in Enumerable.Range(0, Dim)
let min = Math.Min(Dim - y, Dim - x)
from z in Enumerable.Range(1, min - 1)
select new Ex2Result(
new CoordsStruct(x,y,z),
parsum = (z == 1 ? Mat[x, y] : parsum) + Mat[x + z, y + z] +
(from t in Enumerable.Range(0, z)
select Mat[x+t,y+z]+Mat[x+z,y+t]).Sum()
);

var orig = from y in Enumerable.Range(0, Dim)
from x in Enumerable.Range(0, Dim)
select new Ex2Result(new CoordsStruct(x, y, 0), Mat[x, y]);

var complete = domgrp.Concat(orig);

Ex2Result res = complete.Max(t => t.val);
return res;
}
}

public static class Extensor
{
public static void ForAll<T>(this IEnumerable<T> domain,Action<T> act)
{
foreach (T t in domain) act(t);
}

public static T Max<T, U>(this IEnumerable<T> domain, Func<T, U> elem) where U:IComparable<U>
{
T CurmaxRow = default(T);
U CurMax=default(U);
foreach (T t in domain)
{
U CurVal=elem(t);
if (CurVal.CompareTo(CurMax) > 0)
{
CurmaxRow = t;
CurMax = CurVal;
}
}
return CurmaxRow;
}
}

[cdimauro]

Questo lo so, e infatti mi aspettavo che la lettura "manuale" fosse più rapida, però la scanf(), a parte l'interpretazione della stringa di formato, un cast e poco altro, cosa fa in più oltre a leggere il numero? Non mi aspettavo che ci impiegasse 3 volte (anzi, anche di più a vedere dal risultato che ha postato ora Vincenzo :D) il tempo normalmente necessario. :D
Io sì e, anzi, pensavo si guadagnasse qualcosa di più.

Considera che un automa a stati finiti fa veramente "il minimo indispensabile", mentre la scanf ha numerosi controlli in più che esegue sempre. ;)
Ovvero... provarla in Python? :D
Matteo 26,25

"Tu l'hai detto."

:D
Be' sì, perché no? :)
"Make it work, make it right, make it fast" - Kent Beck

:cool:

[Vincenzo1968]

Ho snellito un po' il codice dell'automa con l'aggiunta di uno stato che rende più agevole la gestione dei numeri negativi:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, int **a, int array_size)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= array_size)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' )
{
a[riga][colonna] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int main()
{
clock_t c_start, c_end;

int x;
int **m;
int array_size;
Stati stato;
char *szFileName = "matrix1.txt";

c_start = clock();

array_size = GetArraySize(szFileName);
if ( array_size <= 0 )
return;

m = (int**)malloc(sizeof(int*)*array_size);
if ( m != NULL )
{
for ( x = 0; x < array_size; x++ )
{
m[x] = (int*)malloc(sizeof(int)*array_size);
if ( m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

//c_start = clock();

stato = DFA(szFileName, m, array_size);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}

c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

printf("\ngli ultimi dieci elementi della matrice:\n");
for ( x = array_size - 10; x < array_size; x++ )
printf("m[%d][%d] -> %d\n", array_size - 1, x, m[array_size - 1][x]);
printf("\n");

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return 0;
}

[DanieleC88]

E' interessante notare come il mio futuro libro di sistemi riesca a trattare la macchina di Touring senza citare gli automi a stati finiti:rolleyes: :O

Turing! :p

[DanieleC88]

Comunque alla fine ho tradotto in Python l'idea che avevo, ma sembra dannatamente lenta... :D
In fondo era solo un metodo "velocizzato" per analizzare tutti i possibili sottoquadrati, ma l'ho lanciato oltre venti minuti fa ed è ancora lì che gira, quindi non so se vale la pena di tradurlo anche in C: dubito di riuscire anche lontanamente a raggiungere gugoXX, pure su un computer serio. :)
Magari dopo provo a farlo lo stesso e vediamo che schifezza ne esce fuori.

ciao ;)

EDIT: come non detto, ha appena finito... :asd:
Ci ha messo appena 35 minuti. :stordita:
Lettura completata in 2500.54476273 millisecondi.
Caricata una matrice 200x200.
Inizio la ricerca... completata in 2115368.25458 millisecondi.

Risultato: posizione (94, 60) larghezza 56 somma 3185
Il codice è il seguente:
from time import clock

def read(filename):
f = open(filename)

list = []
first = f.readline()
side = int(first[2 : len(first)-3])
for line in f:
tmp = []
for w in line.split():
tmp.append(int(w))
list.append(tmp)
f.close()
return side, list

def sumrange(a, x1, y1, x2, y2):
s = 0
for y in xrange(y1, y2):
for x in xrange(x1, x2):
s += a[y][x]
return s

def contest5b(w, a):
max_side = 1
max_coord = (0, 0)
max_sum = 0

side = 1
while side <= w:
x = 0
while (x + side) <= w:
tmp = sumrange(a, x, 0, x + side, side)

if (tmp > max_sum):
max_coord = (x, 0)
max_side = side
max_sum = tmp

y = 0
while (y + side) < w:
for i in xrange(side):
tmp += (a[y+side][x+i] - a[y][x+i])

if (tmp > max_sum):
max_coord = (x, y+1)
max_side = side
max_sum = tmp
y += 1
x += 1
side += 1
return max_coord, max_side, max_sum

t1 = clock()
w, a = read("Matrix2.txt")
t2 = clock()
print "Lettura completata in", (t2-t1)*1000.0, "millisecondi."

print "Caricata una matrice %dx%d." % (w, w)
print "Inizio la ricerca...",
t1 = clock()
coord, side, sum = contest5b(w, a)
t2 = clock()
print "completata in", (t2-t1)*1000.0, "millisecondi."
print
print "Risultato: posizione", coord, "larghezza", side, "somma", sum

Considerando che il mio Contest 4 in Python ci ha messo 13 minuti sulla mia macchina e 38 secondi su quella di grigor91, questo mio Contest 5B dovrebbe impiegare sulla sua macchina la bellezza di 1 minuto e 42 secondi. Considerando anche che il Contest 4 tradotto in C sono riuscito a farlo scendere a 4 minuti su questo catorcio, sul PC di grigor91 il Contest 5B dovrebbe arrivare intorno a... 30 secondi. :asd:

[cdimauro]

Daniele, perché non provi Psyco (http://psyco.sourceforge.net/)?

Installalo, e all'inizio del tuo programma Python scrivi le seguenti 2 righe:
import psyco
psyco.full()
Eventualmente puoi anche disabilitare il garbage collector. In questo caso il codice di cui sopra diventa così:
import psyco, gc
psyco.full()
gc.disable()
Vedrai che con queste tre righe otterrai un buon miglioramento delle prestazioni. ;)

[grigor91]

Ciao Grigor, si, è decisamente interessante! Fammi sapere il titolo del libro quando esce(che evito di comprarlo). :) A dire la verità è gia uscito da 15 anni:D, ho detto futuro perchè sistemi ce l'ho da settembre.
comunque il titolo è :"Affrontare l'Informatica"
autori : Daniela Cappelletti Sandra Frigiolini Luigi Giacchetti
editore: Loescher
Turing! :p Ahh la fretta...:cry:

Ci ha messo appena 35 minuti. :stordita: Lettura completata in 2500.54476273 millisecondi. Caricata una matrice 200x200. Inizio la ricerca... completata in 2115368.25458 millisecondi. Risultato: posizione (94, 59) larghezza 56 somma 3185 Considerando che il mio Contest 4 in Python ci ha messo 13 minuti sulla mia macchina e 38 secondi su quella di grigor91, questo mio Contest 5B dovrebbe impiegare sulla sua macchina la bellezza di 1 minuto e 42 secondi. Considerando anche che il Contest 4 tradotto in C sono riuscito a farlo scendere a 4 minuti su questo catorcio, sul PC di grigor91 il Contest 5B dovrebbe arrivare intorno a... 30 secondi. :asd: perchè 200x200? mica era 1000x1000? comunque i miei risultati sono questi: Lettura completata in 120.084256519 millisecondi.Caricata una matrice 200x200. Inizio la ricerca... completata in 103166.230345 millisecondi. Risultato: posizione (94, 59) larghezza 56 somma 3185 Script terminated.
Con Psyco i risultati migliorano notevolmente:

Inizio la ricerca... completata in 5039.79835426 millisecondi.Risultato: posizione (94, 59) larghezza 56 somma 3185
Script terminated.
Senza GC i miglioramenti sono minimi:

Inizio la ricerca... completata in 4981.60464528 millisecondi.Risultato: posizione (94, 59) larghezza 56 somma 3185
Script terminated.

[cdimauro]

:eek: E' 20 volte più veloce!!! :p

[DanieleC88]

Lo metto subito a scaricare, anche se so che la maggior parte della colpa non è di Python, ma di questa anticaglia da cui vi scrivo. :D

Comunque visto che è interessante e poco invasivo, da quel che vedo, lo provo e poi rilancio il programma. :)

ciao ;)

[Tommo]

Bene. Mi ci sono messo un pò, e ora dichiaro a tutti voi il vostro PWNAGE! :sofico:

matrix loading, su matrix2.txt (200x200) funzionante richiede.......

3 millisecondi!

Chi ci riesce con phyton gli do la bambolina :D

Tuttavia c'ha solo un minimo problema, legge le cifre al contrario. Quando avrò tempo vedrò di fixarlo...

[DanieleC88]

:eek: E' 20 volte più veloce!!! :p
È davvero pazzesco, su questo stesso PC di prima mi ha ridotto il tempo di esecuzione da 35 minuti a 4 minuti! :eekk:

E dal momento che a grigor il tempo viene già così di 5 secondi, voglio provare una modifica che evita un pochino di cicli inutili. Se poi ho tempo lo traduco anche in C e vedo fin dove lo posso spingere. :D
matrix loading, su matrix2.txt (200x200) funzionante richiede.......

3 millisecondi!
EDIT: avevo capito male io... :stordita:

[DanieleC88]

Aggiornamento: ho spremuto ancora un po' il codice, da 4 minuti sono sceso a poco più di 2 minuti sulla mia macchina:
Lettura completata in 1204.76541679 millisecondi.
Caricata una matrice 200x200.
Inizio la ricerca... completata in 128279.977036 millisecondi.

Risultato: posizione (94, 60) larghezza 56 somma 3185
Se la velocità è raddoppiata anche sul PC di grigor91, sono intorno ai 2.6 secondi.
Psyco è davvero forte. :)

[WarDuck]

Ci siamo finalmente, sono stato un po' tardo, ma per il 1° punto sembra che tutto finalmente vada per il verso giusto.

Ecco il codice (ho escluso la parte del caricamento da file) in C#:

static int findSub(int[,] mat) {
int p = 0;
int next_i = 0;
int next_j = 0;
int max_i = 0;
int max_j = 0;
int max = 0;

for (int i = 0; i < dim - 1; i++) {
for (int j = 0; j < dim - 1; j++) {

if (mat[i, j] == 0) {
next_i = i;
next_j = j;
p = 1;
for (int k = p - 1; k >= 0 && k <= dim && i < dim - 1 && j < dim - 1; k--) {
if (mat[i - k, j + 1] == 0 && mat[i + 1, j - k] == 0) {
if (k == 0 && mat[i + 1, j + 1] == 0) {
i++;
j++;
k = ++p;
}
} else break;
}
i = next_i;
j = next_j;
if (p > max) {
max = p;
max_i = next_i;
max_j = next_j;
}
}
}
}
Console.WriteLine("Max dimension found: " + max + " at index (" + max_i + ", " + max_j + ")");
// viewMatrix(mat, max_i, max_j, max);
return max;
}

Ecco l'output:


Matrix dimensions: 1000
Max dimension found: 10 at index (110,257)
Elapsed: 26,7577ms

[VICIUS]

Giuro che questa è l'ultima versione del primo punto che posto. Tempo impiegato circa 1/3 della precedente :)
require 'tools'

def min(a,b,c)
a < b ? a < c ? a : c : b < c ? b : c
end

def contest5a(matrix)
best = best_row = best_col = 0

c = r = matrix.size - 1
while c >= 0 do
matrix[r][c] = matrix[r][c] == 0 ? 1 : 0
c -= 1
end

c = r = matrix.size-1
while r >= 0 do
matrix[r][c] = matrix[r][c] == 0 ? 1 : 0
r -= 1
end

c = r = matrix.size - 2
while r >= 0 do
while c >= 0 do
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
c -= 1
end
c = matrix.size - 2
r -= 1
end

return "best:#{best} row:#{best_row} col:#{best_col}"
end

test_function :contest5a, 'Matrix1.txt'
mirco@Macintosh:Contest5> ruby contest-a.rb
carico la matrice... fatto (1.064655 secondi)
trovo la sottomatrice... fatto (0.611063 secondi)
best:10 row:110 col:257

[VICIUS]

3 millisecondi!

Chi ci riesce con phyton gli do la bambolina :D

Tuttavia c'ha solo un minimo problema, legge le cifre al contrario. Quando avrò tempo vedrò di fixarlo...
require 'tools.rb'


start = Time.now()
matrix = fast_load_matrix()
puts "Carico la matrice.... ok. (" + (Time.now - start).to_s + " secondi)"
mirco@Macintosh:Contest5> ruby prova.rb
Carico la matrice.... ok. (0.000311 secondi)
Aspetto la bambolina :D

[DanieleC88]

Ah ma lui intendeva il solo caricamento! Pensavo la ricerca, LOL. :D

E comunque quello non è Python... :p

[VICIUS]

Ah ma lui intendeva il solo caricamento! Pensavo la ricerca, LOL. :D

E comunque quello non è Python... :p
Ruby è più lento di Python quindi la mia soluzione vale ancora di più. :p

[DanieleC88]

Giuro che questa è l'ultima versione del primo punto che posto. Tempo impiegato circa 1/3 della precedente :)
Solo un dubbio: sbaglio o modifichi la matrice? (è ammessa la modifica?)

[VICIUS]

Solo un dubbio: sbaglio o modifichi la matrice? (è ammessa la modifica?)
Penso di si. Al massimo si può allocare una matrice di appoggio su cui scrivere. La memoria richiesta raddoppia e le prestazioni ridursi di pochissimo per via di qualche cache miss in più.

[DanieleC88]

Portata in C anche la soluzione al secondo punto:
Lettura completata in 380 millisecondi.
Inizio la ricerca...
Ricerca completata in 21.42000 secondi.

Sottomatrice quadrata di somma massima:
-> index: 12094
-> side: 56
-> sum: 3185

Devo stampare il sottoquadrato (94; 60)-(150; 116).
[...]

Sul PC di grigor91 la versione Python, che da me impiegava 4 minuti, girava in 5 secondi, questa dovrebbe essere più veloce, anche considerando che al momento uso TCC come compilatore, quindi l'eseguibile non dovrebbe nemmeno essere ottimizzato.

Per comodità allego un file .zip con le soluzioni, postarle qui occuperebbe troppo spazio. :)

[banryu79]

Giuro che questa è l'ultima versione del primo punto che posto. Tempo impiegato circa 1/3 della precedente :)
[...cut...]

Bello è migliorata molto anche la "strutturazione" del codice e il suo valore estetico (almeno a me piace molto: non saprei bene come spiegarlo a parole però la sensazione che ho al colpo d'occhio è che ci sia una "bella ritmica". Certo questo non è direttamente correlato alla logica dell'algortimo, ed è soggettivo)
Bravo Vicius!

[Vincenzo1968]

http://www.guidealgoritmi.it/images/ImgForums/contest05b.jpg


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, int **a, int array_size)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= array_size)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' )
{
a[riga][colonna] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int main()
{
clock_t c_start, c_end;

int **m;
int x, y, k;
int array_size;
Stati stato;
char *szFileName = "matrix2.txt";

int riga, colonna;
int dim;
int somma;

int riga2, colonna2;

int riga_temp, colonna_temp;
int dim_temp;
int somma_temp;

c_start = clock();

array_size = GetArraySize(szFileName);
if ( array_size <= 0 )
return;

m = (int**)malloc(sizeof(int*)*array_size);
if ( m != NULL )
{
for ( x = 0; x < array_size; x++ )
{
m[x] = (int*)malloc(sizeof(int)*array_size);
if ( m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

stato = DFA(szFileName, m, array_size);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}

c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

c_start = clock();

x = y = 0;
while ( x < array_size - x && y < array_size - y )
{
somma = somma_temp = 0;
dim = array_size/2;
while ( dim > 1 )
{
for ( riga = y; riga <= y + dim; riga++ )
{
for ( colonna = x; colonna <= x + dim; colonna++ )
{
somma += m[riga][colonna];
}
if ( somma > somma_temp )
{
riga_temp = riga - dim;
colonna_temp = colonna - dim;
dim_temp = dim;
somma_temp = somma;
}
}
somma = 0;
--dim;
}
x++;
y++;
}

riga = riga_temp - 1;
colonna = colonna_temp - 1;
dim = dim_temp + 1;
k = 0;
somma = somma_temp;
while ( riga >= 0 )
{
y = riga--;
x = colonna--;

for ( k = 0; k < dim; k++ )
{
somma += m[y][x+(k+1)];

if ( somma > somma_temp )
{
riga_temp = riga;
colonna_temp = colonna;
dim_temp = dim;
somma_temp = somma;
}
}
dim++;
}

riga = riga_temp + 1;
colonna = colonna_temp + 1;
dim = dim_temp;
somma = 0;

for ( y = riga; y <= riga + dim; y++ )
{
for ( x = colonna; x <= colonna + dim; x++ )
{
somma += m[y][x];
}
}

if ( somma > somma_temp )
{
riga_temp = riga;
colonna_temp = colonna;
dim_temp = dim;
somma_temp = somma;
}

c_end = clock();

printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", riga_temp, colonna_temp, dim_temp, somma_temp);

printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return 0;
}


:D

[WarDuck]

Incredibile :eek: Complimenti Vincenzo... io ancora sto cercando di capire perché non funziona sulla matrice grande (o meglio non mi tornano i vostri risultati), con una matrice di prova 4x4 funziona (anche logicamente sembra) ma con quella da usare no.

In sostanza parto dall'origine (0,0) sommando tutti gli elementi della 2x2 dopodiché vi aggiungo quelli della 3x3, poi quelli della 4x4 e così via facendo sempre confronti col massimo attuale... poi cambio posizione (0,1), (0,2) e così via...

[DanieleC88]

http://www.guidealgoritmi.it/images/ImgForums/contest05b.jpg
Tu mi fai paura. :asd:

A parte scherzi, ottimo risultato. :)
Già che ci sei proveresti anche a lanciare la mia soluzione per il punto? Sono curioso di vedere quanto tempo impiega su un computer degno di tale nome. :D

ciao ;)

[DanieleC88]

Comunque, sbaglio io o la sottomatrice è 56x56, e non 55x55? Ho visto l'output stampato dal mio programma (che è 56x56) una volta terminata la ricerca e sommando i numeri mi viene effettivamente 3185... :boh:

[Tommo]

require 'tools.rb'


start = Time.now()
matrix = fast_load_matrix()
puts "Carico la matrice.... ok. (" + (Time.now - start).to_s + " secondi)"
mirco@Macintosh:Contest5> ruby prova.rb
Carico la matrice.... ok. (0.000311 secondi)
Aspetto la bambolina :D

"Ma questo è un mostro" (cit.) :D

Beh davvero complimenti... lo sospettavo che le versioni migliori sarebbero uscite più in là...
cmq come diavolo hai fatto? Io ho tolto qualsiasi cosa, cioè la conversione in float la faccio con un elenco di else if :sofico:
Dev'essere iostream che non è esattamente velocissimo. Magari una macchina a stati andrebbe di più. Peccato che non abbia idea di come si fa :doh:

Cmq niente bambolina, l'hai fatto in Ruby, non in Phyton :mc:

[WarDuck]

Finalmente ho concluso anche la seconda parte!!!

Ora via di ottimizzazione (la parte più divertente direi :sofico: ).

Ecco il codice (va ripulito):

static int findMaxSum(int[,] mat) {
int old_i;
int old_j;

int max = 0;
int max_i = 0;
int max_j = 0;
int p = 0;
int max_p = 0;

int dim = (int)Math.Sqrt(mat.Length);

for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
int sum = mat[i, j];
old_i = i;
old_j = j;
p = 1;
for (int k = p - 1; k >= 0 && i < dim - 1 && j < dim - 1; k--) {
sum = sum + mat[i - k, j + 1] + mat[i + 1, j - k];
if (k == 0) {
sum = sum + mat[i + 1, j + 1];
i++;
j++;
k = ++p;
if (sum > max) {
max = sum;
max_i = old_i;
max_j = old_j;
max_p = p;
}
}
}
i = old_i;
j = old_j;
}
}

Console.WriteLine("Max sum is " + max + " -> matrix "+max_p+"x"+max_p+" at index "+"("+max_i+","+max_j+")");
return max;
}

E l'output:
http://img359.imageshack.us/img359/3564/goodec2.jpg

[marco.r]

http://www.guidealgoritmi.it/images/ImgForums/contest05b.jpg
:D

Una risposta veloce non e' un buon sostituto di una risposta corretta :p.
Ho provato a sostituire in matrix2.txt 10000 nella prima casella in alto a sinistra il risultato del programma non cambia :mbe:, mentre dovrebbe quantomeno darmi come valore migliore da sottomatrice di dimensione 1 nella posizione (0,0).
Tra l'altro mi da un errore quando provo a leggere la seguente matrice

--2--
0 1
2 3

con errore

Automa: Stato S1 errore sul carattere -> '
'

ovvero trova un ritorno a capo che non gli piace... cosa sbaglio :confused:

[WarDuck]

Probabilmente il suo programma (così come il mio e penso pure quello degli altri) non tiene conto dei singoli elementi, ma cerca almeno una sottomatrice da 2.

[DanieleC88]

Probabilmente il suo programma (così come il mio e penso pure quello degli altri) non tiene conto dei singoli elementi, ma cerca almeno una sottomatrice da 2.
Ah ecco dov'era l'inghippo. :p

No, le mie soluzioni tengono sempre conto del caso generale, e quindi processano prima ogni singolo elemento, e poi le sottomatrici quadrate più larghe. :O

[WarDuck]

Ah ecco dov'era l'inghippo. :p

No, le mie soluzioni tengono sempre conto del caso generale, e quindi processano prima ogni singolo elemento, e poi le sottomatrici quadrate più larghe. :O

Si penso sia più giusto, ora modifico anche il mio affinché lo faccia...

Cmq sto pensando che almeno nel mio caso non dovrebbe influenzare molto il risultato, poiché si tratta solo di fare un confronto in più col massimo. I cicli restano gli stessi.

[gugoXX]

.

[Tommo]

Apposto ho finito la fase 1 dell'esercizio 2:

ecco il source... ho messo tutti e 3 i files (main, h e cpp) in una sola finestra perchè sennò diventava lunghissimo...

Cmq ho aggiunto una funzione precisa al millesimo (rippata spudoratamente dai samples di PhysX :D)per calcolare il tempo, e per aumentare ancora di piu' la precisione carico la matrice 20 volte e faccio la media dei tempi.

Il risultato così è di 0.00244625 secondi
magari senza usare iostream sarebbe piu rapido, ma non mi va :D



MAIN.CPP
#include "Matrix.h"

#include <iostream>
#include <time.h>
#include <windows.h>

using namespace std;

#ifdef __cplusplus
extern "C" {
#endif


double deltaTime()
{
double d;
#ifndef LINUX
static __int64 gTime,gLastTime;
__int64 freq;
QueryPerformanceCounter((LARGE_INTEGER *)&gTime); // Get current count
QueryPerformanceFrequency((LARGE_INTEGER *)&freq); // Get processor freq
d = (double)(gTime - gLastTime)/(double)freq;
gLastTime = gTime;
#else
struct timeval tv;
static struct timeval lasttv = { 0 , 0 };
if (lasttv.tv_usec == 0 && lasttv.tv_sec == 0)
gettimeofday(&lasttv, NULL);
gettimeofday(&tv, NULL);
d = (tv.tv_usec - lasttv.tv_usec)/1000000.f
+ (tv.tv_sec - lasttv.tv_sec);
lasttv = tv;
#endif
return d;
}

int main(int argc, char *argv[])
{
double delta;

//Creiamo il gioco con la configurazione specifica
Matrix* m = new Matrix( 200 );

//init
deltaTime();

//va fatto 20 volte e poi mediato
unsigned int rep = 20;

for(unsigned int i = 0; i < rep; ++i)
m->load( "Matrix2.txt" );
//delta
delta = deltaTime()/rep;


#ifdef _DEBUG
m->listNumbers();
#endif

cout << "Tempo impiegato per caricare: " << delta << " secondi!" << endl;

Matrix::MaxSum s = m->searchMaxSum();

std::cout << s.value << ", posizione:" << s.x << "," << s.y << endl << "dimensioni: " << s.sizeX << "," << s.sizeY;
return 0;
}

#ifdef __cplusplus
}
#endif



MATRIX.H

#include <string>

class Matrix
{
public:

struct MaxSum
{
float value;
unsigned int x, y, sizeX, sizeY;
};

Matrix( unsigned int declaredSide )
{
side = declaredSide;
//alloca l'indice
matrix = (float**)malloc( side*sizeof(float*) );

//alloca l'intera matrice
for( unsigned int i = 0; i < side; ++i)
matrix[i] = (float*)malloc( side*sizeof(float) );
}

~Matrix()
{
//dealloca l'intera matrice
for( unsigned int i = 0; i < side; ++i)
free( matrix[i] );

free(matrix);
}

void listNumbers();

void load( std::string path );

MaxSum searchMaxSum() { return sum; }

protected:
unsigned int side;

MaxSum sum;

float** matrix;
};

MATRIX.CPP

#include "matrix.h"

#include <fstream>
#include <iostream>

using namespace std;

typedef unsigned int uint;

void Matrix::load( string path )
{
uint chars;
char* buffer;

fstream f;

//apri e trova la lunghezza
f.open( path.c_str(), ios::in | ios::ate );
chars = f.tellg();
f.seekg(0);

//schiaffa tutto nel buffer
buffer = (char*)malloc(chars* sizeof(char));
f.read(buffer, chars);

//a questo punto si puo' convertire i caratteri in numeri
float number = 0;
uint digitIndex = 1;
uint digit;

int X = side-1;
int Y = side-1;

int i = chars-1;
for(; i != -1; i--)
{
if( buffer[i] == '-')
number *= -1;

//e' uno spazio, terminare e salvare

else if ( buffer[i] == ' ')
{
//salva nel buffer
matrix[Y][X] = number;

//scorri la matrice
X--;
if( X < 0 )
{
X = side-1;
Y--;
}

//e resetta
number = 0;
digitIndex = 1;
}
else
{
digit = 0;

if( buffer[i] == '1' ) digit = 1;
else if( buffer[i] == '2' ) digit = 2;
else if( buffer[i] == '3' ) digit = 3;
else if( buffer[i] == '4' ) digit = 4;
else if( buffer[i] == '5' ) digit = 5;
else if( buffer[i] == '6' ) digit = 6;
else if( buffer[i] == '7' ) digit = 7;
else if( buffer[i] == '8' ) digit = 8;
else if( buffer[i] == '9' ) digit = 9;
//una cifra, inserirla nel numero

number += digit * digitIndex;
digitIndex *= 10;
}
}
//salva nel buffer il primo numero, cioe' l'ultimo, prima del quale non c'e' lo spazio
matrix[0][0] = number;

free(buffer);
}

void Matrix::listNumbers()
{
{
for(unsigned int y = 0; y < side; ++y)
{
for(unsigned int x = 0; x < side; ++x)
std::cout << matrix[y][x] << " ";

std::cout << std::endl;
}
}
}

[marco.r]

Probabilmente il suo programma (così come il mio e penso pure quello degli altri) non tiene conto dei singoli elementi, ma cerca almeno una sottomatrice da 2.
Dovrebbe cmq tornarmi almeno la sottomatrice di dimensione 2 sita in (0,0) e con valore totale 10021. Probabilmente non e' solo quello.

Per inciso, se non e' chiedere troppo, proporrei che le soluzioni postate contengano un minimo di codice per farle funzionare (un main che carica la matrice ad esempio), in modo che gli altri che vogliono provarle possano farlo senza tanti sbattimenti (in modo simile a quello che hanno gia' fatto vincenzo e gugo, tanto per capirsi). Prometto che lo faro' anche io :D

[WarDuck]

Dovrebbe cmq tornarmi almeno la sottomatrice di dimensione 2 sita in (0,0) e con valore totale 10021. Probabilmente non e' solo quello.

Per inciso, se non e' chiedere troppo, proporrei che le soluzioni postate contengano un minimo di codice per farle funzionare (un main che carica la matrice ad esempio), in modo che gli altri che vogliono provarle possano farlo senza tanti sbattimenti (in modo simile a quello che hanno gia' fatto vincenzo e gugo, tanto per capirsi). Prometto che lo faro' anche io :D

Allora col codice che avevo postato, modificandolo per fargli controllare anche i singoli elementi, ti posso dire che a me viene:

Matrix dimensions: 200
Max sum is 11190 -> matrix 27x27 at index (0,0)
Elapsed: 1133,9412 milliseconds.

Questo mettendo 10000 al primo elemento (al posto del -42 iniziale):

(non l'ho testato a fondo quindi nn so se funziona esattamente)

Cmq ora sto lavorando su come ottimizzarlo usando 2 indici (si potrebbe fare a 4 partendo da ogni "vertice" della matrice ma è meglio provare prima con 2), facendo quindi più somme contemporaneamente, ma ancora non funge bene perchè si mangia 4 cicli non so dove (si ferma cioè prima del previsto).

Se ci riesco posto soluzione e main :D

[Vincenzo1968]

Già che ci sei proveresti anche a lanciare la mia soluzione per il punto? Sono curioso di vedere quanto tempo impiega su un computer degno di tale nome. :D

ciao ;)

http://www.guidealgoritmi.it/images/ImgForums/contest05b_daniele.jpg

:)

[Vincenzo1968]

Una risposta veloce non e' un buon sostituto di una risposta corretta :p.
Ho provato a sostituire in matrix2.txt 10000 nella prima casella in alto a sinistra il risultato del programma non cambia :mbe:, mentre dovrebbe quantomeno darmi come valore migliore da sottomatrice di dimensione 1 nella posizione (0,0).
Tra l'altro mi da un errore quando provo a leggere la seguente matrice

--2--
0 1
2 3

con errore

ovvero trova un ritorno a capo che non gli piace... cosa sbaglio :confused:

Vedo(spero presto :cry: ) di trovare il bug.
Per il secondo problema, l'automa assume che i numeri siano separati da uno spazio, compreso l'ultimo. Si può facilmente modificare in modo che l'ultimo numero sia separato, indifferentemente, da uno spazio o da un newline.

[DanieleC88]

http://www.guidealgoritmi.it/images/ImgForums/contest05b_daniele.jpg

:)
Grazie ;)

Cavoli mi batti di oltre 10 volte... Mi arrendo! :D

[WarDuck]

Che computer hai vincenzo, per curiosità? :D

[Vincenzo1968]

Grazie ;)

Cavoli mi batti di oltre 10 volte... Mi arrendo! :D

No, non ti batto per niente. Il codice che ho postato è velocissimo in certi casi ma, in altri, dà dei risultati del tutto sballati.

Ciao WarDuck,

il computer è questo:


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

[WarDuck]

Chiaro ;)

[gugoXX]

650ms in C#
E ho pure usato il crivello di Eratostene per calcolare i numeri primi (e il divisore piu' grande di ciascuno dei compositi).
La parte in blu e' sempre l'algoritmo principale.
Provero' a mettere il parallelismo, per vedere cosa succede, anche se e' difficile inserirlo efficientemente.

La versione funzionale e' sempre li' sotto, giusto come paragone (Scesa a 6 secondi, ma effettivamente non paragonabile)

Ora, fatto salvo che per testare eventuali differenze algoritmiche dobbiamo scalare piu' in alto,
a nessuno e' venuto in mente o ha provato a risolvere il problema con un algoritmo greedy?
Gli algoritmi greedy non hanno la pretesa di fornire il risultato migliore. Ne forniscono uno molto buono, ma sono in genere velocissimi. Idee?


Coordinate: 94,60 - Dimensione 55 - Somma 3185
Time: 657ms
Test: 3185



class Program
{
static void Main(string[] args)
{
//int[,] vals = Randomizer.GetRandom2(10);
//Matrix mat = new Matrix(vals);
Stopwatch sw = new Stopwatch();
sw.Start();
Matrix mat = new Matrix("Matrix2.txt");
long ll = sw.ElapsedMilliseconds;
sw.Reset();
sw.Start();
var toprint = mat.Ex4();
sw.Stop();
Console.WriteLine("Coordinate: {0},{1} - Dimensione {2} - Somma {3}", toprint.Coords.x, toprint.Coords.y, toprint.Coords.z, toprint.val);
Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);

int x=toprint.Coords.x;
int y=toprint.Coords.y;
int z=toprint.Coords.z;

int test = (from yy in Enumerable.Range(y, z+1)
from xx in Enumerable.Range(x, z+1)
select mat.Mat[xx, yy]).Sum();
Console.WriteLine("Test: {0}", test);

Console.ReadKey();
}
}

public class Matrix
{
public int Dim;
public int[,] Mat;

public void Save(string fname)
{
StreamWriter sw = new StreamWriter(@"C:\temp\" + fname);
sw.WriteLine("--{0}--", Dim);
for (int y = 0; y < Dim; y++)
{
for (int x = 0; x < Dim; x++)
{
sw.Write("{0} ", Mat[x, y].ToString());
}
sw.WriteLine();
}
sw.Close();
}

public Matrix(string fname)
{
Load(fname);
}

public Matrix(int[,] vals)
{
Mat = vals;
Dim = vals.GetLength(0);
}

public void Load(string fname)
{
StreamReader sr = new StreamReader(@"C:\temp\" + fname);
string fline = sr.ReadLine();
string mds = fline.Substring(2, fline.Length - 4);
Dim = int.Parse(mds);
Mat = new int[Dim, Dim];
for (int y = 0; y < Dim; y++)
{
string line = sr.ReadLine();
string[] valss = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
var valis = valss.Select(t => int.Parse(t)).ToArray();
Enumerable.Range(0, Dim).ForAll(x => Mat[x, y] = valis[x]);
}
sr.Close();
}

public struct CoordsStruct
{
public int x;
public int y;
public int z;
public CoordsStruct(int ix, int iy, int iz)
{
x = ix;
y = iy;
z = iz;
}
}

public struct Ex2Result
{
public CoordsStruct Coords;
public int val;

public Ex2Result(CoordsStruct ics,int ival)
{
Coords = ics;
val = ival;
}
}

public Ex2Result Ex4()
{
int[,][] Compl = new int[Dim, Dim][];
for (int y = 0; y < Dim; y++)
{
for (int x = 0; x < Dim; x++)
{
int mxy = Dim - ((x > y) ? x : y);
int[] st = Compl[x, y] = new int[mxy];
st[0] = Mat[x, y];
if (mxy > 1) st[1] = Mat[x, y] + Mat[x, y + 1] + Mat[x + 1, y] + Mat[x + 1, y + 1];
}
}

int[] Eratost = Eratostene();

Ex2Result rer = new Ex2Result();
int rerval = int.MinValue;
for (int z = 2; z < Dim; z++)
{
int era = Eratost[z + 1];
for(int y=0;y<Dim;y++)
{
for (int x = 0; x < Dim; x++)
{
int mxy = Dim - ((x > y) ? x : y);
if (z < mxy)
{
int[] ToCalc = Compl[x, y];

int cur;
if (era == -1)
{
//OldStyle se e' primo
int sum = ToCalc[z - 1];
for (int u = 0; u < z; u++)
{
sum += Mat[x + u, y + z] + Mat[x + z, y + u];
}
cur = sum + Mat[x + z, y + z];
}
else
{
//NewStyle se e' composito
int div = (z + 1) / era;
int divm1 = era - 1;
int divdivm1 = div * divm1;
int ydivdivm1 = y + divdivm1;
int xdivdivm1 = x + divdivm1;
int sum = ToCalc[divdivm1 - 1];
int divmm1 = div - 1;
for (int u = 0, xu=x,yu=y; u < divm1; u++, xu+=div, yu+=div)
{
int s1 = Compl[xu, ydivdivm1][divmm1];
int s2 = Compl[xdivdivm1, yu][divmm1];
sum += s1 + s2;
}
int s3 = Compl[xdivdivm1, ydivdivm1][divmm1];
cur = sum + s3;
}
ToCalc[z] = cur;
if (cur > rerval)
{
rer=new Ex2Result(new CoordsStruct(x, y, z), cur);
rerval = cur;
}
}
else break;
}
}
}
return rer;
}

private int[] Eratostene()
{
int[] ret = new int[Dim+1];
int ms=((int)Math.Sqrt(Dim))+1;
int t;
for (t = 2; t < ms; t++)
{
if (ret[t] == 0)
{
ret[t] = -1;
for (int u = t+t; u <= Dim; u += t)
{
if (ret[u]==0) ret[u] = t;
}
}
}
for (; t <= Dim; t++)
{
if (ret[t] == 0) ret[t] = -1;
}
return ret;
}
public Ex2Result Ex2()
{
int parsum = 0;
var domgrp = from y in Enumerable.Range(0, Dim)
from x in Enumerable.Range(0, Dim)
let min = Math.Min(Dim - y, Dim - x)
from z in Enumerable.Range(1, min - 1)
select new Ex2Result(
new CoordsStruct(x, y, z),
parsum = (z == 1 ? Mat[x, y] : parsum) + Mat[x + z, y + z] +
(from t in Enumerable.Range(0, z)
select Mat[x + t, y + z] + Mat[x + z, y + t]).Sum()
);

var orig = from y in Enumerable.Range(0, Dim)
from x in Enumerable.Range(0, Dim)
select new Ex2Result(new CoordsStruct(x, y, 0), Mat[x, y]);

var complete = domgrp.Concat(orig);

Ex2Result res = complete.Max(t => t.val);
return res;
}
}

[DanieleC88]

Non li conosco nemmeno di nome... nessuna idea al riguardo. :boh:

[Vincenzo1968]

Ho risolto(grazie a Fibonacci ;) ):

http://www.guidealgoritmi.it/images/ImgForums/contest5b_1.jpg

Col valore 10000 al posto del primo numero(-42):
http://www.guidealgoritmi.it/images/ImgForums/contest5b_2.jpg

Adesso è molto più lento ma sembra funzionare bene(ho provato con l'inserimento del valore 10000 in più punti del file).
Ho sistemato anche l'automa in modo da fargli accettare il carattere di ritorno a capo per l'ultimo numero della riga.



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, int **a, int array_size)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= array_size)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
a[riga][colonna] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int main()
{
clock_t c_start, c_end;

int **m;
int x, y, k;
int array_size;
Stati stato;
char *szFileName = "matrix2.txt";

int riga, colonna;
int dim;
int somma;

int riga_temp, colonna_temp;
int dim_temp;
int somma_temp;

int fibDim = 10;

int Fibonacci[] = {2,3,5,8,13,21,34,55,89,144};

c_start = clock();

array_size = GetArraySize(szFileName);
if ( array_size <= 0 )
return;

m = (int**)malloc(sizeof(int*)*array_size);
if ( m != NULL )
{
for ( x = 0; x < array_size; x++ )
{
m[x] = (int*)malloc(sizeof(int)*array_size);
if ( m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

stato = DFA(szFileName, m, array_size);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}

c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

c_start = clock();

if ( array_size == 1 )
{
c_end = clock();
printf("\nRiga -> 0\nColonna -> 0\nDimensione -> 1\nSomma -> %d\n", m[0][0]);
printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);
return 0;
}
else if ( array_size == 2 )
{
riga = colonna = 0;
dim = 1;
somma = m[riga][colonna];
colonna++;
if ( m[riga][colonna] > somma )
somma = m[0][1];
colonna = 0;
riga++;
if ( m[riga][colonna] > somma )
somma = m[riga][colonna];
colonna++;
if ( m[riga][colonna] > somma )
somma = m[1][1];

if ( m[0][0] + m[0][1] + m[1][0] + m[1][1] > somma )
{
dim = 2;
riga = 0;
colonna = 0;

somma = m[0][0] + m[0][1] + m[1][0] + m[1][1];
}

c_end = clock();
printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", riga, colonna, dim, somma);
printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);
return 0;
}

somma_temp = m[0][0] + m[0][1];
riga_temp = 0;
colonna_temp = 0;
dim_temp = 2;

for ( k = 0; k < fibDim; k++ )
{
dim = Fibonacci[k];
x = y = 0;
riga = colonna = 0;
somma = 0;
for ( riga = 0; riga <= array_size - dim; riga++ )
{
for ( colonna = 0; colonna <= array_size - dim; colonna++ )
{
for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
somma += m[y][x];
}
}
if ( somma > somma_temp )
{
somma_temp = somma;
riga_temp = riga;
colonna_temp = colonna;
dim_temp = dim;
}
x = y = 0;
somma = 0;
}
}
}

dim = dim_temp + 1;
colonna = colonna_temp;
while ( dim < array_size - dim )
{
x = y = 0;

riga = riga_temp - 1;
if ( riga < 0 )
riga = 0;

somma = 0;

if ( riga + dim > array_size - 1 )
break;
if ( colonna + dim > array_size - 1 )
break;

for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
somma += m[y][x];
}
}
if ( somma > somma_temp )
{
somma_temp = somma;
riga_temp = riga;
colonna_temp = colonna;
dim_temp = dim;
}

dim++;
}

c_end = clock();

printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", riga_temp, colonna_temp, dim_temp, somma_temp);

printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return 0;
}

[Vincenzo1968]

650ms in C#
E ho pure usato il crivello di Eratostene per calcolare i numeri primi (e il divisore piu' grande di ciascuno dei compositi).
La parte in blu e' sempre l'algoritmo principale.
Provero' a mettere il parallelismo, per vedere cosa succede, anche se e' difficile inserirlo efficientemente.

La versione funzionale e' sempre li' sotto, giusto come paragone (Scesa a 6 secondi, ma effettivamente non paragonabile)
...


Ciao Gugo,

intanto grazie per le nottate(e, per giunta, in ferie) passate a programmare per i tuoi contest(ovviamente, scherzo ;) , quella dei contest la trovo un'idea fantastica).

Ho provato a compilare il tuo codice ma ho questo errore:


'System.Collections.Generic.IEnumerable<int>' non contiene
una definizione di 'ForAll' e non è stato trovato alcun metodo
di estensione 'ForAll'che accetta un primo argomento di tipo
'System.Collections.Generic.IEnumerable<int>'.
Probabilmente manca una direttiva using o un riferimento a un assembly.


che direttive debbo usare?

[cdimauro]

La direttiva 4. :Perfido:

[gugoXX]

Ciao Gugo,

intanto grazie per le nottate(e, per giunta, in ferie) passate a programmare per i tuoi contest(ovviamente, scherzo ;) , quella dei contest la trovo un'idea fantastica).

Ho provato a compilare il tuo codice ma ho questo errore:


Eheh. Mi fa piacere che interessino.

Per l'errore hai ragione, aggiungo qui il codice che manca.
Il problema e' che nelle mie soluzioni divido tutto in classi e file diversi, e poi ad appendere tutto insieme in un'unico testo talvolta si dimentica qualcosa.


public static class Extensor
{
public static void ForAll<T>(this IEnumerable<T> domain,Action<T> act)
{
foreach (T t in domain) act(t);
}

public static T Max<T, U>(this IEnumerable<T> domain, Func<T, U> elem) where U:IComparable<U>
{
T CurmaxRow = default(T);
U CurMax=default(U);
foreach (T t in domain)
{
U CurVal=elem(t);
if ((CurVal.CompareTo(CurMax) > 0)||(CurMax.CompareTo(default(U))==0))
{
CurmaxRow = t;
CurMax = CurVal;
}
}
return CurmaxRow;
}
}

[Vincenzo1968]

La direttiva 4. :Perfido:

:confused:

[Vincenzo1968]

Eheh. Mi fa piacere che interessino.

Per l'errore hai ragione, aggiungo qui il codice che manca.
Il problema e' che nelle mie soluzioni divido tutto in classi e file diversi, e poi ad appendere tutto insieme in un'unico testo talvolta si dimentica qualcosa.


public static class Extensor
{
public static void ForAll<T>(this IEnumerable<T> domain,Action<T> act)
{
foreach (T t in domain) act(t);
}

public static T Max<T, U>(this IEnumerable<T> domain, Func<T, U> elem) where U:IComparable<U>
{
T CurmaxRow = default(T);
U CurMax=default(U);
foreach (T t in domain)
{
U CurVal=elem(t);
if ((CurVal.CompareTo(CurMax) > 0)||(CurMax.CompareTo(default(U))==0))
{
CurmaxRow = t;
CurMax = CurVal;
}
}
return CurmaxRow;
}
}


Grazie mille :)

[cdimauro]

:confused:
http://iconsoffright.com/news/robocop.jpg

[marco.r]

Ho risolto(grazie a Fibonacci ;) ):

http://www.guidealgoritmi.it/images/ImgForums/contest5b_1.jpg

Col valore 10000 al posto del primo numero(-42):
http://www.guidealgoritmi.it/images/ImgForums/contest5b_2.jpg

Adesso è molto più lento ma sembra funzionare bene(ho provato con l'inserimento del valore 10000 in più punti del file).
Ho sistemato anche l'automa in modo da fargli accettare il carattere di ritorno a capo per l'ultimo numero della riga.

Continua a non tornarmi qualcosa :confused: ad esempio con la seguente matrice in alto a sinistra

10000 1000 1000 1000 1000 14000 -80000
1000 1000 1000 1000 -2100 -45 44
1000 1000 1000 1000 -3700 -13 -46
1000 19 -2 -3 8 -27 46
47 6 -31 6 -4 -44 -13
31 30 27 36 -18 30 25

mi ritorna come matrice migliore la 5x5 che comincia in riga 0 colonna 1, mentre mi sembra dovrebbe la 6x6 che comincia in (0,0)
Piu' in generale non mi e' chiaro l'algoritmo che avete scelto (a naso il tuo e di gugo sembrano simili). Da quel che sembra partite calcolando solo le sottomatrici di una dimensione prefissata (secondo i numeri primi piuttosto che la serie di fibonacci), ma non mi e' affatto chiaro come poi calcoliate quelle di dimensione rimanente :mbe:

[gugoXX]

Continua a non tornarmi qualcosa :confused: ad esempio con la seguente matrice in alto a sinistra

10000 1000 1000 1000 1000 14000 -80000
1000 1000 1000 1000 -2100 -45 44
1000 1000 1000 1000 -3700 -13 -46
1000 19 -2 -3 8 -27 46
47 6 -31 6 -4 -44 -13
31 30 27 36 -18 30 25

mi ritorna come matrice migliore la 5x5 che comincia in riga 0 colonna 1, mentre mi sembra dovrebbe la 6x6 che comincia in (0,0)
Piu' in generale non mi e' chiaro l'algoritmo che avete scelto (a naso il tuo e di gugo sembrano simili). Da quel che sembra partite calcolando solo le sottomatrici di una dimensione prefissata (secondo i numeri primi piuttosto che la serie di fibonacci), ma non mi e' affatto chiaro come poi calcoliate quelle di dimensione rimanente :mbe:

Ciao
Il mio risultato per questi dati e'

Coordinate: 0,0 - Dimensione 5 - Somma 31253
Time: 1ms
Test: 31253

Fatto salvo che in realta' 5 e' geometricamente 6, e che forse dovrei cambiare almeno l'ouput, confermo che il risultato migliore e' quello da te proposto, e la somma totale ne e' la prova.
Dimensione 0 per me era il singolo elemento.

Il mio algoritmo e' semplice. Partendo dalle matrici di dimensione 0 (che sarebbe 1), ovvero i singoli elementi, calcolo le matrici successive di dimensione maggiore.
Per ciascuna coordinata associo e calcolo la somma di tutte le matrici che hanno come punto inziale proprio quella coordinata.
Per calcolare una matrice di dimensione 17 per esempio parto dalla matrice di dimensione 16, e ci sommo tutti gli elmenti della nuova riga (in basso) e della nuova colonna (a destra), ovvero 16+16+1 somme.
Per passare da 199 a 200 invece le somme sarebbero 199+199+1
Pero' ho trovato una semplificazione: Per passare p.es da 199 a 200, ho scelto di prendere le sottomatrici di dimensione 100 e sommarle fra di loro.
In pratica 4 somme.
L'importante e' avere le sottomatrici di dimensione inferiore gia' tutte calcolate e disponibili.

Quindi, per le matrici di dimensione pari ad un numero primo procedo come prima.
Per le matrici di dimensione composita (es:21), avendo calcolato il piu' piccolo (e il piu' grande) fattore primo, procedo con le somme delle sottomatrici gia' calcolate.
Per 21 = 7*3, parto dalla sottomatrice di dimensione 7*2 = 14
e ci sommo le sottomatrici di dimensione 3 dell'ultima rigona dell'ultima colonnona, che sono 6+6+1
contro 20+20+1 somme del caso dei numeri primi.

[marco.r]

Ah ok, ora ho capito la tua soluzione. Avevo abbozzato una soluzione analoga, ma non mi piaceva l'idea di tenere un sacco di matrici per le soluzioni temporanee. In effetti pero' se uno tiene solo quelle relative alle dimensioni prime diventa una cosa molto buona.

[WarDuck]

Io faccio tutto in loco, praticamente partendo dal vertice (i,j) imposto il primo elemento come somma, dopodiché vi aggiungo i rimanenti elementi di profondità 1 (quindi di dimensione p+1) dopo di profondità 2, 3 e così via...

a b e
c d f
g h i

Dimensione 1
faccio somma = a;

Dimensione 2
poi somma = somma + b + c
poi somma = somma + d;

Dimensione 3
poi somma = somma + e + g;
poi somma = somma + f + h;
poi somma = somma + i;

Poi per ogni elemento in posizione i,j mi calcolo tutte le sottomatrici possibili aggiornando quando c'è bisogno il massimo, la posizione e la dimensione.

Il risultato non è malaccio, sulla matrice di 200 elementi ci metto mediamente 950ms circa.

Ho provato ad usare 2 (4) indici per scorrere contemporaneamente la matrice in 2 sensi (faccio 2 somme di matrici per volta), ma ho notato che non ci vogliono dim/2 passi come supponevo ma un po' di più :( Questo poiché ci sono alcune matrici incrociate che non vengono calcolate e tra le altre cose ho notato che non si può scomporre questo problema più di tanto in sottoproblemi uguali.

[DanieleC88]

Io faccio qualcosa di simile a WarDuck: prendo il primo elemento come somma massima di larghezza 1 e ripeto fino a raggiungere la larghezza uguale all'intera matrice: per ogni larghezza effettuo due cicli; quello più interno aggiunge "larghezza" elementi dalla prossima riga e sottrae altrettanti elementi dalla riga precedente, aggiornando il massimo se necessario. Questo viene ripetuto per ogni colonna dove, allo stesso modo, aggiungo solo i nuovi elementi dalla prossima colonna e sottraggo quelli sulla prima colonna, e così via per ogni larghezza e per tutta la matrice. Ad ogni nuova larghezza aggiungo solo gli elementi che non erano già memorizzati all'inizio del primo ciclo. :)

[ercand]

Non ero sparito:p , ho concluso il primo punto dell'esercizio
#include <Windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <ctime>

#define SRCFILE "Matrix1.txt"
#define FILEBUFER 4096

int matrixSize = 1000;
char matrix[1000][1000];
char readingBuffer[FILEBUFER + 1];
std::ifstream inputFile;

//
void OpenContestFile2(char* pFileName)
{
int value = 0;

// Apre il file alla fine
inputFile.open(pFileName, std::ios_base::ate);

// Dimensione del file in byte
unsigned int FileLength = 0;
FileLength = inputFile.tellg();
inputFile.seekg(2, std::ios_base::beg);


char* pCharBuffer = new char[FileLength + 1];
inputFile.read(pCharBuffer, FileLength);

char* tempBuffer = pCharBuffer;

// Record della matrice
while ( 1 )
{
if ( *tempBuffer < '0')// || *tempBuffer > '9' )
break;

value = ( value * 10 ) + ( *tempBuffer - '0' );
++tempBuffer;
}
matrixSize = value;
tempBuffer = tempBuffer + 3; // 2 volte per il -- e una volta per il carattere '\n'

// Legge tutti i valori della matrice
int Row = 0;
char* tempMatrix = matrix[0];

while (Row < matrixSize)
{
tempMatrix = matrix[Row];

for (int i = 0; i < matrixSize; ++i)
{
value = 0;

if (*tempBuffer == '-')
{
++tempBuffer;
while ( 1 )
{
if ( *tempBuffer < '0')// || *tempBuffer > '9' )
break;

value = ( value * 10 ) + ( *tempBuffer - '0' );
++tempBuffer;
}
tempMatrix[i] = -value;
}
else
{
while ( 1 )
{
if ( *tempBuffer < '0')// || *tempBuffer > '9' )
break;

value = ( value * 10 ) + ( *tempBuffer - '0' );
++tempBuffer;
}
tempMatrix[i] = value;
}
// Salta lo spazio tra due numeri
++tempBuffer;
}
++tempBuffer;
++Row;
}
delete[] pCharBuffer;
inputFile.close();
}

//
int FindMaxSubMatrix(int* pRiga, int* pColonna)
{
int MaxSubMatrix = 0;
for (int i = 0; i < matrixSize; ++i)
{
for (int j = 0; j < matrixSize; ++j)
{
if (matrix[i][j] == 0)
{
int next = 1;
int sizeFound = 0;

bool isValid = true;
bool exitWhile = false;
bool checkInternal = true;

while (matrix[i][j + next] == 0 && matrix[i + next][j] == 0 && exitWhile == false && next < matrixSize-i && next < matrixSize-j)
{
if (next > MaxSubMatrix)
{
// Se sono già stati controllati gli zero interni allora controlliamo solo quelli lungo i bordi
if (checkInternal == false)
{
for (int toTry = 1; toTry <= next; ++toTry)
{
if (matrix[i + next][j + toTry] != 0 || matrix[i + toTry][j + next] != 0)
{
isValid = false;
exitWhile = true;
break;
}
}
}
else
{
for (int RowCheck = 1; RowCheck <= next; ++RowCheck)
{
for (int ColCheck = 1; ColCheck <= next; ++ColCheck)
{
if (matrix[i + RowCheck][j + ColCheck] != 0)
{
exitWhile = true;
isValid = false;
RowCheck = matrixSize + 1;
break;
}
}
}
checkInternal = false;
}
if (isValid == true)
{
sizeFound = next;
}
}
++next;
}

// Controlla se questa matrice è più grande dell'ultima
if (sizeFound > MaxSubMatrix)
{
MaxSubMatrix = next;
(*pColonna) = j;
(*pRiga) = i;
}
}
}
}

// Togliere 1 unità
return MaxSubMatrix - 1;
}
int main()
{
LARGE_INTEGER frequency;
LARGE_INTEGER time1;
LARGE_INTEGER time2;
QueryPerformanceFrequency(&frequency);
QueryPerformanceCounter(&time1);
QueryPerformanceCounter(&time2);


// Lettura file
QueryPerformanceCounter(&time1);
OpenContestFile2(SRCFILE);
QueryPerformanceCounter(&time2);

double readTime = ((double)(time2.QuadPart - time1.QuadPart)) / frequency.QuadPart;
char text[512];
sprintf(text, "Lettura file completata in: %5.5f secondi\n", readTime);
OutputDebugStr(text);

// Cerca la matrice più grande
int Riga;
int Colonna;
QueryPerformanceCounter(&time1);
int maxSubMatrix = FindMaxSubMatrix(&Riga, &Colonna);
QueryPerformanceCounter(&time2);
readTime = ((double)(time2.QuadPart - time1.QuadPart)) / frequency.QuadPart;
sprintf(text, "Ricerca sub-matrice più ampia trovata\nRiga:%d\nColonna:%d\nLa dimensione è:%d. Tempo impiegato: %5.5f secondi\n", Riga, Colonna, maxSubMatrix, readTime);
OutputDebugStr(text);

return 0;
}


Questo è il risultato (intel a 2.0giga)

Lettura file completata in: 0.01914 secondi
Ricerca sub-matrice più ampia trovata
Riga:110
Colonna:257
La dimensione è:10. Tempo impiegato: 0.01976 secondi

Va bene come risultato?

[Vincenzo1968]

Continua a non tornarmi qualcosa :confused: ad esempio con la seguente matrice in alto a sinistra

10000 1000 1000 1000 1000 14000 -80000
1000 1000 1000 1000 -2100 -45 44
1000 1000 1000 1000 -3700 -13 -46
1000 19 -2 -3 8 -27 46
47 6 -31 6 -4 -44 -13
31 30 27 36 -18 30 25

mi ritorna come matrice migliore la 5x5 che comincia in riga 0 colonna 1, mentre mi sembra dovrebbe la 6x6 che comincia in (0,0)
Piu' in generale non mi e' chiaro l'algoritmo che avete scelto (a naso il tuo e di gugo sembrano simili). Da quel che sembra partite calcolando solo le sottomatrici di una dimensione prefissata (secondo i numeri primi piuttosto che la serie di fibonacci), ma non mi e' affatto chiaro come poi calcoliate quelle di dimensione rimanente :mbe:

Risolto:



http://www.guidealgoritmi.it/images/ImgForums/contest5b_3.jpg


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}


Stati DFA(const char *szFileName, int **a, int array_size)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= array_size)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
a[riga][colonna] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int main()
{
clock_t c_start, c_end;

int **m;
int x, y, k;
int array_size;
Stati stato;
char *szFileName = "matrix3.txt";

int riga, colonna;
int dim;
int somma;

int riga_temp, colonna_temp;
int dim_temp;
int somma_temp;

int fibDim = 10;

int Fibonacci[] = {2,3,5,8,13,21,34,55,89,144};

c_start = clock();

array_size = GetArraySize(szFileName);
if ( array_size <= 0 )
return;

m = (int**)malloc(sizeof(int*)*array_size);
if ( m != NULL )
{
for ( x = 0; x < array_size; x++ )
{
m[x] = (int*)malloc(sizeof(int)*array_size);
if ( m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

stato = DFA(szFileName, m, array_size);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}

c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

c_start = clock();

if ( array_size == 1 )
{
c_end = clock();
printf("\nRiga -> 0\nColonna -> 0\nDimensione -> 1\nSomma -> %d\n", m[0][0]);
printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return 0;
}
else if ( array_size == 2 )
{
riga = colonna = 0;
dim = 1;
somma = m[riga][colonna];
colonna++;
if ( m[riga][colonna] > somma )
somma = m[riga][colonna];
colonna = 0;
riga++;
if ( m[riga][colonna] > somma )
somma = m[riga][colonna];
colonna++;
if ( m[riga][colonna] > somma )
somma = m[riga][colonna];

if ( m[0][0] + m[0][1] + m[1][0] + m[1][1] > somma )
{
dim = 2;
riga = 0;
colonna = 0;

somma = m[0][0] + m[0][1] + m[1][0] + m[1][1];
}

c_end = clock();
printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", riga, colonna, dim, somma);
printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return 0;
}

somma_temp = m[0][0] + m[0][1];
riga_temp = 0;
colonna_temp = 0;
dim_temp = 2;

for ( k = fibDim - 1; k >= 0; k-- )
{
dim = Fibonacci[k];
x = y = 0;
riga = colonna = 0;
somma = 0;

for ( riga = 0; riga <= array_size - dim; riga++ )
{
for ( colonna = 0; colonna <= array_size - dim; colonna++ )
{
for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
somma += m[y][x];
}
}
if ( somma > somma_temp )
{
//printf("dimensione -> %d Somma -> %d\n", dim, somma);
somma_temp = somma;
riga_temp = riga;
colonna_temp = colonna;
dim_temp = dim;
}
x = y = 0;
somma = 0;
}
}
}

dim = dim_temp + 1;
colonna = colonna_temp;
while ( dim < array_size - dim )
{
x = y = 0;

riga = riga_temp - 1;
if ( riga < 0 )
riga = 0;

somma = 0;

if ( riga + dim > array_size - 1 )
break;
if ( colonna + dim > array_size - 1 )
break;

for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
somma += m[y][x];
}
}
if ( somma > somma_temp )
{
somma_temp = somma;
riga_temp = riga;
colonna_temp = colonna;
dim_temp = dim;
}

dim++;
}

dim = dim_temp + 1;
riga = riga_temp;
while ( dim < array_size - dim )
{
x = y = 0;

colonna = colonna_temp - 1;
if ( colonna < 0 )
colonna = 0;

somma = 0;

if ( riga + dim > array_size - 1 )
break;
if ( colonna + dim > array_size - 1 )
break;

for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
somma += m[y][x];
}
}
if ( somma > somma_temp )
{
somma_temp = somma;
riga_temp = riga;
colonna_temp = colonna;
dim_temp = dim;
}

dim++;
}

c_end = clock();

printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", riga_temp, colonna_temp, dim_temp, somma_temp);

printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return 0;
}


Per la spiegazione dell'algoritmo, prima vorrei capire io stesso quello che cabasisi ho scritto :D (scherzo, sto cercando di migliorare il codice. Alla fine spiegherò tutto).

[Vincenzo1968]

Non ero sparito:p , ho concluso il primo punto dell'esercizio
...

Questo è il risultato (intel a 2.0giga)

Lettura file completata in: 0.01914 secondi
Ricerca sub-matrice più ampia trovata
Riga:110
Colonna:257
La dimensione è:10. Tempo impiegato: 0.01976 secondi

Va bene come risultato?

Direi proprio di si. Complimenti :)
Ho provato il tuo codice su questa macchina:


AMD Athlon(tm) 64 X2 Dual
Core Processor 4800+
2.50 GHz 896 MB di RAM

Microsoft Windows XP Professional
Service Pack 2


e il tempo è di 0.01810 secondi per la lettura da file e 0.01655 secondi per la ricerca.

[Vincenzo1968]

Ho corretto qualche altro bug.

Su questa macchina:

AMD Athlon(tm) 64 X2 Dual
Core Processor 4800+
2.50 GHz 896 MB di RAM

Microsoft Windows XP Professional
Service Pack 2


impiega 0.20300 secondi


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, int **a, int array_size)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= array_size)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
a[riga][colonna] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int main()
{
clock_t c_start, c_end;

int **m;
int x, y, k;
int array_size;
Stati stato;

char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix3.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix4.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix5.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix6.txt";

int riga, colonna;
int dim;
int somma;

int riga_temp, colonna_temp;
int dim_temp;
int somma_temp;

int fibDim = 10;
int bTrovato;

int Fibonacci[] = {2,3,5,8,13,21,34,55,89,144};

c_start = clock();

array_size = GetArraySize(szFileName);
if ( array_size <= 0 )
return;

m = (int**)malloc(sizeof(int*)*array_size);
if ( m != NULL )
{
for ( x = 0; x < array_size; x++ )
{
m[x] = (int*)malloc(sizeof(int)*array_size);
if ( m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

stato = DFA(szFileName, m, array_size);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}

c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

c_start = clock();

if ( array_size == 1 )
{
c_end = clock();
printf("\nRiga -> 0\nColonna -> 0\nDimensione -> 1\nSomma -> %d\n", m[0][0]);
printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return 0;
}
else if ( array_size == 2 )
{
dim = 1;
riga = colonna = 0;
somma = m[riga][colonna];
if ( m[0][1] > somma )
{
riga = 0;
colonna = 1;
somma = m[riga][colonna];
}

if ( m[1][0] > somma )
{
riga = 1;
colonna = 0;
somma = m[riga][colonna];
}

if ( m[1][1] > somma )
{
riga = 1;
colonna = 1;
somma = m[riga][colonna];
}

if ( m[0][0] + m[0][1] + m[1][0] + m[1][1] > somma )
{
dim = 2;
riga = 0;
colonna = 0;

somma = m[0][0] + m[0][1] + m[1][0] + m[1][1];
}

c_end = clock();
printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", riga, colonna, dim, somma);
printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return 0;
}

somma_temp = m[0][0] + m[0][1];
riga_temp = 0;
colonna_temp = 0;
dim_temp = 2;

for ( k = fibDim - 1; k >= 0; k-- )
{
dim = Fibonacci[k];
x = y = 0;
riga = colonna = 0;
somma = 0;

for ( riga = 0; riga <= array_size - dim; riga++ )
{
for ( colonna = 0; colonna <= array_size - dim; colonna++ )
{
for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
somma += m[y][x];
}
}
if ( somma > somma_temp )
{
somma_temp = somma;
riga_temp = riga;
colonna_temp = colonna;
dim_temp = dim;
}
x = y = 0;
somma = 0;
}
}
}

dim = dim_temp - 1;
y = riga_temp + 1;
x = colonna_temp + 1;
while ( dim > 0 )
{
if ( y > array_size - 1 )
break;
if ( x > array_size - 1 )
break;

somma = 0;
for ( riga = y; riga < y + dim; riga++ )
{
for ( colonna = x; colonna < x + dim; colonna++ )
{
somma += m[riga][colonna];
}
}

if ( somma > somma_temp )
{
somma_temp = somma;
riga_temp = y;
colonna_temp = x;
dim_temp = dim;
}

dim--;
y++;
x++;
}

dim = dim_temp + 1;
y = riga_temp - 1;
x = colonna_temp;
if ( y < 0 )
y = 0;
somma = 0;
for ( riga = y; riga < y + dim && riga < array_size; riga++ )
{
for ( colonna = x; colonna < x + dim && colonna < array_size; colonna++ )
{
somma += m[riga][colonna];
}
}
if ( somma > somma_temp )
{
somma_temp = somma;
riga_temp = y;
colonna_temp = x;
dim_temp = dim;
}

dim = dim_temp + 1;
y = riga_temp;
x = colonna_temp - 1;
if ( x < 0 )
x = 0;
somma = 0;
for ( riga = y; riga < y + dim && riga < array_size; riga++ )
{
for ( colonna = x; colonna < x + dim && colonna < array_size; colonna++ )
{
somma += m[riga][colonna];
}
}
if ( somma > somma_temp )
{
somma_temp = somma;
riga_temp = y;
colonna_temp = x;
dim_temp = dim;
}

dim = dim_temp;
somma = 0;
for ( riga = riga_temp; riga <= array_size - dim; riga++ )
{
for ( colonna = 0; colonna < dim; colonna++ )
{
for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
//printf("m[%d][%d] -> %d\n", y, x, m[y][x]);
somma += m[y][x];
}
}
if ( somma > 29999 )
printf("Somma ->%d\n", somma);
if ( somma > somma_temp )
{
somma_temp = somma;
riga_temp = riga;
colonna_temp = colonna;
dim_temp = dim;
}
x = y = 0;
somma = 0;
}
}

c_end = clock();

printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", riga_temp, colonna_temp, dim_temp, somma_temp);

printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return 0;
}

[gugoXX]

Riduzione codice e tempi.
Toglo Eratostene, tolgo molti if e aggiusto output.
Mi sa che se non riesco a passare a qualche greedy decente finisco qui.


Coordinate: 94,60 - Dimensione 56 - Somma 3185
Time: 297ms
Test: 3185



class Program
{
static void Main(string[] args)
{
Matrix mat = new Matrix("Matrix2.txt");
Stopwatch sw = new Stopwatch();
sw.Start();
var toprint = mat.Ex7();
sw.Stop();

int x = toprint.Coords.x;
int y = toprint.Coords.y;
int z = toprint.Coords.z;

Console.WriteLine("Coordinate: {0},{1} - Dimensione {2} - Somma {3}", x, y, z, toprint.val);
Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);

int test = mat.Test(x, y, z);
Console.WriteLine("Test: {0}", test);

Console.ReadKey();
}
}

public class Matrix
{
public int Dim;
public int[,] Mat;

public void Save(string fname)
{
StreamWriter sw = new StreamWriter(@"C:\temp\" + fname);
sw.WriteLine("--{0}--", Dim);
for (int y = 0; y < Dim; y++)
{
for (int x = 0; x < Dim; x++)
{
sw.Write("{0} ", Mat[x, y].ToString());
}
sw.WriteLine();
}
sw.Close();
}

public Matrix(string fname)
{
Load(fname);
}

public Matrix(int[,] vals)
{
Mat = vals;
Dim = vals.GetLength(0);
}

public void Load(string fname)
{
StreamReader sr = new StreamReader(@"C:\temp\" + fname);
string fline = sr.ReadLine();
string mds = fline.Substring(2, fline.Length - 4);
Dim = int.Parse(mds);
Mat = new int[Dim, Dim];
for (int y = 0; y < Dim; y++)
{
string line = sr.ReadLine();
string[] valss = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
var valis = valss.Select(t => int.Parse(t)).ToArray();
Enumerable.Range(0, Dim).ForAll(x => Mat[x, y] = valis[x]);
}
sr.Close();
}

public struct CoordsStruct
{
public int x;
public int y;
public int z;
public CoordsStruct(int ix, int iy, int iz)
{
x = ix;
y = iy;
z = iz;
}
}

public struct Ex2Result
{
public CoordsStruct Coords;
public int val;

public Ex2Result(CoordsStruct ics,int ival)
{
Coords = ics;
val = ival;
}
}

public int Test(int x, int y, int d)
{
var dom = from ty in Enumerable.Range(y, d)
from tx in Enumerable.Range(x, d)
select Mat[tx, ty];
return dom.Sum();
}

public Ex2Result Ex7()
{
int[,][] Compl = new int[Dim, Dim][];
for (int y = 0; y < Dim; y++)
{
for (int x = 0; x < Dim; x++)
{
int mxy = (Dim+1) - ((x > y) ? x : y);
int[] st = Compl[x, y] = new int[mxy];
st[1] = Mat[x, y];
if (mxy > 2) st[2] = Mat[x, y] + Mat[x, y + 1] + Mat[x + 1, y] + Mat[x + 1, y + 1];
if (mxy > 3) st[3] = st[2] + Mat[x, y + 2] + Mat[x + 1, y + 2] + Mat[x + 2, y + 2] + Mat[x + 2, y + 1] + Mat[x + 2, y];
}
}

Ex2Result rer = new Ex2Result();
int rerval = int.MinValue;
for (int z = 4; z <= Dim; z++)
{
int mda = (z >> 1);
int ze1 = z & 1;
int md = mda + ze1;
bool ze1u1 = ze1 == 1;
int dimmz = Dim - z;
for (int y = 0; y < dimmz; y++)
{
for (int x = 0; x < dimmz; x++)
{
int xmda = x + mda;
int ymda = y + mda;

int cur = Compl[x, y][md]
+ Compl[x, y + md][mda]
+ Compl[x + md, y][mda]
+ Compl[xmda, ymda][md];

if (ze1u1)
{
cur -= Mat[xmda, ymda];
}

Compl[x, y][z] = cur;
if (cur > rerval)
{
rer = new Ex2Result(new CoordsStruct(x, y, z), cur);
rerval = cur;
}
}
}
}
return rer;
}}

[Vincenzo1968]

Riduzione codice e tempi.
Toglo Eratostene, tolgo molti if e aggiusto output.
Mi sa che se non riesco a passare a qualche greedy decente finisco qui.


Coordinate: 94,60 - Dimensione 56 - Somma 3185
Time: 297ms
Test: 3185

...


Ciao Gugo,

purtroppo debbo dirti che ho riscontrato delle piccole incongruenze nel tuo codice.

Con questi file dà i seguenti risultati:

www.guidealgoritmi.it/public/matrix.zip

File Matrix4.txt:
Il risultato dovrebbe essere

http://www.guidealgoritmi.it/images/ImgForums/contest05_ris4.jpg

e invece è

http://www.guidealgoritmi.it/images/ImgForums/contest05_ris4_gugo.jpg


File Matrix5.txt:
Il risultato dovrebbe essere

http://www.guidealgoritmi.it/images/ImgForums/contest05_ris5.jpg

e invece è

http://www.guidealgoritmi.it/images/ImgForums/contest05_ris5_gugo.jpg


File Matrix6.txt:
Il risultato dovrebbe essere

http://www.guidealgoritmi.it/images/ImgForums/contest05_ris6.jpg

e invece è

http://www.guidealgoritmi.it/images/ImgForums/contest05_ris6_gugo.jpg

[gugoXX]

Ciao Gugo,

purtroppo debbo dirti che ho riscontrato delle piccole incongruenze nel tuo codice.



Eheh, penso dovro' fare qualche aggiustamento, mi sa che mi sono mangiato qualche indice.
Il concetto e i tempi non dovrebbero cambiare troppo. Vedremo.

[Vincenzo1968]

Eheh, penso dovro' fare qualche aggiustamento, mi sa che mi sono mangiato qualche indice.
Il concetto e i tempi non dovrebbero cambiare troppo. Vedremo.

E io metto le mani avanti e dico subito che il mio codice contiene ancora qualche bug. Ho fatto altre prove, su altri file, e, a volte, si avvicina(come nel tuo caso) ma il risultato non è corretto.

Il codice di Daniele è risultato, invece, perfetto. Non ne sbaglia una ;)

A proposito, Daniele, su questa macchina(che è un po' più veloce rispetto al portatile che usavo prima) i tempi del tuo programma sono:


AMD Athlon(tm) 64 X2 Dual
Core Processor 4800+
2.50 GHz 896 MB di RAM


0.30191 secondi :)

[marco.r]

Eheh, penso dovro' fare qualche aggiustamento, mi sa che mi sono mangiato qualche indice.
Il concetto e i tempi non dovrebbero cambiare troppo. Vedremo.

Ho fatto qualche prova con del codice basato sulla tua idea.
Quali matrici salvi, solo quelle relative alle dimensioni prime ?
Salvando solo quelle non usi tanta memoria ma ci mette parecchio per la 1000x1000 (circa 600 secondi). Salvandole tutte la memoria non basta (andiamo sopra i 4GiB per la suddetta matrice). Salvandone solo una parte sembra un buon compromesso (e.g. primi + multipli di 2 o multipli di 3). Cosi' riesco a stare attorno a 150-200 secondi. Cachando solo quelle piu' utilizzate (oltre a quelle dei primi da tenere sempre) si potrebbe far tarare automaticamente l'uso della memoria.

[DanieleC88]

Il codice di Daniele è risultato, invece, perfetto. Non ne sbaglia una ;)
:yeah: :gluglu:

Ti ringrazio anche della nuova misurazione. ;)

[WarDuck]

Ho fatto qualche prova con del codice basato sulla tua idea.
Quali matrici salvi, solo quelle relative alle dimensioni prime ?
Salvando solo quelle non usi tanta memoria ma ci mette parecchio per la 1000x1000 (circa 600 secondi). Salvandole tutte la memoria non basta (andiamo sopra i 4GiB per la suddetta matrice). Salvandone solo una parte sembra un buon compromesso (e.g. primi + multipli di 2 o multipli di 3). Cosi' riesco a stare attorno a 150-200 secondi. Cachando solo quelle piu' utilizzate (oltre a quelle dei primi da tenere sempre) si potrebbe far tarare automaticamente l'uso della memoria.

Eheh come si dice... "possiamo aspettare tutto il tempo del mondo, il tempo è potenzialmente infinito, la memoria limitata".

Comunque appena posso mi ci rimetto anche io, ho un po' mollato la presa per via di Fisica 2 a settembre (il tempo stringe).

[Vincenzo1968]

Questi sono i miei tempi su una matrice 1000x1000 (http://www.guidealgoritmi.it/public/matrix8.zip):

http://www.guidealgoritmi.it/images/ImgForums/matrix1000x1000.jpg

Il codice, lo ricordo, contiene ancora qualche bug :(

[WarDuck]

Ho portato il mio codice per il secondo punto in C++, compilatore mingw-gcc 3.4.5.


Produttore sistema Dell Inc.
Modello sistema XPS M1330
Tipo sistema PC basato su X86
Processore Intel(R) Core(TM)2 Duo CPU T8300 @ 2.40GHz, 2401 Mhz, 2 core, 2 processori logici

Preparatevi che è un po' lungo, ho incluso tutto, anche il main:

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <ctime>

using namespace std;

int** loadMatrix(char* fileName, int& dim) {
int** array;
ifstream fs;
fs.open(fileName);

if (fs.is_open()) {
fs >> dim;

array = new int*[dim];
for (int i=0; i<dim; i++) {
array[i] = new int[dim];
}


int i = 0;
while (!fs.eof() && i<dim) {
int j=0;
while (j<dim) {
fs >> array[i][j];
j = j+1;
}
i = i+1;
}
}
fs.close();
return array;
}

static void findMaxSum(int** mat, int& dim) {
int old_i;
int old_j;

int max = 0;
int max_i = 0;
int max_j = 0;
int p = 0;
int max_p = 0;

for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
int sum = mat[i][j];
old_i = i;
old_j = j;
p = 1;

if (sum > max) {
max = sum;
max_i = old_i;
max_j = old_j;
max_p = p;
}
for (int k = (p - 1); k >= 0 && i < dim - 1 && j < dim - 1; k--) {
sum = sum + mat[i - k][j + 1] + mat[i + 1][j - k];
if (k == 0) {
sum = sum + mat[i + 1][j + 1];
i++;
j++;
k = ++p;

if (sum > max) {
max = sum;
max_i = old_i;
max_j = old_j;
max_p = p;
}
}
}
i = old_i;
j = old_j;
}
}

cout << "Max sum is " << max << " -> matrix " << max_p << "x" << max_p << " at index " << "(" << max_i << "," << max_j << ")\n";
}

int main(int argc, char** argv) {
clock_t start, end;
double diff;
int dim = 0;
int** array;

start = clock();
array = loadMatrix("Matrix2.txt", dim);
end = clock();

diff = (double(end)-double(start))/CLOCKS_PER_SEC;

cout << "Matrix Loaded. Time elapsed: ";
cout << diff;
cout << "ms\n";

start = clock();
findMaxSum(array, dim);
end = clock();

diff = (double(end)-double(start))/CLOCKS_PER_SEC;

cout << "Computation Done. Time elapsed: ";
cout << diff;
cout << "ms\n";

return 0;
}

Output:
http://img360.imageshack.us/img360/8797/good2bi4.png

Edit: ovviamente i risultati sono in secondi, ho sbagliato io a scrivere, pardon.

[Vincenzo1968]

Ecco la versione senza bug(almeno spero):

Prova sul matricione 1000x1000:

http://www.guidealgoritmi.it/images/ImgForums/contest05b_finale.jpg

La macchina è questa:

AMD Athlon(tm) 64 X2 Dual
Core Processor 4800+
2.50 GHz 896 MB di RAM

Microsoft Windows XP Professional
Service Pack 2


e il codice è questo:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, int **a, int array_size)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= array_size)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
a[riga][colonna] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

void FindSubMatrix(char *szFileName, int *row, int *col, int *size, int *sum)
{
int **m;
int x, y, k;
int array_size;
int subarray_size;
Stati stato;

int riga_sub, colonna_sub;

int riga, colonna;
int dim;
int somma;

clock_t c_start, c_end;

int fibDim = 10;
int fibRange;

int Fibonacci[] = {2,3,5,8,13,21,34,55,89,144};

c_start = clock();

array_size = GetArraySize(szFileName);
if ( array_size <= 0 )
return;

m = (int**)malloc(sizeof(int*)*array_size);
if ( m != NULL )
{
for ( x = 0; x < array_size; x++ )
{
m[x] = (int*)malloc(sizeof(int)*array_size);
if ( m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return;
}

stato = DFA(szFileName, m, array_size);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}

c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

if ( array_size == 1 )
{
c_end = clock();
printf("\nRiga -> 0\nColonna -> 0\nDimensione -> 1\nSomma -> %d\n", m[0][0]);
printf("\nTempo impiegato per la ricerca -> 0 secondi\n");

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return;
}
else if ( array_size == 2 )
{
dim = 1;
riga = colonna = 0;
somma = m[riga][colonna];
if ( m[0][1] > somma )
{
riga = 0;
colonna = 1;
somma = m[riga][colonna];
}

if ( m[1][0] > somma )
{
riga = 1;
colonna = 0;
somma = m[riga][colonna];
}

if ( m[1][1] > somma )
{
riga = 1;
colonna = 1;
somma = m[riga][colonna];
}

if ( m[0][0] + m[0][1] + m[1][0] + m[1][1] > somma )
{
dim = 2;
riga = 0;
colonna = 0;

somma = m[0][0] + m[0][1] + m[1][0] + m[1][1];
}

printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", riga, colonna, dim, somma);
printf("\nTempo impiegato per la ricerca -> 0 secondi\n");

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);

return;
}

*sum = m[0][0] + m[0][1];
*row = 0;
*col = 0;
*size = 2;

for ( k = fibDim - 1; k >= 0; k-- )
{
dim = Fibonacci[k];
x = y = 0;
riga = colonna = 0;
somma = 0;

for ( riga = 0; riga <= array_size - dim; riga++ )
{
for ( colonna = 0; colonna <= array_size - dim; colonna++ )
{
for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
somma += m[y][x];
}
}
if ( somma > *sum )
{
*sum = somma;
*row = riga;
*col = colonna;
*size = dim;
}
x = y = 0;
somma = 0;
}
}
}

fibRange = Fibonacci[3];
subarray_size = *size + fibRange;
dim = subarray_size;
x = y = 0;
riga_sub = *row;
colonna_sub = *col;
somma = 0;

riga_sub -= fibRange;
if ( riga_sub < 0 )
riga_sub = 0;
colonna_sub -= fibRange;
if ( colonna_sub < 0 )
colonna_sub = 0;

while ( dim >= 2 )
{
for ( riga = riga_sub; riga <= *row*2 && riga + dim <= array_size; riga++ )
{
for ( colonna = colonna_sub; colonna <= *col*2 && colonna + dim <= array_size; colonna++ )
{
for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
somma += m[y][x];
}
}
if ( somma > *sum )
{
*sum = somma;
*row = riga;
*col = colonna;
*size = dim;
}
x = y = 0;
somma = 0;
}
}
dim--;
}

for ( x = 0; x < array_size; x++ )
free(m[x]);
free(m);
}

int main()
{
clock_t c_start, c_end;
int row, col, size, sum;

//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix3.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix4.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix5.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix6.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix7.txt";
char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix8.txt";


c_start = clock();

FindSubMatrix(szFileName, &row, &col, &size, &sum);

c_end = clock();

printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", row, col, size, sum);

printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

return 0;
}

[gugoXX]

Aggiusto i bug e tiro l'ultimo colpo di coda.
Rulla il C#, rulla. (In realta' no, ma ci stava bene)

Risultato 200x200

Coordinate: 94,60 - Dimensione 56 - Somma 3185
Time: 68ms
Test: 3185


Risultato 1000x1000

Coordinate: 232,565 - Dimensione 410 - Somma 2419
Time: 11148ms
Test: 2419


Codice

class Program
{
static void Main(string[] args)
{
//int[,] vals = Randomizer.GetRandom2(5);
//Matrix mat = new Matrix(vals);

Matrix mat = new Matrix("Matrix2.txt");
Stopwatch sw = new Stopwatch();
sw.Start();
var toprint = mat.Ex8();
sw.Stop();

int x = toprint.x;
int y = toprint.y;
int z = toprint.z;

Console.WriteLine("Coordinate: {0},{1} - Dimensione {2} - Somma {3}", x, y, z, toprint.val);
Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);

int test = mat.Test(x, y, z);
Console.WriteLine("Test: {0}", test);

Console.ReadKey();
}
}

public class Matrix
{
public int Dim;
public int[,] Mat;

public void Save(string fname)
{
StreamWriter sw = new StreamWriter(@"C:\temp\" + fname);
sw.WriteLine("--{0}--", Dim);
for (int y = 0; y < Dim; y++)
{
for (int x = 0; x < Dim; x++)
{
sw.Write("{0} ", Mat[x, y].ToString());
}
sw.WriteLine();
}
sw.Close();
}

public Matrix(string fname)
{
Load(fname);
}

public Matrix(int[,] vals)
{
Mat = vals;
Dim = vals.GetLength(0);
}

public void Load(string fname)
{
StreamReader sr = new StreamReader(@"C:\temp\" + fname);
string fline = sr.ReadLine();
string mds = fline.Substring(2, fline.Length - 4);
Dim = int.Parse(mds);
Mat = new int[Dim, Dim];
for (int y = 0; y < Dim; y++)
{
string line = sr.ReadLine();
string[] valss = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
var valis = valss.Select(t => int.Parse(t)).ToArray();
Enumerable.Range(0, Dim).ForAll(x => Mat[x, y] = valis[x]);
}
sr.Close();
}

public struct Result
{
public int x;
public int y;
public int z;
public int val;
public Result(int ix, int iy, int iz, int ival)
{
x = ix;
y = iy;
z = iz;
val = ival;
}
}

public int Test(int x, int y, int d)
{
var dom = from ty in Enumerable.Range(y, d)
from tx in Enumerable.Range(x, d)
select Mat[tx, ty];
return dom.Sum();
}

public Result Ex8()
{
int[][,] Compl = new int[(Dim/2)+2][,];
Compl[1]=Mat;

var dom00 = from y in Enumerable.Range(0, Dim)
from x in Enumerable.Range(0, Dim)
select new Result(x, y, 1, Mat[x, y]);

Result rer = dom00.Max(t => t.val);
int rerval = rer.val;

for (int z = 2; z <= Dim; z++)
{
int mda = (z >> 1);
int ze1 = z & 1;
int md = mda + ze1;
bool ze1u1 = ze1 == 1;
int dimmz = Dim - z;

int[,] Complcur = null;
bool tobemem = z < ((Dim >> 1) + 1);
if (tobemem)
{
Complcur = Compl[z] = new int[dimmz, dimmz];
}
int[,] Complmda = Compl[mda];
int[,] Complmd = Compl[md];
for (int y = 0; y < dimmz; y++)
{
int ymda = y + mda;
int ymd = y + md;
for (int x = 0; x < dimmz; x++)
{
int cur = Complmd[x, y]
+ Complmda[x, ymd]
+ Complmda[x + md, y]
+ Complmd[x + mda, ymda];

if (ze1u1)
{
cur -= Mat[x + mda, ymda];
Compl[mda] = null;
}

if (tobemem)
{
Complcur[x, y] = cur;
}
if (cur > rerval)
{
rerval = cur;
rer = new Result(x, y, z, cur);
}
}
}
}
return rer;
}
}

public static class Extensor
{
public static void ForAll<T>(this IEnumerable<T> domain,Action<T> act)
{
foreach (T t in domain) act(t);
}

public static T Max<T, U>(this IEnumerable<T> domain, Func<T, U> elem) where U:IComparable<U>
{
T CurmaxRow = default(T);
U CurMax=default(U);
foreach (T t in domain)
{
U CurVal=elem(t);
if ((CurVal.CompareTo(CurMax) > 0)||(CurMax.CompareTo(default(U))==0))
{
CurmaxRow = t;
CurMax = CurVal;
}
}
return CurmaxRow;
}
}

[WarDuck]

Siete mostri ragazzi, complimenti... :D

PS: se allegate anche il vostro "principio di funzionamento" (cioè il ragionamento che avete fatto) è anche più educativo :D

[DanieleC88]

Siete mostri ragazzi, complimenti... :D
Concordo pienamente, ad ogni Contest mi tocca scappare con la coda fra le gambe... :p (leggiti l'intervento di repne scasb per il Contest 3, se non ricordo male)

[banryu79]

Con repne scab non c'è confronto, solo apprendimento :D

[gugoXX]

Siete mostri ragazzi, complimenti... :D

PS: se allegate anche il vostro "principio di funzionamento" (cioè il ragionamento che avete fatto) è anche più educativo :D

E' giusto.
Si tratta di calcolare tutte le possibili sottomatrici quadrate presenti sul matricione.
Nella mia implementazione (come penso finora tutte le altre), per ciascuna coordinata quindi occorre calcolare tutte le sottomatrici quadrate che hanno come vertice proprio quella coordinata.
Parto con il calcolare tutte le matrici quadrate di dimensione pari a 1, ovvero la matriciona originale stessa.
Poi salgo, e cerco tutte quelle di dimensione pari a 2
poi 3,... e cosi' via fino ad N.

Per ottenere la sottomatrice di dimensione Z, partendo dal presupposto che ho memorizzato e calcolato tutte le sottomatrici precedenti, ho diviso il problema in 2.
Se Z e' un numero pari, allora sommo fra di loro 4 sottomatrici di lato z/2
Se Z e' un numero dispari invece sommo fra di loro 2 sottomatrici di lato z/2 arrotondato inferiore e 2 sottomatrici di lato z/2 arrotondato superiore, posizionate come in figura.
In questo modo pero' l'elemento centrale lo considero 2 volte, che verra' quindi tolto se del caso.

http://img.photobucket.com/albums/v314/gugogugo/Contest5.png

Inoltre, non e' necessario tenere in memoria tutte le matrici.
Innanzitutto quelle con dimensione superiore a DIM/2 non le memorizzeremo, in quanto non verranno mai utilizzate
In piu', mano a mano che si prosegue, possiamo inziare a rimuovere sottomatrici precedenti che non si useranno piu'.
Es: Quando ho terminato di calcolare le sottomatrici lato 9, posso rimuovere tutte le sottomatrici lato 4, in quanto non verranno piu' usate.
Nel calcolo delle sottomatrici lato 10 si useranno le sottomatrici lato5, e non torneremo mai piu' indietro.

Cosi' ho trovato lo spazio per calcolare la 1000x1000.

L'algoritmo e' quindi un O(5N*N^2) = O(N^3)
Per la memoria richiesta massima invece devo calcolare il volume di un tronco di piramide sghemba, e ad Agosto non ho proprio voglia.
Comunque e' O(N^3) anche lui, ma con coefficienti bassi.

[DanieleC88]

Metodo molto ingegnoso, complimenti. ;)

[WarDuck]

Sto sviluppando una teoria, per tentare di prevedere se continuare o meno il calcolo delle sottomatrici in base alle somme già trovate e alla media dei valori positivi, vediamo se funziona... :D

[DanieleC88]

Però fermare il calcolo in base alla media dei numeri positivi presuppone che questi siano distribuiti in modo più o meno uniforme attraverso la matrice, mentre è perfettamente legale ricevere in input una matrice piena di zeri o di numeri negativi e trovare poi una serie di interi positivi molto grandi nell'angolo in basso a destra, per esempio. Non trovi? :)

[Vincenzo1968]

Ogni volta che correggo qualche bug, ne spuntano altri mille. :muro:
Io mi fermo qui, mi arrendo.

[WarDuck]

Però fermare il calcolo in base alla media dei numeri positivi presuppone che questi siano distribuiti in modo più o meno uniforme attraverso la matrice, mentre è perfettamente legale ricevere in input una matrice piena di zeri o di numeri negativi e trovare poi una serie di interi positivi molto grandi nell'angolo in basso a destra, per esempio. Non trovi? :)

Si infatti sto cercando di risolvere la questione usando la media dei numeri calcolati nello stesso passo.

Chiaramente il problema della distribuzione c'è... La mia idea è qualcosa del tipo "se ad un certo punto tutte le somme degli elementi fatte finora sono inferiori alla media evita di andare avanti".

Il problema è capire se possa funzionare con la maggior parte delle distribuzioni possibili (dovrei tirare fuori qualcosa di matematicamente valido da poter essere dimostrato, non una cosa facile insomma) e soprattutto capire qual è il famoso "punto" di cui parlo al paragrafo precedente (finora ho fatto delle prove legandolo alla dimensione della matrice, calcolandomi un fattore ad esempio dim/2 ).

Cmq è solo una idea, il problema come dice einstein sono i nostri "pregiudizi". Bisognerebbe ragionare fuori dagli schemi (per quanto sia possibile), magari provare a ristendere il programma da capo, tentando qualche altra soluzione.

[gugoXX]

Corretto un BUG.
Iniettato il parallelismo
e chiudo qui anche io.

Per poter compliare occorre scaricare le parallel extension (PLINQ)
e includere la reference appena scaricata: system.threading nel progetto.

Matrice 1000x1000

Coordinate: 232,565 - Dimensione 410 - Somma 2419
Time: 6844ms
Test: 2419



class Program
{
static void Main(string[] args)
{
//int[,] vals = Randomizer.GetRandom2(5);
//Matrix mat = new Matrix(vals);

Matrix mat = new Matrix("Matrix1.txt");
Stopwatch sw = new Stopwatch();
sw.Start();
var toprint = mat.Ex8();
sw.Stop();

int x = toprint.x;
int y = toprint.y;
int z = toprint.z;

Console.WriteLine("Coordinate: {0},{1} - Dimensione {2} - Somma {3}", x, y, z, toprint.val);
Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);

int test = mat.Test(x, y, z);
Console.WriteLine("Test: {0}", test);

Console.ReadKey();
}
}

public class Matrix
{
public int Dim;
public int[,] Mat;

public void Save(string fname)
{
StreamWriter sw = new StreamWriter(@"C:\temp\" + fname);
sw.WriteLine("--{0}--", Dim);
for (int y = 0; y < Dim; y++)
{
for (int x = 0; x < Dim; x++)
{
sw.Write("{0} ", Mat[x, y].ToString());
}
sw.WriteLine();
}
sw.Close();
}

public Matrix(string fname)
{
Load(fname);
}

public Matrix(int[,] vals)
{
Mat = vals;
Dim = vals.GetLength(0);
}

public void Load(string fname)
{
StreamReader sr = new StreamReader(@"C:\temp\" + fname);
string fline = sr.ReadLine();
string mds = fline.Substring(2, fline.Length - 4);
Dim = int.Parse(mds);
Mat = new int[Dim, Dim];
for (int y = 0; y < Dim; y++)
{
string line = sr.ReadLine();
string[] valss = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
var valis = valss.Select(t => int.Parse(t)).ToArray();
Enumerable.Range(0, Dim).ForAll(x => Mat[x, y] = valis[x]);
}
sr.Close();
}

public struct Result
{
public int x;
public int y;
public int z;
public int val;
public Result(int ix, int iy, int iz, int ival)
{
x = ix;
y = iy;
z = iz;
val = ival;
}
}

public int Test(int x, int y, int d)
{
var dom = from ty in Enumerable.Range(y, d)
from tx in Enumerable.Range(x, d)
select Mat[tx, ty];
return dom.Sum();
}

public Result Ex8()
{
int[][,] Compl = new int[(Dim/2)+2][,];
Compl[1]=Mat;

var dom00 = from y in Enumerable.Range(0, Dim)
from x in Enumerable.Range(0, Dim)
select new Result(x, y, 1, Mat[x, y]);

Result rer = dom00.Max(t => t.val);
int rerval = rer.val;

int limmem=((Dim >> 1) + 1);
for (int z = 2; z <= Dim; z++)
{
int mda = (z >> 1);
int ze1 = z & 1;
int md = mda + ze1;
bool ze1u1 = ze1 == 1;
int dimmz = Dim - z;

int[,] Complcur = null;
bool tobemem = z < limmem;
if (tobemem)
{
Complcur = Compl[z] = new int[dimmz, dimmz];
}
int[,] Complmda = Compl[mda];
int[,] Complmd = Compl[md];
Parallel.For(0, dimmz, y =>
{
int ymda = y + mda;
int ymd = y + md;
for (int x = 0; x < dimmz; x++)
{
int cur = Complmd[x, y]
+ Complmda[x, ymd]
+ Complmda[x + md, y]
+ Complmd[x + mda, ymda];

if (ze1u1)
{
cur -= Mat[x + mda, ymda];
}

if (tobemem)
{
Complcur[x, y] = cur;
}
if (cur > rerval)
{
mut.WaitOne();
if (cur > rerval)
{
rerval = cur;
rer = new Result(x, y, z, cur);
}
mut.ReleaseMutex();
}
}
});
if (ze1u1) Compl[mda] = null;
}
return rer;
}

private Mutex mut = new Mutex();
}

public static class Extensor
{
public static void ForAll<T>(this IEnumerable<T> domain,Action<T> act)
{
foreach (T t in domain) act(t);
}

public static T Max<T, U>(this IEnumerable<T> domain, Func<T, U> elem) where U:IComparable<U>
{
T CurmaxRow = default(T);
U CurMax=default(U);
foreach (T t in domain)
{
U CurVal=elem(t);
if ((CurVal.CompareTo(CurMax) > 0)||(CurMax.CompareTo(default(U))==0))
{
CurmaxRow = t;
CurMax = CurVal;
}
}
return CurmaxRow;
}
}

[Vincenzo1968]

Corretto un BUG.
Iniettato il parallelismo
e chiudo qui anche io.

Per poter compliare occorre scaricare le parallel extension (PLINQ)
e includere la reference appena scaricata: system.threading nel progetto.
...


Mi dispiace scassarti ancora i cabasisi, ma ho, purtroppo, trovato un altro errore nel tuo programma.
Sostituendo, nel file matrix1, i numeri agli indici [0][0] e [999][999] con il numero 1.000.000, l'output del tuo programma è:

http://www.guidealgoritmi.it/images/ImgForums/contest05b_finale2_gugo.jpg

mentre, come mostra il programma di Daniele, dovrebbe essere:
http://www.guidealgoritmi.it/images/ImgForums/contest05b_finale2_daniele.jpg

Daniele è dunque, fino a questo momento, il vincitore. Vero è che il suo programma è più lento, ma fornisce sempre i risultati corretti(e ha il pregio di utilizzare solo la memoria strettamente necessaria).

Ciao.

P.S.
Daniele, ho modificato, nel tuo programma, il modo di visualizzare l'output. Spero non ti dispiaccia. Ciao.

[WarDuck]

Qualcuno per caso ha matrici più grosse delle 1000x1000? :sofico: Dovrei farci delle prove...

[DanieleC88]

P.S.
Daniele, ho modificato, nel tuo programma, il modo di visualizzare l'output. Spero non ti dispiaccia. Ciao.
No, ma figurati, è più chiaro così in effetti. ;)

[marco.r]

Mi dispiace scassarti ancora i cabasisi, ma ho, purtroppo, trovato un altro errore nel tuo programma.
Sostituendo, nel file matrix1, i numeri agli indici [0][0] e [999][999] con il numero 1.000.000, l'output del tuo programma è:

Uhm, strano, ho provato a riportare il codice di gugo in C++ (non ho un compilatore C# decente sulla mia macchina per provare direttamente il codice originale) e sembra dare risultati corretti :mbe:

[gugoXX]

Mi dispiace scassarti ancora i cabasisi, ma ho, purtroppo, trovato un altro errore nel tuo programma.


Ma che sono i cabasisi??? Immagino...
Quel che e' giusto e' giusto.
Ma perche' non debuggi il tuo? Non mi sembrava tanto distante.

Ecco l'indice corretto comunque.


class Program
{
static void Main(string[] args)
{
//int[,] vals = Randomizer.GetRandom2(5);
//Matrix mat = new Matrix(vals);

Matrix mat = new Matrix("Matrix1.txt");
Stopwatch sw = new Stopwatch();
sw.Start();
var toprint = mat.Ex8();
sw.Stop();

int x = toprint.x;
int y = toprint.y;
int z = toprint.z;

Console.WriteLine("Coordinate: {0},{1} - Dimensione {2} - Somma {3}", x, y, z, toprint.val);
Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);

int test = mat.Test(x, y, z);
Console.WriteLine("Test: {0}", test);

Console.ReadKey();
}
}

public class Matrix
{
public int Dim;
public int[,] Mat;

public void Save(string fname)
{
StreamWriter sw = new StreamWriter(@"C:\temp\" + fname);
sw.WriteLine("--{0}--", Dim);
for (int y = 0; y < Dim; y++)
{
for (int x = 0; x < Dim; x++)
{
sw.Write("{0} ", Mat[x, y].ToString());
}
sw.WriteLine();
}
sw.Close();
}

public Matrix(string fname)
{
Load(fname);
}

public Matrix(int[,] vals)
{
Mat = vals;
Dim = vals.GetLength(0);
}

public void Load(string fname)
{
StreamReader sr = new StreamReader(@"C:\temp\" + fname);
string fline = sr.ReadLine();
string mds = fline.Substring(2, fline.Length - 4);
Dim = int.Parse(mds);
Mat = new int[Dim, Dim];
for (int y = 0; y < Dim; y++)
{
string line = sr.ReadLine();
string[] valss = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
var valis = valss.Select(t => int.Parse(t)).ToArray();
Enumerable.Range(0, Dim).ForAll(x => Mat[x, y] = valis[x]);
}
sr.Close();
}

public struct Result
{
public int x;
public int y;
public int z;
public int val;
public Result(int ix, int iy, int iz, int ival)
{
x = ix;
y = iy;
z = iz;
val = ival;
}
}

public int Test(int x, int y, int d)
{
var dom = from ty in Enumerable.Range(y, d)
from tx in Enumerable.Range(x, d)
select Mat[tx, ty];
return dom.Sum();
}

public Result Ex8()
{
int limmem = ((Dim >> 1) + 2);
int[][,] Compl = new int[limmem][,];
Compl[1] = Mat;

var dom00 = from y in Enumerable.Range(0, Dim)
from x in Enumerable.Range(0, Dim)
select new Result(x, y, 1, Mat[x, y]);

Result rer = dom00.Max(t => t.val);
int rerval = rer.val;

for (int z = 2; z <= Dim; z++)
{
int mda = (z >> 1);
int ze1 = z & 1;
int md = mda + ze1;
bool ze1u1 = ze1 == 1;
int dimmz = Dim - z;

int[,] Complcur = null;
bool tobemem = z < limmem;
if (tobemem)
{
Complcur = Compl[z] = new int[dimmz+1, dimmz+1];
}
int[,] Complmda = Compl[mda];
int[,] Complmd = Compl[md];
Parallel.For(0, dimmz+1, y =>
{
int ymda = y + mda;
int ymd = y + md;
for (int x = 0; x <= dimmz; x++)
{
int cur = Complmd[x, y]
+ Complmda[x, ymd]
+ Complmda[x + md, y]
+ Complmd[x + mda, ymda];

if (ze1u1)
{
cur -= Mat[x + mda, ymda];
}

if (tobemem)
{
Complcur[x, y] = cur;
}
if (cur > rerval)
{
mut.WaitOne();
if (cur > rerval)
{
rerval = cur;
rer = new Result(x, y, z, cur);
}
mut.ReleaseMutex();
}
}
});
if (ze1u1) Compl[mda] = null;
}
return rer;
}

private Mutex mut = new Mutex();
}

public static class Extensor
{
public static void ForAll<T>(this IEnumerable<T> domain, Action<T> act)
{
foreach (T t in domain) act(t);
}

public static T Max<T, U>(this IEnumerable<T> domain, Func<T, U> elem) where U : IComparable<U>
{
T CurmaxRow = default(T);
U CurMax = default(U);
foreach (T t in domain)
{
U CurVal = elem(t);
if ((CurVal.CompareTo(CurMax) > 0) || (CurMax.CompareTo(default(U)) == 0))
{
CurmaxRow = t;
CurMax = CurVal;
}
}
return CurmaxRow;
}
}


Per quanto riguarda la memoria massima occupata, essa dovrebbe essere il volume del tronco di piramide quadrata di
base maggiore: (3/4Dim)(3/4Dim)
base minore: (1/2Dim)(1/2Dim)
altezza: (1/4Dim)

Ho trovato un metodo che garantirebbe prestazioni paragonabili e consumo di memoria molto piu' basso.
Nel calcolare le sottomatrici di dimensione Z, si puo' far uso delle sole sottomatrici di dimensione Z-1 e Z-2, con quindi
O(Z^2) sul consumo memoria e O(Z^3) sulle prestazioni.

[DanieleC88]

Ma che sono i cabasisi???
I cog**oni (ayin docet) :D

[WarDuck]

Cmq non è un problema divisibile strettamente in più sottoproblemi, se abbiamo una matrice 1000*1000 e la dividiamo in 4 sottomatrici quadrate, elaborandone una per volta non possiamo risolvere il problema, perché mancano tutte le intersezioni tra le 4 matrici.

[Vincenzo1968]

Se per il C# ci vuole il rullo di tamburi, per il C occorre la banda al completo:

Versione C (senza parallelismo);
http://www.guidealgoritmi.it/images/ImgForums/contest05new.jpg

Versione C# (con parallelismo):
http://www.guidealgoritmi.it/images/ImgForums/contest05gugo.jpg

Meno di tre secondi contro i diciassette della versione C#(che una volta eseguita, mi rallenta il sistema e mi tocca riavviare :cry: )

La macchina è questa:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM


e questo è il codice:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

// http://www.hwupgrade.it/forum/showthread.php?t=1799059

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
int **m;
int side;
} Array;

typedef struct tagResult
{
int row;
int col;
int size;
int sum;
} Result;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

pArray->side = GetArraySize(szFileName);
if ( pArray->side <= 0 )
{
printf("Errore nella lettura del file.\n");
return S_ERROR;
}

pArray->m = (int**)malloc(sizeof(int*)* pArray->side);
if ( pArray->m != NULL )
{
for ( x = 0; x < pArray->side; x++ )
{
pArray->m[x] = (int*)malloc(sizeof(int)* pArray->side);
if ( pArray->m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= pArray->side)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
pArray->m[riga][colonna] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int FindKadane(Array *pArray, Result *pRes)
{
int *pr;

int riga, colonna, dim, somma;

int riga1, colonna1, dim1;
int riga2, colonna2, dim2;

int z, i, x, y, w;
int t = 0;
int S = 0, s = 0, k, l, x1 = 0, x2 = 0, y1 = 0, y2 = 0, j;

pr = (int*)malloc(sizeof(int)*(pArray->side*pArray->side));
if ( !pr )
{
printf("Memoria insufficiente.\n");
return -1;
}

for( z = 0; z < pArray->side; z++ )
{
for( i = 0; i < pArray->side; i++ )
pr[i] = 0;

for( x = z; x < pArray->side; x++ )
{
t = 0;
s = 0;
j = 0;
k = 0; l = 0;
for( w = 0; w < pArray->side; w++ )
{
pr[w] = pr[w] + pArray->m[x][w];
t = t + pr[w];
if( t > s)
{
s = t;
k = w;
l = j;
}
if( t < 0 )
{
t = 0;
j = w + 1;
}
}
if( s > S )
{
if ( z - x == l - k )
{
S = s;
x1 = x;
y1 = k;
x2 = z;
y2 = l;
}
}
}
}

free(pr);

pRes->row = x2;
pRes->col = y2;
pRes->size = x1 - x2 + 1;
pRes->sum = S;

somma = 0;

riga1 = pRes->row - 5;
if ( riga1 < 0 )
riga1 = 0;
riga2 = pRes->row + 5;
if ( riga2 >= pArray->side )
riga2 = pArray->side - 1;

colonna1 = pRes->col - 5;
if ( colonna1 < 0 )
colonna1 = 0;
colonna2 = pRes->col + 5;
if ( colonna2 > pArray->side )
colonna2 = pArray->side - 1;

dim1 = pRes->size - 10;
if ( dim1 < 1 )
dim1 = 1;
dim2 = pRes->size + 10;
if ( dim2 > pArray->side )
dim2 = pArray->side;

for ( dim = dim1; dim <= dim2; dim++ )
{
for ( riga = riga1; riga <= riga2; riga++ )
{
for ( colonna = colonna1; colonna <= colonna2; colonna++ )
{
for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
somma += pArray->m[y][x];
}
}

if ( somma > pRes->sum )
{
pRes->sum = somma;
pRes->row = riga;
pRes->col = colonna;
pRes->size = dim;
}

somma = 0;
}
}
}

return 0;
}

int main()
{
clock_t c_start, c_end;
Array a;
Result res;
Stati stato;

char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1bis.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1tris.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix8.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix9.txt";

//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2bis.txt";

//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix3.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix5.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix6.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix7.txt";

c_start = clock();
stato = DFA(szFileName, &a);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}
c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

c_start = clock();
FindKadane(&a, &res);
c_end = clock();
printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", res.row, res.col, res.size, res.sum);
//printf("\nRiga1 -> %d\nColonna1 -> %d\nRiga2 -> %d\nColonna2 -> %d\nDimensione -> %d\nSomma -> %d\n", res.row1, res.col1, res.row2, res.col2, res.size, res.sum);
printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

return 0;
}


Grazie di cuore al Sig. Kadane che, parecchi anni or sono, inventò l'algoritmo(complessità = O(m^2n)):

http://www.cosc.canterbury.ac.nz/tad.takaoka/35950621.pdf

e tanti saluti e sono al C# :D

[Vincenzo1968]

Corretto un piccolo bug e migliorati leggermente i tempi(2.75 secondi):


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
int **m;
int side;
} Array;

typedef struct tagResult
{
int row;
int col;
int size;
int sum;
} Result;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

pArray->side = GetArraySize(szFileName);
if ( pArray->side <= 0 )
{
printf("Errore nella lettura del file.\n");
return S_ERROR;
}

pArray->m = (int**)malloc(sizeof(int*)* pArray->side);
if ( pArray->m != NULL )
{
for ( x = 0; x < pArray->side; x++ )
{
pArray->m[x] = (int*)malloc(sizeof(int)* pArray->side);
if ( pArray->m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= pArray->side)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
pArray->m[riga][colonna] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int FindKadane(Array *pArray, Result *pRes)
{
int *pr;

int riga, colonna, dim, somma;

int riga1, colonna1, dim1;
int riga2, colonna2, dim2;

int z, i, x, y, w;
int t = 0;
int S = 0, s = 0, k, l, x1 = 0, x2 = 0, y1 = 0, y2 = 0, j;

pr = (int*)malloc(sizeof(int)*pArray->side);
if ( !pr )
{
printf("Memoria insufficiente.\n");
return -1;
}

for( z = 0; z < pArray->side; z++ )
{
for( i = 0; i < pArray->side; i++ )
pr[i] = 0;

for( x = z; x < pArray->side; x++ )
{
t = 0;
s = 0;
j = 0;
k = 0;
l = 0;
for( w = 0; w < pArray->side; w++ )
{
pr[w] = pr[w] + pArray->m[x][w];
t = t + pr[w];
if( t > s)
{
s = t;
k = w;
l = j;
}
if( t < 0 )
{
t = 0;
j = w + 1;
}
}
if( s > S )
{
if ( z - x == l - k )
{
S = s;
x1 = x;
y1 = k;
x2 = z;
y2 = l;
}
}
}
}

free(pr);

pRes->row = x2;
pRes->col = y2;
pRes->size = x1 - x2 + 1;
pRes->sum = S;

somma = 0;

riga1 = pRes->row - 5;
if ( riga1 < 0 )
riga1 = 0;
riga2 = pRes->row + 5;
if ( riga2 >= pArray->side )
riga2 = pArray->side - 1;

colonna1 = pRes->col - 5;
if ( colonna1 < 0 )
colonna1 = 0;
colonna2 = pRes->col + 5;
if ( colonna2 >= pArray->side )
colonna2 = pArray->side - 1;

dim1 = pRes->size - 10;
if ( dim1 < 1 )
dim1 = 1;
dim2 = pRes->size + 10;
if ( dim2 > pArray->side )
dim2 = pArray->side;

for ( dim = dim1; dim <= dim2; dim++ )
{
for ( riga = riga1; riga <= riga2; riga++ )
{
if ( riga + dim > pArray->side )
break;
for ( colonna = colonna1; colonna <= colonna2; colonna++ )
{
if ( colonna + dim > pArray->side )
break;
for( y = riga; y < riga + dim; y++ )
{
for( x = colonna; x < colonna + dim; x++ )
{
somma += pArray->m[y][x];
}
}

if ( somma > pRes->sum )
{
pRes->sum = somma;
pRes->row = riga;
pRes->col = colonna;
pRes->size = dim;
}

somma = 0;
}
}
}

return 0;
}

int main()
{
clock_t c_start, c_end;
Array a;
Result res;
Stati stato;

char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1bis.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1tris.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix8.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix9.txt";

//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2bis.txt";

//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix3.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix5.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix6.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix7.txt";

c_start = clock();
stato = DFA(szFileName, &a);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}
c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

c_start = clock();
FindKadane(&a, &res);
c_end = clock();
printf("\nRiga -> %d\nColonna -> %d\nDimensione -> %d\nSomma -> %d\n", res.row, res.col, res.size, res.sum);
printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

return 0;
}

[marco.r]

deve avere altri bugs.
Cambiando qualche valore nella matrice da risultati sballati.

[Vincenzo1968]

deve avere altri bugs.
Cambiando qualche valore nella matrice da risultati sballati.

Dalle prove che ho fatto io non risultano. Puoi farmi qualche esempio?

Ciao

[marco.r]

Ho modificato un valore a caso della matrice, non so la posizione esatta per cui do il diff rispetto all'originale:

281c281
< 10 -5 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 -6 0 0 0 0 -7 0 0 0 0 0 10 1 0 0 0 0 0 0 -6 0 0 0 0 0 0 -9 0 0 -8 0 0 0 0 0 0 0 3 -2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -6 -2 0 0 0 0 0 6 0 0 0 0 -6 5 0 0 0 0 0 0 0 7 0 0 4 -5 -8 10 0 0 1 0 0 0 1 0 0 8 -4 -4 0 0 0 0 -7 0 0 0 0 0 -9 0 0 0 0 0 8 0 0 0 9 -8 9 4 0 0 -1 0 0 0 0 0 0 0 0 -10 0 0 -10 -10 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 4 -9 -9 0 3 6 0 0 0 0 0 0 0 0 0 0 -2 0 0 2 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 -8 8 0 8 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 2 0 0 0 0 -4 0 0 0 6 0 0 8 0 0 0 0 0 0 0 0 7 5 3 0 0 0 -7 0 -8 0 0 0 0 0 -1 0 0 0 9 0 4 0 -4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 9 0 4 0 0 0 -9 0 10 0 0 0 0 0 0 0 0 6 0 2 0 0 -4 0 -6 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 7 0 0 5 0 -6 0 0 0 -7 0 0 0 0 0 0 0 5 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 5 0 0 0 -1 -4 0 0 -9 0 -3 0 0 0 -1 0 0 0 0 0 0 0 0 -3 0 0 0 -7 0 0 0 -9 0 -1 0 0 0 0 -7 0 2 0 -2 0 -2 -7 0 9 0 0 0 0 0 0 0 0 -3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 10 0 -5 0 0 -9 0 0 -9 0 0 0 0 0 0 9 -8 -6 -5 0 0 -8 0 0 0 0 0 0 1 9 0 0 -8 0 0 0 0 0 0 0 0 0 4 0 0 0 -7 -10 0 0 6 0 0 -1 -7 0 -10 0 0 0 0 0 0 0 -4 -4 0 0 0 0 0 -4 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 3 0 3 0 0 -5 0 0 0 0 5 -9 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 5 0 0 0 -9 0 0 0 0 -8 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 -4 0 0 0 -7 0 8 0 0 -2 0 0 0 0 5 5 1 0 6 0 0 1 0 0 0 0 0 -9 0 10 0 0 0 0 0 0 0 0 0 -2 0 -4 0 0 0 0 2 0 0 0 0 0 10 0 0 0 -6 0 0 0 0 0 6 -10 0 0 0 0 0 -4 0 1 0 0 0 8 -5 2 0 0 0 0 0 -7 6 0 -8 0 0 0 0 0 0 0 0 2 0 0 0 -1 0 0 0 0 0 1 0 2 0 0 -1 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 -8 0 0 0 0 0 0 0 -8 9 0 0 0 0 0 4 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -6 3 0 8 0 -3 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 8 0 0 0 8 0 0 5 0 0 0 1 0 -10 0 0 0 0 0 -9 0 0 0 0 0 0 0 -10 0 0 -9 0 0 0 -5 0 0 0 4 0 -8 0 0 0 0 -3 0 0 1 0 0 0 0 0 0 10 0 -4 0 4 0 0 6 0 9 6 -3 0 0 0 -7 10 0 0 0 0 0 0 0 6 0 0 0 0 0 0 -4 0 0 0 0 -1 0 0 0 0 0 0 -7 0 0 0 0 0 -8 0 -9 -8 0 0 -3 0 2 0 0 0 0 -7 0 0 0 0 0 0 0 0 8 0 0 0 0 0 -1 0 6 0 0 0 0 0 0 0 0 0 0 -4
---
> 10 -5 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 -6 0 0 0 0 -7 0 0 0 0 0 10 1 0 0 0 0 0 0 -6 0 0 0 0 0 0 -9 0 0 -8 0 0 0 0 0 0 0 3 -2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -6 -2 0 0 0 0 0 6 0 0 0 0 -6 5 0 0 0 0 0 0 0 7 0 0 4 -5 -8 10 0 0 1 0 0 0 1 0 0 8 -4 -4 0 0 0 0 -7 0 0 0 0 0 -9 0 0 0 0 0 8 0 0 0 9 -8 9 4 0 0 -1 0 0 0 0 0 0 0 0 -10 0 0 -10 -10 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 4 -9 -9 0 3 6 0 0 0 0 0 0 0 0 0 0 -2 0 0 2 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 -8 8 0 8 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 2 0 0 0 0 -4 0 0 0 6 0 0 8 0 0 0 0 0 0 0 0 7 5 3 0 0 0 -7 0 -8 0 0 0 0 0 -1 0 0 0 9 0 4 0 -4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 9 0 4 0 0 0 -9 0 10 0 0 0 0 0 0 0 0 6 0 2 0 0 -4 0 -6 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 7 0 0 5 0 -6 0 0 0 -7 0 0 0 0 0 0 0 5 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 5 0 0 0 -1 -4 0 0 -9 0 -3 0 0 0 -1 0 0 0 0 0 0 0 0 -3 0 0 0 -7 0 0 0 -9 0 -1 0 0 0 0 -7 0 2 0 -2 0 -2 -7 0 9 0 0 0 0 0 0 0 0 -3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 10 0 -5 0 0 -9 0 0 -9 0 0 0 0 0 0 9 -8 -6 -5 0 0 -8 0 0 0 0 0 0 1 9 0 0 -8 0 0 0 0 0 0 0 0 0 4 0 0 0 -7 -10 0 0 6 0 0 -1 -7 0 -10 0 0 0 0 0 0 0 -4 -4 0 0 0 0 0 -4 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 3 0 3 0 0 -5 0 0 0 0 5 -9 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 5 0 0 0 -9 0 0 0 1200 -8 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 -4 0 0 0 -7 0 8 0 0 -2 0 0 0 0 5 5 1 0 6 0 0 1 0 0 0 0 0 -9 0 10 0 0 0 0 0 0 0 0 0 -2 0 -4 0 0 0 0 2 0 0 0 0 0 10 0 0 0 -6 0 0 0 0 0 6 -10 0 0 0 0 0 -4 0 1 0 0 0 8 -5 2 0 0 0 0 0 -7 6 0 -8 0 0 0 0 0 0 0 0 2 0 0 0 -1 0 0 0 0 0 1 0 2 0 0 -1 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 -8 0 0 0 0 0 0 0 -8 9 0 0 0 0 0 4 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -6 3 0 8 0 -3 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 8 0 0 0 8 0 0 5 0 0 0 1 0 -10 0 0 0 0 0 -9 0 0 0 0 0 0 0 -10 0 0 -9 0 0 0 -5 0 0 0 4 0 -8 0 0 0 0 -3 0 0 1 0 0 0 0 0 0 10 0 -4 0 4 0 0 6 0 9 6 -3 0 0 0 -7 10 0 0 0 0 0 0 0 6 0 0 0 0 0 0 -4 0 0 0 0 -1 0 0 0 0 0 0 -7 0 0 0 0 0 -8 0 -9 -8 0 0 -3 0 2 0 0 0 0 -7 0 0 0 0 0 0 0 0 8 0 0 0 0 0 -1 0 6 0 0 0 0 0 0 0 0 0 0 -4


Se provo con il tuo codice mi da sempre il risultato iniziale.

Riga -> 565
Colonna -> 232
Dimensione -> 410
Somma -> 2419

Il conto non e' sbagliato, ma non e' il valore ottimale.
A me risulta che dovrebbe essere

Riga 198, colonna 212 dimensione 476 ed ottenere una somma di 2573.

Allego il codice che uso per verificare se il risultato ha valore corretto

#include <iostream>
#include <vector>
#include <iterator>
#include <fstream>

using namespace std;
struct Matrix
{
public:
Matrix():_cols(0),_rows(0){}
Matrix(const char* filename );
Matrix(int rows, int cols );
int& operator()(int row,int col);
const int& operator()(int row,int col) const;
int rows() const { return _rows; }
int cols() const { return _cols; }
Matrix& operator= ( const Matrix& m );
private:
int _cols;
int _rows;
std::vector<int> matrix;
};



Matrix::Matrix( const char* filename )
{
std::ifstream in(filename);
string s;
in >> s;
s = s.substr( 2, s.size() - 4 );
_cols = atoi( s.c_str() );
_rows = _cols;
matrix.resize( _rows*_cols );
std::copy( istream_iterator<int>(in), istream_iterator<int>(), &matrix[0] );
}

Matrix::Matrix( int rows, int cols )
{
_cols = cols;
_rows = rows;
matrix.resize( rows*cols, 0 );
}

Matrix& Matrix::operator=( const Matrix& m )
{
if ( &m != this )
{
matrix.resize( m.matrix.size() );
copy( m.matrix.begin(), m.matrix.end(), matrix.begin() );
_rows = m._rows;
_cols = m._cols;

}

return *this;
}


int& Matrix::operator()(int i, int j)
{
return matrix[ i* _cols + j ];
}

const int& Matrix::operator()(int i, int j) const
{
return matrix[ i* _cols + j ];
}



int main(int argc, char** argv )
{
if ( argc != 5 )
{
cout << "Usage: " << argv[0] << " matrix row col size" << endl;
exit(1);
}

Matrix m(argv[1]);
int start_row = atoi(argv[2]);
int start_col = atoi(argv[3]);
int size = atoi(argv[4]);
int sum=0;
for ( int i = start_row ; i < start_row+size ; ++i )
{
for ( int j= start_col ; j < start_col+size ; ++j )
{
sum+= m(i,j);
}
}
cout << "The sum of the submatrix is " << sum << endl;
}


e una versione pseudo-becera dell'algoritmo di gugo che ho usato per calcolare il risultato ottimale (non avendo un compilatore C# sulla mia macchina).

#include <fstream>
#include <string>
#include <vector>
#include <iterator>
#include <iostream>
#include <time.h>
#include <sys/time.h>
#include <map>

using namespace std;


typedef int Size;
;
struct Matrix
{
Matrix():_cols(0),_rows(0){}
Matrix(const char* filename );
Matrix(int rows, int cols );
int& operator()(int row,int col);
const int& operator()(int row,int col) const;
int rows() const { return _rows; }
int cols() const { return _cols; }
Matrix& operator= ( const Matrix& m );
private:
int _cols;
int _rows;
std::vector<int> matrix;
};

Matrix::Matrix( const char* filename )
{
std::ifstream in(filename);
string s;
in >> s;
s = s.substr( 2, s.size() - 4 );
_cols = atoi( s.c_str() );
_rows = _cols;
matrix.resize( _rows*_cols );
std::copy( istream_iterator<int>(in), istream_iterator<int>(), &matrix[0] );
}

Matrix::Matrix( int rows, int cols )
{
_cols = cols;
_rows = rows;
matrix.resize( rows*cols, 0 );
}

Matrix& Matrix::operator=( const Matrix& m )
{
if ( &m != this )
{
matrix.resize( m.matrix.size() );
copy( m.matrix.begin(), m.matrix.end(), matrix.begin() );
_rows = m._rows;
_cols = m._cols;

}

return *this;
}


int& Matrix::operator()(int i, int j)
{
return matrix[ i* _cols + j ];
}

const int& Matrix::operator()(int i, int j) const
{
return matrix[ i* _cols + j ];
}

typedef int Size;

Matrix calculate2x2Matrices( const Matrix& m )
{
Matrix n( m.rows(), m.cols() );
for ( int i=0; i+1 < m.rows() ; ++i )
{
for ( int j=0 ; j+1 < m.cols() ; ++j )
{
n(i,j) = m(i,j) + m(i+1,j) + m(i,j+1) + m(i+1,j+1);
}
}
return n;
}



void solve( const Matrix& m, int& _bestRow, int& _bestCol, int& _bestSize, int& _bestValue )
{
int bestRow, bestCol, bestSize, bestValue;
bestRow = bestCol = 0;
bestSize = 1;
bestValue = m(0,0);

map<Size,Matrix*> sums;
sums[1] = new Matrix(m);
sums[2] = new Matrix(calculate2x2Matrices(m));


Matrix current_sums( m.rows(), m.cols() );

for ( int size = 3; size <= m.rows() ; ++size )
{
if ( size % 10 == 0 )
cerr << size << flush;
else
cerr << '.' << flush;

int sizea = size/2;
int sizeb = size - sizea;

const Matrix& a = *sums[sizea];
const Matrix& b = *sums[sizeb];


for ( int i=0; i <= m.rows() - size ; ++i )
{
for ( int j=0 ; j <= m.cols() - size ; ++j )
{
current_sums(i,j) = b(i,j) + a(i+sizeb,j) + a(i,j+sizeb) + b(i+sizea,j+sizea);

if ( sizea != sizeb )
current_sums(i,j) -= m(i+sizea ,j+sizea);
if ( current_sums(i,j) > bestValue )
{
// cout << "good!" << i << ' ' << j << " " << size << ' ' << current_sums(i,j) << endl;
bestRow = i;
bestCol = j;
bestSize = size;
bestValue = current_sums(i,j);
}
}
}
if ( size <= m.rows()/2 )
sums[size] = new Matrix(current_sums);
for ( map<Size,Matrix*>::iterator i = sums.begin(); i != sums.end() ; ++i )
{
if ( i->first < size/2 )
{
delete i->second;
sums.erase(i);
}

}
}

_bestRow = bestRow;
_bestCol = bestCol;
_bestSize = bestSize;
_bestValue = bestValue;

}


double deltaTime()
{
double d;
struct timeval tv;
static struct timeval lasttv = { 0 , 0 };
if (lasttv.tv_usec == 0 && lasttv.tv_sec == 0)
gettimeofday(&lasttv, NULL);
gettimeofday(&tv, NULL);
d = (tv.tv_usec - lasttv.tv_usec)/1000000.f
+ (tv.tv_sec - lasttv.tv_sec);
lasttv = tv;
return d;
}


int main(int argc, char** argv )
{
string filename;
if ( argc > 1 )
{
filename = argv[1];
}
else
{
filename = "matrix1.txt";
}
clock_t c_start, c_end;
// c_start = clock();
deltaTime();
Matrix m( argv[1] );
// c_end = clock();
// float time = ((float)(c_end - c_start))/CLOCKS_PER_SEC;
float time = deltaTime();
printf("File read completed in %5.5f seconds\n", time);


int row,col,size,value;
c_start = clock();
solve(m,row,col,size,value);
c_end = clock();
cout << "found solution in " << row << ' ' << col << " of size " << size << " and value " << value;
time = ((float)(c_end - c_start))/CLOCKS_PER_SEC;
printf(" in %5.5f seconds\n", time);
}

[Vincenzo1968]

Si, effettuando qualche altra prova ho verificato che il programma contiene ancora dei bug.

Il problema è che la versione originale dell'algoritmo di Kadane trova la sottomatrice rettangolare di somma massima.
Io ho cercato(senza riuscirci :cry: ) di adattarlo alla ricerca di sottomatrici quadrate.

Posto il codice con l'algoritmo originale(che, ripeto, trova la sottomatrice di somma massima rettangolare e non necessariamente quadrata). Se qualcuno vuole smanettarci un po'.

Sarebbe un peccato non riuscire ad adattarlo visti i tempi di esecuzione. La complessità è O(m^2 * n). Per m = n (come nel nostro caso), la complessità è, ovviamente, n^3.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
int **m;
int side;
} Array;

typedef struct tagResult
{
int row1;
int col1;
int row2;
int col2;
int sum;
} Result;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

pArray->side = GetArraySize(szFileName);
if ( pArray->side <= 0 )
{
printf("Errore nella lettura del file.\n");
return S_ERROR;
}

pArray->m = (int**)malloc(sizeof(int*)* pArray->side);
if ( pArray->m != NULL )
{
for ( x = 0; x < pArray->side; x++ )
{
pArray->m[x] = (int*)malloc(sizeof(int)* pArray->side);
if ( pArray->m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= pArray->side)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
pArray->m[riga][colonna] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int FindKadane(Array *pArray, Result *pRes)
{
int *pr;

int z, i, x, w;
int t = 0;
int S = 0, s = 0, k, l, x1 = 0, x2 = 0, y1 = 0, y2 = 0, j;

pr = (int*)malloc(sizeof(int)*pArray->side);
if ( !pr )
{
printf("Memoria insufficiente.\n");
return -1;
}

for( z = 0; z < pArray->side; z++ )
{
for( i = 0; i < pArray->side; i++ )
pr[i] = 0;

for( x = z; x < pArray->side; x++ )
{
t = 0;
s = 0;
j = 0;
k = 0;
l = 0;
for( w = 0; w < pArray->side; w++ )
{
pr[w] = pr[w] + pArray->m[x][w];
t = t + pr[w];
if( t > s)
{
s = t;
k = w;
l = j;
}
if( t < 0 )
{
t = 0;
j = w + 1;
}
}

// riga -> 138
// colonna -> 1
// dimensione -> 751
// somma -> 7997600

if( s > S )
{
S = s;
x1 = x;
y1 = k;
x2 = z;
y2 = l;
}
}
}

free(pr);

pRes->row1 = x2;
pRes->col1 = y2;
pRes->row2 = x1;
pRes->col2 = y1;
pRes->sum = S;

return 0;
}

int main()
{
clock_t c_start, c_end;
Array a;
Result res;
Stati stato;

//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1bis.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1tris.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix8.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix9.txt";

//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2bis.txt";

char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix3.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix5.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix6.txt";
//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix7.txt";

c_start = clock();
stato = DFA(szFileName, &a);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}
c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

c_start = clock();
FindKadane(&a, &res);
c_end = clock();
printf("\nRiga1 -> %d\nColonna1 -> %d\nRiga2 -> %d\nColonna2 -> %d\nSomma -> %d\n", res.row1, res.col1, res.row2, res.col2, res.sum);
printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

return 0;
}

:)

[Vincenzo1968]

...
Il conto non e' sbagliato, ma non e' il valore ottimale.
A me risulta che dovrebbe essere

Riga 198, colonna 212 dimensione 476 ed ottenere una somma di 2573.

Allego il codice che uso per verificare se il risultato ha valore corretto
...
e una versione pseudo-becera dell'algoritmo di gugo che ho usato per calcolare il risultato ottimale (non avendo un compilatore C# sulla mia macchina).
...


Io per verificare i risultati utilizzo il codice di Daniele che è risultato affidabilissimo.

[Vincenzo1968]

Penso di aver trovato la soluzione. Ho effettuato delle prove sul matricione e su un centinaio di piccoli file(matrici di dimensione 10x10), verificando i risultati col programma di Daniele.
I file di prova li creo con questo programmino:


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

int main()
{
FILE *fp;
char str[256];
char strnum[256];
char strFile[256];
int i, j, k;
int num;
int m = 10, n = 10;
int range_min = -100, range_max = 100;
int numFiles = 100;

srand( (unsigned)time( NULL ) );

for ( k = 1; k < numFiles; k++ )
{
strcpy(strFile, "C:\\Temp\\Contest5\\Files\\MyMatrix");
itoa(k, strnum, 10);
if ( k <= 9 )
strcat(strFile, "00");
else if ( k > 9 && k < 100 )
strcat(strFile, "0");
strcat(strFile, strnum);
strcat(strFile, ".txt");
fp = fopen(strFile, "a");

strcpy(str, "--10--\n");
fwrite(str, strlen(str), 1, fp);

for( i = 1; i <= m; i++ )
{
for( j = 1; j <= n; j++ )
{
num = (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min;
itoa(num, str, 10);
strcat(str, " ");
fwrite(str, strlen(str), 1, fp);
}
fwrite("\n", 1, 1, fp);
}

fclose(fp);

printf("File %s\n", strFile);
}

return 0;
}


Prima di postare il codice voglio effettuare delle altre prove(almeno un migliaio) per essere sicuro al 100%.

:)

[Vincenzo1968]

Il mio collega mi fa notare che, dal punto di vista pratico, è più utile trovare la sottomatrice rettangolare(che potrebbe anche essere quadrata).
Per esempio, nella manipolazione delle immagini, la sottomatrice rettangolare di somma massima rappresenta la cosidetta brightest part.
Un altro esempio è dato dalle statistiche nel campo socio-economico.

Per questi motivi posto la versione originale dell'algoritmo e tanti saluti e sono:

Questi i risultati sul matricione 1000x1000:
http://www.guidealgoritmi.it/images/ImgForums/contest05new2.jpg

e questo è il codice:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
int **m;
int side;
} Array;

typedef struct tagResult
{
int row1;
int col1;
int row2;
int col2;
int sum;
} Result;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

pArray->side = GetArraySize(szFileName);
if ( pArray->side <= 0 )
{
printf("Errore nella lettura del file.\n");
return S_ERROR;
}

pArray->m = (int**)calloc(pArray->side + 1, sizeof(int*));
if ( pArray->m != NULL )
{
for ( x = 0; x < pArray->side + 1; x++ )
{
pArray->m[x] = (int*)calloc(pArray->side + 1, sizeof(int));
if ( pArray->m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= pArray->side)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
pArray->m[riga + 1][colonna + 1] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int FindKadane(Array *pArray, Result *pRes)
{
int Somma;
int i,j,k,l,m,n,z,x,x1,x2,y1,y2,s,t;

int **column;

column = (int**)calloc(pArray->side + 1, sizeof(int*));
if ( column != NULL )
{
for ( x = 0; x < pArray->side + 1; x++ )
{
column[x] = (int*)calloc(pArray->side + 1, sizeof(int));
if ( column[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

m = pArray->side;
n = pArray->side;

x1 = 0; x2 = 0; y1 = 0; y2 = 0;
Somma = -999999999;

for( z = 1; z <= m; z++)
{
for( i = 1; i <= n; i++ )
column[z - 1][i] = 0;

for( x = z; x <= m; x++ )
{
t = 0;
s = -999999999;
k = 0;
l = 0;
j = 1;
for( i = 1; i <= n; i++ )
{
column[x][i] = column[x - 1][i] + pArray->m[x][i];
t = t + column[x][i];
if(t > s)
{
s = t; k = i; l = j;
}
if( t < 0 )
{
t = 0;
j = i + 1;
}
}


if( s > Somma )
{
Somma = s;
x1 = x;
y1 = k;
x2 = z;
y2 = l;
}
}
}

pRes->row1 = x2 - 1;
pRes->col1 = y2 - 1;
pRes->row2 = x1 - 1;
pRes->col2 = y1 - 1;
pRes->sum = Somma;

return 0;
}


int main()
{
clock_t c_start, c_end;
Array a;
Result res;
Stati stato;

char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";

c_start = clock();
stato = DFA(szFileName, &a);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}
c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

//printf("\n\npArray->m[1][1] -> %d\npArray->m[200][200] -> %d\n\n", a.m[1][1], a.m[200][200]);

c_start = clock();
FindKadane(&a, &res);
c_end = clock();
printf("\nRiga1 -> %d\nColonna1 -> %d\n\nRiga2 -> %d\nColonna2 -> %d\n\nSomma -> %d\n\n", res.row1, res.col1, res.row2, res.col2, res.sum);
printf("Tempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

return 0;
}

[Vincenzo1968]

E ci metto pure il carrico da undici:

http://www.guidealgoritmi.it/images/ImgForums/contest05new3.jpg


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
int **m;
int side;
} Array;

typedef struct tagResult
{
int row1;
int col1;
int row2;
int col2;
int sum;
} Result;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

pArray->side = GetArraySize(szFileName);
if ( pArray->side <= 0 )
{
printf("Errore nella lettura del file.\n");
return S_ERROR;
}

pArray->m = (int**)calloc(pArray->side + 1, sizeof(int*));
if ( pArray->m != NULL )
{
for ( x = 0; x < pArray->side + 1; x++ )
{
pArray->m[x] = (int*)calloc(pArray->side + 1, sizeof(int));
if ( pArray->m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= pArray->side)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
pArray->m[riga + 1][colonna + 1] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int FindKadaneSubCubic(Array *pArray, Result *pRes)
{
int Somma;
int i, j, k, l, m, n, kmin, x, z, x1, x2, y1, y2, s, t;
int min_prefix;

int **sum;
int **column;

column = (int**)calloc(pArray->side + 1, sizeof(int*));
if ( column != NULL )
{
for ( x = 0; x < pArray->side + 1; x++ )
{
column[x] = (int*)calloc(pArray->side + 1, sizeof(int));
if ( column[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

sum = (int**)calloc(pArray->side + 1, sizeof(int*));
if ( sum != NULL )
{
for ( x = 0; x < pArray->side + 1; x++ )
{
sum[x] = (int*)calloc(pArray->side + 1, sizeof(int));
if ( sum[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

m = pArray->side;
n = pArray->side;

for( i = 1; i <= m; i++ )
{
for( j = 1; j <= n; j++ )
{
column[i][j] = column[i - 1][j] + pArray->m[i][j];
sum[i][j] = sum[i][j - 1] + column[i][j];
}
}

x1 = 0; x2 = 0; y1 = 0; y2 = 0;
Somma = -999999999;

for( z = 1; z <= m; z++ )
{
for( i = 1; i <= n; i++)
column[z - 1][i] = 0;

for( x = z; x <= m; x++)
{
t = 0;
s = -999999999;
k = 0;
l = 0;
kmin = 0;
min_prefix = 0;

for( i = 1; i <= n; i++ )
{
t = sum[x][i] - sum[z - 1][i] - min_prefix;
if( t > s )
{
s = t;
k = kmin;
l = i;
}

if( sum[x][i] - sum[z - 1][i] < min_prefix )
{
min_prefix = sum[x][i] - sum[z - 1][i];
kmin = i;
}
}

if( s > Somma )
{
Somma = s;
x1 = x;
y1 = l;
x2 = z;
y2 = k + 1;
}
}
}

for ( x = 0; x < pArray->side + 1; x++ )
free(column[x]);
free(column);

for ( x = 0; x < pArray->side + 1; x++ )
free(sum[x]);
free(sum);

pRes->row1 = x2 - 1;
pRes->col1 = y2 - 1;
pRes->row2 = x1 - 1;
pRes->col2 = y1 - 1;
pRes->sum = Somma;

return 0;
}

int main()
{
clock_t c_start, c_end;
Array a;
Result res;
Stati stato;
int x;

char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";

c_start = clock();
stato = DFA(szFileName, &a);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}
c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

c_start = clock();
FindKadaneSubCubic(&a, &res);
c_end = clock();
printf("\nRiga1 -> %d\nColonna1 -> %d\n\nRiga2 -> %d\nColonna2 -> %d\n\nSomma -> %d\n\n", res.row1, res.col1, res.row2, res.col2, res.sum);
printf("Tempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

for ( x = 0; x < a.side + 1; x++ )
free(a.m[x]);
free(a.m);

return 0;
}


Grazie all'algoritmo ideato dai Sigg. Tamaki e Tokuyama, la complessità scende al di sotto di O(m^2 * n) e, quindi, nel caso m = n, sotto O(n^3).
:)

[Vincenzo1968]

Ecco, dopo il millesimo test e controllando ogni volta il risultato sia col programma di Daniele che con quello di Gugo, la versione per la ricerca delle sottomatrici quadrate:

http://www.guidealgoritmi.it/images/ImgForums/contest05bfinale.jpg


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
int **m;
int side;
} Array;

typedef struct tagResult
{
int row1;
int col1;
int row2;
int col2;
int sum;
} Result;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

pArray->side = GetArraySize(szFileName);
if ( pArray->side <= 0 )
{
printf("Errore nella lettura del file.\n");
return S_ERROR;
}

pArray->m = (int**)calloc(pArray->side + 1, sizeof(int*));
if ( pArray->m != NULL )
{
for ( x = 0; x < pArray->side + 1; x++ )
{
pArray->m[x] = (int*)calloc(pArray->side + 1, sizeof(int));
if ( pArray->m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= pArray->side)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
pArray->m[riga + 1][colonna + 1] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int FindKadaneSquareSubmatrix(Array *pArray, Result *pRes)
{
int Somma;
int i, t, m, n, z, x, y, s;

int riga, colonna, dim;

int **column;

column = (int**)calloc(pArray->side + 1, sizeof(int*));
if ( column != NULL )
{
for ( x = 0; x < pArray->side + 1; x++ )
{
column[x] = (int*)calloc(pArray->side + 1, sizeof(int));
if ( column[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

m = pArray->side;
n = pArray->side;

// somma dell'intero array
Somma = 0;
for( y = 1; y <= pArray->side; y++ )
{
for( x = 1; x <= pArray->side; x++ )
{
Somma += pArray->m[y][x];
}
}

pRes->sum = Somma;
pRes->row1 = 1;
pRes->col1 = 1;
pRes->row2 = m;
pRes->col2 = n;

// singoli elememti
for( y = 1; y <= pArray->side; y++ )
{
for( x = 1; x < pArray->side; x++ )
{
s = pArray->m[y][x];
if ( s > Somma )
{
Somma = s;
pRes->row1 = y;
pRes->col1 = x;
pRes->row2 = y;
pRes->col2 = x;
}
}
}

for ( z = 1; z <= m; z++ )
{
for ( i = 1; i <= n; i++ )
{
column[z][i] = column[z - 1][i] + pArray->m[z][i];
}
}

s = 0;
for ( dim = 2; dim <= pArray->side; dim++ )
{
for ( riga = 1; riga <= pArray->side - dim + 1; riga++ )
{
s = 0;
for ( x = 1; x <= dim; x++ )
{
s += column[riga + dim - 1][x] - column[riga-1][x];
}

if ( s > Somma )
{
Somma = s;
pRes->sum = s;
pRes->row1 = riga;
pRes->col1 = 1;
pRes->row2 = dim + 1;
pRes->col2 = dim + 1;
}

for ( colonna = x; colonna <= pArray->side; colonna++ )
{

t = column[riga + dim - 1][colonna - dim] - column[riga - 1][colonna - dim];
s += column[riga + dim - 1][colonna] - column[riga-1][colonna];
s -= t;

if ( s > Somma )
{
Somma = s;
pRes->sum = s;
pRes->row1 = riga;
pRes->col1 = colonna - dim + 1;
pRes->row2 = riga + dim - 1;
pRes->col2 = colonna;
}
}
}
}


return 0;
}


int main()
{
clock_t c_start, c_end;
Array a;
Result res;
Stati stato;

char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";

c_start = clock();
stato = DFA(szFileName, &a);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}
c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

c_start = clock();
FindKadaneSquareSubmatrix(&a, &res);
c_end = clock();
printf("\nRiga1 -> %d\nColonna1 -> %d\n\nRiga2 -> %d\nColonna2 -> %d\n\nSomma -> %d\n\n", res.row1, res.col1, res.row2, res.col2, res.sum);
printf("Tempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

return 0;
}

:D

[Vincenzo1968]

up

:bimbo: