तो साथ बदलें चाहते हैं आप एक NxN ग्रिड है और आप सभी क्षैतिज निकालना चाहते हैं , लंबाई एम की ऊर्ध्वाधर और विकर्ण रेखाएं, फिर अधिकतम उत्पाद खोजने के लिए। पर उदाहरण 4x4 ग्रिड कुछ हास्केल तकनीक को वर्णन करते हैं, लाइन की लंबाई जा रहा है 2 के साथ:
chunks 2 [1,2,3,4] == [[1,2],[2,3],[3,4]]
:
[[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9,10,11,12],
[13,14,15,16]]
क्षैतिज और ऊर्ध्वाधर आसान है, आप सभी की जरूरत एक समारोह है कि एक सूची से लंबाई एम का हिस्सा निकालने है
इस तरह का फ़ंक्शन [a] -> [[a]] है।यह एक सूची से संबंधित कार्य है, इसलिए पहिया को फिर से शुरू करने से पहले, देखते हैं कि Data.List में कुछ ऐसा है या नहीं। अहा, tails समान है, यह सूची की शुरुआत से हटाया से अधिक से अधिक तत्वों के साथ सूचियों रिटर्न:
tails [1,2,3,4] == [[1,2,3,4],[2,3,4],[3,4],[4],[]]
केवल हम उन्हें लंबाई 2. बनाने के लिए उप-सूचियों को छोटा कर सकता है लेकिन हम, map का उपयोग करके कर सकते हैं समारोह, सूची के प्रत्येक तत्व के लिए एक समारोह लागू होता है और एक नई सूची देता है जो:
map (take n) (tails xs) -- [[1,2],[2,3],[3,4],[4],[]]
मैं छोटे लाइनों के बारे में चिंता नहीं करता, के रूप में मूल कार्य सबसे बड़ी उत्पाद मिल रहा है, और [15, N] ≥ के उत्पाद [15], एन ≥ 1. का उत्पाद। लेकिन यदि आप उनसे छुटकारा पाना चाहते हैं, तो ऐसा लगता है लंबाई की सूची में एन में लंबाई एम के एन-एम + 1 भाग होते हैं, इसलिए आप परिणामी सूची में take (4-2+1) लागू कर सकते हैं। वैकल्पिक रूप से आप कर सकते थे बस filter सूची:
chunks n xs = filter ((==n) . length) $ map (take n) (tails xs)
-- [[1,2],[2,3],[3,4]]
ठीक है, हम एक सूची से हिस्सा की एक सूची निकाल सकते हैं, लेकिन हम एक 2 डी ग्रिड, नहीं एक फ्लैट सूची है! map फिर हमें बचाता है:
map (chunks 2) grid -- [[[1,2],[2,3],[3,4]],[[5,6],[6,7],[7,8]],...]
लेकिन यहाँ बात है, जिसके परिणामस्वरूप कोड अलग-अलग सूचियों में हिस्सा रखती है, और बातें पेचीदा हो, जैसा कि हम वास्तव में, परवाह नहीं है जो लाइन से हिस्सा ही शुरू होता है। इसलिए हम concat . map या समकक्ष concatMap द्वारा एक स्तर है, जिसके परिणामस्वरूप सूची समतल करना चाहेंगे: अब
concatMap (chunks 2) grid -- [[1,2],[2,3],[3,4],[5,6],[6,7],[7,8],...]
, मैं कैसे एक ग्रिड से खड़ी हिस्सा मिलता है? पहली बार में डरावना लगता है, जब तक आप महसूस करते हैं कि आप पूरे ग्रिड transpose कर सकते हैं, जैसे कि पंक्तियों में स्तंभों और स्तंभों में पंक्तियों की बारी है, और फिर एक ही कोड लागू करें:
concatMap (chunks 2) (transpose grid) -- [[1,5],[5,9],[9,13],[2,6],[6,10],...]
अब कठिन हिस्सा: विकर्ण लाइनों। Norman Ramsey एक विचार देता है: क्या होगा यदि आप लाइन 0 से 0 तत्वों को छोड़ सकते हैं, लाइन 1 से 1 तत्व इत्यादि? विकर्ण रेखा एक ऊर्ध्वाधर रेखा बन जाएगी, जो निकालना आसान है। आपको याद है कि सूची के प्रत्येक तत्व में एक फ़ंक्शन लागू करने के लिए आप map का उपयोग करते हैं, लेकिन यहां आपको प्रत्येक तत्व, drop 0, drop 1, drop 2, आदि map के अनुरूप विभिन्न कार्यों को लागू करने की आवश्यकता नहीं है। लेकिन देखो, drop का पहला तर्क लगातार संख्याओं का एक पैटर्न बनाता है, जिसे अनंत सूची [0..] के रूप में प्रदर्शित किया जा सकता है। अब क्या होगा यदि हम [0..] से एक तत्व ले सकते हैं तो हमें एक ऐसी फ़ंक्शन है जो एक अनंत सूची [0..] और ग्रिड से एक पंक्ति से एक संख्या लेती है, और इस संख्या के साथ drop लागू होती है। zipWith तुम क्या जरूरत है:
zipWith drop [0..] grid -- [[1,2,3,4],[6,7,8],[11,12],[16]]
map head $ zipWith drop [0..] grid -- [1,6,11,16]
लेकिन मैं लंबाई 2 के सभी विकर्ण, न सिर्फ सबसे बड़ी विकर्ण चाहते हैं। तो ग्रिड को देखो और सोचें, पंक्ति 0 पर तत्वों के साथ आप कौन सी विकर्ण रेखाएं देखते हैं? [1,6],[2,7],[3,8]। कैसे मैं अन्य पंक्तियों से शुरू के रूप में अच्छी विकर्णों मिलता है
transpose $ zipWith drop [0,1] grid -- [[1,6],[2,7],[3,8],[4]]
अब: तो यह स्पष्ट है कि आप केवल पहले 2 पंक्तियाँ लेने के लिए और तत्वों स्थानांतरित करने के लिए की जरूरत है? हमारी tails चाल याद रखें?हम एक concatMap के लिए हमारी नई समारोह प्रदान करने और tails grid पर लागू करके सभी विकर्णों प्राप्त कर सकते हैं:
concatMap (transpose . zipWith drop [0,1]) (tails g)
-- [[1,6],[2,7],[3,8],[5,10],[6,11],...]
लेकिन इन केवल विकर्णों कि से जाना जाता है ऊपर-बाईं ओर निचले-दाएं कोने। उन लोगों के बारे में क्या जो ऊपर-दाएं से नीचे-बाएं जाते हैं? बस ग्रिड की पंक्तियों को उल्टा करने के यह सबसे आसान है:
concatMap (transpose . zipWith drop [0,1]) (tails $ reverse g)
-- [[13,10],[14,11],[15,12],[9,6],[10,7],...]
अंत में, आप सभी लाइनों के उत्पादों को खोजने और सबसे बड़ी चयन करने के लिए की जरूरत है। अंतिम कोड इस तरह दिखता है:
grid = [[1..4],[5..8],[9..12],[13..16]]
chunks n xs = map (take n) (tails xs)
horizontal = concatMap (chunks 2) grid
vertical = concatMap (chunks 2) (transpose grid)
grave = concatMap (transpose . zipWith drop [0,1]) (tails grid)
acute = concatMap (transpose . zipWith drop [0,1]) (tails $ reverse grid)
maxProduct = maximum $ map product $ horizontal ++ vertical ++ grave ++ acute
-- answer: 240
क्या यह कोड अधिकतम रूप से सुरुचिपूर्ण और कुशल है? नरक नहीं, लेकिन यह काम करता है और कार्यात्मक प्रोग्रामिंग की सोच के कुछ पैटर्न दिखाता है। सबसे पहले आपको केवल उस कोड को लिखने की आवश्यकता होती है जो केवल काम करता है, फिर इसे पुन: सक्रिय करें, जब तक कि आप उस समाधान पर न आएं जो पढ़ने और सामान्य दोनों आसान हो।
कृपया यूलर समस्या संख्या भी निर्दिष्ट करें। कुछ लोगों ने पहले से ही इसे हल कर लिया है और शायद अपने स्वयं के समाधान को देखने की इच्छा रख सकते हैं, और शायद आपको – yairchu
पर आधारित एक उपयोगी उत्तर दे सकते हैं। यह समस्या # 11 – MtnViewMark