Взрывчатые вещества в киберпространстве


Адвент кода 2016 День 9

Часть 1

  1. Тот же день, другой год
  2. Пишу спецификацию для цикла
  3. Запуск каждого юнит-теста, затем мой входной пазл

Тот же день, другой год

День 9 2017 года предлагал задачу на аналогичную тему: обработка потока символов.

На этот раз уникальные аспекты:

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

Написание спецификации для цикла

Set answer to 0
Set pointer to 0
Do as long as pointer is not beyond the length of the input string
  Increment answer and pointer depending on the value at pointer:
    1. Value is (
       Create marker as an empty string
       Append to marker one character at a time for all characters after the ( and before the next )
       Split the resulting string at the x into an array of two strings
         Coerce each string to a number
       Increment answer by the product of both numbers
       Increment pointer by the sum of the length of marker, the first of the two numbers, and 2 
    2. Value is anything else
       Increment answer by 1
       Increment pointer by 1
Return answer
Вход в полноэкранный режим Выход из полноэкранного режима

Уравнение, с которым я боролся больше всего:

Increment pointer by the sum of the length of marker, the first of the two numbers, and 2
Вход в полноэкранный режим Выход из полноэкранного режима

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

Запуск каждого модульного теста, затем входной сигнал моей головоломки

  • Эта головоломка любезно предлагает шесть модульных тестов
  • Я прошел первую пару
  • Но провалил средний.
  • Затем прошел средний
  • Но провалил несколько ранних.
  • Затем я исправил свой алгоритм так, что он стал таким, как показано выше.
  • И прошел все модульные тесты.

Затем, запустив его на входе моей головоломки:

  • Сгенерировал правильный ответ!

Мой основной цикл на JavaScript:

let answer = 0, pointer = 0
while (pointer < input.length) {
  switch (input[pointer]) {
    case "(":
      let marker = ""
      for (let j = pointer + 1; input[j] !== ')'; j++) {
        marker += input[j]
      }
      let [chars, times] = marker.split('x').map(Number)
      answer += chars * times
      pointer += marker.length + 2 + chars
      break;
    default:
      answer++
      pointer++
  }
}
return answer
Вход в полноэкранный режим Выход из полноэкранного режима

Часть 2

  1. По-прежнему только длина, но теперь… рекурсия?
  2. Обновление моего алгоритма для использования рекурсии
  3. Запуск каждого модульного теста, а затем входная головоломка

По-прежнему только длина, но теперь… рекурсия?

Итак… я думаю, это хорошая и плохая новость.

Мне нужно внимательнее изучить второй пример:

X(8x2)(3x3)ABCY
Вход в полноэкранный режим Выход из полноэкранного режима
  • Вместо того, чтобы добавить 16 к моей сумме и перейти к Y.
  • мне нужно декомпрессировать этот бит.
  • Попытка декомпрессии приводит к 3.
  • Таким образом, (3x3)ABC в разложенном виде имеет длину 9
  • Вместо 8x2 у меня теперь 9x2 = 18.
  • Добавьте 18 к сумме, затем перейдите к Y.
  • Окончательная сумма: 1 + 18 + 1 = 20.

Хм. Это кажется сложным.

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

Обновление моего алгоритма для использования рекурсии

  • Теперь весь мой алгоритм должен стать функцией
  • Вместо того чтобы увеличивать answer на произведение chars и times, я буду увеличивать answer на число, возвращаемое при вызове функции, но с количеством символов, указанных в скобках, вырезанных из строки сразу после pointer.

Кажется, вот оно!

Запуск каждого юнит-теста, затем на вход моей головоломки

  • Эта часть любезно предлагает еще четыре модульных теста.
  • Я прошел их все!

Затем, запуск на входе моей головоломки:

  • Сгенерирован правильный ответ!

Мой новый основной цикл в JavaScript:

function decompress(stream) {
  let answer = 0, pointer = 0
  while (pointer < input.length) {
    switch (input[pointer]) {
      case "(":
        let marker = ""
        for (let j = pointer + 1; input[j] !== ')'; j++) {
          marker += input[j]
        }
        let [chars, times] = marker.split('x').map(Number)
        answer += times * decompress(
          stream.slice(
            pointer + marker.length + 2, 
            pointer + marker.length + 2 + chars
          )
        )
        pointer += marker.length + 2 + chars
        break;
      default:
        answer++
        pointer++
    }
  }
  return answer
}
Вход в полноэкранный режим Выход из полноэкранного режима

Анимация того, как работает мой рекурсивный алгоритм:

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

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

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