8
\$\begingroup\$

Goal

Sometimes dinner menus can have long winded names. It's much easier for the waiter to write an abbreviation that unambiguously identifies the dish.

For example, given this list:

beef burger
chicken burger
chicken nuggets

The abbreviation c n matches chicken nuggets.
The abbreviation bur matches beef burger and chicken burger.

Write a program of function that identifies one or more items that match an abbreviation.

Input

  1. The abbreviated string to find.
  2. A list of items to search.

You may change this order and use any suitable data types.

Output

  • If the abbreviation does not match any items: Not found
  • If the abbreviation unambiguously matches an item: output the unabbreviated item.
  • If the abbreviation ambiguously matches several items: output a comma separated list of words that would make the selection unambiguous, followed by a question mark. The order is not important. Extra spaces are permitted.

Matching rules

Each word in the abbreviation and the items is considered separately. If an abbreviated word matches the start of an item word, the item is a potential match. If none of an item's words start with any if the abbreviated words, that item is not a match.

Abbreviated words can be in any order.

An abbreviated word cannot be used to match multiple item words and visa-versa.

Abbreviations only match the start of words.

Assume no item will contain all of the words of another item. For example, you will never have beef burger and beef cheese burger.

Test Cases

Given this list:

beef burger
crispy chicken burger
grilled chicken burger
chicken nuggets
chocolate cone
strawberry cone
vanilla cone

These abbreviation give the specified output:

fish           Not found
cones          Not found
chicken cone   Not found
nilla          Not found
v              vanilla cone
be             beef burger
c n            chicken nuggets
b b            beef burger
c b c          crispy chicken burger
c b            crispy,grilled?
bu             beef,crispy,grilled?
            or beef,crispy chicken,grilled chicken?
ch             crispy,grilled,nuggets,cone?
            or crispy chicken,grilled chicken,nuggets,cone?

Scoring

This is code golf. The shortest answer in bytes in 12 days wins acceptance. (I would have made it one week, but I won't be around for that.)

\$\endgroup\$
  • \$\begingroup\$ I'm not certain why An abbreviated word cannot be used to match multiple item words would be important if v matches vanilla cone. \$\endgroup\$ – Dennis Oct 15 '15 at 3:51
  • \$\begingroup\$ Related \$\endgroup\$ – Alex A. Oct 15 '15 at 4:01
  • 1
    \$\begingroup\$ @Dennis, if an abbreviated word matched multiple item words, c b would match crispy chicken burger instead of being ambiguous. When I say "word" I mean a string of characters delimited by a space, so g c b is three words. \$\endgroup\$ – Hand-E-Food Oct 15 '15 at 6:20
  • \$\begingroup\$ If the abbreviation ambiguously matches several items: output a comma separated list of words that would make the selection unambiguous. Does that refer to a word that, by itself, would allow to choose from the matching options, or in addition to the abbreviations? With the first interpretation, crispy,grilled,nuggets,chocolate should be valid for the ch test case? With the second interpretation, chicken,grilled should be valid for the c b test case. What am I missing? \$\endgroup\$ – Dennis Oct 15 '15 at 16:48
  • \$\begingroup\$ Given input b b beef burger battered bacon what would be acceptable output? \$\endgroup\$ – Peter Taylor Oct 15 '15 at 21:05
1
\$\begingroup\$

Python 2 - 181 bytes

It turns the abbreviated string into a regex and attempts to match groups from the search list.

The ternary operation if and elses are 14 bytes. I've tried to cut it down into a list and then accessing one of the items based on the state of r, but don't have anything shorter that this yet.

import re
def s(a,l):
 r=[m.group(1)for e in l for m in[re.compile('^('+a.replace(' ','\w+ ')+'\w+)$').search(e)]if m]
 print','.join(r)+'?'if len(r)>1 else r[0]if r else'Not found'

Call with s(str, list):

s('c n', ['chicken burger', 'chicken nuggets', 'cheeseburger'])
>>> chicken nuggets
s('c n', ['chicken burger', 'chicken nuggets', 'cheeseburger', 'chicken nuggets with sauce', 'foobar'])
>>> chicken nuggets
s('c n', ['chicken burger', 'chicken nuggets', 'cheeseburger', 'chicken nuggets with sauce', 'foobar', 'cfoo nbar'])
>>> chicken nuggets,cfoo nbar?
\$\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.