पैटर्न में गतिशील प्रोग्रामिंग

इस तरह की एक अद्भुत सप्ताहांत साइट है जैसे कि codeeval.com । जिस पर छोटी एल्गोरिथम समस्याओं का एक अच्छा संग्रह है और एक सुविधाजनक सत्यापन प्रणाली है जो मनोरंजक प्रोग्रामरों को एक मनोरंजक शाम बिताने की अनुमति देती है। आमतौर पर, एक परीक्षण डेटा फ़ाइल का उपयोग इनपुट के रूप में किया जाता है। हालाँकि, मुझे एक समस्या के बारे में पता चला जिसमें परीक्षण डेटा पहले से जाना जाता है। एक प्रोग्राम डाउनलोड करना जो केवल सही उत्तर प्रदर्शित करेगा, स्पोर्टी नहीं है, लेकिन संकलन चरण में इसकी गणना करना बस इतना ही है।

इसके बारे में क्या कहा अंदर देखा जा सकता है।

कार्य अपने आप में जटिल नहीं है और बहुत सरलता से पुनरावर्ती है। उदाहरण के लिए, निम्नलिखित फ़ंक्शन का उपयोग कर:

int GetRouteCount(int map, int x, int y) { if ((x == -1) || (y == -1) || (x == 4) || (y == 4)) return 0; if ((x == 3) && ( y == 3)) return 1; if ( ( map & (1 << ( ( x << 2) +y) )) != 0 ) return 0; map |= (1 << ( (x << 2) +y)); return GetRouteCount(map, x-1, y) + GetRouteCount(map, x+1, y) + GetRouteCount(map, x, y-1) + GetRouteCount(map, x, y+1); } 

और वास्तव में परिणाम मिल रहा है:

 int result = GetRouteCount(1, 0, 1) << 1; 

अब आइए टेम्प्लेट में समान गणना करने का प्रयास करें। टेम्पलेट मापदंडों के रूप में, हमें आंदोलनों के "मानचित्र" और वर्तमान बिंदु के निर्देशांक को प्रसारित करने की आवश्यकता है। चूँकि विशेषज्ञता का उपयोग इसके बजाय किया जाएगा, यदि बिंदु की यात्रा के लिए जाँच करने के लिए, आपको एक अलग टेम्पलेट बनाने की आवश्यकता है जिसमें इस मामले के लिए विशेषज्ञता होगी। यदि आप मुख्य टेम्प्लेट में एक और पैरामीटर जोड़ने का प्रयास करते हैं, तो आप संकलन चरण में असंगत स्थितियों का सामना करेंगे। एक यात्रा की जाँच इस तरह होगी:

 template< template<int, int, int> class _MR, int map, int x, int y, bool visited> struct GetCount { enum Result { value = _MR<(map | (1 << ( ( x << 2) +y ))), (x-1), y>::value + _MR<(map | (1 << ( ( x << 2) +y ))), (x+1), y>::value + _MR<(map | (1 << ( ( x << 2) +y ))), x, (y-1)>::value + _MR<(map | (1 << ( ( x << 2) +y ))), x, (y+1)>::value }; }; template< template<int, int, int> class _MR, int map, int x, int y> struct GetCount<_MR, map, x, y, true> { enum Result { value = 0 }; }; 

अब एक मूल टेम्प्लेट बनाएं जो निर्देशांक के विशेषज्ञ होंगे जो ग्रिड से आगे जाते हैं और सत्यापित करते हैं कि गंतव्य पहुंच गया है:

 template <int map, int x, int y> struct MapRoute { enum Result { value = GetCount<MapRoute, map, x, y, ( (map & ( 1 << ( (x << 2) +y))) != 0 )>::value }; }; template<int map, int y> struct MapRoute<map, -1, y> { enum Result { value = 0 }; }; template<int map, int y> struct MapRoute<map, 4, y> { enum Result { value = 0 }; }; template<int map, int x> struct MapRoute<map, x, -1> { enum Result { value = 0 }; }; template<int map, int x> struct MapRoute<map, x, 4> { enum Result { value = 0 }; }; template<int map> struct MapRoute<map, 3, 3> { enum Result { value = 1 }; }; 

यही कारण है कि, परिणाम प्राप्त करना लगभग उतना ही कठिन है जितना कि रनटाइम में गणना:

 int result = MapRoute<0, 0, 0>::value; 

आप सभी कोड और इसके निष्पादन के परिणाम को लिंक पर क्लिक करके देख सकते हैं।