CGAC2022 Day 10: Help Santa sort presents!

Question

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.

---

Santa likes to sort his presents in a special way. He keeps "uninterleaving" the pile of presents into smaller sub-piles until each sub-pile is either full of toys or full of coal.
Your job is to, given a pile of presents, determine the maximum number of uninterleavings.

Uninterleaving a pile of presents, (eg. \$1011011\$), means separating every second item and every second + 1 item into its own sub-pile (\$1101\$, \$011\$).

Sorting \$010011100101\$ would be (implies that \$1\$ is a present full of toys and \$0\$ is a present full of coal):

- 010011100101
 - 001100
     - 010
         - 00
         - 1
     - 010
         - 00
         - 1
 - 101011
     - 111
     - 001
         - 01
             - 0
             - 1
         - 0

The answer would be the maximum number of times Santa has to uninterleave the presents (from \$010011100101\$ to \$0\$ or \$1\$), \$4\$.

The shortest code wins. code-golf

Test cases

[In]:  1
[Out]: 0

[In]: 1010101
[Out]: 1

[In]: 101011
[Out]: 3

[In]: 1011001101110001101011100
[Out]: 5
```

Answer 1

J, 34 bytes

1 i.~]*/@(1=#@=/.~)"1(|/~2^])@i.@#

Try it online!

Assuming my comments for test case corrections on the OP are correct, this answer should be right.

This generates "power of 2" masks for grouping the input like:

0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7

It uses each candidate to group the input, and then checks if, using that grouping, we have "pure" coal or present groups. Then it returns the index of the first grouping that works.

Answer 2

Python, 41 bytes (@dingledooper)

f=lambda e,j=1:e[j:]!=e[:-j]and-~f(e,j*2)

Attempt This Online!

Python, 49 bytes

lambda e,j=1:sum(e[j:]!=e[:j-(j:=2*j)]for _ in e)

Attempt This Online!

Brazenly stole @jezza_99's test harness.

How?

Based on the observation that the required split depth equals the number of powers of two j=1,2,4,8,... such that e[j:] != e[:-j].

For example, if j=4 then e[j:] == e[:-j] means precisely that any two characters 4 positions apart must be equal. And the four full chains of such element are exactly the uninterleaved piles after two splits.

Answer 3

Jelly, 15 bytes

WŒœ€ẎQƊƬE€Ạ$€¬S

A monadic Link that accepts a list and yields the maximal number of uninterleavings required to separate the items (works for more than just two categories).

Try it online!

How?

WŒœ€ẎQƊƬE€Ạ$€¬S - Link: list, A
W               - wrap (A)
       Ƭ        - collect up (starting with that) while distinct applying:
      Ɗ         -   last three links as a monad:
   €            -     for each:
 Œœ             -       odd-even (e.g. [1,0,1,0,0] -> [[1,1,0],[0,0]])
    Ẏ           -     tighten
     Q          -     deduplicate
            €   - for each:
           $    -   last two links as a monad:
         €      -     for each:
        E       -       all equal?
          Ạ     -     all?
             ¬  - logical NOT
              S - sum

Answer 4

Charcoal, 29 21 bytes

Ｗ⊙Ｅθ✂θλＬθＸ²ⅈ‹⌊κ⌈κＭ→Ｉⅈ

Try it online! Link is to verbose version of code. Explanation: Now uses @Jonah's observation that the problem is equivalent to finding the smallest power of two count of groups where all of the groups are pure.

Ｗ⊙Ｅθ✂θλＬθＸ²ⅈ‹⌊κ⌈κ

While at least one slice of step 2 to the power the number of iterations contains both toys and coal...

Ｍ→

Increment the number of iterations. (The previous version didn't need the Ｍ because the block meant that it wasn't ambiguous.) Moving the cursor horizontally doesn't change the output since the canvas trims automatically in this case.

Ｉⅈ

Output the number of iterations. Using the X position as the iteration count saves 3 bytes over pushing dummy values to the predefined empty list and 4 bytes over using a counter variable.

Answer 5

Vyxal, 12 9 bytes

E?ẇ∩v≈A)Ṅ

Try it online!

Explanation

Based upon Jonah's observation.

       )  # a lambda taking N:
E         #   2 ** N
 ?        #   push input
  ẇ       #   wrapped in chunks of length 2 ** N
   ∩      #   transposed
    v≈    #   is every element the same? (vectorise)
      A   #   all?
        Ṅ # first non-negative integer where it is true

Answer 6

Python, 69 58 bytes

f=lambda e:0if len({*e})<2else max(f(e[::2]),f(e[1::2]))+1

Attempt This Online!

A recursive function that splits into two branches at each indentation if the pile is not all 0 or 1, and returns the maximum number of indentations from all of the branches.

-11 bytes thanks to @GandhiGandhi

Answer 7

JavaScript (ES6), 71 bytes

f=(a,g=q=>v=new Set(a).size>1&&1+f(a.filter(_=>++q&1)))=>g``<g(1)?v:g``

Try it online!

Or:

f=(a,g=q=>v=/0,1|1,0/.test(a)&&1+f(a.filter(_=>++q&1)))=>g``<g(1)?v:g``

Try it online!

Answer 8

Nibbles, 12.5 10.5 bytes (21 nibbles)

,|`,,$+.`'`/^2$@>>=~

Inspired by Jonah's answer.

,|`,,$+.`'`/^2$@>>=~
 |                          # filter each n in
  `,                        # 0..
    ,$                      #    length of input
          `/                #   get chunks of
               @            #   input
            ^2$             #   of size 2^n,
        `'                  #   transpose,
       .                    #   and map over each group
                  =~        #     collect identical elements into groups
                >>          #     and remove the first group
,                           # finally, get the length

Answer 9

Nekomata, 9 bytes

ˡ{ᵗ≡ĭ?}aṀ

Attempt This Online!

ˡ{ᵗ≡ĭ?}aṀ
ˡ{    }     Loop until failure, and count the number of iterations:
  ᵗ≡            Check that elements in the list are not all equal
    ĭ           Uninterleave
     ?          Choose any of the two lists
       a    All possible values
        Ṁ   Maximum

Answer 10

PARI/GP, 51 bytes

f(a,i=1)=if(i<#a&&a[1+i..-1]-a[1..-i-1],1+f(a,2*i))

Attempt This Online!

A port of @loopy walt's Python answer.

Answer 11

Japt, 13 12 bytes

èø2¤á)©ÒßUcó

Try it

èø2¤á)©ÒßUcó     :Implicit input of (initially singleton) array U
è                :Count the element that
 ø               :  Contain any element of
  2¤             :    2 converted to a binary string
    á            :    Permutations
     )           :End count
      ©          :Logical AND with
       Ò         :Negate the bitwise NOT of
        ß        :A recursive call with argument
         Uc      :  Flat map U
           ó     :    Uninterleave

Answer 12

05AB1E, 12 10 bytes

∞<.Δoι0KSP

o is inspired by @Jonah's J answer.

Try it online or verify all test cases.

∞<.Δ could alternatively be ÅΔIN for the same byte-count:
Try it online or verify all test cases.

Explanation:

∞           # Push an infinite positive list: [1,2,3,...]
 <          # Decrease each by 1 to an infinite non-negative list: [0,1,2,...]
  .Δ        # Pop and find the first which is truthy for:
    o       #  Push 2 to the power this value
     ι      #  Uninterleave the (implicit) input into that many parts
      0KSP  #  Check if each item consists of unique digits (or is empty):
      0K    #   Remove all 0s from the list (including "00","000",etc.)
        S   #   Convert it to a flattened list of digits (also removes empty items)
         P  #   Check if all are 1s by taking the product (only 1 is truthy in 05AB1E)
            # (after which the found result is output implicitly)

Answer 13

JavaScript (Node.js), 46 bytes

a=>(g=i=>a.some((v,j)=>v^a[j%i])&&1+g(2*i))(1)

Try it online!

Bit magic

Answer 14

Scala 3, 120 bytes

A port of @loopy walt's Python answer.

---

def f(a:Seq[Int],i:Int=1):Int=if(i<a.length&& !a.slice(i,a.length).sameElements(a.slice(0,a.length-i)))1+f(a, 2*i)else 0

Attempt This Online!