7
\$\begingroup\$

A partition of a list \$A\$ is a way of splitting \$A\$ up into smaller parts, concretely it is list of lists that when concatenated gives back \$A\$.

For example [[1],[2,3],[5,6]] is a partition of [1,2,3,5,6]. The trivial partition is a partition that "splits" the list into only one piece, so [[1,2,3,5,6]] is also a partition of [1,2,3,5,6].

One partition \$X\$ is finer than another partition \$Y\$ iff \$X\$ can be made by partitioning the pieces of \$Y\$ in place. So for example [[1],[2],[3],[5,6]] is finer than [[1],[2,3],[5,6]]. But [[1,2],[3],[5],[6]] is not finer than [[1],[2,3],[5,6]], even though it splits it into more parts. Note by this definition every partition is finer than itself. For two partitions it can easily be the case that neither of them is finer than the other.

Your task is to take as input a partition \$A\$ of a list of positive integers and output a distinct partition \$B\$ of the same list, such that \$A\$ is not finer than \$B\$ and \$B\$ is not finer than \$A\$. The input will never be the trivial partition (no cuts made) or the cotrivial partition (all cuts made). That is you don't need to worry about cases where there is no valid output.

Input can be taken as a list of list, array of arrays, vector of vectors or any reasonable equivalent. Output should be given in the same format as input.

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

\$\endgroup\$
9
  • \$\begingroup\$ Is the 51 a typo? Also, can you give a few test cases? Is A = [[1,2],[3,4]], B = [[1,2,3],[4]] a valid pair (to make sure I understand correctly)? \$\endgroup\$ Oct 5, 2022 at 14:35
  • \$\begingroup\$ @97.100.97.109 I can't really give test cases for a open-ended-function challenge. The output isn't fixed and what cases are tricky for one method of solving are completely different from another method. \$\endgroup\$
    – Wheat Wizard
    Oct 5, 2022 at 14:42
  • 1
    \$\begingroup\$ Sorry, I should be clearer - I meant could you give a few example pairs of lists (A,B) where A isn't finer than B and B isn't finer than A? (Also, for short inputs I think it's reasonable to provide all the valid possible outputs.) \$\endgroup\$ Oct 5, 2022 at 14:44
  • 1
    \$\begingroup\$ I don't think I will. I'd like to keep the spec small and I find that examples like that can just lead to misunderstanding. If the spec is unclear I can clarify it. \$\endgroup\$
    – Wheat Wizard
    Oct 5, 2022 at 14:48
  • 1
    \$\begingroup\$ @AZTECCO That challenge has different edge cases. I need to think of what I want to be acceptable and not and how to put that into objective criteria. \$\endgroup\$
    – Wheat Wizard
    Oct 6, 2022 at 2:41

9 Answers 9

8
\$\begingroup\$

Retina 0.8.2, 7 bytes

T`,;`;,

Try it online! Takes input and output as a semicolon-delimited list of comma-delimited lists. Explanation: Simply partitions the original list only in the places that the input list didn't partition it. In particular, anywhere the input list partitions the original list, the output list does not, and therefore is not finer than the input list, but the same applies in reverse so that the input list is not finer than the output list.

13 bytes with a more standard I/O format:

,
},{
}},{{
,

Try it online! Takes output as a list of lists, each element separated by , and each list wrapped with { and }. Explanation: Switches between , and },{ (which represents ; above) by first wrapping each , to },{ and then double-unwrapping }},{{ to ,.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I feel that this is probably stretching the limits on what reasonable IO format can be considered. \$\endgroup\$
    – Wheat Wizard
    Oct 5, 2022 at 14:51
  • 1
    \$\begingroup\$ @WheatWizard How's my alternative 13-byte answer? \$\endgroup\$
    – Neil
    Oct 5, 2022 at 15:01
  • 1
    \$\begingroup\$ Yeah, that of course seems like a more standard input format. \$\endgroup\$
    – Wheat Wizard
    Oct 5, 2022 at 15:08
4
\$\begingroup\$

Haskell, 47 bytes

f((h:t):r)|t>[]=[h]:[id=<<t:r]|a:b<-f r=(h:a):b

Try it online!

Recursively pattern matching first element (h:t):r
t>[] : if its tail is a list, we isolate head [h] and join everything else.
Else we do the same with the rest and join first el. of result with h which is a singleton.

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

Python, 98 bytes

lambda a:[(l:=[*chain(*a)])[:(i:=-~[len(x)>1for x in a].index(1))]]+[l[i:]]
from itertools import*

Attempt This Online!

Takes input as a list of lists, returns as a list of list. Though the code is a bit retch-inducing, the way it works is

  1. Join all of the lists together.
  2. Split the list at an index which is associated with a list of at least 2 elements in \$A\$.
\$\endgroup\$
2
\$\begingroup\$

Japt -Q, 6 bytes

m¸·¸m·

Try it

Basically the same logic as Neil's Retina answer.

m¸·¸m·
m¸     # Join each part to a string with " " as a delimiter
  ·    # Join the resulting strings with "\n" as a delimiter
   ¸   # Split that string at " " characters
    m· # Split the substrings at "\n" characters

Input and output are "Array of arrays of strings". The same code works for input as numbers/output as strings. Input and output as numbers takes an extra 2 bytes.

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

Jelly, 6 bytes

ẈÄṬ¬kẎ

Try it online!

Another port of Neil's logic--completely invert the partition--except without string operations. Takes and returns a list of lists.

  Ṭ       Generate an array with 1s at the indices in
 Ä        the cumulative sum of
Ẉ         the lengths of the original partitions.
    k     Partition the array
     Ẏ    concatenated
   ¬      after positions of 0s.
\$\endgroup\$
1
  • \$\begingroup\$ That was a fast downvote--did I miss something? \$\endgroup\$ Oct 7, 2022 at 22:59
2
\$\begingroup\$

Python 2, 58 bytes (@AZTECCO)

lambda s:eval(`s`.replace('], [',',').replace(', ','],['))

Attempt This Online!

Port of @Neil's answer. This takes and returns a list of lists.

Python, 50 bytes

lambda s:s.replace(',','],[').replace(']],[[',',')

Attempt This Online!

Port of @Neil's answer. Takes and returns strings (brackets, commas, no spaces).

Python, 73 bytes

def f(s):
 *o,i=[],[],0
 for c,*r in s:o[i]+=c,;o[1]+=r;i|=r>[]
 return o

Attempt This Online!

Port (to no-itertools) of @97.100.97.109's answer.

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

Wolfram Language (Mathematica), 46 bytes

f@{x___,{a_,b__},y___}:=Flatten/@{{x,a},{b,y}}

Try it online!

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

05AB1E, 5 bytes

»#¶δ¡

Inspired by @Neil's Retina answer: outputs the inverted partition of the given input.

I/O as a list of lists of strings.

Try it online or verify some more test cases.

Explanation:

»      # Join each inner list by spaces, and then each string by newlines
 #     # Split this multiline string by spaces
   δ   # Map over each substring:
  ¶ ¡  #  Split it by newlines
       # (after which the result is output implicitly)
\$\endgroup\$
0
0
\$\begingroup\$

Python, 72 bytes

def f(a):
 a+=[z:=[]]
 for x in a:z+=[x.pop()]
 while[]in a:a.remove([])

Attempt This Online!

Port of AZTECCO's solution

\$\endgroup\$
3
  • \$\begingroup\$ This doesn't seem to be correct: its output is not in the same order as the input (once flattened). \$\endgroup\$
    – pxeger
    Oct 19, 2022 at 15:57
  • \$\begingroup\$ @pxeger why the order should matter? the output is a partition, a set of sets \$\endgroup\$
    – matteo_c
    Oct 19, 2022 at 16:11
  • \$\begingroup\$ Moreover, not all partitions can be represented in the same order as the input once flattened, e.g. [[1,3],[2,4]] (supposing the input is [[1,2],[3,4]]) \$\endgroup\$
    – matteo_c
    Oct 19, 2022 at 16:12

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.