Безопасный взлом

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

Примечание автора: в этой статье много JavaScript вместо моего обычного языкового псевдокода.

Часть 1

1. Это один сложный opcode!
2. Написание моего метода tgl.
3. Обновление других моих методов opcode.
4. Метод, который доставил мне больше всего хлопот.

Это один сложный opcode!

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

Написание моего метода tgl

Сначала немного настроек:

• Я хочу упростить определение arity метода.

let arity = [['inc','dec','tgl'],['cpy','jnz']]

Теперь напишем tgl.

• Мне нужно сохранить местоположение и инструкцию в этом месте, если таковая имеется.
• Местоположение будет представлено либо как число, либо как строка. Если это строка, то мне нужно найти число, хранящееся в этом регистре.
• В JavaScript я могу условно установить значение в зависимости от типа данных, которые я оцениваю.

// Set arity
tgl(x) {
  let location = pointer + (
    (typeof x == 'number') ? x : registers[x]
  )
  let rule = rules[location]
}

Далее я учту это правило:

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

• В JavaScript, когда я пытаюсь получить доступ к индексу массива, который не существует, программа возвращает undefined, значение false-y

tgl(x) {
  // Set location and rule
  if (rule) {
    // The target instruction is inside the program
  } else {
    // The target instruction is outside the program
  }
}

Далее я учту эти правила:

Для инструкций с одним аргументом inc становится dec, а все остальные инструкции с одним аргументом становятся inc. Для двухаргументных инструкций jnz становится cpy, а все остальные двухаргументные инструкции становятся jnz.

В моем алгоритме rule будет массивом, содержащим либо два, либо три элемента, где первый элемент гарантированно будет трехбуквенной строкой: одним из opcodes.

Я могу проверить первый элемент — по индексу 0 — на включение в arity, чтобы определить, является ли это одноаргументной или двухаргументной инструкцией.

// Set arity
tgl(x) {
  // Set location and rule
  if (rule) {
    if (arity[0].includes(rule[0]) {
      // Account for one-argument instructions
    } else if (arity[0].includes(rule[0]) {
      // Account for two-argument instructions
    }
  }
}

Внутри каждого ответвления я буду использовать оператор switch, чтобы указать, какой из двух cases использовать при обновлении opcode каждой целевой инструкции.

if (arity[0].includes(rule[0]) {
  // Account for one-argument instructions
  switch (rule[0]) {
    case "inc":
      rules[location][0] = "dec"
      break;
    default:
      rules[location][0] = "inc"
      break;
  }
} else if (arity[0].includes(rule[0]) {
  // Account for two-argument instructions
  switch (rule[0]) {
    case "jnz":
      rules[location][0] = "cpy"
      break;
    default:
      rules[location][0] = "jnz"
      break;
  }
}

Наконец, для tgl, мне нужно переместить pointer вперед.

Мой первоначальный метод имел ветвь else, связанную с if, которая проверяла, является ли правило неопределенным.

Мне не нужна эта ветвь else, поскольку все, что она должна была сделать, это увеличить pointer… и мне нужно сделать это независимо от того, что такое rule.

// Set arity
tgl(x) {
  // Set location and rule
  if (rule) {
    // All code written thus far
  }
  pointer++
}

Далее, мне нужно обновить все остальные методы opcode, чтобы учесть эти новые возможные типы данных аргументов.

Обновление моих других методов opcode

Основное изменение небольшое, но важное, и основано на этом влиянии от tgl:

Если переключение производит недопустимую инструкцию (например, cpy 1 2) и позже будет сделана попытка выполнить эту инструкцию, пропустите ее вместо этого.

В каждом из четырех других методов я добавлю это условие:

If the type of the argument being written to is a number
  Increment pointer by 1

Для cpy аргументом является y.

Для inc, dec и jnz аргументом является x.

Метод, который доставил мне больше всего хлопот.

Это был jnz.

Это был мой первоначальный метод:

jnz(x,y) {
  if (typeof x == 'number') {
    x !== 0 ? pointer += y : pointer++
  } else {
    registers[x] !== 0 ? pointer += y : pointer++
  }
}

Как я обнаружил, что именно jnz вел себя неправильно:

• Моя программа завершилась почти мгновенно
• Это был неправильный ответ
• Я добавил протоколирование в метод tgl.
• В моей головоломке была только одна инструкция tgl.
• В первый и единственный раз, когда tgl запустился, rule было undefined.
• Это произошло потому, что местоположение инструкции, которая должна быть изменена, находилось за пределами списка правил.
• Следующая инструкция была cpy — без проблем
• Следующая инструкция была jnz.
• Более точно: jnz 1 c.
• К этому времени регистр c содержал 16.

Пройдемся по моему методу jnz:

jnz(x=1,y='c')

1 is a number
  1 is not 0 ? pointer += 'c'

pointer was 18

pointer += 'c'

pointer is now '18c'

That's not good!

Я не могу полагаться на то, что y всегда будет числом.

Вместо этого мне нужно проверить его тип и либо изменить pointer на число, либо на число, связанное с регистром.

Мой обновленный, рабочий метод:

jnz(x,y) {
  if (typeof x == 'number') {
    x !== 0 ? pointer += (
      (typeof y == 'number') ? y : registers[y]
    ) : pointer++
  } else {
    registers[x] !== 0 ? pointer += (
      (typeof y == 'number') ? y : registers[y]
    ) : pointer++
  }
}

После внесения этого изменения мой алгоритм выполнялся несколько секунд.

После завершения работы регистр a сохранил значение больше 10 000.

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

Часть 2

1. Отлично, мое наименее любимое упражнение
2. Что я должен делать в этой ситуации?
3. Исследую как можно лучше

Отлично, мое наименее любимое упражнение

• Снова задача opcode, которая, похоже, требует, чтобы я диагностировал части программы, из-за которых программа так долго завершается.
• Я не смог успешно сделать это во всех предыдущих упражнениях в другие годы.
• Я не ожидаю успеха и в этот раз.
• Но я должен попытаться!

Что же мне делать в этой ситуации?

Автор полагает:

…не связано ли отсутствие какой-либо более мощной инструкции, чем «прибавить один», с тем, что программа так долго завершается. Разве кролики обычно не умножают?

• Должен ли я изменить свой метод inc, чтобы увеличить значение соответствующего регистра на более существенную величину?
• Я почти уверен, что не должен менять правила.
• Я знаю, что должен начать с регистра a как 12.
• Я мог бы попытаться начать другие регистры со значения, отличного от 0, но это кажется неправильным.

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

Исследую, как могу

• Я попробовал зарегистрировать несколько разных вещей
• Я заметил, что регистр d неоднократно становился экспоненциально большим и медленно возвращался к 0.
• И я заметил, что регистр a постоянно колеблется с большей скоростью.
• В то время как регистры b и c, казалось, изменялись не так сильно.
• Но, в конечном счете, я не нашел никакого существенного крючка для выведения ответа.

Поиск ответа на Reddit

Я благодарен одному комментатору, который поделился коротким путем к решению:

• Найдите пару команд cpy и jnz в конце программы с двузначными аргументами x.
• Вычислить сумму факториала 12 и произведения этих двузначных чисел.

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

cpy 73 c
jnz 82 d

12! + (73 * 82)
---------------
      479007586

Я не собираюсь представлять его, так как не смог найти ответ без посторонней помощи.

Однако приятно осознавать, что ответ все это время «смотрел мне в лицо»… как это обычно и бывает!

Празднование моих достижений

• Я решил часть 1!
• Устранив неполадки и определив ошибочный метод!
• Затем, написав, отладив и повторно протестировав этот метод, пока больше не появлялись ошибки!
• Благодаря одному решателю на reddit я обнаружил то, что, скорее всего, является правильным ответом на часть 2!

Хотя в сегодняшней головоломке была забавная задача по реализации опкода tgl, я надеюсь, что 25-й день — последний в этом и 2015 годах.

Вперед к третьему и, надеюсь, последнему раунду головоломок opcode этого года!