Frontend, algoritmos e gambá Frederick. Analisamos as tarefas do concurso Yandex

Com este post, estamos concluindo uma série de publicações sobre os concursos do Yandex.Blitz em 2018. Esperamos que você tenha a oportunidade de participar ou, pelo menos, ver que tipo de tarefas que propomos perto da produção. O último concurso foi dedicado ao uso de algoritmos no frontend. Hoje publicamos análises detalhadas de 12 problemas: os 6 primeiros foram propostos na rodada de qualificação e os problemas de 7 a 12 na final. Tentamos explicar como as condições se formaram, a quais habilidades prestamos atenção. Obrigado a todos os participantes pelo interesse!

Tarefa 1

A primeira tarefa foi o aquecimento, por 20 minutos, e decidimos fazer sua condição para que ela fosse facilmente resolvida com a ajuda de expressões regulares.

Todas as opções para a tarefa são construídas de maneira semelhante - há uma divisão em pontos, cada um dos quais pode ser representado pelo grupo na expressão regular final.

Considere uma das opções: Agência Postal.

Condição

No planeta Jopan-14-53, os habitantes locais querem enviar cartas uns aos outros, mas os robôs pombos que devem entregá-los estão confusos nos endereços. Você precisa ensiná-los a analisar as letras e verificar sua validade.

A estrutura da parte básica do endereço consiste na região, município, nome e sobrenome do destinatário. O município pode ser dividido em condados e correios. Todas as partes são separadas por vírgula.

Os nomes de regiões, municípios e distritos são palavras, a primeira letra de cada palavra é grande, o restante é pequeno. São possíveis nomes de duas palavras, separados por um espaço ou um sinal de menos. Em cada palavra de três a oito letras AZ.

Os habitantes têm 6 dedos nas mãos, na vida cotidiana o sistema duodecimal. Os números de 0 a 9 são usados ​​como estão e 10 e 11 são indicados pelos sinais ~ e ≈ .

O número da agência postal na composição possui 3 dígitos seguidos ou 4 divididos em 2 grupos de 2 dígitos com um sinal de menos. Exemplos: 300 , 44-99 .

Às vezes, os moradores enviam cartas para o município sob demanda. Nesse caso, não há endereço: apenas o município e o nome do destinatário.

É engraçado, mas as pessoas no planeta são chamadas apenas seis nomes e nove sobrenomes. Nomes: Shob, Ryob, Mob, Xiang, Ryan, Mans. Sobrenomes: Sho, Ryo, Mo, Xia, Rya, Ma, Syu, Ryu, Mu. Os habitantes deste planeta não são sonhadores.

Análise

A estrutura da parte básica do endereço consiste na região, município, nome e sobrenome do destinatário. O município pode ser dividido em condados e correios. Todas as partes são separadas por vírgula.

Nos primeiros parágrafos, aprendemos como indicar a região, município, distrito, agência postal, nome e sobrenome, e em que ordem eles devem seguir na linha testada.

Os nomes de regiões, municípios e distritos são palavras, a primeira letra de cada palavra é grande, o restante é pequeno. São possíveis nomes de duas palavras, separados por um espaço ou um sinal de menos. Em cada palavra de três a oito letras AZ.

Desse parágrafo, fica claro que o grupo corresponde às palavras ([-][-]{2,7}) . E os nomes, respectivamente, ([-][-]{2,7}(?:[- ][-][-]{2,7})) .

Os habitantes têm 6 dedos nas mãos, na vida cotidiana o sistema duodecimal. Os números de 0 a 9 são usados ​​como estão e 10 e 11 são indicados pelos sinais ~ e ≈ .

Aqui aprendemos que não é suficiente usar \d para números - você precisa usar [0-9~≈] .

O número da agência postal na composição possui 3 dígitos seguidos ou 4 divididos em 2 grupos de 2 dígitos com um sinal de menos. Exemplos: 300 , 44-99 .

Assim, o grupo corresponde aos números da agência postal ([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2}) .

Às vezes, os moradores enviam cartas para o município sob demanda. Nesse caso, não há endereço: apenas o município e o nome do destinatário.

Entendemos, lembramos e levamos em consideração na montagem da função final que o distrito e os correios podem estar ausentes simultaneamente.

É engraçado, mas as pessoas no planeta são chamadas apenas seis nomes e nove sobrenomes. Nomes: Shob, Ryob, Mob, Xiang, Ryan, Mans. Sobrenomes: Sho, Ryo, Mo, Xia, Rya, Ma, Syu, Ryu, Mu. Os habitantes deste planeta não são sonhadores.

Esta é a última parte da condição. Aqui precisávamos de outro grupo simples (||||||||) (|||||) ou seu equivalente mais curto ([][]|[]) ([C]|[]||) .

Por simplicidade, salvamos os grupos em variáveis ​​e os usamos na expressão regular resultante.

 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); }; 

Tarefa 2. Código no qual há um erro

Condição

Durante o dia, a equipe de desenvolvimento fez vários novos recursos. Mas, ao preparar o lançamento, ocorreram conflitos de mesclagem e, depois de resolvidos, o layout se separou. É urgente se livrar dos erros devido ao número mínimo de correções no código, para que o lançamento tenha tempo para entrar em produção.

Você recebe uma página HTML com estilos desfeitos e um formato PNG (com o resultado esperado). Você precisa corrigir os erros para que o resultado ao visualizar no Chrome se torne o mesmo da captura de tela original. Envie a página corrigida como uma solução para o problema.

Página HTML com estilos quebrados. Layout:

Análise

Nesta tarefa, tentamos imitar a situação que os desenvolvedores do Yandex enfrentam regularmente: na enorme base de código, encontre as poucas linhas simples de código, cuja correção leva ao resultado desejado. Ou seja, a dificuldade não estava em escrever o código, mas em entender exatamente onde escrevê-lo (ou excluí-lo).

Pegamos o código real do mecanismo de pesquisa e fizemos apenas algumas correções que quebraram o layout. Os participantes da competição tiveram menos de uma hora para lidar com aproximadamente 250 kilobytes de layout e levar o código a um estado correspondente ao layout.

É claro que o prazo para a competição não permitiu a leitura de todo o código; portanto, os participantes devem usar as ferramentas para desenvolvedores no navegador.

Para corrigir uma das quatro opções de tarefas, as seguintes alterações foram suficientes:

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

  índice 36b9af8..1e30545 100644 

  --- a / blitz.html 

  +++ b / blitz.html 

  @@ -531.10 +531.6 @@ 

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

  altura: auto; 

  } 

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

  - fundo: # ff0! important; 

  -} 

  - 

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

  / * ../../node_modules/islands/common.blocks/input/__clear/input__clear.css começa * / 

  / * Posicionado em relação à caixa de entrada. 

  @@ -744.10 +740.6 @@ 

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

  clipe de fundo: caixa de preenchimento; 

  } 

  .input_theme_websearch .input__clear { 

  background-image: url ("/ static / web4 / node_modules / islands / common.blocks / input / _theme / input_theme_websearch.assets / clear.svg"); 

  tamanho do plano de fundo: 16 px; 

  @@ -857,6 +849,7 @@ 

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

  cor de fundo: # f2cf46; 

  } 

  .websearch-button__text: antes de { 

  + posição: absoluta; 

  superior: -6px; 

  direita: -9px; 

  largura: 0; 

  @@ -866,8 +859,6 @@ 

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

  estilo de borda: sólido; 

  cor da borda: rgba (255,219,76,0); 

  cor da borda esquerda: herdar; 

  - posição: relativa; 

  - índice z: -1000; 

  } 

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

  @@ -1349,6 +1340,7 @@ 

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

  tamanho da fonte: 14 px; 

  altura da linha: 40 px; 

  posição: relativa; 

  + display: bloco embutido; 

  altura: auto; 

  estofamento: 0; 

  alinhamento vertical: meio; 

Tarefa 3. Uma imagem com uma dada variabilidade

Condição

O designer projetou o logotipo. Ele precisará ser usado em uma variedade de condições. Para torná-lo o mais conveniente possível, crie um elemento HTML em CSS puro.

Você não pode usar imagens (mesmo através dos dados: uri).

Análise

Como a tarefa era usar apenas uma div, tudo o que temos é a própria div e os pseudo-elementos :: before e :: after.

Felizmente, a imagem no layout consiste em apenas três áreas de cores diferentes. Criamos nosso próprio plano de fundo para cada elemento acessível, posicionamos corretamente e cantos arredondados. Há uma sombra na área cinza do layout - fazemos com um gradiente.

 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; } 

Tarefa 4

Condição

Petya trabalha como compositora sênior no jornal Moscow Frontender. Para o layout do jornal, Petya usa uma pilha de tecnologias da web. A tarefa mais difícil que Petya enfrentou foi o layout dos títulos nos artigos de jornal: as colunas dos jornais de cada edição têm larguras diferentes e os títulos têm uma fonte diferente e um número diferente de caracteres.

Petya precisa escolher seu próprio tamanho de fonte para cada cabeçalho, para que o tamanho da fonte seja máximo, mas ao mesmo tempo todo o texto do cabeçalho se encaixa no espaço que lhe é atribuído.

Ajuda Petya: implemente a função calcFontSize, que permitirá inserir o texto transferido no contêiner para que ele caiba no contêiner inteiro e tenha o tamanho máximo possível. Se isso falhar, a solução deve retornar nula. O comprimento máximo da linha de entrada é de 100 caracteres. A sequência de entrada não pode estar vazia. Sua solução deve conter todo o código de função e não deve usar dependências externas para que Petya possa copiá-lo em seu projeto e chamá-lo em seu código.

Verificaremos o quão otimamente sua solução funciona e a multaremos se produzir muitas manipulações DOM.

Análise

A primeira coisa a fazer é aprender a determinar se o texto cabe no contêiner, pois o texto no contêiner pode levar várias linhas. A maneira mais fácil de fazer isso é usar a função element.getBoundingClientRect () , que permite obter as dimensões do elemento.

Você pode desenhar texto com um elemento de extensão separado dentro do contêiner e verificar se a largura ou altura desse elemento excede o tamanho do contêiner. Se sim, o texto não cabe no contêiner.

Em seguida, verifique as condições de contorno. Se o texto não couber no contêiner, mesmo com um tamanho mínimo de fonte, ele não poderá ser inserido. Se o texto quebrar com o tamanho máximo permitido, max será a resposta correta. Em outros casos, o tamanho da fonte desejado está em algum lugar no intervalo [min, max].

Para encontrar uma solução, você precisa classificar essa lacuna inteira e encontrar um valor de tamanho da fonte no qual o texto é colocado no contêiner, mas se você aumentar em 1 - não caberá.

Você pode fazer isso com um loop for simples no intervalo [min, max], mas a solução fará várias verificações e redesenhos da página - pelo menos uma para cada valor a ser verificado no intervalo. A complexidade algorítmica de uma solução desse tipo será linear.

Para minimizar o número de verificações e obter uma solução que funcione para O (log n), você precisa usar o algoritmo de pesquisa binária. A idéia do algoritmo é que, a cada iteração da pesquisa, o intervalo de valores seja dividido em duas metades e a pesquisa continue recursivamente na metade em que a solução está localizada. A pesquisa terminará quando o intervalo diminuir para um único valor. Leia mais sobre o algoritmo de pesquisa binária no artigo da Wikipedia .

Verificamos a complexidade algorítmica da solução usando MutationObserver : a colocamos na página e calculamos quantas mutações o DOM toma a decisão no processo de encontrar a resposta. Para alguns testes, o número de mutações foi estritamente limitado a partir de cima, de modo que somente uma solução baseada em pesquisa binária pudesse passar nessa restrição.

Para obter a pontuação completa da tarefa, também foi necessário verificar cuidadosamente as diferentes condições de contorno (correspondendo min e max, uma linha de texto vazia na entrada) e fornecer várias condições ambientais nas quais o código é executado (por exemplo, corrigido com! Importante tamanho da fonte na página CSS )

Tarefa 5. Dificuldades na comunicação

Em cada uma das opções de qualificação, havia uma tarefa em que uma página HTML com alguma interface era oferecida como entrada. As tarefas tinham uma legenda diferente, mas todas se resumiam ao fato de que era necessário extrair alguns dados da página e, usando esses dados, de alguma forma interagir com a interface.

Vamos analisar a solução para uma das tarefas desta série, chamada "Dificuldades na comunicação".

Condição

O cavalo Adolf adora conversar com os amigos por telefone. Infelizmente, isso é raro. Cada vez que Adolf quer ligar, leva mais de uma hora para discar o número de um amigo. Isso ocorre porque é muito difícil para ele acertar as teclas certas com seus cascos grossos.

Felizmente, o telefone de Adolf suporta JavaScript. Por favor, escreva um programa que disque os amigos de Adolf clicando no teclado. Todos os números necessários são gravados em um notebook. O cavalo infeliz será muito grato a você!

Análise

Aqui está a página que foi oferecida como entrada:



A primeira parte da solução é recuperar dados
Cada um dos dígitos do número de telefone é definido por uma imagem via imagem de fundo. Ao mesmo tempo, durante a verificação, os números são substituídos dinamicamente. Se você abrir o depurador em um navegador e olhar para a árvore DOM da página, notará que cada elemento DOM usa classes claras:

 <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> 

Nesse caso, bastava criar um dicionário, extrair classes CSS e convertê-las em uma string com um número no dicionário, excluindo separadores (separador de classes CSS). Por exemplo, assim:

 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; }, []); 

Como resultado, obtemos a seguinte matriz: [9, 8, 5, 4, 1, 2, 8, 0, 9, 0].

A segunda parte da solução é interagir com a interface
Nesse estágio, já temos uma matriz com todos os dígitos do número e precisamos entender quais botões do teclado correspondem a qual dígito. Se olharmos para o código HTML, veremos que não há classes de dicas especiais indicando um número no teclado:

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

Pode-se simplesmente criar outro dicionário manualmente por índice, mas existe uma maneira mais simples. Se você observar atentamente os estilos no inspetor da web, notará que o número no botão é definido por meio do conteúdo da propriedade CSS para o pseudoelemento: before. Por exemplo, para a tecla "3", os estilos são assim:

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

Para obter o valor dessa propriedade, usamos o método 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; }, {}); 

Como resultado, obtemos um objeto em que os textos-chave serão os textos dos botões (número ou "chamada") e os valores serão nós DOM.

Resta apenas pegar os valores da primeira matriz (phoneNumber), passar por eles e clicar nos botões correspondentes usando o nosso dicionário de chaves:

 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(); 

Observe: antes de discar, adicionamos um valor de chamada ao final da matriz. Isso é exigido pelas condições da tarefa, pois se você discar o número e não pressionar "ligar", a solução não passará no teste.

Outro recurso é a pressão assíncrona dos botões do teclado. Se o intervalo de tempo entre as teclas pressionadas durante a discagem for menor que 50 ms, essa solução também não passará no teste. Esse recurso não foi explicitamente descrito nas condições do problema, e esperávamos que o participante descobrisse lendo o código fonte da página. A propósito, uma pequena surpresa aguardava os participantes no código fonte. ;)

Tarefa 6

Condição

Fedor Rakushkin administra o sistema de gerenciamento de tarefas em sua empresa. O servidor no qual o sistema está localizado falhou (e o Fedor não fez backups).

Na memória do servidor, havia um cache de estruturas descrevendo tarefas, executores e observadores, bem como os relacionamentos entre essas estruturas. Além disso, o link do cache para a última estrutura que foi alterada foi preservado.

Ajude o Fedor a escrever uma função que possa restaurar todas as conexões possíveis entre tarefas e usuários e salvá-las em um documento no formato Markdown, a partir do qual o Fedor restaurará o banco de dados em um novo servidor.

O documento de remarcação deve ter o seguinte formato:

 ##  - %  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% 

A lista de tarefas, a lista de executores na tarefa, a lista de observadores na tarefa, a lista de usuários e a lista de tarefas que o usuário realiza devem ser classificadas lexicograficamente.

Descrição das estruturas no cache

Os usuários são armazenados no cache como uma estrutura do tipo `Usuário`:

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

As tarefas são armazenadas no cache como uma estrutura do tipo `Tarefa`:

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

Modelo de Solução

Sua solução deve conter um módulo CommonJS exportando uma função correspondente à seguinte assinatura:

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

Exemplos

 //    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; 

Se você exibir um link para `lastEdited`, obterá a seguinte estrutura:

 { 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 . Por exemplo:









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

.