🧛🏾 🐁 👩🏽‍💻 हास्केल पर आइंस्टीन की पहेली को सुलझाने 😭 👼🏻 🛡️

प्रस्तावना

बहुत समय पहले मैंने हबेरी पर एक लेख पढ़ा था जिसने मुझे एक दिलचस्प पहेली की याद दिलाई थी जिसे " आइंस्टीन पहेली " या "ज़ेबरा पहेली" कहा जाता था। संभवतः आप में से बहुत से लोगों ने इस समस्या को कागज के एक टुकड़े पर हल किया और इस बात पर गर्व किया कि वे दुनिया की आबादी का कुछ प्रतिशत सक्षम हैं।

लेख पढ़ने के बाद, मैंने इस समस्या के समाधान के बारे में सोचा। लेख में प्रस्तुत दृष्टिकोण दिलचस्प था और ब्लॉग के नाम को पूरी तरह से सही ठहराया, लेकिन यह मुझे पूरी तरह से स्पष्ट नहीं लग रहा था। फिलहाल, मुझे हास्केल प्रोग्रामिंग भाषा में दिलचस्पी है, जो मस्तिष्क को गर्म करने के लिए अपने आप में पूरी तरह से उपयुक्त है, लेकिन इस पर पहेली को हल करना मेरे लिए एक बड़ी चुनौती थी।

एल्गोरिथ्म

सामान्य तौर पर, कार्य इस तरह दिखता है:

वस्तुओं का एक क्रमबद्ध सेट है (स्थिति में पांच हैं और ये एक ही सड़क पर घर हैं);
प्रत्येक ऑब्जेक्ट में विशेषताओं का एक सेट होता है, जो बदले में मूल्यों के एक निश्चित सेट पर ले जा सकता है (ऐसी विशेषताओं की स्थिति में भी पांच हैं: मालिक की राष्ट्रीयता, घर का रंग, पालतू, पसंदीदा पेय और मालिक का सिगरेट ब्रांड);
विभिन्न वस्तुओं के लिए विशेषता मान समान नहीं हो सकते हैं और प्रत्येक विशेषता के मूल्यों की संख्या वस्तुओं की संख्या के बराबर है।
इसके अलावा, कई प्रतिबंध (15) दिए गए हैं जो विशेषता मूल्यों के संयोजन का वर्णन करते हैं (स्थिति का पूरा पाठ लेख की शुरुआत में एक लिंक से पढ़ा जा सकता है)।

सभी वस्तुओं (या उनमें से कुछ, जो एक और अन्य मामलों में एक ही है) के विशेषता मूल्यों को पुनर्स्थापित करना आवश्यक है, जो प्रतिबंधों का खंडन नहीं करेगा।

पहले सोचा था कि कार्यों की शर्तों की पूर्ति की जाँच के साथ विकल्पों की एक पूरी गणना है, लेकिन सरल गणना दर्शाती है कि संयोजनों की संख्या बराबर है
5! ⁵ = 24.883.200.000 5! ⁵ = 24.883.200.000 , जो काफी है।

कुछ विचारों के क्रम में, निम्नलिखित दृष्टिकोण का जन्म हुआ: समाधानों का एक स्वीकार्य स्थान है, बाधाएं समाधानों के सबसेट का वर्णन करती हैं, सही समाधान ऐसे सबसेट के चौराहे पर झूठ बोलते हैं (यानी, उस क्षेत्र में जहां सभी स्थितियां संतुष्ट हैं)।

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

निर्णय

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

इसलिए, मैंने अप्रशिक्षित लोगों द्वारा कार्यक्रम को पढ़ने में हस्तक्षेप करने वाले दृष्टिकोणों के उपयोग को कम करने की कोशिश की। समाधान पूरी तरह से सार्वभौमिक होने का दावा नहीं करता है, हालांकि, समस्याओं के इस वर्ग को हल करने के लिए कुछ उपकरणों का वर्णन किया गया है।

हालाँकि, अपने लिए पढ़ें - मैंने आपके लिए बहुत सारी टिप्पणियाँ छोड़ दी हैं।
लेकिन मुझे आपकी टिप्पणियों पर भी खुशी होगी।

आयात डेटा । सूची ( लुकअप , नब)
आयात डेटा । हो सकता है (मेम्बे , कैटमायब से)
-----------------------------------------------
- आइंस्टीन का रहस्य -
- अतामुर द्वारा -
-----------------------------------------------
---------------------------
- कार्य का सामान्य विवरण -
---------------------------
- समस्या का समाधान वस्तुओं का एक क्रम है
प्रकार समाधान = [वस्तु]
- प्रत्येक ऑब्जेक्ट को विशेषता जोड़े और उनके मूल्यों के एक सेट द्वारा वर्णित किया गया है
प्रकार वस्तु = [( स्ट्रिंग , स्ट्रिंग )]
- गुण-मान जोड़ी का संकेत = चिन्ह के साथ:
Attr = : value = (attr , value)
विशेषताएँ = [ "राष्ट्रीयता" , "घर" , "पालतू" , "पेय" , "धुआं" ]
आकार = 5
- हम कुछ को संतोषजनक समाधान खोजने की समस्या को हल करेंगे
- प्रतिबंध
- हम इसे सभी निर्णयों के सेट से शुरू करेंगे और धीरे-धीरे स्पष्ट करेंगे
यह एक समाधान तक कम होने तक एक सेट है, जो होगा
- सच।
- इसलिए, एक वस्तु तुरंत कई वास्तविक वस्तुओं का वर्णन कर सकती है,
- जिसमें कुछ विशेषताएँ सेट हैं, और बाकी (सेट नहीं)
- कोई भी हो सकता है। इसलिए, एक खाली वस्तु सभी संभव का एक टेम्पलेट है
- वस्तुएं:
anyObject = [] :: ऑब्जेक्ट
- और खाली वस्तुओं का सेट दिए गए के सामने सभी निर्णयों का सेट है
- आयाम:
anySolution = [anyObject | एन n [1 .. आकार]]
- प्रत्येक समाधान, समाधान के संगत सेट का वर्णन करता है, उदाहरण के लिए समाधान
- [["राष्ट्रीयता" =: "अंग्रेज"], anyObject, anyObject]
- वस्तुओं के सभी त्रिभुजों का वर्णन करता है, जिनमें से पहली में एक विशेषता है
- "राष्ट्रीयता अंग्रेजी है"
- लेकिन फैसलों को स्पष्ट करने में हमें कई असंगत होने की आवश्यकता है
- निर्णय (उदाहरण के लिए, "अंग्रेज या पहले या दूसरे लेकिन एक ही समय में नहीं"):
प्रकार समाधान = [समाधान]
खाली = [] :: समाधान
- समस्या को हल करने के लिए, हमें समाधान पर प्रतिबंध लगाने की आवश्यकता है
- प्रत्येक बाधा कई निर्णयों को बदल देगी
- परिणाम कई असंबंधित सेट या हो सकता है
- फैसलों का खाली सेट
प्रकार प्रतिबंध = समाधान → समाधान
- कई फैसलों पर प्रतिबंध लगाना
- कई समाधानों को बदलते समय, हम जांच करेंगे
- गुण मानों की विशिष्टता:
लागू करें :: प्रतिबंध → समाधान → समाधान
प्रतिबंधित सॉल लागू करें =
concat [ फ़िल्टर (डुप्लिकेट नहीं ) (प्रतिबंधित समाधान) | समाधान solution तल]
जहाँ
डुप्लिकेट सोल्स = कोई डुप्लिकेट वैल्यूज़ ( नक्शा (वैल्यू सोल) एट्रिब्यूट्स)
मान एसएलआर अटर = मानचित्र (लुकिंग एटर) सोल
डुप्लिकेट वैल्यूज़ ' =
मान दें
में (वैल्स val नूब वैल्स)
- वस्तुओं का वर्णन करने वाले दो पैटर्न का प्रतिच्छेदन
- दोनों स्रोत टेम्पलेट्स से विशेषता वाले एक टेम्पलेट हो सकता है,
- और स्रोत टेम्पलेट अलग होने पर असंगत हो सकते हैं
- समान विशेषताओं के मूल्य
दोनों :: वस्तु → वस्तु → शायद वस्तु
obj obj ' = foldl join (Just []) विशेषताएँ - विशेषता के अनुसार सम्मिलित हों
जहाँ
- यदि हमारे पास पहले से ही एक खाली सेट है, तो परिणाम भी खाली है
Join Nothing = _ कुछ नहीं
- अन्यथा हम विशेषताओं द्वारा बाधाओं के मूल्यों की तुलना करते हैं
join (बस बाकी) attr =
मामला ( लुकअप अटर ओज , लुकिंग अटर ओब्ज ’)
(कुछ नहीं , कुछ नहीं) → बस आराम करो
(बस मूल्य , कुछ नहीं) → बस ((Attr = : value): बाकी)
(कुछ नहीं , बस मूल्य) → बस ((Attr = : value): बाकी)
(बस मूल्य , जस्ट वैल्यू ’) →
यदि मान == मान '
तब बस ((attr = : value): बाकी)
और कुछ नहीं
- बुनियादी प्रतिबंध - किसी स्थिति में वस्तु के साथ मेल खाना चाहिए
- पूर्व निर्धारित टेम्पलेट
objectAt :: Int → ऑब्जेक्ट → प्रतिबंध
objectAt n obj solution =
मामला दोनों obj (समाधान !! (n - 1))
कुछ भी नहीं → खाली - यदि टेम्प्लेट पहले से ही वहां खड़े के साथ संगत नहीं है
बस Res → [बदलें n Res समाधान]
जहाँ
nx xs को बदलें = take (n - 1) xs ++ [x] ++ ड्रॉप n xs
- प्रतिबंधों पर संचालन ---------------------------------------------
- प्रतिच्छेदन - दोनों प्रतिबंध सत्य हैं
( < & > ) rs rs 'समाधान = rs (rs' समाधान लागू करें)
r _ all = foldl1 ( < & > ) - सेट से सभी प्रतिबंध
- मिलन - एक या दूसरा सत्य है
( <|> ) rs rs 'solution = rs solution ++ rs' समाधान
r _ any = foldl1 ( <|> ) - प्रतिबंधों में से एक
- प्राप्त प्रतिबंध ---------------------------------------------- -
- कुछ वस्तु है (या तो पहली स्थिति में, या दूसरी में, आदि)
present obj = r _ any [objectAt n obj | एन .. [1 .. 5]]
- एक वस्तु हमेशा दूसरे का अनुसरण करती है
obj से पहले ' = r _ any [
objectAt n obj < & > objectAt (n + 1) obj ' | n .. [1 .. आकार - 1]]
- पास (या दूसरे से पहले एक, या पहले के बाद दूसरा)
निकट obj obj ' = (obj `से पहले` obj') <|> (obj '` से पहले `obj)
------------------------------------------------
- विशिष्ट समस्याओं का विवरण -
------------------------------------------------
प्रतिबंध =
objectAt 1 [ "राष्ट्रीयता" = : "नॉर्वेजियन" ] < & >
मौजूद है [ "राष्ट्रीयता" = : "अंग्रेज" , "घर" = : "लाल" ] < & >
([ "घर" = : "हरा" ] `पहले " [ "घर" = : "सफेद" ] < & >
मौजूद है [ "राष्ट्रीयता" = : "डेन" , "पेय" = : "चाय" ] < & >
([ "धुआं" = : " मालबोरो " ] `निकट` [ " पालतू " = : " बिल्ली " ] < & >
मौजूद है [ "धूम्रपान" = : "डनहिल" , "घर" = : "पीला" ] < & >
मौजूद है [ "राष्ट्रीयता" = : "जर्मन" , "धुआं" = : "रोथमान्स" ] < & >
objectAt 3 [ "पेय" = : "दूध" ] < & >
([ "धुआं" = : " मालबोरो " ] `निकट` [ " पेय " = : " जल " ] < & >
मौजूद है [ "धुआं" = : "पाल्माल" , "पालतू" = : "पक्षी" ] < & >
मौजूद है [ "राष्ट्रीयता" = : "स्वेड" , "पालतू" = : "डॉग" ] < & >
([ "राष्ट्रीयता" = : "नॉर्वेजियन" ] `निकट` [ " घर " = : " ब्लू " ] < & >
मौजूद है "" पालतू " = : " घोड़ा " , " घर " = : " नीला " ] < & >
मौजूद है [ "धूम्रपान" = : "विनफील्ड" , "पेय" = : "बीयर" ] < & >
मौजूद [ "घर" = : "ग्रीन" , "पेय" = : "कॉफी" ] < & >
मौजूद है [ "pet" = : "मछली" ]
- मछली कहीं दिखाई नहीं देती है, यह पूछना आवश्यक है कि यह क्या है
मुख्य = समाधान दें = प्रतिबंध लागू करें [anySolution]
अगर लंबाई समाधान > 1 में
फिर putStrLn ( "कुल समाधान सेट:" ++ शो ( लंबाई समाधान))
और $ $ descrSolution $ सिर समाधान डाल दिया
-----------------------------
- स्ट्रिंग प्रतिनिधित्व -
-----------------------------
- एक व्यक्ति का स्ट्रिंग प्रतिनिधित्व:
descrMan man = descr "nationality" ++ "में रहता है" ++
descr "घर" ++ "घर," ++ का मालिक है
descr "pet" ++ ", पेय" ++
descr "पेय" ++ "और धूम्रपान" ++
descr "स्मोक"
descr attr = fromMaybe "?" ( लुक एटर मैन)
- समाधान का स्ट्रिंग प्रतिनिधित्व:
descrSolution sol = concat [descrMan man ++ + \ n " | आदमी ← सोल]

हास्केल पर आइंस्टीन की पहेली को सुलझाने

प्रस्तावना

एल्गोरिथ्म

निर्णय

More articles: