[Vari] Contest 8: Compattamento Barionico

[Vincenzo1968]

La mia soluzione brute-force per il punto 1:



La mia macchina:

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

Microsoft Windows XP Professional (32 bit)
Service Pack 3

El codigo fuente:

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <malloc.h>

#define BUFFER_SIZE 4096

typedef struct tagPunti
{
	double A;
	double B;
	double C;
} Punti;

typedef struct tagRes
{
	Punti P1;
	Punti P2;
	double Distanza;
	int index1;
	int index2;
} Res;

typedef struct tagArray
{
	int dimensione;
	double dmax;
	Punti *m;
} Array;

typedef enum tagStati
{
	S_ERROR = -1, S0 = 0, S1, S2, S3, S4, S5, S6, S7, S8, S9
} Stati;


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

	unsigned char byteCR = 0xD; // Carriage Return
	unsigned char byteLF = 0xA; // Line Feed

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

	pArray->dimensione = 0;
	k = 0;
	c = *(buffer + k++);
	while ( 1 )
	{
		if ( c >= '0' && c <= '9' )
		{
			pArray->dimensione = pArray->dimensione * 10 + c - '0';
		}
		else if ( c == ' ' || c == '\t' )
		{
			j = 0;
			while ( c != byteLF )
			{
				c = *(buffer + k++);
				if ( c >= '0' && c <= '9' )
					szNum[j++] = c;
			}
			szNum[j] = '\0';
			pArray->dmax = atof(szNum);
			break;
		}
		else if ( c == '\n' )
		{
			break;
		}

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

	pArray->m = (Punti*)malloc(pArray->dimensione*sizeof(Punti));
	if ( !pArray->m )
	{
		printf("Memoria insufficiente.\n");
		fclose(fp);
		return S_ERROR;
	}

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

		if ( c == byteLF )
		{
			riga++;
			colonna = 0;
		}

		switch (stato)
		{
		case S0:
			j = 0;
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S2;
			}
			else if ( c == '.' )
			{
				szNum[j++] = c;
				stato = S3;
			}
			else if ( c == '-' || c == '+' )
			{
				szNum[j++] = c;
				stato = S1;
			}
			else if ( c == ' ' || c == '\t' )
			{
				while ( c == ' ' || c == '\t' )
				{
					c = *(buffer + k++);
					if ( k >= numread )
						break;
				}
				k--;
			}
			else if ( c == byteCR || c == byteLF )
			{
				// nada
			}
			else
			{
				printf("Errore: stato S0; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S1:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S2;
			}
			else if ( c == '.' )
			{
				szNum[j++] = c;
				stato = S3;
			}
			else
			{
				printf("Errore: stato S1; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S2:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
			}
			else if ( c == '.' )
			{
				szNum[j++] = c;
				stato = S4;
			}
			else if ( c == 'E' || c == 'e' )
			{
				szNum[j++] = c;
				stato = S5;
			}
			else if ( c == ' ' || c == '\t' || c == byteCR || c == byteLF )
			{
				szNum[j] = '\0';
				if ( colonna == 0 )
					pArray->m[riga].A = atof(szNum);
				else if ( colonna == 1 )
					pArray->m[riga].B = atof(szNum);
				else if ( colonna == 2 )
					pArray->m[riga].C = atof(szNum);
				colonna++;
				stato = S0;
			}
			else
			{
				printf("Errore: stato S2; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S3:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S6;
			}
			else
			{
				printf("Errore: stato S3; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S4:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S6;
			}
			else if ( c == 'E' || c == 'e' )
			{
				szNum[j++] = c;
				stato = S7;
			}
			else if ( c == ' ' || c == '\t' || c == byteCR || c == byteLF )
			{
				szNum[j] = '\0';
				if ( colonna == 0 )
					pArray->m[riga].A = atof(szNum);
				else if ( colonna == 1 )
					pArray->m[riga].B = atof(szNum);
				else if ( colonna == 2 )
					pArray->m[riga].C = atof(szNum);
				colonna++;
				stato = S0;
			}
			else
			{
				printf("Errore: stato S4; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S5:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S9;
			}
			else if ( c == '-' || c == '+' )
			{
				szNum[j++] = c;
				stato = S8;
			}
			else
			{
				printf("Errore: stato S5; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S6:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S6;
			}
			else if ( c == 'E' || c == 'e' )
			{
				szNum[j++] = c;
				stato = S7;
			}
			else if ( c == ' ' || c == '\t' || c == byteCR || c == byteLF )
			{
				szNum[j] = '\0';
				if ( colonna == 0 )
					pArray->m[riga].A = atof(szNum);
				else if ( colonna == 1 )
					pArray->m[riga].B = atof(szNum);
				else if ( colonna == 2 )
					pArray->m[riga].C = atof(szNum);
				colonna++;
				stato = S0;
			}
			else
			{
				printf("Errore: stato S6; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S7:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S9;
			}
			else if ( c == '-' || c == '+' )
			{
				szNum[j++] = c;
				stato = S8;
			}
			else
			{
				printf("Errore: stato S7; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S8:
		case S9:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S9;
			}
			else if ( c == ' ' || c == '\t' || c == byteCR || c == byteLF )
			{
				szNum[j] = '\0';
				if ( colonna == 0 )
					pArray->m[riga].A = atof(szNum);
				else if ( colonna == 1 )
					pArray->m[riga].B = atof(szNum);
				else if ( colonna == 2 )
					pArray->m[riga].C = atof(szNum);
				colonna++;
				stato = S0;
			}
			else
			{
				printf("Errore: stato S9; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;
		}

		if ( k >= numread )
		{
			numread = fread(buffer, 1, BUFFER_SIZE, fp);
			k = 0;
			x++;
		}
	}

	fclose(fp);

	return stato;
}

void Calcola(Punti P[], int dim, Res *pMin, Res *pMax)
{
	int x, y;
	double distanza, distanzaMin, distanzaMax;
	double diffA, diffB, diffC;

	distanzaMin = distanzaMax = -1;

	x = y = 0;

	while( x < dim - 1 )
	{
		y = x + 1;
		while( y < dim )
		{
			//distanza = sqrt( pow(P[x].A - P[y].A, 2.0) + pow(P[x].B - P[y].B, 2.0) + pow(P[x].C - P[y].C, 2.0) );
			diffA = P[x].A - P[y].A;
			diffB = P[x].B - P[y].B;
			diffC = P[x].C - P[y].C;
			distanza = diffA*diffA + diffB*diffB + diffC*diffC;

			if ( distanza < distanzaMin || distanzaMin == -1 )
			{
				distanzaMin = distanza;
				pMin->P1 = P[x];
				pMin->P2 = P[y];
				pMin->index1 = x;
				pMin->index2 = y;
			}
			if ( distanza > distanzaMax )
			{
				distanzaMax = distanza;
				pMax->P1 = P[x];
				pMax->P2 = P[y];
				pMax->index1 = x;
				pMax->index2 = y;
			}
			++y;
		}
		++x;
	}

	pMin->Distanza = sqrt( distanzaMin );
	pMax->Distanza = sqrt( distanzaMax );
}

int main()
{
	Stati stato;
	Array myArray;
	Res r1, r2;

	clock_t c_start, c_end;

	char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest 08 - Compattamento Barionico\\Coords\\Coords.dat";

	c_start = clock();
	stato = DFA(szFileName, &myArray);
	c_end = clock();
	printf("\nTempo impiegato per caricamento dati -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	c_start = clock();
	Calcola(myArray.m, myArray.dimensione, &r1, &r2);
	c_end = clock();

	printf("\nDistanza Min: P[%d] - P[%d] -> %.15lf\n", r1.index1, r1.index2, r1.Distanza);
	printf("\nDistanza Max: P[%d] - P[%d] -> %.15lf\n", r2.index1, r2.index2, r2.Distanza);
	printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	free(myArray.m);

	return 0;
}

[gugoXX]

Originariamente inviato da Vincenzo1968

Cosa rappresenta quell'uno dopo il diecimila nella prima riga del file?

E' un centomila... Comunque il primo uno è il secondo parametro, il lato del cubo di contenimento, quindi è il valore massimo che puo' assumere la coordinata di uno qualsiasi dei punti.
Non sara' sempre 1 pertanto, potrebbe essere anche 3.14 volendo.
Ma l'avatar cos'è? Un nuovo tipo di faccia dopo l'ennesima tortura medioevale?

[Vincenzo1968]

Originariamente inviato da gugoXX

E' un centomila... Comunque il primo uno è il secondo parametro, il lato del cubo di contenimento, quindi è il valore massimo che puo' assumere la coordinata di uno qualsiasi dei punti.
Non sara' sempre 1 pertanto, potrebbe essere anche 3.14 volendo.

Grazie mille

Ma l'avatar cos'è? Un nuovo tipo di faccia dopo l'ennesima tortura medioevale?

No, è il bassista dei mitici Kiss:

http://it.youtube.com/watch?v=HnqUAbGMjLI

http://it.youtube.com/watch?v=DWLpbc...eature=related

[VICIUS]

In sostanza per il primo punto si devono controllare tutte le coppie di punti presenti nel file e calcolare la distanza? Se è così è piuttosto facile da scrivere anche se se ho il sospetto che ruby impiegherà una vita per completare il file...

[gugoXX]

Originariamente inviato da VICIUS

In sostanza per il primo punto si devono controllare tutte le coppie di punti presenti nel file e calcolare la distanza? Se è così è piuttosto facile da scrivere anche se se ho il sospetto che ruby impiegherà una vita per completare il file...

Certo, diciamo che questa è la soluzione di base di riferimento.
Si spera poi di trovare algoritmi migliori.

[VICIUS]

Originariamente inviato da gugoXX

Certo, diciamo che questa è la soluzione di base di riferimento.
Si spera poi di trovare algoritmi migliori.

Ottimo. Ora sto provando a scrivere questa così ho qualcosa di corretto su cui basarmi.

[VICIUS]

Per ora sono arrivato a questo e come pensavo è di una lentezza disarmante.

Infinity = 1.0/0.0

class Point
  attr_reader :x, :y, :z
  
  def initialize(x, y, z)
    @x, @y, @z = x.to_f, y.to_f, z.to_f
  end
  
  def distance_from(other)
    # manca la radice
    (@x - other.x) ** 2 +
    (@y - other.y) ** 2 +
    (@z - other.z) ** 2
  end
  
  def to_s
    "(#{@x},#{@y},#{@z})"
  end
end


class Result
  attr_reader :a, :b, :dist
  
  def initialize(a, b, dist)
    @a, @b, @dist = a, b, dist
  end
  
  def to_s
    "#{a} -> #{b} = #{Math.sqrt(dist)}"
  end
end


def load_points_from_file(file_name)
  list = Array.new
  File.open(file_name, 'r') do |file|
    file.gets # ignora la prima riga
    while line = file.gets
      list.push Point.new(*line.split)
    end
  end
  
  list
end


def contest_9(list)
  min, max = Result.new(0, 0, Infinity), Result.new(0, 0, -Infinity)
  list.combination(2).each do |a,b|
    dist = a.distance_from b
    min = Result.new(a, b, dist) if dist < min.dist
    max = Result.new(a, b, dist) if dist > max.dist
  end
  
  [min, max]
end

list = load_points_from_file('Coords.txt')
puts contest_9(list)

Con soli 2000 punti impiega circa 7 secondi quindi non chiedetemi di provare con quello completo che non ho alcuna intenzione di fondere il pc

[rеpne scasb]

■

[Vincenzo1968]

Originariamente inviato da rеpne scasb

Accludo la mia versione:
...
Tempo per la creazione del software: meno di 30 minuti.
Algoritmo utilzzato: non e' la forza bruta.
Commento sul codice: e' scritto nel solito modo => incomprensibile
Commento sul contest: mi sarei aspettata qualcosa di meglio della forza bruta, cionci dove sei?

Io ho postato per primo quello a forza bruta in modo da seguire i criteri per la valutazione di cui si era parlato(e, cioè, prendere il rapporto fra il tempo della soluzione brute-force e quello della soluzione ottimizzata).

Addendum: a richesta, se interessa, accludero' una spiegazione dettagliata dell'algoritmo.

A me interessa.

P.S. Non mi pare ci siano bugs, ma nel caso ne troviate avvertitemi, grazie.

L'ho provato e funziona perfettamente:

[rеpne scasb]

■

[Vincenzo1968]

Per la mia soluzione ottimizzata ho ordinato codesto libro:

http://www.amazon.com/Computational-.../dp/0521649765

[rеpne scasb]

■

[Vincenzo1968]

Originariamente inviato da rеpne scasb

E vabbe'...il tempo che ti arriva il libro, lo leggi, lo assimili, pensi ad una soluzione ottimizzata, la sviluppi....e' arrivato sicuramente Natale!

Qualcosa in tempi piu' rapidi?

eh lo so.
Dove posso documentarmi? Qualche link? C'entrano qualcosa i diagrammi di Voronoi? E i KD-Tree?

[rеpne scasb]

■

[Vincenzo1968]

Originariamente inviato da rеpne scasb

Non saprei dirti, a naso mi pare di no. La mia attuale soluzione "ottimizzata", non e' nulla di particolare, e non servono libri o documentazione "particolare" per implementarla; non serve alcuna conoscenza matematica specifica.

La mia seconda soluzione ottimizzata (che non ho ancora pubblicato), sfrutta invece una proprieta' delle funzioni monotone crescenti. In questo caso sono necessarie alcune nozioni di matematica elementare.

C'entrano comunque gli alberi binari, giusto? (lo costruisci e successivamente lo linearizzi con Bin2Nor; è corretto?).

[rеpne scasb]

■

[Vincenzo1968]

Io provo coi kD-Trees utilizzando questa libreria:

http://code.google.com/p/kdtree/

[gugoXX]

Per ora sono qui.

ResMin : 70ms  Dist: 0.000366913641159708 Indexes: 22503-72620
ResMax : 1546ms  Dist: 1.70445415447397 Indexes: 72832-48483
1616ms

[Vincenzo1968]

Originariamente inviato da gugoXX

Per ora sono qui.

ResMin : 70ms  Dist: 0.000366913641159708 Indexes: 22503-72620
ResMax : 1546ms  Dist: 1.70445415447397 Indexes: 72832-48483
1616ms

Io invece sono qui:

[rеpne scasb]

■