Променад перестановок


Адвент кода 2017 День 16

Попробуйте в симуляторе посмотреть один танцевальный круг, используя входные данные головоломки!

Часть 1

  1. Танцующие массивы? Рассчитывайте на меня!
  2. Разбор каждой инструкции мутации массива
  3. Написание каждой функции инструкции мутации
  4. Выполнение каждой инструкции
  5. Проверка результатов

Танцующие массивы? Запишите меня!

  • Забавная задача о мутации массивов на месте.
  • Впервые видео, на которое дана ссылка — это просто улет!

Итак, приступим к первой задаче: регулярные выражения!

Разбор каждой инструкции по мутации массива

Необходимо подобрать три шаблона:

Таким образом, / и второе целое число являются необязательными.

Мое регулярное выражение выглядит следующим образом:

/(w)([d|w]+)/?([d|w]*)/g
Войти в полноэкранный режим Выйти из полноэкранного режима

Используя это выражение, я перехватываю:

s15
s, 15, empty

pg/b
p, g, b

x7/14
x, 7, 14
Ввести полноэкранный режим Выход из полноэкранного режима

Мне нужно будет немного исправить ситуацию, чтобы убедиться, что я учитываю пустую группу захвата в инструкции s.

Операции matchAll(), slice() и switch позже…

С примером ввода:

s1,x3/4,pe/b
Войти в полноэкранный режим Выйти из полноэкранного режима

Мой алгоритм генерирует следующий список инструкций:

[ [ 's', 1 ], [ 'x', 3, 4 ], [ 'p', 'e', 'b' ] ]
Войти в полноэкранный режим Выйти из полноэкранного режима

Отлично!

Написание каждой функции мутационной инструкции

Я буду использовать словарь, в котором:

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

Это выглядит следующим образом:

const moves = {
  s(X) {
    ...
  },
  x(X,Y) {
    ...
  },
  p(X,Y) {
    ...
  }
}
Войти в полноэкранный режим Выход из полноэкранного режима

Вращение

Я использую комбинацию slice(), concat() и меняю знак аргумента на противоположный, чтобы начать с конца списка:

s(X) {
  programs = programs.slice(-X).concat(programs.slice(0,-X))
}
Вход в полноэкранный режим Выход из полноэкранного режима

Обмен

Я имитирую традиционное средство обмена двумя значениями — использование временной переменной:

x(X,Y) {
  let temp = programs[X]
  programs[X] = programs[Y]
  programs[Y] = temp
}
Войти в полноэкранный режим Выйти из полноэкранного режима

Партнер

Я делаю почти то же самое, что и в Exchange, но создаю две дополнительные переменные для хранения целевых индексов

p(X,Y) {
  let [x,y] = [programs.indexOf(X),programs.indexOf(Y)]
  let temp = programs[x]
  programs[x] = programs[y]
  programs[y] = temp
}
Войти в полноэкранный режим Выход из полноэкранного режима

Выполнение каждой инструкции

For each instruction
  If the first element is an 's'
    Call the appropriate moves function, passing the second element as the sole argument
  Else
    Call the appropriate moves function, passing the second and third elements as arguments
Вход в полноэкранный режим Выход из полноэкранного режима

Тестирование моих результатов

  • Пример ввода: Успех!
  • Ввод моей головоломки: Успех!

Часть 2

  1. Тест на распознавание образов
  2. Экстраполяция на 1 миллиард
  3. Головоломка осталась неразгаданной
  4. Шутка: решена!

Тест на распознавание образов

  • Моя головоломка включает 10 000 инструкций
  • Эти инструкции образуют один танец
  • Мне нужно экстраполировать 1 миллиард танцев.
  • И найти порядок букв в тот самый момент.

Я думаю про себя:

  • Как часто повторяется порядок букв?

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

560,000

Похоже, что это количество инструкций между следующим появлением каждого расположения.

Экстраполяция до 1 миллиарда

  • Изначально я неправильно понимал инструкции.
  • Я думал, что каждая инструкция — это танец.

Таким образом, мое уравнение должно было решить X, где X =:

В этом уравнении X = 1785, а число 400000.

Я понял это как:

  • Расположение букв после 400000 инструкций было таким же, как расположение букв после 1 миллиарда инструкций.

Я ошибся.

Я попробовал расположить буквы после 400001 на всякий случай, вдруг я ошибся на единицу.

Я ошибся.

  • Я перечитал инструкции.
  • Теперь я увидел, что каждый раунд инструкций — это танец.

Таким образом, мое уравнение должно было решить X, где X =:

В этом уравнении X = 17857142, а число 480000.

Я понял это как:

  • Расположение букв после 480000 инструкций было таким же, как расположение букв после 1 миллиарда инструкций.

Я ошибся.

Я попробовал расположить буквы после 480001 на всякий случай, вдруг я ошибся на единицу.

Я ошибся.

Головоломка осталась нерешенной

  • Скорее всего, я где-то неправильно интерпретирую арифметику.
  • Облом. Но пора двигаться дальше.

Шучу: решено!

  • Я ошибся на единицу в другую сторону: 479999!

Я сделал это!!!

  • Я решил обе части!
  • Я получил хорошую практику с регулярными выражениями и манипуляцией массивами на месте!
  • Я построил симулятор для визуализации одного танцевального раунда!
  • Я нашел магическое число и уравнение, которые открыли уравнение для решения части 2!

Оцените статью
devanswers.ru
Добавить комментарий