Considere una serie de enteros:

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

Hay muchas maneras de dividir esta lista en sublistas consecutivas. Aquí hay tres:

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

Llamaremos a una partición Y y al refinamiento de otra partición X si se puede obtener X de Y uniendo algunas de sus sublistas nuevamente.

Entonces, Bes un refinamiento de A: si unimos las dos primeras y las últimas dos sublistas nuevamente, obtenemos A. Pero noC es un refinamiento de : tendríamos que dividir el y el para recuperarnos de él. Además, cualquier partición es trivialmente un refinamiento de sí misma.A91A

Tenga en cuenta que no podemos reorganizar ninguna sublista o elemento en ningún momento.

El reto

Dadas dos particiones (listas de listas de enteros) Xy Y, determinar si Yes un refinamiento de X.

Puede suponer que las particiones solo contendrán enteros desde 0hasta 9, inclusive. No debe suponer eso Xy Yson particiones de la misma lista (si no lo son, tampoco son refinamientos entre sí). Xy / o Ypuede estar vacío pero nunca contendrá sublistas vacías.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

La entrada puede tomarse en cualquier cadena conveniente o formato de lista. Dado que los elementos solo serán enteros de un solo dígito, puede optar por omitir un delimitador dentro de las sublistas, pero asegúrese de que los 0s iniciales sean posibles. Puede elegir tomar Xy Yen orden opuesto.

La salida debe ser veraz si Yes un refinamiento Xy una falsedad de lo contrario.

Su código debe poder resolver cada uno de los casos de prueba a continuación en 1 segundo en una máquina de escritorio razonable. (Esto es simplemente un control de cordura para evitar soluciones simples de fuerza bruta).

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Casos de prueba

Cada caso de prueba está en su propia línea, escrita como X Y. Estoy usando la notación de matriz estilo GolfScript / CJam para ahorrar espacio horizontal:

Verdad:

[] []
[[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]]

Tablas de clasificación

Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

# 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>

Desafíos relacionados

• Calcule la unión y reunión de particiones

CJam, 13 10 9 bytes

lr.-F-U-!

Pruébelo en línea en el intérprete de CJam .

Gracias a @ MartinBüttner por sugerir el ingenioso formato de entrada de @ edc65 .

Gracias a @ jimmy23013 por mejorar el formato de entrada y jugar 3 bytes adicionales.

I / O

Entrada

Las sublistas están separadas ;entre sí por ,:

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

Salida

1

Cómo funciona

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.

Para cadenas de diferente longitud, .-dejará caracteres en la matriz, que no pueden ser iguales a los enteros 0 o 15.

Pyth, 19 bytes

&gF_m{.u+NYdYQqFsMQ

Pruébelo en línea: demostración o prueba de arnés

Estoy usando el formato de tupla / lista de Pyth como entrada. Simplemente reemplace los espacios de los casos de prueba con comas.

Explicación:

                     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

Dado que el pseudocódigo sigue siendo un poco confuso, demostraré el algoritmo usando una entrada de ejemplo.

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

La .u+NYdYparte calcula todas las sublistas continuas que contienen el primer elemento.

[[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]]

Bes un refinamiento de A, si cada sublista continua de Aes también una sublista continua de B(solo hay una excepción).

Así que simplemente verifico si el conjunto de sublistas continuas de Aes un subconjunto del conjunto de sublistas continuas de B( gF_m.u+NYdYQ).

La única excepción es, si la primera lista de entrada contiene menos elementos que la segunda lista de entrada. Por ejemplo <Fm.u+YdYQ, volvería Truepara la entrada [[1]],[[1],[2]].

Por lo tanto, también verifico si las listas unidas también son iguales &...qFsMQ.

JavaScript ( ES6 ), 67 70

Editar 3 bytes guardados thx @apsillers

Ejecute el fragmento a continuación en Firefox para probar

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>

C, 69 75

Una función con 2 parámetros de cadena, que devuelve 0 o 1.

Formato de parámetro: sublista separada con espacios (''), elementos de lista separados por comas.

Ejemplo: "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);}

Menos golf

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
}

Prueba de ideona (anticuada)

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

Devoluciones Trueo False. Ejemplo de uso: [[1,0,9],[1,3,8]] # [[1,0],[9]]-> False.

Enfoque recursivo simple: si los primeros elementos coinciden, continúe con las colas, de lo contrario, comience de nuevo pero concatene los dos elementos al principio de la segunda lista. Los casos base son: ambas listas están vacías -> True; ambas listas con un solo elemento -> compárelas; solo una lista vacía -> False.

CJam, 19 bytes

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

Pruébalo en línea.

I / O

Entrada

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

Salida

1

Idea

Cada partición se puede identificar de forma única observando las siguientes dos propiedades:

• La lista formada al concatenar todas las sublistas.

• Los "puntos de corte", incluidos los extremos de la lista.

Podemos combinar ambos criterios en uno reemplazando cada punto de corte con la sublista de elementos desde el punto de corte hasta el final de la lista.

Para verificar que una partición dada es más fina que otra, solo tenemos que verificar si la partición más gruesa, representada como arriba, es un subconjunto de la más fina y si las listas más grandes de ambas particiones coinciden.

Código

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.

Para la entrada del ejemplo de E / S, la pila contiene

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

antes de ejecutar -!.

Tenga en cuenta que el primer elemento de cada matriz tiene un espacio final. Esto asegura que comparemos la lista completa de la primera entrada con la lista completa de la segunda.

CJam, 24 bytes

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

Algoritmo

Aquí simplemente usamos un algoritmo codicioso para ver si las primeras Nsublistas de la segunda lista pueden fusionarse para formar la primera sublista de la primera lista. Una vez que Nse encuentra, eliminamos las primeras Nsublistas de la segunda lista y la primera sublista de la primera lista y repetimos el proceso.

Idealmente, si la segunda lista era un refinamiento de la primera, deberíamos quedar con 2 listas vacías en la pila. Simplemente verificamos eso e imprimimos 1si ese es el caso. En cualquier otra combinación, después de iterar completamente sobre las sublistas de la segunda lista, no terminaremos con 2 listas vacías. Por lo tanto 0, se imprimirá a para tales casos.

Expansión de código

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

Pruébelo en línea aquí o ejecute el conjunto de pruebas completo aquí

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;}

No he jugado mucho al golf recientemente, así que pensé en probarlo.

Definimos una función R(char* s, char* t)que devuelve 1si tes una partición refinada de s, y de lo 0contrario. sy tse espera que tengan el formato [DDDD...][DDDD...]...Donde cada uno Des otro elemento de un solo dígito.

Código de prueba:

#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));
}

Lo anterior imprime lo siguiente:

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

Parece funcionar, al menos.

Haskell, 52 50 53 bytes

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

Completamente diferente de mi otra solución . Utiliza el mismo formato de entrada inteligente que la respuesta de @ edc65 , es decir, los elementos se separan ,y se enumeran con .

Ejemplo de uso: "1,0,9,1,3,8" # "1,0,9 1,3,8"-> True.

El segundo parámetro es un refinamiento del primero, si tienen elementos iguales en cada posición o si el primero lo es ,. Tengo que agregar un token final único (-> ..) a ambos parámetros, porque zipWithtrunca el parámetro más largo y, por ejemplo "1,2,3" # "1,2", también lo sería True.

Mathematica, 65 bytes

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

¡Las matemáticas con expresiones regulares son divertidas!

Javascript ES6, 53 caracteres

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

Javascript Vintage, 70 caracteres

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

Utiliza el mismo formato de entrada que la respuesta de edc65 .

Demo completa que incluye todos los casos de prueba aquí.

Mathematica, 55 bytes

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

Esto define una función sin nombre, tomando las dos particiones en una sola lista , en orden inverso (es decir Y, primero, Xsegundo).

Explicación

Equal@@Join@@@#

Esto comprueba que ambas particiones son en realidad particiones de la misma lista.

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

Esta es una forma de golf de mi enfoque en esta pregunta sobre Mathematica.SE , que inspiró este desafío. Básicamente, una partición se define como un número de índices donde se insertan divisiones, y esto comprueba que todas las posiciones de división Xtambién aparecen Yacumulando las longitudes de las sublistas.

Python 2, 68 51 bytes

¡Gracias a xnor por algunos considerables ahorros en bytes!

Función anónima que toma dos cadenas de la forma "1,0,9 1,3,8"(tomada de la respuesta C de edc65 ) y devuelve Trueo False. La nueva versión map(None)ya no funciona en Python 3.

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

Banco de pruebas:

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

Solución anterior de 92 bytes que toma datos como "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