Problema matemático binario

LOc0

#27 Tienes toda la razón en que los barcos no están identificados, como comenta #21 (no lo leí). Con tanta abstracción se me fue la pinza y olvidé lo de Hundir la flota porque entonces necesitas tener los barcos que están juntos delimitados para saber cuándo te los hunden... Así que nada, como curiosidad queda, pero NO vale. Manita a Ulmo y a Enzo pues ;)

Salu2 ;)

PD: y me parece que la nono-solución peca de lo mismo xD Esperando con ansia la explicación de Gusete ;)

GreyShock

#29 El objetivo es "derrotar" al oponente. No necesitas saber como son sus barcos, sólo hundírselos.

Por ejemplo, marcar con 8bits cada una de las casillas donde hay barcos sería válido. Lo malo es que ocuparía 160 bits de este modo.

..Sigo perdido en cuanto a lo de las dobleces, suena a ciencia ficción XD

2 respuestas
EnZo

#32 Así tambien se puede jugar, pero no lo considero el juego de hundir la flota. Ya que saber cuando has hundido un barco te hace saber cuantos y que tipos de barcos te quedan pendientes por hundir. Forma parte de la estrategia del juego. Aunque si el enunciado original no contempla eso me callo :P

En cualquier caso la solucion de 89 de loco es muy ingeniosa :P

2 respuestas
LOc0

#33 Ingeniosa, defectuosa e inservible xD (Ya la he corregido, aunque no queda tan espectacular).

Salu2 ;)

NeV3rKilL

#32 Yo lo de los dobleces tampoco lo veo claro. Si haces un pliegue, vale, reduces la coordenada en un bit, pero a la vez necesitas ese bit para decir en qué parte del pliegue está el barco así que estás en las mismas de 4 bits pro barco.

GreyShock

#33 Yo considero que no hay estrategia cuando conoces exactamente las casillas que ocupan todos sus barcos, en un turno puedes decir todas las coordenadas y ganar.

Aunque creo que tu vas por la parte de que el código es para "generar" partidas, o algo así? Que luego el programa sea capaz de descrifrar la tira de bits, colocarlos en el tablero, saber cual es cada barco, y después permitir que dos humanos jueguen ¿puede ser?

El ejercicio estaba planteado como un "espía" que te manda los datos del oponente para derrotarlo. Pero bueno, tampoco pasa nada por resolverlo con, y sin los barcos. Más diversión xD

Ya que estamos, expongo mi manera "inspirada" en los nonogramas, que poco tiene de nonograma, pero me dio esta idea.

En el caso de ejemplo me ocupa 81 (EDIT: mentira, me ocupa 98) bits. Sería así:

spoiler

aunque para mi gusto, la mejor y más elegante sigue siendo la de 94 de momento :P

1 respuesta
EnZo

#36 "en un turno puedes decir todas las coordenadas y ganar" cuando pasa eso? 1 de cada millon de partidas? xD
El no saber que barcos te quedan por hundir le quita la gracia al juego de hundir la flota para mi.

Sip, yo veia el problema como un juego real por internet. Donde meter toda la configuracion en 127 bits es super optimo pensando en transferencia de datos.

Pero si problema está planteado como un "espia"... entonces ya es otro tema. Además tienes razon de que asi tienes mas opciones para devanarte los sesos.

Aunque estoy convencido de que es imposible bajar de los 94 si quieres descodificarlo luego, quites de donde quites luego tienes que ponerselos... yo ya he desistido. A ver si algun genio se le ocurre algo :P

Ulmo

Uffff, he tenido una idea bastante loca q quizás puede reducir algo la cosa, a ver si la desarrollo un poco pero os hago un pequeño croquis:

La idea sería numerar las filas y columnas con bits, 0 si en esa columna no hay ningun barco, 1 si hay alguna casilla ocupada con un barco. De esa forma gastas solo 24 bits, pero aun tienes q resolver las colisiones, gastando nuevos bits.

De hecho gastando 1 solo bit puedes volver el peor caso (todos los barcos situados en la diagonal) en el mejor caso si usas el primer bit para decir si listaras diagonales o horizontales-verticales.

Le daré un poco al tarro pero creo q puede ser interesante de explorar, de hecho incluso usando los 2 sistemas (cruces de diagonales + cruces de horizontales-verticales) podrías desestimar algunos casos y estarias gastando solo 56 bits.

1 respuesta
EnZo

#38 No te he entendido bien. Gastas 24bits (que en realidad son 28, 14+14) para decir en que fila/columna está. Pero luego tendras que ver que mas casillas estan ocupadas no?

1 respuesta
Ulmo

#39 Sí sí claro, es como punto de partida.

PandragoQ

Asi, a bote pronto... haciendo un LZ78 de los 196 bits, con la densidad de "1" que te vas a encontrar (un 10%) creo que se reduciria un huevo. Esta noche si puedo lo programo en un pis-pas :P

Edit: Pues no, no funciona... pero me ha gustado el problemilla... el record esta en 93?

1 respuesta
GreyShock

#41 Eso dicen, aunque yo creo que son 94 bits, al menos si es por el método de identificadores para las formas, no se me ocurre como quitar ese bitillo.

PorkoJones

Saludos,

muy interesante el problema, la verdad que si... creo que reduzco a 88 bits, manteniendo la codificación.

spoiler
3 2 respuestas
GreyShock

#43 Eres el amo. Yo también estuve buscando reducción de bits mediante combinatoria y no llegué a nada... pero la maravilla esa de ordenar los barcos de 1... uf, obra de arte.

Me quito el sombrero, el pelo y la tapa del cráneo. Sí señor.

EnZo

#43 Y como consigues hacer la descodificacion sin flags que especifiquen el orden en el que lo colocas todo?

1 respuesta
PandragoQ

#45 el orden lo puedes sacar sumando las coordenadas XY de cada barco de 1. El menor de los 4, el barco 1, el siguiente, el 2... it's easy, my friend :)

#47 si nos ponemos asi.... 2X + Y :P

1 respuesta
PorkoJones

Saludos,

#46 Cuidado con eso, porque entonces un barco en (4,9) tendria el mismo orden que uno en (9,4).

spoiler
1 respuesta
PorkoJones

Saludos,

vale... he tenido que seguir dándole vueltas mientras volvia a casa con el coche... :o_o:

Llego a 85 bits (reduzco 3 más).

spoiler
3
LOc0

Salu2 ;)

EnZo

Que crack eres :P

Echa el curriculum en inteligencia jeje