13
\$\begingroup\$

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.

Test cases

[In]:  1
[Out]: 0

[In]: 1010101
[Out]: 1

[In]: 101011
[Out]: 3

[In]: 1011001101110001101011100
[Out]: 5
```
\$\endgroup\$
4
  • 5
    \$\begingroup\$ For the last test case, I get 1011001101110001101011100 -> 1101010011110 -> 1000110 -> 001 -> 01. \$\endgroup\$
    – Nitrodon
    Dec 9, 2022 at 23:01
  • 8
    \$\begingroup\$ If 1 is 1, then shouldn't 101011 be 3, not 2? It has 3 levels of indendation. Similarly, it seems like 1010101 must be 1, as it must be at least 1 greater than 1, which is already uninterleaved. \$\endgroup\$
    – Jonah
    Dec 10, 2022 at 1:31
  • \$\begingroup\$ oopps. @Jonah since there already are many answers, would it make it better if I change 1 to 0? Or should I increment the other examples? (I did the former for now) \$\endgroup\$
    – math scat
    Dec 10, 2022 at 6:57
  • \$\begingroup\$ I think your fix is good, thanks \$\endgroup\$
    – Jonah
    Dec 10, 2022 at 7:03

14 Answers 14

8
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ 41 bytes: f=lambda s,x=1:s[x:]!=s[:-x]and-~f(s,x*2) \$\endgroup\$ Dec 10, 2022 at 6:20
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 29 21 bytes

W⊙Eθ✂θλLθX²ⅈ‹⌊κ⌈κM→Iⅈ

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.

W⊙Eθ✂θλLθX²ⅈ‹⌊κ⌈κ

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

M→

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.

Iⅈ

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice way to find the return condition with {*e}! Converting this to a regular function can shave off 6 bytes: def f(e):return 0if len({*e})<2else max(f(e[::2]),f(e[1::2]))+1 \$\endgroup\$ Dec 12, 2022 at 14:47
  • 1
    \$\begingroup\$ @GandhiGandhi good tip about saving bytes, but your tip actually works better with a lambda function \$\endgroup\$
    – jezza_99
    Dec 12, 2022 at 19:02
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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

enter image description here

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.