Con esta publicación, estamos completando una serie de publicaciones sobre los concursos Yandex.Blitz en 2018. Esperamos que haya tenido la oportunidad de participar o al menos ver qué tipo de tareas proponemos cerca de la producción. El último concurso se dedicó al uso de algoritmos en la interfaz. Hoy publicamos análisis detallados de 12 problemas: los primeros 6 de ellos fueron propuestos en la ronda de calificación y los problemas 7–12 en la final. Intentamos explicar cómo se formaron las condiciones, a qué habilidades prestamos atención. ¡Gracias a todos los participantes por su interés!
Tarea 1
La primera tarea fue calentar, durante 20 minutos, y decidimos hacer su condición para que se resolviera fácilmente con la ayuda de expresiones regulares.
Todas las opciones para la tarea se construyen de manera similar: hay un desglose en puntos, cada uno de los cuales puede ser representado por el grupo en la expresión regular final.
Considere una de las opciones: la oficina de correos.
Condición
En el planeta Jopan-14-53, los lugareños quieren enviarse cartas entre ellos, pero los robots de las palomas que deberían entregarlos están confundidos en las direcciones. Tienes que enseñarles a analizar letras y verificar su validez.
La estructura de la parte básica de la dirección consiste en la región, municipio, nombre y apellido del destinatario. El municipio se puede dividir en condados y oficinas de correos. Todas las partes están separadas por una coma.
Los nombres de las regiones, municipios y distritos son palabras, la primera letra de cada palabra es grande, el resto son pequeñas. Los nombres de dos palabras son posibles, separados por un espacio o un signo menos. En cada palabra de tres a ocho letras AZ.
Los habitantes tienen 6 dedos en sus manos, en la vida cotidiana el sistema duodecimal. Los números 0–9 se usan tal cual, y 10 y 11 se indican con los signos
~ y
≈ .
El número de la oficina postal en la composición tiene 3 dígitos seguidos o 4 divididos en 2 grupos de 2 dígitos con un signo menos. Ejemplos:
300 ,
44-99 .
A veces los residentes envían cartas al municipio a pedido. En este caso, no hay dirección: solo el municipio y el nombre del destinatario.
Es gracioso, pero las personas en el planeta se llaman solo seis nombres y nueve apellidos. Nombres: Shob, Ryob, Mob, Xiang, Ryan, Mans. Apellidos: Sho, Ryo, Mo, Xia, Rya, Ma, Syu, Ryu, Mu. Los habitantes de este planeta no son soñadores en absoluto.
Analizando
La estructura de la parte básica de la dirección consiste en la región, municipio, nombre y apellido del destinatario. El municipio se puede dividir en condados y oficinas de correos. Todas las partes están separadas por una coma.
En los primeros párrafos, aprendemos cómo indicar la región, el municipio, el distrito, la oficina de correos, el nombre y el apellido, y en qué orden deben seguir en la línea probada.
Los nombres de las regiones, municipios y distritos son palabras, la primera letra de cada palabra es grande, el resto son pequeñas. Los nombres de dos palabras son posibles, separados por un espacio o un signo menos. En cada palabra de tres a ocho letras AZ.
De este párrafo queda claro que el grupo corresponde a las palabras
([-][-]{2,7}) . Y los nombres, respectivamente,
([-][-]{2,7}(?:[- ][-][-]{2,7})) .
Los habitantes tienen 6 dedos en sus manos, en la vida cotidiana el sistema duodecimal. Los números 0–9 se usan tal cual, y 10 y 11 se indican con los signos ~ y ≈ .
Aquí aprendemos que no es suficiente usar
\d para los números; debe usar
[0-9~≈] .
El número de la oficina postal en la composición tiene 3 dígitos seguidos o 4 divididos en 2 grupos de 2 dígitos con un signo menos. Ejemplos: 300 , 44-99 .
Por lo tanto, el grupo corresponde a los números de la oficina postal
([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2}) .
A veces los residentes envían cartas al municipio a pedido. En este caso, no hay dirección: solo el municipio y el nombre del destinatario.
Entendemos, recordamos y tenemos en cuenta en la asamblea de la función final que el distrito y la oficina de correos pueden estar simultáneamente ausentes.
Es gracioso, pero las personas en el planeta se llaman solo seis nombres y nueve apellidos. Nombres: Shob, Ryob, Mob, Xiang, Ryan, Mans. Apellidos: Sho, Ryo, Mo, Xia, Rya, Ma, Syu, Ryu, Mu. Los habitantes de este planeta no son soñadores en absoluto.
Esta es la última parte de la condición. Aquí necesitábamos otro grupo simple
(||||||||) (|||||) o su contraparte más corta
([][]|[]) ([C]|[]||) .
Para simplificar, guardamos los grupos en variables y los usamos en la expresión regular resultante.
const w = '[-][-]{2,7}';
Tarea 2. Código en el que hay un error
Condición
Durante el día, el equipo de desarrollo realizó varias funciones nuevas. Pero al preparar el lanzamiento, se produjeron conflictos de fusión y, una vez resueltos, el diseño se separó. Es urgente deshacerse de los errores debido a la cantidad mínima de correcciones en el código para que la versión tenga tiempo de entrar en producción.
Se le proporciona una página HTML con estilos rotos y un formato PNG (con el resultado esperado). Debe corregir los errores para que el resultado al visualizar en Chrome sea el mismo que el de la captura de pantalla original. Envíe la página corregida como una solución al problema.
Página HTML con estilos rotos. Diseño:
Analizando
En esta tarea, tratamos de imitar la situación que los desarrolladores de Yandex encuentran regularmente: en la enorme base de código, encuentre las muy pocas líneas simples de código, cuya corrección conduce al resultado deseado. Es decir, la dificultad no estaba en escribir el código, sino en entender exactamente dónde escribirlo (o eliminarlo).
Tomamos el código real del motor de búsqueda e hicimos solo algunas correcciones que rompieron el diseño. Los participantes de la competencia tuvieron menos de una hora para lidiar con aproximadamente 250 kilobytes de diseño y llevar el código a un estado correspondiente al diseño.
Está claro que el límite de tiempo para la competencia no permitió leer el código completo, por lo que los participantes deberían usar las herramientas para desarrolladores en el navegador.
Para corregir una de las cuatro opciones de tarea, los siguientes cambios fueron 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) { - fondo: # ff0! importante;
-}
-
/ * ../../blocks-desktop/input/__control/input__control.styl end * /
/ * ../../node_modules/islands/common.blocks/input/__clear/input__clear.css begin * /
/ * Posicionado en relación con input__box.
@@ -744.10 +740.6 @@
iframe [src $ = 'ext-analytics.html'] { clip de fondo: cuadro de relleno;
}
.input_theme_websearch .input__clear { background-image: url ("/ static / web4 / node_modules / islands / common.blocks / input / _theme / input_theme_websearch.assets / clear.svg"); tamaño de fondo: 16px;
@@ -857.6 +849.7 @@
iframe [src $ = 'ext-analytics.html'] { color de fondo: # f2cf46;
}
.websearch-button__text: antes de { + posición: absoluta;
arriba: -6px;
derecha: -9px;
ancho: 0;
@@ -866.8 +859.6 @@
iframe [src $ = 'ext-analytics.html'] { estilo de borde: sólido;
color del borde: rgba (255,219,76,0);
color del borde izquierdo: heredar;
- posición: relativa;
- índice z: -1000;
}
/ * ../../blocks-deskpad/websearch-button/websearch-button.styl end * /
@@ -1349.6 +1340.7 @@
iframe [src $ = 'ext-analytics.html'] { tamaño de fuente: 14px;
altura de línea: 40 px;
posición: relativa;
+ display: bloque en línea;
altura: auto;
relleno: 0;
alineación vertical: medio;
Tarea 3. Una imagen con una variabilidad dada
Condición
El diseñador diseñó el logo. Tendrá que usarse en una variedad de condiciones. Para hacerlo lo más conveniente posible, complételo con un elemento HTML en CSS puro.
No puede usar imágenes (incluso a través de datos: uri).
Analizando
Como la tarea consistía en usar solo un div, todo lo que tenemos es el div en sí y los pseudo elementos :: before y :: after.
La imagen en el diseño, afortunadamente, consta de solo tres áreas de diferentes colores. Hacemos nuestro propio fondo para cada elemento accesible, colocamos correctamente y redondeamos las esquinas. Hay una sombra en el área gris del diseño; lo hacemos con un degradado.
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; }
Tarea 4
Condición
Petya trabaja como redactora senior en el periódico Moscú Frontender. Para el diseño del periódico, Petya utiliza una pila de tecnologías web. La tarea más difícil que enfrentó Petya fue el diseño de los encabezados en los artículos de los periódicos: las columnas de los periódicos en cada número tienen diferentes anchos, y los encabezados tienen diferentes fuentes y diferentes números de caracteres.
Petya necesita elegir su propio tamaño de fuente para cada encabezado, de modo que el tamaño de fuente sea máximo, pero al mismo tiempo, todo el texto del encabezado se ajusta al espacio asignado para él.
Ayuda a Petya: implementa la función calcFontSize, que te permitirá ingresar el texto transferido en el contenedor para que encaje en todo el contenedor y tenga el tamaño máximo posible. Si esto falla, la solución debería ser nula. La longitud máxima de la línea de entrada es de 100 caracteres. La cadena de entrada no puede estar vacía. Su solución debe contener todo el código de función y no debe usar dependencias externas para que Petya pueda copiarlo en su proyecto y llamarlo en su código.
Comprobaremos qué tan óptimamente funciona su solución y la aplicaremos si produce demasiadas manipulaciones DOM.
Analizando
Lo primero que debe hacer es aprender a determinar si el texto se ajusta al contenedor, dado que el texto en el contenedor puede tomar varias líneas. La forma más fácil de hacer esto es usar la función
element.getBoundingClientRect () , que le permite obtener las dimensiones del elemento.
Puede dibujar texto con un elemento span separado dentro del contenedor y verificar si el ancho o la altura de este elemento excede el tamaño del contenedor. En caso afirmativo, el texto no cabe en el contenedor.
Luego, verifique las condiciones de contorno. Si el texto no cabe en el contenedor incluso con un tamaño de fuente mínimo, entonces no se puede ingresar. Si el texto se rompe con el tamaño máximo permitido, max será la respuesta correcta. En otros casos, el tamaño de fuente deseado está en algún lugar del intervalo [min, max].
Para encontrar una solución, debe ordenar todo este espacio y encontrar un valor de tamaño de fuente en el que el texto se coloca en el contenedor, pero si lo aumenta en 1 –– dejará de ajustarse.
Puede hacer esto con un bucle for simple en el rango [min, max], pero la solución hará muchas verificaciones y redibujos de la página, al menos uno para cada valor que se verificará en el rango. La complejidad algorítmica de tal solución será lineal.
Para minimizar el número de comprobaciones y obtener una solución que funcione para O (log n), debe usar el algoritmo de búsqueda binaria. La idea del algoritmo es que en cada iteración de la búsqueda, el rango de valores se divide en dos mitades, y la búsqueda continúa de manera recursiva en la mitad en la que se encuentra la solución. La búsqueda finalizará cuando el rango se contraiga en un solo valor. Lea más sobre el algoritmo de búsqueda binaria
en el artículo de Wikipedia .
Verificamos la complejidad algorítmica de la solución usando
MutationObserver : la colocamos en la página y calculamos cuántas mutaciones toma el DOM la decisión en el proceso de encontrar la respuesta. Para algunas pruebas, el número de mutaciones estaba estrictamente limitado desde arriba para que solo una solución basada en la búsqueda binaria pudiera pasar esta restricción.
Para obtener el puntaje completo de la tarea, también fue necesario verificar cuidadosamente las diferentes condiciones de contorno (coincidencia mínima y máxima, una línea de texto vacía en la entrada) y proporcionar varias condiciones ambientales en las que se ejecuta el código (por ejemplo, arreglado con! Tamaño de fuente importante en la página CSS )
Tarea 5. Dificultades en la comunicación.
En cada una de las opciones de calificación, había una tarea en la que se ofrecía una página HTML con alguna interfaz como entrada. Las tareas tenían una leyenda diferente, pero todas se reducían al hecho de que era necesario extraer algunos datos de la página y, utilizando estos datos, interactuar de alguna manera con la interfaz.
Analicemos la solución a una de las tareas de esta serie, que se denominó "Dificultades en la comunicación".
Condición
A Horse Adolf le encanta hablar con amigos por teléfono. Lamentablemente, esto es raro. Cada vez que Adolf quiere llamar, le lleva más de una hora marcar el número de un amigo. Esto se debe a que es muy difícil para él golpear las teclas correctas con sus gruesos cascos.
Afortunadamente, el teléfono de Adolf es compatible con JavaScript. Escriba un programa que llame a los amigos de Adolf haciendo clic en el teclado. Todos los números necesarios se registran en un cuaderno. ¡El desafortunado caballo te estará muy agradecido!
Analizando
Aquí está la página que se ofreció como entrada:
La primera parte de la solución es recuperar datos.Cada uno de los dígitos del número de teléfono se establece mediante una imagen a través de la imagen de fondo. Al mismo tiempo, durante la verificación, los números se sustituyen dinámicamente. Si abre el depurador en un navegador y mira el árbol DOM de la página, notará que cada elemento DOM utiliza clases 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>
En este caso, fue suficiente crear un diccionario, extraer clases CSS y convertirlas en una cadena con un número de acuerdo con el diccionario, excluyendo los separadores (separador de clase CSS). Por ejemplo, así:
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, obtenemos la siguiente matriz: [9, 8, 5, 4, 1, 2, 8, 0, 9, 0].
La segunda parte de la solución es interactuar con la interfaz.En esta etapa, ya tenemos una matriz con todos los dígitos del número, y necesitamos entender qué botones del teclado corresponden a qué dígito. Si miramos el código HTML, veremos que no hay clases especiales de pistas que indiquen un número en el teclado:
<div class="keys"> <div class="key"></div> <div class="key"></div> </div>
Uno simplemente podría crear manualmente otro diccionario por índice, pero hay una manera más simple. Si observa detenidamente los estilos en el inspector web, notará que el número en el botón se establece a través del contenido de la propiedad CSS para el pseudo-elemento: before. Por ejemplo, para la tecla "3", los estilos se ven así:
.key:nth-child(3):before { content: '3'; }
Para obtener el valor de esta propiedad, utilizamos el método window.getComputedStyle:
const keys = Array.from(document.querySelectorAll('.game .key')).reduce((res, elem) => { const key = window
Como resultado, obtenemos un objeto donde los textos clave serán los textos en los botones (número o "llamada"), y los valores serán nodos DOM.
Solo resta tomar los valores de la primera matriz (número de teléfono), revisarlos y hacer clic en los botones correspondientes utilizando nuestro diccionario de teclas:
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();
Tenga en cuenta: antes de marcar, agregamos un valor de llamada al final de la matriz. Esto es requerido por las condiciones de la tarea, ya que si marca el número y no presiona "llamar", la solución no pasará la prueba.
Otra característica es la presión asincrónica de los botones del teclado. Si el intervalo de tiempo entre pulsaciones de teclas al marcar es inferior a 50 ms, entonces esta solución tampoco pasará la prueba. Esta característica no se describió explícitamente en las condiciones del problema, y esperábamos que el participante lo descubriera leyendo el código fuente de la página. Por cierto, una pequeña sorpresa esperaba a los participantes en el código fuente. ;)
Tarea 6
Condición
Fedor Rakushkin administra el sistema de gestión de tareas en su empresa. El servidor en el que se encuentra el sistema falló (y Fedor no hizo copias de seguridad).
En la memoria del servidor, quedaba un caché de estructuras que describían tareas, ejecutores y observadores, así como las relaciones entre estas estructuras. Además, se conservó el enlace de caché a la última estructura que se modificó.
Ayuda a Fedor a escribir una función que pueda restaurar todas las conexiones posibles entre tareas y usuarios y guardarlas en un documento en formato Markdown, desde el cual Fedor restaurará la base de datos a un nuevo servidor.
El documento de rebaja debe tener el siguiente 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%
La lista de tareas, la lista de ejecutores en la tarea, la lista de observadores en la tarea, la lista de usuarios y la lista de tareas que realiza el usuario deben clasificarse lexicográficamente.
Descripción de estructuras en el caché.
Los usuarios se almacenan en la memoria caché como una estructura de tipo `Usuario`:
type User = { login: string; tasks: Task[]; spectating: Task[]; };
Las tareas se almacenan en la memoria caché como una estructura de tipo `Tarea`:
type Task = { title: string; assignee: User; spectators: User[]; subtasks: Task[]; parent: Task | null; };
Plantilla de solución
Su solución debe contener un módulo CommonJS que exporte una función correspondiente a la siguiente firma:
module.exports = function (data) {
Ejemplos
Si muestra un enlace a `lastEdited`, obtendrá la siguiente estructura:
{ 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
, .
, , . , :
function traverse(ctx, handlers) {
. , , …
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));
… — :
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();
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 ejemplo:
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> </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');
— 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 =
12. -
X . VCS , .
, -. — , .
, . , , . .
, . ( ) .
.
. — 1000, - — 20.
:
type PullRequest = { files: string[], id: string, created: number, }
(created) (id) – .
CommonJS- :
module.exports = function (pullRequests) {
NodeJS v9.11.2. .
function mergeAllPRs(prs) { } 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
2 ).
, , ( .
). — 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
2 ), . .
, , . , , .
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); } } function doPRsConflict(pr1, pr2) { const i = prToIndex.get(pr1); const j = prToIndex.get(pr2); return conflictMatrix[i * prs.length + j] === 1; }
«» , . ( ) , . , , - .
, , .
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++;
.