Imagine el siguiente escenario: está jugando acorazados con un amigo pero decide hacer trampa. En lugar de mover un barco después de que él dispara donde solía estar tu barco, decides no colocar ningún barco en absoluto. Le dices que todos sus disparos son fallidos, hasta que es imposible colocar naves de esa manera.
Tienes que escribir una función, o un programa completo, que de alguna manera tome 3 argumentos: el tamaño del campo, una lista de cantidades de tamaños de barcos y una lista de disparos.
Campo de batalla
Uno de los parámetros dados es el tamaño del tablero. El campo de batalla es un cuadrado de celdas, y el parámetro dado es simplemente un lado del cuadrado.
Por ejemplo, la siguiente es una tabla de tamaño 5.
Las coordenadas en el campo se especifican como una cadena de 2 componentes: una letra seguida de un número. Puede confiar en que las letras están en algún caso particular.
La letra especifica la columna, el número especifica la fila de la celda (1 indexado). Por ejemplo, en la imagen de arriba, la celda resaltada se denota por "D2"
.
Como solo hay 26 letras, el campo no puede ser mayor que 26x26.
Barcos
Las naves son líneas rectas de 1 o más bloques. La cantidad de naves se especifica en una lista, donde el primer elemento es la cantidad de naves de 1 celda, la segunda de naves de 2 celdas, etc.
Por ejemplo, la lista [4,1,2,0,1]
crearía el siguiente paquete de envío:
Cuando se colocan en el campo de batalla, las naves no pueden cruzarse, ni siquiera tocarse entre sí. Ni siquiera con esquinas. Sin embargo, pueden tocar los bordes del campo.
A continuación puede ver un ejemplo de colocación de barco válida:
Puede suponer que para un conjunto de barcos determinado, siempre existe una ubicación en un tablero vacío de un tamaño determinado.
Salida
Si existen tales ubicaciones de naves, debe generar cualquiera de ellas.
El programa tiene que generar una matriz separada por una nueva línea de caracteres ascii de cualquiera de los 3 tipos: uno para denotar una celda en blanco, uno - una pieza de envío y uno - una celda marcada como "perdida". No se deben mostrar otros caracteres.
Por ejemplo,
ZZ@Z
\@@Z
@\\Z
\Z\\
(En este ejemplo, definí @
ser una celda en blanco, \
una celda "perdida" y Z
ser una pieza de envío)
Si no existe tal ubicación, el programa / función debería regresar sin generar nada.
Entrada
Si decide hacer un programa completo, depende de usted especificar cómo se ingresan las listas, algunas pueden ser a través de argumentos, otras a través de stdin.
Este es el código de golf , gana la menor cantidad de personajes.
Una solución optimizada ejemplo no golfed-se puede encontrar aquí
compilar con -std=c99
, el primer argumento es el tamaño de la tabla, los otros argumentos son los tamaños de buques. Se proporciona una lista de disparos separada por nueva línea en stdin. Ejemplo:
./a 4 1 1 1 <<< $'A2\nA4\nB3\nC3\nC4\D4'
fuente
26x26
? Dibujé una solución basada en expresiones regulares y recursividad, y se vuelve extremadamente lenta = inutilizable para campos más que6x6
. O hago algo muy estúpido o la falta de respuestas significa que otros tampoco tienen éxito.10x10
con un conjunto de4,3,2,1
barcosRespuestas:
GolfScript, 236 caracteres
La entrada se da en STDIN. La primera línea contiene el tamaño y el número de barcos, cada una de las siguientes coordenadas de línea de un solo disparo.
Ejemplo:
Pensé que también este desafío debería tener al menos una respuesta de GolfScript. Al final, se volvió muy poco realista debido al algoritmo utilizado que favorece el rendimiento sobre la brevedad.
Código anotado:
fuente
SWI-Prolog,
536441 1 bytes1 final de línea UNIX, nueva línea final no contada
La versión con todas las optimizaciones eliminadas ( 441 bytes):
Como el código se cambia para minimizar el número de bytes, ya no aceptará una lista de disparos que tengan duplicados.
La versión con optimización básica, totalmente golfizada ( 536 → 506 bytes)
Implemento algunas comprobaciones básicas ( cuente el número de bloques de envío necesarios ) para que el código salga más rápido en casos claramente imposibles. El código también es inmune a duplicarse en la lista de disparos hasta ahora.
A continuación se muestra la versión (algo) legible, con comentarios detallados:
Formato de consulta:
Consulta de muestra (usando la muestra en la pregunta):
fuente
Matlab - 536 caracteres
Actualizado: formato de salida mucho más pequeño, algunos espacios en blanco de bucle eliminados.
Actualizado: versión de golf agregada
Actualizado: versión comentada agregada, versión reducida de golf en ~ 100 caracteres
Aquí está la versión de golf.
Aquí hay algunas muestras.
La gran línea con 'kron' (cerca de la parte inferior del código sin golf) es mi parte favorita de esto. Escribe un '1' en todas las ubicaciones en el mapa vecino de una posición dada. ¿Puedes ver cómo funciona? Utiliza el producto tensor de kronecker, la multiplicación de matrices e indexa el mapa como una matriz lineal ...
fuente
Python, 464 caracteres
Entrada (stdin):
Salida:
Funciona usando enteros que contienen mapas de bits de varias características:
fuente
[::-1]
que hace que primero pruebe el barco más largo. También retrocede tan pronto como encuentra un barco que no puede ubicar.Python, 562 caracteres, -8 con salida fea, +4? para invocación bash
Nota: los niveles de sangría son espacio, tabulación, tabulación + espacio, tabulación + tabulación y tabulación + tabulación + espacio. Esto evita que algunos caracteres usen espacios solamente.
Uso y ejemplo :
Toma información de los argumentos de la línea de comandos. Emite un espacio en blanco como espacio, un disparo como a
.
y@
como parte de un barco:Cuando no se puede resolver, no imprime nada:
El
2>X
objetivo es suprimir un mensaje de error ya que el programa se cierra lanzando una excepción. Siéntase libre de agregar una penalización de +4 si se considera justo. De lo contrario tendría que hacer untry: ... except:0
para suprimirlo, lo que de todos modos tomaría más caracteres.También puedo imprimir la salida como números (
0
,1
y2
) para eliminar 8 caracteres, pero valoro la estética.Explicación :
Represento el tablero como una lista de listas de enteros con un tamaño 2 mayor que la entrada, para evitar tener que hacer controles de límites.
0
representa un espacio vacío,1
un tiro y2
una nave. Reviso la lista de disparosQ
y marco todos los disparos. Convierto la lista de barcos en una lista explícitaX
de barcos, por ejemplo, se[4, 0, 2, 0, 1]
convierte en[5, 3, 3, 1, 1, 1, 1]
. Entonces es un algoritmo de retroceso simple: en orden de orden de tamaño descendente, intente colocar un barco y luego intente colocar el resto de los barcos. Si no funciona, prueba la siguiente ranura. Tan pronto como tiene éxito, la lista de envíoX
es nula y el accesoX[0]
genera una excepción que cierra el programa. El resto es solo golf pesado (inicialmente fue de 1615 caracteres).fuente
Perl,
455 447 437 436 422418Sangrado:
Espero que se pueda jugar más (por ejemplo, con
eval<>
entrada preformateada, como veo que está bien (?)), Y también algunas otras cosas (50$
sigilos? No, se quedarán).La velocidad, como dije antes, puede ser un problema (desde instantáneo (ver el ejemplo a continuación) hasta muy, muy largo), dependiendo de dónde esté la solución en el árbol de recursión, pero que sea la cuestión de la obsolescencia del hardware utilizado. Haré una versión optimizada más tarde, con la recursión desaparecida y otros 2-3 trucos obvios.
Se ejecuta así, se alimentan 3 líneas a través de STDIN:
~
es el océano (solución artística, ¿no es así?),o
s yx
s son barcos y disparos. Las primeras 5 líneas obtienen la entrada y preparan nuestro 'campo de batalla'.$N
es tamaño,@S
es una matriz desenrollada de barcos (por ejemplo,1 1 1 1 2 3 3 5
como se$f
indica arriba), es una cadena que representa el campo de batalla (filas con líneas nuevas concatenadas). Lo siguiente es la subrutina recursiva, que espera el estado actual del campo de batalla y la lista de naves restantes. Comprueba de izquierda a derecha, de arriba a abajo e intenta colocar cada nave en cada posición, tanto horizontal como verticalmente (¿ves? Madura para optimizar, pero eso será más adelante). La nave horizontal es un reemplazo obvio de expresiones regulares, vertical un poco más complicado: manipulación de cadenas bit a bit para reemplazar en 'columna'. En caso de éxito (H, V o ambos), las nuevas posiciones inaccesibles se marcan con!
, y se bifurca a la siguiente iteración. Y así.Editar: OK, aquí hay una versión de 594 bytes (sin sangría) que realmente intenta ser útil (es decir, rápida), optimizada al máximo de mi capacidad mientras aún implementa las mismas técnicas: recursión (aunque se hace 'manualmente') y expresiones regulares. Mantiene una 'pila' -
@A
: una variedad de estados que vale la pena investigar. Un 'estado' tiene 4 variables: cadena actual del campo de batalla, índice desde donde comenzar a tratar de colocar las naves, referencia a la matriz de naves restantes e índice de la próxima nave a intentar. Inicialmente hay un solo 'estado': inicio de cadena vacía, todos los barcos. En el partido (H o V, ver arriba), se empuja el estado actual para investigar más tarde, se empuja el estado actualizado (con un barco colocado y posiciones inaccesibles marcadas) y se reinicia el bloque. Cuando se llega al final de la cadena del campo de batalla sin éxito,@A
se investiga el siguiente estado disponible desde (si lo hay).Otras optimizaciones son: no reiniciar desde el principio de la cadena, tratar de colocar barcos grandes primero, no verificar barcos del mismo tamaño si el anterior falló en la misma posición, + tal vez algo más (como ninguna
$&
variable, etc.)..
OTOH, todavía toma una eternidad para el caso imposible
6 5 4 3 2 1
en el ejemplo anterior. Tal vez la versión práctica debería salir inmediatamente si el tonelaje total del barco excede la capacidad del campo de batalla.fuente
Solución C #
fuente
size=1 ships={1} moves={"A1"}
.Java, 1178
Sí, demasiado tiempo.
Sin golf:
Entrada de muestra
Salida de muestra
Con
O
tiro errado#
parte del barco_
dispara aquí a continuación ;-)Ver en ideone.com
El manejo de entrada espera los espacios alrededor de los números /
;
y no funcionará de otra manera.Estoy colocando grandes barcos primero ya que tienen menos lugares para ir. Si desea cambiar a pequeña primero se puede sustituir
pop()
porremove(0)
ypush(s)
poradd(0,s)
, incluso la sustitución de uno solo de los dos todavía debe resultar en un programa válido.Si permite que los barcos se toquen entre sí, la
g(int,int)
función se puede simplificar o eliminar enormemente.fuente