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:

an apple
spiderman 3
7pm pick up laundry
fake mustache
dishes on wednesday

Example output:


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:


And its output:

  • 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, 2015 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\$ Mar 30, 2015 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, 2015 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, 2015 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, 2015 at 12:01

1 Answer 1


Pyth, 39 bytes


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.

  • \$\begingroup\$ I get a bad type combination error when I test this. pyth.herokuapp.com/… \$\endgroup\$
    – freekvd
    Apr 1, 2015 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, 2015 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.