Рекурсивный цирк

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

Часть 1

1. Поиск иголки в стоге сена… с помощью грубой силы
2. Мой ужасно работающий алгоритм

Поиск иголки в стоге сена… с помощью грубой силы

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

Мой ужасно работающий алгоритм

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

Set bottom as empty

For each string
  Split the string at each space character into an array of strings
    Store the first element in the array of strings as the current tower name
  For each string, again
    Check whether the string either starts with the current tower name, or contains the current tower name
    Filter the resulting list of booleans to only include false: meaning the string either started with the current tower name or it contains the current tower name
    Return true if the length of the list is 1: a single false matches the string where the current tower is referenced as the first tower name
  If the above operations returned true, update bottom to the name of the current tower

Return the string stored in bottom

Моя головоломка содержит примерно 1500 башен.

Значит, в худшем случае этот алгоритм должен был работать 2.25M раз!

Ужасно, я знаю.

Но… он сгенерировал правильный ответ!

Часть 2

1. А теперь настоящий вызов!
2. Решим часть 1 быстрее, чтобы подготовиться к решению части 2
3. Попытка №1: Решение части 2 сверхувниз
4. Попытка №2: Решение части 2 внизвверх

А теперь настоящий вызов!

• Регулярные выражения? Скорее всего.
• Рекурсия? Возможно.
• Арифметика? Определенно.
• Какой-то объект, имитирующий древовидную структуру данных? Наверняка.

Решаем часть 1 быстрее в рамках подготовки к решению части 2

Я намерен построить структуру данных, подобную этой:

{
  tknk: {
    weight: 41,
    parent: null,
    children: [ugml, padx, fwft]
  },
  // ...
}

После разбора полной строки ввода:

• В ней будет столько ключей, сколько строк во входных данных моей головоломки.
• Только один ключ будет иметь parent: null.
• Поиск этого ключа не займет много времени… по сравнению с алгоритмом части 1.
• Самое главное, у меня будет плоская структура данных для выполнения поиска в алгоритме, который я собираюсь написать для второй части!

Вот так!

…

После устранения следующих неполадок:

• Быть осторожным при инициализации объекта — я не должен аннулировать существующие пары ключ-значение.
• Проверять все условия на наличие существующего объекта и создавать его, если такового не существует
• Устанавливать каждое свойство отдельно и в соответствующем условии — даже если оно избыточно.

У меня была надежная квази-база данных каждой башни с этими шаблонами объектов:

{
  'tower': {
     parent: 'tower',
     children: ['tower','tower','tower']
     weight: number
  },
  'tower': {
     children: ['tower','tower','tower']
     weight: number
  },
  'tower': {
     parent: 'tower',
     weight: number
  },
}

Теперь поиск нижней башни занял едва ли миллисекунду, поскольку это было всего ~1500 операций… по сравнению с моими первоначальными 2.5M операциями в худшем сценарии

Вот как работает мой более быстрый алгоритм части 1 на исходном примере:

Провал: Решение части 2 вверхвниз

Я ошибочно предположил следующее о башнях:

• Что дерево идеально сбалансировано по количеству ветвей и количеству узлов в каждой ветви.

Как я это определил? Ну, это заняло около часа.

Вот мой алгоритм:

Generate a list of all towers with no children: the `leaf` nodes, or `tops` in this context

For each of those towers
  Add a key, total_weight, whose value is the same as the weight

For each of those towers, again
  Store a reference to the parent tower
  For each tower in the parent tower's list of child towers
    Update the tower name to the tower's weight
  Create a unique set of values from each weight
  If that set's size is 1
    All weights are identical and the sub-tower is balanced
  Else
    I found the unbalanced tower!

Когда я запустил его и отобразил сообщения balanced или unbalanced:

• Я неожиданно увидел много сообщений unbalanced.

Что происходило?

• Я добавил операторы печати, чтобы увидеть вес каждого ребенка башни.
• Многие из них были неопределены.

Как это может быть?

• Я добавил операторы печати, чтобы увидеть имена дочерних башен одного родителя.
• У некоторых из них были дети!

Все это открыло мне глаза:

• Я не могу решить эту головоломку сверху вниз (то есть от узлов листьев к корневому узлу).
• Вместо этого мне придется начать с дочерних узлов корневого узла и работать рекурсивно вниз по башням…
• …как следует из названия головоломки и инструкций.

Попытка №2: Решение части 2 внизвверх

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

После нескольких часов работы я написал рабочий алгоритм, который в основном анимирован ниже:

Набросок того, как это работает:

The recursive function:
  Expect one parameter: an array of child tower names
  The base case:
    An empty array as argument
      Return 0
  Otherwise:
    For each child tower name
      Change the name to a number that is the sum of:
        1. That tower's weight
        2. Calling the recursive function with that tower's children, or an empty array if it has no children
    Create a set of unique values from the updated array
    If the set has more than one unique value, I found the wrong number!
      Create an object that will tally each number in the updated array
      Set wrong to the key who's tally is 1
      Set right to the key who's tally is not 1
      Get the location of the wrong number in the updated array, and use it to get the tower in the same location in the original input array, then get that tower's weight
      Determine whether the wrong number is larger or smaller than the right number
      Set as answer the tower's weight changed by the difference between the wrong and right numbers...using the correct sign (positive/negative)

Call the recursive function
  Pass as argument the bottom tower's children

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

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

Мой алгоритм распечатывает каждый ответ.

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

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

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

Рекурсия по-прежнему пугает меня.

К счастью, в этом раунде я снова справился с ней.

Даже лучше:

• На момент окончания седьмого дня у меня 34 звезды!
• Это мой самый низкий результат, который я набрал за два года!
• Это значит, что если я наберу еще одну звезду, то сравняю свой второй самый низкий результат!
• А если я наберу еще 6 звезд, то сравняю свой лучший результат!
• А если я наберу как минимум 7 звезд, то достигну нового личного рекорда!

Я очень мотивирован закончить год с более чем 40 звездами!