15
3
Challenge:
I have thousands of songs in my music collection, and luckily for me, my favorite player has a search function. I also have a great memory—I can remember the title of every song in my collection. However, I'm very lazy and don't like to type—each extra keystroke is a chore!
- What is the shortest string I must search for to isolate one song? Help me memorize a list of keys I can use to minimize typing when searching!
This is code-golf, so shortest code wins.
Rules:
Given an input list of song titles, generate a list of search keys subject to the following constraints:
- Each song title should have a search key.
- The total number of characters in the output list must be as few as possible.
- My favorite music player is foobar2000:
- The search function is not case-sensitive. (
apple
is the same asaPpLE
). - Each search key must consist of one or more "words", in any order, separated by spaces:
- Each word must be a substring of the corresponding song title.
- If the same substring is specified multiple times, then it must occur that many times in its corresponding song title.
- If a substring itself contains a space, then that substring must be surrounded with quotes.
- The search function is not case-sensitive. (
Hints:
- Often, for some song titles, there are multiple search keys meeting rule 2. In such a case, any one key will do, but you get brownie points for listing them all.
- You may assume that the input list will only ASCII characters, but brownie points will be awarded for UTF-8 compatibility.
- Was Rule 3 hard to follow? Here's how it works:
+----------------------+ +--------+ +----------------+ +------------------------------------+
| Input | | Output | | Statistics | | Explanation |
|----------------------| |--------| |----------------| |------------------------------------|
| | | Search | | Key | # of | | |
| Song title | | Key | | length | words | | Why is the output what it is? |
|----------------------| |--------| |--------|-------| |------------------------------------|
| Wanna Be A Wanna Bea | | e e | | 3 | 2 | | ["Wanna Be A Wanna Bea"] |
| | | | | | | | is the only string containing |
| | | | | | | | ["e"] twice |
|----------------------| |--------| |--------|-------| |------------------------------------|
| Wanta Bea A Wanna B | | t ea | | 4 | 2 | | ["Wanta Bea A Wanna B"] |
| | | | | | | | is the only string containing both |
| | | | | | | | ["t"] and ["ea"] |
|----------------------| |--------| |--------|-------| |------------------------------------|
| Wanta Be A Wanna B | | t "e " | | 6 | 2 | | ["Wanta Be A Wanna B"] |
| | | | | | | | is the only string containing both |
| | | | | | | | ["t"] and ['e' preceding a space] |
+----------------------+ +--------+ +----------------+ +------------------------------------+
Total number of characters in output (par): 13
Example:
If my music collection consisted only of two albums, Michael Jackson's Off the Wall and Thriler:
+--------------------------------+ +--------+ +----------------+
| Input | | Output | | Statistics |
|--------------------------------| |--------| |----------------|
| | | Search | | key | # of |
| Song title | | key | | length | words |
|--------------------------------| |--------| |--------+-------|
| Don't Stop 'Til You Get Enough | | Do | | 2 | 1 |
| Rock with You | | Ro | | 2 | 1 |
| Working Day and Night | | Wo | | 2 | 1 |
| Get on the Floor | | Fl | | 2 | 1 |
| Off the Wall | | ff | | 2 | 1 |
| Girlfriend | | lf | | 2 | 1 |
| She's out of My Life | | Sh | | 2 | 1 |
| I Can't Help It | | Ca | | 2 | 1 |
| It's the Falling in Love | | v | | 1 | 1 |
| Burn This Disco Out | | Bu | | 2 | 1 |
| Wanna Be Startin' Somethin' | | nn | | 2 | 1 |
| Baby Be Mine | | Ba | | 2 | 1 |
| The Girl Is Mine | | G M | | 3 | 2 |
| Thriller | | hr | | 2 | 1 |
| Beat It | | Bea | | 3 | 1 |
| Billie Jean | | J | | 1 | 1 |
| Human Nature | | Hu | | 2 | 1 |
| P.Y.T. (Pretty Young Thing) | | . | | 1 | 1 |
| The Lady in My Life | | La | | 2 | 1 |
+--------------------------------+ +--------+ +----------------+
Total number of characters in output (par): 37
You may use the lists above to test your program. Here is the raw version of the second list:
["Don't Stop 'Til You Get Enough","Rock with You","Working Day and Night","Get on the Floor","Off the Wall","Girlfriend","She's out of My Life","I Can't Help It","It's the Falling in Love","Burn This Disco Out","Wanna Be Startin' Somethin'","Baby Be Mine","The Girl Is Mine","Thriller","Beat It","Billie Jean","Human Nature","P.Y.T. (Pretty Young Thing)"]
1Do you have an example that requires multiple strings for a key? – Jonathan Allan – 2017-04-30T01:06:05.377
1How about
["Wanta Be A Wanna B","Wanta Bea A Wanna B","Wanna Be A Wanna Bea"]
? – Jonathan Allan – 2017-04-30T01:11:11.270...but what should they / could they be if no spaces are allowed in the substrings themselves - note that all whole words collide. – Jonathan Allan – 2017-04-30T01:22:05.903
Why is the raw version in a spoiler? – Leaky Nun – 2017-04-30T02:38:45.887
What is the length of the output (and the individual parts) in the multi-string example? What do we do with a (or even multiple) literal
"
in our output parts (or are we guaranteed not to receive input containing them)? – Jonathan Allan – 2017-04-30T03:19:01.910@JonathanAllan The input will never contain a
"
character; each"
in the the output is treated as one extra character. I also updated the example to show how length is counted. – ayane – 2017-04-30T03:41:37.230Example 2 is not optimal,
nt "e "
is shorter. Andnn nn
is the same as justnn
, because you specified no order/multiple rules. – orlp – 2017-04-30T12:23:37.023Just type one character at a time until the one you want is the only one that shows up. – Esolanging Fruit – 2017-05-02T01:57:50.000
1Related – Robert Fraser – 2017-05-02T19:04:44.560
Does the order of the words in the search key matter? That is, would "M G" also be a valid search key for "The Girl is Mine"? – RootTwo – 2017-05-03T18:18:00.080
@RootTwo No, order doesn't matter. – ayane – 2017-05-03T20:31:06.573