الواجهة الأمامية والخوارزميات ووفيروم فريدريك. نقوم بتحليل مهام مسابقة ياندكس

مع هذا المنشور ، نكمل سلسلة من المنشورات حول مسابقات Yandex.Blitz في 2018. نأمل أن تكون قد أتيحت لك الفرصة للمشاركة أو على الأقل رؤية نوع المهام التي نقترحها قريبة من الإنتاج. تم تخصيص المسابقة الأخيرة لاستخدام الخوارزميات في الواجهة الأمامية. ننشر اليوم تحليلات تفصيلية لـ 12 مشكلة: تم اقتراح أول 6 منها في جولة التأهيل ، والمشكلات 7-12 في النهائي. حاولنا شرح كيف تشكلت الظروف ، وما هي المهارات التي نهتم بها. شكرا لجميع المشاركين على اهتمامهم!

المهمة 1

كانت المهمة الأولى هي الإحماء ، لمدة 20 دقيقة ، وقررنا جعل حالتها بحيث يتم حلها بسهولة باستخدام التعبيرات العادية.

يتم إنشاء جميع خيارات المهمة بطريقة مماثلة - هناك تقسيم إلى نقاط ، يمكن تمثيل كل منها من قبل المجموعة في التعبير العادي النهائي.

خذ بعين الاعتبار أحد الخيارات: مكتب البريد.

الشرط

على كوكب Jopan-14-53 ، يريد السكان المحليون إرسال رسائل إلى بعضهم البعض ، ولكن روبوتات الحمام التي يجب أن تسلمها مرتبكة في العناوين. يجب عليك تعليمهم تحليل الحروف والتحقق من صحتها.

يتكون هيكل الجزء الأساسي من العنوان من المنطقة والبلدية واسم ولقب المرسل إليه. يمكن تقسيم البلدية إلى مقاطعات ومكاتب بريد. يتم فصل جميع الأجزاء بفاصلة.

أسماء المناطق والبلديات والمقاطعات هي كلمات ، والحرف الأول في كل كلمة كبير والباقي صغير. الأسماء المكونة من كلمتين ممكنة ، مفصولة بمسافة أو علامة ناقص. في كل كلمة من ثلاثة إلى ثمانية أحرف من الألف إلى الياء.

السكان لديهم 6 أصابع في أيديهم ، في الحياة اليومية نظام الاثني عشر. تُستخدم الأرقام من 0 إلى 9 كما هي ، ويُشار إلى 10 و 11 بالعلامات ~ و ≈ .

يتكون رقم مكتب البريد في التكوين من 3 أرقام متتالية ، أو 4 مقسمة إلى مجموعتين من رقمين بعلامة ناقص. أمثلة: 300 ، 44-99 .

في بعض الأحيان يرسل المقيمون رسائل إلى البلدية عند الطلب. في هذه الحالة ، لا يوجد عنوان: فقط البلدية واسم المرسل إليه.

إنه أمر مضحك ، لكن الناس على هذا الكوكب يطلق عليهم ستة أسماء فقط وتسعة ألقاب. الأسماء: شوب ، ريوب ، موب ، شيانغ ، ريان ، مان. الألقاب: Sho ، Ryo ، Mo ، Xia ، Rya ، Ma ، Syu ، Ryu ، Mu. سكان هذا الكوكب ليسوا حالمين على الإطلاق.

التحليل

يتكون هيكل الجزء الأساسي من العنوان من المنطقة والبلدية واسم ولقب المرسل إليه. يمكن تقسيم البلدية إلى مقاطعات ومكاتب بريد. يتم فصل جميع الأجزاء بفاصلة.

من الفقرات الأولى نتعلم كيفية الإشارة إلى المنطقة والبلدية والمنطقة ومكتب البريد والاسم واللقب ، وبأي ترتيب يجب أن يتبعوا في الخط المختبر.

أسماء المناطق والبلديات والمقاطعات هي كلمات ، والحرف الأول في كل كلمة كبير والباقي صغير. الأسماء المكونة من كلمتين ممكنة ، مفصولة بمسافة أو علامة ناقص. في كل كلمة من ثلاثة إلى ثمانية أحرف من الألف إلى الياء.

من هذه الفقرة يتضح أن المجموعة تتوافق مع الكلمات ([-][-]{2,7}) . والأسماء ، على التوالي ، ([-][-]{2,7}(?:[- ][-][-]{2,7})) .

السكان لديهم 6 أصابع في أيديهم ، في الحياة اليومية نظام الاثني عشر. تُستخدم الأرقام من 0 إلى 9 كما هي ، ويُشار إلى 10 و 11 بالعلامات ~ و ≈ .

هنا نعلم أنه لا يكفي استخدام \d للأرقام - تحتاج إلى استخدام [0-9~≈] .

يتكون رقم مكتب البريد في التكوين من 3 أرقام متتالية ، أو 4 مقسمة إلى مجموعتين من رقمين بعلامة ناقص. أمثلة: 300 ، 44-99 .

وبالتالي ، تقابل المجموعة أرقام مكتب البريد ([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2}) .

في بعض الأحيان يرسل المقيمون رسائل إلى البلدية عند الطلب. في هذه الحالة ، لا يوجد عنوان: فقط البلدية واسم المرسل إليه.

نحن نتفهم ونتذكر ونأخذ في الاعتبار في تجميع الوظيفة النهائية أن المنطقة ومكتب البريد قد يكونا غائبين في نفس الوقت.

إنه أمر مضحك ، لكن الناس على هذا الكوكب يطلق عليهم ستة أسماء فقط وتسعة ألقاب. الأسماء: شوب ، ريوب ، موب ، شيانغ ، ريان ، مان. الألقاب: Sho ، Ryo ، Mo ، Xia ، Rya ، Ma ، Syu ، Ryu ، Mu. سكان هذا الكوكب ليسوا حالمين على الإطلاق.

هذا هو الجزء الأخير من الحالة. هنا كنا بحاجة إلى مجموعة بسيطة أخرى (||||||||) (|||||) أو نظيره الأقصر ([][]|[]) ([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); }; 

المهمة الثانية: الرمز الذي يوجد به خطأ

الشرط

خلال النهار ، قدم فريق التطوير العديد من الميزات الجديدة. ولكن أثناء إعداد الإصدار ، حدثت تعارضات الدمج ، وبعد حلها ، افترق التخطيط. من الضروري التخلص من الأخطاء بسبب الحد الأدنى من التصحيحات في التعليمات البرمجية بحيث يكون للإصدار وقت لبدء الإنتاج.

يتم تزويدك بصفحة HTML ذات أنماط مقطوعة وتنسيق PNG (بالنتيجة المتوقعة). تحتاج إلى إصلاح الأخطاء بحيث تصبح النتيجة عند العرض في Chrome هي نفس لقطة الشاشة الأصلية. أرسل الصفحة المصححة كحل للمشكلة.

صفحة HTML ذات أنماط مقطوعة. التخطيط:

التحليل

في هذه المهمة ، حاولنا تقليد الموقف الذي يواجهه مطورو Yandex بانتظام: في قاعدة الرموز الضخمة ، اعثر على الأسطر القليلة جدًا من التعليمات البرمجية ، والتي يؤدي تصحيحها إلى النتيجة المرجوة. أي أن الصعوبة لم تكن في كتابة الرمز ، ولكن في فهم مكان كتابته بالضبط (أو حذفه).

أخذنا كود محرك البحث الحقيقي وقمنا ببعض التصحيحات التي كسرت التصميم. كان لدى المشاركين في المسابقة أقل من ساعة للتعامل مع ما يقرب من 250 كيلوبايت من التخطيط وإحضار الرمز إلى الحالة المقابلة للتخطيط.

من الواضح أن المهلة الزمنية للمسابقة لم تسمح بقراءة الرمز بالكامل ، لذلك يجب على المشاركين استخدام الأدوات للمطورين في المتصفح.

لتصحيح أحد خيارات المهام الأربعة ، كانت التغييرات التالية كافية:

  diff --git a / blitz.html ب / 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 * / 

  / * ../../node_modules/islands/common.blocks/input/__clear/input__clear.css تبدأ * / 

  / * الموضع بالنسبة إلى الإدخال__box. 

  -744.10 +740.6 

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

  خلفية مقطع: padding-box؛ 

  }} 

  .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: قبل { 

  + موقف: مطلق. 

  أعلى: -6px ؛ 

  اليمين: -9px ؛ 

  العرض: 0 ؛ 

  -866.8 +859.6 

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

  نمط الحدود: صلب ؛ 

  لون الحدود: rgba (255،219،76،0) ؛ 

  لون الحد الأيسر: يرث ؛ 

  - الموقف: نسبي ؛ 

  - مؤشر z: -1000 ؛ 

  }} 

  / * ../../blocks-deskpad/websearch-button/websearch-button.styl end * / 

  -1349.6 +1340.7 

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

  حجم الخط: 14 بكسل ؛ 

  ارتفاع الخط: 40 بكسل ؛ 

  الموقف: قريب ؛ 

  + عرض: كتلة مضمنة ؛ 

  الارتفاع: السيارات ؛ 

  حشوة: 0 ؛ 

  محاذاة عمودية: وسط ؛ 

المهمة 3. صورة مع تغير معين

الشرط

صمم المصمم الشعار. ستحتاج إلى استخدامها في مجموعة متنوعة من الظروف. لجعله مناسبًا قدر الإمكان ، اختلقه باستخدام عنصر HTML واحد في CSS خالص.

لا يمكنك استخدام الصور (حتى من خلال البيانات: 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

الشرط

يعمل بيتيا كرائد كتابة في صحيفة Moscow Frontender. لتخطيط صحيفة Petya يستخدم مجموعة من تقنيات الويب. كانت أصعب مهمة واجهها بيتيا هي تخطيط العناوين في مقالات الصحف: أعمدة الصحف في كل عدد لها عرض مختلف ، والعناوين لها خطوط مختلفة وأرقام مختلفة من الشخصيات.

يحتاج بيتيا إلى اختيار حجم الخط الخاص به لكل عنوان بحيث يكون حجم الخط الأقصى ، ولكن في نفس الوقت كل نص العنوان يتناسب مع المساحة المخصصة له.

مساعدة Petya: تنفيذ وظيفة calcFontSize ، والتي ستسمح لك بإدخال النص المنقول في الحاوية بحيث تتناسب مع الحاوية بأكملها ولها أقصى حجم ممكن. إذا فشل هذا ، فيجب أن يعود الحل فارغًا. الحد الأقصى لطول خط الإدخال هو 100 حرف. لا يمكن أن تكون سلسلة الإدخال فارغة. يجب أن يحتوي الحل الخاص بك على رمز الوظيفة بالكامل ويجب ألا يستخدم التبعيات الخارجية حتى يتمكن بتيا من نسخه في مشروعه وتسميته في التعليمات البرمجية الخاصة به.

سوف نتحقق من كيفية عمل حلك على النحو الأمثل ونحسنه إذا أنتج الكثير من عمليات التلاعب في DOM.

التحليل

أول شيء يجب فعله هو معرفة كيفية تحديد ما إذا كان النص يناسب الحاوية ، نظرًا لأن النص الموجود في الحاوية يمكن أن يأخذ عدة أسطر. أسهل طريقة للقيام بذلك هي استخدام الوظيفة element.getBoundingClientRect () ، والتي تسمح لك بالحصول على أبعاد العنصر.

يمكنك رسم نص بعنصر امتداد منفصل داخل الحاوية والتحقق مما إذا كان عرض أو ارتفاع هذا العنصر يتجاوز حجم الحاوية. إذا كانت الإجابة بنعم ، فإن النص لا يتناسب مع الحاوية.

بعد ذلك ، تحقق من شروط الحدود. إذا كان النص لا يتناسب مع الحاوية حتى مع الحد الأدنى لحجم الخط ، فلا يمكن إدخاله. إذا انقطع النص بالحجم الأقصى المسموح به ، فسيكون الحد الأقصى هو الإجابة الصحيحة. في حالات أخرى ، يكون حجم الخط المطلوب في مكان ما في الفاصل الزمني [min، max].

لإيجاد حل ، تحتاج إلى فرز هذه الفجوة بأكملها والعثور على قيمة حجم الخط التي يتم وضع النص بها في الحاوية ، ولكن إذا قمت بزيادة حجمها بمقدار 1 –– فسوف تتوقف عن ملاءمتها.

يمكنك القيام بذلك بطريقة بسيطة للتكرار عبر النطاق [min ، max] ، ولكن الحل سيقوم بالكثير من عمليات الفحص وإعادة رسم الصفحة - واحدة على الأقل لكل قيمة يتم التحقق منها في النطاق. التعقيد الخوارزمي لمثل هذا الحل سيكون خطيًا.

لتقليل عدد عمليات التحقق والحصول على حل يعمل مع O (log n) ، تحتاج إلى استخدام خوارزمية البحث الثنائية. فكرة الخوارزمية هي أنه في كل تكرار للبحث ، ينقسم نطاق القيم إلى نصفين ، ويستمر البحث بشكل متكرر في النصف الذي يوجد فيه الحل. سينتهي البحث عندما ينهار النطاق إلى قيمة واحدة. اقرأ المزيد عن خوارزمية البحث الثنائي في مقالة ويكيبيديا .

لقد تحققنا من التعقيد الخوارزمي للحل باستخدام MutationObserver : وضعناه على الصفحة وحسبنا عدد الطفرات التي يتخذها DOM في عملية العثور على الإجابة. بالنسبة لبعض الاختبارات ، كان عدد الطفرات محدودًا بشكل صارم من الأعلى بحيث لا يتمكن سوى حل قائم على البحث الثنائي من تجاوز هذا التقييد.

للحصول على الدرجة الكاملة للمهمة ، كان من الضروري أيضًا التحقق بعناية من شروط الحدود المختلفة (مطابقة الحد الأدنى والحد الأقصى ، سطر فارغ من النص عند الإدخال) وتوفير العديد من الظروف البيئية التي يتم فيها تشغيل الرمز (على سبيل المثال ، تم إصلاحه! حجم الخط المهم في صفحة CSS )

المهمة 5. الصعوبات في الاتصال

في كل من خيارات التأهيل ، كانت هناك مهمة حيث تم عرض صفحة HTML مع بعض الواجهات كمدخلات. كان للمهام وسيلة إيضاح مختلفة ، لكنها اختتمت جميعها بحقيقة أنه كان من الضروري استخراج بعض البيانات من الصفحة ، وباستخدام هذه البيانات ، بطريقة أو بأخرى التفاعل مع الواجهة.

دعونا نحلل حل إحدى مهام هذه السلسلة ، والتي كانت تسمى "صعوبات في التواصل".

الشرط

يحب الحصان أدولف التحدث مع الأصدقاء على الهاتف. لسوء الحظ ، هذا نادر. في كل مرة يريد أدولف الاتصال بها ، يستغرق الأمر أكثر من ساعة للاتصال برقم صديق. هذا لأنه من الصعب عليه أن يضغط على المفاتيح اليمنى بحوافره السميكة.

لحسن الحظ ، يدعم هاتف Adolf JavaScript. يرجى كتابة برنامج يطلب أصدقاء Adolf بالضغط على لوحة المفاتيح. يتم تسجيل جميع الأرقام اللازمة في دفتر الملاحظات. الحصان المؤسف سيكون ممتنا جدا لك!

التحليل

فيما يلي الصفحة التي تم عرضها كمدخل:



الجزء الأول من الحل هو استرداد البيانات
يتم تعيين كل رقم من أرقام الهاتف من خلال صورة عبر صورة خلفية. في نفس الوقت ، أثناء التحقق ، يتم استبدال الأرقام ديناميكيًا. إذا فتحت المصحح في مستعرض ونظرت إلى شجرة 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> 

في هذه الحالة ، كان يكفي فقط إنشاء قاموس واستخراج فئات CSS وتحويلها إلى سلسلة برقم وفقًا للقاموس ، باستثناء الفواصل (فاصل فئة CSS). على سبيل المثال ، مثل هذا:

 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> 

يمكن للمرء ببساطة إنشاء قاموس آخر يدويًا حسب الفهرس ، ولكن هناك طريقة أبسط. إذا نظرت عن كثب إلى الأنماط الموجودة في مفتش الويب ، فسوف تلاحظ أن الرقم الموجود على الزر يتم تعيينه من خلال محتوى خاصية CSS للعنصر: قبل العنصر الزائف. على سبيل المثال ، بالنسبة للمفتاح "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; }, {}); 

ونتيجة لذلك ، نحصل على كائن حيث ستكون النصوص الرئيسية هي النصوص الموجودة على الأزرار (رقم أو "اتصال") ، وستكون القيم عبارة عن عقد DOM.

يبقى فقط لأخذ القيم من المصفوفة الأولى (phoneNumber) ، وتصفحها وانقر على الأزرار المقابلة باستخدام قاموس المفاتيح الخاص بنا:

 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 نظام إدارة المهام في شركته. فشل الخادم الذي يوجد عليه النظام (ولم يقم Fedor بعمل نسخ احتياطية).

في ذاكرة الخادم ، بقيت ذاكرة تخزين مؤقت من الهياكل تصف المهام والمنفذين والمراقبين ، بالإضافة إلى العلاقات بين هذه الهياكل. بالإضافة إلى ذلك ، تم الحفاظ على ارتباط ذاكرة التخزين المؤقت إلى الهيكل الأخير الذي تم تغييره.

ساعد Fedor على كتابة وظيفة يمكنها استعادة جميع الاتصالات الممكنة بين المهام والمستخدمين وحفظها في مستند بتنسيق Markdown ، والذي ستقوم منه Fedor بعد ذلك باستعادة قاعدة البيانات إلى خادم جديد.

يجب أن يكون مستند تخفيض السعر بالتنسيق التالي:

 ##  - %  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[]; }; 

يتم تخزين المهام في ذاكرة التخزين المؤقت كهيكل من نوع `Task`:

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

قالب الحل

يجب أن يحتوي الحل الخاص بك على وحدة CommonJS تصدر دالة تتوافق مع التوقيع التالي:

 /** * @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; // ...      

.