LOc0
 
LOc0
 
#31 19 feb 12, 21:19
#31 19 feb 12, 21:19

#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
 
#32 19 feb 12, 21:56
#32 19 feb 12, 21:56

#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

 
EnZo
 
EnZo
 
#33 20 feb 12, 00:05
#33 20 feb 12, 00:05

#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

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

 
LOc0
 
LOc0
 
#34 20 feb 12, 01:20
#34 20 feb 12, 01:20

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

Salu2 ;)

 
NeV3rKilL
:psyduck:
NeV3rKilL
:psyduck:
#35 20 feb 12, 08:47
#35 20 feb 12, 08:47

#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
 
#36 20 feb 12, 10:11
#36 20 feb 12, 10:11

#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

-Leer línea por línea horizontalmente las casillas que están ocupadas y marcarlas sólo con 4 bits, ya que al leer línea por línea, ya sabemos en que letra estamos.

  • Si en esa línea no hay barcos ponemos un 0 y pasamos a la siguiente línea.

  • Si sí que hay ponemos 1, y a cotinuación su número, p.ej: 0110.

  • Si no hay más casillas ocupadas en esa línea, ponemos un 0 y pasamos a la siguiente.

  • Si hay otro barco a continuación, ponemos un 1 y aquí se diversifica en:

a) Si el siguiente barco no es contiguo ponemos un 0, y luego el barco, p.ej. 0100
b) Si la casilla contigua está ocupada, ponemos un 1. Podemos añadir a continuación tantos unos como casillas ocupadas contiguas halla. 111, serían 3 casillas en línea. Y nos ahorramos marcarlas todas. Teminamos la serie con un 0, para marcar que ahí se acaba.

  • Al terminar el combo de b, tras el 0 de cierre, marcamos con 1 si hay otro barco, o con 0 si la línea está completada. Si hay otro barco ponemos su posición, p.ej. 0110, y volvemos a los pasos anteriores. Si no, 0 al canto y siguiente línea.

Entonces, siguiendo esas reglas, el caso del ejemplo me queda así (los dígitos de 4 bits son simulados, quedaros sólo con los bits de "lógica"):

0
1 0110 0
1 0111 0
1 0011 10 0110 11 00
1 0000 111 01 0100 0
1 0111 10 0010 11 00
1 0000 11 00
1 0001 0
1 0001 0
1 1100 0
0
0

TOTAL: 81 bits.

me falta calcular casos peores y mejores, pero me da la sensación (seguro que algo falla xD) de que no variará mucho.

EDIT: La hostia, me he comido dos filas, soy la leche. Me faltan 17 bits por codificar, se me va a los 98, shit. De todas formas dejo la idea, para que ahí quede. Por si a alguien le inspira algo mejor.

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

 
EnZo
 
EnZo
 
#37 20 feb 12, 12:07
#37 20 feb 12, 12:07

#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

 
Ulmo
 
Ulmo
 
#38 20 feb 12, 14:55
#38 20 feb 12, 14:55

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.

 
EnZo
 
EnZo
 
#39 20 feb 12, 17:14
#39 20 feb 12, 17:14

#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?

 
Ulmo
 
Ulmo
 
#40 20 feb 12, 18:16
#40 20 feb 12, 18:16

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

 
PandragoQ
 
#41 22 feb 12, 01:09
#41 22 feb 12, 01:09

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

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

 
GreyShock
 
#42 22 feb 12, 08:49
#42 22 feb 12, 08:49

#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.

  3
PorkoJones
 
#43 22 feb 12, 15:01
#43 22 feb 12, 15:01

Saludos,

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

Spoiler

Los 94 bits que se conseguian se obtienen de una organización como la que sigue:

FFFFCCCC x4 == 32
XFFFFCCCC x3 == 27
XXXFFFFCCCC x2 == 22
XXXXXFFFFCCCC x1 == 13

Donde FFFFCCCC son los 8 bits necesarios para identificar fila-columna, y las X son los bits necesarios para identificar la variante de barco. El x4, x3, etc denota la cantidad, con lo que ya se ve que la codificación es para los barcos de 1, 2, 3 y 4 piezas respectivamente. Es decir, las variantes de los de 4 piezas se codifican con XXXXX (5 bit). Al final hay el recuento de bits, que si se suma, da los 94 bits que teniamos hasta ahorra.

Mirando de optimizar el tema, se me ocurre como reducir 1 bit para la codificación de los barcos de 3 piezas. Actualmente se usan 6 bits (3+3), pero fijaos que, en lugar de codificar cada versión de barco de entre las 6 posibles, lo que podemos hacer es codificar la configuración de los 2 barcos, y además teniendo en cuenta que el orden de los barcos lo ponemos nosotros, con lo que se reduce la cosa.

Sabiendo que hay 6 versiones de cada barco, tenemos las siguientes posibilidades:
1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 2-2, 2-3, 2-4, 2-5, 2-6, 3-3, 3-4, 3-5, 3-6, 4-4, 4-5, 4-6, 5-5, 5-6, 6-6 (21 combinaciones en total)

Fijaos que no pongo ni la 2-1, ni la 3-1, 3-2, etc, ya que son la misma que la 1-2, 1-3, 2-3 solo que cambiando el orden en que vamos a poner los barcos (y el orden lo ponemos nosotros).

Vale, hasta aquí vemos que 21 posibilidades se codifican en 5 bits, y ya reducimos 1... tenemos 93.

Ahora la forma en que se pueden reducir los 5 bits (enteritos) para la codificación del tipo de barco de 4 piezas:

Recordemos que hay 19 posibilidades (de ahí los 5 bits). Bien, pues en lugar de codificarlo con bits, lo codificamos con el orden en que introducimos los 4 barcos de 1 unidad.

Estamos de acuerdo en que cada casilla de la matriz de 14x14 puede tener su número (del 0 al 195), con lo que las cuatro posiciones de los barcos pueden establecer un orden entre ellas (1, 2,3 y 4). Así pues, podemos introducir los barcos ordenados tal que 1-2-3-4, o los podemos introducir en plan 3-2-4-1.

Partiendo de ese principio, vemos que podemos introducir esos 4 barcos de 24 formas distintas:
1-2-3-4, 1-2-4-3, 1-3-2-4, 1-3-4-2, 1-4-2-3, 1-4-3-2,
2-1-3-4, 2-1-4-3, 2-3-1-4, 2-3-4-1, 2-4-1-3, 2-4-3-1,
3-1-2-4, 3-1-4-2, 3-2-1-4, 3-2-4-1, 3-4-1-2, 3-4-2-1,
4-1-2-3, 4-1-3-2, 4-2-1-3, 4-2-3-1, 4-3-1-2, 4-3-2-1.

Por lo tanto, sólo necesitamos ordenar la introducción de nuestros 4 barcos de forma que codifiquen una de las 19 versiones disponibles para el barco de 4 piezas, ahorrandonos de esta forma los 5 bits necesarios para esta codificación. (Las 5 ordenaciones restantes, simplemente no las usaremos nunca).

Por lo tanto, 93-5 = 88 bits.

Si no se entiende algo de la solución, lo aclaro con mucho gusto...

 
GreyShock
 
#44 22 feb 12, 15:36
#44 22 feb 12, 15:36

#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
 
EnZo
 
#45 22 feb 12, 17:30
#45 22 feb 12, 17:30

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

 
PandragoQ
 
#46 22 feb 12, 17:35
#46 22 feb 12, 17:35

#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

 
PorkoJones
 
#47 22 feb 12, 17:47
#47 22 feb 12, 17:47

Saludos,

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

Spoiler

Como ya he dicho, cada casilla tiene su código (de 0 a 195). Pasar de coordenadas a "código" és tan fácil como hacer algo del estilo:

Q = X + Y*14 , entendiendo que empezamos a contar desde (0,0)

Luego, para saber en que orden has puesto los barcos, pues le calculas esa Q y si obtienes algo como:

34,3,141,98

pues sabes que el orden en que los has metido es:

2,1,4,3

y eso te codifica una versión del barco de 4.

  3
PorkoJones
 
#48 22 feb 12, 19:50
#48 22 feb 12, 19:50

Saludos,

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

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

Spoiler

Partiendo de lo propuesto anteriormente...

Si seguimos en la línea de codificar cosas con el orden en que introducimos las coordenadas, vemos que los 3 barcos de 2 se pueden aprobechar para codificar 6 estados:
1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1

Justamente, cada barco de 3 puede tener 6 versiones, que inicialmente codificabamos con 3 bits cada una (un total de 6 del propuse la mejora a 5 reduciendo combinaciones y ordenando los barcos).

Con estos 6 estados no podemos codificar las versiones de los 2 barcos de 3, pero si que podemos codificar la versión de uno de ellos, necesitando entonces únicamente 3 bits para codificar la versión el otro. Así pues, en lugar de los 5 propuestos anteriormente, con este sistema tenemos suficiente con 3 bits (ya tenemos 2 menos, 86 bits).

Ah! y ahora podemos introducir los barcos de 3 en el orden que nos plazca, con lo que podemos codificar un nuevo bit con los 2 estados resultantes del orden posible de estos barcos:
1-2, 2-1

Este bit se puede usar para partir el tablero en 2 mitades y codificar en qué mitad se encuentra el barco de 4, reduciendo así en 1 bit sus coordenadas (FFFCCCC ó FFFFCCC, dependiendo de como partais el tablero), o directamente puede sustituir el primer bit del sistema de coordenadas normal que ya teniamos. Sea como sea, reducimos 1 nuevo bit, por lo que obtenemos los 85 bits que he comentado.

Aun así, le doy vueltas a la posibilidad de que el orden total de combinaciones del orden de las coordenadas (de todas) pueda codificar la combinación de variantes (en conjunto), però así de primeras diria que no... aunque lo dejo como línea "a seguir".

Lo que digo es que podemos codificar:

2x6x24 = 288 estados usando sólo 8x10 bits (las coordenadas).
Si añadiendo algún bit, sin llegar a 85, podemos codificar todas las versiones que usamos, pues tendremos una nueva mejora... ahí lo dejo

 
LOc0
 
LOc0
 
#49 22 feb 12, 23:35
#49 22 feb 12, 23:35

Salu2 ;)

 
EnZo
 
EnZo
 
#50 23 feb 12, 00:38
#50 23 feb 12, 00:38

Que crack eres

Echa el curriculum en inteligencia jeje

12
Favoritos
3