फ्रंटेंड, एल्गोरिदम और फ्रेडरिक पर कब्जा। हम यैंडेक्स प्रतियोगिता के कार्यों का विश्लेषण करते हैं

इस पोस्ट के साथ, हम 2018 में Yandex.Blitz प्रतियोगिताओं के बारे में प्रकाशनों की एक श्रृंखला पूरी कर रहे हैं। हम आशा करते हैं कि आपके पास भाग लेने या कम से कम यह देखने का अवसर था कि हम उत्पादन के करीब किस तरह के कार्य प्रस्तावित करते हैं। अंतिम प्रतियोगिता सीमांत में एल्गोरिदम के उपयोग के लिए समर्पित थी। आज हम 12 समस्याओं का विस्तृत विश्लेषण प्रकाशित करते हैं: उनमें से पहले 6 को क्वालिफिकेशन राउंड में प्रस्तावित किया गया था, और फ़ाइनल में 7–12 को समस्याएं। हमने यह बताने की कोशिश की कि कैसे स्थितियां बनीं, हमने किन कौशलों पर ध्यान दिया। सभी प्रतिभागियों को उनकी रुचि के लिए धन्यवाद!

टास्क 1

पहला कार्य 20 मिनट के लिए वार्म-अप होना था, और हमने इसकी स्थिति बनाने का फैसला किया ताकि इसे नियमित अभिव्यक्तियों की मदद से आसानी से हल किया जा सके।

कार्य के सभी विकल्पों का निर्माण एक समान तरीके से किया जाता है - अंकों में एक विघटन होता है, जिनमें से प्रत्येक को अंतिम नियमित अभिव्यक्ति में समूह द्वारा दर्शाया जा सकता है।

विकल्पों में से एक पर विचार करें: पोस्ट ऑफिस।

शर्त

Jopan-14-53 ग्रह पर, स्थानीय लोग एक-दूसरे को पत्र भेजना चाहते हैं, लेकिन कबूतर रोबोट जो उन्हें वितरित करना चाहिए, वे पते में भ्रमित हैं। आपको उन्हें पत्रों को पार्स करना और वैधता के लिए जांचना सिखाना होगा।

पते के मूल भाग की संरचना में क्षेत्र, नगरपालिका, नाम और पते का उपनाम शामिल है। नगरपालिका को काउंटियों और डाकघरों में विभाजित किया जा सकता है। सभी भागों को एक अल्पविराम द्वारा अलग किया जाता है,।

क्षेत्रों, नगर पालिकाओं और जिलों के नाम शब्द हैं, प्रत्येक शब्द में पहला अक्षर बड़ा है, बाकी छोटे हैं। दो-शब्द नाम संभव हैं, एक स्थान या एक शून्य चिह्न द्वारा अलग किए गए हैं। प्रत्येक शब्द में तीन से आठ अक्षर AZ।

निवासियों के हाथों में 6 उंगलियां हैं, रोजमर्रा की जिंदगी में ग्रहणी प्रणाली। संख्या ०- ९ का उपयोग किया जाता है, और १० और ११ संकेत ~ और – द्वारा दर्शाए जाते हैं।

रचना में पोस्ट ऑफिस नंबर में या तो 3 अंक एक पंक्ति में होते हैं, या 4 शून्य से 2 अंकों के 2 समूहों में विभाजित होते हैं। उदाहरण: 300 , 44-99 ।

कभी-कभी निवासी मांग पर नगरपालिका को पत्र भेजते हैं। इस मामले में, कोई पता नहीं है: केवल नगरपालिका और पते वाले का नाम।

यह हास्यास्पद है, लेकिन ग्रह पर लोगों को केवल छह नाम और नौ उपनाम कहा जाता है। नाम: शोब, रयोब, मोब, जियांग, रयान, मैन्स। उपनाम: थानेदार, रियो, मो, ज़िया, राया, मा, स्यू, रयू, मु। इस ग्रह के निवासी सपने देखने वाले नहीं हैं।

पदच्छेद

पते के मूल भाग की संरचना में क्षेत्र, नगरपालिका, नाम और पते का उपनाम शामिल है। नगरपालिका को काउंटियों और डाकघरों में विभाजित किया जा सकता है। सभी भागों को एक अल्पविराम द्वारा अलग किया जाता है,।

पहले पैराग्राफ से हम सीखते हैं कि क्षेत्र, नगरपालिका, जिला, डाकघर, नाम और उपनाम को कैसे इंगित किया जाए, और उन्हें किस क्रम में परीक्षण किए गए क्रम में पालन करना चाहिए।

क्षेत्रों, नगर पालिकाओं और जिलों के नाम शब्द हैं, प्रत्येक शब्द में पहला अक्षर बड़ा है, बाकी छोटे हैं। दो-शब्द नाम संभव हैं, एक स्थान या एक शून्य चिह्न द्वारा अलग किए गए हैं। प्रत्येक शब्द में तीन से आठ अक्षर AZ।

इस पैराग्राफ से यह स्पष्ट है कि समूह शब्दों से मेल खाता है ([-][-]{2,7}) । और नाम क्रमशः, ([-][-]{2,7}(?:[- ][-][-]{2,7})) ।

निवासियों के हाथों में 6 उंगलियां हैं, रोजमर्रा की जिंदगी में ग्रहणी प्रणाली। संख्या ०- ९ का उपयोग किया जाता है, और १० और ११ संकेत ~ और – द्वारा दर्शाए जाते हैं।

यहां हम सीखते हैं कि संख्याओं के लिए \d का उपयोग करना पर्याप्त नहीं है - आपको [0-9~≈] का उपयोग करने की आवश्यकता है।

रचना में पोस्ट ऑफिस नंबर में या तो 3 अंक एक पंक्ति में होते हैं, या 4 शून्य से 2 अंकों के 2 समूहों में विभाजित होते हैं। उदाहरण: 300 , 44-99 ।

इस प्रकार, समूह पोस्ट ऑफिस नंबर ([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2}) मेल खाता है।

कभी-कभी निवासी मांग पर नगरपालिका को पत्र भेजते हैं। इस मामले में, कोई पता नहीं है: केवल नगरपालिका और पते वाले का नाम।

हम अंतिम फ़ंक्शन की विधानसभा में समझते हैं, याद करते हैं और ध्यान में रखते हैं कि जिला और पोस्ट ऑफिस एक साथ अनुपस्थित हो सकते हैं।

यह हास्यास्पद है, लेकिन ग्रह पर लोगों को केवल छह नाम और नौ उपनाम कहा जाता है। नाम: शोब, रयोब, मोब, जियांग, रयान, मैन्स। उपनाम: थानेदार, रियो, मो, ज़िया, राया, मा, स्यू, रयू, मु। इस ग्रह के निवासी सपने देखने वाले नहीं हैं।

यह हालत का आखिरी हिस्सा है। यहाँ एक और सरल समूह की आवश्यकता थी (||||||||) (|||||) या इसके छोटे समकक्ष ([][]|[]) ([C]|[]||)

सरलता के लिए, हम समूहों को चर में सहेजते हैं और परिणामी नियमित अभिव्यक्ति में उनका उपयोग करते हैं।

 const w = '[-][-]{2,7}'; // word const d = '[0-9~≈]'; // digit const name = `(?:${w}(?:[- ]${w})?)`; const number = `(?:${d}{3}|${d}{2}-${d}{2})`; const person = '(?:[][]|[]) (?:|||||)'; // , , (,  , )?  const re = new RegExp(`^(${name}),\\s*(${name}),\\s*(?:(${name}),\\s*(${number}),\\s*)?(${person})$`); module.exports = function(str) { //      if (typeof str !== 'string') return null; const res = str.match(re); //   -   if (!res) return null; //    //    ,     return res.slice(1); }; 

कार्य 2. वह कोड जिसमें कोई त्रुटि हो

शर्त

दिन के दौरान, विकास टीम ने कई नई सुविधाएँ बनाईं। लेकिन रिलीज की तैयारी में, मर्ज संघर्ष हुआ, और उनके हल होने के बाद, लेआउट ने भाग लिया। कोड में न्यूनतम संख्या में सुधार के कारण त्रुटियों से छुटकारा पाना तत्काल आवश्यक है ताकि उत्पादन में आने का समय निकल जाए।

आपको टूटी हुई शैलियों और एक PNG प्रारूप (अपेक्षित परिणाम के साथ) के साथ एक HTML पृष्ठ प्रदान किया जाता है। आपको त्रुटियों को ठीक करने की आवश्यकता है ताकि क्रोम में देखने पर परिणाम मूल स्क्रीनशॉट के समान हो जाए। समस्या के समाधान के रूप में सही पृष्ठ भेजें।

HTML पेज टूटी हुई शैलियों के साथ। लेआउट:

पदच्छेद

इस कार्य में, हमने उस स्थिति की नकल करने की कोशिश की, जो यांडेक्स डेवलपर्स नियमित रूप से मुठभेड़ करते हैं: विशाल कोड आधार में, कोड की बहुत कम सरल रेखाएं ढूंढते हैं, जिनमें से सुधार वांछित परिणाम की ओर जाता है। यही है, कठिनाई कोड लिखने में नहीं थी, लेकिन यह समझने में कि वास्तव में इसे कहां लिखना है (या इसे हटा दें)।

हमने वास्तविक खोज इंजन कोड लिया और लेआउट को तोड़ने वाले कुछ सुधार किए। प्रतियोगिता के प्रतिभागियों को लगभग 250 किलोबाइट लेआउट से निपटने और लेआउट के अनुरूप राज्य में कोड लाने के लिए एक घंटे से भी कम समय था।

यह स्पष्ट है कि प्रतियोगिता के लिए समय सीमा ने पूरे कोड को पढ़ने की अनुमति नहीं दी, इसलिए प्रतिभागियों को ब्राउज़र में डेवलपर्स के लिए टूल का उपयोग करना चाहिए।

चार कार्य विकल्पों में से एक को ठीक करने के लिए, निम्नलिखित परिवर्तन पर्याप्त थे:

  diff --it / a / blitz.html b / blitz.html 

  सूचकांक 36b9af8..1e30545 100644 

  --- a / blitz.html 

  +++ b / blitz.html 

  @@ -531.10 +531.6 @@ 

  iframe [src $ = 'ext-analytics.html'] { 

  ऊंचाई: ऑटो; 

  } 

  -search2__button .suggest2-form__button: nth-child (1) { 

  - पृष्ठभूमि: # ff0; महत्वपूर्ण; 

  -} 

  - 

  / * ../../blocks-desktop/input/__control/input__control.styl end * / 

  / * ../../ode_modules/islands/common.blocks/input/__clear/input__clear.css शुरू * / 

  / * Input__box के सापेक्ष स्थिति। 

  @@ -744.10 +740.6 @@ 

  iframe [src $ = 'ext-analytics.html'] { 

  पृष्ठभूमि-क्लिप: पैडिंग-बॉक्स; 

  } 

  .input_theme_websearch .input__clear { 

  पृष्ठभूमि-छवि: url ("/ static / web4 / node_modules / Islands / common.blocks / input / _theme / input_theme_websearch.assets / clear.svg"); 

  पृष्ठभूमि का आकार: 16 पीएक्स; 

  @@ -857.6 +849.7 @@ 

  iframe [src $ = 'ext-analytics.html'] { 

  पृष्ठभूमि-रंग: # f2cf46; 

  } 

  .websearch-button__text: इससे पहले { 

  + स्थिति: निरपेक्ष; 

  शीर्ष: -6 पीएक्स; 

  दाईं ओर: -9 पीएक्स; 

  चौड़ाई: 0; 

  @@ -866.8 +859.6 @@ 

  iframe [src $ = 'ext-analytics.html'] { 

  सीमा-शैली: ठोस; 

  सीमा-रंग: rgba (255,219,76,0); 

  सीमा-वाम-रंग: विरासत; 

  - स्थिति: रिश्तेदार; 

  - जेड-इंडेक्स: -1000; 

  } 

  / * ../../blocks-deskpad/websearch-button/websearch-button.styl अंत * / 

  @@ -1349.6 +1340.7 @@ 

  iframe [src $ = 'ext-analytics.html'] { 

  फ़ॉन्ट-आकार: 14 पीएक्स; 

  लाइन-ऊँचाई: 40 पीएक्स; 

  स्थिति: रिश्तेदार; 

  + प्रदर्शन: इनलाइन-ब्लॉक; 

  ऊंचाई: ऑटो; 

  गद्दी: 0; 

  ऊर्ध्वाधर-संरेखित करें: मध्य; 

कार्य 3. दी गई परिवर्तनशीलता के साथ एक तस्वीर

शर्त

डिज़ाइनर ने लोगो डिज़ाइन किया। इसे विभिन्न स्थितियों में उपयोग करने की आवश्यकता होगी। इसे यथासंभव सुविधाजनक बनाने के लिए, इसे शुद्ध सीएसएस में एक एचटीएमएल तत्व के साथ बनाएं।

आप चित्रों का उपयोग नहीं कर सकते हैं (यहां तक ​​कि डेटा के माध्यम से: uri)।

पदच्छेद

चूँकि कार्य केवल एक div का उपयोग करना था, हमारे पास केवल div और छद्म तत्व हैं :: पहले और बाद में।

सौभाग्य से, विभिन्न रंगों के सिर्फ तीन क्षेत्रों में लेआउट पर चित्र शामिल हैं। हम प्रत्येक सुलभ तत्व, सही ढंग से स्थिति और गोल कोनों के लिए अपनी पृष्ठभूमि बनाते हैं। लेआउट के ग्रे क्षेत्र पर एक छाया है - हम इसे एक ढाल के साथ बनाते हैं।

 div { background: #0C0C0C; border-radius: 10px; position: relative; } div:before { border-radius: 9px 9px 0 0; position: absolute; width: 100%; height: 50%; background: #F8E34B; content: ''; } div:after { content: ''; background: linear-gradient(178deg, #C8C8C8 0px , transparent 7px), #EEEDEF; position: absolute; width: 50%; height: 50%; bottom: 0; border-radius: 0 0 0 9px; } 

टास्क 4

शर्त

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

पेटी को प्रत्येक हेडिंग के लिए अपना स्वयं का फॉन्ट साइज चुनने की जरूरत है ताकि फॉन्ट का साइज अधिकतम हो, लेकिन उसी समय सभी हेडिंग टेक्स्ट उसके लिए आवंटित स्पेस में फिट हो जाते हैं।

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

हम यह जांचेंगे कि आपका समाधान कितनी अच्छी तरह काम करता है और यदि यह बहुत अधिक डोम हेरफेर करता है तो यह ठीक है।

पदच्छेद

पहली बात यह है कि यह निर्धारित करना सीखें कि पाठ कंटेनर में फिट बैठता है या नहीं, यह देखते हुए कि कंटेनर में पाठ कई लाइनें ले सकता है। ऐसा करने का सबसे आसान तरीका है तत्व का उपयोग करना ।getBoundingClientRect () फ़ंक्शन, जो आपको तत्व के आयाम प्राप्त करने की अनुमति देता है।

आप कंटेनर के अंदर एक अलग स्पैन तत्व के साथ पाठ आकर्षित कर सकते हैं और जांच सकते हैं कि इस तत्व की चौड़ाई या ऊंचाई कंटेनर के आकार से अधिक है या नहीं। यदि हाँ, तो पाठ कंटेनर में फिट नहीं होता है।

अगला, सीमा की स्थिति की जाँच करें। यदि पाठ न्यूनतम फ़ॉन्ट आकार के साथ भी कंटेनर में फिट नहीं होता है, तो इसे दर्ज नहीं किया जा सकता है। यदि पाठ अधिकतम अनुमत आकार के साथ टूटता है, तो अधिकतम सही उत्तर होगा। अन्य मामलों में, वांछित फ़ॉन्ट आकार अंतराल [न्यूनतम, अधिकतम] में कहीं है।

समाधान खोजने के लिए, आपको इस पूरे अंतर को छाँटने की जरूरत है और फ़ॉन्ट-आकार का मान ढूंढना चाहिए जिस पर पाठ कंटेनर में रखा गया है, लेकिन यदि आप इसे 1 से बढ़ाते हैं, तो यह फिट होने के लिए बंद हो जाएगा।

आप रेंज [मिनट, अधिकतम] पर लूप के लिए एक सरल के साथ ऐसा कर सकते हैं, लेकिन समाधान पेज की बहुत सारी जांच और रीड्रा करेगा - रेंज में चेक किए गए प्रत्येक मान के लिए कम से कम एक। इस तरह के समाधान की एल्गोरिथम जटिलता रैखिक होगी।

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

हमने MutationObserver का उपयोग करके समाधान की एल्गोरिथम जटिलता की जांच की: हमने इसे पृष्ठ पर रखा और गणना की कि उत्तर खोजने की प्रक्रिया में DOM कितने निर्णय लेता है, इसकी गणना की। कुछ परीक्षणों के लिए, उत्परिवर्तन की संख्या ऊपर से सख्ती से सीमित थी ताकि केवल द्विआधारी खोज पर आधारित एक समाधान इस प्रतिबंध को पारित कर सके।

कार्य के लिए पूर्ण स्कोर प्राप्त करने के लिए, अलग-अलग सीमा स्थितियों (मिलान मिनट और अधिकतम, इनपुट पर पाठ की एक खाली रेखा) की सावधानीपूर्वक जांच करना और कई पर्यावरणीय परिस्थितियां प्रदान करना आवश्यक था जिसमें कोड चलाया जाता है (उदाहरण के लिए, सीएसएस पृष्ठ में महत्वपूर्ण फ़ॉन्ट-आकार! )।

कार्य 5. संचार में कठिनाइयाँ

प्रत्येक योग्यता विकल्प में, एक कार्य था जहां कुछ इंटरफ़ेस के साथ एक HTML पृष्ठ इनपुट के रूप में पेश किया गया था। कार्यों में एक अलग किंवदंती थी, लेकिन वे सभी इस तथ्य से उबरे थे कि पृष्ठ से कुछ डेटा निकालना आवश्यक था और इस डेटा का उपयोग करते हुए, किसी तरह इंटरफ़ेस के साथ बातचीत करें।

आइए हम इस श्रृंखला के कार्यों में से एक के समाधान का विश्लेषण करें, जिसे "संचार में कठिनाइयाँ" कहा जाता था।

शर्त

घोड़े एडॉल्फ को फोन पर दोस्तों के साथ बात करना पसंद है। दुर्भाग्य से, यह दुर्लभ है। हर बार जब एडॉल्फ कॉल करना चाहता है, तो उसे एक दोस्त की संख्या डायल करने में एक घंटे से अधिक समय लगता है। इसका कारण यह है कि उसके लिए अपनी मोटी खुरों के साथ सही चाबियाँ हिट करना बहुत मुश्किल है।

सौभाग्य से, एडॉल्फ का फोन जावास्क्रिप्ट का समर्थन करता है। कृपया एक कार्यक्रम लिखें जो कीबोर्ड पर क्लिक करके एडोल्फ के दोस्तों को डायल करता है। सभी आवश्यक नंबर एक नोटबुक में दर्ज किए गए हैं। दुर्भाग्यशाली घोड़ा आपका बहुत आभारी होगा!

पदच्छेद

यहाँ वह पृष्ठ है जो इनपुट के रूप में पेश किया गया था:



समाधान का पहला भाग डेटा पुनर्प्राप्त कर रहा है
फोन नंबर के प्रत्येक अंक को एक चित्र द्वारा पृष्ठभूमि-छवि के माध्यम से सेट किया जाता है। उसी समय, सत्यापन के दौरान, संख्याओं को गतिशील रूप से प्रतिस्थापित किया जाता है। यदि आप किसी ब्राउज़र में डीबगर को खोलते हैं और पृष्ठ के DOM ट्री को देखते हैं, तो आप देखेंगे कि प्रत्येक DOM तत्व स्पष्ट कक्षाओं का उपयोग करता है:

 <div class="game"> <div class="target"> <div class="line"> <div class="symbol nine"></div> <div class="symbol eight"></div> <div class="symbol five"></div> <div class="symbol separator"></div> <div class="symbol four"></div> <div class="symbol one"></div> <div class="symbol two"></div> <div class="symbol separator"></div> </div> <!-- ... --> </div> <!-- ... --> </div> 

इस मामले में, यह केवल एक शब्दकोश बनाने, सीएसएस कक्षाओं को निकालने और उन्हें अलग-अलग (सीएसएस वर्ग विभाजक) को छोड़कर, शब्दकोश के अनुसार एक संख्या के साथ एक स्ट्रिंग में परिवर्तित करने के लिए पर्याप्त था। उदाहरण के लिए, इस तरह:

 const digits = document.querySelectorAll('.game .target .symbol:not(.separator)'); const dict = { 'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'eight': 8, 'nine': 9, 'zero': 0, }; const phoneNumber = Array.from(digits).reduce((res, elem) => { for (const className of elem.classList) { if (className in dict) { res.push(dict[className]); break; } } return res; }, []); 

नतीजतन, हमें निम्नलिखित सरणी मिलती है: [9, 8, 5, 4, 1, 2, 8, 0, 9, 0]।

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

 <div class="keys"> <div class="key"></div> <div class="key"></div> <!-- … --> </div> 

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

 .key:nth-child(3):before { content: '3'; } 

इस संपत्ति का मूल्य पाने के लिए, हम window.getComputedStyle विधि का उपयोग करते हैं:

 const keys = Array.from(document.querySelectorAll('.game .key')).reduce((res, elem) => { const key = window //  CSSStyleDeclaration  - .getComputedStyle(elem, ':before') //    .getPropertyValue('content') //     ,      .replace(/"/g, ''); res[key] = elem; return res; }, {}); 

नतीजतन, हमें एक वस्तु मिलती है जहां प्रमुख ग्रंथ बटन (संख्या या "कॉल") पर ग्रंथ होंगे, और मान डोम नोड होंगे।

यह केवल पहले सरणी (फोननंबर) से मान लेने के लिए बनी हुई है, उनके माध्यम से जाएं और हमारे कुंजीशब्द शब्दकोश का उपयोग करके संबंधित बटन पर क्लिक करें:

 phoneNumber.push('call'); const call = () => { const event = new Event('click'); const next = phoneNumber.shift(); keys[next].dispatchEvent(event); if (phoneNumber.length) { setTimeout(call, 100); } } call(); 

कृपया ध्यान दें: डायल करने से पहले, हम सरणी के अंत में एक कॉल वैल्यू जोड़ते हैं। यह कार्य की शर्तों द्वारा आवश्यक है, क्योंकि यदि आप नंबर डायल करते हैं और "कॉल" नहीं दबाते हैं, तो समाधान परीक्षण पास नहीं करेगा।

एक अन्य विशेषता कीबोर्ड बटन के अतुल्यकालिक दबाव है। यदि डायल करते समय कीस्ट्रोक्स के बीच का समय अंतराल 50 एमएस से कम है, तो यह समाधान भी परीक्षा पास नहीं करेगा। इस सुविधा को समस्या की स्थितियों में स्पष्ट रूप से वर्णित नहीं किया गया था, और हमने पृष्ठ के स्रोत कोड को पढ़कर प्रतिभागी का पता लगाने की अपेक्षा की। वैसे, स्रोत कोड में प्रतिभागियों को थोड़ा आश्चर्य हुआ। ;)

टास्क 6

शर्त

Fedor Rakushkin अपनी कंपनी में कार्य प्रबंधन प्रणाली का संचालन करता है। जिस सर्वर पर सिस्टम स्थित है वह विफल हो गया है (और फेडर ने बैकअप नहीं किया है)।

सर्वर की मेमोरी में, कार्यों, निष्पादकों और पर्यवेक्षकों के साथ-साथ इन संरचनाओं के बीच संबंधों का वर्णन करने वाली संरचनाओं का एक कैश बना रहा। इसके अलावा, अंतिम संरचना के कैश लिंक को संरक्षित किया गया था।

फ़ेडर एक फ़ंक्शन लिखने में मदद करता है जो कार्यों और उपयोगकर्ताओं के बीच सभी संभावित कनेक्शन को पुनर्स्थापित कर सकता है और उन्हें मार्कडाउन प्रारूप में एक दस्तावेज़ में सहेज सकता है, जिससे फ़ेडोर फिर डेटाबेस को एक नए सर्वर पर पुनर्स्थापित करेगा।

मार्कडाउन दस्तावेज में निम्नलिखित प्रारूप होना चाहिए:

 ##  - %  1%,  %username1%, : %username2% - %  2%,  %username1%, : %username2%, %username3% - %  3%,  %username1% //     - %  4%, : %username1%, %username2% //     - %  5% //       - %  6%, : %username1% - %  1%,  %username1% //  - %  2% - %  3%, : %username1% ##  - %username1% * %  1% // ,    * %  2% * %  3% * %  1% - %username2% * %  3% 

कार्यों की सूची, कार्य में निष्पादकों की सूची, कार्य में पर्यवेक्षकों की सूची, उपयोगकर्ताओं की सूची और कार्यों की सूची जो उपयोगकर्ता को क्रमबद्ध रूप से क्रमबद्ध करनी चाहिए।

कैश में संरचनाओं का विवरण

उपयोगकर्ताओं को कैश में स्टोर किया जाता है टाइप `उपयोगकर्ता` की संरचना के रूप में:

 type User = { login: string; tasks: Task[]; spectating: Task[]; }; 

टास्क को कैश में स्टोर किया जाता है।

 type Task = { title: string; assignee: User; spectators: User[]; subtasks: Task[]; parent: Task | null; }; 

समाधान टेम्पलेट

आपके समाधान में कॉमनजस मॉड्यूल होना चाहिए जो निम्न हस्ताक्षर के अनुरूप फ़ंक्शन का निर्यात करता है:

 /** * @param {User|Task} data -     , *        (User  Task) * @return {string} */ module.exports = function (data) { //   return '…'; } 

उदाहरण

 //    const User1 = { type: 'user', login: 'fedor', tasks: [], spectating: [] }; const User2 = { type: 'user', login: 'arkady', tasks: [], spectating: [] }; //    const Task1 = { type: 'task', title: 'Do something', assignee: null, spectators: [], subtasks: [], parent: null }; const Task2 = { type: 'task', title: 'Something else', assignee: null, spectators: [], subtasks: [], parent: null }; const Task3 = { type: 'task', title: 'Sub task', assignee: null, spectators: [], subtasks: [], parent: null }; //    : //      Task1.assignee = User1; User1.tasks.push(Task1); // ...    —  Task1.spectators.push(User2); User2.spectating.push(Task1); //      , //       Task2.spectators.push(User1); User1.spectating.push(Task2); //      Task3.parent = Task2; Task2.subtasks.push(Task3); // ,     —  3 const lastEdited = Task3; 

यदि आप `lastEdited` का लिंक प्रदर्शित करते हैं, तो आपको निम्न संरचना मिलेगी:

 { type: 'task', title: 'Sub task', assignee: null, spectators: [], subtasks: [], parent: { type: 'task', title: 'Something else', assignee: null, spectators: [ { type: 'user', login: 'fedor', tasks: [ { type: 'task', title: 'Do something', assignee: [Circular], spectators: [ { type: 'user', login: 'arkady', tasks: [], spectating: [ [Circular] ] } ], subtasks: [], parent: null } ], spectating: [ [Circular] ] } ], subtasks: [ [Circular] ], parent: null } } 

Markdown , :

 ##  - Do something,  fedor, : arkady - Something else, : fedor - Sub task ##  - arkady - fedor * Do something 

, .

, , . , :

 /** *  ,     * @param {{ref: object, visited: ?boolean}} ctx * @param {object} handlers —     */ function traverse(ctx, handlers) { //    ,  ctx.ref , — ,     task.parent if (!ctx.ref) { return; } //   ,    ,       const visited = ctx.visited || new Set(); if (visited.has(ctx.ref)) { return; } visited.add(ctx.ref); //       handlers[ctx.ref.type](ctx.ref, goDeeper); //  ,       function goDeeper(subrefs) { //       for (const subref of [].concat(subrefs)) { traverse({ visited, ref: subref }, handlers); } } } //      const users = []; const tasks = []; // ref   —     traverse({ ref }, { user(user, deeper) { users.push(user); deeper(user.tasks); // to task.assignee deeper(user.spectating); // to task.spectators }, task(task, deeper) { tasks.push(task); deeper(task.assignee); // to user.tasks deeper(task.spectators); // to user.spectating deeper(task.parent); // to task.subtasks deeper(task.subtasks); // to task.parent } ); 

. , , …

 users.sort((u1, u2) => u1.login < u2.login ? -1 : (u1.login > u2.login ? 1 : 0)); tasks.sort((t1, t2) => t1.title < t2.title ? -1 : (t1.title > t2.title ? 1 : 0)); 

… — :

 //    const taskLine = t => `${ t.title }${ t.assignee ? `,  ${t.assignee.login}` : '' }${ t.spectators.length ? `, : ${t.spectators.map(u => u.login).join(', ')}` : '' }`; function renderTasks (parent = null, indent = 0) { return tasks .filter(t => t.parent === parent) .map(t => [ '\n', ' '.repeat(indent), //  '- ', taskLine(t), //    t.subtasks.length ? printTasks(t, indent + 2) : '' //   ].join('')) .join(''); } function renderUsers () { return ${users.map(u => `\n- ${u.login}${ u.tasks.map(t => `\n * ${t.title}`).join('') }`).join('')} } const result = ` ##  ${renderTasks()} ##  ${renderUsers()} `.trim(); 

7.

, .. :



, . , «».



.



, . , . . . HTML CSS. JavaScript .

, , - . , .

HTML/CSS, , , - .

CSS, , — float, . float , , .

— , . ( jsfiddle.net .)

— padding-top, margin-top ( ). DOM- (). ( .)

8.

HTML-. , . , . .

(pixel perfect). .

. .

, , . , . , : - , , .

, . , , .

, — . — CSS- border ( ), background ( ) box-shadow ( ).

- « » ( ) . , , .

— , 70 70 . : , . CSS- , CSS- , .



— 210 210 , 70 70 .

9.

— , -. JavaScript, . , .

: . , , . .

, — . — . , JavaScript API . , -, , . 10 , HTTP- .

— . , , , .

-.

:
— API npm- @yandex-blitz/phone.
— API .
— -, : task.js .
— - runkit- .

-, .

— GET- return connect.

: - . , , . .

, : , . :

 const writeQueue = []; const processQueue = () => { if (writeQueue.length) { const fn = writeQueue.shift(); fn().then(() => { processQueue(); }); } } 

, « ».

 const writeQueue = []; let isWriteInProgress = false; const processQueue = () => { if (isWriteInProgress) { return; } if (writeQueue.length) { isWriteInProgress = true; const fn = writeQueue.shift(); fn().then(() => { isWriteInProgress = false; processQueue(); }); } } 

, POST- . , , .

 app.post("/speeddial/:digit/:phonenumber", (req, res) => { writeQueue.push(makeWriteJob(phone, req, res)); processQueue(); }); 

:

 const express = require('express'); const { BEEP_CODES } = require('@yandex-blitz/phone'); const writeQueue = []; let isWriteInProgress = false; const processQueue = () => { if (isWriteInProgress) { return; } if (writeQueue.length) { isWriteInProgress = true; const fn = writeQueue.shift(); fn().then(() => { isWriteInProgress = false; processQueue(); }); } } const makeWriteJob = (phone, req, res) => { return () => { return phone.getData() .then(value => { const speeddialDict = JSON.parse(value); speeddialDict[req.params.digit] = Number(req.params.phonenumber); return phone .setData(JSON.stringify(speeddialDict)) .then(() => phone.beep(BEEP_CODES.SUCCESS)) .then(() => { res.sendStatus(200); }) }) .catch(e => { phone.beep(BEEP_CODES.ERROR).then(() => { res.sendStatus(500); }) }) } }; const createApp = ({ phone }) => { const app = express(); //   ,   « »   digit app.get("/speeddial/:digit", (req, res) => { phone.getData().then(value => { const speeddialDict = JSON.parse(value); return phone.connect() .then(async () => { await phone.dial(speeddialDict[req.params.digit]); res.sendStatus(200); }, async() => { await phone.beep(BEEP_CODES.FATAL); res.sendStatus(500); }); }).catch(async (e) => { await phone.beep(BEEP_CODES.ERROR); res.sendStatus(500); }); }); //   « »   digit  phonenumber app.post("/speeddial/:digit/:phonenumber", (req, res) => { writeQueue.push(makeWriteJob(phone, req, res)); processQueue(); }); return app; }; exports.createApp = createApp; 

10.

. , «».

:
— , .
— , , .
— , , .
— , : ← ↓ ↑ →.
— — , .

, , , , .

.

.

HTML- ( ).

, window.onMazeReady(). . 2 , .

CSS- map.

click CSS-:
— — control_direction_left,
— — control_direction_down,
— — control_direction_up,
— — control_direction_right.

CSS- :

 background: radial-gradient(circle at 5px 5px, #eee, #000); 

25 , 500 . उदाहरण के लिए:









window.map String. :
# —
। —
o —
x —

, , , — . .

,

 window.map = ` ##### #o#x# #.#.# #...# ##### `; 

:



:

 <!DOCTYPE html> <html lang=ru/> <head> <style> body { padding: 100px 0 0 100px; } .game-box { perspective: 500px; perspective-origin: center; } .map { transform-style: preserve-3d; } .map__tilt_left { transform: rotateY(-25deg); } .map__tilt_down { transform: rotateX(-25deg); } .map__tilt_up { transform: rotateX(25deg); } .map__tilt_right { transform: rotateY(25deg); } </style> <title></title> </head> <body> <div class="game-box"> <div class="map"> <!--  --> </div> </div> <script> // JavaScript </script> </body> </html> 

(HTML, CSS, JS). , «» .

. ( ), , .

, , .

, :

 <table class="map map__tilt_none"> <!-- ... --> <tr> <td class="map__cell map__cell_content_wall"></td> <td class="map__cell map__cell_content_empty"></td> <td class="map__cell map__cell_content_ball"></td> <td class="map__cell map__cell_content_exit"></td> <td class="map__cell map__cell_content_wall"></td> </tr> <!-- ... --> </table> 

:

 .map { border: 0; border-spacing: 0; border-collapse: separate; background-color: #ccc; transform-style: preserve-3d; } .map__cell { box-sizing: border-box; border: 1px solid; border-color: #9b9b9b #575757 #575757 #9b9b9b; width: 30px; height: 30px; text-align: center; vertical-align: middle; font-size: 0; line-height: 0; background-color: #707070; } .map__cell_content_ball:after { content: ''; display: inline-block; width: 20px; height: 20px; border-radius: 50%; background: radial-gradient(circle at 5px 5px, #eee, #000); } .map__cell_content_wall { border-width: 4px; } .map__cell_content_exit { background-color: #000; border: 5px solid; border-color: #222 #555 #555 #222; } 

— — .

, .

«» , . , . , :

 window.map = ` ####### ##.#### #..o..# ##x.#.# ###...# ####### `; 

:

 function convertMap(mapInput) { return mapInput .trim() .split(/\n\s*/) .map(row => row.split('')); } 

, HTML :

 const CELL_CONTENT = { '#': 'wall', 'o': 'ball', '.': 'empty', 'x': 'exit' }; function buildGameBoxHtml(map) { return ` <div class="game-box"> <table class="map map__tilt_none"> ${map.map(row => ` <tr> ${row.map(cell => ` <td class="map__cell map__cell_content_${CELL_CONTENT[cell]}"></td> `).join('')} </tr> `).join('')} </table> <!--      --> <div class="controls"> <button class="control control_direction_left">←</button> <button class="control control_direction_down">↓</button> <button class="control control_direction_up">↑</button> <button class="control control_direction_right">→</button> </div> </div> `; } 

, :

 let gameBox = document.querySelector('.game-box'); let map = gameBox.querySelector('.map'); //           gameBox.addEventListener('click', ({ target }) => { //      if (!target.classList.contains('control')) { return; }; //      - const direction = target.className.match(/\bcontrol_direction_(\w+)/)[1]; //  ,   - map.className = map.className.replace(/\bmap__tilt_\w+/, `map__tilt_${direction}`); //  ,     let ball = map.querySelector('.map__cell_content_ball'); //       let nextBall = getNextCell(map, ball, direction); //      ball.classList.remove('map__cell_content_ball'); ball.classList.add('map__cell_content_empty'); //     ,            while ( !nextBall.classList.contains('map__cell_content_wall') && !ball.classList.contains('map__cell_content_exit') ) { ball = nextBall; nextBall = getNextCell(map, ball, direction); } //      ball.classList.remove('map__cell_content_empty'); ball.classList.add('map__cell_content_ball'); }); const DIRECTIONS = { 'left': [-1, 0], 'up': [0, -1], 'down': [0, 1], 'right': [1, 0] }; //  DOM API ,        function getNextCell(map, cell, direction) { const directionDiff = DIRECTIONS[direction]; return map.rows[cell.parentNode.rowIndex + directionDiff[1]].cells[cell.cellIndex + directionDiff[0]]; } 

— callback : window.onMazeReady(). .

, . , , . HTML, CSS JS — , .

, :
— ,
— , ,
— , ,
— , ,
— , ,
— , .

, :
— ,
— ,
— DOM API ,
— .

11.

, , . , . , .

, . , . . .js, :

 module.exports = function solveCaptcha(captcha) { // ... } 

. .
:

 captcha = ' TRABWARH THSCAHAW WWBSCWAA CACACHCR ' 

:
— S — (sign)
— T — (tree)
— R — (road)
—…

:

 [ 'TRABWARH THSCAHAW' , 'WWBSCWAA CACACHCR' ] 

:
— 1 10.
— .
— , .
— ( ).
— , , .
— , .

Cut the cake codewars.com.

, 10. , . , . :
— ;
— , .

, . : «… , ». . .



. . , . .

. «», .

 module.exports = function solveCaptcha(captcha) { const n = //     const sizes = getAllSizes(); //      // board —    //   —   ,   //  ,    const board = []; //    function placeNext(remains) { //    ... if (remains === 0) { // ... ,   ,   return board; } else { // ... //         // ,     const pos = getEmptyPos(); //        for (let i = 0; i < sizes.length; i++) { //  ,    const size = sizes[i]; //          //     (      //     !== 1),  null const layer = getLayer(pos, size); //     if (layer) { //     board.push(layer); //     const res = placeNext(remains - 1); //  ,  if (res) return res; //      //    board.pop(); } } } } //   return placeNext(n); } 

12. -

X . VCS , .

, -. — , .

, . , , . .

, . ( ) .

.



. — 1000, - — 20.

:

 type PullRequest = { /** *     ( ) *   N: 1 <= N <= 1000 */ files: string[], /** *     VCS */ id: string, /** * Unix-timestamp  - */ created: number, } 

(created) (id) – .



CommonJS- :

 /** * @param {PullRequest[]} pullRequests  PR,     * @returns {string[]}      */ module.exports = function (pullRequests) { //   } 

NodeJS v9.11.2. .

 function mergeAllPRs(prs) { /* solution */ } console.assert( mergeAllPRs([ { id: '#1', created: 1536077100, files: ['.gitignore', 'README.md'] }, { id: '#2', created: 1536077700, files: ['index.js', 'package-lock.json', 'package.json'] }, { id: '#3', created: 1536077800, files: ['.pnp.js', 'yarn.lock'] } ]) .join(',') === [ "#1", "#2", "#3" ].join(',') ); console.assert( mergeAllPRs([ { id: '#1', created: 1536074100, files: ['README.md'] }, { id: '#2', created: 1536078700, files: ['README.md'] }, { id: '#3', created: 1536097800, files: ['README.md'] } ]).join(',') === [ "#1" ].join(',') ); console.assert( mergeAllPRs([ { id: '#1', created: 1536077100, files: ['.gitignore', 'README.md'] }, { id: '#2', created: 1536077700, files: ['index.js', 'package-lock.json', 'package.json'] }, { id: '#3', created: 1536077800, files: ['.pnp.js', 'package-lock.json', 'yarn.lock'] }, { id: '#4', created: 1536077900, files: ['index.spec.js', 'index.spec.ts', 'index.ts'] } ]) .join(',') === [ "#1", "#2", "#4" ].join(',') ); 

— , .

, « » (, ).

, , , . ( some includes). — O(n ² ).

, , ( . ). — O(n).

:

 function conflicts(a, b) {  let i = 0;  let j = 0;  while (i < a.length && j < b.length) {      if (a[i] === b[j]) {          return true;      } else if (a[i] > b[j]) {          j++;      } else {          i++;      }  }  return false; } function mergeAllPrs (input) {  let i = 0;  const mergedFiles = [];  const mergedPrs = [];  while (i < input.length) {      const pr = input[i];      if (!conflicts(mergedFiles, pr.files)) {          mergedPrs.push(pr);          mergedFiles.push(...pr.files);      }      i++;  }  return mergedPrs.map(x => x.id); }; 

, , . , :

 console.assert(  mergeAllPrs([      {          "id": "1",          "created": 1538179200,          "files": [ "a", "b", "c", "d" ]      },      {          "id": "2",          "created": 1538189200,          "files": [ "a", "x" ]      },      {          "id": "3",          "created": 1538199200,          "files": [ "b", "g" ]      },      {          "id": "4",          "created": 1538209200,          "files": [ "c",  "f" ]      },      {          "id": "5",          "created": 1538219200,          "files": [ "d", "w" ]      }  ])  .join(',') === ['2', '3', '4', '5'].join(',') ); 

, ( , ).

: «» -, «» — ( ). ( ).

:

 [  {      "id": "#1",      "created": 1536077100,      "files": [ ".gitignore", "README.md" ]  },  {      "id": "#2",      "created": 1536077700,      "files": [ "index.js", "package-lock.json", "package.json" ]  },  {      "id": "#3",      "created": 1536077800,      "files": [ "index.js" ]  } ] 

#2 #3 , ["#1", "#2"]. .



, .

, — O(n ² ), . .

, , . , , .

conflicts , . :

 const conflictMatrix = new Uint8Array(prs.length ** 2); const prToIndex = new WeakMap(); for (let i = 0; i < prs.length; i++) {  const pr1 = prs[i];  prToIndex.set(pr1, i);  conflictMatrix[i * prs.length + i] = 0;  for (let j = i + 1; j < prs.length; j++) {      const pr2 = prs[j];      conflictMatrix[i * prs.length + j] = conflictMatrix[j * prs.length + i] = conflicts(pr1.files, pr2.files);  } } /** *     PR (    ) */ function doPRsConflict(pr1, pr2) {  const i = prToIndex.get(pr1);  const j = prToIndex.get(pr2);  return conflictMatrix[i * prs.length + j] === 1; } 

«» , . ( ) , . , , - .

, , .

 /** *     prsSet,           */ function getNonConflictingPRs (prsSet, mergedPrs) {  const result = [];  const prsToTest = [...prsSet, ...mergedPrs];  prsSet.forEach((pr) => {      if (!conflictsWithSomePR(pr, prsToTest)) {          result.push(pr);      }  });  return result; } 

.

 const fullSearch = (prsSet, mergedPrs = [], mergedFilesCount = 0) => {  hits++;  //  ,            //   ,      const safeToMergePRs = getNonConflictingPRs(prsSet, mergedPrs);  mergedPrs = mergedPrs.concat(safeToMergePRs);  safeToMergePRs.forEach((pr) => {      prsSet.delete(pr);      mergedFilesCount += pr.files.length;  });  const pr = prsSet.values().next().value; // ...      

.