Интересная задачка с пробного этапа Yandex Cup "20

Всем привет)

Сегодня я покажу одну из задач, предложенных на Yandex Cup "20. Она совсем несложная, но на мой взгляд интересная. Этап пробный, поэтому я думаю нет ничего страшного в том, что я расскажу как решил ее. Но если вы хотите решить ее сами, закройте статью прямо сейчас.

Для ее просмотра надо зарегистрироваться на контест, а копировать ее сюда я не хочу. Если вкратце, суть задачи в следующем:

Имеется какой-то JS-объект отладочной информации и мы должны отобразить ее на экранчике 300х96 пикселей в виде баркода. Что то типа такого:

Вот структура:

%lang(js)%
{  
    /**  
     * Идентификатор — строка [A-Za-z0-9], len=10  
     */  
    id: string;  
    /**  
     * Код ошибки — целое число от 0 до 999  
     */  
    code: number;  
    /**  
     * Сообщение об ошибке — строка [A-Za-z0-9 ], 0 <= len <= 34
     */  
    message: string;  
}

Структура преобразуется в строку (массив байтов) путем конкатенации компонент (плюс, добавляем незначащие нули и пробелы где это нужно).

Далее мы считаем контрольную сумму всех элементов путем сложения по модулю 2 всех элементов массива. Если мы все сделали правильно, мы получим массив из 48 элементов, где каждый элемент принадлежит диапазону $[0; 255]$ .

Для начала рассмотрим вот такие функции:

%lang(js)%
const fixCode = (code) => {
  if (code < 10) return `00${code}`;
  if (code < 100) return `0${code}`;
  return String(code);
}

const fixMessage = (message) => {
  let newMessage = message;
  while (newMessage.length < 34) newMessage += ' ';
  return newMessage;
}

Они нужны для того, чтобы наше итоговое сообщение всегда было длиной 48 символов.

Нам нужно как то переводить строку в массив байт и считать контрольную сумму. Для этого мы будем использовать вот эти две функции

%lang(js)%
/*
 * Мы превращаем строку в массив строк длиной=1 (грубо говоря, массив символов)
 * затем проходим по каждому элементу получившегося массива с целью
 * узнать код символа, находящегося в позиции 0
 */
const toByteArray = (message) => 
  message.split('').map(x => x.charCodeAt(0));

/*
 * Тут мы делаем побитовое исключающее ИЛИ для подсчета контрольной суммы
 */
const getChecksum = (byteArray) => 
  byteArray.reduce((acc, b) => acc ^= b, 0);

Для рендера кода я решил использовать HTML5 Canvas, потому что двигать div`ы мне не очень то и хотелось. К тому же, решение должно быть предоставлено в виде только JS кода, поэтому все стили пришлось бы писать там же.

%lang(js)%
const prepareBarcodeDOM = (barcodeElement) => {
  // создаем новый canvas элемент
  const canvas = document.createElement('canvas');

  // устанавливаем ему ширину и высоту с помощью атрибутов
  canvas.setAttribute('width', '300px');
  canvas.setAttribute('height', '96px');
  
  /*
   * на всякий случай устанавливаем ширину и высоту div контейнера
   * не знаю точно как происходит проверка решения, но div растягивается
   * на всю ширину (т.к. это блочный элемент) и, возможно, робот,
   * проверяющий решение посчитал бы, что я сгенерировал баркод,
   * ширина которого явно больше 300 пикс.
   */
  barcodeElement.style.width = '300px';
  barcodeElement.style.height = '96px';

  // присоединяем canvas к DOM в качестве ребенка barcodeElement
  barcodeElement.append(canvas);

  // получаем 2d контекст canvas
  const context = canvas.getContext('2d');

  // будем рисовать только черным
  context.fillStyle = 'rgb(0, 0, 0)';

  // вернем контекст (он нам еще пригодится)
  return context;
}

Контекст нам пригодится для рисования, вот кстати функция, которая отвечает за это:

%lang(js)%
const draw = (ctx, buffer) => {
  /*
   * по условию задачи нас просят нарисовать "зебру" из 3 черных и 2 белых линий
   * c двух сторон баркода. 
   * При этом ширина черной линии - 4 пикс., белой - 5 пикс.
   */
  [0, 9, 18, 296, 287, 278].forEach(x => ctx.fillRect(x, 0, 4, 96));

  /* 
   * Потом мы просто бежим по всему экрану, но не по отдельным пикселям, а по
   * блокам 8х8
   */
  for (let i = 0; i < 12; i += 1) {
    for (let j = 0; j < 32; j += 1) {
      /*
       * Эта страшная запись проверяет каждый бит (j / 8 + i * 4)-го
       * элемента нашего массива (обращаю внимание, что j / 8 - 
       * операция целочисленного деления
       *
       * (7 - (j % 8)) - эта штука считает сдвиг, при этом 
       * порядок проверки от седьмого бита к нулевому, а не наоборот
       */
      if ((buffer[Math.floor(j / 8) + i * 4] >> (7 - (j % 8))) & 1) {
        /*
         * Рисуем квадратик 8х8, если в конкретном бите конкретного байта
         * входных данные едицица, иначе ничего не делаем

         * 22 - это смещение вправо из за 5 полосок (сумма их ширин)
         */
        ctx.fillRect(j * 8 + 22, i * 8, 8, 8);
      }
    }
  }
}

Выглядит сложночитаемо, не правда ли? Довольно забавная ситуация на самом деле. Дело в том, что я создавал константы для этого, но программа не прошла по лимиту памяти, лол. Потом я убрал константы и некоторые промежуточные присвоения и смог сдать решение.

Ну и, собственно, штука, которая все это объединяет:

%lang(js)%
const renderBarcode = ({ id, code, message }, el) => {
  const buffer = toByteArray(`${id}${fixCode(code)}${fixMessage(message)}`);
  buffer.push(getChecksum(buffer));
  draw(prepareBarcodeDOM(el), buffer);
}

Входные данные поступают в виде вышеописанного объекта (и мы сразу достаем эти поля с помощью деструктуризации). Затем мы конкатенируем (склеиваем воедино) строки, предварительно дополнив их (code незначащими нулями, а message пробелами). Сейчас в нашем массиве должно быть 47 элементов и мы добавляем еще один - контрольную сумму. Ну и в конце концов вызываем draw().

Тестируем:

%lang(js)%
{  
  "id": "VladIvanov",  
  "code": 999,  
  "message": "Thank you for reading!"  
}

Как-то так:

Спасибо за внимание!