[Vari] Contest 5: Sottomatrici

[gugoXX]

Originariamente inviato da Vincenzo1968

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]

Originariamente inviato da cdimauro

La direttiva 4.

[Vincenzo1968]

Originariamente inviato da gugoXX

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]

Originariamente inviato da Vincenzo1968

[marco.r]

Originariamente inviato da Vincenzo1968

Ho risolto(grazie a Fibonacci ):



Col valore 10000 al posto del primo numero(-42):


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

[gugoXX]

Originariamente inviato da marco.r

Continua a non tornarmi qualcosa 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

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

Originariamente inviato da marco.r

Continua a non tornarmi qualcosa 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

Risolto:

#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 (scherzo, sto cercando di migliorare il codice. Alla fine spiegherò tutto).

[Vincenzo1968]

Originariamente inviato da ercand

Non ero sparito , 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]

Originariamente inviato da 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

...

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



e invece è




File Matrix5.txt:
Il risultato dovrebbe essere



e invece è




File Matrix6.txt:
Il risultato dovrebbe essere



e invece è

[gugoXX]

Originariamente inviato da Vincenzo1968

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]

Originariamente inviato da gugoXX

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]

Originariamente inviato da gugoXX

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]

Originariamente inviato da Vincenzo1968

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

Ti ringrazio anche della nuova misurazione.

[WarDuck]

Originariamente inviato da marco.r

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