Advent of Code 2020 D13

День 13 занял у того же товарища, что решает AoC на Zig, чуть более трёх часов (из которых два с половиной часа он решал вторую часть). Я, думая что могу решить быстрее, потратил на попытки сделать это два дня :( В итоге всё равно получается решение «в лоб» и грубой силой.

Часть 1

Приведу текст задачи (часть 1) полностью.

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

К счастью, есть автобусы, которые отвезут вас из морского порта в аэропорт. У каждого автобуса есть номер (ID), который показывает, как часто автобус выезжает в направлении аэропорта.

График движения автобусов определяется меткой времени, которая отмеряет число минут от какой-то отсчётной точки в прошлом. В момент 0 все автобусы отправляются из морского порта одновременно. После этого каждый автобус едет в аэропорт, потом по другим остановкам, и наконец возвращается в морской порт, чтобы продолжать это бесконечно.

Время, которое занимает этот круг, является номером (ID) автобуса: автобус с номером 5 отправляется из морского порта в моменты 0, 5, 10, 15 и так далее. Автобус с номером 11 отправляется в 0, 11, 22, 33 и так далее. Если вы будете там к моменту отправления автобуса, сможете на нём уехать в аэропорт.

Ваши заметки (исходные данные загадки) состоят из двух строк. Первая строка — оценка самого раннего времени (timestamp), когда вы сможете отправиться на автобусе. Вторая строка перечисляет номера автобусов, которые работают согласно данных от компании-перевозчика; записи с меткой x похоже что не работают, так что вы решаете их проигнорировать.

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

К примеру, заметки у вас следующие:

939
7,13,x,x,59,x,31,19

Самая ранняя метка времени, в которую вы сможете уехать — 939, а автобусы на линии — 7, 13, 59, 31 и 19. Рядом с меткой 939, эти автобусы отправляются во время, отмеченное буквой D.

time   bus 7   bus 13  bus 59  bus 31  bus 19
929      .       .       .       .       .
930      .       .       .       D       .
931      D       .       .       .       D
932      .       .       .       .       .
933      .       .       .       .       .
934      .       .       .       .       .
935      .       .       .       .       .
936      .       D       .       .       .
937      .       .       .       .       .
938      D       .       .       .       .
939      .       .       .       .       .
940      .       .       .       .       .
941      .       .       .       .       .
942      .       .       .       .       .
943      .       .       .       .       .
944      .       .       D       .       .
945      D       .       .       .       .
946      .       .       .       .       .
947      .       .       .       .       .
948      .       .       .       .       .
949      .       D       .       .       .

Самый ранний автобус, на которым вы сможете уехать — 59. Он не уедет ранее метки 944, так что потребуется подождать 944 − 939 = 5 минут до отправления. Умножение номера автобуса на число минут ожидания даст 295.

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

Входные данные:

1003055
37,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,433,x,x,x,x,x,x,x,23,x,x,x,x,x,x,x,x,17,x,19,x,x,x,x,x,x,x,x,x,29,x,593,x,x,x,x,x,x,x,x,x,x,x,x,13

Решение, конечно, элементарное: поскольку все автобусы отправляются с заданной периодичностью, равной числу в списке, нужно найти число, у которого разница между самим числом (номером автобуса) и остатком от деления начального времени на этот номер минимальна. То есть, искомое минимальное время равно ID - @mod(Timestamp, ID), где @mod возвращает остаток от деления.

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

while (it.next()) |b| {
   if (std.mem.eql(u8, b, "x")) continue;
   var n = std.fmt.parseInt(usize, b, 10) catch 999999;
   var wait_time = n - @mod(start_time, n);
   if ( wait_time < minutes_wait ) {
      bus_number = n;
      minutes_wait = wait_time;
   }
}

Переходим ко второй части, которая заняла два с половиной часа у стримера.

Часть 2

Компания-перевозчик объявила конкурс: золотую монету тому, кто найдёт самую раннюю отметку времени, чтобы первый автобус отправлялся в это время, и чтобы последующие автобусы отправлялись в соответствующую минуту. (Первая строка исходных данных больше не важна).

К примеру, у вас тот же список автобусов, что и ранее:

7,13,x,x,59,x,31,19

Символ x означает, что ограничений на то, какой автобус отправится, в этом поле нет.

Это значит, что вы ищете самую раннюю метку времени (t), чтобы:

  • Автобус 7 отправлялся во время t.

  • Автобус 13 отправлялся на минуту позже t.

  • На вторую и третью минуты после t ограничения не накладываются.

  • Автобус 59 отправляется на 4 минуты позже t.

  • На пятую минуту после t ограничения не накладываются.

  • Автобус 31 отправляется через шесть минут после t.

  • Автобус 19 отправляется через семь минут после t.

Важны только те автобусы, которые указаны на соответствующих местах (смещениях) после t. Эти автобусы могут отправляться в другое время, и другие автобусы могут отправиться в это время. К примеру, в списке ниже, поскольку автобус 19 должен отправиться через семь минут после отметки времени, в которую отправится 7, автобус 7 также будет отправляться одновременно с автобусом 19 после t.

В этом примере наиболее ранняя отметка времени, в которую это произойдёт, 1068781:

time     bus 7   bus 13  bus 59  bus 31  bus 19
1068773    .       .       .       .       .
1068774    D       .       .       .       .
1068775    .       .       .       .       .
1068776    .       .       .       .       .
1068777    .       .       .       .       .
1068778    .       .       .       .       .
1068779    .       .       .       .       .
1068780    .       .       .       .       .
1068781    D       .       .       .       .   <<<
1068782    .       D       .       .       .
1068783    .       .       .       .       .
1068784    .       .       .       .       .
1068785    .       .       D       .       .
1068786    .       .       .       .       .
1068787    .       .       .       D       .
1068788    D       .       .       .       D
1068789    .       .       .       .       .
1068790    .       .       .       .       .
1068791    .       .       .       .       .
1068792    .       .       .       .       .
1068793    .       .       .       .       .
1068794    .       .       .       .       .
1068795    D       D       .       .       .
1068796    .       .       .       .       .
1068797    .       .       .       .       .

В примере выше, автобус 7 отправится во время 1068788 (через 7 минут после t). Это нормально; единственное требование в том, что 19 должен отправиться в это же время, что и происходит.

Другие примеры:

  • Наиболее ранняя метка времени для 17,x,13,19 — 3417.

  • 67,7,59,61 происходит во время 754018.

  • 67,x,7,59,61 происходит во время 779210.

  • 67,7,x,59,61 происходит во время 1261476.

  • 1789,37,47,1889 происходит во время 1202161486.

Однако, с тем количеством автобусов в вашем списке, самая ранняя метка времени будет больше 100000000000000!

Какая самая ранняя метка времени, в которую все указанные автобусы отправятся в соответствии со своими смещениями в списке?

Исходные данные не изменились.

Я рассуждал так: поскольку первый автобус должен отправиться во время, кратное его номеру (как и все остальные автобусы), то

  • получаем ближайшее кратное первому автобусу и максимально близкое к числу-подсказке 100000000000000, и далее

  • последовательно увеличиваем это кратное на номер этого первого автобуса (проход по кратным значениям) (x);

  • проверяем, кратно ли число x + номер позиции в списке автобусов номеру автобуса на этой позиции.

Если первый автобус отправляется во время t, то следующий автобус по индексу i должен отправиться во время t + i, а число t + i кратно этому номеру автобуса.

Проблема только в том, что без распараллеливания процесса этот подход реализуем только в теории; в один поток это займёт дни — проверено на себе.

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

Разумеется, считать соответствие всех чисел — нерационально. Поэтому на пространстве чисел, кратных наибольшему номеру автобуса, проверяем наличие чисел, кратных меньшему номеру автобуса, и если не кратно — прерываем и переходим к следующему кратному наибольшему номеру:

// от наибольшего номера автобуса к наименьшему
for (list.items[1..]) |item| {
   // текущее число, кратное наибольшему номеру автобуса, уменьшаем на смещение этого наибольшего номера и прибавляем смещение следующего (в сторону уменьшения) номера автобуса; это число кратно следующему по величине номеру автобуса
   var current = @mod(value - list.items[0].index + item.index, item.bus) == 0;
   success = success and current;
   if (!success) break; // если остаток от деления [числа минус смещение плюс смещение нового] не равен нулю, переходим к следующему
}

За пять часов алгоритм проверил числа от 100000000000000 до ≈414148637009525.

Автобусы из исходных данных уезжают…

  • № 37 первым;

  • № 41 через 27 минут;

  • № 433 через 37 минут;

  • № 23 через 45 минут;

  • № 17 через 54 минуты;

  • № 19 через 56 минут;

  • № 29 через 66 минут;

  • № 593 через 68 минут;

  • № 13 через 81 минуту.

После ещё нескольких часов подсчётов я получил число 600691418730595, которое:

  • делится нацело на 37: 600691418730595 % 37 == 0;

  • (600691418730595 + 27) % 41 == 0;

  • (600691418730595 + 37) % 433 == 0;

  • (600691418730595 + 45) % 23 == 0;

  • (600691418730595 + 54) % 17 == 0;

  • (600691418730595 + 56) % 19 == 0;

  • (600691418730595 + 66) % 29 == 0;

  • (600691418730595 + 68) % 593 == 0;

  • (600691418730595 + 81) % 13 == 0.

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

Дополнение

Решение задачи — в китайской теореме об остатках.