Монорельс Леонардо

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

Часть 1

1. Слава богу: нет опоры на день 11
2. Ассемблерный код: Раунд…?
3. Написание моего рабочего алгоритма

Слава богу: без опоры на День 11

• Мне не удалось решить ни одной части задачи дня 11.
• Это беспокоило меня перед 12-м днем.

К счастью, 12-й день — это еще один…

Ассемблерный код: Раунд…?

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

Эта кажется более простой:

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

Я отправляюсь писать тот же алгоритм в третий или четвертый раз…

Написание моего рабочего алгоритма

Извлечение опкодов и операндов каждой строки:

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

For each string
  Split the string at each space character into an array of two or three strings, saved as op, x and y
  If y contains a value (meaning there were three strings)
    Construct a three-element array containing the opcode string, and either a string or number for x and y
  Else, if y is empty (meaning there were two strings)
    Construct a two-element array containing the opcode string, and either a string or number for x

Вот JavaScript, который я написал:

input.split('n').map(line => {
  let [op, x, y] = line.split(' ')
  if (y) {
    return [op, isNaN(x) ? x : +x, isNaN(y) ? y : +y]
  } else {
    return [op, isNaN(x) ? x : +x]
  }
})

Дополнительная настройка:

Set pointer to 0 so it starts reading at the first instruction
Set registers as an object with four keys, a-d, each with 0 as a value

Словарь функций опкодов:

cpy(x,y) {
  registers[y] = (typeof x == 'string') ? registers[x] : x;
  pointer++
},
inc(x) {
  registers[x]++
  pointer++
},
dec(x) {
  registers[x]--
  pointer++
},
jnz(x,y) {
  registers[x] !== 0 ? pointer += y : pointer++
}

Главный цикл:

Do as long as pointer contains a number that could refer to an index within the bounds of the list of instructions
  Invoke the appropriate function in the dictionary of opcodes, passing as arguments the second value in the instruction and the third...even if there is no third value

while (pointer >= 0 && pointer < rules.length) {
  opcodes[rules[pointer][0]](
    rules[pointer][1], rules[pointer][2]
  )
}

При написании приведенного выше кода я допустил две ошибки:

• Я забыл увеличить pointer в трех функциях, не являющихся jnz.
• Я написал rules[pointer[1]] вместо rules[pointer][1], запутав программу в ожидании, что какое-то свойство 1 существует у числа, хранящегося в pointer.

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

Часть 2

1. Дайте угадаю… тест производительности?
2. К счастью, он завершается через несколько секунд.

Дайте угадаю… тест на производительность?

• Кажется, что это простая задача: изменить c, чтобы он начинался как 1, затем повторно запустить программу.
• В предыдущих головоломках изменение начального значения регистра приводило к тому, что программа выполнялась экспоненциально дольше… казалось, вечно!
• Будет ли так и в этом случае?

К счастью, она завершается за несколько секунд.

• Семь секунд, если быть точным — не очень хорошо
• регистр a содержит число более 9 миллионов — в части 1 он заканчивался числом чуть более 300 тысяч.
• Я не настолько заинтересован, чтобы проверять причину длительного времени выполнения — я пытался сделать это в предыдущих головоломках, и это никогда не помогало мне решить головоломку.
• Я просто рад, что она завершилась менее чем за минуту и выдала правильный ответ!

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

• Я решил обе части!
• К сожалению, я споткнулся на тех же ошибках, что и в предыдущих попытках: просмотр массива и инкремент указателя!
• Я чувствую себя готовым к решению первой части 23-го дня!

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