пс. ищите все другие мои решения проблем Advent of Code здесь.

День 19

Подробности челленджа смотрите здесь.

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

Чтобы понять вышеизложенное, посмотрите видео на YouTube в разделе ссылок ниже.

Часть 2

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

Например, с пятью эльфами (снова пронумерованными от 1 до 5):

  • Эльфы сидят в кругу; Эльф 1 ходит первым:
1
5   2
 4 3
  • Эльфы 3 и 4 расположены поперек круга; Подарок Эльфа 3 украден, он
    слева. Эльф 3 выходит из круга, а остальные эльфы входят:
1           1
5   2  -->  5   2
 4 -          4
  • Эльф 2 крадет у Эльфа прямо через круг, Эльф 5:
1         1 
-   2  -->     2
  4         4
  • Next is Elf 4 who, choosing between Elves 1 and 2, steals from Elf 1:
-          2  
    2  -->
 4          4
  • Наконец, Elf 2 крадет у Elf 4:
2
    -->  2  
 -

Итак, с пятью эльфами эльф, который сидит в начале позиции 2, получает все
подарки.

Учитывая количество эльфов, указанное в вашей головоломке, какой из эльфов теперь получит все
подарки?

Я не знаю об этой вариации задачи Иосифа Флавия, но готов поспорить, что в результатах, аналогичных результатам в части 1, будет какая-то закономерность, поэтому я собрал решение для динамического программирования, чтобы получить некоторые результаты. (ps. решение недостаточно хорошо для ввода, так как возврат займет слишком много времени)

С помощью этого я вижу появляющуюся закономерность:

n : ответ

1 : 1
2 : 2
3 : 3
4 : 1
5 : 2
6 : 3
7 : 5
8 : 7
9 : 9
10 : 1
11 : 2
12 : 3
13 : 4
14 : 5
15 : 6
16 : 7
17 : 8
18 : 9
19 : 11
20 : 13
21 : 15
22 : 17
23 : 19
24 : 21
25 : 23
26 : 25
27 : 27
28 : 1
29 : 2
30 : 3

…

  • где n — степень числа 3, тогда ответ сам по себе
  • иначе n может быть выражено как m + l, где m степень числа 3
  • где l ‹= m (например, n = 5 = 3 + 2, где m = 3 и l = 2), тогда ответ просто l
  • иначе ответ будет m + (l — m) * 2 (например, n = 7 = 3 + 4, где m = 3 и l = 4 и m + (l — m) * 2 = 5)

Ссылки