Нет времени на такси


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

Часть 1

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

Больше манхэттенского расстояния

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

Структура данных кругового компаса

  • Мне нужно знать направление, в котором я нахожусь.
  • Таким образом, я могу увеличивать или уменьшать соответствующую ось на заданное количество шагов.
  • Я буду использовать массив из 4 элементов, где каждый элемент — это массив из 2 элементов, содержащий модификатор, на который нужно умножить количество по оси: либо 0, либо 1, либо -1.
  • В зависимости от направления вращения, я буду перемещать элемент из начала в конец или наоборот.
  • Мой алгоритм всегда будет использовать первый элемент в массиве
compass = [
  [0,-1], // North
  [1,0],  // East
  [0,1],  // South
  [-1,0]  // West
]
Вход в полноэкранный режим Выйти из полноэкранного режима

Переключение направления на основе типа вращения

  • Мне нужно отделить тип вращения от количества
  • В зависимости от символа вращения, R или L, мне нужно вращать элементы в массиве
let [turn, amount] = [c[0], +c.slice(1)]
switch (turn) {
  case "R":
    compass.unshift(compass.pop())
    break;
  case "L":
    compass.push(compass.shift())
    break;
}
Войти в полноэкранный режим Выйти из полноэкранного режима

Начиная с NSEW, поворот R перемещает N в конец:

N<-S<-E<-W
S  E  W  N
Вход в полноэкранный режим Выход из полноэкранного режима

После поворота L все перемещается вправо:

S->E->W->N
N  S  E  W
Войти в полноэкранный режим Выход из полноэкранного режима

Прохождение дистанции

Команда типа R5 должна переместить меня из:

 x y
[0,0]
Войти в полноэкранный режим Выйти из полноэкранного режима

Чтобы:

 x y
[5,0]
Войти в полноэкранный режим Выйти из полноэкранного режима

Как изменяется компас при повороте R:

[[0,-1],[1,0],[0,1],[-1,0]]

// R5

[[1,0],[0,1],[-1,0],[0,-1]]

// Only reference first item

 [1,0]
Войти в полноэкранный режим Выйти из полноэкранного режима

Как работает умножение:

[ 0 , 0 ]
 +1  +0
 *5  *5

[ 5 , 0 ]
Войти в полноэкранный режим Выход из полноэкранного режима

Вычисление Манхэттенского расстояния

Сумма абсолютных значений каждой координаты.

Например:

[10, -2]

 10 + 2

 12
Войти в полноэкранный режим Выход из полноэкранного режима

Итоговая анимация

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

Мой алгоритм на JavaScript:

let compass = [[0,-1],[1,0],[0,1],[-1,0]]
return input.reduce(
  (coords, move) => {
    let [rotation, amount] = [move[0], +move.slice(1)]
    switch (rotation) {
      case "R":
        compass.unshift(compass.pop())
        break;
      case "L":
        compass.push(compass.shift())
        break;
    }
    return [
      coords[0] + amount * compass[0][0], 
      coords[1] + amount * compass[0][1]
    ]
  }, [0,0])
    .reduce((a, b) => Math.abs(a) + Math.abs(b))
Вход в полноэкранный режим Выход из полноэкранного режима

Часть 2

  1. Вход: Set() и цикл for

Введите: Set() и цикл for

  • Теперь мне нужно отслеживать каждый шаг на этом пути.
  • На каждом шаге мне нужно проверить, был ли этот шаг уже посещен.

Моя Set() будет начинаться так:

let visited = new Set('0|0')
Войти в полноэкранный режим Выйти из полноэкранного режима
  • Я строю координаты, потому что сравнение двух массивов всегда возвращает false.

Мне также нужно собирать каждый повторяющийся шаг:

let answers = []
Вход в полноэкранный режим Выход из полноэкранного режима

Наконец, вместо того, чтобы изменять координату на полную величину, мне нужно:

  • Переместить ее на 1
  • Проверить, был ли этот шаг посещен.
  • Если да, то добавить расстояние до Манхэттена в answers.
  • Добавьте шаг к visited.

Мой цикл for на JavaScript:

for (let i = 0; i < amount; i++) {
  coords = [
    coords[0] + compass[0][0], 
    coords[1] + compass[0][1]
  ]
  if (visited.has(coords.join('|'))) {
    answers.push(Math.abs(coords[0]) + Math.abs(coords[1]))
  }
  visited.add(coords.join('|'))
}
Вход в полноэкранный режим Выход из полноэкранного режима

Оптимизация заключается в использовании цикла while, который завершается, как только answer имеет значение.

Но путь настолько короткий, что алгоритм все равно завершается почти мгновенно с правильным ответом, сохраненным в качестве первого элемента в answer!

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

  • Я решил обе части!
  • Я использовал такие инструменты, как reduce(), Set()s, switch statements, array manipulation methods, Math и array destructuring!
  • Я сохранил свою серию из 2 звезд — за исключением 11-го дня — с 22-го дня!

Итоги года

  • Заработано 43 звезды: 2-й лучший год!
  • 21 день с двумя звездами
  • 1 день с одной звездой
  • 3 дня с нулевой звездой
  • Построено 2 тренажера (самый низкий показатель, но, к сожалению, очень мало визуально-интерактивных головоломок)
  • Создано бесчисленное количество GIF-файлов

Моя карта в основном освещена:

Мои подсчеты звезд до конца этого года:
232/300 возможных звезд на данный момент: 77% — это все еще проходной балл: C+!

Я так рад, что дошел до последнего — самого раннего? — года.

Но мне грустно, что у меня осталось всего 25 головоломок…

…то есть до декабря этого года! Я надеюсь!

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