Refined Partitions

Question

Consider an array of integers:

[1, 0, 9, 1, 3, 8]

There are a lot of ways to partition this list into consecutive sublists. Here are three:

A: [[1, 0, 9], [1, 3, 8]]
B: [[1], [0, 9], [1, 3], [8]]
C: [[1, 0], [9, 1], [3, 8]]

We will call a partition Y and refinement of another partition X if X can be obtained from Y by joining some of its sublists back together.

So B is a refinement of A: if we join the first two and the last two sublists back together, we obtain A. But C is not a refinement of A: we'd have to split up the 9 and the 1 in order to recover A from it. Also, any partition is trivially a refinement of itself.

Note that we're not allowed to rearrange any sublists or elements at any point.

The Challenge

Given two partitions (lists of lists of integers) X and Y, determine whether Y is a refinement of X.

You may assume that the partitions will only contain integers from 0 to 9, inclusive. You must not assume that X and Y are partitions of the same list (if they aren't, they also are not refinements of each other). X and/or Y may be empty but will never contain empty sublists.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be taken in any convenient string or list format. Since the elements will only be single-digit integers, you may choose to omit a delimiter within the sublists, but make sure that leading 0s are possible. You may choose to take X and Y in opposite order.

Output should be truthy if Y is a refinement of X and falsy otherwise.

Your code must be able to solve each of the test cases below in 1 second on a reasonable desktop machine. (This is merely a sanity check to avoid simple brute force solutions.)

This is code golf, so the shortest answer (in bytes) wins.

Test Cases

Each test case is on its own line, written as X Y. I'm using GolfScript/CJam-style array notation to save some horizontal space:

Truthy:

[] []
[[0]] [[0]]
[[1 0 9 1 3 8]] [[1 0 9] [1 3 8]]
[[1 0 9 1 3 8]] [[1 0 9 1 3] [8]]
[[1 0 9 1 3 8]] [[1] [0] [9] [1] [3] [8]]
[[1 0 9] [1 3 8]] [[1 0 9] [1 3 8]]
[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]
[[9 8 8 5 8 2 7] [5] [1 4] [2 0 0 6 0 8 4 2 6 4 2 3 7 8 7 3 9 5 7 9 8 2 9 5] [3 9 8] [7 1 4 9 7 4 5 9] [3 3 3] [9 0 7 8] [3 9 4 7 2 7 8 0 3 0] [8 2 2 7 3 9 3 2] [2 9 0 8 5 4 1 8 5 5 6 2 0 9 2 7 7 9 2 7] [3 6] [1 2 7 7 4 4 2 9]] [[9 8] [8] [5 8 2] [7] [5] [1 4] [2] [0 0 6] [0] [8 4 2] [6 4] [2] [3] [7 8] [7 3] [9] [5 7 9] [8 2] [9 5] [3] [9 8] [7 1 4] [9 7] [4 5 9] [3 3] [3] [9 0] [7 8] [3] [9] [4] [7 2] [7 8] [0] [3 0] [8 2] [2] [7 3] [9 3] [2] [2] [9] [0] [8 5 4] [1 8] [5 5] [6] [2 0] [9] [2] [7 7 9] [2 7] [3 6] [1 2] [7 7] [4 4 2] [9]]

Falsy:

[[0]] []
[[0]] [[1]]
[[1 0 9]] [[1 0 9] [1 3 8]]
[[1 0 9] [1 3 8]] [[1 0 9 1 3 8]]
[[1 0 9] [1 3 8]] [[1 0 9]]
[[1 0 9] [1 3 8]] [[1 0] [9]]
[[1 0 9] [1 3 8]] [[1 0] [9 1] [3 8]]
[[1] [0 9] [1 3] [8]] [[1 0 9] [1 3 8]]
[[9 8 8 5 8 2 7] [5] [1 4] [2 0 0 6 0 8 4 2 6 4 2 3 7 8 7 3 9 5 7 9 8 2 9 5] [3 9 8] [7 1 4 9 7 4 5 9] [3 3 3] [9 0 7 8] [3 9 4 7 2 7 8 0 3 0] [8 2 2 7 3 9 3 2] [2 9 0 8 5 4 1 8 5 5 6 2 0 9 2 7 7 9 2 7] [3 6] [1 2 7 7 4 4 2 9]] [[9 8] [8] [5 8 2] [7] [5 1] [4] [2] [0 0 6] [0] [8 4 2] [6 4] [2] [3] [7 8] [7 3] [9] [5 7 9] [8 2] [9 5] [3] [9 8] [7 1 4] [9 7] [4 5 9] [3 3] [3] [9 0] [7 8] [3] [9] [4] [7 2] [7 8] [0] [3 0] [8 2] [2] [7 3] [9 3] [2] [2] [9] [0] [8 5 4] [1 8] [5 5] [6] [2 0] [9] [2] [7 7 9] [2 7] [3 6] [1 2] [7 7] [4 4 2] [9]]

Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51719</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

Related Challenges

• Compute the Join and Meet of Partitions

Answer 1

Pyth, 19 bytes

&gF_m{.u+NYdYQqFsMQ

Try it online: Demonstration or Test harness

I'm using Pyth's tuple/list format as input. Simply replace the spaces of the test cases with commas.

Explanation:

                     implicit: Q is the evaluated input
    m        Q       map each input list d to:
      .u   dY          reduce with intermediate states over d, initial value = []
        +NY              update initial value N with sum of N and Y (current element of d)
     {                 generate a set
   _                 invert
 gF                  check, if the first element is >= (superset) than the second
&                    and
                sMQ  check, if the joined lists of the input
              qF     are equal

Since the pseudo-code is still a little bit confusing, I'll demonstrate the algorithm using an example input.

Input: [[1,0,9],[1,3,8]],[[1],[0,9],[1,3],[8]]

The .u+NYdY part computes all continuous sublists, that contain the first element.

[[1,0,9],[1,3,8]]     => [[], [1,0,9], [1,0,9,1,3,8]]
[[1],[0,9],[1,3],[8]] => [[], [1], [1,0,9], [1,0,9,1,3], [1,0,9,1,3,8]]

B is a refinement of the A, iff each continuous sublist of A is also a continuous sublist of B (there's only one exception).

So I simply check, if the set of continuous sublists of A is a subset of the set of continuous sublists of B (gF_m.u+NYdYQ).

The only exception is, if the first input list contains less elements than the second input list. For instance <Fm.u+YdYQ would return True for the input [[1]],[[1],[2]].

Therefore I also check if the joined lists are also equal &...qFsMQ.

Answer 2

CJam, 13 10 9 bytes

lr.-F-U-!

Try it online in the CJam interpreter.

Thanks to @MartinBüttner for suggesting @edc65's ingenious input format.

Thanks to @jimmy23013 for improving the input format and golfing off 3 additonal bytes.

I/O

Input

Sublists are separated by ; and from each other by ,:

1;0;9,1;3;8
1,0;9,1;3,8

Output

1

How it works

lr e# Read line and a whitespace-separated token from STDIN.
.- e# Vectorized difference. Pushes the differences of corresponding code points.
F- e# Remove all occurrences of 15 (';' - ',') from the array.
U- e# Remove all occurrences of 0 from the array.
!  e# Push 1 if the resulting array is empty and 0 if not.

For strings of different length, .- will leave characters in the array, which cannot be equal to the integers 0 or 15.

Answer 3

JavaScript (ES6), 67 70

Edit 3 bytes saved thx @apsillers

Run the snippet below in Firefox to test

f=(a,b)=>a+''==b // same values in the lists ?
&![...a.join(' ')].some((c,p)=>c<','&b.join(c)[p]>c) // splits in a are present in b?

// TEST

out=x=>O.innerHTML += x+'\n';

OK=[
[[],[]],
[[[0]],[[0]]],
[[[1,0,9,1,3,8]],[[1,0,9],[1,3,8]]],
[[[1,0,9,1,3,8]],[[1,0,9,1,3],[8]]],
[[[1,0,9,1,3,8]],[[1],[0],[9],[1],[3],[8]]],
[[[1,0,9],[1,3,8]],[[1,0,9],[1,3,8]]],
[[[1,0,9],[1,3,8]],[[1],[0,9],[1,3],[8]]],
[[[9,8,8,5,8,2,7],[5],[1,4],[2,0,0,6,0,8,4,2,6,4,2,3,7,8,7,3,9,5,7,9,8,2,9,5],[3,9,8],[7,1,4,9,7,4,5,9],[3,3,3],[9,0,7,8],[3,9,4,7,2,7,8,0,3,0],[8,2,2,7,3,9,3,2],[2,9,0,8,5,4,1,8,5,5,6,2,0,9,2,7,7,9,2,7],[3,6],[1,2,7,7,4,4,2,9]],[[9,8],[8],[5,8,2],[7],[5],[1,4],[2],[0,0,6],[0],[8,4,2],[6,4],[2],[3],[7,8],[7,3],[9],[5,7,9],[8,2],[9,5],[3],[9,8],[7,1,4],[9,7],[4,5,9],[3,3],[3],[9,0],[7,8],[3],[9],[4],[7,2],[7,8],[0],[3,0],[8,2],[2],[7,3],[9,3],[2],[2],[9],[0],[8,5,4],[1,8],[5,5],[6],[2,0],[9],[2],[7,7,9],[2,7],[3,6],[1,2],[7,7],[4,4,2],[9]]]
];

KO=[
[[[0]],[]],
[[[0]],[[1]]],
[[[1,0,9]],[[1,0,9],[1,3,8]]],
[[[1,0,9],[1,3,8]],[[1,0,9,1,3,8]]],
[[[1,0,9],[1,3,8]],[[1,0,9]]],
[[[1,0,9],[1,3,8]],[[1,0],[9]]],
[[[1,0,9],[1,3,8]],[[1,0],[9,1],[3,8]]],
[[[1],[0,9],[1,3],[8]],[[1,0,9],[1,3,8]]],
[[[9,8,8,5,8,2,7],[5],[1,4],[2,0,0,6,0,8,4,2,6,4,2,3,7,8,7,3,9,5,7,9,8,2,9,5],[3,9,8],[7,1,4,9,7,4,5,9],[3,3,3],[9,0,7,8],[3,9,4,7,2,7,8,0,3,0],[8,2,2,7,3,9,3,2],[2,9,0,8,5,4,1,8,5,5,6,2,0,9,2,7,7,9,2,7],[3,6],[1,2,7,7,4,4,2,9]],[[9,8],[8],[5,8,2],[7],[5,1],[4],[2],[0,0,6],[0],[8,4,2],[6,4],[2],[3],[7,8],[7,3],[9],[5,7,9],[8,2],[9,5],[3],[9,8],[7,1,4],[9,7],[4,5,9],[3,3],[3],[9,0],[7,8],[3],[9],[4],[7,2],[7,8],[0],[3,0],[8,2],[2],[7,3],[9,3],[2],[2],[9],[0],[8,5,4],[1,8],[5,5],[6],[2,0],[9],[2],[7,7,9],[2,7],[3,6],[1,2],[7,7],[4,4,2],[9]]]
];

dump=l=>l.map(x=>'['+x+']').join(',');

out('YES');
OK.forEach(l=>out(f(l[0],l[1])+' a['+dump(l[0])+'] b['+dump(l[1])+']'));
out('NO');
KO.forEach(l=>out(f(l[0],l[1])+' a['+dump(l[0])+'] b['+dump(l[1])+']'));

<pre id=O></pre>

Answer 4

C, 69 75

A function with 2 string parameters, returning 0 or 1.

Parameter format: sublist separated with spaces (' '), list elements separated with commas.

Example: "1,0,9 1,3,8" "1,0 9,1,3,8"

f(char*a,char*b){for(;*a-44?*a&&*b==*a:*b<48;a++)b++;return!(*b|*a);}

Less golfed

int f(char *a, char *b)
{
    // expected in a,b: digit,separator,digit... with separator being ' ' or ','
    for(; *a; a++,b++)
       // ' ' or digit in a must be the same in b
       // comma in a must be comma or space in b
       if (*a != ',' ? *b != *a : *b > *a) return 0;
    return !*b; // must have a null in *b too
}

Test Ideone (outdated)

Answer 5

Haskell, 76 bytes

[]#[]=1<2
[x]#[y]=x==y
x@(a:b)#(c:d:e)|a==c=b#(d:e)|1<2=x#((c++d):e)
_#_=2<1

Returns True or False. Example usage: [[1,0,9],[1,3,8]] # [[1,0],[9]] -> False.

Simple recursive approach: if the first elements match, go on with the tails, else start over but concatenate the two elements at the front of the second list. Base cases are: both lists empty -> True; both lists with a single element -> compare them; only one list empty -> False.

Answer 6

CJam, 19 bytes

q~]{_,,\f>:sS.+}/-!

Try it online.

I/O

Input

[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]

Output

1

Idea

Each partition can be uniquely identified by observing the following two properties:

• The list formed by concatenating all sublists.

• The "cutting points", including the extremes of the list.

We can combine both criteria into one by replacing each cutting point with the sublist of elements from the cutting point to the end of the list.

To verify that a given partition is finer than another, we only have to verify if the coarser partition, represented as above, is a subset of the finer one and that the largest lists of both partitions match.

Code

q~]   e# Read from STDIN and evaluate.
{     e# For each array P from the input:
  _,, e#   Push [0 ... L], where L == length(P) - 1.
  \f> e#   Push [P[0:] ... P[L]].
  :s  e#   Stringify each P[k:] (flattens).
  S.+ e#   Vectorized concatenation. This appends a space to the first element.
}/    e#
-!    e# Push the logical NOT of the difference A-B to check if A is a subset of B.

For the input form the I/O example, the stack holds

["109138 " "138"] ["109138 " "09138" "138" "8"]

before executing -!.

Note that the first element of each array has a trailing space. This makes sure we compare the full list of the first input with the full list of the second.

Answer 7

CJam, 24 bytes

l~L\{+_a2$1<={;1>L}&}/+!

Algorithm

Here we simply use a greedy algorithm to see if first N sub-lists of the second list can be merged together to form the first sub-list of the first list. Once such N is found, we remove the first N sub-lists from second list and the first sub-list from the first list and repeat the process.

Ideally, if the second list was a refinement of the first, we should be left with 2 empty lists on stack. We just check for that and print 1 if that is the case. In any other combination, after fully iterating over sub-lists of second list, we won't end up with 2 empty lists. Thus a 0 will be printed for such cases.

Code expansion

l~L\{+_a2$1<={;1>L}&}/+!
l~L\                       e# Read the line, evaluate the two lists and put an empty list
                           e# between them
    {               }/     e# Iterate over all sub-lists of the second list
     +                     e# Append the current sub-list to whatever is on stack. Originally
                           e# an empty array, but eventually the sum of first N sub-lists
      _a                   e# Copy this and wrap it in an array
        2$                 e# Copy the first list on top of stack
          1<               e# Get only its first element wrapped in an array. This approach
                           e# is exception safe in case the array was already 0 length
            ={    }&       e# If we have a match, remove both first sub-lists
              ;            e# Remove the first N sub-lists array
               1>          e# Remove the first element from the first array
                 L         e# Put an empty array on stack to repeat the process
                      +!   e# If we are left with two empty arrays, sum them and do logical
                           e# not to get 1. If any of the arrays is non-empty, logical not
                           e# gives 0

Try it online here or run the complete test suite here

Answer 8

C, 120 114 bytes

#define C(x),x+=(*x/93)*(1+!!x[1])|1
o;R(char*s,char*t){for(o=1;*s;o&=*s==t[2*(*t==93&&93>*s)]C(s)C(t));return o;}

I haven't golfed much recently, so I thought I'd try this one out.

We define a function R(char* s, char* t) which returns 1 if t is a refined partition of s, and 0 otherwise. s and t are expected to be in the format [DDDD...][DDDD...]... Where each D is another single-digit element.

Testing code:

#include "stdio.h"

int main(int argc, char** argv) {
    char* str1, *str2;
    str1 = "[109][138]";
    str2 = "[1][09][13][8]";
    printf("Input: %s, %s --> %d\n", str1, str2, R(str1, str2));
    
    str1 = "[109][138]";
    str2 = "[1][19][13][8]";
    printf("Input: %s, %s --> %d\n", str1, str2, R(str1, str2));
    
    str1 = "[109][138]";
    str2 = "[10][91][3][8]";
    printf("Input: %s, %s --> %d\n", str1, str2, R(str1, str2));
}

The above prints the following:

Input: [109][138], [1][09][13][8] --> 1
Input: [109][138], [1][19][13][8] --> 0
Input: [109][138], [10][91][3][8] --> 0

It seems to work, at least.

Answer 9

Haskell, 52 50 53 bytes

x#y=and$zipWith(\a b->a==b||a==',')(x++"..")(y++"..")

Completely different from my other solution. Uses the same clever input format as @edc65's answer, i.e. elements are separated with , and lists with .

Usage example: "1,0,9,1,3,8" # "1,0,9 1,3,8" -> True.

The second parameter is a refinement of the first, if they have either equal elements at every position or the first one is ,. I have to append a unique end token (->..) to both parameters, because zipWith truncates the longer parameter and for example "1,2,3" # "1,2" would also be True.

Answer 10

Mathematica, 65 bytes

f@__=1<0;{}~f~{}=1>0;{a_,b___}~f~{c__,d___}/;a==Join@c:={b}~f~{d}

Answer 11

Maths with regular expressions is fun!

ES6 Javascript, 53 chars

(a,b)=>RegExp('^'+a.replace(/,/g,'[ ,]')+'$').test(b)

Vintage Javascript, 70 chars

function f(a,b){return RegExp('^'+a.replace(/,/g,'[ ,]')+'$').test(b)

Uses the same input format as edc65's answer.

Full demo including all test cases here.

Answer 12

Mathematica, 55 bytes

Equal@@Join@@@#&&SubsetQ@@(Accumulate[Length/@#]&)/@##&

This defines an unnamed function, taking the two partitions in a single list, in reverse order (i.e. Y first, X second).

Explanation

Equal@@Join@@@#

This checks that both partitions are actually partitions of the same list.

SubsetQ@@(Accumulate[Length/@#]&)/@##

This is a golfed form of my approach in this question over on Mathematica.SE, which inspired this challenge. Basically, a partition is defined as a number of indices where splits are inserted, and this checks that all the splitting positions in X also appear in Y by accumulating the lengths of the sublists.

Answer 13

Python 2, 68 51 bytes

Thanks to xnor for some considerable byte-savings!

Anonymous function that takes two strings of the form "1,0,9 1,3,8" (taken from edc65's C answer) and returns True or False. New version with map(None) no longer works in Python 3.

lambda a,b:all(i in[j,","]for i,j in map(None,a,b))

Test suite:

>>> def runTests(f):
    assert f("1,0,9 1,3,8","1 0,9 1,3 8")
    assert not f("1,0,9 1,3,8","1,0 9,1 3,8")
    assert f("1 0,9 1,3 8","1 0,9 1,3 8")
    assert not f("1 0,9 1,3 8","1,0,9 1,3,8")
    assert not f("1 0,9 1,3 8","1 0,9 1,3")
    assert not f("1 0,9 1,3,8","1 0,9 1,3")
    print("All tests pass.")


>>> runTests(lambda a,b:all(i in[j,","]for i,j in map(None,a,b)))
All tests pass.

Previous 92-byte solution that takes input as "109 138":

def R(a,b):
 r=1
 for i in b.split():r&=a.find(i)==0;a=a[len(i):].strip()
 return r and""==a

Answer 14

Jelly, 7 5 bytes

O_/²Ƒ

Try it online!

This implements Dennis' string-based algorithm, with a slight modification to the input format. Sublists are separated by - and from each other by , (e.g. [[1], [0, 9], [1, 3], [8]] -> 1,0-9,1-3,8). If this is too much of a stretch, Dennis' input format is 9 bytes

A pure array based method comes out at 10 6 bytes.

ŒbF€€i

Try it online!

This takes inputs reversed (i.e. X on the right and Y on the left), and outputs a non-zero integer for truthy and zero for falsey. It's 2 bytes longer (ŒbF€€iɗ@) to take input the normal way around. This does time out on TIO for the 2 longest inputs however.

How they work

The 5 byter is simply an adaptation of of Dennis' CJam answer into Jelly:

O_/²Ƒ - Main link. Take the pair [X, Y] on the left
O     - Convert everything to ordinals
 _/   - Element-wise subtraction
      - This results in:
      -   A list entirely containing 0s and 1s for truthy outputs
      -   A list consisting of at least one non-0 or 1 element for falsey outputs
   ²Ƒ - All elements are unchanged when squaring, i.e. all elements are 1 or 0

The 7 byter works as follows:

ŒbF€€i - Main link. Takes Y on the left and X on the right
Œb     - Generate all partitions of Y, yielding [[]] if Y is empty
    €  - Over each:
  F€   -   Flatten each sub-partition
       -  This has the effect of generating all possible concatenations of Y
     i  - Index of X in these concatenations, or 0 if not found