17
\$\begingroup\$

Given a dictionary file (a text file containing a word or phrase on each line, with possible punctuation but no numbers; lines are alphabetized), you must output each combination of words where one letter can be removed from a word to make another; the removed letter should be encased in parentheses.

For example, the input

cat
cart
code
golf
ode
verify
versify

should give an output of

ca(r)t
(c)ode
ver(s)ify

Multiple ways to get the same pair must only be displayed once. You can output scra(p)ped or scrap(p)ed, but not both.

The output should be ordered alphabetically by the longer entry;

mart
mar
mat
ma

should have an output of

ma(r)
ma(t)
ma(r)t
mar(t)

and the latter two could be in either order.

The dictionary file may include capitalizations, spaces, hyphens, or apostrophes; these should be ignored. For instance,

inlay 
in-play

should produce in(p)lay. Your output should all be in the same case. Extra whitespace is allowed.

Input can be STDIN or from a file; it is separated by newlines. Output can be return value of a function or STDOUT (or written to a file if you wanted).

This is , so the shortest code in bytes wins.

(This is my first challenge on PPCG - let me know if I've done anything wrong and I'll fix it.)

\$\endgroup\$
  • 3
    \$\begingroup\$ What should be the output for mart mar mat ma? Would it be mar(t) ma(r)t ma(r) ma(t)? \$\endgroup\$ – Sp3000 Sep 28 '15 at 6:51
  • \$\begingroup\$ @Sp: Forgot to specify the order - edited to clarify. \$\endgroup\$ – Deusovi Sep 28 '15 at 6:54
  • \$\begingroup\$ In the first example the word golf isn't in the output. Is that because it's a word that doesn't have other combinations? \$\endgroup\$ – LukStorms Sep 28 '15 at 7:35
  • \$\begingroup\$ @Luk: Yep! For most dictionary files, there will be a lot of words that don't make other words at all - those shouldn't appear anywhere in the output. \$\endgroup\$ – Deusovi Sep 28 '15 at 7:36
  • 2
    \$\begingroup\$ What about allowing a function with a (big) string parameter, returning the requested output as a string array? This put the focus on the algorithm, avoiding the need to manage file I/O. \$\endgroup\$ – edc65 Sep 28 '15 at 8:47
1
\$\begingroup\$

Perl -an0, 101+3 bytes

@F=sort{length$a<=>length$b}map{s/\W//g;lc}@F;map{$`.$'~~@F?print"$`($1)$'\n":$\while/(.)(?!\1)/g}@F;

where

  • @F is the dictionary, stored in an array, provided by runtime flag magic. (b-oost, BoO#@%@#$%$#@T)
  • map{s/\W//g;lc}@F removes all symbols from the words and turns everything lowercase. (boost, boot)
  • sort{length$b<=>length$a} sorts on length. (boot, boost)
  • map{ (...) while/(.)(?!\1)/g}@F matches all characters that aren't followed up by the same character ([b]oot, bo[o]t,boo[t],...)
  • print"$`($1)$'\n" prints the parts that precede, parenthesize, and succeed a match... (boo(s)t)
  • if $`.$'~~@F ...if the concatenation of everything before and after the match is in the dictionary. ([boo]s[t])
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 225

A function with a string parameter, no input from file. I asked OP if this could be valid.

Test running the snippet in an EcmaScript 6 compliant browser (implementing arrow functions, template string, spread operator - Firefox, maybe Safari or MS Edge, not Chrome)

f=t=>t.split`
`.map(w=>(d[k=w.replace(/\W/g,'').toLowerCase()]={},k),d={},r=[]).map(w=>[...w].map((c,i,v)=>(d[v[i]='',x=v.join``]&&!d[x][w]&&r.push(d[x][w]=(v[i]=`(${c})`,v.join``)),v[i]=c)))&&r.sort((a,b)=>a.length-b.length)

// LESS GOLFED

Q=t=>{
  // convert to canonical form and put in a dictionary
  // each value in the dictionary is an hashtable tha will store the list
  // of words that can generate the current word, removing a letter
  d={},
  t=t.split`\n`.map(w=>(k=w.replace(/\W/g,'').toLowerCase(),d[k]={},k))
  r=[], // result array 
  t.forEach(w =>
    [...w].forEach((c,i,v)=>( // for each letter in word, try to remove
      v[i]='', x=v.join``, // build string with missing letter
      v[i]='('+c+')', y=v.join``, // and build string with brackets
      v[i]=c, // restore the current letter
      d[x] && // if the word with removed letter is present in the dictionary
      !d[x][w] && // and not already from the same generating word
         r.push(d[x][w]=y) // update dictionary and add word to result array
    ))
  )
  return r.sort((a,b)=>a.length-b.length) // sort result by length
}  

// TEST
function test() { R.innerHTML=f(I.value) }
textarea { height: 20em }
Test <button onclick="test()">-></button>
<span id=R></span>
<br><textarea id=I>cat
cart
code
golf
node
scraped
scrapped
verify
versify
mart
mar
mat
ma</textarea>

\$\endgroup\$
  • \$\begingroup\$ @ETHproductions right, thx \$\endgroup\$ – edc65 Sep 28 '15 at 15:24
3
\$\begingroup\$

Ruby, 173

->d{o=[]
c={}
d=d.sort_by{|w|[w.size,w]}.map{|w|w=w.upcase.gsub /[^A-Z]/,''
c[w]=l=1
w.size.times{|i|p,x,s=w[0...i],w[i],w[i+1..-1]
c[p+s]&&l!=x&&o<<p+"(#{w[i]})"+s
l=x}}
o}

Test it here: http://ideone.com/86avbe

Readable version here: http://ideone.com/ynFItB

\$\endgroup\$
  • \$\begingroup\$ On mobile so I can't test right now - could you add a test case for the SCRAPPED/SCRAPED one? \$\endgroup\$ – Deusovi Sep 28 '15 at 8:39
  • \$\begingroup\$ @Deusovi That case does not work correctly. I'm fixing it now... \$\endgroup\$ – Cristian Lupascu Sep 28 '15 at 8:42
  • \$\begingroup\$ @Deusovi Updated! \$\endgroup\$ – Cristian Lupascu Sep 28 '15 at 8:51
  • \$\begingroup\$ This answer does not provide correct output for e.g. the ['jacklantern','jackslantern','jack-o-lantern'] dict. \$\endgroup\$ – 14mRh4X0r Sep 28 '15 at 14:46
  • 1
    \$\begingroup\$ @14mRh4X0r can't find that request in the question ... The output should be ordered by the longer entry; ... and the latter two could be in either order. \$\endgroup\$ – edc65 Sep 28 '15 at 15:48
1
\$\begingroup\$

Ruby, 211

I decided I'd take a different approach to solve this, using regex.

->d{o=[]
d.map{|x|x.upcase!.gsub! /[-' ]/,''}
d.map{|x|(x.size+1).times{|i|o+=d.map{|w|w.b.sub! /(#{x[0...i]})(.)(#{x[i..-1]})/,'\1(\2)\3'if w[i]!=w[i+1]}}}
o.compact.sort_by{|w|[w.size,w.gsub(/[()]/,'')]}.uniq}
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 210

The code loads the input in an sorted array, and checks for each value against all values in the array that are 1 byte longer.

map{@W=split//,$w=$_;map{@X=split//,$x=$_;if(@W+1==@X){$i=0;while($W[$i]eq$X[$i]&&$i<@W){$i++}$c=$X[$i];$e=substr($w,$i);print substr($w,0,$i)."($c)$e\n",if substr($x,$i+1)eq$e}}@D}@D=sort(map{s/[^\w]//g;lc}<>)

Test

$ perl dictionairy_same_words.pl dictionairywords.txt
ca(r)t
in(p)lay
ma(r)
ma(t)
mar(t)
ma(r)t
(c)ode
ver(s)ify
\$\endgroup\$
0
\$\begingroup\$

Haskell, 201 bytes

import Data.List
import Data.Char
a#(b:c)=(a,b,c)
g a=[l++'(':m:')':n|x<-a,((l,m,n):_)<-[[o|o@(i,j,k)<-zipWith(#)(inits x)$init$tails x,elem(i++k)a]]]
f=sortOn length.g.map(filter isLetter.map toLower)

I'm not sure what input format is allowed. f takes a list of strings. If only a single string (with nl separated words) is allowed, add .lines to f (+6 bytes).

Usage example:

f ["cat","cart","code","golf","od-e","verify","versify","on","s-o-n","Scrapped","scraped"]

["(s)on","ca(r)t","(c)ode","ver(s)ify","scra(p)ped"]

How it works: turn every word to lowercase and keep only the letters. Split every word x into two parts at every possible position and make triples (i,j,k) where i is the first part, j is the first character of the second part and k is the tail of the second part. Keep the triples where i++k also appears in the word list. If this list is non-empty, take the first element, call it (l,m,n). Turn all those list heads into the required output format by surrounding m with () and putting it between l and n.

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