18
\$\begingroup\$

The largest forum on the web, called postcount++ decided to make a new forum game. In this game, the goal is to post the word, but the word has to have one letter added, removed, or changed. Your boss wanted you to write a program which gets the word, and the UNIX dictionary, as you work for company who has more intelligent forum with more intelligent forum games, and wants to destroy the competition (hey, it's your boss, don't discuss with him, you get lots of cash from your job anyway).

Your program will get two arguments, the word, and the dictionary. Because the user managing the program (yes, an user, your company doesn't have resources to run bots) is not perfect, you should normalize the case in both. The words in dictionary may have ASCII letters (both upper-case and lower-case, but it should be ignored during comparison), dashes, apostrophes, and non-consecutive spaces in middle. They won't be longer than 78 characters. You have to output list of words that would be accepted in the game, to break the fun of people who think of words manually.

This is an example of your expected program, checking for similar words to golf.

> ./similar golf /usr/share/dict/words
Goff
Wolf
gold
golfs
goof
gulf
wolf

The /usr/share/dict/words is a list of words, with line break after each. You can easily read that with fgets(), for example.

The company you work in doesn't have much punch cards (yes, it's 2014, and they still use punch cards), so don't waste them. Write as short program as possible. Oh, and you were asked to not use built-in or external implementations of Levenshtein distance or any similar algorithm. Something about Not Invented Here or backdoors that apparently the vendor inserted into the language (you don't have proof of those, but don't discuss with your boss). So if you want distance, you will have to implement it yourself.

You are free to use any language. Even with punch cards, the company has the access to most modern of programming languages, such as Cobol Ruby or Haskell or whatever you want. They even have GolfScript, if you think it's good for string manipulation (I don't know, perhaps...).

The winner gets 15 reputation points from me, and probably lots of other points from the community. The other good answers will get 10 points, and points from community as well. You heard that points are worthless, but most likely that they will replace dolars in 2050. That wasn't confirmed however, but it's good idea to get points anyway.

\$\endgroup\$
5
  • 6
    \$\begingroup\$ We should not "use built-in or external implementations of Levenshtein distance or any similar algorithm"? There goes the 30 character Mathematica solution. \$\endgroup\$ Apr 14, 2014 at 20:04
  • \$\begingroup\$ @MichaelStern and a similarly short python one using the fuzzy matching of this regex library \$\endgroup\$ Apr 14, 2014 at 20:15
  • 2
    \$\begingroup\$ Almost the same as codegolf.stackexchange.com/questions/6939/…. \$\endgroup\$
    – Howard
    Apr 14, 2014 at 21:04
  • \$\begingroup\$ "such as Ruby or Haskell" - ok, I've got it, you want me to participate. \$\endgroup\$ Apr 14, 2014 at 22:18
  • \$\begingroup\$ Please provide a better example, so that all types of changes would appear or people will keep submitting wrong algorithms. \$\endgroup\$
    – swish
    Apr 16, 2014 at 9:44

8 Answers 8

6
\$\begingroup\$

Bash + coreutils, 99 bytes

Either I totally misunderstood the question (@lambruscoAcido's answer gives very different results), or this is a fairly straightforward regexp application:

for((i=0;i<${#1};i++)){
a=${1:0:i}
b=${1:i+1}
egrep -i "^($a$b|$a.$b|$a.${1:i}|$1.)$" $2
}|sort -u

Output:

$ ./similar.sh golf /usr/share/dict/words
Goff
gold
golf
golfs
goof
gulf
wolf
Wolf
$ 
\$\endgroup\$
4
  • \$\begingroup\$ Can you please explain what ${a:b:c} do? \$\endgroup\$
    – A.L
    Apr 15, 2014 at 1:33
  • 1
    \$\begingroup\$ @n.1 it takes the characters at positions b to c in the variable a \$\endgroup\$
    – user16402
    Apr 15, 2014 at 11:45
  • 2
    \$\begingroup\$ @professorfish Close - its the substring of length c starting at position b (zero-based) from variable a. Substring expansion is one of the bash parameter expansions \$\endgroup\$ Apr 15, 2014 at 16:47
  • 2
    \$\begingroup\$ @DigitalTrauma oh I forgot even though I keep using it in my Bash golfs \$\endgroup\$
    – user16402
    Apr 15, 2014 at 17:14
4
\$\begingroup\$

GolfScript, 59 chars

{32|}%"*"%.|(:w;{:x,),{:^[x>.1>]{.[^w=]\+}%{^x<\+w=},},},n*

Sure, GolfScript is great for string manipulation!

What GolfScript is not so good at is handling file I/O or command-line arguments. Thus, this program expects to receive all its input via stdin: the first non-blank line is taken to be the target word, while the remaining lines should contain the dictionary. On a Unixish system, you can run this code e.g. with:

(echo golf; cat /usr/share/dict/words) | ruby golfscript.rb similar.gs

On my Ubuntu Linux box, the output of the above command is:

goff
wolf
gold
golfs
goof
gulf

Note that all the words are converted to lowercase, and any duplicates are eliminated; thus, unlike your sample output, mine does not list Wolf and wolf separately. Based on your challenge description, I assume this is acceptable.

Also, the code is really slow, since it uses a fairly brute force approach, and doesn't use even obvious optimizations like checking that the length of the candidate word matches that of the target word ± 1. Still, it does manage to go through the full, unfiltered /usr/share/dict/words list in... um... I'll let you know when it finishes, OK?

Edit: OK, it took about 25 minutes, but it did finish.

\$\endgroup\$
1
  • \$\begingroup\$ +1 for an accurate representation of how good GolfScript is for string manipulation (and doing string manipulation in GolfScript) \$\endgroup\$ Apr 16, 2014 at 23:59
3
\$\begingroup\$

Python 3, 291 characters

Very straightforward, and thus not very clever. But with a big yummy generator tangle and optimized slowness. Because you don't want to leave your allocated computation time unused, do you?

from itertools import*
from sys import*
a=argv[1].lower()
r,l=range,len
n=l(a)
print('\n'.join((b for b in(s.strip()for s in open(argv[2]).readlines())if l(b)>n-2and b.lower()in(''.join(compress(a,(i!=j for j in r(n))))for i in r(n))or n==l(b)and sum(1for i in r(n)if a[i]!=b.lower()[i])<2)))
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Can use l=len and r=range to reduce those functions further. \$\endgroup\$
    – TyrantWave
    Apr 15, 2014 at 9:56
2
\$\begingroup\$

Python, 174 chars:

Quick and to the point.

import re;from sys import*;w=argv[1]
print"\n".join(set(sum([re.findall(r"\b%s%s?[^'\n]?%s\b"%(w[:i],w[i],w[i+1:]),open(argv[2]).read(),re.I)for i in range(len(w))],[]))-{w})

Example:

python similar.py golf /usr/share/dict/words

Output:

goof
gola
gulf
gold
gol
gowf
goli
Golo
Gulf
goaf
Wolf
Goll
Rolf
wolf
goff
Gold

I suppose the OS X words file just has more entries.

\$\endgroup\$
4
  • \$\begingroup\$ List shouldn't include word itself and also it doesn't ignore apostrophes: with UNIX dictionary it also has golf'. \$\endgroup\$
    – swish
    Apr 16, 2014 at 9:51
  • \$\begingroup\$ What do you mean by ignoring apostrophes? After re-reading the prompt, I still don't see what you are getting at. \$\endgroup\$ Apr 16, 2014 at 21:24
  • \$\begingroup\$ If I run your code on dictionary with golf' in it, it will be printed. \$\endgroup\$
    – swish
    Apr 16, 2014 at 21:34
  • \$\begingroup\$ Ah, I had misread the prompt, but it's fixed now. \$\endgroup\$ Apr 16, 2014 at 21:55
1
\$\begingroup\$

Scala - 403 130

[Updated]: completely updated because former solution also allowed for permuted letters. Does not use regex or any builtin tools.

def f(x:String,d:List[String])={for{y<-d;c=(x zip y filter(t=>t._1!=t._2)length);n=y.length-x.length;if c<2&n==0|c==0&n==1}yield y

Ungolfed:

def f(x:String, d:List[String]) = {
  for {
    y <- d
    c = (x zip y filter (t=>t._1!=t._2) length)  // #letter changes.
    n = y.length-x.length                        // Difference in word length.
    if c<2 & n==0 | c==0 & n==1
  } yield y
}

Usage:

f("golf", io.Source.fromFile("/usr/share/dict/words").getLines.toList)
\$\endgroup\$
5
  • \$\begingroup\$ @DigitalTrauma Can you give me an example for that issue? \$\endgroup\$ Apr 14, 2014 at 23:25
  • \$\begingroup\$ I got it: I also considered all the permutations of the letters. Sigh - so the reality is easier. Thanks... \$\endgroup\$ Apr 14, 2014 at 23:28
  • \$\begingroup\$ atechny doesn't change one letter. This solution does something unrelated to the question. \$\endgroup\$ Apr 15, 2014 at 5:22
  • \$\begingroup\$ +1. looks like it fits the spec better now ;-) \$\endgroup\$ Apr 15, 2014 at 17:02
  • \$\begingroup\$ A complete program would be nice, not just function. \$\endgroup\$
    – swish
    Apr 16, 2014 at 9:53
0
\$\begingroup\$

Haskell - 219

import System.Environment
import Data.Char
u@(x:a)%w@(y:b)|x==y=a%b|1>0=1+minimum[a%w,u%b,a%b]
x%y=max(length x)$length y
main=do[w,d]<-getArgs;readFile d>>=mapM putStrLn.filter((==1).(%map toLower w).map toLower).words
\$\endgroup\$
0
\$\begingroup\$

Rebol - 213

set[i d]split system/script/args" "r:[skip i | i skip]repeat n length? i[append r compose[|(poke s: split i 1 n 'skip s)|(head remove at copy i n)]]foreach w read/lines to-file d[if all[w != i parse w r][print w]]


Ungolfed (with some some comments):

set [i d] split system/script/args " "

; build parse rule
r: [skip i | i skip]       ; RULE - one letter added (prefix and postfix)

; sub-rule for each letter in word
repeat n length? i [
    append r compose [
        | (poke s: split i 1 n 'skip s)     ; RULE - letter changed
        | (head remove at copy i n)         ; RULE - letter removed
    ]
]

foreach w read/lines to-file d [
    if all [w != i parse w r] [print w]
]

Usage example (tested in Rebol 3 on OS X Lion):

$ rebol similar.reb golf /usr/share/dict/words
goaf
goff
gol
gola
Gold
gold
goli
Goll
Golo
goof
gowf
Gulf
gulf
Rolf
Wolf
wolf

Below is the parse rule created to match similar words to golf:

[
    skip "golf"
  | "golf" skip
  | skip "o" "l" "f"
  | "olf"
  | "g" skip "l" "f"
  | "glf"
  | "g" "o" skip "f"
  | "gof"
  | "g" "o" "l" skip
  | "gol"
]
\$\endgroup\$
-1
\$\begingroup\$

Python (103):

f=lambda x:[a for a in open('/usr/share/dict/words')if len(x)==len(a)&sum(b!=c for b,c in zip(a,x))==1]

Quite efficient, I think. Also, I like how well this golfed in Python.

\$\endgroup\$
1
  • \$\begingroup\$ You don't account for removal or adding a character. \$\endgroup\$
    – swish
    Apr 16, 2014 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.