Hat jemand ein ähnliches Programmierrätsel gesehen?

Question

"Nehmen wir an, Sie wollen eine massive Platte aus Reihen von 4×1 und 6×1 Legosteinen bauen. Um die strukturelle Festigkeit zu gewährleisten, dürfen die Abstände zwischen den Steinen in benachbarten Reihen nicht übereinander liegen. Die unten gezeigte 18×3-Platte ist zum Beispiel nicht akzeptabel, weil die Abstände zwischen den Blöcken in den oberen beiden Reihen übereinander liegen.

Es gibt 2 Möglichkeiten, eine 10×1-Platte zu bauen, 2 Möglichkeiten, eine 10×2-Platte zu bauen, 8 Möglichkeiten, eine 18×3-Platte zu bauen, und 7958 Möglichkeiten, eine 36×5-Platte zu bauen.

Wie viele verschiedene Möglichkeiten gibt es, eine 64×10-Tafel zu bauen? Die Antwort passt in eine 64-Bit-Ganzzahl mit Vorzeichen. Schreiben Sie ein Programm, um die Antwort zu berechnen. Ihr Programm sollte sehr schnell laufen - auf jeden Fall sollte es nicht länger als eine Minute dauern, selbst auf einem älteren Rechner. Teilen Sie uns mit, welchen Wert Ihr Programm berechnet, wie lange es für die Berechnung gebraucht hat und auf welchem Rechner Sie es ausgeführt haben. Fügen Sie den Quellcode des Programms als Anhang bei. "

Ich habe vor kurzem ein Programmierrätsel bekommen und habe mir den Kopf zerbrochen, um es zu lösen. Ich habe einen Code mit C++ geschrieben und ich weiß, dass die Zahl riesig ist... mein Programm lief einige Stunden, bevor ich mich entschied, es einfach zu stoppen, weil die Anforderung 1 Minute Laufzeit war, selbst auf einem langsamen Computer. Hat jemand ein ähnliches Rätsel gesehen? Es ist schon ein paar Wochen her und ich kann es nicht mehr einreichen, aber es hat mich wirklich gestört, dass ich es nicht richtig lösen konnte. Hat jemand Vorschläge für Algorithmen, die man verwenden könnte? Oder vielleicht mögliche Lösungswege, die "außerhalb der Box" liegen. Ich habe mir ein Programm ausgedacht, das jede mögliche "Schicht" aus 4x1- und 6x1-Blöcken zu einer 64x1-Schicht zusammensetzt. Das waren dann etwa 3300 verschiedene Ebenen. Dann habe ich mein Programm durchlaufen lassen und sie zu allen möglichen 10 Schichten hohen Wänden gestapelt, die keine Risse haben, die sich aneinanderreihen ... wie Sie sehen können, würde diese Lösung eine lange, lange, lange Zeit dauern. Offensichtlich scheint rohe Gewalt nicht effektiv zu sein, um dieses Problem innerhalb der Zeitvorgabe zu lösen. Für Vorschläge/Einblicke wären wir sehr dankbar.

Answer 1

Die wichtigste Erkenntnis ist folgende: Wenn Sie bestimmen, was in Zeile 3 steht, ist es Ihnen egal, was in Zeile 1 steht, sondern nur, was in Zeile 2 steht.

Nennen wir also den Aufbau einer 64x1-Ebene ein "Zeilenszenario". Sie sagen, dass es etwa 3300 Zeilenszenarien gibt. Das ist gar nicht so schlecht.

Berechnen wir eine Funktion:

f(s, r) = die Anzahl der Möglichkeiten, die Zeile mit der Szenariennummer "s" in die Zeile "r" zu setzen und alle Zeilen über "r" legal zu füllen.

(Ich zähle mit Reihe "1" oben und Reihe "10" unten)

HÖREN SIE JETZT AUF ZU LESEN, WENN SIE SPOILER VERMEIDEN WOLLEN.

Jetzt ganz klar (wir nummerieren unsere Zeilen von 1 bis 10):

f(s, 1) = 1

für alle Werte von "s".

Außerdem, und das ist der Punkt, an dem die Einsicht kommt, (mit Mathematica -ische Schreibweise)

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

wobei "fits" eine Funktion ist, die zwei Szenarionummern annimmt und "1" zurückgibt, wenn man diese beiden Reihen legal übereinander stapeln kann, und "0", wenn das nicht möglich ist. Diese Funktion nutzt die Erkenntnis, dass die Anzahl der legalen Möglichkeiten, Szenarien zu platzieren, nur von der Anzahl der Möglichkeiten abhängt, Szenarien übereinander zu platzieren, die gemäß "fits" kompatibel sind.

Jetzt können Passungen vorberechnet und in einem 3328 mal 3328 Byte großen Array gespeichert werden. Das sind nur etwa 10 Meg Speicherplatz. (Weniger, wenn man es als Bit-Array speichert)

Die Antwort lautet dann offensichtlich nur

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

Answer 2

Hier ist meine Antwort. Es ist Haskell, unter anderem, erhalten Sie bignums kostenlos.

EDIT: Jetzt wird das Problem tatsächlich in einer angemessenen Zeitspanne gelöst.

MEHR EDITS: Bei einer spärlichen Matrix dauert es auf meinem Computer eine halbe Sekunde.

Sie berechnen jede mögliche Art, eine Reihe zu kacheln. Nehmen wir an, es gibt N Möglichkeiten, eine Reihe zu kacheln. Erstellen Sie eine NxN-Matrix. Element i,j ist 1, wenn Reihe i neben Reihe j erscheinen kann, sonst 0. Beginne mit einem Vektor, der N 1en enthält. Multipliziere die Matrix mit dem Vektor so oft, wie die Höhe der Wand minus 1 ist, und addiere dann den resultierenden Vektor.

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)

Und die Ergebnisse...

$ 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

Okay, 500 ms, damit kann ich leben.

Answer 3

Ich habe ein ähnliches Problem für einen Programmierwettbewerb gelöst, bei dem ich einen langen Flur mit Kacheln in verschiedenen Formen verlegt habe. Ich habe dynamische Programmierung verwendet: Für jede beliebige Platte gibt es einen Weg, sie zu konstruieren, indem ich eine Reihe nach der anderen verlege. Jede Reihe kann endlich viele Formen an ihrem Ende haben. Ich berechne also für jede Anzahl von Reihen und für jede Form, wie viele Möglichkeiten es gibt, diese Reihe zu bilden. (Für die unterste Reihe gibt es genau eine Möglichkeit, jede Form zu bilden.) Dann bestimmt die Form jeder Reihe die Anzahl der Formen, die die nächste Reihe annehmen kann (d. h. die Zwischenräume dürfen niemals aneinandergereiht werden). Diese Anzahl ist für jede Reihe endlich, und da man nur zwei Größen von Steinen hat, wird sie klein sein. So verbringen Sie pro Reihe eine konstante Zeit und das Programm ist schnell fertig.

Um eine Form darzustellen, würde ich einfach eine Liste mit 4er und 6er Zahlen erstellen und diese Liste dann als Schlüssel in einer Tabelle verwenden, um die Anzahl der Möglichkeiten, diese Form zu bilden, in einer Zeile zu speichern i für jede i .