Четырехмерное приключение


Адвент кода 2018 День 25

Задача: Решите задачу X, где…

Часть 1

X = the number of constellations formed by the fixed points in spacetime
Войдите в полноэкранный режим Выход из полноэкранного режима

Пример ввода

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

Представляет:

  • Список фиксированных точек в пространстве-времени
  • Набор четырехмерных координат

Часть 1

  1. Понимание правил
  2. Анализ примера 1
  3. Анализ примера 2
  4. Анализ примера 3
  5. Анализ примера 4
  6. Повторный анализ примера 3
  7. Уже обеспокоены производительностью
  8. Написание удивительно работающего алгоритма!

Понимание правил

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

  1. Их манхэттенское расстояние друг от друга не больше 3 (оно же меньше или равно 3).
  2. между ними может образоваться цепочка точек, каждая из которых находится на расстоянии не более 3 от предыдущей.

Правило 2 является интересным. Если сказать по-другому:

Если точка находится достаточно близко к созвездию, она «присоединяется» к этому созвездию.

Анализ примера 1

Здесь снова приведен список фиксированных точек:

 0,0,0,0
 3,0,0,0
 0,3,0,0
 0,0,3,0
 0,0,0,3
 0,0,0,6
 9,0,0,0
12,0,0,0
Войти в полноэкранный режим Выйти из полноэкранного режима

Как указано в инструкции:

Первые шесть точек образуют единое созвездие: 0,0,0,0 находится на расстоянии ровно 3 от следующих четырех, а точка 0,0,0,6 связана с остальными, находясь на расстоянии 3 от 0,0,0,3, которая уже находится в созвездии.

Похоже, что это точки отсчета и правила, передаваемые для первых шести точек:

 0,0,0,0 Source: forms constellation A
 3,0,0,0 Passes Rule 1 compared to Source
 0,3,0,0 Passes Rule 1 compared to Source
 0,0,3,0 Passes Rule 1 compared to Source
 0,0,0,3 Passes Rule 1 compared to Source
 0,0,0,6 Passes Rule 2 compared to prior fixed point
 9,0,0,0 Fails both rules compared to all prior points: forms constellation B
12,0,0,0 Passes Rule 1 compared to prior fixed point
Войти в полноэкранный режим Выйти из полноэкранного режима

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

Анализ примера 2

Вот список фиксированных точек:

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

Попытка вручную определить созвездия:

1. -1,2,2,0   Passes Rule 1 compared to fourth point: B
2.  0,0,2,-2  Passes Rule 1 compared to third point: A
3.  0,0,0,-2  Passes Rule 1 compared to second point: A
4. -1,2,0,0   Passes Rule 1 compared to first point: B
5. -2,-2,-2,2 Fails both rules compared to all prior points: D
6.  3,0,2,-1  Passes Rule 1 compared to tenth point: C
7. -1,3,2,2   Passes Rule 1 compared to first point: B
8. -1,0,-1,0  Passes Rule 1 compared to fourth point: B
9.  0,2,1,-2  Passes Rule 1 compared to third point: A
10. 3,0,0,0   Passes Rule 1 compared to sixth point: C
Войти в полноэкранный режим Выйти из полноэкранного режима

Я определил четыре созвездия, что является правильным ответом.

Лучший способ, которым я могу описать свой алгоритм:

For each fixed point X
  For each fixed point Y
    As long as X is not Y (I'm not comparing a point to itself):
      Do both points pass Rule 1?
        Add them both to a new constellation if X is not already in one
        Otherwise, add to the constellation that X is already in
      Else - No points pass Rule 1 when comparing X and Y
        Add X to a new constellation
Войти в полноэкранный режим Выход из полноэкранного режима

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

Анализ примера 3

Вот список фиксированных точек:

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

Попытка вручную определить созвездия:

1.  1,-1,0,1  Passes Rule 1 compared to point 9: A
2.  2,0,-1,0  Passes Rule 1 compared to point 3: B
3.  3,2,-1,0  Passes Rule 1 compared to point 2: B
4.  0,0,3,1   Fails both rules compared to all prior points: D
5.  0,0,-1,-1 Passes Rule 1 compared to point 9: A
6.  2,3,-2,0  Passes Rule 1 compared to point 3: B
7. -2,2,0,0   Fails both rules compared to all prior points: C
8.  2,-2,0,-1 Passes Rule 1 compared to point 9: A
9.  1,-1,0,-1 Passes Rule 1 compared to point 1: A
10. 3,2,0,2   Passes Rule 1 compared to point 3: B
Войти в полноэкранный режим Выход из полноэкранного режима

Это четыре. Правильный ответ — три. Чего мне не хватает?

Когда я распределяю по группам:

2.  2,0,-1,0  Passes Rule 1 compared to point 3: B
3.  3,2,-1,0  Passes Rule 1 compared to point 2: B
6.  2,3,-2,0  Passes Rule 1 compared to point 3: B
10. 3,2,0,2   Passes Rule 1 compared to point 3: B
1.  1,-1,0,1  Passes Rule 1 compared to point 9: A
5.  0,0,-1,-1 Passes Rule 1 compared to point 9: A
8.  2,-2,0,-1 Passes Rule 1 compared to point 9: A
9.  1,-1,0,-1 Passes Rule 1 compared to point 1: A
4.  0,0,3,1   Fails both rules compared to all prior points: D
7. -2,2,0,0   Fails both rules compared to all prior points: C
Войти в полноэкранный режим Выход из полноэкранного режима

Я замечаю, как проходит одно Правило 2:

2.  2,0,-1,0  B
3.  3,2,-1,0  
6.  2,3,-2,0  
10. 3,2,0,2   
1.  1,-1,0,1  A
5.  0,0,-1,-1 Passes Rule 2 compared to point 2: Was A, joins B
8.  2,-2,0,-1 A
9.  1,-1,0,-1 A
4.  0,0,3,1   Fails both rules compared to all prior points: D
7. -2,2,0,0   Fails both rules compared to all prior points: C
Войти в полноэкранный режим Выйти из полноэкранного режима

В результате A и B образуют одно созвездие:

2.  2,0,-1,0  Passes Rule 1 compared to point 3: B
3.  3,2,-1,0  Passes Rule 1 compared to point 2: B
6.  2,3,-2,0  Passes Rule 1 compared to point 3: B
10. 3,2,0,2   Passes Rule 1 compared to point 3: B
1.  1,-1,0,1  Comes with 5 to join B 
5.  0,0,-1,-1 Passes Rule 2 compared to point 2: B
8.  2,-2,0,-1 Comes with 5 to join B
9.  1,-1,0,-1 Comes with 5 to join B
4.  0,0,3,1   Fails both rules compared to all prior points: D
7. -2,2,0,0   Fails both rules compared to all prior points: C
Войти в полноэкранный режим Выйти из полноэкранного режима

И теперь у меня три созвездия!

Но ведь был и более быстрый способ, верно?

1.  1,-1,0,1  Passes Rule 1 compared to point 9: B
2.  2,0,-1,0  Passes Rule 1 compared to point 3: B
3.  3,2,-1,0  Passes Rule 1 compared to point 2: B
4.  0,0,3,1   Fails both rules compared to all prior points: D
5.  0,0,-1,-1 Passes Rule 1 compared to points 2 AND 9: B
6.  2,3,-2,0  Passes Rule 1 compared to point 3: B
7. -2,2,0,0   Fails both rules compared to all prior points: C
8.  2,-2,0,-1 Passes Rule 1 compared to point 9: B
9.  1,-1,0,-1 Passes Rule 1 compared to point 1: B
10. 3,2,0,2   Passes Rule 1 compared to point 3: B
Войти в полноэкранный режим Выйти из полноэкранного режима

Я в недоумении, как это сделать алгоритмически.

Как насчет последнего примера?

Анализ примера 4

Вот список фиксированных точек:

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

Попытка вручную определить созвездия:

1.   1,-1,-1,-2 Fails both rules: A
2.  -2,-2,0,1   Fails both rules: B
3.   0,2,1,3    Fails both rules: C
4.  -2,3,-2,1   Fails both rules: D
5.   0,2,3,-2   Passes Rule 1 compared to point 8: E
6.  -1,-1,1,-2  Passes Rule 1 compared to point 10: F
7.   0,-2,-1,0  Fails both rules: G
8.  -2,2,3,-1   Passes Rule 1 compared to point 5: E
9.   1,2,2,0    Fails both rules: H
10. -1,-2,0,-2  Passes Rule 1 compared to point 5: F
Войти в полноэкранный режим Выход из полноэкранного режима

Я определил восемь созвездий. Это правильный ответ.

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

Мне нужно переделать пример 3.

Повторный анализ примера 3

Попытка вручную правильно определить созвездия за один проход:

1.  1,-1,0,1  Passes Rule 1 compared to point 9: A
2.  2,0,-1,0  Passes Rule 1 compared to point 3: A
3.  3,2,-1,0  Passes Rule 1 compared to point 2: A
4.  0,0,3,1   Fails both rules compared to all prior points: D
5.  0,0,-1,-1 Passes Rule 1 compared to points 2 and 9: A
6.  2,3,-2,0  Passes Rule 1 compared to point 3: A
7. -2,2,0,0   Fails both rules compared to all prior points: C
8.  2,-2,0,-1 Passes Rule 1 compared to point 9: A
9.  1,-1,0,-1 Passes Rule 1 compared to point 1: A
10. 3,2,0,2   Passes Rule 1 compared to point 3: A
Войти в полноэкранный режим Выход из полноэкранного режима

Когда точка проходит Правило 1 относительно двух точек, которые находятся в разных созвездиях, она должна провалиться одна в другую.

Уже беспокоюсь о производительности

  • Я предполагаю, что мой алгоритм будет проверять N^2 точек: 10 точек? 100 проверок, по 10 для каждой точки.
  • 100 — не проблема.
  • Но мой вход имеет 1084 точки
  • 1084^2 = более 1 миллиона
  • Это очень много проверок.
  • Плюс, в каждой проверке будет проделана определенная работа.

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

Мне это не очень нравится.

Но я должен попробовать!

Написание удивительно работающего алгоритма!

До того, как я начал его писать

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

В процессе написания

  • Простая часть: разобрать входные данные в массив массивов, каждый из которых содержит четыре целочисленных значения
  • Мне нужен словарь для хранения точек в качестве ключей и связанных с ними созвездий, которые могут быть просто числами от 0 и больше
  • Нужно ли мне сравнивать все точки друг с другом, или можно двигаться в одном направлении?

Например, должен ли я делать это?

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

Или так?

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

К счастью — с точки зрения производительности — второй подход сработал.

  • Довольно просто: вычисление манхэттенского расстояния каждой точки по сравнению с исходной использует встроенные функции Math.abs() и reduce().

Например:

-2,-2,-2,2
3,0,2,-1

 -2  -2  -2    2
- 3 - 0 - 2 - -1
----------------
  5  -2  -4    3
----------------
  5 + 2 + 4  + 3
----------------
              14
Войдите в полноэкранный режим Выход из полноэкранного режима
  • Мой алгоритм работал в примерах 1 и 2 без необходимости вычисления общего созвездия, что делало ситуацию обманчиво простой.
  • Пример 3 был самым сложным: мне пришлось переработать и расширить логику моего алгоритма, чтобы убедиться, что точки, ранее назначенные одному созвездию, в котором позже появилась точка сопряжения, будут снова назначены другому созвездию.
  • Это потребовало много проб и ошибок, а также изучения того, как правильно использовать Math.min() с массивом.
  • К счастью, мне потребовалось всего две ветви: выполнить одну серию шагов, если нет «групп», и выполнить другую, если они есть
  • Излишне жадный шаг — это когда я перебираю все ключи в моем словаре в попытках переназначить точки на их потенциально новое созвездие.

Письменное описание полного, рабочего алгоритма

Parse the input:
  Split the input at each newline character into a list of strings
  Split each string at each comma character into a list of stringified numbers
  Coerce each string into an integer

Prepare the accumulating values:
- Set c as an empty object - this will store each stringified fixed point and the constellation it is part of
- Set counter to 0 - this will store the next constellation to be formed if a fixed point is outside of the range of any other known constellations

The main loop:
For each fixed point A, except the last one in the list
  Set matches as an empty array
  Set source as the stringified representation of point A
  For each fixed point B, starting with the point after A and never back-checking
    Check for a passing Rule 1 by performing the following operations:
      Calculate the sum of the absolute value of the differences of both integers in the same locations for point A and B
        If the sum is less than or equal to 3
          Add to matches a stringified representation of B's fixed points
  By now, matches will contain each point B that is within a manhattan distance of 3 to point A
  Store in groups an array containing the result of the following operations:
    Start by adding source
    Then add each point in matches
    Then replace each stringified point with the constellation assigned to it's key in the object, c, if any. If none exists, it will be replaced by undefined.
    Then, filter that list of values to remove any that are undefined, leaving only integers 0 or greater.
  If groups is empty, I have identified a fixed point that currently does not fit in any existing constellations. I must create a constellation for it and each of the points that pass Rule 1 compared to it:
    Create a key for it in c using counter as the value
    Create keys for each of the matches, also using counter as the value
    Increment counter by one
  Else, if groups contains at least one non-negative number:
    Set num as the smallest number in groups
    Set (or update) the value associated with point A's key in c to num
    Do the same for each of the matches: setting their associated value as num
    For each key-value pair in c:
      If the value is one of the integers in groups:
        Reassign the value as num

Counting the number of constellations:
Extract the list of all non-zero integer values in c
  Create a set of only the unique values
    Return the size of the set
Вход в полноэкранный режим Выход из полноэкранного режима

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

Я был удивлен по нескольким причинам:

  • Я НЕ ожидал, что он выдаст правильный ответ на мой вход, так как был уверен, что примеры скрывают какой-то важный крайний случай, найденный в моей головоломке.
  • Я НЕ ожидал, что он будет работать так быстро, как он работает — миллисекунды вместо секунд. Наверное, помогает то, что я не проверяю каждую точку в каждой итерации главного цикла. Наверное, не помогает и то, что я проверяю каждый ключ в словаре.

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

Я так рад, что он сработал!

Часть 2

  • У 25-го дня никогда не было головоломки для части 2.
  • Часть 2 должна мгновенно наградить решателей их 50-й золотой звездой.
  • Однако в этом году в тексте упоминается День 21.
  • А День 21 ссылается на Дни 16 и 19
  • Таким образом, похоже, что в этом году у меня будет еще одна партия головоломок, которые нужно завершить в хронологическом порядке. Радость.

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

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

Облом:

  • Нет симулятора. На мой взгляд, смотреть было бы неинтересно.
  • Нет GIF-файлов. Как бы мне ни хотелось визуально изобразить свой алгоритм, на данный момент я готов перейти к дню 24.

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