Фон

Я был вдохновлен недавним видео 3Blue1Brown о проблеме расщепления ожерелья (или, как он это называет, о проблеме украденного ожерелья) и ее связи с теоремой Борсука-Улама .

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

Ниже приведен пример с четырьмя типами драгоценностей , обозначенных S, E, Dи R(для сапфир, изумруд, алмаз, рубин и, соответственно). Допустим, ожерелье выглядит следующим образом:

[S,S,S,E,S,D,E,R,S,R,E,S,S,S,D,R,E,E,R,E,D,E,R,R,D,E,E,E]

Есть 8сапфиры, 10изумруды, 4бриллианты и 6рубины. Мы можем разделить ожерелье следующим образом:

[[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]

Затем, если мы передадим первый, третий и пятый сегменты одному вору, а второй и четвертый сегменты - другому вору, каждый из них получит 4сапфиры, 5изумруды, 2бриллианты и 3рубины:

[S],    [S,E,S,D,E,R,S],                            [R,R,D,E,E,E]
    [S],                [R,E,S,S,S,D,R,E,E,R,E,D,E],

Используя 0-indexing, эти сокращения происходят по индексам [1,2,9,22].

Цель

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

вход

Ввод может быть в любом удобном формате. Ожерелье должно быть последовательностью драгоценных камней и ничего более; например, список целых чисел, словарь с ключами, представляющими типы драгоценных камней, и значения, являющиеся списками индексов. При желании вы можете указать длину ожерелья или количество различных типов драгоценных камней, но вы не должны принимать никаких других данных.

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

Выход

Опять же, вывод может быть в любом удобном формате; например, список сегментов, список позиций выреза, словарь с ключами, представляющими двух воров, и значениями, являющимися списками сегментов, и т.д. Сегменты могут быть представлены их начальным индексом, конечным индексом, списком последовательных индексов, списком драгоценных камней, их длина и т. д. Вы можете использовать 0или 1индексировать. Если порядок не имеет значения для вашего формата, то ваш вывод может быть в любом порядке. Вот вышеупомянутый вывод в нескольких различных форматах:

list of segments: [[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]
list of cuts:     [1,2,9,22]
list of lengths:  [1,1,7,13,6]
dictionary:       {'thief1' : [(R,R,D,E,E,E),(S),(S,E,S,D,E,R,S)], 'thief2' : [(S),(R,E,S,S,S,D,R,E,E,R,E,D,E)]}

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

Контрольные примеры

[1,2,1,2,1,3,1,3,3,2,2,3] -> [[1,2,1],[2,1,3,1],[3,3,2],[2,3]]
[1,1,1,1,2,2,3,3,3,3,3,3] -> [[1,1],[1,1,2],[2,3,3,3],[3,3,3]]
[1,1,1,1,1,1,1,1,1,1,1,1] -> [[1,1,1,1,1,1],[1,1,1,1,1,1]]
[1,1,1,1,2,3,4,2,3,4,2,2] -> [[1,1],[1,1,2,3,4,2],[3,4,2,2]]

Примечания

1. Стандартные лазейки запрещены.
2. Это код-гольф ; кратчайший ответ (в байтах) выигрывает.

Брахилог , 13 байт

~c.ġ₂z₁Ċcᵐoᵛ∧

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

Примечание: метапредикат ᵛновее этой задачи.

объяснение

~c.ġ₂z₁Ċcᵐoᵛ∧  Input is a list, say L = [1,2,2,2,1,2,3,3]
~c.            Output is a partition of the input: [[1,2,2],[2,1,2],[3],[3]]
  .ġ₂          Split the output into chunks of length 2: [[[1,2,2],[2,1,2]],[[3],[3]]]
     z₁        Zip (transpose) the chunks: [[[1,2,2],[3]],[[2,1,2],[3]]]
       Ċ       This is a 2-element list (forbid the trivial partition).
        cᵐ     Concatenate both: [[1,2,2,3],[2,1,2,3]]
          oᵛ   If you sort both lists, they are equal.
            ∧  Don't unify with the output.

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

Желе , 18 байт

s2ZFṢ$€E¬,L
ŒṖṖÇÞḢ

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

Не эффективно - пример имеет 28 драгоценных камней , которые не будут работать без огромных ресурсов , так как первый шаг этой реализации было бы построить список из 2 ²⁷ возможных разбиений.

Возвращает список списков - сегменты для того, чтобы разделить их между альтернативными ворами. (Относительно вывода TIO: когда список содержит только один элемент, неявная печать не затрагивает скобки, [])

Как?

s2ZFṢ$€E¬,L - Link 1, get (isUnfair, Slices): A possible partition
s2          - split into slices of length 2 (any odd one on it's own at the end)
  Z         - transpose (first item is one thief's slices, second is the others)
     $€     - last two links as a monad for €ach
   F        -     flatten
    Ṣ       -     sort
       E    - equal? (theif1's jewels == theif2's jewels)
        ¬   - not
          L - length (number of slices in the partition)
         ,  - pair

ŒṖṖÇÞḢ - Main link: necklace
ŒṖ     - all partitions
  Ṗ    - pop, we must remove the rightmost one...
              because Link 1 will say it is fair, and it will have length 1!
              (a list of one thing has all entries equal)
    Þ  - sort by
   Ç   -     last link (1) as a monad
     Ḣ - head (get the first one, i.e. minimal isUnfair, then minimal length)

Mathematica, 118 байт

Почти победил желе ... только 1;)

SelectFirst[l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};i=#;(i±#)&/@Range@#2~Subsets~#3,Tr[Tr/@#]==0&]&

Чистая функция, принимающая три аргумента: ожерелье, как список токенов, таких как {A, A, A, A, B, C, D, B, C, D, B, B}; длина ожерелья; и количество отдельных драгоценностей раз. Возвращает список подсписков в форме {{A, A}, {-A, -A, -B, -C, -D, -B}, {C, D, B, B}}, в которой токены без отрицательных знаков идут одному вору, а токены с отрицательными знаками - другому вору. (Хотя это избыточная информация, алгоритм приводит к такому представлению, и удаление отрицательных знаков будет стоить несколько байтов.)

Сначала мы должны реализовать функцию, которая принимает список и набор nвырезок и возвращает список n+1вложенных списков, полученных путем вырезания входного списка в этих nвырезанных местах; двоичный инфиксный оператор ±используется для этой цели и рекурсивно определяется через l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};. Из-за отрицательного знака сразу после Appendэтого, в списках поочередно есть отрицательные знаки, прикрепленные к каждому токену.

Затем мы генерируем все возможные наборы вырезов, длина которых не превышает количество типов драгоценных камней, используя Range@#2~Subsets~#3и i=#;(i±#)&/@применяя ±оператор (с входным списком драгоценных камней) к каждому из этих наборов вырезов по очереди.

Наконец, SelectFirst[...,Tr[Tr/@#]==0&]&выбирает первое из полученных делений ожерелья, которое справедливо. Это достигается путем буквального суммирования всех элементов во всех подсписках; Mathematica достаточно мудра, чтобы отменить положительные и отрицательные копии каждого токена очевидным образом.

Pyth, 16 байт

hfqFSMsM.TcT2t./

Попробуйте онлайн: демонстрация или тестовый набор

Объяснение:

hfqFSMsM.TcT2t./Q   implicit Q (=input) at the end
              ./Q   create all partitions of the input list 
                    (they are already sorted by number of cuts)
             t      remove the partition with zero splits
 f                  filter for partitions T, which satisfy:
          cT2          chop into pieces of length 2
        .T             transpose to get the pieces of each thieve
    SMsM               combine all pieces for each thieve and sort the results
  qF                   check if they got the same jewels
h                   print the first such partition

05AB1E , 14 байтов

.œ¨ʒ2ôζε˜{}Ë}¤

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

.œ                # All partitions of the (implicit) input
                  #  i.e. [2,3,2,1,3,1]
                  #   → [[[2],[3],[2],[1],[3],[1]],[[2],[3],[2],[1],[3,1]],
                  #      ...,[[2,3,2,1,3,1]]]
  ¨               # Remove the last one
   ʒ        }     # Filter this list by:
    2ô            # Split it into parts of 2
                  #  i.e. [[2,3],[2],[1],[3,1]] → [[[2,3],[2]],[[1],[3,1]]]
                  #  i.e. [[2,3,2],[1,3],[1]] → [[[2,3,2],[1,3]],[[1]]]
      ζ           # Swap rows and columns (using space as filler if necessary)
                  #  i.e. [[[2,3],[2]],[[1],[3,1]]] → [[[2,3],[1]],[[2],[3,1]]]
                  #  i.e. [[[2,3,2],[1,3]],[[1]]] → [[[2,3,2],[1]],[[1,3]," "]]
       ε  }       # Map each inner list to:
        ˜         # Flatten the list
                  #  i.e. [[2,3],[1]] → [2,3,1]
                  #  i.e. [[1,3]," "] → [1,3," "]
         {        # Sort the list
                  #  i.e. [2,3,1] → [1,2,3]
                  #  i.e. [1,3," "] → [1,3," "]
           Ë      # Check if both sorted lists are equal
                  # (if not, remove them from the partitions)
             ¤    # After filtering, take the last one as result (and output implicitly)
                  #  i.e. [[[2],[3,2],[1,3],[1]],[[2,3],[2],[1],[3,1]]]
                  #   → [[2,3],[2],[1],[3,1]]