Problema matemático binario

GreyShock

Unos colegas que estudian telecos vinieron a pedirme consejo sobre un ejercicio que les propusieron en clase. El caso, es que me moló tanto que me he viciado y estoy tratando de optimizar cada vez más el resultado.

Antes de nada, os expongo el problema.

Simulando al juego de hundir la flota, sobre un tablero de 14x14 se presentan 10 barcos.
Hay un barco de 4, dos barcos de 3, tres barcos de 2 y cuatro barcos de 1.

Los barcos de 2 pueden aparecer tanto en horizontal, como en vertical.

Los barcos de 3 pueden aparecer tanto rectos, en horizontal y vertical; o en forma de "L", con sus cuatro orientaciones posibles.

El barco de 4 puede adoptar cualquier forma de las que puede adoptar una ficha de tetris, con todas sus orientaciones de rotación. Es decir: Rectas, L, Z, S, L invertida, T, o Cuadrado. giradas 90º de cualquier manera.

Ahora el reto, es almacenar la posición de todos los barcos en una cadena inferior a 128 bits.
(Obviamos la parte del ejercicio que es crear el código que codifica y decodifica esta cadena de bits, que también mola, pero no me parece tanto reto.)

Dado que el tablero es de 14x14, existen 196 casillas, si usáramos un bit para cada casilla (1 si hay barco, 0 si es agua) gastaríamos 196 bits, suspendidos :P

Para reducir bits, una manera es utilizar 4 bits para marcar el eje Y y 4 para el eje X.
Por ejemplo A, sería 0000, B 0001, C 0010, etc... y lo mismo para los números (1=0000,2=0001...) así que C4 sería 0010 0011.

Los barcos ocupan 20 casillas en total, si usáramos el método de X e Y gastaríamos 8x20=160bits en total, suspendidos :D

Así que el reto está ahí, cuando menor sean los bits empleados, mayor será la nota.

Yo he conseguido dejarlo de momento en 94 bits. Si alguien se interesa contaré mi método, pero no quiero "contaminaros" para ver si podéis encontrar algún método mejor vosotros.

Tengo una teoría que podría bajarlo a 83 bits, pero mis capacidades matemáticas no dan más de sí y necesitaré consejo experto... pero para no liar más la cosa de momento, dejo así el enunciado.

¡Animaros! Yo llevo un par de días muy divertidos con el asunto xD

B

Hostia,gracias por alegrarme la tarde. Voy a ponerme a ver en cuanto lo comprimo.

edit 2 : en realidad eran 123 xdddd
edit3 : 113 , soy cortico xddd
edit4 : 93 bits , creo que me voy a ir a estudiar , pero esto me lo guardo para optimizarlo más si se me ocurre xD

1
inkiet

100 -> 93 Luego seguiré pensando :/

Gusete

Progresion:
116 -> 108 -> 96 -> 94 -> 91 -> (80 -> 79)?

#5
En cuanto llegue a casa me pongo un rato con la explicacion pero creo que en el 79 tengo un gazapo y son realmente 80.

Pensandolo mejor voy a poner el 80 y sobre todo el 79 en cuarentena, esta tarde en casa intento explicar por lo menos el 91 y a ver si me cuadra lo que pense para el 80! :D

1 respuesta
GreyShock

79?? Ok, creo que es hora de poner en común los resultados :D

Esta noche no podía dormir casi con los malditos bits en la cabeza. A mí me están volviendo loco esas dos posiciones que sobran al utilizar 0000 0000 como eje de coordenadas. Ya que son 14x14 y eso cubre 16x16, y estoy buscando una manera de guardar información con todos esos bits sobrantes, que entre todos suman un buen pico.

Yo pensaba que mi límite serían 80 si conseguía guardar toda la info ajena a las coordenadas dentro esa diferencia. Usando 8 bits por barco. Estuve mirando métodos rolllo XOR para reciclar ese "sobrante", pero ahí ya me pierdo un poco.

Realmente me gustaría saber como se llega a #4 79 O_O

1 respuesta
LOc0

Sí, y ponedlo en spoiler, por favor (intentando bajar de 93...)

Salu2 ;)

elkaoD

EDIT: He mentido, no eran 75, voy a seguir pensando xD
EDIT2: Tengo un método que puede ocupar hasta 112 bits (en el peor de los casos) pero dependiendo de la configuración del tablero puedo ocupar hasta sólo 44 bits. A ver si lo depuro un poco y posteo. Lo malo es que al ser de tamaño variable es un poco extraño de medir.

Me he planteado hacer un programa que mida el peor, mejor y caso medio, pero me da pereza, así que ya os contaré la locura que he pensado xD

Ulmo

Creo q en 70 se puede hacer xD, luego pongo para q me digais en q me equivoco.

spoiler

Y creo q el de 4 piezas puedo usar 1 o 2 bits menos.

1 respuesta
elkaoD

#8

8 bits para los de 1 casilla -> 84=32 bits
9 bits para los de 2 -> 9
3=27 bits
10 bits para los de 3 -> aquí te falta un bit, son 11 bits, 8 de posición y 3 para las 6 posibilidades (2 rectos+4 en L) -> 112=22 bits
16 bits para el de 4 -> aquí te sobran bits. 8 bits de posicion + 6
4=24 formas diferntes (5 bits) -> 13*1=13 bits

Aunque el cuadrado en el de 4 no tenga 4 orientaciones, eso nos deja en 21 formas diferentes, que siguen siendo 5 bits (a no ser que puedas bajar hasta 16 posibilidades, que lo veo difícil.)

32+27+22+13 = 94 bits (y eso que me he ahorrado bits) ¿Pero tú cómo has sumado chico? xD

4 respuestas
LOc0

#9

spoiler

Salu2 ;)

1 2 respuestas
GreyShock

#9 Efectivamente, si ocupan 8bits mínimo cada pieza ya son 80 bits de base xD

Yo de esos 94 no consigo bajar, y mira que he probado trucos de magia...

#10 Eso es, el resultado tiene que ser estático, y de no serlo, suponer siempre el peor de los casos. Aunque en un resultado no-estático no me imagino luego como decodificar las fichas :S

2 respuestas
elkaoD

#9 hombre, si se "aceptan" como solución de tamaño variable, tampoco es cosa de comparar con el mejor caso, pero sí con el caso medio (a mi parecer es igual de "injusto" comparar con el mejor que con el peor.)

#10 no me refiero a ese tipo de tamaño dinámico, eso si sería cutre total. Se puede hacer de tamaño dinámico pero más "elegante". Como mínimo que el caso peor cumpla el límite de 128 bits (que no es fácil incluso usando tamaño variable, ojo... los flags ocupan un preciado espacio.)

+1 por el ahorro de un bit :)

#11 para decodificar los de tamaño variable sólo hay que contar que debe haber bits de flag o casos especiales. Aquí te dejo mi locura-idea donde uso ambas.

Mi solución de tamaño variable
1 2 respuestas
Ulmo

#9 Cierto, estaba en clase y sumé mal de cabeza, de todas formas el de 3 se puede hacer con solo 2 bits adicionales, ya q solo necesitas saber horizontal, vertical, diagonal derecha, diagonal izquierda. Ya q de las 8 posiciones 4 de ellas son idénticas cogiendo como referencia el otro extremo de la figura.

Veis pq decía q me dierais tiempo a hacerlo en casa con más calma, sumé rapido de cabeza en clase de máster y se me fueron los número xD

#11 El de 94 es mejorable pq contais 11 bits para el barco de 3 posiciones y en verdad solo necesitais 10 bits, solo hay 3 figuras posibles.

1 respuesta
GreyShock

#13 No entiendo bien lo de que de las 8 posiciones 4 de ellas son idénticas :S Podrías ejemplificarmelo, por favor? >__<

#12 NONOLOCURA! no sabía la existencia de esto.. me lo estudiaré, que siempre estábien abrir la mente a nuevas perspectivas bizarras xD

No sé por qué las cantidades variables no terminan de convencerme... Si que tienes razón en que es injusto mirar el peor caso, pero mirado desde un punto de vista práctico, si tuvieras que trabajar con esos resultados para X cosa, habría que contar siempre con el peor caso para que el programa fuera fino. Un resultado fijo es más estable y hermético, pero es cuestión de gustos y manías, supongo.

2 respuestas
Ulmo

#14 Estais contando 11 bits para los barcos de 3 no? Lo digo pq se puede hacer en 10, ya q los de 3 solo los puedes poner:

_ | / \

Vale nada, no leí q los de 3 tambien pueden estar en "L"

1 respuesta
GreyShock

#15 AVISO: los barcos no pueden estar en diagonal. Debí haberlo especificado en el planteamiento.

Las rotaciones de fichas son de 90º sólo. Si no, de locos xD

elkaoD

#14 ojo, puede ser útil empeorar el caso peor para ganar en los casos medios. Es como la eterna lucha entre uso de CPU vs. memoria.

Vale que la solución no es elegante, pero... funciona. Soy un fan de los "hacks", no puedo evitarlo xD

1 respuesta
Czhincksx

A ver qué te parece esto.

Creas una matriz de bits de 14x14. Haces dos dobleces a la mitad (a lo largo y a lo ancho) como si fuera una AND y creas de nuevo otra matriz de bits de 7x7 = 49bits.

Después necesitas un array con los coordenadas de las casillas que se superponen 6(x1x2x3,y1y2y3)bits + 3 bits para saber en qué pliegue se han superpuesto.

No te da una cifra exacta del tamaño final, pero en el peor de los casos sería 49 + 9x5 = 94.

Al final el tamaño oscilaría entre los 49 y los 94 bits dependiendo de la situación de los barcos.

1 3 respuestas
GreyShock

#18 Uf.. creo que tu idea no sería capaz de entenderla sin una pizarra xD No te sigo.

#17 Lo de los nonogramas me ha dado una idea que no tiene mucho que ver con ellos.. pero he conseguido dejar el caso del ejemplo en 87 bits. No sé como sería el caso peor y mejor, o si la variación es muy grande. Pero parece suculento.. :3 Si lo desarrollo un poco más pongo los picos de variación.

LOc0

Manita a #12 por la nono-idea y a #18 media porque CREO que no has tenido en cuenta bien el peor caso...

Si no he entendido mal, como los barcos ocupan 20 casillas y has troceado el plano en 4 cuadrantes, de "media" cada cuadrante está ocupado por 5 casillas de barcos y por tanto, en el "peor" caso habría 5 solapamientos después de hacer las dos dobleces.

PERO, ¿ Y SI repartes todos los barcos entre dos cuadrantes contiguos de forma simétrica? (10 casillas por cada cuadrante) Al terminar de doblar tendrías 10 solapamientos, es decir 49 + 10*9 = 139 ¿O no?

Salu2 ;)

1 1 respuesta
Ulmo

Lo de partirlo en 4 partes iguales el panel ya lo habia pensado, pero para q funcionase deberian ocupar todos los barcos la misma cantidad de bits, de ser así podrías llegar a ahorrar casi 1 bit por barco.

Pero al ocupar cada barco un número de bits diferentes te obligan a forzar la ordenación y ya creo q no sirve de nada partir el mapa.

1 1 respuesta
Czhincksx

#20 Tienes razón. Voy a seguir pensando XD

EnZo

Una pregunta de penco. Los de 3 solo pueden estar en vertical u horizontal no? Es decir no pueden adoptar la forma de los de 4...
Es que no entiendo porque elkaod dice en #9 que hacen falta 3bits de orientacion para ellos.

EnZo

Creo que lo tengo en 89 fijos. Aunque es un poco mierda si habeis conseguio los 80 por ahí arriba xD

89 Fijos
2 respuestas
LOc0

CORREGIDO
Inspirado en la idea de las dobleces de #18, CREO que tengo uno de 109 en el peor caso y de 20 en el mejor (me tengo que pirar, luego intento explicarlo mejor).

spoiler

#24 Los de 3 pueden estar en 6 formas (horizontal, vertical y cuatro 'L' ) Por eso, hacen falta 3 bits.

Salu2 ;)

1 respuesta
elkaoD

#24 lee bien el enunciado, te faltan bits por todos lados. No sólo pueden estar en horizontal/vertical. El de 4 tiene 19 variantes (5 bits en total, no 4, te olvidaste la L y la _| ) y los de 3 tienen 6 variantes, es decir 3 bits (pueden estar en L)

EnZo

Vale me he comido las eles con patatas xD. No he mejorado nada de los 94, asiq a seguir probando...

#25 El problema que le veo es que en tu chorizo de 49bits no especificas que barcos son. Solo si la casilla está ocupada o no. Y supongo que el planteamiento es para hacer un semijuego de hundir la flota. Al tenerlos tan apelotonados no podras identificar cual es cual porque habran casos en los que esten muy juntos todos.

1 2 respuestas
elkaoD

#27 nadie ha dicho que hubiera que identificar los barcos.

1 respuesta
EnZo

#28 #1 No lo habra especificado en su enunciado pero en el ejercicio original seguro que habria que hacerlo. Porque si no carece de sentido.

1 respuesta
Thanat0s

Llamarme loco, ¿pero si diagonalizas no consigues reducir mucho más el tamaño?

Recuerdo haberlo estudiado en Algebra de primero de carrera (hace mucho tiempo) y funcionaba para cosas como estas bastante bien.

pd: http://es.wikipedia.org/wiki/Matriz_diagonalizable