<< Пред. След. >>

Вызов

Теперь, когда Санта наконец понял, как попасть в свое настоящее хранилище, он понимает, что эльфы каким-то образом оказались там перед ним и украли некоторые из его подарков! Они еще не выяснили, как покинуть хранилище, поэтому Санта должен попытаться поймать их всех. У Санты и эльфов есть бесконечная энергия, чтобы бегать, но, к сожалению, у эльфов есть более высокая бесконечность энергии, поэтому, если они в конечном итоге будут бегать петлями повсюду, эльфы освободятся.

Дан график nузлов иe ребер с обходом, существующим между любыми двумя узлами, и позициями эльфов и Санты, определите, сколько эльфов Санта может поймать, прежде чем он устанет.

Погоня пошаговая. Каждый цикл, эльфы сначала двигаются одновременно (они могут перемещаться друг к другу и на один и тот же узел), а затем Санта будет двигаться. Если Санта переходит на тот же узел, что и эльф, то он поймал этого эльфа. Каждый эльф может двигаться только от одного узла к соседу за один шаг. Поначалу то же самое касается Санты, но на каждого пойманного им эльфа Санта может сделать один дополнительный шаг. Таким образом, если Санта поймал эльфа, он может перейти от узла к соседу соседа. Это означает, что он может перейти к узлу, а затем обратно. Тем не менее, поскольку Санта бежит слишком быстро в течение этого периода времени, он не поймает эльфов, которые проходят на промежуточных этапах (поэтому, если он находится на A, A подключен к B, B подключен к C, есть эльф на B, а Санта уходит от A -> B -> C, эльф еще не пойман). Тем не менее, Санта не должен делать столько шагов одновременно; он перемещается на 1 + (количество пойманных эльфов) каждый ход.

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

Все сущности (эльфы, Санта) будут в начале на разных узлах.

Технические характеристики и правила

Ваша программа теоретически должна работать для ввода любого размера. Ввод будет представлен в виде графика, положения эльфов и положения Санты. Вы можете взять график в любом приемлемом формате (список узлов + список ребер, список ребер, матрица смежности, циклическая запись и т. Д.), И вы можете занять позиции в любом приемлемом формате, который работает с вашим форматом ввода графа (индекс в списке узлов и т. д.). Выходными данными должно быть одно положительное целое число, указывающее максимальное количество эльфов, которых Санта может поймать.

Тестовые случаи

Они приведены в виде списков ребер и номеров узлов для позиций.

Input -> Output
[(0, 1), (1, 2)], [0, 2], 1 -> 2 # Easy win for Santa, the elves get themselves caught :P
[(0, 1), (1, 2), (2, 3), (3, 0)], [0, 1], 2 -> 2 # The elf opposite of Santa cannot escape but the other one can always just run away each turn, until Santa catches the first elf. Then he can easily just catch the rest.
[(0, 1), (1, 2), (2, 3), (3, 0)], [1], 0 -> 0 # Santa will never catch up
[(0, 1), (1, 2), (2, 3), (3, 0), (1, 4), (4, 5), ..., (10, 11), (11, 3)], [2, 6], 0 -> 2 # The first elf moves to either 1 or 3 and then gets caught. Then, Santa can use his 2-step move to catch up to the second elf no matter what.

^{Я думаю, что Санта не может поймать ни эльфов, ни всех эльфов, так что этот вызов может быть просто подсказкой «может ли он поймать эльфа»}

правила

• Применяются стандартные лазейки
• Это Код-гольф вызов, поэтому выигрывает самый короткий ответ в байтах
• Ответы не принимаются

Счастливого гольфа!

^{Примечание: я черпал вдохновение для этой серии испытаний из Advent Of Code . У меня нет связи с этим сайтом}

Вы можете увидеть список всех испытаний в серии, посмотрев раздел «Связанные» первой задачи здесь .

Wolfram Language (Mathematica) , 129 байт

Block[{a=#},Clear@f;s_~f~e_:=If[s==e,1,s~f~e=0;s~f~e=Min[(hMax[#~f~h&/@a@s,Boole[h==s]])/@a@e]];Tr[Max[(e#3~f~e)/@#2]^#2]]&

Попробуйте онлайн!

Аналогичный подход к моему ответу на этот вопрос .

Функция принимает в качестве входных данных 3 аргумента: список смежности, представленный в виде ассоциации ( инструмент для генерации списка смежности из списка ребер ), позиция эльфов и позиция Санты.

Обратите внимание, что Clear[f]это необходимо, потому что представления функций должны быть многоразовыми.

Код ниже - это код без правил с частичным объяснением. Больше объяснений позже.

reverseBoole = # != 0 &

(* Or@@{a, b} === reverseBoole[booleOr[Boole[{a, b}]]] *)
booleOr = Max

booleAnd = Min

(* Boole@f[s, e] = Santa can catch Elf ? *)

mainfunc = Block[{adjlist = #},
  Clear[f];
  f[s_, e_] := If[ s == e, f[s, e] = 1,
    f[s, e] = Boole[False];
    f[s, e] = booleAnd[
      (e1  booleOr[
        ( s1  f[s1, e1] ) /@ adjlist[s],
        Boole[e1 == s]
      ]) /@ adjlist[e]
    ]
  ];
  If [ 0 == booleOr[ ( e  f[#3, e] ) /@ #2 ] , 0, Length[#2] ]
]&