[SOLUCIONADO] recorrido caballo

[Aleinshir]

hola estoy haciendo el recorrido del caballo en java es una clase que se encarga de crear el array terminado luego lo retorna y la interfaz que hare en jframe lo representara primero lo quise hacer con fuerza bruta pero no carga es un error logico o es por la propia caracteristica de java ya que hice uno parecido "parecido" en c y lo saca en un santiamen se nota tanto la dif entre java y c mi duda es mas sobre ello el codigo luego lo puedo optimizar este es el codigo

Código Java:

package tableroajedrez.caballo;
 
import java.util.Random;
 
/**
 *
 * @author aleinshir
 */
public class Kernel {
    
    private int Tablero[][];                                                        // Tablero de ajedre representado en una matriz
    private static int horizontal[] = new int[] {  2,  1, -1, -2, -2, -1, 1, 2 };                       // Movimientos posibles de manera horizonta
    private static int vertical[] = new int[]      { -1, -2, -2, -1,  1,  2, 2, 1 };                        // Movimientos posibles de manera vertical
    private int movimientos;                                                        // Movimientos realizados
    private boolean aux_mov;                                                        // Auxiliar de prueba
    private int prueba;                                                         // Variable para probar todos los movimientos
    private boolean auxiliar;                                                       // Auxiliar para saber si se soluciono el problema
    private int siguiente_mov;                                                      // Siguiente movimiento que hara el caballo
    private int errores;                                                            // Se asegura que el caballo no este atrapado
    private Random rand;                                                        // Numero aleatorio
    private boolean auxiliar_ex;
    private boolean auxiliar_listo;
    private int numero;
    /**
     * Inicializa el tablero y randomiza la clase "Random".
     */
    public Kernel() {
        this.Tablero = new int[8][8];
        rand = new Random(System.nanoTime());
        construir_array();
    }
    
    /**
     * 
     * Clase que inicial el kernel para determina el final del problema.
     * 
     * @param posicionH Posicion inicial vertical
     * @param posicionV Posicion inicial vertical
     * @return El tablero ya resuelto
     */
    @SuppressWarnings("empty-statement")
    public int [][] start(int posicionH, int posicionV) {
        do
            auxiliar_listo =  recorrido_completo(posicionH, posicionV);
        while (auxiliar_listo == false);
        return Tablero;
    }
    
    /**
     * 
     * @return True si esta completo el recorrido
     */
    private  boolean recorrido_completo(int posicionH, int posicionV) {
        
        auxiliar = true;
        for (movimientos = 1, errores = 0; movimientos <= 64 && auxiliar; movimientos++)    // Ciclo exterior
        {
            aux_mov = true;
            siguiente_mov = rand.nextInt(8);                                        // Determina el proximo movimiento
            for (prueba = 0; prueba < 8 && aux_mov; prueba++, siguiente_mov++, errores++)// Prueba todos los posibles movimientos
            {
                
                if (siguiente_mov == 8)                                         // Pasa al movimento 0 cuando llega al 8
                    siguiente_mov = 0;
                
                try 
                {
                    if (Tablero[posicionH + horizontal[siguiente_mov]][posicionV + vertical[siguiente_mov]] == 0)
                    {
                        Tablero[posicionH][posicionV] = movimientos;
                        
                        errores = 0;
                        aux_mov = false;
                        posicionV += vertical[siguiente_mov] ;
                        posicionH += horizontal[siguiente_mov] ;
                    }
                }
                catch(ArrayIndexOutOfBoundsException e)
                {
                    
                }
            }
            
            if (errores >= 8)                                                   // Si hay mas de 8 errores corta el recorrido
                auxiliar =false;
        }
        
        return movimientos >= 64;                                               // True si hizo los 64 movimiento
    }
    
    /**
     * 
     * Construye el array dandole 0 (no necesario en java pero es mejor inicializarlo.
     */
    private void construir_array() {
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                Tablero[i][j] = 0;
            }
        }
    }
}
 

use un manejo de excepciones trate de hacerlo asi porque era mas "estetico"
por cierto este es el de c

Código C:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
 
#define TAMANIOV 12                                     // Altura del tablero
#define TAMANIOH 12                                     // Anchura del tablero
 
int despliega_tablero(const int tablero[][TAMANIOV]);
int llamar(int posicionH, int posicionV, int intento);
 
int main()
{
    srand(time(NULL));
    int posicionH, posicionV;
    scanf("%d%d", &posicionH, &posicionV);
    posicionH += 2;
    posicionV += 2;
    int i, intento = 0;
    for (i = 0; i == 0;)
    {
        intento++;
        if (llamar(posicionH, posicionV, intento) == 1)
        {
            intento = 0;
        }
    }
    system("pause");
    return 0;
}
 
int llamar(int posicionH, int posicionV, int intento)
{
    int Tablero[TAMANIOH][TAMANIOV] = { 0 };
    int horizontal[8] = { 02, 01, -1, -2, -2, -1, 1, 2 };
    int vertical[8] =   { -1, -2, -2, -1, 01, 02, 2, 1 };
    int movimientos, errorlevel, almacenaH, almacenaV;
    int siguiente, fun;
    for  (movimientos = 1, errorlevel = 0; movimientos != 65;)
    {
         siguiente = rand() % 7;
         for (fun = 0; fun < 8; siguiente++, fun++)
         {
             if (siguiente == 8)
                 siguiente = 0;
             if (Tablero[posicionH + horizontal[siguiente]][posicionV + vertical[siguiente]] == 0)
             {
                 errorlevel = 0;
                 Tablero[posicionH][posicionV] = movimientos;
                 almacenaH = posicionH;
                 almacenaV = posicionV;
                 posicionH += horizontal[siguiente];
                 posicionV += vertical[siguiente];
                 if (posicionH == 0 || posicionH == 1 || posicionV == 0 || posicionV == 1)
                 {
                     Tablero[posicionH][posicionV] = 1;
                     posicionH = almacenaH;
                     posicionV = almacenaV;
                     continue;
                 }
 
                 if (posicionH == 10 || posicionH == 11 || posicionV == 10 || posicionV == 11)
                 {
                     Tablero[posicionH][posicionV] = 1;
                     posicionH = almacenaH;
                     posicionV = almacenaV;
                     continue;
                 }
                 movimientos++;
                 break;
             }
         }
        errorlevel++;
        if (errorlevel >= 8)
           break; 
 
    }
 
    if (movimientos >= 64)
    {
        system("cls");
        despliega_tablero(Tablero);
        printf("movimientos = %d\nintentos = %d\n", movimientos, intento);
        system("pause");
        return 1;
    }
    else
    {
        return 0;
    }
 
 
}
 
int despliega_tablero(const int tablero[][TAMANIOV])
{
     int columna, fila;
     for (columna = 2; columna < 10; columna++)
     {
         for(fila = 2; fila < 10; fila++)
         {
                  if( tablero[columna][fila] == 0)
                      printf("%3s", "0" );
                  if(tablero[columna][fila] != 0)
                      printf("%3d", tablero[columna][fila]);
         }
         printf("\n");
     
     }
     return 0;
}
 

//**
como ven arregle el problema usando un array mas grande (12x12) el cual daba para un margen de "error" luego pense que podia usar la posicion si esta era menor que 0 no lo ejecutaba y si era mayor que 7 igual pero como ya habia implementado aquel ah y tambien pense que quizas funcionaria aprobechandome del desplazamiento de c (eso de que un array de 8x8 i[8][0] si le quitas 2 a 0 este se transforma en i[7][6] pero no me gusto (ademas que en java no se puede) gracias de adelantado
PD: si quieren ignoran todo despues del //** ya que no tiene que ver a mi pregunta :D
PD de la PD: seguro algunos me dicen que es malo usar break por eso de la programacion estructurada etc pero cuando hice el code no lo sabia xd y me dio lala corregirlo en java si use una variable de "escape"

[Xerelo]

¿Podrías explicar de otra forma lo que hace tú código? Usar puntos y comas ayudaría.

Yo no me he enterado de nada.

[ipraetoriux]

Iniciado por Xerelo

Yo no me he enterado de nada.

jajajaja, ya somos dos.
.

[Aleinshir]

Lo siento, escribi algo rapido.

De nuevo:

El codigo java (el primero):
Es una clase que hice, la cual crea un arreglo que contiene todo el recorrido del caballo ya resuelto (enumera del 1 al 64 los movimientos a seguir). El problema: Tarda mucho en resolverlo.

El codigo C (el segundo):
Es uno que cree hace ya tiempito, resolvia el recorrido y luego lo mostraba, la manera que se me ocurrio de resolverlo fue llenar con 2 arreglos mas de cada lado para saber cuando se desbordaba (no me se explicar muy bien, pero se nota en el codigo ya que es 12x12 en vez de 8x8). Este se ejecuta bastante rapido (casi instantaneo) apesar de que usa la fuerza bruta.

Mi pregunta:
¿Hice algo malo en el codigo de java?, ¿porqué este tarda mucho mas? o ¿Es por el hecho de que C es un lenguaje compilado y java interpretado?.

Post Data: Gracias por tu tiempo y por prestar atencion a una pregunta tan desordenada (es que lo hice en la mañana como a las 3 am xd)

[HackmanC]

Hola,

Lo que no me queda claro a mi en lo personal, es ¿cual es tu pregunta específicamente? Hasta ahora que mostraste tu segundo mensaje creo que posiblemente lo que deseas es optimizar el código.

Posiblemente te pueda ser de alguna ayuda ...

Primero, en tu código en lenguaje C se produce un ciclo infinito por lo cual no pude probar que realmente funcionara y que me mostrara por lo menos algún resultado.

Código:

 for (i = 0; i == 0;)
	{
		intento++;
		if (llamar(posicionH, posicionV, intento) == 1)
		{
			intento = 0;
		}
	}

Ahora, en tu código Java, después de un par de minutos sin que mostrara ningún resultado me aburrí y detuve el proceso. Pero aún así pude observar que aproximadamente la mitad del tiempo lo consume el try/catch. Se producen tantos ArrayIndexOutOfBoundsException que la mayor parte del tiempo en esa sección del código.

Código:

				try 
				{
					if (Tablero[posicionH + horizontal[siguiente_mov]][posicionV + vertical[siguiente_mov]] == 0)
					{
						Tablero[posicionH][posicionV] = movimientos;
						
...					}
				}
				catch(ArrayIndexOutOfBoundsException e)
				{
					
				}

Ahora, ¿que significa esto?

Java tiene un mecanismo de try/catch como C++, pero C no tiene ningún mecanismo de este tipo, el equivalente de un ArrayIndexOutOfBoundsException en C es nada, es decir, en C posiblemente estoy escribiendo en un area de la memoria inválida y ni cuenta me voy a dar por la misma naturaleza del lenguaje C. En el mejor de los casos voy a obtener un Invalid Address Write. Pero ese try/catch tiene su precio en la velocidad del código que procesa.

Hay tres tipos de errores en programación, el primero y el mas fácil de descubrir es el error sintáctico, es cuando escribes mal el wihle{} o el fro{} y el compilador muestra error (en tu código no se encuentran de este tipo de errores). El segundo tipo es el error lógico, es por el ejemplo cuando el resultado de una operación tira una división entre 0, y al correr el programa se detiene porque encuentra algún error (en tu código pareciera que no hay muchos errores de este tipo, solo ArrayIndexOutOfBoundsException, que aunque no lo creas son errores, el try/catch no es una solución a que tus indices no los calculaste bien).

El tercer tipo es el mas complicado, es que no hay errores sintácticos ni lógicos, pero tu programa no hace lo que debe hacer, no logra el resultado esperado, puede ser que se ejecute pero no funciona porque no logra el fin que se espera.

Al parecer en tu código si está sucediendo eso, tanto en C (ciclo infinito) como en Java (ArrayOutOfBoundsException). Primero corrige eso, cuando tu programa haga lo que tiene que hacer entonces preocúpate que lo haga rápido, de otra forma no tiene sentido. No sirve de nada que tu programa corra a la velocidad de la luz si no logra el resultado esperado.

Saludos,

[Aleinshir]

Iniciado por HackmanC

Primero, en tu código en lenguaje C se produce un ciclo infinito por lo cual no pude probar que realmente funcionara y que me mostrara por lo menos algún resultado.

Respuesta:
Lo acabo de reproducir y si tiene fin, lo que pasa es que el codigo te pide la posicion inicial, prueba abriendolo de nuevo colocas 0 (enter) y 0 (enter) (son las cordenadas de inicio lo que pasa es que no puse un mensaje indicando al usuario) para que el programa empiece en la esquina superior derecha

Iniciado por HackmanC

en C posiblemente estoy escribiendo en un area de la memoria inválida y ni cuenta me voy a dar por la misma naturaleza del lenguaje C.

Respuesta:
Con respecto a eso, el array es de 12x12 de forma que aun si escribe escribiria en un area reservada

Iniciado por HackmanC

Al parecer en tu código si está sucediendo eso, tanto en C (ciclo infinito) como en Java (ArrayOutOfBoundsException). Primero corrige eso, cuando tu programa haga lo que tiene que hacer entonces preocúpate que lo haga rápido, de otra forma no tiene sentido. No sirve de nada que tu programa corra a la velocidad de la luz si no logra el resultado esperado.

Respuesta:
Ya lo de C te explique arriba (tienes que introducir la posicion inicial) respecto a java si ocurre ya que si le bajas la "meta" por ejemplo en vez de hacer los 64 movimientos que el programa se ejecute a los 20 el programa si termina y lo logra (osea si llega al objetivo). Lo que me da a pensar que el programa se ejecuta muy lento y no ocurre ninguna combinacion que logre los 64 movimientos.

[HackmanC]

Hola,

Pues bueno, en mi opinión personal, si tu dices que no se produce un ciclo infinito en el ciclo for que marqué en rojo, por que la variable i nunca cambia de valor, y la condición dice que se repita mientras i == 0, como puedo contradecirte.

Iniciado por Aleinshir

... Con respecto a eso, el array es de 12x12 de forma que aun si escribe escribiria en un area reservada ...

Lo cual solo me indica que no estás seguro si escribe en o no fuera del arreglo.


Te expreso solamente mi opinión personal, aunque todavía sigo con la duda del cual es tu pregunta realmente.

¿Quieres optimizarlo? Ya te indique el el try/catch está consumiendo aproximadamente 50% del tiempo, si lo quitas posiblemente el código va a ser mas rápido. Una vez estés seguro de que no suceden excepciones en ese código puedes pasar a optimizar otras cosas.

¿Quieres saber si C es mas rápido que Java? Positivamente, en la mayoría de los casos C va a ser mas rápido que Java porque no es lo mismo, ni hacen lo mismo. En tu código en lenguaje C no hay validación si se salió fuera del rango permitido en la matriz, en Java si verifica eso, el índice fuera del rango.

Pero no creas que Java va a ser demasiado lento en comparación con C, simplemente tu código no es el mejor ejemplo para esta comparación, ni lo mas mínimo, donde evidentemente tuviste que subirle el tamaño a la matriz en C porque no estabas seguro si los índices se salían del rango o no, mientras que en Java te muestra claramente que sí se sale (si le pones un print en el catch).

En lo personal, me encanta el lenguaje C pero nunca voy a compararlo con Java, con el lenguaje C estás manipulando el procesador y la memoria casi directamente, mientras que Java hace mucho mas que simplemente eso.

Esa es simplemente mi opinión al respecto,

Saludos,

[Aleinshir]

Iniciado por HackmanC

Hola,

Pues bueno, en mi opinión personal, si tu dices que no se produce un ciclo infinito en el ciclo for que marqué en rojo, por que la variable i nunca cambia de valor, y la condición dice que se repita mientras i == 0, como puedo contradecirte.



Lo cual solo me indica que no estás seguro si escribe en o no fuera del arreglo.


Te expreso solamente mi opinión personal, aunque todavía sigo con la duda del cual es tu pregunta realmente.

¿Quieres optimizarlo? Ya te indique el el try/catch está consumiendo aproximadamente 50% del tiempo, si lo quitas posiblemente el código va a ser mas rápido. Una vez estés seguro de que no suceden excepciones en ese código puedes pasar a optimizar otras cosas.

¿Quieres saber si C es mas rápido que Java? Positivamente, en la mayoría de los casos C va a ser mas rápido que Java porque no es lo mismo, ni hacen lo mismo. En tu código en lenguaje C no hay validación si se salió fuera del rango permitido en la matriz, en Java si verifica eso, el índice fuera del rango.

Pero no creas que Java va a ser demasiado lento en comparación con C, simplemente tu código no es el mejor ejemplo para esta comparación, ni lo mas mínimo, donde evidentemente tuviste que subirle el tamaño a la matriz en C porque no estabas seguro si los índices se salían del rango o no, mientras que en Java te muestra claramente que sí se sale (si le pones un print en el catch).

En lo personal, me encanta el lenguaje C pero nunca voy a compararlo con Java, con el lenguaje C estás manipulando el procesador y la memoria casi directamente, mientras que Java hace mucho mas que simplemente eso.

Esa es simplemente mi opinión al respecto,

Saludos,

Waa lo siento, mi error xd. Si tienes razon es un ciclo infinito, lo que sucede es que pense que te referias al trozo de codigo que ejecutaba el caballo y como si la consola se quedara "pensando" sin mostrar nada, fue mi error xd no lei bien tu respuesta.

Con respecto a la pregunta efectivamente mi duda es esa perdida de velocidad que tiene java (gracias por resolver mi duda con respecto a el try/catch) asi que es por culpa de eso que se ejecuta mas lento... pero yo aplique otro metodo e igual tardaba en mostrar el resultado, este es el que aplique:
en vez de excepciones use:

Código Java:

if (posicionH + horizontal[siguiente_mov] > 0 && posicionV + vertical[siguiente_mov] < 8 && posicionV + vertical[siguiente_mov] > 0 && posicionH + horizontal[siguiente_mov] < 8)
{
if (Tablero[posicionH + horizontal[siguiente_mov]][posicionV + vertical[siguiente_mov]] == 0)
                    {
                        Tablero[posicionH][posicionV] = movimientos;
                       
                        errores = 0;
                        aux_mov = false;
                        posicionV += vertical[siguiente_mov] ;
                        posicionH += horizontal[siguiente_mov] ;
                    }
}
 

asi evitando de antemano un posible error e igual tarda bastante...

PD: Si es un ciclo infinito, pero es porque cuando le das enter o cualquier tecla el te muestra otra forma de resolverlo (era la intencion). Si muestra resultado demostrando que funciona, ahora que el programa nunca termina hasta cerrarlo con la x es cierto.

[HackmanC]

Hola,

Iniciado por Aleinshir

... lo que sucede es que pense que te referias al trozo de codigo que ejecutaba el caballo y como si la consola se quedara "pensando" sin mostrar nada, ...

Básicamente el problema era para los que quisieran probar tu código, como en mi caso, no pude hacer un verdadero "Profile" de cuanto tiempo y en donde se tarda más, porque pide los datos y no sale de la aplicación normalmente. Aunque era algo que se puede corregir fácilmente es algo que toma tiempo hacer.

Iniciado por Aleinshir

... Con respecto a la pregunta efectivamente mi duda es esa perdida de velocidad que tiene java (gracias por resolver mi duda con respecto a el try/catch) asi que es por culpa de eso que se ejecuta mas lento...

Ahora que estamos mas claros de que se trata, efectivamente Java en la mayoría de los casos va a ser un poco mas lento que el lenguaje C, pero no demasiado.

Aún cuando quitaste el Exception, que por definición son caros a nivel de velocidad, todavía no va a ser más rápido que un acceso directo a la memoria, que seguramente se trata con una sola instrucción del procesador como el código que genera el lenguaje C.

El motivo es que Java va a verificar que la memoria no se corrompa tan fácilmente y va a hacer otras operaciones dependiendo del tipo de programa, como cualquier otro lenguaje avanzado y no tan básico como C.

Saludos,