Este desafío está inspirado en esta aplicación . Los casos de prueba están tomados de esa aplicación.
Este es un desafío de código más rápido , donde el objetivo es resolver los casos de prueba más grandes en la menor cantidad de tiempo. Se proporcionan algunos casos de prueba más pequeños, para que las personas puedan probar sus algoritmos más rápido.
Se le dará una cuadrícula de entrada cuadrada, de dimensiones n-por-n donde 9 <= n <= 12 . Esta cuadrícula se dividirá en n áreas, donde las celdas de cada área tienen identificadores únicos (usaré letras minúsculas de al en el texto aquí, pero puede elegir lo que quiera, por ejemplo, números enteros 1-12 ) .
La entrada puede verse así (formato de entrada opcional):
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
O, más fácil de visualizar:
Desafío:
Debe colocar 2 * n árboles en este parque, de acuerdo con las siguientes reglas:
- Habrá exactamente 2 árboles por columna y 2 árboles por fila
- Todas las áreas deben tener exactamente 2 árboles.
- Ningún árbol puede ser adyacente a otro árbol, vertical, horizontal o diagonal
La solución al diseño anterior es:
Nota: solo hay una solución para cada rompecabezas
Reglas adicionales:
- Los formatos de entrada y salida son opcionales.
- El resultado podría ser, por ejemplo, una lista de índices, una cuadrícula con 1/0 que indica si hay un árbol en esa posición, o una versión modificada de la entrada donde se indican los árboles
- El tiempo de ejecución debe ser determinista.
- El programa debe terminar dentro de 1 minuto en la computadora de @ isaacg
- Especificaciones: 4 CPU, CPU i5-4300U a 1.9 GHz, 7.5G de RAM.
- En caso de que su programa no pueda resolver los dos casos de prueba más grandes en un minuto cada uno, entonces el tiempo para el segundo más grande ( n = 11 ) será su puntaje. Perderá contra una solución que resuelva el caso más grande.
Casos de prueba:
Podría editar esta lista si los envíos parecen estar personalizados para adaptarse a estos casos de prueba.
12 por 12 :
--- Input ---
aaaaabccccdd
aaaaabccccdd
aaaaabbbbddd
eeeafffgbghh
eeaafffgbghh
eefffffggghh
eeefijffghhh
iieiijjjjkhh
iiiiijjjjkhk
lljjjjjjjkkk
llllllkkkkkk
llllllkkkkkk
--- Solution ---
aaaaabcccCdD
aaaaaBcCccdd
aAaaabbbbdDd
eeeaffFgBghh
eeAaFffgbghh
eefffffGgGhh
EeefijffghhH
iiEiIjjjjkhh
IiiiijjjjkHk
lljJjJjjjkkk
lLllllkkKkkk
lllLllKkkkkk
11 por 11 :
--- Input ---
aaaaaaabbcc
adddabbbbcc
edddbbbbbbc
eddddbbbbbb
effffggghhh
effffgghhii
eefffjjhhii
eeeejjjhhii
eeejjjjkiii
jjjjjjkkiii
jjjjjkkkiii
--- Solution ---
aaAaaaabbCc
adddAbBbbcc
eDddbbbbbbC
eddDdBbbbbb
effffggGhHh
eFfffGghhii
eefFfjjhHii
EeeejjjhhiI
eeEjjjjKiii
JjjjJjkkiii
jjjjjkKkIii
10 por 10
--- Input ---
aaaaabccdd
aeaabbbccd
aeaabfbgcd
eeeaafggcd
eeeaafghcd
eeeiifghcd
ieiiigghcd
iiijighhcd
jjjjighhcd
jjjggghhdd
--- Solution ---
aaAaabccdD
aeaaBbBccd
aEaabfbgcD
eeeaaFgGcd
eEeAafghcd
eeeiiFghCd
IeiIigghcd
iiijigHhCd
JjJjighhcd
jjjgGghHdd
9 por 9
--- Input ---
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
--- Solution ---
aAbBbbbcc
adddbbBcC
adEeEcccc
AdddefgCc
hhhDiFggg
hDddifffG
hhhiIfFfg
HiHiifffg
iiiiiIgGg
--- Input ---
aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg
--- Solution ---
aaAbBbccc
AaaabbcCc
aaaDdBcce
fFddddcCe
fffFdDeee
fGffdheeE
fggfHhHee
IggggheeE
iiIgggGgg
fuente
There shall be exactly 2 trees per column, and 2 trees per row
por lo que una fuerza bruta es probablemente imposible.Respuestas:
JavaScript (ES6), 271 bytes
Toma entrada como una matriz de matrices de caracteres. Devuelve una matriz de máscaras de bits (enteros) que describen la posición de los árboles en cada fila, donde el bit menos significativo es la posición más a la izquierda.
Formateado y comentado
Casos de prueba
Este fragmento incluye una función adicional para mostrar los resultados en un formato más legible. Es demasiado lento para resolver el último caso de prueba.
Tiempo de ejecución esperado: ~ 5 segundos.
Mostrar fragmento de código
fuente
C, hora oficial: 5 ms para 12x12
Compilado con GCC 7 usando las banderas
-O3
y-fopenmp
. Debería tener resultados similares en cualquier versión de GCC con OpenMP instalado.Los formatos de entrada y salida son los que figuran en la pregunta.
En mi máquina, esto toma
0.009s0.008s0.005s para el ejemplo 12x12, y0.022s0.020s0.019s para ejecutar todos los ejemplos. En la máquina de referencia, isaacg informa 5 ms para el ejemplo de 12x12 utilizando la versión original (sin hilos) del código.Uso:
Solo un simple solucionador de fuerza bruta, trabajando en una fila a la vez. Funciona a una buena velocidad al reconocer situaciones imposibles temprano (por ejemplo, no quedan celdas de la región, pero menos de 2 árboles en la región).
La primera actualización mejora los aciertos de caché al poner los datos relacionados juntos en la memoria, y hace que los posibles cálculos de árboles restantes en el segmento sean un poco más inteligentes (ahora explica el hecho de que los árboles no pueden ser adyacentes). También extrae el bucle más externo para que se necesiten menos casos especiales en la parte más activa del algoritmo.
La segunda actualización hace que el bucle más externo se ejecute en paralelo a través de los procesadores disponibles (usando OpenMP), dando un impulso de velocidad lineal. Esto solo está habilitado para n> = 11, ya que la sobrecarga de los hilos de desove supera los beneficios para las cuadrículas más pequeñas.
fuente
Java (OpenJDK 8) , temporización oficial: 1.2s en 12x12
editar: ya no codifica golf
Pruébalo en línea!
El enlace TIO es para el caso de prueba 12x12. TIO informa 2.429s para el tiempo de ejecución.
Toma una matriz de enteros como entrada y modifica la matriz para que contenga 1 para árboles y 0 para no árboles.
Esto funciona para todos los casos de prueba. El caso de prueba más grande se ejecuta en mi máquina en menos de un segundo, aunque tengo una máquina bastante poderosa
Código de prueba para el 12x12, puede modificar para otros
Produce esto en mi máquina:
fuente
Clingo , ≈ 7 ms para 12 × 12, 116 bytes
(Las nuevas líneas son opcionales y no cuentan).
Ejecute con
clingo plant.lp - -c n=<n>
donde<n>
está el tamaño de la cuadrícula. El formato de entrada es una lista dec(X,Y,Z).
estados para cada celda (X
,Y
) coloreadoZ
, con 1 ≤X
,Y
,Z
≤n
, separadas por espacios en blanco opcional. La salida incluyet(X,Y)
para cada árbol en (X
,Y
).El tiempo no tiene sentido, ya que básicamente es solo el tiempo de inicio, así que considere esto como un voto para casos de prueba más grandes.
Manifestación
Para hacer que el formato de entrada / salida sea más fácil de manejar, aquí hay programas de Python para convertir y al formato dado en el desafío.
Entrada
Salida
fuente