Недавно я подписался на веселую еженедельную рассылку от Брэндона Моррисона под названием Все тесты пройдены. Каждую неделю я получаю головоломку JavaScript внутри ссылки JSBin, а на следующей неделе я вижу, как другие люди решили ту же проблему.

Большую часть времени программирование заключается в том, чтобы найти правильный компромисс: оптимизируем ли мы пространство или время?

Code Golf — это развлекательный стиль программирования, специально оптимизированный под длину кода. Это означает реализацию алгоритма в кратчайшем количестве символов. Для этого некоторые языки программирования имеют обширные библиотеки коллекций, которые упрощают написание однострочника для реализации алгоритма. JavaScript не входит в их число, но у него есть встроенные методы для работы с массивами, такие как map, filter или reduce. Это позволяет разработчикам JS писать в функциональном стиле, что может привести к довольно краткому коду.

Игра

Задача этой недели заключалась в реализации итератора или генератора для Игры жизни Конвея. Если вы не знакомы с Игрой жизни Конвея, то на самом деле это не столько игра, сколько симуляция (клеточный автомат).

В качестве исходных данных Игра Жизни принимает состояние мира (или доски), которое представлено матрицей живых и мертвых клеток. Каждая итерация функции создает новое состояние на основе определенных правил:

  1. Любая живая клетка с менее чем двумя живыми соседями умирает.
  2. Любая живая клетка с двумя-тремя живыми соседями продолжает жить.
  3. Любая живая клетка с более чем тремя живыми соседями умирает.
  4. Любая мертвая клетка, имеющая ровно три живых соседа, становится живой клеткой.

Эти правила были тщательно подобраны Конвеем для имитации идей недонаселения, перенаселения и размножения.

Теперь я пройдусь по моему мыслительному процессу, оптимизируя код по длине.

Отправная точка

Вот рабочий алгоритм игры «Жизнь»:

Если мы проверим количество слов с помощью команды wc, у нас будет 192 слова и 1333 символа (включая пробелы).

Метод getCellNeighborCount немного длинный, поэтому давайте посмотрим, сможем ли мы найти какие-либо быстрые выигрыши. Этот метод проверяет все ячейки, непосредственно окружающие позицию (x, y), и подсчитывает количество живых соседей. Поскольку нам нужно проверить 8 соседей (это много дублирования), давайте реорганизуем этот метод, создав функцию с именем isAlive, которая проверяет, жива ли ячейка:

const isAlive = (x, y) => board[x] && board[x][y]

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

Теперь функция getCellNeighborCount выглядит так:

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

Следующее, на что я собираюсь обратить внимание, — это основная часть исходного алгоритма, который выполняет итерацию по ячейкам:

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

Мы могли использовать forEach для перебора массива и заполнения returnBoard, но на самом деле мы можем сделать немного лучше. Array.prototype.map перебирает элементы массива, но также возвращает значение, что является хорошим способом моделирования преобразований данных. Если представить доску как состояние мира, то результатом будет следующее состояние мира. Другими словами, цель нашей функции — преобразовать ввод из одного состояния в другое. Использование map также дает нам возможность полностью избавиться от переменной returnBoard.

Мы заменим вложенные циклы for на это:

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

Распаковываем.

Вызов board.map выполняет итерацию по доске, которая представляет собой массив строк на доске. Мы используем функцию стрелки для преобразования каждой строки ввода. Обратите внимание, что из-за отсутствия фигурных скобок вызов row.map явно возвращается как значение.

Вызов row.map перебирает каждую ячейку в строке и делает две вещи:

  • получает количество живых соседей
  • использует правила для возврата следующего состояния ячейки (должна ли она быть живой или мертвой)

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

(isAlive(x, y) ? n > 1 && n < 4 : n === 3) ? 1 : 0

Это выражение проверяет, жива ли ячейка в позиции (x, y).

  • Если это так, он проверяет, есть ли у него 2 или 3 живых соседа. Причина, по которой я решил проверить, больше ли число живых соседей 1, заключается в том, что > — это один символ, а не 3 символа для оператора строгого равенства. Именно поэтому я решил использовать n < 4.
  • Если ячейка мертва, она проверяет, есть ли ровно 3 живых соседа.

Поскольку логические сравнения приводят к true или false, мы проверяем результат выражения с помощью другого тернарного условного оператора и возвращаем 1, если оно true, или 0, если оно false.

Вот что мы имеем на данный момент:

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

Заменим следующие переменные:

  • isAlive становится a
  • board становится b
  • neighborCount становится n
  • row становится r

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

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

Последняя оптимизация подсчета символов, которую мы можем сделать, — это заменить отдельные операторы ветвления if условным оператором и оператором (&&).

На этом этапе мы мудрим, но заменяем оператор if условным оператором, что позволяет нам избавиться от круглых скобок вокруг условия, сэкономив нам еще 2 символа на оператор if.

Резюме

Вот результаты нашего путешествия по кодовому гольфу:

  • Если мы добавим пробелы, исходная версия будет 1333 символа, а окончательная версия будет 418 символов.
  • Если убрать пробелы (поскольку они не имеют семантического значения в JS), исходная версия будет 824 символа, а окончательная версия будет 294 символа.