9
\$\begingroup\$

Menu Shortcuts

Traditionally, user menus are accessible by keyboard shortcuts, such as Alt + (a letter), or even simply hitting the letter when all textboxes are unfocused (gmail style).

Your task

Given the menu entries as an input, your task is to grant each menu entry a proper shortcut letter.

Write a function or a program that accepts a set of words - the menu entries (as an array of strings, or your language equivalent), and returns a dictionary, or a hashmap, from a single letter to a menu entry.

You can either use a parameter and return a value, or use the STDIN and output your results to STDOUT. You are not allowed to assume a global/scope variable is already populated with the input.

Algorithm to determine the proper letter

  • Basically it's the first available letter of the word. See assumptions and examples below.
  • In case all entry's letters are not available, the shortcut will be (a letter) + (a number). Which letter you pick from the entry is arbitrary. The number should start from 0 and be incremented by 1 - such that all shortcuts are unique. See third example below.

Assumptions

  • The input will be a Set, i.e. no repetitions, every entry is unique.
  • Length of the input can be any non-negative integer (up to MAX_INT of your language).
  • Case sensitivity: Input is case-sensitive, (but will stay unique when ignoring case). The results should contain the original entries with their original casing. However, the output shortcut letters are not case-sensitive.
  • All input words will not end with numbers.
  • No "evil input" will be tested. "Evil input" is such that you have to increment the counter of a certain letter more than 10 times.

Examples

Examples below are in JSON, but you can use your language equivalent for an array and a Dictionary, or - in case you're using STD I/O - any readable format for your input and output (such as csv, or even space-separated values).

1.

Input:  ['File', 'Edit', 'View', 'Help']
Output: {f:'File', e:'Edit', v:'View', h:'Help'}

2.

Input:  ['Foo', 'Bar', 'FooBar', 'FooBars']
Output: {f:'Foo', b:'Bar', o:'FooBar', a:'FooBars'}

3.

Input:  ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']
Output: {a:'a', b:'b', a0:'aa', b0:'bb', q:'bbq', b1:'bbb', b2:'ba'}

Winning conditions

Shortest code wins. Only ASCII is allowed.

\$\endgroup\$
  • \$\begingroup\$ "a" is already taken by the first entry. So for "aa" since both of its letters are already taken up, it gets a0. Same with b0-b2. \$\endgroup\$ – mattacular Jun 1 '14 at 15:45
  • \$\begingroup\$ What happens when you run out of numbers? \$\endgroup\$ – nderscore Jun 1 '14 at 18:57
  • \$\begingroup\$ @nderscore Is that really necessary? \$\endgroup\$ – seequ Jun 1 '14 at 19:03
  • \$\begingroup\$ Should ['ab', 'a'] give {a:'ab', a0:'a'} or {b:'ab', a:'a'}? \$\endgroup\$ – Adám Feb 6 at 11:29
  • \$\begingroup\$ @Adám both are acceptable. It would be easier to implement the former since you scan the input array in an ordered manner, but if for some reason you prefer the latter - go for it. \$\endgroup\$ – Jacob Feb 6 at 12:34
4
\$\begingroup\$

Javascript (ES6) 106 105 100

This function takes input as an an array and outputs a javascript object.

f=i=>i.map(a=>{for(b of c=a.toLowerCase(d=0)+d+123456789)d<!o[e=b>=0?c[0]+b:b]&&(o[d=e]=a)},o={})&&o

Results:

f(['File', 'Edit', 'View', 'Help']);
// {"f":"File","e":"Edit","v":"View","h":"Help"}

f(['Foo', 'Bar', 'FooBar', 'FooBars']);
// {"f":"Foo","b":"Bar","o":"FooBar","a":"FooBars"}

f(['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']);
// {"a":"a","b":"b","a0":"aa","b0":"bb","q":"bbq","b1":"bbb","b2":"ba"}

Ungolfed / Commented:

f=i=>{
  o={};                                        // initialize an object for output
  i.map(a=>                                    // loop through all values in input
    for(b of c=a.toLowerCase(d=0)+d+123456789) // loop through all characters of the string with 0123456789 appended to the end
                                               // and initialize d as 0 to be used as a flag 
      e=b>=0?c[0]+b:b                          // if b is a number, set e to the first character + the number, otherwise b
      if(d<!o[e])                              // if the flag hasn't been triggered and o doesn't have a property e
        o[d=e]=a                               // then store the value at e and trigger the d flag
  )
  return o                                     // return the output object
}
\$\endgroup\$
  • \$\begingroup\$ This is beautiful. It may fail for the evil input ['a', 'aa', 'aaa', 'aaaa', 'aaaaa', 'aaaaaa', 'aaaaaaa', 'aaaaaaaa', 'aaaaaaaaa', 'aaaaaaaaaa', 'aaaaaaaaaaa', 'aaaaaaaaaaaa'], but I think we can ignore such edge cases, can't we? \$\endgroup\$ – Jacob Jun 2 '14 at 13:42
  • \$\begingroup\$ @Jacob And what happens when we hit 11? You can't press the one key twice in a keyboard shortcut :P \$\endgroup\$ – nderscore Jun 2 '14 at 14:28
  • \$\begingroup\$ You have a point there (though it might be possible, given an implementation that waits until end of keystrokes (200ms or so)). Anyhow, I will add to assumptions no such evil input will be tested. \$\endgroup\$ – Jacob Jun 2 '14 at 19:49
2
\$\begingroup\$

Python 2.x - 176 170 157 114 bytes

Very simple approach, but someone has to kick the game going.

r={}
for i in input():a=list(i.upper());r[([c for c in a+[a[0]+`x`for x in range(10)]if c not in r])[0]]=i
print r

Edit 1: Reversed the checking operation and made it set the result only once.
Edit 2: Removed branching.
Edit 3: Removed unnecessary dictionary. (thanks to the added assumption)

Examples:

Input:  ['File', 'Edit', 'View', 'Help']
Output: {'H': 'Help', 'V': 'View', 'E': 'Edit', 'F': 'File'}

Input:  ['Foo', 'Bar', 'FooBar', 'FooBars']
Output: {'A': 'FooBars', 'B': 'Bar', 'O': 'FooBar', 'F': 'Foo'}

Input:  ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']
Output: {'A': 'a', 'B': 'b', 'Q': 'bbq', 'A0': 'aa', 'B0': 'bb', 'B1': 'bbb', 'B2': 'ba'}

I think the only required explanation is the ungolfed code. (This actually is the original version)

items = input() # ['File', 'Edit', 'View', 'Help']
chars = map(chr,range(65,91))
numbers = {}.fromkeys(chars,0)
result = {}
for item in items:
    try:
        key = [c for c in item.upper() if c in chars][0] # causes an exception when no items match
        result[key] = item
        chars.remove(key)
    except:
        key = item[0].upper()
        result[key+`numbers[key]`] = item
        numbers[key] += 1
print result
\$\endgroup\$
  • \$\begingroup\$ I have to say humble thank you to @Jacob. The input format is just great. \$\endgroup\$ – seequ Jun 1 '14 at 17:03
2
\$\begingroup\$

JavaScript (ECMAScript 6) - 107 Characters

f=a=>(o={},p={},[o[[c for(c of l=w.toLowerCase())if(!o[c])][0]||(k=l[0])+(p[k]=p[k]+1|0)]=w for(w of a)],o)

Explanation:

f=a=>(
  o={},                              // The dictionary to output
  p={},                              // Stores record of numbers appended after duplicate
                                     // menu keys
  [                                  // Use array comprehension for each word w of input a
   (unmatchedCharacters
     =[c                             // Use array comprehension for each character c of
      for(c of l=w.toLowerCase())    //   the lower case of word w but only get
      if(!o[c])                      //   those characters which are not already a key in o.
     ],
    key=unmatchedCharacters[0]       // Take the first of those characters
     ||                              // Or if all characters are already in o
     (k=l[0])                        // Take the first character of the lower-case word
     +(p[k]=p[k]+1|0),               //   concatenated with the increment of the digit stored
                                     //   in p (or zero). 
   o[key]=w)                         // Set o to map from this key to the word
   for(w of a)
  ],
  o)                                 // return o

Tests:

f(['File', 'Edit', 'View', 'Help']);
{f: "File", e: "Edit", v: "View", h: "Help"}

f(['Foo', 'Bar', 'FooBar', 'FooBars']);
{f: "Foo", b: "Bar", o: "FooBar", a: "FooBars"}

f(['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']);
{a: "a", b: "b", a0: "aa", b0: "bb", q: "bbq", b1: "bbb", b2: "ba"}
\$\endgroup\$
1
\$\begingroup\$

PHP >= 5.4 - 149 characters

According to PHP's standards (insert sniggers here), the input isn't valid JSON as it uses ' instead of ", so I've been a bit cheeky and I'm using the Input as an actual variable declaration:

<?
$i = ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba'];
$c=[];foreach($i as$w){foreach(str_split($w) as$j)if(!$c[$j]){$x=$j;goto f;}$n=0;do{$x=$w[0].$n++;}while($c[$x]);f:$c[$x]=$w;}echo json_encode($c);

Using the examples:

Input:  ['File', 'Edit', 'View', 'Help']
Output: {"F":"File","E":"Edit","V":"View","H":"Help"}

Input:  ['Foo', 'Bar', 'FooBar', 'FooBars']
Output: {"F":"Foo","B":"Bar","o":"FooBar","a":"FooBars"}

Input:  ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']
Output: {"a":"a","b":"b","a0":"aa","b0":"bb","q":"bbq","b1":"bbb","b2":"ba"}

Un-golfified it's pretty basic:

<?
$i = ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba'];
$c = [];
foreach($i as $w)
{
    foreach(str_split($w) as $j)
        if(!$c[$j])
        {
            $x = $j;
            goto f;
        }
    $n = 0;
    do
    {
        $x = $w[0] . $n++;
    }
    while($c[$x]);
    f: $c[$x] = $w;
}
echo json_encode($c);
\$\endgroup\$
  • \$\begingroup\$ PHP has jump declarations? That's so... 90's. \$\endgroup\$ – seequ Jun 1 '14 at 22:21
  • 2
    \$\begingroup\$ You don't have to stick to JSON, I only provided the examples in JSON, but, as stated in the question, you may choose any readable format for output or use your language equivalent for a Dictionary. (You can save 13 characters by removing the json_encode invocation). \$\endgroup\$ – Jacob Jun 2 '14 at 9:10
  • \$\begingroup\$ echo doesn´t work with arrays; but print_r($c); would do it, saving 9 bytes. \$\endgroup\$ – Titus Sep 14 '16 at 21:03
  • \$\begingroup\$ But this isn´t case insensitive. str_split(strtoupper($w)) and ucfirst($w[0]) can solve that (+21); or $s=strtoupper($w); (+18) \$\endgroup\$ – Titus Sep 14 '16 at 21:11
0
\$\begingroup\$

PHP, 153 bytes

for($c=[];$w=trim(fgets(STDIN));$c[reset(array_diff(str_split($s),array_keys($c)))?:$y]=$w){$s=strtoupper($w);for($n=0;$c[$y=$s[0].$n++];);}print_r($c);

run with php-r '<code>' <<EOF + Enter + <word1>+Enter + <word2>+Enter + ... + EOF+Enter

working on argv for 155 bytes:

$c=[];foreach($argv as$i=>$w)if($i){$s=strtoupper($w);for($n=0;$c[$y=$s[0].$n++];);$c[reset(array_diff(str_split($s),array_keys($c)))?:$y]=$w;}print_r($c);

run with php -r '<code>' <word1> <word2> ...

(-13 bytes with a defined global: foreach($i as$w) instead of foreach($argv as$i=>$w)if($i))

\$\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.