¡Prueba si una cadena se puede hacer con subcadenas!

23

Dada una cadena sy una matriz / lista l, determine si spuede hacerse o no con partes de l.

Por ejemplo, si la cadena es "Hello, world!"y la lista es [' world!', 'Hello,'], entonces el programa / función debería devolver un valor verdadero, porque puede organizar la lista para formar la cadena. La siguiente lista también devolver un valor Truthy: ['l', 'He', 'o, wor', 'd!']. Imagínese el 'l'relleno donde necesita en la cuerda. Entonces sí, puede repetir elementos de la lista para formar la cadena. Si no puede formar la cadena, debería devolver un valor falso. Métodos estándar de IO, se aplican las lagunas estándar.

Casos de prueba:

Input (In the form of s, l)
Output (1 if possible, 0 if impossible)

"Hello, world!", ["l", "He", "o, wor", "d!"]
1

"la lal al ", ["la", " l", "al "]
1

"this is a string", ["this should return falsy"]
0

"thi is a string", ["this", "i i", " a", " string"]
0

"aaaaa", ["aa"]
0

"foo bar foobar", ["foo", "bar", " ", "spam"]
1

"ababab", ["a","ba","ab"]
1

"", ["The string can be constructed with nothing!"]
1
Camarada SparklePony
fuente
¿Importa si la matriz contiene más cadenas de las necesarias para construir la cadena principal?
Shaggy
¿Cuál debería ser el valor de retorno en esos casos?
Shaggy
@Shaggy Truthy. Si hay más, entonces la cadena se puede construir con todas las partes no adicionales. Agregaré un caso de prueba.
Camarada SparklePony
3
Recomiendo agregar este caso de prueba:"ababab", ["a","ba","ab"]
adicto a las matemáticas
3
Te sugiero que agregues un caso de prueba que contenga metacaracteres regex.
Joey

Respuestas:

11

Brachylog , 8 bytes

~c¬{∋¬∈}

Pruébalo en línea!

Esto es realmente lento. Tomó alrededor de 37 segundos para el "¡Hola, mundo!" caso de prueba en mi PC, y se agotó el tiempo de espera en TIO.

Esto lleva la cadena a través de la variable Entrada y la lista a través de la variable Salida

Explicación

             String = ?, List = .

             It is possible to find…
~c           …a deconcatenation of ?…
  ¬{   }     …such that it is impossible…
    ∋¬∈      …that an element of that deconcatenation is not an element of .
Fatalizar
fuente
"la lal al" más de 60 segundos ...
RosLuP
1
@RosLuP Con esta entrada y ["la", " l", "al "]como lista, terminó en mi computadora y respondió correctamente false.después de 6800 segundos, y "solo" 113 mil millones de inferencias.
Fatalize
Siento que escribir cualquier cosa en este idioma daría como resultado un programa no ejecutable en TIO jaja.
Urna mágica del pulpo
@carusocomputing El lenguaje no es tan lento para la mayoría de los programas, es solo que, en algunos casos, debido a la declaratividad del programa, resulta en tiempos de ejecución muy lentos (que podrían mejorarse drásticamente a costa de la longitud del código)
Fatalize
@Fatalize errr ... Quise decir que jugar al golf no escribir, parece que cuantas menos instrucciones, más amplia se vuelve la "pregunta" y más cálculos necesitas. Parece un lenguaje impresionante para problemas matemáticos teóricos.
Urna mágica de pulpo
7

Mathematica, 29 bytes

StringMatchQ[#,""|##&@@#2..]&

Explicación:

             #,               (* The first argument *)
StringMatchQ[                 (* matches the string pattern *)
               ""|##&         (*   Alternatives *)
                     @@       (*     applied to *)
                       #2     (*     the second argument *)
                         ..   (*   repeated *)
                           ]&

Solución límite de trampas, 21 bytes

StringMatchQ[#,#2..]&

Dado que Mathematica es un lenguaje de programación simbólico, no existe una * diferencia entre las expresiones List[a,b,...]y la Alternatives[a,b,...]forma en que interactúan con otros símbolos y cómo se muestran ( {a,b,...}y a|b|..., respectivamente). Cuando se usa en el segundo argumento de StringMatchQ, una Alternativesexpresión se trata como un patrón de cadena y, por lo tanto, podemos guardar 8bytes sobre mi solución anterior tomando el segundo argumento como una Alternativesexpresión.

* Técnicamente Listtambién lo es Locked, lo que evita que los usuarios lo Unprotectingieran y cambien su comportamiento.

ngenisis
fuente
1
{x,y,z}se trata de la misma manera que x|y|zpara la coincidencia de patrones de cadena. Creo que puedes reemplazar ""|##&@@#2..con solo #2...
No es un árbol
5

Pyth, 23 bytes

AQW&GhGJ.(G0Vf!xJTH aG>JlN;G

Toma entrada como [['string'],['list', 'of', 'parts']]. El resultado es una lista vacía o una lista con valores dentro. En Pyth, una lista que contiene cualquier cosa, incluso una cadena nula ( ['']), se evalúa como verdadera.

Pruébalo en línea!

Explicación:

                             | Implicit: Q = eval(input())
AQ                           | Assign the first value of Q to G and the second to H
  W&GhG                      | While G is not empty and G doesn't contain an empty string:
       J.(G0                 |  Pop the first value of G and store into J
            Vf!xJTH          |  For N in elements in H that match the beginning of J:
                             |   Additional space for suppressing printing 
                    aG>JlN   |   Append to G the elements of J from the length of N to the end
                          ;  | End all loops
                           G | Print G

Esta solución intenta continuamente eliminar todas las partes posibles desde el comienzo de la cadena y realiza un seguimiento de los valores que aún necesita analizar.

Si observamos el valor de Gen el caso de prueba [['ababab'],['a','ba','ab']]después de cada iteración del ciclo while, esto es lo que obtenemos:

['ababab']
['babab', 'abab']
['abab', 'bab']
['bab', 'bab', 'ab']
['bab', 'ab', 'b']
['ab', 'b', 'b']
['b', 'b', '']
['b', '']
['']   <---Remember, this evaluates to True

Y, en el caso de prueba [['aaaaa'],['aa']], esto es lo que obtenemos:

['aaaaa']
['aaa']
['a']
[]   <---And this evaluates to False

Creé otro caso de prueba, [['aaaaaa'],['a','aa','aaa']]y el resultado fue este:

['', 'aaa', 'aa', 'a', 'aa', 'a', '', 'a', '', 'aa', 'a', '', 'a', '', '', 'a', '', '']

La lista de salida contiene un montón de basura dentro de ella, pero sigue siendo un valor verdadero.

K Zhang
fuente
5

Perl 5 , 39 bytes

38 bytes de código + -pbandera.

map{chop;$v.="\Q$_\E|"}<>;$_=/^($v)*$/

Pruébalo en línea!

Para la entrada "Hello, world!", ["l", "He", "o, wor", "d!"](separada por líneas nuevas en realidad), construye el patrón l|He|o, wor|d!|(con los metacaracteres escapados, gracias a \Q..\E), y luego mira si la primera cadena coincide con este patrón /^($v)*$/.

En TryItOnline, tenga en cuenta que debe haber una nueva línea final.

Dada
fuente
"¡Hola, mundo! ¡Oh, qué!" esta entrada con un espacio después de la "l" no genera ningún resultado
RosLuP
@RosLuP ¿Me puede dar un enlace TryItOnline por favor? (No entiendo lo que quieres decir exactamente. Tenga en cuenta que "falso" en realidad no imprime nada, ya que esto es Perl)
Dada
Entonces, para la impresión falsa nada? En este caso, discúlpeme, pero este valor sin salida no me parece demasiado útil ...
RosLuP
@RosLuP Eso es correcto. En Perl, undefes el valor falso devuelto por la mayoría de los incorporados. Y al imprimirlo, en realidad no imprime nada. Y eso es exactamente lo que estoy haciendo. Imprimir "1/0" es natural para lenguajes tipo C, pero para Perl, "1 / undef" es la forma natural.
Dada
Ninguna salida tiene una ambigüedad "¿se está ejecutando o ya el programa finaliza falso?"
RosLuP
4

PHP, 69 bytes

<?=($s=$_GET[0])>""?ctype_digit(strtr($s,array_flip($_GET[1])))?:0:1;

Casos de prueba

Jörg Hülsermann
fuente
Muy inteligente, me tomó un minuto entender lo que estás haciendo. +1 por pensar fuera de la caja
Martijn
Falso negativo para ese caso de borde molesto["", ["The string can be constructed with nothing!"]]
Jonathan Allan
@JonathanAllan hecho es una cadena vacía una cadena?
Jörg Hülsermann
Sí, el problema de la partición vacía es un problema en muchas soluciones.
Jonathan Allan
3

Python 2, 141 bytes

lambda s,l:s in[''.join(i)for r in range(len(s)+1)for j in combinations_with_replacement(l,r)for i in permutations(j)]
from itertools import*

Pruébalo en línea!

Extremadamente ineficiente. El primer caso de prueba expira en TIO.

adicto a las matemáticas
fuente
3

JavaScript (ES6), 59 bytes

Toma la matriz de subcadenas ay la cadena sen sintaxis curry (a)(s). Devoluciones false/ true.

a=>g=s=>!s||a.some(e=>s.split(e)[0]?0:g(s.slice(e.length)))

Comentado

a =>                          // main function that takes 'a' as input
  g = s =>                    // g = recursive function that takes 's' as input
    !s ||                     // if 's' is empty, return true (success!)
    a.some(e =>               // else, for each element 'e' in 'a':
      s.split(e)[0] ?         //   if 's' doesn't begin with 'e':
        0                     //     do nothing
      :                       //   else:
        g(s.slice(e.length))  //     remove 'e' at the beginning of 's' and
    )                         //     do a recursive call on the remaining part

Casos de prueba

Arnauld
fuente
3

Haskell , 35 bytes

#toma una Stringy una lista de Strings, y devuelve a Bool.

s#l=elem s$concat<$>mapM("":)(l<$s)

Pruébalo en línea!

Simplemente no me importa el caso de prueba que dejé fuera porque golpeó mi exigua computadora portátil, incluso con -O2. Sospecho que GHC no fusiona esa lista de elementos intermedios 30517578125, tiene demasiado uso compartido para recolectar basura rápidamente, y debido a que el caso de prueba es falso, el programa tiene que generarlo todo ... siéntase libre de intentarlo si puede maneja eso.

mapM("":)(l<$s)es una lista de todas las formas de hacer una length slista de elementos que son cadenas vacías o cadenas de l.

Ørjan Johansen
fuente
3

Pyth, 17 15 11 14 bytes

AQ|!G}Ym-dH./G

El requisito para la cadena vacía cambió, agregando 3 bytes.

Explicación

AQ|!G}Ym-dH./G
AQ                     Save the input into G, H.
           ./G         Get all partitions of G.
       m-dH            Check if the parts are in H.
     }Y                The empty list should be present if and only
                           if the string can be made...
  |!G                  ... or the string might be empty.

versiones antiguas

AQ}Ym-dH./G

¡Más corto y corre en la vida útil del universo!

Explicación

AQ}Ym-dH./G
AQ                  Save the input into G, H.
        ./G         Get all partitions of G.
    m-dH            Check if the parts are in H.
  }Y                The empty list should be present if and only
                        if the string can be made.

AQ&G}GsMs.pMy*HlG

Esto es horriblemente lento, pero funciona para mis casos de prueba (trivialmente pequeños).

Explicación

AQ&G}GsMs.pMy*HlG
AQ                  Save the input into G, H.
             *HlG   Repeat the list of substrings for each character of G.
            y       Take the power set.
         .pM        Take every permutation of each set of substrings.
      sMs           Get a list of all the joined strings.
    }G              Check if G is one of them.
  &G                Make sure G is not empty.

fuente
3

Jalea , 14 12 8 bytes

;FŒṖḟ€Ạ¬

Pruébalo en línea!

Cómo funciona

;FŒṖḟ€Ạ¬   - main function, left argument s, right argument l
;F         - concatenate to the string the list, flattened to deal with "" as string
  ŒṖ       - Get all partitions of s, that is, all ways to make s from substrings
     €     - For each partition...
    ḟ      -   Filter out (exclude) those elements which are not in... 
           -   (implicit right arg) the list l. This leaves the empty set (falsy) if the partition can be made of elements from the list
      Ạ    - If any element is falsy (thus constructable from l), return 0; else return 1
       ¬   - Apply logical not to this, to yield the proper 1 = constructable from list, 0 otherwise.

"", ["The string can be constructed with nothing"]corrección de errores en el caso gracias a @JonathanAllan

fireflame241
fuente
Falso negativo para"", ["The string can be constructed with nothing!"]
Jonathan Allan
Será mucho más lento pero ;FŒṖḟ⁹$€Ạ¬lo solucionará.
Jonathan Allan
... y se puede usar un argumento implícito adecuado para , por lo que no necesita el $o : ;FŒṖḟ€Ạ¬.
Jonathan Allan
Grr, eso es lo que obtengo por no probar cada caso de prueba. Es posible que pueda mantener 8 bytes reemplazándolos ¬con una operación que siempre devuelve verdadero con el argumento correcto "".
fireflame241
^ bueno, lo recuperé a 8 :)
Jonathan Allan
2

R, 49 bytes

function(s,l)gsub(paste(l,collapse='|'),"",s)==""

Pruébalo en línea!

Neil
fuente
2
Debería fallar ('x', '.'), pero no lo hace.
Joey
2

Pyth, 10 8 bytes

f!-TQ./+zh

Banco de pruebas

Esto toma la lista en la primera línea de STDIN y la cadena (sin comillas) en la segunda.

Para comenzar, la lista se almacena en Q, y la cadena se almacena en z. A continuación, formamos todas las particiones posibles de z. Cada partición se filtrará ( f) para verificar si solo usa piezas Q. Para ello, se elimina todos los elementos de Qpartir T, la partición que estamos partición, y lógicamente negar el resultado con !, por lo que sólo las particiones donde cada elemento estaba en Qse mantienen.

Para solucionar el problema que ''no tiene particiones, agregamos la primera palabra del diccionario a z, para que no sea una cadena vacía.

isaacg
fuente
El conjunto de pruebas pierde el resultado final (una cadena vacía): ¿necesita comillas? Con una línea vacía o ""parece fallar ese caso.
Jonathan Allan
Una cadena vacía no tiene particiones, por lo que en realidad solo da la respuesta incorrecta aquí. Maldición, intentaré arreglarlo.
isaacg
La solución que sugerí para Jelly era concatenar la cadena de entrada con la matriz de entrada aplanada, ¿tal vez puede hacer lo mismo?
Jonathan Allan
@ JonathanAllan Hice algo similar, gracias.
isaacg
Los casos de "", [""]y "", []no han sido cubiertos - no vayamos allí :)
Jonathan Allan
2

Potencia Shell, 61 58 57 bytes

{$s,$l=$_;$l|sort -d length|%{$s=$s.replace($_,'')};+!$s}

Pruébalo en línea!

Viejas soluciones:

{$s,$l=$_;$l|sort -d length|%{$s=$s.replace($_,'')};[int]!$s}
{$s,$l=$_;$l|sort -d length|%{$s=$s.replace($_,'')};0+!$s}  
Andrei Odegov
fuente
Este es casi ilegible, por lo que recomiendo cambiarlo un poco. Estoy bastante seguro de que la mayoría de las personas estarían de acuerdo.
Rɪᴋᴇʀ
Gracias por la explicación de la razón de su corrección de mi solución.
Andrei Odegov,
1

Python 2, 64 bytes

lambda s,l:len(re.findall("^("+"|".join(l)+")*$",s))>0
import re

¡Prueba esto en línea!

Neil
fuente
Creo que esto no funciona totalmente, inténtalo ("aaaaaaa",["aa","aaa"]).
xnor
@xnor lo actualicé. Ven a descubrirlo, regex es perfecto para esto.
Neil
44
Debería fallar ('x', '.'), supongo, pero no lo hace.
Joey
1
@nfnneil ¿Lo hiciste? Tu última edición fue hace 10 horas.
Dennis
1
... o "Hello", ["\w"]etc.
Jonathan Allan
1

PowerShell, 78

$s,$l=$args;!($s-creplace(($l|sort -d length|%{[regex]::escape($_)})-join'|'))

Enfoque bastante directo basado en expresiones regulares.

Joey
fuente
1

CJam (16 bytes)

{Ma+1$,m*:e_\a&}

Este es un bloque anónimo (función) que toma la cadena y la matriz de cadenas en la pila. Demo en línea .

Utiliza el algoritmo obvio:

{        e# Declare a block. Call the args str and arr
  Ma+    e#   Add the empty string to the array
  1$,m*  e#   Take the Cartesian product of len(str) copies of (arr + [""])
  :e_    e#   Flatten each element of the Cartesian product into a single string
  \a&    e#   Intersect with an array containing only str
}

El valor de retorno es una matriz / cadena vacía (falso) si strno se puede hacer, o una matriz que contiene str(verdad, incluso si stres la cadena vacía) si se puede hacer.

Peter Taylor
fuente
@RosLuP, no estoy seguro de lo que quieres decir. Ese caso de prueba en particular se ejecuta tan rápido que en realidad no puedo cronometrarlo. Otros casos de prueba tardan mucho en ejecutarse, pero la especificación no incluye restricciones de tiempo.
Peter Taylor
@RosLuP, demostración en línea . Pero no entiendo cuál es su queja.
Peter Taylor el
1

C ++ (Bcc), 287 bytes

#include<algorithm.h>
f(a,b)char*a,**b;{int i,j,k,v,p[256];if(!a||!b||!*b)return-1;for(v=0;v<256&&b[v];++v)p[v]=v;if(v>=256)return-1;la:for(i=0,j=0;j<v&&a[i];){for(k=0;b[p[j]][k]==a[i]&&a[i];++i,++k);j=b[p[j]][k]?(i-=k),j+1:0;}if(a[i]&&next_permutation(p,p+v)) goto la;return i&&!a[i];}

porque no escribí o usé demasiado la next_permutation () no sé si todo está bien. No sé al 100% si es una solución demasiado, posiblemente esto esté fuera de calidad ... Una lista de cadenas es aquí una matriz de punteros para char; NULL terminado. El algoritmo es fácil, hay un algoritmo que intenta la linealidad si todas las cadenas de la lista encajan con el argumento "a". Hay otro algoritmo que permuta el índice de la lista de cadenas para que intente todas las combinaciones posibles.

deshazte de él, prueba el código y los resultados aquí

#include<stdio.h>
g(a,b)char*a,**b;
{int i,j,k,v,p[256];
 if(!a||!b||!*b) return -1;
 for(v=0;v<256&&b[v];++v) p[v]=v;
 if(v>=256)      return -1; // one array of len >256 is too much
la: 
 for(i=0,j=0;j<v&&a[i];)
   {for(k=0;b[p[j]][k]==a[i]&&a[i];++i,++k); 
    j=b[p[j]][k]?(i-=k),j+1:0;
   } 
 if(a[i]&&next_permutation(p,p+v)) goto la;
 return i&&!a[i];  
}

#define F for
#define P printf

test(char* a, char** b)
{int i;
 P("f(\"%s\",[",a);
 F(i=0;b[i];++i) 
       P("\"%s\"%s", b[i], b[i+1]?", ":"");
 P("])=%d\n", f(a,b));
}

main()
{char *a1="Hello, world!",    *b1[]={"l","He", "o, worl", "d!",      0};//1
 char *a2="la lal al ",       *b2[]={"la", " l", "al ",              0};//1
 char *a3="this is a string", *b3[]={"this should return falsy",     0};//0
 char *a4="thi is a string",  *b4[]={"this", "i i", " a", " string", 0};//0
 char *a5="aaaaa",            *b5[]={"aa",                           0};//0
 char *a6="foo bar foobar",   *b6[]={"foo","bar"," ","spam",         0};//1
 char *a7="ababab",           *b7[]={"a","ba","ab",                  0};//1
 char *a8="",                 *b8[]={"This return 0 even if has to return 1", 0};//0
 char *a9="ababc",            *b9[]={"a","abc", "b", 0};//1

  test(a1,b1);test(a2,b2);test(a3,b3);test(a4,b4);test(a5,b5);test(a6,b6);
  test(a7,b7);test(a8,b8);test(a9,b9);
}

f("Hello, world!",["l", "He", "o, worl", "d!"])=1
f("la lal al ",["la", " l", "al "])=1
f("this is a string",["this should return falsy"])=0
f("thi is a string",["this", "i i", " a", " string"])=0
f("aaaaa",["aa"])=0
f("foo bar foobar",["foo", "bar", " ", "spam"])=1
f("ababab",["a", "ba", "ab"])=1
f("",["This return 0 even if has to return 1"])=0
f("ababc",["a", "abc", "b"])=1

esto se compilaría en el compilador gcc C ++

#include<algorithm>

int f(char*a,char**b){int i,j,k,v,p[256];if(!a||!b||!*b)return -1;for(v=0;v<256&&b[v];++v)p[v]=v;if(v>=256)return -1;la:;for(i=0,j=0;j<v&&a[i];){for(k=0;b[p[j]][k]==a[i]&&a[i];++i,++k);j=b[p[j]][k]?(i-=k),j+1:0;}if(a[i]&&std::next_permutation(p,p+v))goto la;return i&&!a[i];}
RosLuP
fuente
Tengo que amar C ++! :)
MEMark
1

Python, 66 bytes

lambda s,l:s==''or any(x==s[:len(x)]and f(s[len(x):],l)for x in l)

Sin golf:

def f(s,l):
    if s=='': 
        return 1
    for x in l:
        if s.startswith(x) and f(s[len(x):],l):
            return 1
    return 0
RootTwo
fuente
0

Servidor SQL de Microsoft, 353 bytes

u as(select s.n,s collate Latin1_General_BIN s,l collate Latin1_General_BIN l,
row_number()over(partition by l.n order by len(l)desc)r from s,l where s.n=l.n),
v as(select n,s,l,replace(s,l,'')c,r from u where r=1 union all
select u.n,u.s,u.l,replace(v.c,u.l,''),u.r from v,u where v.n=u.n and v.r+1=u.r)
select s,iif(min(c)='',1,0)u from v group by n,s

Pruébelo en línea.

Versión legible:

with s as(
  select n,s
  from(values(1,'Hello, world!'),
             (2,'la lal al '),
             (3,'this is a string'),
             (4,'thi is a string'),
             (5,'aaaaa'),
             (6,'foo bar foobar'),
             (7,'ababab'),
             (8,''))s(n,s)),
l as(
  select n,l
  from(values(1,'l'),(1,'He'),(1,'o, wor'),(1,'d!'),
             (2,'la'),(2,' l'),(2,'al '),
             (3,'this should return falsy'),
             (4,'this'),(4,'i i'),(4,' a'),(4,' string'),
             (5,'aa'),
             (6,'foo'),(6,'bar'),(6,' '),(6,'spam'),
             (7,'a'),(7,'ba'),(7,'ab'),
             (8,'The string can be constructed with nothing!'))l(n,l)),
--The solution starts from the next line.
u as(
  select s.n,
    s collate Latin1_General_BIN s,
    l collate Latin1_General_BIN l,
    row_number()over(partition by l.n order by len(l)desc)r
  from s,l
  where s.n=l.n),
v as(
  select n,s,l,replace(s,l,'')c,r from u where r=1
    union all
  select u.n,u.s,u.l,replace(v.c,u.l,''),u.r
  from v,u
  where v.n=u.n and v.r+1=u.r
)
select s,iif(min(c)='',1,0)u from v group by n,s
Andrei Odegov
fuente
0

C, 140 bytes

Estoy seguro de que hay una forma más corta de hacer esto en C, pero quería crear una solución que pruebe todas las combinaciones posibles de subcadenas en lugar del método habitual de buscar / reemplazar.

char p[999];c,o;d(e,g,l,f)int*e,**g,**l;{c=f&&c;for(l=g;*l;)strcpy(p+f,*l++),(o=strlen(p))<strlen(e)?d(e,g,0,o):(c|=!strcmp(e,p));return c;}

Pruébalo en línea

Sin golf:

#include <string.h>
#include <stdio.h>

char buf[999];
int result;
int temp;

int test(char *text, char **ss, char **ptr, int length) 
{
    if (length == 0)
        result = 0;

    for(ptr = ss; *ptr; ptr++)
    {
        strcpy(buf + length, *ptr);
        temp = strlen(buf);
        if (temp < strlen(text))
        {
            // test recursivly
            test(text, ss, 0, temp);
        }
        else
        {
            if (strcmp(buf, text) == 0)
                result = 1;
        }
    }
    return result;
}

int main()
{
    char *text = "Hello,World";
    char *keywords[] = { "World", "Hello", ",", 0 };
    printf("%d", test(text, keywords, 0, 0));
}
Johan du Toit
fuente