¡Mis [sub] cuerdas se esconden!

21

Introducción

Hace un tiempo, un usuario SO perdido publicó una pregunta aquí y ahora se ha eliminado, pero creo que sería un buen desafío, así que aquí va ...

Reto

Escriba un programa o función completa que tome dos cadenas y verifique si alguna permutación de la primera cadena es una subcadena de la segunda cadena.

Entrada

Dos cadenas, una cadena y una subcadena para probar (puede elegir el orden).

Salida:

Un valor verdadero si la cadena contiene alguna permutación de la subcadena.
Un valor falso si la cadena no contiene permutaciones de la subcadena.
La prueba distingue entre mayúsculas y minúsculas.

Ejemplos / casos de prueba

         sub-string    string          
input    d!rl          Hello World!
output   truthy

input    Pog           Programming Puzzles & Code Golf
output   falsey

input    ghjuyt        asdfhytgju1234
output   truthy
Notts90
fuente
¿Deben ser consistentes los valores de veracidad y falsey o simplemente de verdad o falsey?
Erik the Outgolfer
@EriktheOutgolfer simplemente apropiado está bien.
Notts90

Respuestas:

14

Brachylog , 2 bytes

sp

Pruébalo en línea!

Explicación

Input variable = "Hello World!", Output variable = "d!rl"

(?)s        Take a substring of the Input variable
    p(.)    It is a permutation of the Output variable
Fatalizar
fuente
44
Herramienta adecuada para el trabajo.
isaacg
7

JavaScript (ES6), 77 bytes

(s,t)=>t&&[...t.slice(0,s.length)].sort()+''==[...s].sort()|f(s,t.slice(1))

Devuelve 1 o 0.

Retazo

f=

(s,t)=>t&&[...t.slice(0,s.length)].sort()+''==[...s].sort()|f(s,t.slice(1))

console.log(f('d!rl','Hello World!'))                   //1
console.log(f('Pog','Programming Puzzles & Code Golf')) //0
console.log(f('ghjuyt','asdfhytgju1234'))               //1

Rick Hitchcock
fuente
2
Esto es mucho más rápido que las versiones que usan permutaciones.
David Conrad
6

Python 2, 67 66 bytes

Toma la entrada como dos cadenas, la subcadena primero.

a=sorted
lambda s,S:a(s)in[a(S[n:n+len(s)])for n in range(len(S))]
TFeld
fuente
1
Guarde un byte nombrando sorted.
Jonathan Allan
6

05AB1E , 3 bytes

όZ

Pruébalo en línea!

-1 byte gracias a Emigna .

Explicación:

όZ 2 inputs
œ                  permutations of the first input
 å  Is each of the                                 in the second input?
  Z Take the maximum of the resulting boolean list
Erik el Outgolfer
fuente
No creo que lo necesites.
Emigna
No estoy seguro de si es mi teléfono, pero TIO parece roto, dice el idioma no encontrado.
Notts90
@ Notts90 Es TIO v2 no TIO Nexus, intente borrar su caché. Esto funciona para mi.
Erik the Outgolfer
@Emigna Aparentemente "vectorizado" significa el segundo argumento, no el primero ...
Erik the Outgolfer
2
Si tan solo pusieras el tachado 4
Neil A.
5

Java 8, 266 244 bytes

import java.util.*;Set l=new HashSet();s->p->{p("",p);for(Object x:l)if(s.contains(x+""))return 1>0;return 0>1;}void p(String p,String q){int n=q.length(),i=0;if(n<1)l.add(p);else for(;i<n;)p(p+q.charAt(i),q.substring(0,i)+q.substring(++i,n));}

Explicación:

Pruébalo aquí

java.util.*;                   // Required import for Set and HashSet

Set l=new HashSet();           // Class-level Set

s->p->{                        // Method (1) with two String parameters and boolean return-type
  p("",p);                     //  Put all permutations in the class-level Set
  for(Object x:l)              //  Loop over the permutations:
    if(s.contains(x+""))       //   If the input String contains one of the permutations:
      return 1>0;//true        //    Return true
                               //  End of loop (implicit / single-line body)
  return 0>1;//false           //  Return false
}                              // End of method (1)

void p(String p,String q){     // Method (2) with two String parameters and no return-type
  int n=q.length(),i=0;        //  Two temp integers
  if(n<1)                      //  If `n` is zero:
    l.add(p);                  //   Add this permutation of the String to the Set
  else                         //  Else:
    for(;i<n;                  //   Loop over `n`
      p(p+q.charAt(i),q.substring(0,i)+q.substring(++i,n))
                               //    Recursive-call with permutation parts
    );                         //   End of loop (no body)
}                              // End of method (2)
Kevin Cruijssen
fuente
En C # un vacío lambda es en Action<params>lugar de Func<params, returnVal>. Supongo que sería algo similar.
TheLethalCoder
1
@TheLethalCoder Tienes razón. Debería usar Consumery en accept(...)lugar de Functiony apply(...)cuando quiero tener una lambda con un parámetro y sin tipo de retorno. Actualmente estoy aprendiendo Java 8. :) Pero como tendré que cambiar void p(String p,String q), p("",p);y p(p+q.ch...,q.sub...)para p->q->, p.apply("").accept(p);y p.apply(p+q.ch...).accept(q.sub...)es más corto usar una combinación de lambda para el método principal, y solo un void p(String p,String q)método Java 7 para el método recursivo.
Kevin Cruijssen
Bien
Usé un Function<String, Predicate<String>>en el mío.
David Conrad
5

Jalea , 5 bytes

Œ!ẇ€Ṁ

Pruébalo en línea!

-1 gracias a Emigna por animarme a reintentar el golf.

Explicación:

Œ!ẇ€Ṁ Main link, dyadic
Œ!               the permutations of the left argument
  ẇ€  Is each of                                      in the right argument?
    Ṁ Maximum of boolean values 
Erik el Outgolfer
fuente
5

Japt, 10 7 bytes

á d!èV

Pruébalo en línea


Explicación

á d@VèX  
         :Implicit input of (sub)string U
á        :Create an array of all possible permutations of U
  d      :Map over the array, checking if any element returns true for...
   @     :the function that checks..
     è   :the number of matches...
      X  :of current element (permutation) X...
    V    :in main string V.
         :(0 is falsey, anything else is truthy)
         :Implicit output of result
Lanudo
fuente
4

Python , 60 bytes

Una forma alterada de la respuesta de TFeld : ¡ve a dar algo de crédito!

s=sorted
f=lambda u,t:s(u)==s(t[:len(u)])or t and f(u,t[1:])

Función recursiva que devuelve el booleano True(verdadero) o una cadena vacía (falso).

Pruébalo en línea!

clasifica la subcadena, uy la misma longitud del frente de la cadena, t(usando un corte t[:len(u)]) si son iguales y luego Truese devuelve, de lo contrario si taún es verdadero (no está vacío) se repite con un dequeued t(usando un corte t[1:]) . Si tse vacía, andno se ejecuta y tse devuelve este vacío .

Jonathan Allan
fuente
También puede tener lambda como parámetro: lambda u,t,s=sorted:para una línea, sin embargo, no se guarda ningún byte
Rod
@cat la asignación es necesaria ya que la función es recursiva.
Jonathan Allan
4

Pyth, 9 8 bytes

sm}dQ.pE

-1 byte gracias a @Erik_the_Outgolfer

Toma dos cadenas citadas, la segunda de las cuales es la subcadena.

¡Intentalo!

KarlKastor
fuente
OP dijo que puede ser simplemente verdadero / falso, no necesariamente consistente, por lo que puede usarlo en slugar de }1.
Erik the Outgolfer
3

Mathematica, 55 50 bytes

-5 bytes del usuario202729

StringFreeQ[#2,""<>#&/@Permutations@Characters@#]&

Devuelve Falsesi una permutación de la primera entrada está en la segunda cadena. Devuelve Truesi una permutación de la primera entrada no está en la segunda cadena.

Explicación:

                                    Characters@#   - split first string into array of characters
                       Permutations@               - make all permutations
               ""<>#&/@                            - join each array of characters together to form a single string
StringFreeQ[#2,                                 ]& - Check if any of these string is in the second input string
Ian Miller
fuente
El resultado solo debe ser "verdadero / falso", no literal True/ False.
Ian Miller
Gracias por recordarlo Characters.
Ian Miller
3

CJam , 13 12 bytes

le!lf{\#)}:+

Pruébalo en línea!

Siento que CJam es realmente limitado en comparación con otros idiomas de golf, pero tal vez solo soy yo siendo malo ...

Estoy pensando en mudarme a otro. 05AB1E parece divertido.

Se corrigió un pequeño error gracias a Erik the Outgolfer.
Cortó una mordida porque los números que no son cero son verdaderos

Explicación:

l                 Read substring
 e!               Generate all permutations
   l              Read string
    f{            For each permutation
      \#            Check if it is in the string (returns -1 if not found)
        )           Add one
         }        End for
          :+      Sum the whole found/not found array
FrodCube
fuente
Creo que esto no es válido, ¿qué pasa con las entradas ay abc?
Erik the Outgolfer
@EriktheOutgolfer Tienes razón. Debería ser un> = 0 en lugar de> 0
FrodCube
1
Pero puedes hacer W>.
Erik the Outgolfer
¿@EriktheOutgolfer se le!lf{\#)}:+consideraría una solución válida? Debería salir 0si la cadena no se encuentra y algún número positivo de lo contrario. ¿Es válido un número distinto de cero truthy?
FrodCube
Puede usar en )lugar de W>, según la aclaración de OP.
Erik the Outgolfer
3

Java 9 JShell , 160 bytes

p->q->IntStream.range(0,q.length()-p.length()+1).anyMatch(
    i->Arrays.equals(
        q.substring(i,i+p.length()).chars().sorted().toArray(),
        p.chars().sorted().toArray()))

(líneas nuevas insertadas para facilitar la lectura)

Pruébalo en línea!

Nota: JShell incluye varias importaciones por defecto. Como una solución Java 8 o Java 9, sería necesario importar:

import java.util.*;import java.util.stream.*;

Para 45 bytes adicionales, o 205 bytes en total. El enlace TIO anterior es a un programa Java 9 ya que TIO actualmente no tiene JShell (y no tengo claro cómo JShell funcionaría en TIO).

David Conrad
fuente
Java 9 es una cosa ahora? : |
CalculatorFeline
@CalculatorFeline Las compilaciones de acceso temprano han estado disponibles durante bastante tiempo, pero la fecha de lanzamiento oficial es 2017-07-27 .
David Conrad
2

C #, 320 bytes

using System.Linq;s=>u=>p(u.ToArray(),0,u.Length-1).Any(p=>s.Contains(p));w=(c,a,b)=>{if (a!=b)(var t=c[a];c[a]=c[b];c[b]=t;)};System.Collections.Generic.IEnumerable<string>p(char[]l,int k,int m){if(k==m)yield return new string(l);else for(int i=k;i<=m;){w(l,k,i);foreach(var c in p(l,k+1,m))yield return c;w(l,k,i++);}}

Estoy seguro de que calcular las permutaciones puede ser mucho más corto, pero no puedo ver cómo en este momento.

Versión formateada / completa:

void test()
{
    Func<string, Func<string, bool>> f = s => u =>
        p(u.ToArray(), 0, u.Length - 1).Any(p => s.Contains(p));

    Console.WriteLine(f("Hello World!")("d!rl"));
    Console.WriteLine(f("Programming Puzzles & Code Golf")("Pog"));
    Console.WriteLine(f("asdfhytgju1234")("ghjuyt"));
}

System.Collections.Generic.IEnumerable<string>p(char[] l, int k, int m)
{
    Action<char[], int, int> w = (c, a, b) =>
    {
        if (a != b)
        {
            var t = c[a];
            c[a] = c[b];
            c[b] = t;
        }
    };

    if (k == m)
        yield return new string(l);

    else
        for (int i = k; i <= m;)
        {
            w(l, k, i);

            foreach (var c in p(l, k + 1, m))
                yield return c;

            w(l, k, i++);
        }
}
TheLethalCoder
fuente
sí, desafortunadamente, usar linq a menudo hace las cosas más largas que simples para (..) {}
Ewan
2

Perl 6 , 48 bytes

{$^a.contains(any $^b.comb.permutations».join)}

Devuelve una unión o de la presencia de cada permutación como una subcadena. Por ejemplo, con argumentos "Hello World!"y "d!l", devuelve:

any(False, False, False, False, True, False)

... que "colapsa" Trueen un contexto booleano. Es decir, las uniones son valores verdaderos.

Sean
fuente
2

PHP> = 7.1, 91 bytes

for([,$x,$y]=$argv;~$p=substr($y,$i++,strlen($x));)$t|=($c=count_chars)($x)==$c($p);echo$t;

Casos de prueba

Jörg Hülsermann
fuente
1
Intenta en ~$plugar de a&$p.
Titus
Cuando intento ejecutar su código usando el enlace dice inesperado ,
Notts90
@ Notts90 Utilice una versión de PHP superior a la 7.1
Jörg Hülsermann
@ JörgHülsermann que funciona, había predeterminado a
7.0.3
1

Haskell, 54 bytes

import Data.List
s#t=any(`isInfixOf`s)$permutations t

Usando el poder de Data.List para ambos isInfixOf, así como permutations.

eje de arce
fuente
1

R , 103 bytes

function(w,x,y=u(w),z=u(x)){for(i in 1:n(w)){F=F|!sum(setdiff(y[1:n(x)+i-1],z))};F}
u=utf8ToInt
n=nchar

Pruébalo en línea!

Vuelve TRUEpor veracidad y NApor falsey.

ngm
fuente