Боты-балансировщики


День 10 Advent of Code 2016

Часть 1

  1. Передавать деньги
  2. Создание словаря ботов
  3. Подтверждение того, что существует один бот с двумя значениями
  4. Передача микрочипов другим ботам
  5. Подтверждение успешной передачи с помощью примера ввода
  6. Я предположил, что ошибся, но исправить это было просто.
  7. Подтверждение успешной передачи с помощью моего ввода головоломки

Передача ответственности

  • Словарь ботов
  • У каждого есть идентификатор, очередь значений микрочипов — максимум 2
  • и пара правил.
  • Я предполагаю, что только один бот будет начинать с двух значений.
  • Дальше, похоже, идет итеративный процесс передачи значений.

Построение словаря ботов

Мой вход имеет такие строки:

bot 125 gives low to output 4 and high to bot 29
value 41 goes to bot 204
bot 69 gives low to bot 197 and high to bot 15
bot 0 gives low to bot 207 and high to bot 110
Войти в полноэкранный режим Выйти из полноэкранного режима

Важные биты:

  • Является ли это присвоением значения или правилом бота
  • идентификатор бота
  • каждый из типов получателей бота
  • идентификаторы получателей бота

Слишком предписывающий подход:

Set bots as a dictionary
Split each line at the space character into an array of words
  If the array's length is 6 - its a value
    Create or update a key in bots associated with the second number in the array, and set as a key in its dictionary value the first number
  Else - its a bot rule
    Store the id, low recipient and id, high recipient and id
    Create or update a key in bots associated with the id, and set as key-value pairs in its dictionary the mapping of recipient types and ids for each direction
Войти в полноэкранный режим Выход из полноэкранного режима

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

value 5 goes to bot 2
bot 2 gives low to bot 1 and high to bot 0
value 3 goes to bot 1
bot 1 gives low to output 1 and high to bot 0
bot 0 gives low to output 2 and high to output 0
value 2 goes to bot 2
Войти в полноэкранный режим Выйти из полноэкранного режима

Результирующий словарь ботов должен быть таким:

{
  0: {
    values: [],
    recipients: [ 
      { type: 'output', id: 2 },
      { type: 'output', id: 0 } 
    ]
  },
  1: {
    values: [3],
    recipients: [
      { type: 'output', id: 1 },
      { type: 'bot', id: 0 }
    ]
  },
  2: {
    values: [5, 2],
    recipients: [
      { type: 'bot', id: 1 },
      { type: 'bot', id: 0 }
    ]
  }
}
Ввести полноэкранный режим Выйти из полноэкранного режима

Я не могу забыть словарь outputs:
Каждый раз, когда получатель является output, я создаю для него ключ в словаре и устанавливаю его значение в 0.

{ 0: 0, 1: 0, 2: 0 }
Вход в полноэкранный режим Выход из полноэкранного режима

Подтверждение того, что есть один бот с двумя значениями

Iterate through all keys in the bots dictionary
  If there's a bot with a values array with length 2
    Display that bot's dictionary
Вход в полноэкранный режим Выход из полноэкранного режима

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

{
  values: [ 5, 2 ],
  recipients: [ 
    { type: 'bot', id: 1 }, 
    { type: 'bot', id: 0 } 
  ]
}
Войти в полноэкранный режим Выход из полноэкранного режима

Что я увидел, используя вход для головоломки:

{
  values: [ 17, 5 ],
  recipients: [ 
    { type: 'bot', id: 50 }, 
    { type: 'bot', id: 53 } 
  ]
}
Войти в полноэкранный режим Выход из полноэкранного режима

Отлично! Но требуется ли для этого итерация?

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

Set next to null

After adding a value to a bot's values array
  If values has a length of 2
    Set next to the id of this bot

Display the dictionary associated with the bot id stored in next
Вход в полноэкранный режим Выйти из полноэкранного режима

Это сработало! Итератор не нужен!

Передача микрочипов другим ботам

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

Цикл, который будет поддерживать этот процесс, следующий:

Do as long as the values array of the bot id stored in next has a length of 2
  Transfer both microchips elsewhere!
Войти в полноэкранный режим Выход из полноэкранного режима

Что должно произойти?

Sort the values array in ascending order, since that's how I stored each bot's rules
Determine each recipient, to know which dictionary and key to reference
Remove each item from the bot's values array, sending the removed item to the correct recipient
After sending, check whether the recipient is a bot, and whether it's values array now has two items
  If it has two items now, set that bot id as next
Войти в полноэкранный режим Выйти из полноэкранного режима

Более простыми словами:

  • Сортировка
  • Проверьте тип получателя
  • Удалить и отправить
  • Обновить следующее
  • Повторить

Пора написать это в коде!

Подтверждение успешных переводов с помощью примера ввода

Используем пример в качестве моего модульного теста:

  • Начнем с bot 2: check
  • Далее bot 1: проверка
  • Программа завершается?
  • Выходные данные { 0: 0, 1: 2, 2: 0 }?

Что происходит? Это должно происходить:

  • Далее bot 0.
  • Далее без изменений, завершение программы
  • Выходы { 0: 5, 1: 2, 2: 3 }.

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

  • Я использую временную переменную queuedBot для отслеживания предстоящего bot.
  • Она начинается как null.
  • Она становится числом, когда bot, который только что получил значение, теперь имеет два значения

Оригинальный код:

next = queuedBot ? queuedBot : next
Вход в полноэкранный режим Выход из полноэкранного режима
  • Установить следующий в зависимости от queuedBot
  • Если значение queuedBot’а истинно, установите next на его значение.
  • В противном случае, оставьте next без изменений
  • К сожалению, 0 является ложным значением.
  • Таким образом, next никогда не изменится после того, как станет 1.

Обновленный код:

next = queuedBot !== null ? queuedBot : next
Вход в полноэкранный режим Выход из полноэкранного режима

Повторное тестирование на примере ввода:

  • Все боты обрабатываются, и в ожидаемом порядке!
  • Генерируются ожидаемые результаты!

Пора протестировать на входе моей головоломки!

Я предположил, что ошибся, но исправить это было легко.

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

Решение: очередь вместо числа

Вместо:

let next = null
// ...process puzzle input
// ......set next to id of only bot with two values
Войти в полноэкранный режим Выход из полноэкранного режима

Мне нужно было:

let queue = []
// ...process puzzle input
// ......add to queue id of only bot with two values
Войти в полноэкранный режим Выйти из полноэкранного режима

Затем, в моем цикле, мне нужно было сделать несколько изменений:

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

Подтверждение успешной передачи с помощью моего пазла

  • Мой код уже был настроен на отображение словаря выходов
  • До исправлений все выходы были 0, как и было изначально зарегистрировано.
  • После исправлений все выходы были числами, отличными от 0, что, похоже, подтверждало правильность работы моего алгоритма.

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

If joining the values with a | creates the string '17|61'
  Print the id of the current bot
Вход в полноэкранный режим Выход из полноэкранного режима

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

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

Часть 2

Неужели я опять ошибся?!

Согласно инструкции:

Перемножьте значения одного чипа в каждом из выходов 0, 1 и 2.

  • Вот это да! Я предполагал, что каждый вывод будет записан только один раз!
  • Они были записаны несколько раз?
  • Подождите. Даже если это так, головоломки Advent of Code никогда не поддаются случайности.
  • Следовательно, должно быть так, что даже если выходы записываются несколько раз, по крайней мере, в 0,1,2 записываются одни и те же значения.

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

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

  • Каждый выход был массивом из 1 элемента.

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

Тем не менее, перемножение трех значений дало правильный ответ!

У меня получилось!!!

  • Я решил обе части!
  • Я использовал один большой reduce() для генерации обоих словарей bots и outputs!
  • Я сделал несколько неверных предположений, которые позже пришлось учитывать!
  • Я использовал простую queue в качестве трекера следующего бота!
  • Я уже решил часть 2 к тому времени, как закончил часть 1!

Это основной цикл моего алгоритма, который возвращает массив, где каждый элемент — это правильный ответ каждой части:

let answers = []
while (queue.length > 0) {
  let bot = bots[queue[0]]
  bot.values.sort((a, b) => a - b)
  if (bot.values.join('|') == '17|61') {
    answers.push(queue[0])
  }
  bot.recipients.forEach((r, i) => {
    switch (r.type) {
      case "bot":
        bots[r.id].values.push(bot.values[i])
        if (bots[r.id].values.length == 2) {
          queue.push(r.id)
        }
        break;
      case "output":
        outputs[r.id] = bot.values[i]
        break;
    }
  })
  bot.values = []
  queue.shift()
}
return answers.concat(outputs[0] * outputs[1] * outputs[2])
Войти в полноэкранный режим Выйти из полноэкранного режима

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