Это второй пост из моей продолжающейся серии о Пришествии кода 2017. Я собираюсь описать свои решения, реализованные на JS (ES6+) и Node.js.

TL;DR: в этом посте мы увидим больше манипуляций с данными и их синтаксического анализа. Мы также рассмотрим некоторые полезные методы массивов JS. Алгоритмическая часть этой проблемы все еще довольно проста.

Описание проблемы за День 2 здесь: http://adventofcode.com/2017/day/2. Вы можете получить ввод головоломки здесь: http://adventofcode.com/2017/day/2/input.

Первая часть

Итак, в этой части нам сначала нужно разобрать матрицу чисел.

Затем в каждой строке нам нужно определить минимальное и максимальное числа и вычислить их разницу. Наконец, мы вычисляем сумму этих различий.

Полное решение здесь:



emirotin/advent2017
advent2017 — Мои решения для AoC 2017github.com



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

const fs = require("fs");                                               const matrixStr = fs.readFileSync("./input", "utf-8").trim();

Мы читаем файл и обрезаем завершающую новую строку. Теперь у нас есть наша матрица в виде одной строки.

const matrix = matrixStr
  .split("\n")
  .map(str => str.split("\t").map(n => parseInt(n, 10)));

Теперь мы разделяем эту строку по новой строке, получая массив строк, где каждая строка представляет одну строку.

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

В результате у нас есть массив массивов чисел, представляющий нашу матрицу в удобном для нашего алгоритма виде.

const sum = a => a.reduce((x, y) => x + y, 0);

Это хорошая маленькая утилита. Он вычисляет сумму элементов массива с помощью метода reduce (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce). Сначала это может быть немного загадочно для расшифровки, но как только вы привыкнете к этому стилю, он станет очень выразительным.

const cs = sum(matrix.map(r => Math.max(...r) - Math.min(...r)));

console.log(cs);

Наконец, мы можем map преобразовать каждую строку в число: разницу между максимальным и минимальным значениями строки. Здесь я использую оператор расширения, потому что Math.max и Math.min не могут работать с массивами. Таким образом, Math.max(…r) является эквивалентом Math.max(r[0], r[1], ...) (если бы мы только могли писать все элементы массива вручную).

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

Часть вторая

Теперь вместо получения минимума и максимума мы хотим найти пару чисел в каждой строке так, чтобы одно делило другое поровну. Например, 10 делится на 5, 12 делится на 4, а 21 не делится на 6.

Полный код здесь:



emirotin/advent2017
advent2017 — Мои решения для AoC 2017github.com



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

Единственная оптимизация, которую мы здесь делаем, основана на тривиальном наблюдении: если a делится на b, то, очевидно, a ≥ b. Таким образом, чтобы найти пары, мы можем отсортировать каждую строку, а затем попытаться разделить только более поздние числа на те, которые расположены ранее в отсортированной строке.

const isInt = n => n === ~~n;

Это крошечная утилита для проверки, является ли число целым. В JS есть только один тип чисел — с плавающей запятой, что имеет некоторые неприятные последствия для программ, интенсивно использующих вычисления. К счастью, в наших решениях мы не столкнемся ни с одной из этих стен. Здесь происходит то, что я использую оператор побитового отрицания ~, который работает только с целыми числами, поэтому он отбрасывает дробную часть числа и инвертирует биты целочисленной части. Теперь я снова использую его, чтобы восстановить биты int обратно, но дробная часть исчезла. Если число остается прежним, мы заключаем, что на самом деле оно не имеет дробной части, поэтому оно целое.

Теперь, чтобы найти число в одной строке:

const findDiv = r => {
  r = r.slice().sort((x, y) => x - y);
  const l = r.length;
  for (let i = 0; i < l - 1; i++) {
    const x = r[i];
    for (let j = i + 1; j < l; j++) {
      const y = r[j];
      const d = y / x;
      if (isInt(d)) {
        return d;
      }
    }
  }
};

Сначала мы делаем копию строки (r.slice()) и сортируем ее по возрастанию. Есть уродливая ошибка в сортировке массивов JS. Поскольку массивы могут содержать произвольные объекты, сортировка по умолчанию сравнивает их как строки. Таким образом, мы должны сами передать функцию сравнения, чтобы иметь правильную числовую сортировку.

Затем для каждого iго элемента x и для каждого jго элемента y (как описано выше, мы можем искать только ys справа от x после сортировки списка) мы получаем результат деления, и если это целое число, мы мгновенно возвращаем его из функция.

Теперь остальная часть метода тривиальна:

const cs = sum(matrix.map(findDiv));

console.log(cs);

На этом День 2 подходит к концу. Оставайтесь с нами.

Бонус: Кложур

Те же решения в Clojure



emirotin/advent2017
advent2017 — Мои решения для AoC 2017github.com