DESAFÍO
Dado un conjunto de letras agrupadas, colóquelas en el tablero para que cubran el área por completo.
Representación de la Junta (también conocido como BARCO DECK)
- El tablero es una cuadrícula de 6x6.
- Siempre habrá 36 cuadrados totales.
- Las columnas están marcadas AF.
- Las filas están marcadas 1-6.
Ejemplo:
A B C D E F
+---+---+---+---+---+---+
1 : : : : : : :
+---+---+---+---+---+---+
2 : : : : : : :
+---+---+---+---+---+---+
3 : : : : : : :
+---+---+---+---+---+---+
4 : : : : : : :
+---+---+---+---+---+---+
5 : : : : : : :
+---+---+---+---+---+---+
6 : : : : : : :
+---+---+---+---+---+---+
ENTRADA (también conocido como los cajones)
- Una cadena multilínea que contiene el conjunto de letras agrupadas.
- Las cajas están hechas de grupos de letras idénticas.
- Las cajas son INMUTABLES, lo que significa que no se pueden girar ni voltear.
- El punto de partida para cada caja está en la parte superior izquierda (debe tenerse en cuenta al mover una caja a la cubierta).
- Desde el punto superior izquierdo de una caja, los siguientes cuadrados idénticos solo pueden estar a la derecha o debajo.
- Cualquier letra puede usarse para representar una caja. Las cajas siempre comienzan con letras
[a]y suben el alfabeto. - Las cajas están etiquetadas por su letra (es decir, caja A, caja B, etc.)
- El número de cajas puede variar (no siempre es 10, a pesar de los ejemplos dados).
- Hay 24 caracteres que separan cada bloque de cajas por línea. (inicio de [a] a inicio de [b] separados por 24 caracteres, etc.)
Ejemplo:
[a][a][a] [b] [c][c]
[a] [b][b][b] [c]
[a] [b][b]
[d] [e] [f][f][f][f][f]
[d][d] [e]
[d][d] [e]
[e]
[e][e]
[g] [h] [i]
[g] [i]
[i]
SALIDA
Es necesario que imprima una serie de comandos que coloquen las cajas en posiciones en la plataforma para que quede completamente cubierta (sin espacios vacíos).
El formato del comando es así:
HAUL <crate> TO <column> <row>
es decir, HAUL E A A 1
Para aclarar, siempre habrá una solución para la entrada dada.
CASOS DE PRUEBA <- Haga clic para más.
Entrada
[a][a][a] [b] [c][c][c]
[a][a] [b]
[a] [b][b]
[b][b]
[d] [e] [f]
[d] [f]
[d] [f]
[d]
[d]
[g][g] [h] [i]
[i][i]
[i]
[i][i]
[j][j][j]
Salida
HAUL I TO A 1
HAUL B TO A 3
HAUL A TO B 1
HAUL J TO D 6
HAUL D TO F 1
HAUL F TO E 1
HAUL C TO C 5
HAUL G TO D 4
HAUL E TO D 3
HAUL H TO C 6
Resultado:
A B C D E F
+---+---+---+---+---+---+
1 : i : a : a : a : f : d :
+---+---+---+---+---+---+
2 : i : i : a : a : f : d :
+---+---+---+---+---+---+
3 : b : i : a : e : f : d :
+---+---+---+---+---+---+
4 : b : i : i : g : g : d :
+---+---+---+---+---+---+
5 : b : b : c : c : c : d :
+---+---+---+---+---+---+
6 : b : b : h : j : j : j :
+---+---+---+---+---+---+
PUNTUACIÓN
Este es el código de golf, por lo que gana la respuesta más corta en caracteres.
code-golf
sequence
decision-problem
parsing
board-game
Jonathan Picazo
fuente
fuente
Respuestas:
Python 3.6,
435437385331 bytesLlame
F()con la cuerda de la caja.Logré jugar al golf mucho más:
- Analiza la cadena de cajas directamente en lugar de usar la
- Se usó setdefault para guardar la primera coordenada de un conjunto de cajas, de modo que se pueda crear la máscara de bits al analizar la cadena de cajas. Eliminando un bucle for.
Versión anteriorrebiblioteca.Reestructurado el código para eliminar bucles redundantes.
Versión previaEl código anterior creó una lista de todas las posiciones de una caja
F()y luego iteró sobre la lista enR(). El nuevo código crea una posición de una cajaF()yR()prueba todas las posiciones posibles.En el código anterior,
R()recopilaba una posible soluciónayF()luego iteraba sobre la solución devuelta. En el nuevo código,R()imprime los comandos HAUL directamenteExplicación
La idea básica es representar la cubierta del barco y las cajas como mapas de bits. Mediante el uso de mapas de bits, mover una caja se convierte en un cambio de su mapa de bits y la comprobación de la superposición entre cajas se convierte en un AND en bits y prueba de cero.
Código sin golf:
F()analiza la cadena de definición de caja y construye los mapas de bits. Una expresión regular busca (línea 9) cada línea de la cadena de definición de caja en busca de cajas (una letra seguida de un ']'). Cuando se encuentra una coincidencia, la correspondiente (fila, col) se agrega a un diccionario con la letra (líneas 11-13). Para el ejemplo de cadena de definición de caja dada en el problema:Las coordenadas de cada caja están normalizadas (línea 17), de modo que cada caja comienza en (0,0) y cada bloque tiene una unidad de ancho (en lugar de 3 a la '[a]').
Luego se crea un mapa de bits para cada caja en función de las coordenadas normalizadas (línea 18).
La plataforma se trata como una cuadrícula de 7 x 7. La columna 'G' y la fila 7 se utilizan para detectar cuándo una forma se extiende fuera del tablero. Un mapa de bits tiene un 1 si las cajas ocuparían el cuadrado correspondiente en la cubierta. Los bits 48 a bit 42 corresponden a los cuadrados A1 a A7, los bits 41 a 35 corresponden a los cuadrados B1 a B7, y así sucesivamente.
R(used, bitmaps)luego usa los mapas de bits para buscar recursivamente ubicaciones de cajas que no intentan colocar dos cajas en el mismo cuadrado.usedes una máscara de bits que indica qué cuadrados no se pueden usar porque ya están ocupados por una caja o porque están fuera del tablero (es decir, la columna G y la fila 7).bitmapses una lista de cajas que aún deben colocarse.El caso base para la recursión es cuando no quedan más cajas para colocar, es decir,
bitmapsestá vacío (línea 23). En este caso, se devuelve True para indicar que se ha encontrado una solución.De lo contrario, un nombre de caja y su mapa de bits se extraen de la lista de mapas de bits (línea 26). Si bien el mapa de bits de la caja no está vacío (línea 28), verifique si la ubicación de la caja actual, representada por el mapa de bits de la caja, entra en conflicto con las cajas colocadas previamente. En la línea 29,
not used & crate_bitmapes Falso siusedycrate_bitmapambos tienen un 1 en la misma posición de bit, lo que indica un conflicto. Si no hay un conflicto,R()se llama de forma recursiva (línea 30) para intentar colocar las cajas restantes.Si la llamada recursiva a
R()devuelve True, significa que se ha encontrado una solución y que la ubicación actual de las cajas es parte de esa solución. Por lo tanto, se imprime el comando correspondiente para mover las cajas y True se propaga por las llamadas recursivas (líneas 31-32).Cuando se crea en
F(), cada mapa de bits de caja representa los cuadrados de la cubierta que serían ocupados por las cajas si se colocan en la posición A1. Cambiar un mapa de bits un bit a la derecha corresponde a mover las cajas a la posición A2. Un desplazamiento a la derecha de siete bits corresponde a mover las cajas a B1, etc. Por ejemplo, los siguientes mapas de bits representan cajas 'a' en varias posiciones:Si una posible colocación de cajas no funciona porque entra en conflicto con una caja previamente colocada (línea 30) o porque no hay una ubicación válida de las cajas restantes (línea 31). Las cajas se mueven a una posición diferente desplazando la máscara de bits un bit hacia la derecha (línea 35).
Shiftrealiza un seguimiento de cuántos lugares se ha desplazado el mapa de bits, que corresponde a la posición actual de las cajas.Si el mapa de bits está vacío (cero), indica que se han intentado todas las ubicaciones posibles. Se devuelve falso (línea 37) para indicar un error, de modo que una llamada
R()anterior a la recursión intentará otra ubicación para sus cajas.Para garantizar que las cajas no se extiendan por el costado de la plataforma, los bits correspondientes a la columna G y la fila 7 se configuran
usedpara la llamada inicial aR()(línea 20).4432676798719es la cubierta vacía correspondiente a0b0000001000000100000010000001000000100000011111111fuente
Python 2 , 864 bytes
Pruébalo en línea!
Explicación
Se utilizan muchos bytes para analizar las cajas bidimensionales ingresadas a través de una sola cadena. Las cajas se representan como una lista anidada de valores booleanos.
Después de analizar las cajas, la función considera todas las posiciones posibles de todas las cajas. Para hacerlo, se llama iterativamente a sí mismo. Cuando encuentra una posición imposible (si la caja se coloca fuera de la cubierta o encima de otra caja), mata la rama del árbol de recursión actual para mejorar el rendimiento.
Cuando ve que una determinada combinación de ubicaciones dio como resultado una cubierta completamente cubierta, imprime el historial de ubicación de cajas registrado y se cierra globalmente al intentar una división desesperada. Las instrucciones de transporte impresas incluso se ordenan alfabéticamente.
Python 2 , 812 bytes
Pruébalo en línea!
Explicación
La cadena de cajas se analiza y transforma en un nido de booleanos que representa cada caja.
Una función iterativa genera todas las listas posibles de longitud igual a la cantidad de cajas que contienen los enteros
0 <= x < 36(todas las posiciones posibles de la cubierta del barco). Cada lista se interpreta como una instrucción para colocar todas las cajas y probarlas. Si la lista de instrucciones probadas da como resultado un mazo sin espacios vacíos, la lista de instrucciones tiene que ser válida y se imprime.Al ser extremadamente ineficiente, no lo probé en el caso de prueba proporcionado, aunque en escenarios con menos cajas (ver el enlace TIO). Debido a que el algoritmo busca en todos los arreglos posibles, trata
36**10 = 3.656e15de verlos. Sin embargo, en teoría , aún debería funcionar.fuente
H/Mfuera de la declaración de función, ya que tenerlos en la declaración hace que las funciones no sean reutilizables. Buen viejo Python.[i]con[b], que funciona . El algoritmo podría mejorarse clasificando primero las cajas para que las más grandes se prueben antes que las pequeñas.JavaScript, 366
Nota: esta función puede analizar una entrada más compacta, ya que no le importa el espacio entre 24 caracteres y se permiten agujeros en las cajas.
Creo que podría jugarse un poco más, pero ahora es corto y no demasiado lento, así que me gusta como está
Menos golf
Casos de prueba muchos de ellos
fuente