Кто-нибудь видел загадку программирования, подобную этому?

Question

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

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

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

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

Answer 1

Основное понимание заключается в следующем: при определении того, что находится в строке 3, вы не заботитесь о том, что в строке 1, как раз то, что в строке 2.

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

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

F (s, г) = количество способов поставить строки номер сценария «s» в строке «г», и юридически заполнить все строки выше «г».

(Я рассчитываю со строкой «1» в верхней части, и ряд «10» в нижней части)

СТОП ЧТЕНИЯ Теперь, если вы хотите избежать интерцепторы.

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

F (S, 1) = 1

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

Кроме того, и это где понимание приходит, (с помощью 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

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

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

Answer 3

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

EDIT: теперь он фактически решает проблему в разумные сроки.

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

Вы вычисляете каждый возможный способ чередования строки. Предположим, что существует 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 мс, я могу жить с этим.