जेनरेटिंग गेम स्काला

Question

के साथ कार्यात्मक रूप से चलता है मैं स्कैला का उपयोग करके लेखन रणनीति गेम को समझने की कोशिश कर रहा हूं, लेकिन दुर्भाग्यवश मुझे बहुत मूल बातें मिलती हैं। (यह घर का काम नहीं है, लेकिन कुछ नया, अर्थात् "शुद्ध" कार्यात्मक प्रोग्रामिंग जानने के लिए मेरे प्रयास।)

के निम्नलिखित सरल "खेल" लेते हैं: (एकमात्र) खिलाड़ी एक्स एक अंतहीन पंक्ति पर समान टुकड़े है वर्गों का टुकड़े वर्ग 0 पर शुरू होते हैं और प्रत्येक मोड़ वह एक टुकड़ा आगे एक वर्ग को स्थानांतरित कर सकता है।

डेटा संरचना के रूप में मैं List[Int] का उपयोग करूंगा प्रत्येक आइटम एक टुकड़ा की स्थिति (वर्ग) था।

संभव चाल मैं के साथ आया था बनाने के लिए:

def moves(start: List[Int]) = 
    (0 until start.length).map({i => start.updated(i, start(i) + 1)}); 

val m1 = moves(List(0,0,0)) 
// m1 then contains Vector(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1)) 

val m2 = moves(List(1,2,3)) 
// m1 then contains Vector(List(2, 2, 3), List(1, 3, 3), List(1, 2, 4)) 

क्या मुझे पसंद नहीं है सूचकांक पाश (0 until start.length) का उपयोग है। यह मेरे लिए बहुत "कार्यात्मक" प्रतीत नहीं होता है। क्या यह करने का सही तरीका है या क्या कोई बेहतर तरीका है?

---

अब मेरी खेल उदाहरण में सभी टुकड़ों को समान है, इसलिए मामले m1 में सभी तीन संभावित चाल भी समान हैं और/एक कदम के रूप में घनीभूत किया जाना चाहिए सकता है। मैं moves संशोधित, प्रत्येक चाल के आइटम सॉर्ट करने के लिए इतना है कि मैं अलग मदों की एक सूची प्राप्त कर सकते हैं:

def moves(start: List[Int]) = 
    (0 until start.length).map({i => start.updated(i, start(i) + 1).sorted}).distinct; 

val m1 = moves(List(0,0,0)) 
// m1 then contains Vector(List(0, 0, 1)) 

val m2 = moves(List(1,2,3)) 
// m1 then contains Vector(List(2, 2, 3), List(1, 3, 3), List(1, 2, 4)) 

हालांकि इस sortable और मेरे "वास्तविक" आवेदन में होने की डेटा संरचना की आवश्यकता है, यह एक List[Int] सबसे अधिक संभावना नहीं , लेकिन एक ट्यूपल या एक केस क्लास। मुझे लगता है कि मुझे एक distinct विधि चाहिए, जो एक समानता को परिभाषित करता है जो समानता को परिभाषित करता है। मैं इसे कैसे कार्यान्वित करूं?

Answer 1

यदि आपके टुकड़े समान हैं, तो मुझे लगता है कि आपको गलत डेटा संरचना मिली है। आप एक मानचित्र [Int, Int] चाहते हैं जहां कुंजी आपको अपने वर्ग की अनुक्रमणिका बताती है, और मूल्य आपको बताता है कि कितने टुकड़े हैं (कोई डिफ़ॉल्ट गिनती सेट नहीं है या यह भी आसान होगा)। फिर

def moves(start: Map[Int,Int]) = start.keySet.map(k => { 
    val n = start(k) 
    val pickup = (if (n == 1) (start - k) else start + (k -> (n-1))) 
    pickup + ((k+1) -> (start.getOrElse(k+1, 0) + 1)) 
}) 

यह आपके खिलौने उदाहरण में सभी समस्याओं को हल करता है (लेकिन शायद आपका असली नहीं)। और यह अच्छी तरह से तैयार करता है:

scala> val firstmoves = moves(Map(0->3))       
firstmoves: scala.collection.Set[scala.collection.immutable.Map[Int,Int]] = 
Set(Map((0,2), (1,1))) 

scala> val secondmoves = firstmoves.flatMap(moves)       
secondmoves: scala.collection.Set[scala.collection.immutable.Map[Int,Int]] = 
Set(Map((0,1), (1,2)), Map((0,2), (2,1))) 

scala> val thirdmoves = secondmoves.flatMap(moves) 
thirdmoves: scala.collection.Set[scala.collection.immutable.Map[Int,Int]] = 
Set(Map((1,3)), Map((0,1), (1,1), (2,1)), Map((0,2), (3,1))) 

Answer 2

एक छोटी सी पिकअप रूप में, आप start.indices साथ (0 until start.length) बदल सकते हैं। एक पुनरावर्ती समाधान सूचियों के उपयोग को पूरी तरह से बचा जाता है:

def moves(start: List[Int]): List[List[Int]] = start match { 
    case Nil => Nil 
    case head :: tail => (head + 1 :: tail) :: (moves(tail) map (head :: _)) 
} 

यह अनुक्रमित पहुँच का उपयोग कर की तुलना में बेहतर प्रदर्शन किया है, और यह भी, अपने समाधान की तुलना में बेहतर स्मृति पदचिह्न है के रूप में यह सूची घटकों के एक बहुत ही उच्च फिर से उपयोग किया है । यह एक सामान्य कार्यात्मक तकनीक का भी उपयोग करता है, जो समस्या को एक ज्ञात और एक पुनरावर्ती चरण में विभाजित करता है।

मुझे थोड़ा सा समझाएं। किसी भी गैर-खाली सूची के लिए, समाधान के तत्वों में से एक सूची पहले तत्व के साथ एक सूची होगी, और अन्य सभी तत्व समान होंगे। यह ऊपर गैर खाली सूची के लिए समाधान का पहला हिस्सा है:

head + 1 :: tail 

अब, सभी अन्य समाधान आम में है कि पहला तत्व एक ही हो जाएगा।एक संपीड़ित रूप में

solutions map (solution => head :: solution) 

या,

solutions map (head :: _) 

अब हम केवल गणना करने के लिए solutions की जरूरत: तो, कल्पना करो कि solutions सभी अन्य समाधान शून्य से पहला तत्व है, तो निम्नलिखित समाधान पुन: होगा । जैसा कि होता है, हमारे पास पहले से गणना करने का एक तरीका है: moves स्वयं! हम केवल यह सूची के tail को खिलाने के लिए है:

(moves(tail) map (head :: _)) 

तो, अगर हम इन दो एक साथ जोड़, हम समाधान उपरोक्त कोड में दिखाया गया है मिलता है।

कि सभी ने कहा, मैं यकीन नहीं करता है, तो एक सूची इस समस्या के लिए एक अच्छा डेटा संरचना या तो है।

समाधानों की एक अलग सूची प्राप्त करने के लिए, यदि आप चाल को स्टोर करने के लिए कक्षा बनाते हैं, तो आपके पास equals विधि हो सकती है जो तत्वों के क्रम को अनदेखा कर देती है, जिसमें distinct जैसी विधिएं ठीक काम करती हैं।

हैं कि व्यवहार्य नहीं है, तो आप SortedSet की एक खास इस्तेमाल कर सकते हैं - कि वे निहित Ordering का उपयोग समानता निर्धारित करने के लिए - समस्या को हल करने के लिए। उदाहरण के लिए:

object LO extends Ordering[List[Int]] { 
    def compare(x: List[Int], y: List[Int]) = cmp(x.sorted, y.sorted) 
    def cmp(x: List[Int], y: List[Int]): Int = (x, y) match { 
    case (Nil, Nil) => 0 
    case (Nil, _ ) => -1 
    case (_ , Nil) => 1 
    case (h1 :: t1, h2 :: t2) if h1 < h2 => -1 
    case (h1 :: t1, h2 :: t2) if h2 < h1 => 1 
    case (h1 :: t1, h2 :: t2) => cmp(t1, t2) 
    } 
} 

val m1 = SortedSet(moves(List(0, 0, 0)): _*)(LO).toList