10
\$\begingroup\$

Given a string of letters and a set of words, output an ordering of the words so that they can be found in the string by dropping letters that are not needed. Words may occur more than once in the word set. The input string and all words will consist of 1 to 1000 lower case letters each. The letters to be dropped may occur inside words or between words.

Your program or function can accept the letter string and words as lists, a string, or from STDIN, and must output all words in a correct order as a list or string output. If there is more than one correct solution, only output one of them. If there is no possible correct solution, output an empty list or an empty string.

Examples:

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)

This is code golf. Lowest number of bytes wins.

Edit: Explained that extra characters can be inside words.

\$\endgroup\$
  • \$\begingroup\$ Can the input format be one string and then another list of the remaining strings? \$\endgroup\$ – Doorknob Apr 2 '16 at 2:41
  • \$\begingroup\$ @Doorknob, yes, that is fine. Input and output structures are flexible. Added to challenge. \$\endgroup\$ – Logic Knight Apr 2 '16 at 2:46
  • \$\begingroup\$ From the test cases it appears that the dropped letters are always between words. Is that so? You should state that in the challenge, or include a test case with letters dropped within a word \$\endgroup\$ – Luis Mendo Apr 2 '16 at 12:23
  • \$\begingroup\$ I don't understand that third test case; your answer puts cc before bb but the bb and cc substrings only appear once and the bb substring appears first. \$\endgroup\$ – Neil Apr 2 '16 at 18:19
  • \$\begingroup\$ @Neil, in the ccbcb part of the string we output the cc then output bb after dropping the middle c. \$\endgroup\$ – Logic Knight Apr 3 '16 at 1:17
5
\$\begingroup\$

Pyth, 20 24 bytes

My first attempt on Pyth :)

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

How it works:

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

Notes: it takes a long time in the third example (dababbabadbaccbcbaaacdacdbdd aa bb cc dd ba ba ba ab ac da db dc).

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

Pyth, 10 bytes

h@s./Myz.p

Demonstration

This program is very much brute force. It first constructs every subset of the input, then every partition of the subsets, then checks for the first one which is a reordering of the word list. No possibilities is handled via erroring with no output to stdout, which is allowed by meta consensus. The error can be removed for 2 extra bytes.

Note that for many of the given test cases, the program will not complete in a reasonable period of time.

\$\endgroup\$
  • \$\begingroup\$ You missed the second testcase. \$\endgroup\$ – Leaky Nun Apr 2 '16 at 9:53
  • \$\begingroup\$ @KennyLau When I try that case, it simply doesn't return in a reasonable period of time. It doesn't give the wrong answer, however. I think it works. Do you have a test case where it does return an answer, and that answer is wrong? \$\endgroup\$ – isaacg Apr 2 '16 at 9:57
  • \$\begingroup\$ Really nice method. \$\endgroup\$ – Leaky Nun Apr 2 '16 at 10:03
  • \$\begingroup\$ You defeated me. \$\endgroup\$ – Leaky Nun Apr 2 '16 at 10:03
  • \$\begingroup\$ Could you add that to the answer? \$\endgroup\$ – Leaky Nun Apr 2 '16 at 10:04
1
\$\begingroup\$

JavaScript (ES6), 119 bytes

(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)

Accepts a string and an array of words and returns an array of words or undefined on failure. Add 2 bytes if it must return the empty string on failure (?q:``), in which case this alternative version is only 120 bytes and returns the empty string on failure, and can even save 2 bytes if it's allowed to return 0 on failure:

(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:``

(After writing this I noticed that the algorithm is basically the same as @KennyLau's Pyth answer.)

Edited edit: updated after clarification of question, but is now really slow on the third test case; I set it off the night before last and this morning I've just noticed that it has actually found the solution, somewhere between 30 and 40 hours later. I was really mean though and fed the solution to it (it works best with the reversed solution, which it will verify instantly).

\$\endgroup\$
1
\$\begingroup\$

Java 7, 256 bytes

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

It should definitely be possible to golf this more by using a different approach, but this will do for now..

Ungolfed & test code:

Try it here.

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

Output:

dog cat frog 
cat grape fishing 
da ab ba ba ba bb db ac cc aa dd 
\$\endgroup\$
1
\$\begingroup\$

Groovy (44 Bytes)

I can't believe nobody else used regexes for this...

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

Explanation

/${b.join('|')}/ - Create a regex to find any of the words in a string.
.findAll(...) - Find and collect all occurrences in the string into an array.
.join(" ") - Join the array together with spaces.

Basically, if there aren't any occurrences, the array is empty and returns an empty string implicitly. If it does find occurrences, it returns an array object with the occurrences then flattens it into a string.

\$\endgroup\$

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.