19
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Would [[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]] or [["109" "138"] ["1" "09" "13" "8"]] be an acceptable input format? \$\endgroup\$ – Dennis Jun 15 '15 at 17:26
  • \$\begingroup\$ @Dennis Wrapping the entire input in an array seems odd. I'm not aware of that being standard practice but it might be worth a meta question. Without those outer brackets it's definitely fine. \$\endgroup\$ – Martin Ender Jun 15 '15 at 17:30
  • \$\begingroup\$ I'll try to write up a meta question. \$\endgroup\$ – Dennis Jun 15 '15 at 18:07

13 Answers 13

6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If you can use ; as the separator... ll.m27m0-!. \$\endgroup\$ – jimmy23013 Jun 16 '15 at 16:30
  • \$\begingroup\$ @jimmy23013: I don't see why not. , and ; are both common array syntax (and none of them is used by CJam). Thanks! \$\endgroup\$ – Dennis Jun 16 '15 at 16:38
9
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ One of these days I'm going to have to download Firefox to see your awesome solutions in action. :) \$\endgroup\$ – Alex A. Jun 15 '15 at 15:22
  • \$\begingroup\$ @AlexA. how can you live without it? \$\endgroup\$ – edc65 Jun 15 '15 at 15:28
  • \$\begingroup\$ Use repl.it , I think that supports ES6 :D \$\endgroup\$ – Mark K Cowan Jun 16 '15 at 13:50
  • \$\begingroup\$ I like how you named the variables OK and KO. \$\endgroup\$ – rr- Jun 17 '15 at 17:20
7
\$\begingroup\$

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)

\$\endgroup\$
  • 1
    \$\begingroup\$ Clever choice of input format. I've borrowed it for another Haskell answer. \$\endgroup\$ – nimi Jun 15 '15 at 23:27
  • \$\begingroup\$ I ripped off your idea for input for my JS answer, and it turned out to be one byte longer than your C version until I upgraded it to ES6... Who'd have expected that... \$\endgroup\$ – Mark K Cowan Jun 16 '15 at 13:45
6
\$\begingroup\$

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.

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

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.

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

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

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

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.

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ (\a b->a==b||a>b) is just (>=). \$\endgroup\$ – alephalpha Jun 16 '15 at 5:33
  • \$\begingroup\$ wouldn't adding just "." instead of ".." work too? \$\endgroup\$ – proud haskeller Jun 16 '15 at 11:27
  • \$\begingroup\$ this fails on "2"#"1" because the functions only checks if the values are bigger, not equal \$\endgroup\$ – proud haskeller Jun 16 '15 at 11:33
  • \$\begingroup\$ @alephalpha: oh dear, how stupid of me to overlook that. But it is wrong anyway. See other comments. \$\endgroup\$ – nimi Jun 16 '15 at 14:52
  • \$\begingroup\$ @proudhaskeller: damn last minute edits. Yes, this is a bug. Fixed it. Thanks for finding out. BTW, a single dot "."won't work, because it would give a false positive for "2,1" # "2" which would first expand to "2,1." # "2." and then be truncated by zipWith to "2," # "2.". A comma in the first string matches everything. \$\endgroup\$ – nimi Jun 16 '15 at 14:58
2
\$\begingroup\$

Mathematica, 65 bytes

f@__=1<0;{}~f~{}=1>0;{a_,b___}~f~{c__,d___}/;a==Join@c:={b}~f~{d}
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice solution. FYI, I've got a 59-byte solution that doesn't use recursion (or multiple definitions). \$\endgroup\$ – Martin Ender Jun 16 '15 at 7:51
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Clever! Never thought about regular expressions for this task. \$\endgroup\$ – edc65 Jun 16 '15 at 14:19
  • \$\begingroup\$ I wrote a perl program that factorised integers using a recursive function that found prime factors using a backtracking regular expression... They aren't pretty and definitely aren't fast, but they can do some cool stuff! \$\endgroup\$ – Mark K Cowan Jun 16 '15 at 14:21
  • \$\begingroup\$ I also wrote a parser generator, which converts a language specification into a regular expression, and that regular expression can then be used to parse expressions in the specified language. Basically, "compiling" a human-readable language spec to an "executable" regular-expression. github.com/battlesnake/d-slap The generated regular expression for parsing AngularJS comprehension expressions is about 400-500 characters long... \$\endgroup\$ – Mark K Cowan Jun 16 '15 at 14:22
2
\$\begingroup\$

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ I think you can avoid doing an explicit length check by mapping None. The case when one list is longer than another is rejected where one list has None but the other index has a number, since i==j or"0">i>j cannot hold. \$\endgroup\$ – xnor Jun 16 '15 at 7:50
  • \$\begingroup\$ Unless I'm missing something, the second test can just be i==','. This lets you combine the tests as i in[',',j] (we can't do i in ','+j) because j might be None. \$\endgroup\$ – xnor Jun 16 '15 at 8:00
  • \$\begingroup\$ @xnor Wow, thanks. #1 didn't occur to me because I'm pretty used to thinking in Python 3 now; #2 didn't occur to me because "what if b has a number at that spot?" ... forgetting that with this input format, that's not possible. \$\endgroup\$ – DLosc Jun 20 '15 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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