Necklace splitting problem

Question

Background

I was inspired by 3Blue1Brown's recent video about the necklace splitting problem (or as he calls it, the stolen necklace problem) and its relationship to the Borsuk-Ulam theorem.

In this problem, two thieves have stolen a valuable necklace consisting of several different types of jewels. There are an even number of each type of jewel and the thieves wish to split each jewel type evenly amongst the two of them. The catch is that they must do so by splitting the necklace into some number of contiguous segments and distribute the segments between the two of them.

Here is an example with four jewel types denoted S, E, D, and R (for sapphire, emerald, diamond, and ruby, respectively). Let's say the necklace is as follows:

[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]

There are 8 sapphires, 10 emeralds, 4 diamonds, and 6 rubies. We can split the necklace as follows:

[[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]]

Then if we give the first, third, and fifth segments to one thief and the second and fourth segments to the other thief, each will end up with 4 sapphires, 5 emeralds, 2 diamonds, and 3 rubies:

[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],

Using 0-indexing, these cuts occur at the indices [1,2,9,22].

Goal

It turns out that such a fair division can always be done using at most n cuts, where n is the number of jewel types. Your task is to write a complete program or function which takes a necklace as input and outputs a minimal such division (fewest number of cuts).

Input

Input may be in any convenient format. The necklace should be a sequence of jewels and nothing more; e.g. a list of integers, dictionary with keys representing the jewel types and values being lists of indices. You may optionally include the length of the necklace or the number of distinct jewel types, but you should not take any other input.

You may assume that the input necklace is valid. You do not need to handle the case where there is an odd number of jewels of a given type or the necklace is empty.

Output

Again, output may be in any convenient format; e.g. a list of segments, a list of cut positions, a dictionary with keys representing the two thieves and values being lists of segments, etc. Segments may be represented by their starting index, ending index, list of consecutive indices, list of jewels, their lengths, etc. You may use 0- or 1- indexing. If the ordering is not significant to your format, then your output may be in any order. Here is the above output in several different formats:

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)]}

Note that order is important in the list of segments (segments alternate between the thieves) and the list of lengths (in order to identify the segments), but not in the list of cuts or the dictionary. Edit: Greg Martin pointed out that these wouldn't be valid outputs since a fair division can be obtained in two cuts

Test cases

[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]]

Notes

1. Standard loopholes are forbidden.
2. This is code-golf; shortest answer (in bytes) wins.

Answer 1

Brachylog, 13 bytes

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

Try it online!

Note: the metapredicate ᵛ is newer than this challenge.

Explanation

~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.

The partitions are enumerated in increasing order of the number of blocks, so the result will have as few blocks as possible.

Answer 2

Jelly, 18 bytes

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

Try it online!

Not efficient - the example has 28 jewels which wont work without huge resources since this implementation's first step would be to build a list of the 2²⁷ possible partitions.

Returns a list of lists - the segments in the order to dish them out between alternate thieves. (Re the TIO output: when a list only has a single item the implicit print does not bother with the brackets, [])

How?

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)

Answer 3

Mathematica, 118 bytes

Almost beat Jelly ... just 1 off ;)

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

Pure function taking three arguments: the necklace, as a list of tokens such as {A, A, A, A, B, C, D, B, C, D, B, B}; the length of the necklace; and the number of distinct jewel times. It returns a list of sublists in the form {{A, A}, {-A, -A, -B, -C, -D, -B}, {C, D, B, B}}, where the tokens without negative signs go to one thief and the tokens with negative signs go to the other thief. (While this is redundant information, the algorithm leads to this representation, and removing the negative signs would cost several bytes.)

First we have to implement a function that takes a list and a set of n cut-places and returns the list of n+1 sublists obtained by cutting the input list at those n cut-places; the binary infix operator ± is used for this purpose, and defined recursively through l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};. Because of the negative sign right after Append, the result is that the sublists alternately do and do not have negative signs attached to each token.

Then we generate all possible cut-place sets whose length is at most the number of jewel types, using Range@#2~Subsets~#3, and use i=#;(i±#)&/@ to apply the ± operator (with the input list of jewels) to each of these cut-place sets in turn.

Finally, SelectFirst[...,Tr[Tr/@#]==0&]& picks out the first of the resulting necklace divisions that is fair. It does so by literally adding up all of the elements in all of the sublists; Mathematica is wise enough to cancel the positive and negative copies of each token in the obvious way.

Answer 4

Pyth, 16 bytes

hfqFSMsM.TcT2t./

Try it online: Demonstration or Test Suite

Explanation:

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

Answer 5

05AB1E, 14 bytes

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

Try it online or verify all test cases.

Explanation:

.œ                # 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]]