2010-12-27 9 views
9

हाल ही में मैं एक "Scramble Squares" टाइल पहेली का समाधान निर्धारित करने के लिए एक रूबी कार्यक्रम ने लिखा है:अज्ञात उत्तर के साथ पहेली को हल करने के लिए मैं टीडीडी का उपयोग कैसे कर सकता हूं?

मैं TDD इस्तेमाल किया इसमें से अधिकांश को लागू करने, परीक्षण है कि इस तरह देखा करने के लिए अग्रणी:

it "has top, bottom, left, right" do 
    c = Cards.new 
    card = c.cards[0] 
    card.top.should == :CT 
    card.bottom.should == :WB 
    card.left.should == :MT 
    card.right.should == :BT 
end 

यह निचले स्तर के "सहायक" तरीकों के लिए अच्छा काम करता है: एक टाइल के "पक्ष" की पहचान करना, यह निर्धारित करना कि ग्रिड में टाइल को वैध रूप से रखा जा सकता है या नहीं।

लेकिन मैं पहेली को हल करने के लिए वास्तविक एल्गोरिदम कोडिंग करते समय एक समस्या में भाग गया। चूंकि मुझे समस्या के वैध संभावित समाधान नहीं पता था, मुझे नहीं पता था कि पहले परीक्षण कैसे लिखना है।

def play_game 
    working_states = [] 
    after_1 = step_1 
    i = 0 
    after_1.each do |state_1| 
     step_2(state_1).each do |state_2| 
     step_3(state_2).each do |state_3| 
      step_4(state_3).each do |state_4| 
      step_5(state_4).each do |state_5| 
       step_6(state_5).each do |state_6| 
       step_7(state_6).each do |state_7| 
        step_8(state_7).each do |state_8| 
        step_9(state_8).each do |state_9| 
         working_states << state_9[0] 
        end 
        end 
       end 
       end 
      end 
      end 
     end 
     end 
    end 

तो मेरे सवाल है: कैसे आप TDD प्रयोग करते हैं एक विधि लिखने के लिए जब आप पहले से ही पता नहीं है

मैं इसे हल करने के लिए एक बहुत बदसूरत, अपरीक्षित, एल्गोरिथ्म लेखन समाप्त हो गया मान्य आउटपुट?

आप रुचि रखते हैं, कोड GitHub पर है:

उत्तर

8

यह सीधा जवाब नहीं है, लेकिन यह मुझे पीटर Norvig और रॉन जेफ़री द्वारा लिखे गए सुडोकू solvers के बीच the comparison की याद दिलाता है। रॉन जेफरी के दृष्टिकोण ने क्लासिक टीडीडी का इस्तेमाल किया, लेकिन उन्हें वास्तव में कोई अच्छा समाधान नहीं मिला। दूसरी ओर, Norvig, टीडीडी के बिना इसे बहुत सुंदर ढंग से हल करने में सक्षम था।

मौलिक सवाल यह है: क्या एल्गोरिदम टीडीडी का उपयोग कर उभर सकता है?

+0

मुझे लगता है कि अगर आप एक को पता करने के लिए होगा इससे पहले कि आप इसके लिए परीक्षण लिख सकें, लिगोरिदम (या कम से कम इसके टुकड़े)। लिंक के लिए +1, बहुत दिलचस्प है। –

+1

http://pindancing.blogspot.com/2009/09/sudoku-in-coders-at-work.html आपके लिंक से लिंक ओपी को "उत्तर" के प्रकार पर चर्चा करने लगता है। –

+0

सभी के लिए लिंक के लिए धन्यवाद। ऐसा लगता है कि इस ** विशेष ** समस्या स्थान (एक पहेली को हल करने के लिए एक एल्गोरिदम उत्पन्न करना), "डिजाइन के रूप में डिजाइन करने के लिए परीक्षण परीक्षणों" का दृष्टिकोण बेकार या अक्षम समाधानों का कारण बनता है। यह मुझे [टीडीडी की इन आलोचनाओं] की याद दिलाता है (http://www.dalkescientific.com/writings/diary/archive/2009/12/29/problems_with_tdd.html)। मुझे यकीन नहीं है कि आप प्रक्रिया पर खुद को एक व्यापक निर्णय ले सकते हैं। कम से कम, मैं वास्तविक समस्या को हल करने में डाइविंग से पहले उपलब्ध निम्न स्तर की विधियों को काम करने (और परीक्षण) करने के लिए बहुत खुश था। – matthewsteele

1

puzzle website से:

वस्तु स्क्रैबल स्क्वायर® पु zzle गेम नौ रंगीन सचित्र वर्ग के टुकड़े को 12 "x 12" वर्ग में व्यवस्थित करना है ताकि टुकड़े ' किनारों पर यथार्थवादी ग्राफिक्स प्रत्येक दिशा में पूर्ण डिज़ाइन बनाने के लिए पूरी तरह मिलान करें।

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

एक बार match() काम कर रहा है, हम यहां से कहां जाते हैं? खैर, एक स्पष्ट समाधान ब्रूट फोर्स है: ग्रिड के भीतर टाइल्स की सभी संभावित व्यवस्थाओं के सेट से, उनको अस्वीकार करें जहां कोई भी दो निकटतम टाइल्स मेल नहीं खाते हैं। यह एक प्रकार का एल्गोरिदम है, और यह काम करने के लिए बहुत निश्चित है (हालांकि कई पहेलियों में ब्रह्मांड की गर्मी की मृत्यु समाधान से पहले होती है)।

किसी दिए गए किनारे (एलटीआरबी) के साथ मेल खाने वाली टाइल्स के सभी जोड़े के सेट को एकत्रित करने के बारे में कैसे? क्या आप वहां से समाधान तक पहुंच सकते हैं, जल्दी? निश्चित रूप से आप इसे आसानी से पर्याप्त (और परीक्षण-ड्राइव) का परीक्षण कर सकते हैं।

परीक्षण आपको एक एल्गोरिदम देने की संभावना नहीं है, लेकिन वे आपको एल्गोरिदम के बारे में सोचने में मदद कर सकते हैं, और निश्चित रूप से वे आपके दृष्टिकोण को आसान बना सकते हैं।

0

पता नहीं अगर यह "उत्तर" सवाल या तो "पहेली" के

विश्लेषण

9 टाइल्स
प्रत्येक 4 पक्षों
प्रत्येक टाइल आधा एक पैटर्न/चित्र

जानवर है फोर्स APPROACH

इस समस्या को हल करने के लिए आपको 9 उत्पन्न करने की आवश्यकता है! संयोजन (9 टाइल्स एक्स 8 टाइल X 7 टाइल ...)

पहले से ही जगह

माना दृष्टिकोण

क्यू कितने पहलू हैं में मौजूदा टाइल (ओं) को मिलान पक्षों की संख्या से सीमित विभिन्न? आईई कितने मैच हैं?

इसलिए 9 एक्स 4 = 36 पक्षों/2 (के बाद से हर तरफ "चाहिए" मैच कम से कम 1 दूसरी तरफ)
अन्यथा इसकी एक uncompleteable पहेली
नोट: कम से कम 12 "सही ढंग से" से मेल खाना चाहिए एक 3 एक्स के लिए 3 पहेली

लेबल एक अनूठा पत्र

तो का उपयोग कर एक टाइल से प्रत्येक मिलान की ओर प्रत्येक टाइल
आप प्रत्येक टाइल
4 पक्षों (कोनों) इसलिए 4 के लिए तालिका में 4 प्रविष्टियों की आवश्यकता होगी पकड़े एक मेज का निर्माण संयोजन
अगर आप पक्ष और सूचकांक के आधार पर तालिका तालिका

पक्ष में tile_1
BCda tile_1
CDab tile_1
DAbc tile_1

सॉर्ट तालिका का उपयोग कर चीज़ों को गति चाहिए
tile_number
ABCD, क्योंकि आपको केवल
पर केवल 1 या 2 पक्षों से मेल खाना चाहिए, यह

01 को करने के लिए गैर उत्पादक टाइल की मात्रा को सीमित करता है

पैटर्न/चित्र
वहाँ 3 संयोजन (झुकाव) कर रहे हैं के बाद से प्रत्येक टाइल 3 झुकाव
का उपयोग कर रखा जा सकता है की डिजाइन के आधार पर - एक ही (समान टाइल की कई प्रतियां)
- प्रतिबिंब
- रोटेशन

भगवान हमारी मदद करता है, तो वे दूसरी तरफ यह भी कहा कि मैच के लिए
या यहाँ तक कि क्यूब्स में टाइल बनाने और 6 पक्षों मिलान की जरूरत पर समान पैटर्न/तस्वीरें डालकर जीवन बहुत मुश्किल
बनाने का निर्णय !!!

का उपयोग TDD,
आप समस्या से प्रत्येक छोटा सा हिस्सा हल करने के लिए परीक्षण और उसके बाद कोड लिखते थे,
जैसा कि ऊपर बताया और पूरे समस्या को हल करने

नहीं इसकी आसान नहीं और अधिक परीक्षण और कोड लिखने, आप बैठते हैं और परीक्षण लिखने और कोड

नोट अभ्यास करने के लिए की जरूरत है: इस नक्शे रंग समस्या की एक विविधता है

संबंधित मुद्दे

 संबंधित मुद्दे