कुछ घंटे पहले, ICFPC-2012 प्रतियोगिता शुरू हुई, जो
सभी सप्ताहांत तक चलेगी। मैंने इस प्रतियोगिता के लिए कार्य को इस उम्मीद में स्थानांतरित करने का निर्णय लिया कि इच्छुक लोगों में से एक के पास भाग लेने का समय होगा।
कार्य काफी समझ में आता है, इसलिए इसके लिए जाएं।
कार्य में परिवर्तन किए गए थे:
पानी ,
टेलीपोर्टर्स ,
दाढ़ी और
सुपर पत्थर ।
स्कॉटलैंड में लैंबडास की खानों की खोज आपका कार्य खदान के नक्शे को पढ़कर रोबोट के लिए एक कार्यक्रम बनाने में सक्षम होना है।
एक सुंदर सिम्युलेटर के लिए लिंक:
icfp.stbuehler.de/icfp2012बुनियादी नियम
- रोबोट किसी भी वर्ण को अज्ञात करता है (और केवल L, R, U, D, W, A इसे ज्ञात होता है।
- यदि रोबोट कमांड को निष्पादित नहीं कर सकता है, तो यह बस इस कदम को कुछ नहीं करता है।
- रोबोट के चलने के बाद, मानचित्र नीचे वर्णित नियमों के अनुसार अपडेट किया गया है।
- मानचित्र को अपडेट करने के बाद, पूरा होने की शर्तों की जाँच की जाती है।
कार्ड विवरण
एक नक्शा m × n कोशिकाओं का एक ग्रिड है, समन्वय (1,1)
नीचे और बाएं स्थित है।
प्रत्येक सेल में निम्न में से एक वर्ण होता है:
- आर - रोबोट
- * - पत्थर
- L - बंद निकास
- । - जमीन
- # - दीवार
- \ - λ
- ओ - खुला उत्पादन
- " "- अंतरिक्ष, खाली सेल
दीवार में कुछ भी नहीं घुस सकता। M × n क्षेत्र से आगे कुछ भी नहीं जा सकता है। एक रोबोट पृथ्वी को खोद सकता है, λ इकट्ठा कर सकता है और पत्थरों को स्थानांतरित कर सकता है। पत्थर गिर रहे हैं। पत्थर रोबोट को मार सकते हैं।
प्रारंभिक अवस्था का एक उदाहरण:
रोबोट कमांड्स
यदि रोबोट के निर्देशांक (x, y):
- एल - बाईं ओर, (x-1, y) के लिए
- आर - दाईं ओर, (x + 1, y)
- यू - अप, (x, y + 1)
- डी - डाउन, इन (एक्स, वाई -1)
- डब्ल्यू - रुको, कुछ भी मत करो
- ए - गर्भपात मेरा अन्वेषण
आप एक खुले निकास के साथ एक पिंजरे में, एक खाली पिंजरे में, पृथ्वी के साथ एक पिंजरे में और λ के साथ एक पिंजरे में जा सकते हैं। आप अभी भी (केवल बाएं और दाएं) एक पत्थर के साथ पिंजरे में स्थानांतरित कर सकते हैं, अगर पत्थर के पीछे एक खाली जगह है। पिंजरे से निकलने के बाद, रोबोट हमेशा पिंजरे में एक शून्य छोड़ देता है।
मानचित्र अद्यतन (सिमुलेशन)
रोबोट के आंदोलन के बाद सिमुलेशन कदम। इस अवस्था के दौरान, पुराना राज्य हमेशा नए के लिए पढ़ा और लिखा जाता है। निर्देशांक में निम्नलिखित क्रम में: (1, 1), (2, 1), ... (n, 1), (1, 2) ... (n, m)।
नियमों को क्रम से ऊपर से नीचे तक जांचा जाता है। अगर एक ने काम किया, तो अगला काम नहीं करेगा।
- पत्थर के नीचे एक शून्य है - पत्थर 1 सेल नीचे गिरता है।
- पत्थर के नीचे एक पत्थर है, दाईं ओर खाली और नीचे दाईं ओर खाली है - पत्थर तिरछे होकर दाईं ओर गिरता है।
- पत्थर के नीचे एक पत्थर है, बाईं तरफ खाली है और नीचे बाईं तरफ खाली है - पत्थर तिरछे बाईं ओर गिरता है।
- पत्थर के नीचे - λ, दाईं ओर खाली और निचले दाईं ओर खाली - पत्थर तिरछे से दाईं ओर गिरता है।
- शेष कोशिकाएं नहीं चलती हैं।
यदि कार्ड पर कोई λ अधिक नहीं है, तो सभी बंद आउटपुट खुले हैं।
अगर एक रोबोट एक पत्थर के नीचे खड़ा था जो बस गिर गया, तो रोबोट टूट गया, यह एक हार है।
एक सिमुलेशन कदम में, पत्थर 1 सेल नीचे गिरते हैं।
कभी-कभी विभिन्न पक्षों से पत्थर एक सेल में गिर सकते हैं। इस मामले में, 1 पत्थर अब इस सेल में स्थित है।
पूर्णता की स्थिति
- रोबोट ओपन लिफ्ट - जीतता है
- रोबोट ने कमांड ए - विन को निष्पादित किया
- स्टोन क्रश रोबोट - LOSE
इनपुट / आउटपुट
स्टड से इनपुट, आउटपुट से स्टडआउट
यदि कुछ रेखाएं अधिकतम रेखा की लंबाई से छोटी हैं, तो उन्हें दाईं ओर रिक्त स्थान के साथ गद्देदार माना जाता है।
शुरुआत में प्रत्येक नक्शे पर कोई खुला निकास नहीं होता है। बिल्कुल 1 रोबोट है और ठीक 1 बंद आउटपुट है।
कार्ड 1000 × 1000 या अधिक हो सकता है।
स्कोरिंग अंक
प्रत्येक चरण -1 के लिए
एकत्र λ के लिए +25
कमान ए के निष्पादन के समय एकत्र किए गए λ के लिए
आउटपुट ५० तक पहुँचने के समय एकत्रित λ के लिए
आपके टेस्ट कार्ड पासिंग विकल्पों के परीक्षण के लिए स्क्रिप्ट:
सत्यापनकर्तासीमा
कार्यक्रम 1 जीबी रैम के साथ 32 बिट डेबियन-लाइनक्स पर चलना चाहिए।
150 सेकंड के बाद, कार्यक्रम SIGINT प्राप्त करता है, जिसके बाद प्रतिक्रिया को आउटपुट करने के लिए 10 सेकंड का समय होता है।
इन 10 सेकंड के बाद SIGKILL और 0 अंक।
प्रतियोगिता के दौरान 1 से 4 नियम परिवर्तन होंगे।
अंग्रेजी में विवरण:
icfpcontest2012.wordpress.comपहला नियम परिवर्तन: पानी
कुछ खानों में बाढ़ आने लगी!
अब नक्शे के विवरण के बाद एक खाली लाइन और फिर 3 पैरामीटर (प्रति पंक्ति) हो सकते हैं:
पानी ०
बाढ़ ०
पनरोक १०
(0, 0, 10) - डिफ़ॉल्ट मान।
जल जल स्तर के प्रारंभिक मूल्य को इंगित करता है (याद रखें कि हम 1 से निर्देशांक गिनते हैं, और जल स्तर 0 हो सकता है)।
बाढ़ - पानी के आगमन की गति। यदि 0 - पानी बिल्कुल नहीं आता है। यदि एन> 0, तो एन चरणों के ठीक बाद जल स्तर 1 से बढ़ जाता है।
जलरोधी - रोबोट के संरक्षण का स्तर, बिना गोताखोरी के कितने कदम पानी के नीचे जा सकते हैं। जैसे ही यह उभरता है, कदम काउंटर रीसेट करता है और आप फिर से गोता लगा सकते हैं।
एक रोबोट को पानी के नीचे माना जाता है यदि उसका y समन्वय करता है
<= जल स्तर।
यदि रोबोट पानी के नीचे के चरणों से अधिक खर्च करता है, तो यह टूट जाता है।
दूसरा नियम परिवर्तन: टेलीपोर्टर्स
टेलीफ़ोन को गेम में जोड़ा गया है (गोदी में डाइविंग बोर्ड)। टेलीपोर्ट के इनपुट को A..I अक्षरों द्वारा दर्शाया गया है, टेलीपोर्ट का आउटपुट नंबर 1..9 है।
टेलीपोर्ट में प्रवेश करने के बाद, टेलीपोर्ट प्रवेश और इसका निकास गायब हो जाता है।
किस प्रविष्टि से कार्ड के बाद बाहर निकलने का वर्णन है
Trampoline एक लक्ष्य 1
Trampoline बी लक्ष्य 1
Trampoline C लक्ष्य 2
तीसरा नियम परिवर्तन: बायोमास और रेज़र
जोड़ा दाढ़ी -
डब्ल्यू और रेजर -
! । नक्शे के अंत में अब यह लिखा जाता है कि रेजर के पास कितने रेज़र हैं और दाढ़ी कितनी तेजी से बढ़ती है:
विकास 15
उस्तरा २
डिफ़ॉल्ट रूप से वृद्धि मूल्य (छ) 25 है, रेजर की संख्या 0 है।
प्रत्येक जी चरण, एक दाढ़ी 8 पड़ोसी कोशिकाओं को भरता है यदि वे खाली हैं (जो कि विकर्ण सहित है)।
दाढ़ी से निपटने का एकमात्र तरीका रेजर है। एस कमांड को निष्पादित करने के बाद, एक रेजर (यदि रोबोट में एक है) लागू किया जाता है और 8 पड़ोसी कोशिकाओं की दाढ़ी को साफ करता है।
अंतिम नियम परिवर्तन: उच्च क्रम वाले पत्थर
जोड़ा गया @ - उच्च क्रम के पत्थर, जिसके अंदर λ छिपे हुए हैं। किसी भी ऊंचाई से गिरने पर, पत्थर टूट जाता है और उसके स्थान पर λ दिखाई देता है।
कठिनाई मूल्यांकन के बारे में
कृपया ध्यान दें कि यह कार्य जटिल बोल्डर डैश के समान है, जिसके पारित होने पर, सामान्य मामले में, जैसा कि सिद्ध किया गया है, एक एनपी-पूर्ण कार्य है।
प्रमाण काफी सरल है: ऐसे लेबिरिंथ हैं जिनका समाधान एक ग्राफ में हैमिल्टन चक्र खोजने के बराबर है, और यह एक अच्छी तरह से ज्ञात समस्या है:
विकि हैमिल्टन चक्र