CUPCAM 05

Tenemos un "súperapasionante" de #2, ¿alguien da más señores?

Salu2

Estaría bien, pero ahora mismo muchos estamos de exámenes

pues tambien me apunto al carro, ya veremos cuantos hago....

por cierto no sería mala idea como dicen por ahí arriba utilizar este thread para poner retos de programación por que me consta que hay bastante nivel de programadores por aqui.

editado:
creo que deberiamos de poner un lenguaje comun para todos, ¿que os parece java?

me parece bien cuando tenga un ratillo me pongo con el primero.

No te preocupes por la RAM no chupa nada.. amos no se como sera tu algoritmo, nosotros lo intentamos en la CUPCAM con teoria de grafos y es como ellos lo resolvieron despues.

Como es tu algoritmo mas o menos??? por que chupa tanta ram? proboca desbordamiento de la pila??? Las pruebas que pasaban ally eran de 6 fichas como mucho creo recordar y aunq lo hagas con algoritmos recursivos no deberia producir Stack Overflow.

PD: Estudias informatica no? en que curso y uni?

Aquí tenéis --> www.elcopias.com/domino.zip

#include <stdio.h>
#include <conio.h>

typedef struct ficha{

int laficha[2];

}
FICHA;

int crea_permutacion(int[], long double, int, long double);

void crea_jugada(int[], FICHA[], int[], int);

int comprueba_jugada(int[], int);

long double factorial(int);

int main(){

int n, k, p;
long double contador, fact_n;

printf("\n\t\t\t- SOLITARY DOMINO (by LoC0) -");

printf("\n\n\n\tIntroduce el numero de fichas:   ");
scanf("%d", &n);



FICHA fichas[n];
int permutacion[n];
int jugada[2*n], jugada_correcta, quedan_permutaciones;




for(k=0; k<n; k++)
{
	do{
		system("cls");
		printf("\n\t\t\t- SOLITARY DOMINO (by LoC0) -");
		printf("\n\n\n-Introduce el elemento (1) de la [ficha %d]: ", k+1);
		scanf("%d", &fichas[k].laficha[0]);

	}
	while(fichas[k].laficha[0]<0 || fichas[k].laficha[0]>6);

	do{
		system("cls");
		printf("\n\t\t\t- SOLITARY DOMINO (by LoC0) -");
		printf("\n\n\n-Introduce el elemento (2) de la [ficha %d]: ", k+1);
		scanf("%d", &fichas[k].laficha[1]);
	}
	while(fichas[k].laficha[1]<0 || fichas[k].laficha[1]>6);


}

for(k=0; k<n; k++)
	printf("\n\t%d %d", fichas[k].laficha[0], fichas[k].laficha[1]);




fact_n=factorial(n);

jugada_correcta=0;
quedan_permutaciones=1;
contador=0;

printf("\n\n\n\tEchando unas cuentecillas, por favor espere...");

while(quedan_permutaciones && !jugada_correcta)
	{

	quedan_permutaciones = crea_permutacion(permutacion, contador, n, fact_n);

	crea_jugada(permutacion, fichas, jugada, n);

	jugada_correcta = comprueba_jugada(jugada, n);

	contador++;

    }

if(jugada_correcta)		printf("\n\n\n\tSI, hay al menos una jugada posible con esas piezas");
else
    printf("\n\n\n\tNO, no se puede hacer ninguna jugada válida con esas piezas");


getch();

}

int crea_permutacion(int permutacion[], long double contador, int n, long double fact_n){
int valido=1, j, k, r, s, aux;

if(contador<=fact_n)
	{
		if(contador==0)
		{

			for(k=0; k<n; k++)
				permutacion[k]=k+1;
		}
		else
	    {
			j=n-1;

			while(permutacion[j-1]>permutacion[j])
				j--;

			k=n;

			while(permutacion[j-1]>permutacion[k-1])
				k--;

			aux=permutacion[j-1];
			permutacion[j-1]=permutacion[k-1];
			permutacion[k-1]=aux;

			r=n;
			s=j+1;

			while(r>s)    {
				aux=permutacion[r-1];
				permutacion[r-1]=permutacion[s-1];
				permutacion[s-1]=aux;

				r--;
				s++;

			}
		}

}
else
	valido=0;

return valido;

}

void crea_jugada(int permutacion[], FICHA fichas[], int jugada[], int n){

int h, c;

for(h=0, c=0; c<n; h=h+2, c++)
{
	jugada[h]=fichas[permutacion[c]-1].laficha[0];
	jugada[h+1]=fichas[permutacion[c]-1].laficha[1];

}

}

int comprueba_jugada(int jugada[], int n){
int valido=1, j, h;

j=0;
h=0;
while(j<n-1 && valido)    {
	if(jugada[h+1]!=jugada[h+2])                valido=0;

	j++;
	h=h+2;
}

return valido;

}

long double factorial(int numero){
long double res;

if(numero==0)        res = 1;
else
	res = numero*factorial(numero-1);

return res;

}

En resumen lo que hace el programa es ir generando permutaciones de fichas hasta que da con una judada correcta o hasta que haya probado las n! permutaciones.

Ej: Si se introducen las fichas 6-6, 6-5 y 1-6 por ejemplo, iría probando: 6-6 6-5 1-6, 6-5 1-6 6-6, etc... hasta dar con una jugada válida como: 1-6 6-6 6-5

Salu2

Juas. Este hilo no ha tenido mucho éxito (espero que sea por el tema exámenes...) Yo de momento no he tenido tiempo de intentar ningún otro.

En cuanto al problema 1, la parte de introducir las fichas la he hecho así por comodidad y para que quedara más "bonito", porque realmente tendría que leer (de un fichero o de la entrada de teclado) todo el "tocho" de datos.

En fin, en cuanto termine de faena me pondré con los siguientes y espero que todos esos grandes programadores de media-vida den la cara

Salu2

Solución al problema 8. Elijo Perl porque me parece absurdo que den a elegir 4 lenguajes que, para estos menesteres, son iguales (de incómodos). La gracia está en saber qué herramienta utilizar

#!/usr/bin/perl

while (<STDIN>) {
&nbsp;&nbsp;&nbsp;$cadena = <STDIN>;
&nbsp;&nbsp;&nbsp;chomp; chomp $cadena; quotemeta;
&nbsp;&nbsp;&nbsp;$count = 0;
&nbsp;&nbsp;&nbsp;while ($cadena =~ /$/) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$cadena =~ s/$//;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$count++;
&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;print "$count\n";
}

#18 No es necesaria la orientación a objetos, todos tienen punteros (o referencias), y todos son imperativos. Ninguno destaca respecto a los otros (quizá C por bajo nivel). Para eso que lo dejen en C++ y a correr.

Y si fuera algorítmica habría para elegir lenguajes funcionales y/o lógicos, dejarlo en imperativos es mermar la importancia del ingenio y la elegancia de la solución.

Pero bueno, a mí me da igual con Perl, perlcc te lo traduce a C xD

Para el que tenga curiosidad: http://pastebin.com/299518
PD: No sale entero.

No es necesaria la orientación a objetos, todos tienen punteros (o referencias), y todos son imperativos. Ninguno destaca respecto a los otros (quizá C por bajo nivel). Para eso que lo dejen en C++ y a correr.
Yo creo que C a secas sobra xD

Y si fuera algorítmica habría para elegir lenguajes funcionales y/o lógicos, dejarlo en imperativos es mermar la importancia del ingenio.
Estoy de acuerdo

Salu2

L0c0 estudias en la compluntese de Madrid?

Jejejeje, el 3 lo empecé yo el día que Alco sacó el segundo, con un planteamiento MUy parecido al de Kaod aunque lo deseché porque me parecía demasiado ineficiente (por el tema de probar en todos los puntos todos los posibles rectángulos)... El caso es que he probado el algoritmo de ka0d2 en mi P-II 450 y va muy rápido

En fin, como esperaba la comunidad está respondiendo de p.m. (y de manera proporcionada xD) Sólo espero que quede alguno para cuando tenga un ratillo libre...

Salu2