Página 1 de 1

Free Pascal: No se me ocurre un algoritmo

Publicado: Lun Nov 08, 2010 2:24 am
por Mathias
Hola, tengo que hacer un trabajo en donde tengo declarada una matriz ( un array bidimensional) con letras al azar en donde me pueda mover libremente entre letra y letra con el teclado. El tema es que no se me ocurre como hacer cuando estoy seleccionando una letra, en un array todas las letras adyacentes que la rodean que sean iguales se guarden (su posición) en una lista como describiré abajo.
Por ejemplo:

A B D A D B A A
A A B D A A A A
B D D D A B B D
B B D A A B D D

La letra subrayada es la seleccionada con el teclado.
Las letras en negrita son las que son del mismo tipo y estan adyacentes a la seleccionada.

Todas las letras metidas en un array de tipo A B C D de dos dimensiones de donde puedo obtener los parámetros de la letra que seleccione
La interface ya esta hecha, pero al marcar una letra, tengo que mandar a un array de una dimensión con índices enteros que a su vez es del tipo este registro:
Posicion
fila : tamañofila que va de 1..max
columna : tamañocolumna que va de 1..max



a alguien se le ocurre como lo podría hacer? :?: :?: :?:

Re: Free Pascal: No se me ocurre un algoritmo

Publicado: Lun Nov 08, 2010 12:26 pm
por Pitufo
La solución que se me ocurre es un poco compleja, pero tal vez te sirva de base para llegar a algo más efectivo.

Partiríamos de una matriz duplicando la original, y reemplazaríamos por ceros y unos (simplemente por claridad, pues realmente no es necesario) los contenidos que coincidan y los que no coincidan con la letra seleccionada.

1.- En esa matriz, recorreríamos todas las celdas que contienen 1, aplicando sobre ellas una función que comprobaría si hay camino (continuidad de unos adyacentes) desde el elemento seleccionado por teclado al que estamos analizando. No parece simple, la complicación la tendremos en esta función, pero tal vez puede servir de algo la idea.

2.- Otra opción tal vez más simple, partiendo de la matriz de ceros y unos aplicar repetidamente (hasta que no cause cambios) una función que aplique un valor 2 a la letra inicial, indicando con ese valor que sí es adyacente, y luego vaya cambiando unos por doses a cada celda que contenga un uno y tenga adyacente un dos. Al final, dejar a cero los unos que no cambiaron y tendrás en doses y ceros el resultado.

Esto es si entendí el problema planteado, que interpreto que se trata de reconocer elementos iguales adjuntos y los adjuntos de sus adjuntos de forma recursiva, un interesante reto.

Re: Free Pascal: No se me ocurre un algoritmo

Publicado: Lun Nov 08, 2010 1:21 pm
por Mathias
Me gusto el tuyo, pusieron una sugerencia de como poder hacerlo:

Obtener Bloque

Un algoritmo posible consiste en manejar dos listas de posiciones: lista de pendientes y lista de visitadas, aparte del bloque (o lista) que queremos obtener como resultado.

El algoritmo es el siguiente:

1. Agregar la posición inicial a la lista de posiciones pendientes.
2. Mientras haya posiciones en la lista de pendientes, procesar cada posición de la siguiente manera:
1. Quitarla de la lista de pendientes
2. Agregarla a la lista de visitadas
3. Agregarla a la lista de posiciones que forma el bloque que estamos buscando
4. Agregar todas las posiciones adyacentes, que sean del mismo tipo del bloque que estamos armando, y que no hayan sido visitadas, a la lista de pendientes para procesarla más tarde.

voy a revisar tu procedimiento, porque este no me sale, el tema es que tendria que generar en dos listas que a su vez se dividen en filas y coolumnas, no me parece nada práctico. Podría pensarlo Poniendo IF THEN y ahí sumar y restar los parametros de la fila seleccionada (me llevsaría a una de al lado) en filas y comprobar si son iguales, si lo son, para adentro. Lo mismo para columnas. Pero esto no incluiría las letras que estan diagonalmente adyacentes, sino solamente arriba y abajo
Sería un algoritmo medio rebuscado

Re: Free Pascal: No se me ocurre un algoritmo

Publicado: Lun Nov 08, 2010 2:57 pm
por Pitufo
Me parece poco efectivo y difícil de seguir el procedimiento si tienes que trabajar con listas de posiciones pendientes y visitadas.Puedes recorrer todas con un par de bucles anidados (filas y columnas) y luego introducirlo todo en otro bucle cuya condición para finalizar sea no haber encontrado nuevas posiciones adyacentes a las anteriores.

Re: Free Pascal: No se me ocurre un algoritmo

Publicado: Mar Nov 09, 2010 7:26 am
por Mathias
te referis a meter todo en IF THEN busco a un costado, IF THEN busoc a otro costado, IF THEN arriba, IF THEN abajo?
asi lo hice, pero solo me quedan esas cuatro posiciones. como en esos if then agregue a pendiente las otras 4 podria hacer repetir esto con un FOR que haga variar al indice de las posiciones que analizan los IF (indices de los arreglos que contienen la posicon que vendria a ser como si fuera la del teclado) hasta la ultima. Pero me sale un error de ejecucion creo, porque analizaria y agregariaparametros que corresponden a fichas repetidas

Re: Free Pascal: No se me ocurre un algoritmo

Publicado: Mar Nov 09, 2010 9:06 am
por Pitufo
¿Estás buscando sólo los adyacentes a la posición actual que determinaste con el teclado, o de forma recursiva también los adyacentes a las casillas que ya has determinado previamente que también eran adyacentes? En el ejemplo que muestras, marcaste más letras "A" que las adyacentes a la posición del cursor.

Re: Free Pascal: No se me ocurre un algoritmo

Publicado: Mié Nov 10, 2010 8:52 am
por Mathias
La idea es que se marquen todas las letras que son del mismo tipo y estan adyacentes entre si, pero el bloque en donde esta la posicion.fila posicion.columna (el teclado) como esta en el ejemplo, por eso esta complicado, si no seria solo con los 4 IF mas alguna funcion limite (que detecte bordes) y un procedure agregar (que agrege a bloque) ya estaria
tenddria que repetir esto despues.

Ya hice el codigo pero me sale un error de ejecucion:

exited with:
exit code : 217

Le doy Alt + F5:


An unhandled exception occurred at $0040232B :
ERangeError : Range check error
$0040232B
$004016FF
$004051B6
$0040524F
$004058CF

No llega a armar el tablero (y no es por el tablero en si, porque lo arma si le saco el porcedimiento para obtener el bloque)

Re: Free Pascal: No se me ocurre un algoritmo

Publicado: Mié Nov 10, 2010 12:14 pm
por Pitufo
Mathias escribió:Ya hice el codigo pero me sale un error de ejecucion:

exited with:
exit code : 217

Le doy Alt + F5:


An unhandled exception occurred at $0040232B :
ERangeError : Range check error
$0040232B
$004016FF
$004051B6
$0040524F
$004058CF

No llega a armar el tablero (y no es por el tablero en si, porque lo arma si le saco el porcedimiento para obtener el bloque)
Sin ver el código fuente es difícil ver el error.

Haz dos bucles anidados recorriendo el eje X e Y con una copia de la matriz, y ve reemplazando sus valores por:

0: Letra no coincidente.
1: Letra coincidente.
2: Letra coincidente y adyacente.

El paso para determinar los valores "2" se ha de ejecutar repetidas veces, hasta que no encuentre novedades. Al comprobar si es adyacente a otras, has de tener en cuenta los límites de la matriz para no excederte, probablemente por ahí tienes el error.