¿Alguien ha visto un rompecabezas de programación similar a esto?

Question

"Supongamos que desea construir un panel sólido a partir de filas de bloques Lego de 4 × 1 y 6 × 1. Para la resistencia estructural, los espacios entre los bloques nunca deben alinearse en filas adyacentes. Como ejemplo, el 18 × 3 El panel que se muestra a continuación no es aceptable, porque los espacios entre los bloques en las dos filas superiores se alinean.

Hay 2 formas de construir un panel de 10 × 1, 2 formas de construir un panel de 10 × 2, 8 formas de construir un panel de 18 × 3 y 7958 maneras de construir un panel de 36 × 5.

¿Cuántas formas diferentes hay para construir un panel de 64 × 10? La respuesta se ajustará a un entero de 64 bits con signo. programa para calcular la respuesta. Su programa debe ejecutarse muy rápido, sin duda, no debería tomar más de un minuto, incluso en un máquina más vieja. Háganos saber el valor que calcula su programa, cuánto tiempo llevó su programa calcular ese valor y qué tipo de máquina lo ejecutó. Incluya el código fuente del programa como un archivo adjunto. "

Recientemente me dieron un acertijo de programación y he estado trabajando duro tratando de resolverlo. Escribí un código usando C++ y sé que el número es enorme ... mi programa se ejecutó durante unas horas antes de que decidiera solo para detenerlo porque el requerimiento era de 1 minuto de tiempo de ejecución incluso en una computadora lenta. ¿Alguien ha visto un rompecabezas similar a esto? Han pasado unas semanas y no puedo entregar esto más, pero esto realmente ha estado molestando que no pude resolverlo correctamente. ¿Alguna sugerencia sobre algoritmos para usar? O tal vez formas posibles de resolverlo fuera de la caja. A lo que recurrí fue a hacer un programa que construyó cada posible "capa" de 4x1 y 6x1 bloques para hacer una capa de 64x1. Eso resultó ser alrededor de 3300 capas diferentes. Luego hice que mi programa se ejecutara y los apilara en todos los posibles muros de 10 capas que no tienen grietas alinearse ... como puede ver, esta solución tomaría mucho, mucho, mucho tiempo. Entonces, obviamente, la fuerza bruta no parece ser efectiva para resolver esto dentro de la restricción de tiempo. Cualquier sugerencia/idea sería muy apreciada.

Answer 1

La idea principal es la siguiente: la hora de determinar lo que hay en la fila 3, que no se preocupan por lo que está en la fila 1, sólo lo que está en la fila 2.

Así que vamos a llamar a cómo construir una capa de 64x1 una "fila guión". Usted dice que hay aproximadamente 3300 escenarios de filas. Eso no es tan malo.

Vamos a calcular una función:

f (s, r) = el número de maneras de poner el número escenario fila "s" "r" en la fila, y legalmente llenar todas las filas por encima de "r".

(Estoy contando con la fila "1" en la parte superior, y la fila "10" en la parte inferior)

dejar de leer ahora si se quiere evitar SPOILERS.

Ahora claramente (numeración nuestras filas de 1 a 10):

f (s, 1) = 1

para todos los valores de "s".

También, y esto es donde entra en juego la visión en, (Uso de Mathematica notación ish)

f(s, r) = Sum[ f(i, r-1) * fits(s, i) , {i, 1, 3328} ] 

donde "se ajusta" es una función que toma dos números de escenarios y devuelve "1" si legalmente puede apilar esas dos filas una encima de la otra y "0" si no puede.Esto utiliza la información porque la cantidad de formas legales para ubicar el escenario depende únicamente de la cantidad de formas de ubicar los escenarios superiores que sean compatibles de acuerdo con "ajustes".

Ahora, los ajustes se pueden precalcular y almacenar en una matriz de 3328 por 3328 de bytes. Eso es solo alrededor de 10 Meg de memoria. (Menos si se obtiene la fantasía y lo almacena como una matriz de bits)

La respuesta es, entonces, evidentemente, sólo

Sum[ f(i, 10) , {i, 1, 3328} ] 

Answer 2

me resolvió un problema similar para un concurso de programación de alicatado de un largo pasillo con azulejos de diferentes formas. Usé programación dinámica: dado cualquier panel, hay una manera de construirlo colocando una fila a la vez. Cada fila puede tener infinitamente muchas formas en su extremo. Entonces, para cada número de filas, para cada forma, calculo cuántas maneras hay para hacer esa fila. (Para la fila inferior, hay exactamente una forma de hacer cada forma.) Luego, la forma de cada fila determina el número de formas que puede tomar la fila siguiente (es decir, nunca alinee los espacios). Este número es finito para cada fila y, de hecho, debido a que solo tiene dos tamaños de ladrillos, será pequeño. Así que terminas gastando tiempo constante por fila y el programa termina rápidamente.

Para representar una forma me acaba de hacer una lista de 4 de y 6 de, a continuación, utilizar esta lista como una llave en una tabla para almacenar el número de maneras de hacer que la forma en la fila i, para cada i .

Answer 3

Aquí está mi respuesta. Es Haskell, entre otras cosas, obtienes bignums gratis.

EDITAR: Ahora realmente resuelve el problema en un tiempo razonable.

MÁS EDICIONES: Con una matriz dispersa, toma medio segundo en mi computadora.

Calcula cada una de las posibles maneras de marcar una fila. Digamos que hay N maneras de formar una fila en mosaico. Haz una matriz NxN. El elemento i, j es 1 si la fila i puede aparecer al lado de la fila j, 0 en caso contrario. Comience con un vector que contenga N 1s. Multiplica la matriz por el vector varias veces igual a la altura del muro menos 1, luego suma el vector resultante.

module Main where 
import Data.Array.Unboxed 
import Data.List 
import System.Environment 
import Text.Printf 
import qualified Data.Foldable as F 
import Data.Word 
import Data.Bits 

-- This records the index of the holes in a bit field 
type Row = Word64 

-- This generates the possible rows for given block sizes and row length 
genRows :: [Int] -> Int -> [Row] 
genRows xs n = map (permToRow 0 1) $ concatMap comboPerms $ combos xs n 
    where 
    combos [] 0 = return [] 
    combos [] _ = [] -- failure 
    combos (x:xs) n = 
     do c <- [0..(n `div` x)] 
     rest <- combos xs (n - x*c) 
     return (if c > 0 then (x, c):rest else rest) 
    comboPerms [] = return [] 
    comboPerms bs = 
     do (b, brest) <- choose bs 
     rest <- comboPerms brest 
     return (b:rest) 
    choose bs = map (\(x, _) -> (x, remove x bs)) bs 
    remove x (bc@(y, c):bs) = 
     if x == y 
     then if c > 1 
       then (x, c - 1):bs 
       else bs 
     else bc:(remove x bs) 
    remove _ [] = error "no item to remove" 
    permToRow a _ [] = a 
    permToRow a _ [_] = a 
    permToRow a n (c:cs) = 
     permToRow (a .|. m) m cs where m = n `shiftL` c 

-- Test if two rows of blocks are compatible 
-- i.e. they do not have a hole in common 
rowCompat :: Row -> Row -> Bool 
rowCompat x y = x .&. y == 0 

-- It's a sparse matrix with boolean entries 
type Matrix = Array Int [Int] 
type Vector = UArray Int Word64 

-- Creates a matrix of row compatibilities 
compatMatrix :: [Row] -> Matrix 
compatMatrix rows = listArray (1, n) $ map elts [1..n] where 
    elts :: Int -> [Int] 
    elts i = [j | j <- [1..n], rowCompat (arows ! i) (arows ! j)] 
    arows = listArray (1, n) rows :: UArray Int Row 
    n = length rows 

-- Multiply matrix by vector, O(N^2) 
mulMatVec :: Matrix -> Vector -> Vector 
mulMatVec m v = array (bounds v) 
    [(i, sum [v ! j | j <- m ! i]) | i <- [1..n]] 
    where n = snd $ bounds v 

initVec :: Int -> Vector 
initVec n = array (1, n) $ zip [1..n] (repeat 1) 

main = do 
    args <- getArgs 
    if length args < 3 
    then putStrLn "usage: blocks WIDTH HEIGHT [BLOCKSIZE...]" 
    else do 
     let (width:height:sizes) = map read args :: [Int] 
     printf "Width: %i\nHeight %i\nBlock lengths: %s\n" width height 
      $ intercalate ", " $ map show sizes 
     let rows = genRows sizes width 
     let rowc = length rows 
     printf "Row tilings: %i\n" rowc 
     if null rows 
     then return() 
     else do 
      let m = compatMatrix rows 
      printf "Matrix density: %i/%i\n" 
       (sum (map length (elems m))) (rowc^2) 
      printf "Wall tilings: %i\n" $ sum $ elems 
        $ iterate (mulMatVec m) (initVec (length rows)) 
          !! (height - 1) 

Y los resultados ...

$ time ./a.out 64 10 4 6 
Width: 64 
Height 10 
Block lengths: 4, 6 
Row tilings: 3329 
Matrix density: 37120/11082241 
Wall tilings: 806844323190414 

real 0m0.451s 
user 0m0.423s 
sys  0m0.012s 

Vale, 500 ms, puedo vivir con eso.