4
\$\begingroup\$

This challenge is inspired by dmenu, the program I use to launch other programs on my Linux box. To start, for example, GIMP, I simply hit the keyboard shortcut I have assigned to dmenu, type "gimp" and hit enter. However, I don't have to type the whole name. On my machine, if I type "gim", that's enough. Here's how dmenu decides which program to launch when you hit enter1:

  1. Find all program names that contain the input as a substring.
  2. Sort this list alphabetically.
  3. Take the items in the list that begin with the input, and (preserving their order) put them at the beginning.
  4. Launch the first2 program in the list.

While this is usually quite convenient, it is sometimes annoying. For example, on my computer I have chromedriver and chromium. I never want to launch chromedriver, but it's earlier alphabetically than chromium is. If I start typing at the beginning of the word, like I naturally want to do, I have to type six characters to specify that I mean the latter.

However, we don't need to start typing at the beginning of the word! chromium is, alphabetically, the first program name containing the substring iu. I have no programs that start with iu. Therefore, I only need to type those two characters to unambiguously specify which program I want.

For this challenge, your program or function will receive at least two lines of input. No line will contain any whitespace characters (other than the newline, obviously) and the first line is guaranteed to be repeated somewhere in the remaining input. Your program or function will output (stdout, return, etc.) the shortest string that, using dmenu's rules, would find that first line in all the rest. If there are two or more that are tied for shortest, you may output whichever you like.

Examples

In:
bbbb
aaaa
bbbb
cccc

Out:
b

In:
bc
bc
aaaa
bbc

Out:
bc

1: I don't actually know this to be the case, but in my experience it seems to work this way.
2: When actually using dmenu, you can hit left and right to choose different items in the list, but that's irrelevant for this challenge.

\$\endgroup\$
  • 2
    \$\begingroup\$ For example 1, unless I'm misunderstanding things, shouldn't the output be b? \$\endgroup\$ – isaacg May 6 '15 at 21:40
  • \$\begingroup\$ @isaacg Yep, I changed the test and didn't fix the output. mb \$\endgroup\$ – undergroundmonorail May 6 '15 at 22:11
3
\$\begingroup\$

Pyth, 22 21 bytes

hfqzho>xNT0Sf}TY.z.:z

isaacg and me got the same 21 solution more or less at the same time. So he deleted his solution.

Try it online: Pyth Compiler/Executor

Explanation

                         implicit:  z = first input line
                                   .z = all other input lines
 f                .:z   filter all substrings T of z, which satisfy:
            f   .z        filter .z for lines Y, which satisfy:
             }TY            T in Y   
           S              sort these lines alphabetically
     o                    order these lines N by:
      >xNT0                 (index of T in N) > 0
                          (sorting in Pyth is stable, so this brings the lines,                      
                           which start with T, to the beginning
                           without messing up the alphabetically order)
  qzh                     z == first element of ...
h                       print first elment
\$\endgroup\$
  • \$\begingroup\$ hfqzho!!xNTSf}TY.z.:z \$\endgroup\$ – isaacg May 6 '15 at 22:26

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.