21
\$\begingroup\$

In this challenge you will take as input a non-empty list of binary values (these can be booleans or integers on the range 0-1), you should output all the ways to partition the list into non-empty sections such that no two adjacent equal values in the initial list are separated into different sections.

For example if the input is [1,1,0,0,1] then [1,1],[0,0,1] is a valid partition but [1,1,0],[0,1] is not since the adjacent 0s are divided.

This is so the goal is to minimize the size of your source code as measured in bytes.

Test cases

[1,0] ->
  [ [[1,0]]
  , [[1],[0]]
  ]
[1,1,1,1] ->
  [ [[1,1,1,1]]
  ]
[1,1,0,0,1] ->
  [ [[1,1,0,0,1]]
  , [[1,1],[0,0,1]]
  , [[1,1,0,0],[1]]
  , [[1,1],[0,0],[1]]
  ]
\$\endgroup\$
4
  • 9
    \$\begingroup\$ Does the input need to be a list or can it be a string like "11001"? Same question for output, how strict is the formatting here? \$\endgroup\$ Sep 28, 2022 at 17:41
  • \$\begingroup\$ In particular, would an output like 11|001| be valud? \$\endgroup\$
    – xnor
    Sep 30, 2022 at 2:41
  • \$\begingroup\$ Suggest test case [1,1,0,0,1,1,0,0], required me to remove duplicates \$\endgroup\$
    – AZTECCO
    Sep 30, 2022 at 12:47
  • \$\begingroup\$ @CursorCoercer List here just means any list-like container, vectors, arrays etc. are fine, and the characters 0 and 1 are fine as binary values. \$\endgroup\$
    – Wheat Wizard
    Sep 30, 2022 at 15:24

20 Answers 20

8
\$\begingroup\$

K (ngn/k), 22 bytes

{(&'+1,!2-1_=':x)_\:x}

Try it online!

1_=':x For pairs of adjacent values: are they equal?
2- 2 minus that. Gives 2s for the lines between sections and 1s in sections.
! odometer. Returns a matrix with all binary patterns bounded by the vector.
+1, prepend a 1 and transpose to have the binary patterns with leading 1s in the rows.
&' Get indices of 1s for each row.
(...)_\:x For each of those integer vectors, split the input at those indices.

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

Factor + math.combinatorics math.unicode, 81 bytes

[ dup 2 clump [ Σ 1 = ] arg-where 1 v+n all-subsets [ split-indices ] with map ]

Attempt This Online!

  • dup 2 clump [ Σ 1 = ] arg-where 1 v+n get the indices of rising and falling edges
  • all-subsets take all the subsets of that
  • [ split-indices ] with map split the input according to each of these
\$\endgroup\$
5
\$\begingroup\$

Jelly, 8 bytes

ITŒP‘œṖ€

A monadic Link that accepts a list of ones and zeros and yields a list of the valid partitions.

Try it online!

How?

ITŒP‘œṖ€ - Link: list, B  e.g. [0, 0, 1, 1, 0, 1]
I        - deltas (of B)       [  0, 1, 0,-1, 1]
 T       - truthy indices      [     2,    4, 5]
  ŒP     - powerset            [[],[2],[4],[5],[2,4],[2,5],[4,5],[2,4,5]]
    ‘    - increment           [[],[3],[5],[6],[3,5],[3,6],[5,6],[3,5,6]]
       € - for each:
     œṖ  -   partition (B) at  [[[0,0,1,1,0,1]],[[0,0],[1,1,0,1]],[[0,0,1,1],[0,1]],[[0,0,1,1,0],[1]],[[0,0],[1,1],[0,1]],[[0,0],[1,1,0],[1]],[[0,0,1,1],[0],[1]],[[0,0],[1,1],[0],[1]]]
\$\endgroup\$
5
\$\begingroup\$

Curry (PAKCS), 40 bytes

f(a++b:c:d)|b/=c=(a++[b]):f(c:d)
f a=[a]

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Vyxal, 6 bytes

ĠøṖvvf

Try it Online!

Port of @UnrelatedString's Brachylog answer.

\$\endgroup\$
7
  • \$\begingroup\$ How is that useful? is this programming language used anywhere? \$\endgroup\$
    – NotaChoice
    Sep 30, 2022 at 1:42
  • 1
    \$\begingroup\$ @NotaChoice It's only used for golfing (so not really any real-world situations). \$\endgroup\$
    – naffetS
    Sep 30, 2022 at 1:48
  • \$\begingroup\$ You must allow my arrogance, but isn't this then just a waste of time? such a good mind and energy were put together to code such things... I am just surprised since you used 6 bytes why can't you just do with one byte !? \$\endgroup\$
    – NotaChoice
    Oct 3, 2022 at 17:50
  • 1
    \$\begingroup\$ Thank you, that is actually clarifying to me, so your language is designed to be more suitable for the kind of challenges that are typically asked here? One can think of a modeling of such challenges. Then designing a language which will be more suitable for other type of challenges as well, such as, let us say problems from industry! Then you can sell it ! It will dethrone python maybe \$\endgroup\$
    – NotaChoice
    Oct 3, 2022 at 22:41
  • 1
    \$\begingroup\$ I hope you are not mocking me, I am very new to this and I am an advocate for C++ as I like languages that are close to how the 'machine' is functioning. \$\endgroup\$
    – NotaChoice
    Oct 5, 2022 at 13:45
5
\$\begingroup\$

05AB1E, 6 (or 4?) bytes

γ.œ€€˜

Try it online or verify all test cases.

If we can use strings as I/O, this could be 4 bytes instead by replacing €€˜ with J:
Try it online or verify all test cases.

Explanation:

γ       # Split the (implicit) input-list into groups of equal adjacent values
 .œ     # Get all partitions of these groups
   €    # For each partition:
    €   #  For each part of groups within a partition:
     ˜  #   Flatten the part of groups to a single list
        # (or alternatively:)
   J    # Join each list/part of groups within each partition together
        # (after which the result is output implicitly)
\$\endgroup\$
4
\$\begingroup\$

Brachylog, 5 bytes

ḅ~ccᵐ

Try it online!

Takes a list through the input variable and generates a list of lists of lists through the output variable.

ḅ        Partition into runs of consecutive equal elements.
 ~c      Take an arbitrary partition of the list of runs,
   cᵐ    and concatenate each slice.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Well played! I know I've used ~c before, but it didn't even cross my mind this time. :P \$\endgroup\$
    – DLosc
    Sep 29, 2022 at 1:06
3
\$\begingroup\$

Brachylog, 20 bytes

Ė!|ḅa₀cPl;?b₍↰;Pgᵗ↔c

A predicate that takes a list of 0's and 1's as input and outputs each possible partition one after another.

Try it online!

Explanation

This seems way too long.

Ė!|ḅa₀cPl;?b₍↰;Pgᵗ↔c
Ė!                    Either the input is an empty list (in which case return empty list)
  |                   Or, take the input and...
   ḅ                  Partition into blocks of equal elements
    a₀                Get a prefix of that list of blocks
      c               Flatten it
       P              Call that list P
        l             Take its length
         ;?b₍         The original input with that many elements removed from the front
             ↰        Recurse (returns a list of lists)
              ;P      Pair with P
                gᵗ    wrapped in a list
                  ↔   Reverse the order of the pair
                   c  Flatten once
\$\endgroup\$
1
3
\$\begingroup\$

Prolog (SWI), 65 bytes

Q+[E|F]:-append(A,[B,C|D],Q),B\=C,append(A,[B],E),[C|D]+F.
Q+[Q].

Try it online!

Similar to @alephalpha's Curry answer. Outputs as a list of choicepoints.

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

J, 27 bytes

<;.1~1,.[:(#:[:i.*/)2-2=/\]

Try it online!

-1 bytes thanks to the "2 minus" trick stolen from ovs's answer

Say we have, eg, 1,1,0,0,1 -- then we have 2 "change points" and 4 possible combos. This is essentially just the problem of listing:

0 0 
0 1
1 0
1 1

except we want that that list to be embedded in the Xs of this list:

0 X 0 X

The key insight is that this is 0..3 converted using the mixed base number 1 2 1 2. After that we just cut the original input using our 4 lists, with a 1 prepended to each.

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

Jelly, 7 bytes

Ir0Œpk€

Try it online!

Inspired by Jonathan Allan's solution.

I          Get the forward differences of the list.
     k     Partition the list after each truthy position
      €    of each element of
   Œp      the Cartesian product of
 r0        the ranges from each difference to 0 inclusive.

Jelly, 7 bytes

ŒgŒṖẎ€€

Try it online!

Port of my Brachylog solution.

Œg         Partition into runs of consecutive equal elements.
  ŒṖ       Generate every partition of the runs,
    Ẏ€€    and concatenate the runs in each slice.
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 28 bytes

(.),(?!\1)
$1#
+%1`#
;$'¶$`,

Try it online! Link includes test cases. Outputs semicolon-delimited lists. Explanation:

(.),(?!\1)
$1#

Find all acceptable cutting points.

+

Loop until each cutting point has been processed.

%

Loop over each partially cut list.

1`

Only process the first remaining cutting point on each pass.

#
;$'¶$`,

Create two lists, one cut at that point, one not cut at that point.

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

Perl 5, 80 bytes

sub{@p=pop=~/0+|1+/g;$s="@p";map$s=~s, ,$r=$_%2?$&:'';$_/=2;$r,ger,0..2**@p/2-1}

Try it online!

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

Knight (v2), 125 bytes

;=lL=p+=a@P;W=l-lT|?Gp lT Gp-lT1=a+a,l;=n^2LaW+1=n-nT;=x!=b+=o@p;=kLa;W+=k-kT1&%/n^2k 2;=o+o,GbF=d+~x=x[Ga kT=bSbFd@;D+o,bO''

Try it online!

Input as a binary string. Outputs each partition on a separate line.

This probably is not even the golfiest strategy lol, but whatever. The general strategy is to construct a list a that contains the possible indexes that can be cut at (the easy part), then enumerate over all possible combinations of cuts using a (the annoying as f*** part).

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

Haskell, 94 bytes

import Data.List
f l=nub[w|w<-subsequences[id=<<x|x<-tails=<<(inits.group)l,x>[]],(w>>=id)==l]

Try it online!

Corrected as x specifications.

Thanks to @Wheat Wizard for saving some bytes using id=<<x instead of concat.

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

Charcoal, 45 bytes

⊞υ⟦A⟧FυF…ι¹F²F⁺¹⌕A⪫κω⁺Iλ¬λ⊞υ⁺⟦…κμ✂κμ⟧ΦιξEυ⭆¹ι

Try it online! Link is to verbose version of code. Explanation:

⊞υ⟦A⟧

Start with the original list, which is always a valid partition.

Fυ

Loop over the partitions found so far.

F…ι¹

Loop over the lists in the current partition, but stop after the first. (This is a sneaky way of getting the first list into a variable.)

F²

Loop over the possible first bits of a cutting point.

F⁺¹⌕A⪫κω⁺Iλ¬λ

Loop over all of the possible cutting points that start with that bit. The cutting point is in between the bits, thus the extra 1 added to the positions. (Incremented works on empty lists in the newer version of Charcoal on ATO which would save a byte.)

⊞υ⁺⟦…κμ✂κμ⟧Φιξ

Cut the first list of the partition at that point and push the resulting partition to the list of partitions where it will be reevaluated for cutting.

Eυ⭆¹ι

Pretty-print all of the found partitions.

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

Pyth, 11 10 bytes

mmrk9d./r8

Try it online!

Explanation

        r8    length encode the implicitly evaluated input
      ./      get all partitions
mmrk9d        map length decoding to each partition element
\$\endgroup\$
1
\$\begingroup\$

Python, 230 bytes

from itertools import*
import re
def f(M):L=re.split(r'((.)\2*)',''.join(map(str,M)))[1::3];l=len(L);I=[*range(1,l)];return[[M]]+[[[int(c)for c in''.join(L[i:j])]for i,j in pairwise([0,*P,l])]for s in I for P in combinations(I,s)]

Attempt This Online!

Python 3.10+ required for pairwise.

for [1,1,0,0,1] returns:

[[[1, 1, 0, 0, 1]],
 [[1, 1], [0, 0, 1]],
 [[1, 1, 0, 0], [1]],
 [[1, 1], [0, 0], [1]]]

ungolfed:

from itertools import *
import re
def f(M):
  # produce ['11', '00', '1'] by splitting on regex which checks 2 consecutive duplicates
  L = re.split(r'((.)\2*)',''.join(map(str,M)))[1::3]
  l = len(L)
  indexes = [*range(1,l)]
  return [[M]]+[
    # wrap list for each consequtive pair of index combos and convert back from string
    [[int(c) for c in ''.join(L[i:j])]
      for i,j in pairwise([0,*partition_indexes,l])]
    for partition_size in indexes
    for partition_indexes in combinations(indexes,partition_size)
  ]
\$\endgroup\$
1
\$\begingroup\$

Nekomata, 4 bytes

ĉJᵐj

Attempt This Online!

A port of @Unrelated String's Brachylog answer.

ĉ       Partition into runs of consecutive equal elements.
 J      Take an arbitrary partition of the list of runs,
  ᵐj    and concatenate each slice.
\$\endgroup\$
0
\$\begingroup\$

JavaScript (V8), 71 bytes

f=([x,...y],z='')=>x?f(y,z+x)|f(y,[z,x]):/^,|1,1|0,0/.test(z)||print(z)

Try it online!

Seems they look same

JavaScript (V8), 72 bytes

f=([x,...y],z='')=>x?f(y,z+x)|f(y,z+[,x]):/^,|1,1|0,0/.test(z)||print(z)

Try it 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.