Разбор решенных задач с чемпионата по программированию от Яндекса (фронт-энд разработка) 2019

Завершилось мое участие в чемпионате по программированию. Я неплохо прошел квалификацию, решив 4 из 6 задач и шел на 20 месте, поэтому были надежды и в финале попасть топ 20.
Но к сожалению не удалось попасть даже в топ-100. После драки кулаками не машут, но я смог решить еще несколько задач по завершению. Предлагаю вашему вниманию все решенные мной задания.

Отдельная благодарность за помощь в решений:
miraage toster.ru/user/miraage
profesor08 toster.ru/user/profesor08
SmthTo toster.ru/user/SmthTo
RAX7 toster.ru/user/RAX7
dimoff66 toster.ru/user/dimoff66
vk.com/vladilen.minin

Финальный раунд

A. Асинхронный API из параллельной вселенной. (15 баллов)
Условие.

Ваш коллега-разработчик из параллельной вселенной прислал вам свою новую библиотеку для управления космическим кораблем. Т.к. космический корабль штука сложная, то и API у библиотеки довольно «развесистый», точное число методов неизвестно, документации, разумеется, нет. Зато известно, что в параллельной вселенной люди ходят по потолку, спят днём, работают ночью, а ещё используют только асинхронные функции и всегда передают callback первым аргументом. Странные ребята! У нас на Земле уже давно все на промисах пишут. Однако библиотеку нужно интегрировать в проект. Поэтому вам поступила задача написать обёртку, которая будет предоставлять тот же API, но на промисах.

Формат ввода

Пример исходного API:

const api = {  
  a: {  
    b: {  
      c: callback => setTimeout(() => callback(null, ’hello’), 100)  
    }  
  },  
  aa: {  
    bb: (callback, x, y) => setTimeout(() => callback(null, x + y), 200)  
  }  
};

Формат вывода

Отправьте решение в виде:

/**  
 * @param {Object} api - исходное API  
 * @returns {Object}  
 */  
module.exports = function promisify(api) {  
  // ...  
  return promisedApi;  
};

Пример использования:

const promisedApi = promisify(api);  
promisedApi.a.b.c()  
  .then(res => console.log(res)); // => ’hello’

Примечания

обёртка должна возвращать rejected promise в случае ошибки при вызове исходного API, callback всегда принимает ошибку первым аргументом:

callback(error, data)

в исходном API могут встречаться константы (числа, строки и булевые), их нужно возвращать как есть:

api.foo.myConst = 1;  
promisedApi.foo.myConst === 1;

инициализация обёртки должна быть «ленивой»: в исходном API может быть большое количество неймспейсов, и обращаться к ним нужно по мере использования.

Решение

В контесте я решил эту задачу не полностью и получил 12.86 баллов из 15 возможных за решение. Я использовал рекурсию для обхода всех свойств и промисификацию если это функция.
И уже после окончания котеста я доработал решение за счет использования объекта Proxy. Лишь такой вариант прошел все тесты. Ниже представлено решение с учетом доработок.

function promisify (obj) {
  const cache = {}

  return new Proxy(obj, {
    get (target, prop) {
      const value = target[prop]
      const type = Object.prototype.toString.call(value)

      if (type === '[object Object]') {
        cache[prop] = promisify(value) // обходим рекурсивно, если свойство - объект
        return cache[prop]
      } else if (type === '[object Function]') {
        cache[prop] = function (...args) { // переопределяем если функция
          return new Promise((resolve, reject) => {
            const callback = (err, result) => {
              if (err) {
                reject(err)
              } else {
                resolve(result)
              }
            }
            value.call(this, callback, ...args)
          })
        }

        return cache[prop]
      }
      return value
    }
  })
}

На заметку, в node js уже есть такая утилита nodejs.org/dist/latest-v8.x/docs/api/util.html#util_util_promisify_original, только она принимает функцию, у которой callback — это последний аргумент, а не первый.

Все о Proxy:

learn.javascript.ru/proxy
www.youtube.com/watch?v=np08WdS9OXg

B. Будни стажера (15 баллов)
Условие.

В команде Яндекса работает стажёр Степан. Сроки уже поджимают, а он не успевает с вёрсткой страниц. Помогите Степану сверстать одну из них по макету из этой задачи.

При вёрстке не должно быть отступов от левого и верхнего края страницы. Также нельзя использовать изображения. Вот макет:



Как видите, макет состоит из плиток двух размеров: стандартного и двойного. Стандартная плитка занимает 1/3 ширины экрана, двойная — 2/3. Высота плитки фиксированная — 200px. Расстояние между плитками 20 пикселей.

Цвет бекграунда стандартной плитки #8a2be2, цвет двойной #000.

В результате у вас должна получиться HTML-страница с вёрсткой для макета. Размер страницы не должен превышать 10 КБ.

Обратите внимание:

в шаблонах можно писать только вёрстку и стили — JavaScript и изображения использовать нельзя;

Изначально предлагался следующий html файл:

github.com/vito2005/YandexCompetition/blob/master/final-2019/B/original.html

Решение

В принципе можно было обойтись без исходного файла. Но я все таки взял его за основу.
Убрал шрифты и скрипт из разметки, чтобы снизить вес файла.

Далее добавил 6 divов и обернул их во wrapper.

Верстку сделал через display: grid

В итоге получилось следующее:

<html>
    <head>
        <meta charset="utf-8"/>
        <meta http-equiv="X-UA-Compatible" content="IE=edge"/>
        <style>
            body {
                margin: 0;
                padding: 0;
            }
            .wrapper {
                display: grid;
                grid-template-columns: repeat(3, 1fr);
                grid-gap: 20px;
            }
            .banner1, .banner2, .banner3, .banner4, .banner7 {
                background: #8a2be2;
                height: 200px;
            }
            .banner5 {
                background: #000;
                grid-column: 2 /  4;
            }
            .banner6 {
                background: #000;
                grid-column: 1 / 3;
            }
        </style>
    </head>
    <body>
    <div class="wrapper">
        <div class="banner1"></div>
        <div class="banner2"></div>
        <div class="banner3"></div>
        <div class="banner4"></div>
        <div class="banner5"></div>
        <div class="banner6"></div>
        <div class="banner7"></div>
    </div>
    </body>
</html>

C. Идеальные прямоугольники (40 баллов)
Условие.

Боб — художник-экспрессионист. Все его работы представляют собой цветные строго вертикальные прямоугольники на белом фоне.

Недавно его работы опубликовали на сайте известного журнала Top Art. Боб решил разглядеть свои полотна поближе, увеличил масштаб страницы и пришел в ужас от расплывшихся углов и нечётких краёв его идеальных прямоугольников.

Будучи человеком обстоятельным, он изучил проблему и решил свои шедевры сконвертировать в HTML, чтобы под любым углом и в любом масштабе линии оставались идеальными. Для выполнения задуманного он выбрал вас.

Напишите для него сервис, который сможет генерировать html из картинок.

Формат ввода

На вход подаётся строка, которая содержит картинку в base64

Формат вывода

Верните функцию traceImage, которая на вход принимает ссылку на картинку, а возвращает промис, который резолвится со строкой. В строке должна быть вёрстка, которая повторяет эту картинку.

Отправьте решение в виде:

/**  
 *  
 * @param {String} imageSrc - base64 картинки, например ’data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAA...’  
 * @returns {Promise}  
 */  
function traceImage(imageSrc) {  
 // Ваше решение  
}

Примечания

Картинка может быть любого размера
Картинка не прозрачная
Цвет пустых пикселей — белый (r, g, b): (255, 255, 255)
На картинке изображён 1 цветной непрозрачный прямоугольник
Все линии горизонтальные или вертикальные
Код выполняется в браузере

Пример

Дана картинка строкой в base64 (в том виде, в котором она будет передаваться в функцию):

gist.github.com/senaev/50460323558db543256cb7f196e7d81d



Для такой картинки можно сгенерировать строку:

<div>  
    <div style="  
        position: absolute;  
        width: 11px;  
        height: 15px;  
        top: 135px;  
        left: 109px;  
        background-color: rgb(255, 255, 0);  
    "></div>  
</div>

Решение

Суть решения сводиться к тому, чтобы создать canvas по размеру картинки, отрисовать туда картинку и начать c помощью метода getImageData получить информацию о цвете каждого пикселя, далее остается перебирать пиксели с левого верхнего края, пока не попадётся не белый пиксель. Далее продолжить перебирать пиксели по горизонтальной и вертикальной осям пока вновь не встретим белый пиксель, так мы получим ширину и высоту прямоугольника.

В этой статье подробно рассматривается работа с canvas и применение getImageData
code.tutsplus.com/ru/tutorials/canvas-from-scratch-pixel-manipulation--net-20573
К сожалению мой код прошел не все тесты и набрал 30 из 40 баллов, и мне так и не удалось понять ошибки, буду благодарен, если укажите на недочеты:

function traceImage (imgSrc) {
  function loadImg (src) {
    return new Promise((resolve, reject) => {
      if (typeof src !== 'string') reject('wrong data')
      const img = new Image()
      img.addEventListener('load', () => resolve(img))
      img.addEventListener('error', err => reject(err))
      img.src = src
    })
  }

  function calcElementFromImage (img) {
    const TRANSPARENT_COLOR = [255, 255, 255, 1]
    const colorFromData = (data, i) => {
      return [data[i], data[i + 1], data[i + 2], data[i + 3] / 255]
    }
    const w = img.naturalWidth
    const h = img.naturalHeight
    const canvas = document.createElement('canvas')
    canvas.width = w
    canvas.height = h
    const ctx = canvas.getContext('2d')
    ctx.drawImage(img, 0, 0, w, h)
    const data = ctx.getImageData(0, 0, w, h).data

    let top, left, bgColor
    let lastIndex = 0
    for (let i = lastIndex; i < data.length; i += 4) {
      const color = colorFromData(data, i)
      if (!color.every((c, i) => c === TRANSPARENT_COLOR[i])) {
        const px = i / 4
        left = px % w
        top = px / w | 0
        bgColor = color
        lastIndex = i
        break
      }
    }

    let width
    const maxLeftIndex = (w - left) * 4 + lastIndex

    for (let i = lastIndex; i < maxLeftIndex; i += 4) {
      const color = colorFromData(data, i)
      if (color.every((c, i) => c === TRANSPARENT_COLOR[i])) {
        const x = i / 4 % w
        width = x - left
        break
      }
    }

    let height
    const maxTopIndex = (h - top - 1) * w * 4 + lastIndex
    const hStep = w * 4
    for (let i = lastIndex; i < maxTopIndex; i += hStep) {
      const color = colorFromData(data, i)
      if (color.every((c, i) => c === TRANSPARENT_COLOR[i])) {
        const y = i / 4 / w | 0
        height = y - top
        break
      }
    }
    bgColor = Object.values(bgColor).join(',')
    return {
      parentWidth: w,
      parentHeight: h,
      top,
      left,
      width,
      height,
      bgColor
    }
  }
  return loadImg(imgSrc).then(img => {
    const data = calcElementFromImage(img)
    const { parentWidth, parentHeight, top, left, width, height, bgColor } = data
    const div = `<div style="
  position: relative;
  width: ${parentWidth}px;
  height: ${parentHeight}px;">
    <div style=" 
    position: absolute;
    top: ${top}px;
    left: ${left}px;
    width: ${width}px;
    height: ${height}px;
    background-color: rgba(${bgColor})"></div>  
    </div>`
    return Promise.resolve(div)
  })
}

D. Ход конём (40 баллов).
Условие.

Геннадий — интеллектуал. Он любит знакомиться с интересными людьми. Но будучи человеком осмотрительным и недоверчивым, делает он это только в интернете. Недавно Геннадий обнаружил, что сопоставимых по IQ собеседников можно отыскать на шахматном форуме, но вот беда — в шахматы играть Геннадий не умеет, а все обучаторы основаны на javascript-е, который Геннадий осмотрительно отключает, чтобы избежать вероятности подцепить вирус.

Чтобы помочь Геннадию — предлагаем сделать обучатор для игры в шахматы без javascript, который будет показывать, как ходит конь. Обучатор должен выглядеть как шахматная доска. Кликаешь по клетке — тебе показывают, куда с этой клетки может пойти конь.

Формат ввода

html-документ, при загрузке которого рисуется шахматная доска

Формат вывода

Задание будет протестировано в реальном браузере (Chrome 77).
В браузере будет загружен ваш html-документ. Робот кликает в различные ячейки шахматного поля и снимает скриншоты после кликов.
Скриншоты должны соответствовать эталонным

Пример



Примечания

• Реализация на CSS и HTML. Javascript использовать нельзя.
• Вся верстка должна быть квадратной, без теней, градиентов, скруглений и т.п.
• Ширина и высота ячейки — 30 пикселей
• Шахматное поле находится на странице слева сверху, без отступов
• Цвет выделенной ячейки #ff0000
• Цвет ячейки, на которую может ходить фигура #0000ff
• Цвет светлой ячейки #f4cd8d
• Цвет темной ячейки #745853
• Левая верхняя ячейка светлая
• Изначально ни одна ячейка не выделена

Выделение происходит по клику в конкретную ячейку и сохраняется до следующего клика

Решение

К сожалению за отведенные 4 часа мне не удалось полностью предоставить решение, я успел сделать верстку и клик по ячейке, и лишь после окончания турнира, не без помощи коллег с форумов, я все же добил эту задачку.

Итак, первое что надо было сделать — это разместить input type=radio для каждой клеточки, привязать к ним label, задав верстку через display:grid и разбив на 8 колонок через grid-template-columns: repeat(8, 30px). Я долго провозился с версткой для возможных ходов конем.

Сложность заключалась в том, что в css нельзя стилизовать предыдущие элементы.

И она не решаема в данном случае (когда стилизовать требуется и предыдущие, и последующие).
Поэтому, чтобы не загрязнять разметку, я решил добавить псевдоэлементы, которые спозиционированы абсолютом и через background разрисованы линейным градиентом на квадратики. У меня это заняло не мало времени и так и ничего не вышло, однако мне посоветовали отличное решение: задать для выделенной ячейки 8 теней синего цвета и расположить как надо.

В итоге получилось следующее:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
    <style>.white { background: #f4cd8d; }
        .black { background: #746864; }
        body {
            margin: 0;
            display: flex
        }
        div {
            display: grid;
            grid-template-columns: repeat(8, 30px);
            overflow: hidden;
        }
        input {
            display: none;
        }
        label {
            width: 30px;
            height: 30px;
            background: #f4cd8d;
            display: block;
            position: relative;
        }
        input[type="radio"]:checked + label {
            background: #FF0000;
            box-shadow: -30px -60px 0 0 #0000FF, -60px -30px 0 0 #0000FF, 30px -60px 0 0 #0000FF, 60px -30px 0 0 #0000FF, -30px 60px 0 0 #0000FF, -60px 30px 0 0 #0000FF, 30px 60px 0 0 #0000FF, 60px 30px 0 0 #0000FF;
            z-index: 100;
            position: relative;
        }
    </style>
</head>
<body>
<div>
    <input type="radio"  name="tag" id="a1">
    <label class="white a1" for="a1"></label>
    <input type="radio"  name="tag" id="b1">
    <label class="black b1" for="b1"></label>
    <input type="radio"  name="tag" id="c1">
    <label class="white c1" for="c1"></label>
    <input type="radio"  name="tag" id="d1">
    <label class="black d1" for="d1"></label>
    <input type="radio"  name="tag" id="e1">
    <label class="white e1" for="e1"></label>
    <input type="radio"  name="tag" id="f1">
    <label class="black f1" for="f1"></label>
    <input type="radio"  name="tag" id="g1">
    <label class="white g1" for="g1"></label>
    <input type="radio"  name="tag" id="h1">
    <label class="black h1" for="h1"></label>
...........
...........
    <input type="radio"  name="tag" id="a8">
    <label class="black a8" for="a8"></label>
    <input type="radio"  name="tag" id="b8">
    <label class="white b8" for="b8"></label>
    <input type="radio"  name="tag" id="c8">
    <label class="black c8" for="c8"></label>
    <input type="radio"  name="tag" id="d8">
    <label class="white d8" for="d8"></label>
    <input type="radio"  name="tag" id="e8">
    <label class="black e8" for="e8"></label>
    <input type="radio"  name="tag" id="f8">
    <label class="white f8" for="f8"></label>
    <input type="radio"  name="tag" id="g8">
    <label class="black g8" for="g8"></label>
    <input type="radio"  name="tag" id="h8">
    <label class="white h8" for="h8"></label>
</div>
</body>
</html>

Ссылка на рабочий вариант

Продолжение следует…