Búsqueda de patrón, o agrupar casillas

[Drumpi]

Hola a todos:

Normalmente estas cosas suelo pensarlas yo, o buscarlas por internet, pero se me echa el tiempo encima y no sé con qué palabras encontrar la solución a lo que busco.

El problema es el siguiente: tengo una cuadrícula que contiene números, normalmente del 1 al 100. Es normal poder encontrar varios grupos de números idénticos contiguos en cualquiera de las dos dimensiones. Lo que quiero es coger el mayor número de números contiguos en un grupo de 3x3 casillas, de 3x2, de 2x3, de 2x2, de 3x1, de 1x3, de 1x2 o de 2x1 para cambiarlos por un valor que represente ese grupo para ese número.
Es una especie de algoritmo de compresión. Necesito averiguar las dimensiones de dicho grupo, limitado a un máximo de 3 casillas de ancho y/o 3 de alto, pero no sé por dónde empezar a buscar, y no se me ocurre ningún algoritmo eficiente sin comprobar los grupos uno por uno o aprovechando el resultado de algún grupo que contenga a otro.

¿Algúna idea? Gracias.

[GameMaster]

yo miraria el algoritmo jpeg

[javu61]

Hola:

Te refieres a encontrar grupos de casillas que tengan en mismo valor en todas sus casillas, o buscar grupos de casillas que tengan los mismos valores en sus casillas que otro grupo, separado entre si:

1132213
1232221
2564162

En el primer caso hay en horizontal un grupo de 11, dos grupos con 22 o uno 22 y otro 222, en vertical un grupo con 11, otro 33 y dos 22, y en cuadrado uno de 2-2-2-2, aunque hay solapameinto entre grupos.

En el segundo caso hay tres grupos que contienen 1-2 en vertical.

Saludos

[otto_xd]

Sin tener ni **** idea y entrar en algoritmica se me ocurre lo siguiente.

Como tienes ElementosFila*Filas*Columnas elementos, recorreria un bucle de ElementosFila buscando coincidencias de 2 o 3 elementos. Almacenaria las posiciones
Despues comprobaria la posicion de dicho elemento sumando ElementosFila y comprobaria si son iguales, luego +1, luego ElementosFila*2...

Tendrias que tener listas para posibles matrices de 2x2 y de 3x3.

Para mi seria lo mas logico sin usar metodos propios de matrices, que seguro que se pueden usar y son mucho mas eficientes.

En el caso anterior seria

1132213
1232221
2564162

Fila 0
Almacenas en la de 2 [0] [3]
Compruebas que N+[0]==1 y como es cierto N+[1]==1, falso, no tengo matriz
Compruebas que N+[3]==2 y como es cierto N+[4]==2, verdadero, tengo matriz 2x2

Fila 1
Almacenas en la de 3 [3] y en la de 2 [3] [4]
Compruebas que 2N+[3]==2 NOP (descartas tb la de 2), compruebas que 2N+[4]==2 NO

Fila 2, ultima fila, no hay posible matriz

[dr_bacterio]

Yo optaría por ir fila a fila buscando valores iguales contiguos (sean estos números o sustituciones de números por el código que represente a un grupo),



Por ejemplo:
29131

La cuadrícula quedaría:
29132

Transponemos filas por columnas y aplicamos el mismo algoritmo:
29133

La cuadrícula quedaría:
29134

[JJdroid]

Mas que el algoritmo JPEG, uno de compresion sin perdida.

¿Quizas lo quieres para comprimir tiles? ¿Ya lo has pensado?

[Drumpi]

El algoritmo JPEG no me sirve. Hace tiempo le eché un vistazo, pero como dicen, produce pérdidas. Es un algoritmo basado en integrales, por lo que los cambios bruscos en los datos no los trata bien, y además, al suprimir parte de la información tiene una tendencia a igualar valores contiguos, y aquí cualquier modificación de los datos es perjudicial.

La idea del dr_Bacterio es elegante, pero transponer una matriz se me antoja costoso computacionalmente hablando, y más si tenemos en cuenta que cualquier acceso a los datos de dicha matriz son lentos (es una matriz unidimensional, que emula una bidimensional mediante una multiplicación y una suma), y más si hablamos de una matriz de 140x27 (y eso uno de los mapas pequeños.

La idea es coger un mapa de tiles y sustituir grupos de tiles repetidos contiguos por un solo tile más grande, por lo que debo modificar el valor de una posición, y poner a cero los que se le agrupen. De momento, el algoritmo que he hecho es una cosa tal que así


gtmg_tiles[0][0] = obtener_tile(gtmg_mapa, posx , posy , 0);
gtmg_tiles[1][0] = obtener_tile(gtmg_mapa, posx+1, posy , 0);
gtmg_tiles[2][0] = obtener_tile(gtmg_mapa, posx+2, posy , 0);
gtmg_tiles[0][1] = obtener_tile(gtmg_mapa, posx , posy+1, 0);
gtmg_tiles[1][1] = obtener_tile(gtmg_mapa, posx+1, posy+1, 0);
gtmg_tiles[2][1] = obtener_tile(gtmg_mapa, posx+2, posy+1, 0);
gtmg_tiles[0][2] = obtener_tile(gtmg_mapa, posx , posy+2, 0);
gtmg_tiles[1][2] = obtener_tile(gtmg_mapa, posx+1, posy+2, 0);
gtmg_tiles[2][2] = obtener_tile(gtmg_mapa, posx+2, posy+2, 0);

if (gtmg_tiles[0][1] == gtmg_tiles[0][0]) grupo12 = true; end
if (grupo12 && (gtmg_tiles[0][2] == gtmg_tiles[0][0])) grupo13=true; end

if (gtmg_tiles[1][0] == gtmg_tiles[0][0]) grupo21 = true; end
if (grupo21 && (gtmg_tiles[2][0] == gtmg_tiles[0][0])) grupo31=true; end

if (grupo12 && grupo21 && (gtmg_tiles[1][1] == gtmg_tiles[0][0])) grupo22=true; end

if (grupo13 && grupo22 && (gtmg_tiles[1][2] == gtmg_tiles[0][0])) grupo23=true; end
if (grupo31 && grupo22 && (gtmg_tiles[2][1] == gtmg_tiles[0][0])) grupo32=true; end

if (grupo23 && grupo32 && (gtmg_tiles[2][2] == gtmg_tiles[0][0])) grupo33=true; end

switch (true)
case grupo33: *tamx=3; *tamy=3; end
case grupo23: *tamx=2; *tamy=3; end
case grupo32: *tamx=3; *tamy=2; end
case grupo22: *tamx=2; *tamy=2; end
case grupo13: *tamx=1; *tamy=3; end
case grupo31: *tamx=3; *tamy=1; end
case grupo12: *tamx=1; *tamy=2; end
case grupo21: *tamx=2; *tamy=1; end
default: *tamx=1; *tamy=1; end
end //switch


Las primeras líneas obtienen 3x3 tiles del mapa. Luego compruebo si existen grupos pequeños y los uso para otras comprobaciones (grupo12 indica un grupo de 1 tile de ancho y 2 de alto, y uso ese valor para buscar un grupo de 1x3). El switch final me permite devolver mediante punteros el ancho y alto del grupo, según la prioridad de lo que busco. Es como un if-elsif-elsif-...-end pero entiendo que más óptimo (tengo entendido que algunos lenguajes sustituyen el elsif por if anidados que pueden ser menos rápidos).

De momento dejo este algoritmo, a falta de la prueba de rendimiento. Si los tiempos no son buenos lo tendré que sustituir más adelante.

Por cierto: gracias a todos. Aun tengo que estudiar un par de respuestas más que me habeis dado, y sigo abierto a sugerencias.