Find all unambiguous prefixes of a set of strings

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 , so the shortest code in bytes will win!

• Does stdout have to be exactly that format? Or can I do key:value\nkey:value\nkey:value... ? – undergroundmonorail May 20 '14 at 13:26
• Rather than redefining the word abbreviation you could just use prefix with its standard meaning. And I think unambiguous conveys the desired property of the keys more effectively than unique, for which my first intuition was that you wanted only one prefix per input word. – Peter Taylor May 20 '14 at 14:05
• @PeterTaylor Good idea; edited. – Doorknob May 20 '14 at 14:53
• May one print the same key multiple times (with the same value)? – xnor May 21 '14 at 8:42

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
• The link is broken now... – user202729 Apr 27 '18 at 12:19

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.  • You could use sum(b.startswith(e) for b in l) instead of len(filter(lambda b:b.startswith(e),l)) – Niklas B. May 20 '14 at 17:21 • You can also shorten b.startswith(e) to b.find(e)==0 or b[:a+1]==e, and check <2 on the count instead of ==1. – xnor May 21 '14 at 8:29 • Also do e=""\n for a in w:\n\te+=a instead of for a in range(len(w)):\n\te=w[:a+1] as it saves 10 chars – WorldSEnder May 22 '14 at 0:59 • I've made an ungolphed version here for anyone that needs it gist.github.com/stuaxo/c371b2d410191a575b763b74719856c8 – Stuart Axon Apr 28 '16 at 10:57 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,  Haskell 96 87 import Data.List i=inits f a=a>>= \x->[(y,x)|y<-i x,y/="",ynotElem(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? • You can replace concatMap by (=<<), which is in the Prelude. Saves you 10 characters. – Rhymoid May 20 '14 at 20:11 • @Rhymoid Thank you. I removed concatMap but I can't save more than 9 characters. – lortabac May 21 '14 at 7:48 • Oh wait, you're right; Haskell considers >>=\  as a single lexeme. Sorry about that... – Rhymoid May 21 '14 at 13:08 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. • (e<w)*S.count(c+e)>1 can be golfed to e<w<w*S.count(c+e) to save 2 characters. – isaacg May 21 '14 at 12:06 • @isaacg Thanks! I've added your optimization. – xnor May 21 '14 at 19:11 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  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"  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"] 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. 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 codegolfgoing codegolfgoing!(codecodcoc;golfgol;goinggoingoi)  returns a dictionary (syntax keys!values). Keys are a list of symbols (symbsymb..), 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 | codecodcoc golf | golfgol going| goinggoingoi  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 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:

for(;a&$s=$argv[++$i];)for($k=+$t="";a&$c=$s[$k++];)echo$t.=$c,":$s,";  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.  • If duplicates in the output are not tolerated, add three bytes to wrap the whole thing in {}ᵘ, unless there's some shorter way to either exclude something form being a prefix of itself, or generate every necessary output pair without the extra rule ∋gj. – Unrelated String May 19 '19 at 22:47 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!

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!

• Um... I don't see any one of the bad characters that you can't use with Adám's SBCS here... :P – Erik the Outgolfer May 22 '19 at 21:12
• without noticing, i've picked the wrong interpreter version again... thanks for halving my byte count :) – ngn May 22 '19 at 23:34

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?

• Maybe I'm missing something, but this seems to alternately add and delete the prefix entry each time it is encountered, so wouldn't an ambiguous prefix appear if it occurs in 3 words? – xnor May 21 '14 at 8:34

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
}


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!

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


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!