Кто-нибудь видел подобную головоломку?

Question

"Предположим, что вы хотите построить сплошную панель из рядов блоков Lego 4 × 1 и 6 × 1. Для прочности конструкции пробелы между блоками никогда не должны располагаться в соседних рядах. Например, 18 × 3 панель, показанная ниже, неприемлема, потому что промежутки между блоками в двух верхних строках совпадают.

Существует 2 способа построения панели 10 × 1, 2 способа построения панели 10 × 2, 8 способов создания панели 18 × 3 и 7958 способов создания панели 36 × 5.

Сколько существует способов построить панель размером 64 × 10? Ответ помещается в 64-разрядное целое число со знаком. Напишите программу для расчета ответа. Ваша программа должна работать очень быстро - конечно, она не должна занимать больше одной минуты, даже на старой машине. Сообщите нам значение, которое вычисляет ваша программа, сколько времени понадобилось вашей программе для вычисления этого значения и на какой машине вы ее выполняли. Включите исходный код программы в качестве вложения. «

Мне недавно дали головоломку для программирования, и я ломал голову, пытаясь ее решить. Я написал некоторый код, используя c ++, и я знаю, что число огромно ... моя программа работала за несколько часов, прежде чем я решил просто остановить ее, потому что требовалось 1 минута работы даже на медленном компьютере. Кто-нибудь видел подобную головоломку? Прошло несколько недель, и я больше не могу передать это, но это действительно беспокоило меня, что я не мог решить это правильно. Любые предложения по алгоритмам для использования? Или, возможно, возможные способы решения этой проблемы, которые "вне коробки". Я прибегал к созданию программы, которая создавала каждый возможный «слой» из блоков 4x1 и 6x1 для создания слоя 64x1. Это оказалось около 3300 различных слоев. Затем я запустил мою программу и сложил их во все возможные 10-слойные высокие стены, которые не имеют трещин, которые выстраиваются в линию ... как вы можете видеть, это решение займет очень много времени. Очевидно, что грубая сила не кажется эффективной в решении этой проблемы во времени. Любые предложения / понимание будет принята с благодарностью.

Answer 1

Основная идея такова: при определении того, что находится в строке 3, вам не важно, что находится в строке 1, а только то, что в строке 2.

Итак, давайте назовем, как построить слой 64x1, «сценарий строки». Вы говорите, что существует около 3300 сценариев строк. Это не так уж плохо.

Давайте вычислим функцию:

f (s, r) = количество способов поместить номер сценария строки "s" в строку "r" и законно заполнить все строки выше "r".

(я считаю со строкой "1" вверху и строкой "10" снизу)

Хватит читать сейчас, если вы хотите избежать спойлеров.

Теперь ясно (нумерация строк от 1 до 10):

f (s, 1) = 1

для всех значений "s".

Кроме того, и здесь начинается понимание (с использованием Mathematica -ish нотации)

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

где «соответствует» - это функция, которая принимает два номера сценария и возвращает «1», если вы можете легально сложить эти две строки друг над другом, и «0», если не можете. При этом используется понимание, поскольку число законных способов размещения сценария зависит только от количества способов размещения сценариев над ним, которые совместимы в соответствии с «подгонками».

Теперь подгонки могут быть предварительно вычислены и сохранены в массиве байтов 3328 на 3328. Это всего около 10 мегабайт памяти. (Меньше, если вы захотите сохранить его как битовый массив)

Тогда ответ, очевидно, просто

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

Answer 2

Вот мой ответ. Это Haskell, помимо всего прочего, вы получаете Bignums бесплатно.

РЕДАКТИРОВАТЬ: теперь фактически решает проблему в разумные сроки.

БОЛЬШЕ РЕДАКТИРОВАНИЯ: С разреженной матрицей на моем компьютере уходит полсекунды.

Вы вычисляете каждый возможный способ мозаичного ряда. Допустим, есть N способов разбить ряд на части. Сделайте матрицу NxN. Элемент i, j равен 1, если строка i может появиться рядом со строкой j, 0 в противном случае. Начните с вектора, содержащего N 1s. Умножьте матрицу на вектор, количество раз равное высоте стены минус 1, а затем сложите полученный вектор.

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)

И результаты ...

$ 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

Хорошо, 500 мс, я могу жить с этим.

Answer 3

Я решил аналогичную задачу для соревнования по программированию, облицовавшего длинный коридор плитками разных форм. Я использовал динамическое программирование: для любой панели есть способ построить ее, сложив по одной строке за раз. Каждый ряд может иметь конечное число фигур на своем конце. Поэтому для каждого числа рядов, для каждой фигуры я вычисляю, сколько существует способов сделать этот ряд. (Для нижнего ряда есть только один способ создания каждой фигуры.) Затем форма каждой строки определяет количество фигур, которые может принять следующая строка (то есть никогда не выстраивать пробелы). Это число конечно для каждого ряда, и на самом деле, поскольку у вас есть только два размера кубиков, оно будет небольшим. Таким образом, вы тратите постоянное время на строку, и программа быстро завершается.

Чтобы представить форму, я бы просто составил список из 4 и 6, а затем использовал бы этот список в качестве ключа в таблице для хранения количества способов сделать эту форму в строке i для каждого я .