Сканеры пакетов

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

Часть 1

1. Сначала запуганный
2. Затем заинтригован
3. Нахождение шаблона
4. Использование шаблона
5. Написание алгоритма
6. Тестирование моего алгоритма

Сначала запуганный

При беглом просмотре инструкций мой взгляд привлек этот график:

 0   1   2   3   4   5   6
[ ] [S] ... ... [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[S]             [S]     [S]
                [ ]     [ ]

Мне вспомнился 2021 день 23: диаграммы Амфипода:

#############
#...B.......#
###B#C#.#D###
  #A#D#C#A#
  #########

Сходство?

• Структура, похожая на сосульку
• Буквы, занимающие места в любой точке по вертикали внутри сосульки

Затем, заинтригованный

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

Поиск закономерности

Используя пример ввода:

0: 3
1: 2
4: 4
6: 4

И пример диаграммы:

 0   1   2   3   4   5   6
[S] [S] ... ... [S] ... [S]
[ ] [ ]         [ ]     [ ]
[ ]             [ ]     [ ]
                [ ]     [ ]

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

Range  Occupied         Cycle
2      0,2,4,6,8    2
3      0,4,8,12,16  4
4      0,6,12,18    6
5      0,8,16,24    8
6      0,10,20,30,40    10
7      0,12,24      12

Интересно:

2 = 2
3 = 4
4 = 6
5 = 8
6 = 10
7 = 12

Как вычислить правое число по левому?

(left - 1) * 2 = right

(2 - 1) * 2 = 2
(3 - 1) * 2 = 4
(4 - 1) * 2 = 6
(5 - 1) * 2 = 8
(6 - 1) * 2 = 10
(7 - 1) * 2 = 12

Круто!

Теперь, как я могу определить, будет ли сканер занимать крайнюю верхнюю клетку одновременно с моим пакетом?

С помощью шаблона

If the remainder after dividing the depth by double one less than the range is 0
  Caught!
Else
  Unseen!

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

Я очень надеюсь, что это расширится и будет работать на моей головоломке.

Запись моего алгоритма

Split the input at each newline character into an array of strings

For each string
  Accumulate a sum, starting at 0
    Extract the depth and range from each string
      Use the pattern to identify when the packet is caught
      If caught, increment the sum by the product of the depth and range

Return the accumulated sum

Я впечатлен тем, что решил эту задачу менее чем в пяти строках кода.

Я использовал split(), reduce(), map(), ternary operator и array destructuring assignment:

input.split('n').reduce((acc,curr) => {
    let [depth, range] = curr.split(': ').map(Number)
    acc += depth % ((range - 1) * 2) == 0 ? (depth * range) : 0
    return acc
  }, 0)

Тестирование моего алгоритма

• Он сработал на вводе примера!
• Он сработал на входе моей головоломки!

Часть 2

1. Я был близок!
2. Мой шаблон помогает и здесь!
3. Чуть не бросил, пока не сгенерировал правильный ответ

Я был близок!

Я думал, что во второй части будет задан вопрос:

Сколько пикосекунд потребуется для безопасного перемещения пакета через брандмауэр.

Я предполагал, что пакет может запускаться и останавливаться… как в игре Frogger.

Но часть 2 ставит еще более интересную задачу:

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

Мой шаблон помогает и здесь!

После тщательного анализа я заметил, что ответ для примера ввода, 10, является наименьшим числом, удовлетворяющим этому условию:

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

Формула такова:

when (depth + ?) % ((range - 1) * 2) is not 0

• где ? — магическое число.

Начиная с 0 и работая вверх, мой алгоритм работает следующим образом:

Пример, однако, намеренно обманчив.

Я почти выхожу из игры до того, как генерирую правильный ответ.

• Мой алгоритм использует цикл for с произвольным максимумом.
• Поскольку в примере ответ был 10, я начал свой со 100, полагая, что меньше этого значения не будет.

For i from 1 up to and including 100
  Perform the pattern on each depth and range using i to increment the depth
  If every scanner is not in the top-most position
    Print i

Увеличение максимального числа:

Был ли мой шаблон удачным совпадением при использовании в примере?

Наименьшее число пикосекунд не может быть таким высоким… не так ли?!

Увеличение максимального числа:

Первое напечатанное число было на несколько сотен тысяч меньше 4M.

Это был правильный ответ!

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

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

Почему без симулятора?

• Перед решением Части 1 я намеревался построить симулятор.
• После решения части 2 я решил этого не делать.
• Хотя его, возможно, было бы забавно построить и взаимодействовать с ним, я больше горжусь тем, что для решения этой головоломки он мне не понадобился.
• Итак, симулятора нет… потому что он мне не нужен!