Find all unambiguous prefixes of a set of strings

Question

For this challenge, you must implement Ruby's Abbrev module in as little code as possible.

Challenge

• The input will be whatever your language has as an array (array, list, sequence, etc.) of strings. You may write a function, or you may accept comma-separated words on STDIN.

• You must then calculate the set of unambiguous prefixes for those strings. This means you must return a hash (or map, object, etc.) of abbreviations to their original strings.

  • A "prefix" is a substring of the original string starting at the beginning of the string. For example, "pref" is an prefix of the word "prefix."

  • An unambiguous prefix is one that can only mean one word. For example, if your input is car,cat, then ca is not an unambiguous prefix because it could mean either "car" or "cat."

  • The exception to this rule is that a word is always a prefix of itself. For example, if you have input such as car,carpet, car:car must be in your output.

• You can then return the hash/map/object/etc. from your function (or do the equivalent in your language), or print it out to STDOUT in key:value pairs in the form of f:foo,fo:foo,.... (The key-value pairs may also be separated by whitespace if it makes your code shorter.)

Test cases

Input  code,golf,going
Output c:code,co:code,cod:code,code:code,gol:golf,golf:golf,goi:going,goin:going,going:going

Input  pie
Output p:pie,pi:pie,pie:pie

Input  pie,pier,pierre
Output pie:pie,pier:pier,pierr:pierre,pierre:pierre

Input  a,dog
Output a:a,d:dog,do:dog,dog:dog

Rules

• The input will not contain duplicate elements.

• Your output may be in any order; you don't have to sort it.

• You may not use a built-in Abbrev module/function/thing like Ruby's.

• This is code-golf, so the shortest code in bytes will win!

Answer 1

Python 2.7 - 146 141 bytes

l=raw_input().split(',')
for w in l:
 for a in range(len(w)):
    e=w[:a+1]
    if e==w or len(filter(lambda b:b.startswith(e),l))==1:print e+':'+w

Note that the indentation on lines 4 and 5 is not 4 spaces, that's a side effect of SE's markdown interpreter. That's a literal tab character, so only one byte.

This is not technically up to spec, but I'll change it if Doorknob clarifies. It uses newlines instead of commas to separate the output. For example:

$ python2 abbreviations.py <<< code,golf,golfing
c:code
co:code
cod:code
code:code
golf:golf
golfi:golfing
golfin:golfing
golfing:golfing

New: I was able to get rid of 5 characters by assigning the string that I'm checking to a variable e. This means that I only have to type e instead of w[:a] three times. It also means I save characters by doing e=w[:a+1] and changing ...range(1,len(w)+1) to range(len(w)).

---

Explanation:

l=raw_input().split(',') # Gets a line of input from stdin and splits it at every ',' to make a list
for w in l: # For each word in that list...

 for a in range(1,len(w)+1): # For each number a from 1 to the length of that word...

    if (w[:a]==w # w[:a] gets the string w up to the ath index. For example, 'aeiou'[:3] == 'aei'.
                 # We're testing every possible w[:a] to see if it's a unique abbreviation.
                 # However, a word is always its own abbreviation, so we hardcode that in by testing
                 # if w[:a] is the same as w.

or len(filter( # filter takes a function and an iterable as an argument, and returns a list of every
               # element of that iterable where that_function(that_element) returns a True-y value

lambda b:b.startswith(w[:a]),l) # We define an anonymous function that returns True for any string
                                # that begins with our current w[:a]. We filter for words that return
                                # True.

)==1): # If exactly one word returns True for this, it's a unique abbreviation!

     print w[:a]+':'+w # Print the abbreviation, a colon, and the full word.

Answer 2

J - 47 char

(,.~~.@,~[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>)

J sees strings as just vectors of characters, which means that when it tries to make a list of strings it actually ends up making a table of characters, so the ends get padded with spaces. J's solution to this is called the box, so this function takes as argument a boxed list of strings, so as to preserve length.

   'code';'golf';'going'
+----+----+-----+
|code|golf|going|
+----+----+-----+

Also, J lacks a hash type, so the closest it has to that is a two-column table of items, say boxed strings, for instance. If that is unacceptable and I have to default to the key-value form, I can reformat the output to this form in 67 characters total:

;@|.@,@((<&>',:'),."1,.~~.@,[:(#~1-1({.\e."_1]\.){:"1)@;(<,.<\)&.>)

Explanation by explosion:

(,.~~.@,[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>) NB. unambiguous prefixes
                                    (     )&.>  NB. for each string:
                                     <\         NB.   take all prefixes
                                       ,.<      NB.   pair each with string
        [:                         ;            NB. gather up "partial" hashes
          (#~1-                  )@             NB. remove those rows where:
               1({.\        ){."1               NB.   each key
                    e."_1                       NB.   is an element of
               1(        ]\.){."1               NB.   the rest of the keys
 ,.~                                            NB. hash each word to itself
       ,                                        NB. add these rows to hash
    ~.@                                         NB. remove duplicate rows

Examples:

   (,.~~.@,[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>) 'pie';'pier';'pierre'
+------+------+
|pie   |pie   |
+------+------+
|pier  |pier  |
+------+------+
|pierre|pierre|
+------+------+
|pierr |pierre|
+------+------+
   NB. 1-char words have to be made into lists with ,
   (,.~~.@,[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>) (,'a');'dog'
+---+---+
|a  |a  |
+---+---+
|dog|dog|
+---+---+
|d  |dog|
+---+---+
|do |dog|
+---+---+
   NB. "key:value," format, reversed order to save chars
   ;@|.@,@((<&>',:'),."1,.~~.@,[:(#~1-1({.\e."_1]\.){:"1)@;(<,.<\)&.>) 'code';'golf';'going'
goin:going,goi:going,gol:golf,cod:code,co:code,c:code,going:going,golf:golf,code:code,

Answer 3

Haskell 96 87

import Data.List
i=inits
f a=a>>= \x->[(y,x)|y<-i x,y/="",y`notElem`(a>>=i)\\i x||y==x]

Ungolfed version:

 import Data.List
 f a = concatMap (\x ->
     [(y, x) |
      y <- inits x,
      y /= "",
      y `notElem` concatMap inits a \\ inits x || y == x]
     ) a

Example:

> f ["pi","pier","pierre"]
[("pi","pi"),("pier","pier"),("pierr","pierre"),("pierre","pierre")]

I used the inits function, which finds all prefixes of a list/string. Does it count as cheating?

Answer 4

Python 3 (97)

c=','
S=c+input()
for w in S.split(c):
 e=w
 while e:e<w<w*S.count(c+e)or print(e+':'+w);e=e[:-1]

We iterate over prefixes of each word in the input, printing the corresponding prefix/word pair if it either appears exactly once or is to whole word. We take advantage of the short-circuiting behavior of or (and print being a function) to print only if one of these conditions is met.

The while loop repeatedly cuts off the last character to create shorter and shorter prefixes, terminating when the empty string remains. This is the only time we index or slice into anything.

We count the occurrences of the prefix e in the input by searching the original comma-separated input string S for substrings ','+e. We prepend a comma to the input string beaforehand. This addition causes an extra empty string element when we split, but this has no effect because it has no nonempty substrings.

To check for the case when the substring e is the whole word w, we compare them using the string comparison operator. This compares lexicographically, so shorter prefixes are smaller. The double comparison fails if either e==w or S.count(c+e)<2.

If printing outputs in the form e,w were allowed, I'd save a character by writing e+c+w instead.

Credit to undergroundmonorail from whose answer I based my overall code structure.

Answer 5

APL (46)

(Yes, the APL charset does fit in a byte, with room to spare.)

{↑{∆/⍨2=⍴∆←(⊂⍵),∆/⍨⊃¨⍵∘⍷¨∆}¨∪⊃,/{↑∘⍵¨⍳⍴⍵}¨∆←⍵}

This is a function that takes a list of strings, and returns a 2-by-N matrix, where each row contains an unambigous prefix and the word it belongs to:

{↑{∆/⍨2=⍴∆←(⊂⍵),∆/⍨⊃¨⍵∘⍷¨∆}¨∪⊃,/{↑∘⍵¨⍳⍴⍵}¨∆←⍵}'code' 'golf' 'going'
 c      code  
 co     code  
 cod    code  
 code   code   
 gol    golf  
 golf   golf  
 goi    going 
 goin   going 
 going  going 

Explanation:

• ∆←⍵: store the right argument in ∆.
• {↑∘⍵¨⍳⍴⍵}¨∆: for each element of ∆, get the possible prefixes of that element:
  • ⍳⍴⍵: get a list from 1 to the length of ⍵
  • ↑∘⍵¨: for each of those numbers, get that many elements from ⍵.
• ∪⊃,/: concatenate the lists together and take the unique values.
• {...}¨: for each of the unique prefixes:
  • ∆/⍨⊃¨⍵∘⍷¨∆: select the words that start with that prefix
  • (⊂⍵),: also enclose the prefix, and concatenate
  • ∆/⍨2=⍴∆←: only return the list if there are two elements (the prefix and one matching word)
• ↑: turn the list of tuples into a matrix

Answer 6

Ruby, 114

def f(l);h={};l.each{|w|w.size.times{|i|k=w[0..i];h[k]=h[k]&&0||w}};h.delete_if{|k,v|v==0};l.each{|w|h[w]=w};h end

Ungolfed:

def f(list)
  hash = {}
  list.each do |word|
    word.size.times do |i|
      key = word[0..i]
      h[key] = (hash[key] && 0) || word
    end
  end
  hash.delete_if{|key, value| v==0}
  list.each{|word| hash[word] = word}
  hash 
end

Answer 7

k4 (70)

not particularly golfed; i'm sure it could be shorter

pretty similar to the J impl. above, i think -- basically just collects all the (proper) prefixes, removes the words from the prefixes again (to handle the "car"/"carpet" case), groups them into equivalence classes, picks the classes with only one element, reduces them from lists to strings, and adds in the map from strings to themselves.

f:{(x!x),*:'{(&1=#:'x)#x}{x@=y@:&~y in x}.,/'+{1_'(c#,x;(!c:#x)#\:x)}'x}

some test cases

note that in k/q, a string is list of characters, so a string containing only a single character needs to be marked as such using the unary , function; & m.m. w.r.t a list of strings containing only a single string

these use q's show function, which has built-in formatting for some data structures, to make the results more readable:

  .q.show f("code";"golf";"going")
"code" | "code"
"golf" | "golf"
"going"| "going"
,"c"   | "code"
"co"   | "code"
"cod"  | "code"
"gol"  | "golf"
"goi"  | "going"
"goin" | "going"
  .q.show f@,"pie"
"pie"| "pie"
,"p" | "pie"
"pi" | "pie"
  .q.show f("pie";"pier";"pierre")
"pie"   | "pie"
"pier"  | "pier"
"pierre"| "pierre"
"pierr" | "pierre"
  .q.show f(,"a";"dog")
,"a" | ,"a"
"dog"| "dog"
,"d" | "dog"
"do" | "dog"
  .q.show f("car";"carpet")
"car"   | "car"
"carpet"| "carpet"
"carp"  | "carpet"
"carpe" | "carpet"

Answer 8

JavaScript - 212

w=prompt(o=[]).split(",");w.map(function(k,l){for(i=0;++i<k.length;){p=k.slice(0,i);if(w.filter(function(r,t){return t!=l}).every(function(r){return r.indexOf(p)}))o.push(p+":"+k)}o.push(k+":"+k)});console.log(o)

Initial golf.

Input:

code,golf,going

Output:

["c:code", "co:code", "cod:code", "code:code", "gol:golf", "golf:golf", "goi:going", "goin:going", "going:going"]

Answer 9

Perl, 93 77

With newlines and indentation for readability:

sub f{
    (map{
        $h{$x}=[($x=$`.$&,$_)x!$h{$x}]while/./g;
        $_,$_
    }@_),map@$_,values%h
}

A bit too late and too long, but I'm glad it's finally got below 100. Function returns a list which can be assigned to hash variable:

%h = f(qw/code golf going pie pier pierre/);
print "$_ $h{$_}\n" for sort keys %h;

and

perl prefix.pl
c code
co code
cod code
code code
goi going
goin going
going going
gol golf
golf golf
pie pie
pier pier
pierr pierre
pierre pierre

Actually, returned list is not filtered yet - hash construction is completed at the moment of its assignment i.e. outside function. IF it's not clean/fair enough, add 3 to count and put function contents into curly braces, prepending + - then function returns 'true' hash reference.

Answer 10

Q: 44 Bytes

{x!p@'(?0,&:)'p in\:&1=#:'=,/p:`$(-1_)\'$x}

NOTES

• Q language has an inner core named internally K4 (used in this answer and another previously answer to this question)

• To test code, download interpreter (kx.com, free for non-commertial use, support for Windows, Linux, Mac)

Interpreter admits two syntaxes:

• verbose (more readable names, distinct names for moands and diads, more libraries, ...). Load source file with q extension, or interactive interpreter

• compact (functional inner core, one letter operators, same letter for both uses monad/diad, ...). Load source file with k extension, or interactive interpreter in k mode (write \ at prompt). Code must be tested in this mode

The code defines a lambda (anonymous function). To give name to the function we need prefix name: (ex f:{..}), so requires 46 Bytes

TEST

(assumming named function: otherwise substitute f for the code)

f `code`golf`going

`code`golf`going!(`code`cod`co`c;`golf`gol;`going`goin`goi)

returns a dictionary (syntax keys!values). Keys are a list of symbols (`symb`symb..), and values a list of list of symbols. If we execute the sentente at the interactive interpreter, we have a more convenient presentation (each key and associate values at a different line)

code | `code`cod`co`c
golf | `golf`gol
going| `going`goin`goi

EXPLANATION

x is the implicit argument to the lambda

$x convert symbol list to string list

(-1_)\ iterates over each elem of the symbol list

(reads as for each string calculates prefixes (at eat iteration drops last char of the string (-1_), until empty string)

$ transforms to a symbol list again (list of all prefixes)

p: and assigns to p

,/ raze all (concatenates and creates a one-level structure)

= classify -> for each unique prefix, associates the corresponding words

#:' calculates length (number of words associated to each prefix)

1= true if length=1 (unambiguous), false otherwise

& where -> index of true elements

p in\: determines for all prefix if they are in unambiguous prefix

(..)' applies (..) to each value at right (unambiguous prefix)

?0,&: -> distinct 0 concatenated where (to cope words as prefix of itself)

p@ transform indexes to symbols

x!.. construct a dictionary with x (words) as keys, and .. as values

Read as:

• Construct and returns a dictionary with the words as keys, and values ..

• ... values of indexes at distinct positions 0 (all word) and where unambiguous prefix

• ... unambiguous calculated as prefixes that appear only at one word (wordlist associates to each symbols has length one)

• ... lists resulting of classifying all unique symbols with corresponding words

• ... prefixes calculated by repeating drop last char of each word

Answer 11

PHP 7.0, 67 bytes (postdates the challenge)

for(;a&$c=$s[++$k]??($s=$argv[++$i])[$k=+$t=!1];)echo$t.=$c,":$s,";

takes input from command line arguments; prints a trailing comma; run with -nr.

for newer PHP, add one byte: Replace &a with ""<.

for older PHP, use these 70 bytes:

PHP, 70 bytes

for(;a&$s=$argv[++$i];)for($k=+$t="";a&$c=$s[$k++];)echo$t.=$c,":$s,";

Answer 12

Brachylog, 23 bytes

∋Xa₀Y;?↔⟨∋a₀⟩ᶜ1∧Y;X|∋gj

Try it online!

Takes input as a list through the input variable, and generates a list of [key, value] pairs through the output variable. Any input string which is not a prefix of another input string will be generated as a prefix of itself twice, although the header on TIO hides this by using ᵘ to obtain the full list instead of ᶠ.

 X                         X
∋                          is an element of
                           the input variable
    Y                      and Y
  a₀                       is a prefix of
 X                         X.
             ᶜ             The number of ways in which
        ⟨∋  ⟩              an element can be selected from
     ;?↔⟨   ⟩              the input variable
    Y; ↔⟨ a₀⟩              such that it has Y as a prefix
              1            is equal to 1.
               ∧Y          Y is not necessarily 1,
                   |       and the output variable
                Y;X        is the list [Y, X].
                   |       If every choice from the first rule has been taken already,
                           the output variable is
                    ∋      an element of
                   |       the input variable
                     gj    paired with itself.

Answer 13

Perl 5 -a, 76 bytes

map{say"$, $a"if($,=substr$a,0,$_)eq$a||2>grep/^$,/,@F}1..length($a=$_)for@F

Try it online!

Answer 14

APL (Dyalog Classic), 38 bytes

thanks Erik the Outgolfer for reminding me to use a single-byte character encoding

{⊃,/⍵{b,¨⍨(⊂¨⍵~⊃,/a~⊂⍵)∪b←⊂⊂⍺}¨a←,\¨⍵}

Try it online!

Answer 15

Python (127)

So I couldn't comment @undergroundmonorail, but I thought that taking a dictionary approach would be better? I'm sure with some list/dictionary comprehension it could be cut down tremendously too, but can't get it to work with popping from the dict.

i=raw_input().split(",")
d = {}
for x in i:
    for c in range(1,len(x)+1):
        if x[:c] in d:
            del d[x[:c]]
        else:
            d[x[:c]]=x
print d

The print will output the dictionary, unordered.

EDIT: Ahh I missed the car:car / car:carpet criteria. Maybe a length check?

Answer 16

Groovy - 212 chars

Golfed:

c="collectEntries";f="findAll";def g={def h=[:].withDefault{[]};it.each{def w->w.size().times{ h[w[0..it]] << w}};(h."$f"{k,v->v.size()==1}."$c"{k,v->[k,v[0]]}).plus(h."$f"{k,v->v.contains(k)}."$c"{k,v->[k,k]})}

example output:

println g(["code","golf","going"])

[c:code, co:code, cod:code, code:code, gol:golf, golf:golf, goi:going, goin:going, going:going]

Ungolfed:

def g = { def list ->
    def hash = [:].withDefault{[]}
    list.each {
        def word -> word.size().times{ hash[word[0..it]] << word }
    }

    def map = hash.findAll{ k,v -> v.size() == 1 }.collectEntries{ k,v -> [k,v[0]] }
    map.plus(hash.findAll{ k,v -> v.contains(k) }.collectEntries{ k,v -> [k,k] }
    map
}

Answer 17

JavaScript (Node.js), 88 bytes

L=>L.map(s=>[...s].map(c=>L.filter(t=>t>S&t<S+'~',S+=c)[1]&&s>S||(R[S]=s),S=''),R={})&&R

Try it online!

Answer 18

Zsh, 95 bytes

local -A m
for w;{m[$w]=$w;x=
for c (${(s::)w})x+=$c&&[ ${(M)@:#$x*} = $w ]&&m[$x]=$w
}
local m

Try it online!

The only way to "return" an associative array in Bash/Zsh is by declaring it without the local keyword and then accessing it in the parent scope. This would save one byte. However, I/O via variables is generally frowned upon, so we print the array definition instead.

local -A m                          # declare m as associative
                                    # "local" is shorter than "typeset"/"declare"
for w;{                             # for each word
    m[$w]=$w                        # the word is a prefix of itself
    x=                              # ensure x is empty
    for c (${(s::)w})               # for each character in the word
        x+=$c &&                    # append to x (building a prefix
          [ ${(M)@:#$x*} = $w ] &&  # if the only match is the word itself:
          m[$x]=$w                  # ... then x is a prefix of w
}
local m                             # print m

Answer 19

Ruby, 84 bytes

Just noticed there's already an existing Ruby solution, oh well. This basically improves on the old solution by picking prefixes in a smarter way (eliminating the need to add each word as a "prefix" at the end) and counting prefixes to check uniqueness before adding them to the hash, instead of overwriting the value with a dummy if there is a duplicate and then erasing the entry.

->w{h={};w.map{|e|(1..e.size).map{|i|w.count{|d|d[0,i]==e[0,i]}<2?h[e[0,i]]=e:0}};h}

Try it online!