Étant donné une chaîne de lettres et un ensemble de mots, affichez un ordre des mots afin qu'ils puissent être trouvés dans la chaîne en supprimant les lettres inutiles. Les mots peuvent apparaître plusieurs fois dans l'ensemble de mots. La chaîne d'entrée et tous les mots comprendront de 1 à 1 000 lettres minuscules chacune. Les lettres à supprimer peuvent apparaître à l'intérieur des mots ou entre les mots.

Votre programme ou fonction peut accepter la chaîne de lettres et les mots sous forme de listes, une chaîne ou à partir de STDIN et doit générer tous les mots dans un ordre correct en tant que sortie de liste ou de chaîne. S'il existe plusieurs solutions correctes, n'en éditez qu'une seule. S'il n'y a pas de solution correcte possible, affichez une liste vide ou une chaîne vide.

Exemples:

dogcatfrog cat frog dog
-> dog cat frog

xxcatfixsxhingonxgrapexxxfishingcxat cat grape catfish fishing
-> catfish grape fishing cat

dababbabadbaccbcbaaacdacdbdd aa bb cc dd ba ba ba ab ac da db dc
-> da ab ba ba ba cc bb aa ac dc db dd

flea antelope
->
(no solution)

C'est le golf de code. Le plus petit nombre d'octets gagne.

Edit: Expliqué que des caractères supplémentaires peuvent être à l'intérieur des mots.

Pyth, 20 24 octets

Ma première tentative sur Pyth :)

Jcw;FG.ptJI:hJj".*"G0jdG

Comment ça fonctionne:

Jcw;FG.ptJI:hJj".*"G0jdG
Jcw                         assign("J",chop(input()))
    FG.ptJ                  for G in permutations(tail(J)):
          I:hJj".*"G0        if match(head(J),join(".*",G)):
                     jdG      print(join(" ",G))

Remarques: cela prend beaucoup de temps dans le troisième exemple ( dababbabadbaccbcbaaacdacdbdd aa bb cc dd ba ba ba ab ac da db dc).

Pyth, 10 octets

h@s./Myz.p

Manifestation

Ce programme est très brutal. Il construit d'abord chaque sous-ensemble de l'entrée, puis chaque partition des sous-ensembles, puis vérifie la première qui est une réorganisation de la liste de mots. Aucune possibilité n'est gérée via des erreurs sans sortie vers stdout, ce qui est autorisé par le méta consensus. L'erreur peut être supprimée pour 2 octets supplémentaires.

Notez que pour de nombreux cas de test donnés, le programme ne se terminera pas dans un délai raisonnable.

JavaScript (ES6), 119 octets

(s,a,t=``,...r)=>a[0]?a.find((w,i)=>(b=[...a],b.splice(i,1),f(s,b,w+t,w,...r)))&&q:~s.search(t.split``.join`.*`)&&(q=r)

Accepte une chaîne et un tableau de mots et renvoie un tableau de mots ou undefineden cas d'échec. Ajoutez 2 octets si elle doit renvoyer la chaîne vide en cas d'échec ( ?q:``), auquel cas cette version alternative ne fait que 120 octets et renvoie la chaîne vide en cas d'échec, et peut même enregistrer 2 octets si elle est autorisée à retourner 0 en cas d'échec:

(s,a,t=``,...r)=>a[0]?a.reduce((q,w,i)=>q||(b=[...a],b.splice(i,1),f(s,b,w+t,w,...r)),0):~s.search([...t].join`.*`)?r:``

(Après avoir écrit ceci, j'ai remarqué que l'algorithme est fondamentalement le même que la réponse Pyth de @ KennyLau.)

Édition éditée: mise à jour après clarification de la question, mais est maintenant très lente sur le troisième cas de test; Je l'ai déclenché la veille au soir et ce matin, je viens de remarquer qu'il a trouvé la solution, entre 30 et 40 heures plus tard. J'étais vraiment méchant cependant et je lui ai fourni la solution (cela fonctionne mieux avec la solution inversée, qu'elle vérifiera instantanément).

Java 7, 256 octets

import java.util.*;String c(String...a){Map s=new HashMap();int j,i=1,l=a[0].length();for(;i<a.length;i++)if((j=a[0].indexOf(a[i]))>-1)s.put(j,s.get(j)!=null?s.get(j)+" "+a[i]:a[i]);a[0]="";for(j=0;j<l;j++)a[0]+=s.get(j)!=null?s.get(j)+" ":"";return a[0];}

Il devrait certainement être possible de jouer au golf plus en utilisant une approche différente, mais cela fera pour l'instant ..

Code non testé et testé:

Essayez-le ici.

import java.util.*;
class M{
  static String c(String... a){
    Map s = new HashMap();
    int j,
        i = 1,
        l = a[0].length();
    for(; i < a.length; i++){
      if((j = a[0].indexOf(a[i])) > -1){
        s.put(j, s.get(j) != null
                  ? s.get(j) + " " + a[i]
                  : a[i]);
      }
    }
    a[0] = "";
    for(j = 0; j < l; j++){
      a[0] += s.get(j) != null
               ? s.get(j) + " "
               : "";
    }
    return a[0];
  }

  public static void main(String[] a){
    System.out.println(c("dogcatfrog", "cat", "frog", "dog"));
    System.out.println(c("xxcatfixsxhingonxgrapexxxfishingcxat", "cat", "grape", "catfish", "fishing"));
    System.out.println(
        c("dababbabadbaccbcbaaacdacdbdd ", "aa", "bb", "cc", "dd", "ba", "ba", "ba", "ab", "ac", "da", "db", "dc"));
    System.out.println(c("flea", "antelope"));
  }
}

Production:

dog cat frog 
cat grape fishing 
da ab ba ba ba bb db ac cc aa dd 

Groovy (44 octets)

Je ne peux pas croire que personne d'autre n'ait utilisé d'expressions rationnelles pour cela ...

{a,b->a.findAll(/${b.join('|')}/).join(" ")}

Explication

/${b.join('|')}/- Créez une expression régulière pour trouver l'un des mots d'une chaîne.
.findAll(...)- Recherchez et collectez toutes les occurrences de la chaîne dans un tableau.
.join(" ")- Joignez le tableau avec des espaces.

Fondamentalement, s'il n'y a aucune occurrence, le tableau est vide et renvoie implicitement une chaîne vide. S'il trouve des occurrences, il renvoie un objet tableau avec les occurrences, puis l'aplatit en une chaîne.