Спинлок

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

Часть 1

1. Это кажется знакомым…
2. Это кажется довольно простым…

Это кажется знакомым…

Где я раньше видел головоломки с круговой вставкой?

• 2017 В Дне 25 был представлен бесконечно длинный горизонтальный список
• 2018 День 9 содержал похожую головоломку
• 2018 День 14 также содержал подобную головоломку

Это подтверждает мое интуитивное ощущение, что я вспоминаю, что в последнее время видел больше головоломок такого типа.

Это кажется довольно простым…

Start with an array containing the value 0
For i from 1 to 2018 and current starting at 0
  Without deleting anything...
  ...insert i at the location in the array...
  ...equivalent to:
    - the remainder after dividing the sum of
    - current and the puzzle input integer
    - by the length of the array
    - then adding 1
  Then, update current to the location in the array of i

Return the integer at the location one greater than the location of the integer 2017

Этот алгоритм генерирует правильный ответ как для примера ввода 3, так и для моей головоломки!

Однако на пути к его написанию я столкнулся с несколькими ошибками и кажущимися удачными совпадениями:

• Первоначально я использовал цикл для обновления current.
• Мало того, я неправильно увеличивал current на i в каждой итерации этого цикла.
• Удивительно, но я генерировал правильный ответ, используя пример ввода 3!
• Это заставило меня задаться вопросом, почему число, которое я генерировал с помощью моей головоломки, было слишком большим.

К счастью, я решил эти проблемы.

И я упростил, сократил и сжал свой алгоритм до чуть более 5 строк кода!

Вот JavaScript, который я написал для решения части 1:

const part1 = () => {
  let input = 3, RA = [0]
  for (let i = 1, curr = 0; i < 2018; i++) {
    RA.splice((curr + 376) % i + 1, 0, i)
    curr = RA.indexOf(i)
  }
  return RA[RA.indexOf(2017) + 1]
}

Часть 2

1. О да, я это предвидел
2. Обновление после публикации

О да, я это предвидел

• 50 миллионов раз, да?
• И снова я заблокирован от решения, потому что недостаточно знаком со связанными списками… которые являются гораздо более эффективной структурой данных для этой задачи, чем массив.

Надеюсь, я скоро научусь использовать связанные списки.

Затем я вернусь к нескольким вышеупомянутым головоломкам и попытаюсь решить все части 2, которые их требуют.

Обновление после публикации

Использование связанного списка

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

Вот мой основной цикл со связанным списком:

for (let i = 1, curr = 0; i < 2018; i++) {
  let index = (curr + input) % i + 1
  if (index > i - 1) {
    list.insert(i)
    curr = i - 1
  } else {
    list.insertAt(index, i)
    curr = index
  }
}

• Затем я поменял 2018 на 50M и 2017 на 0 и запустил это снова.
• Это тоже, казалось, продолжалось вечно

Облом.

В поисках закономерности

Может быть, существует закономерность для целого числа справа от 0, которую я могу экстраполировать на 50M?

• Я добавил код, который отслеживал любое изменение целого числа справа от 0.
• Я записал новое число: никакой видимой закономерности.
• Я записал разницу между новым и предыдущим числом: никакой видимой закономерности.

Облом.

Я сделал это!

• Я решил часть 1!
• Я сократил свой код почти до 5 строк!
• Я получил еще одну причину для изучения и практики использования связанных списков!
• Обновление: я использовал свою первую библиотеку связанных списков для повторного создания ответа части 1!