9
\$\begingroup\$

I'm a lazy but efficient person, as many of you probably are as well. So, whenever I'm doing something I want to do it with minimal effort. Which is why I'm asking you to solve this problem for me.

What I have here is a document of sorts. On every line of this document is a single word or short phrase. The document is not sorted, but that's ok I know where everything is. I could use some help finding things faster, and for that I need a second list. This is where you come in. For every line of text in this document, I need some identifier. Something I can CTRL+F, but it can't be longer than absolutely necessary for getting that one result.

Example input:

(blank)
an apple
spiderman 3
7pm pick up laundry
tequila
fake mustache
dishes on wednesday
banana
biscuits
(blank)

Example output:

ap,3,7,q,f,w,ba,bi

I'm going to repeat myself here, to make sure we're on the same page:

  • The input is an unformatted text file containing a list of items, separated by line breaks. I have it here in .txt format, it's called "STUFF.TXT"
  • The first and last line of the document are empty. Every other line contains an entry of length >0.
  • The file contains only alfanumeric characters (all lower case), spaces, and line breaks.
  • Desired output is a list of identifiers, in the same order as my original list.
  • I don't want more than one search word for every list item. If there are multiple answers, pick one, I don't care which. In the above example I picked 'ap' for an apple, but you could have picked 'n ', ' a', 'pp', 'pl' or 'le'. Not 'an', because that's in banana.
  • I can assure you, the file is never empty, and it never contains duplicates.
  • If necessary, you can match on the line terminator. But that's a last resort only to be used when there's no other way to distinguish between list items (e.g. 'apple' and 'apples').

Standard loopholes are not allowed. Also, this is code golf so shortest code wins.

One more example:

(blank)
ban
any
king
bean
yen
rake
raki
bar
(blank)

And its output:

ban,ny,g,be,ye,ke,aki,ar
\$\endgroup\$
  • 1
    \$\begingroup\$ @CarpetPython it has to be the shortest possible. Spaces can be in input and output, added that to the question. \$\endgroup\$ – freekvd Mar 30 '15 at 8:41
  • \$\begingroup\$ Can we also use newlines at the beginning of the search term, if one string is a suffix of another? \$\endgroup\$ – Martin Ender Mar 30 '15 at 8:52
  • \$\begingroup\$ @MartinBüttner yes. That's why the document starts and ends with a blank line, so you have those newlines at the start and end of each list item. \$\endgroup\$ – freekvd Mar 30 '15 at 9:09
  • 4
    \$\begingroup\$ I'm pretty sure this problem is NP-complete. I think I can construct a reduction of the exact cover problem to this one. \$\endgroup\$ – FUZxxl Mar 30 '15 at 9:16
  • 4
    \$\begingroup\$ It's more that you won't see any creative solutions as there is no better solution than brute force. \$\endgroup\$ – FUZxxl Mar 30 '15 at 12:01
3
\$\begingroup\$

Pyth, 39 bytes

Lsm.:bdtUbKfT.zj\,mhf!}Yjb-Kk+yky++bkbK

Bruteforces all subsets of every string in increasing length and checks if that string occurs inside any other. If that doesn't work, it will do the same except for all subsets of \nstring\n.

\$\endgroup\$
  • \$\begingroup\$ I get a bad type combination error when I test this. pyth.herokuapp.com/… \$\endgroup\$ – freekvd Apr 1 '15 at 9:17
  • \$\begingroup\$ @freekvd Heroku must have an outdated version of Pyth, because calling .: with first type string and second type int is not an error. Try using Pyth from the repo: github.com/isaacg1/pyth \$\endgroup\$ – orlp Apr 1 '15 at 9:32

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.