Контрольная сумма коррупции

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

Часть 1

1. Восхитительное удовольствие от простоты
2. Анимация моего запланированного алгоритма

Восхитительное удовольствие от простоты

• Список чисел
• Найдите разность между наибольшим и наименьшим
• Просуммировать абсолютные значения этих разностей

Звучит уже достаточно просто!

Анимация моего запланированного алгоритма

Что я намерен делать мой алгоритм:

Пора его создавать!

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

• reduce() для подсчета каждой контрольной суммы.
• Регулярное выражение для извлечения чисел каждой строки
• map() для преобразования каждой совпадающей строки в число
• sort() для расположения чисел в порядке возрастания

return input
    .split('n')
    .reduce((chucksums, row) => {
      let cells = [...row.matchAll(/d+/g)]
        .map(match => +match[0])
        .sort((a,b) => a - b)
      return chucksums += cells.pop() - cells.shift()
    }, 0)

Часть 2

1. Вложенные циклы для победы
2. Анимация моего запланированного алгоритма

Вложенные циклы для выигрыша

• После сортировки каждого списка я буду сравнивать каждое значение.
• В худшем случае для моих исходных данных, каждая строка требует 16+15+14…+1 сравнений: это менее 150, умножьте на 16 строк: это менее 2200 в сумме — ничего особенного.

Анимация моего запланированного алгоритма

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

return input
    .split('n')
    .reduce((chucksums, row) => {
      let cells = [...row.matchAll(/d+/g)]
        .map(match => +match[0])
        .sort((a,b) => a - b)
      let divisor = null
      for (let i = 0; i < cells.length - 1; i++) {
        for (let j = i + 1; j < cells.length; j++) {
          if (
              cells[j] / cells[i] == 
              Math.round(cells[j] / cells[i])
             ) {
            divisor = cells[j] / cells[i]
          }
        }
      }
      return chucksums += divisor
    }, 0)

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

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

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

Вперед, день 1!