हास्केल

Question

में त्रिभुज में तारों को स्वरूपित करना मेरे पास तारों की सूचियों की एक सूची है और मुझे उन्हें प्रत्येक पंक्ति पर अपनी रेखा पर एक त्रिकोण में प्रारूपित करने की आवश्यकता है, और प्रत्येक सूची के तार कम से कम एक से अलग होते हैं अवधि। इसके अतिरिक्त, प्रत्येक चरित्र के ऊपर और नीचे बिंदु होना चाहिए। यह शायद सबसे अच्छा उदाहरण से समझाया गया है:

> dots [["test"], ["hello", "world"], ["some", "random", "words"], ["even", "more", "random", "words"]] 

............test..................... 
.......hello.......world............. 
...some......random......words....... 
not....really......random.....anymore 

लौटना चाहिए अंत में, यह संभव अवधि कम से कम मात्रा का उपयोग करना चाहिए, अधिक से अधिक की लंबाई के हर शब्द बाहर की पैडिंग दृष्टिकोण यानी शब्द बहुत अपमानजनक है; वह यह है कि ऊपर के उदाहरण के लिए वापस नहीं चाहिए

.....................test........................ 
..............hello.........world................ 
.......some..........random........words......... 
not...........really........random........anymore 

मैं आसानी से एक समारोह है कि अवधि के दोनों ओर यह एक त्रिकोण आकार में बनाने के लिए डाल दिया करता है लिख सकते हैं, मेरी समस्या शब्दों के बीच में समय के साथ है।

मेरे पास एक ऐसा कार्य है जो शब्द की लंबाई 1 तक काम करता है, जो कि कार्य के लिए स्पष्ट रूप से बेकार है। फिर भी, मेरी समारोह dots:

dots :: [[String]] -> [[String]] 
dots xss = map dots' xss 
    where dots' (x:[]) = [x] 
      dots' (x:xs) = [x] ++ ["."] ++ dots' xs 

यह एक होमवर्क व्यायाम संकेत को प्राथमिकता दी जाएगी तो है, लेकिन मैं कोई भाग्य के साथ घंटों के लिए यह करने के लिए कोशिश कर रहा है है।

Answer 1

सबसे पहले आप एक समारोह, कि इस प्रकार की सूची के लिए प्लेसहोल्डर कहते हैं की जरूरत है:

addPlaceholders [ ["test"] 
       , ["hello", "world"] 
       , ["some", "random", "words"] 
       , ["not", "really", "random", "anymore"] 
       ] 

==> [ ["" , "" , ""  , "test" , ""  , ""  , ""  ] 
    , ["" , "" , "hello" , ""  , "world" , ""  , ""  ] 
    , ["" , "some", ""  , "random", ""  , "words", ""  ] 
    , ["not", "" , "really", ""  , "random", ""  , "anymore"] 
    ] 

अब आपको इन "" को डॉट्स से भरना होगा।

addDots ["test", "", "random", ""] 

==> ["test..","......","random","......"] 

और फिर fill बस

fill = transpose . map addDots . transpose 

और अपने कार्य है सिर्फ

triangle = map concat . fill . addPlaceholders 

Answer 2

मैं इस प्रकार समस्या से संपर्क करूंगा।

सबसे पहले, प्रत्येक शब्द की लंबाई को उपेक्षा करें। एम शतरंज द्वारा एन के बारे में सोचें, और प्रत्येक शब्द को एक वर्ग में रखें ताकि शब्द केवल काले वर्गों में समाप्त हो जाएं। अब, पंक्तियों की संख्या एन आपके शब्दों की सूचियों की संख्या है। पता करें कि क्या होना चाहिए।

आप अंत में एक त्रिकोण प्राप्त करने के लिए प्रत्येक पंक्ति में आवंटन "केंद्र" करना चाहते हैं।

फिर, शब्द की लंबाई पर विचार करें। एम कॉलम में से प्रत्येक को कितने चौड़े (वर्णों में) होना चाहिए? प्रत्येक कॉलम के लिए, इसकी चौड़ाई की गणना करें। इच्छित चौड़ाई तक पहुंचने के लिए प्रत्येक वर्ग को बिंदुओं के साथ भरें।

मैं कोई दावा इस सरल तरीका है - बस पहले एक है कि मुझे :) पास आया है यह

Answer 3

सबसे पहले, कुछ शब्दावली है: तो तुम एक सहायक समारोह, कि एक सूची में डॉट्स जोड़ता है लिख सकते हैं : किसी दिए गए पंक्ति के लिए, उदाहरण के लिए ["some", "more", "random", "words"], हम पंक्ति में "दिए गए शब्दकोष" पंक्ति में दिए गए शब्द की अनुक्रमणिका को कॉल करेंगे। इस प्रकार "more" में उस पंक्ति में तार्किक कॉलम 1 है; और "words" में लॉजिकल कॉलम 3 है।एक बार जब हम प्रत्येक शब्द के लिए स्थिति चुन लेते हैं, तो हमारे पास "भौतिक कॉलम" भी होगा जो कहता है कि पंक्ति को प्रस्तुत करते समय उसके सामने कितने अक्षर (बिंदु या अन्य शब्द वर्ण) दिखाई दे सकते हैं।

के एक सरल बनाने धारणा (समस्या काफी कठिन भी सरलीकृत है) करते हैं: अंतिम लेआउट में, पंक्ति r पर एक शब्द, तार्किक स्तंभ c शब्दों के बीच में पंक्ति r+1, तार्किक कॉलम c और c+1 पर होना चाहिए। इस समस्या से निपटने के लिए

एक विचार स्तंभ की एक तिहाई तरह जोड़ने के लिए, चलो यह एक "बिसात स्तंभ" कहते हैं, एक मध्यवर्ती कदम के रूप में जाने है। नीचे से भी कई चरणों में पंक्तियों में उनके सभी शब्द चेकरबोर्ड कॉलम में होंगे, और पंक्तियों की एक अजीब संख्या में पंक्तियों में उनके सभी शब्द अजीब चेकरबोर्ड कॉलम में होंगे। फिर प्रत्येक चेकरबोर्ड कॉलम के लिए चौड़ाई चुन सकते हैं, और एक शब्द के भौतिक कॉलम को छोटे से चेकरबोर्ड कॉलम की चौड़ाई के योग के रूप में सेट कर सकते हैं।

बहरहाल, यह एक मामूली समस्या है; इस बिसात, जहां मैं स्पष्ट रूप से बिसात स्तंभ सीमाओं बाहर चिह्नित किया है पर विचार करें:

| | |aa| | | 
| | b| |c| | 
|d| |e | |f| 
g| |hh| |i| |j 

क्योंकि हम प्रत्येक बिसात स्तंभ की चौड़ाई को चुना है, अलग अलग बिसात कॉलम में शब्द कभी नहीं ओवरलैप कर सकते हैं। इस के बाद एक तरह समाधान है, जो थोड़ा परिमित हैं बाहर नियम:

aa 
    b c 
d e f 
g hh i j 

ध्यान दें कि aa और hh ओवरलैप - हालांकि वे सन्निकट पंक्तियों पर नहीं हैं, तो यह ठीक है।

4 
    3 7 
2 6 9 
1 5 8 10 

जब किसी दिए गए शब्द बिछाने, हम तो बस छोटी से छोटी शारीरिक स्तंभ इसके लिए चुन सकते हैं कि देख कर नियमों का उल्लंघन नहीं करता है:

एक अन्य समाधान इस क्रम में शब्द बाहर रखना है ऊपर/बाएं और नीचे/बाईं ओर वाले शब्दों की स्थिति और लंबाई (जो पहले ही गणना की जाएगी)। मैं इस एल्गोरिथ्म, जो मैं (प्रति होमवर्क के बारे में साइट दिशा-निर्देश) कुछ ही दिनों में यह जवाब देने के लिए जोड़ देगा के एक कार्यान्वयन है, लेकिन यह संकेत पर्याप्त होना चाहिए आप अपने आप को बहुत यह की तरह कुछ पुन: पेश करने के लिए। मेरी कार्यान्वयन की दिलचस्प एल्गोरिथम बिट प्रकार Map (Row, LogicalColumn) String -> Map (Row, PhysicalColumn) String की एक दस लाइन समारोह है, और मैं तुम्हें एक इसी तरह टाइप किया समारोह में एक प्रयास कर सलाह देते हैं। इनपुट सूचियों के एक चतुर ट्रैवर्सल के साथ ऐसा करना संभव होना चाहिए (इसलिए किसी भी मैप इंडेक्सिंग लागत को समाप्त करना), लेकिन मैं इसके चारों ओर अपने सिर को लपेट नहीं पाया। हम प्रेरण से साबित कर सकते हैं (जहां हम जिस चर को शामिल कर रहे हैं वह वह क्रम है जिसे हम शब्दों को लिखते हैं) कि यह दृष्टिकोण न्यूनतम चौड़ाई के साथ समाधान उत्पन्न करता है।

के रूप में वादा किया था, कोड मैं के साथ आया था:

import Control.Applicative 
import Data.List 
import Data.Map hiding (empty, map) 
import Data.Ord 

type Row = Int 
type PhysicalColumn = Int 
type LogicalColumn = Int 

layout :: Map (Row, LogicalColumn) [a] -> Map (Row, PhysicalColumn) [a] 
layout m = munge answer where 
    answer = mapWithKey positionFor m 
    positionFor (r, c) as = maximumBy (comparing snd) . concat $ 
     [ [(as, 0)] 
     , addLength as <$> lookup (r+1, c ) answer 
     , addLength as <$> lookup (r-1, c-1) answer 
     ] 
    addLength as (v, p) = (as, p + length v) 
    lookup k m = maybe empty pure (Data.Map.lookup k m) 
    munge = fromAscList . map (\((r, _), (w, c)) -> ((r, c), w)) . toAscList 

parse :: String -> Map (Row, LogicalColumn) String 
parse = fromList 
     . enumerate 
     . map words 
     . lines 

enumerate :: [[a]] -> [((Row, LogicalColumn), a)] 
enumerate xss = concat . zipWith (\i xs -> [((i, j), x) | (j, x) <- xs]) [0..] . map (zip [0..]) $ xss 

groups :: Eq b => (a -> (b, c)) -> [a] -> [(b, [c])] 
groups f 
    = map (\pairs -> (fst . head $ pairs, map snd pairs)) 
    . groupBy ((==) `on` fst) 
    . map f 

flatten :: Map (Int, Int) [a] -> [(Int, [(Int, [a])])] 
flatten 
    = map (\(r, pairs) -> (r, map (concat <$>) (groups id pairs))) 
    . groups (\((r, c), a) -> (r, (c, a))) 
    . toAscList 

pad :: a -> [(Int, [a])] -> [a] 
pad blank = go 0 where 
    go n ((target, v):rest) = replicate (target-n) blank ++ v ++ go (target+length v) rest 
    go _ [] = [] 

pprint = unlines . map (pad ' ' . snd) . flatten 

allTogetherNow = putStr . pprint . layout . parse