क्या किसी ने इस तरह के प्रोग्रामिंग पहेली को देखा है?

Question

"मान लीजिए कि आप 4 × 1 और 6 × 1 लेगो ब्लॉक की पंक्तियों से एक ठोस पैनल बनाना चाहते हैं। संरचनात्मक ताकत के लिए, ब्लॉक के बीच की जगहों को आसन्न पंक्तियों में कभी भी लाइन नहीं करना चाहिए। उदाहरण के तौर पर, 18 × 3 नीचे दिखाया गया पैनल स्वीकार्य नहीं है, क्योंकि शीर्ष दो पंक्तियों में ब्लॉक के बीच की जगहें हैं।

10 × 1 पैनल बनाने के 2 तरीके, 10 × 2 पैनल बनाने के 2 तरीके, 8 तरीके 36 × 5 पैनल बनाने के लिए 18 × 3 पैनल और 7958 तरीके बनाएं।

64 × 10 पैनल बनाने के लिए कितने अलग तरीके हैं? उत्तर 64-बिट हस्ताक्षरित पूर्णांक में फिट होगा। उत्तर की गणना करने के लिए कार्यक्रम। आपका कार्यक्रम बहुत जल्दी चलना चाहिए - निश्चित रूप से, इसे एक मिनट से भी अधिक समय तक नहीं लेना चाहिए पुरानी मशीन आइए जानें कि आपके प्रोग्राम की गणना की गई मान, आपके प्रोग्राम को उस मूल्य की गणना करने में कितना समय लगेगा, और किस प्रकार की मशीन आपने इसे चलाया था। एक अनुलग्नक के रूप में प्रोग्राम के स्रोत कोड शामिल करें। "

मुझे हाल ही में एक प्रोग्रामिंग पहेली दी गई थी और इसे हल करने की कोशिश कर रहे मेरे दिमाग को रैक कर रहा था। मैंने सी ++ का उपयोग करके कुछ कोड लिखा और मुझे पता है कि संख्या बहुत बड़ी है ... मेरा कार्यक्रम तय करने से कुछ घंटे पहले चला बस इसे रोकने के लिए क्योंकि धीमी कंप्यूटर पर भी आवश्यकता का रन 1 मिनट था। क्या किसी ने इस तरह की पहेली देखी है? यह कुछ हफ्तों तक रहा है और मैं इसे अब और नहीं सौंप सकता हूं, लेकिन यह वास्तव में bugging रहा है मुझे लगता है कि मैं इसे सही तरीके से हल नहीं कर सका। एल्गोरिदम पर उपयोग करने के लिए कोई सुझाव? या "बॉक्स के बाहर" इसे हल करने के संभावित तरीके। शायद मैंने जो प्रोग्राम किया था वह एक ऐसा प्रोग्राम बना रहा था जिसने 4x1 की प्रत्येक संभावित "परत" बनाई और 64x1 परत बनाने के लिए 6x1 ब्लॉक। यह लगभग 3300 विभिन्न परतों के रूप में सामने आया। तब मैंने अपना प्रोग्राम चलाया और उन्हें सभी संभावित 10 परत ऊंची दीवारों में ढेर कर दिया, जिनमें कोई दरार नहीं है लाइन अप ... जैसा कि आप देख सकते हैं कि इस समाधान में लंबा, लंबा, लंबा समय लगेगा। तो स्पष्ट रूप से ब्रूट फोर्स समय की बाधा के भीतर इसे हल करने में प्रभावी प्रतीत नहीं होता है। किसी भी सुझाव/अंतर्दृष्टि की सराहना की जाएगी।

Answer 1

मुख्य अंतर्दृष्टि यह है: यह निर्धारित करते हुए पंक्ति 3 में क्या, तुम क्या पंक्ति 1 में है के बारे में परवाह नहीं है, बस क्या पंक्ति में है 2.

तो चलो एक 64x1 परत का निर्माण करने के लिए कैसे एक "पंक्ति कॉल परिदृश्य "। आप कहते हैं कि लगभग 3300 पंक्ति परिदृश्य हैं। ये उतना बुरा नहीं है।

च (रों, आर) = तरीके पंक्ति परिदृश्य संख्या "एस" डाल करने के लिए पंक्ति में "आर", और कानूनी तौर पर "आर" ऊपर सभी पंक्तियों को भरने की संख्या:

के एक समारोह की गणना करते हैं।

(मैं शीर्ष पर पंक्ति "1" के साथ भरोसा कर रहा हूँ, और नीचे "10" पंक्ति)

रोकें पढ़ना अब अगर आप विफल बचना चाहते हैं।

अब स्पष्ट रूप से (1 से 10 के लिए हमारी पंक्तियों नंबर):

च (रों, 1) = 1

"एस" के सभी मानों के लिए

।

इसके अलावा, और इस जहां अंतर्दृष्टि, में आता है (का उपयोग करते हुए मेथेमेटिका -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

मेरा उत्तर यहां है। यह अन्य चीजों के साथ हैस्केल है, आप मुफ्त में bignums मिलता है।

संपादित करें: अब यह वास्तव में उचित समय में समस्या हल करता है।

अधिक संपादन: एक स्पैर मैट्रिक्स के साथ यह मेरे कंप्यूटर पर आधा सेकंड लगता है।

आप पंक्ति को टाइल करने के लिए प्रत्येक संभव तरीके की गणना करते हैं। मान लीजिए कि पंक्ति को टाइल करने के एन तरीके हैं। एक एनएक्सएन मैट्रिक्स बनाओ। एलिमेंट i, j 1 है यदि पंक्ति मैं पंक्ति जे के बगल में दिखाई दे सकता हूं, 0 अन्यथा। एन 1 एस युक्त वेक्टर के साथ शुरू करें। वेक्टर द्वारा मैट्रिक्स को गुणा करें, दीवार शून्य 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 एमएस, मैं उस के साथ रह सकते हैं।