Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

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

8 Answers 8

up vote 4 down vote accepted

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.

share|improve this answer
    
+1 for an accurate representation of how good GolfScript is for string manipulation (and doing string manipulation in GolfScript) –  PlasmaPower Apr 16 at 23:59

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
$ 
share|improve this answer
    
Can you please explain what ${a:b:c} do? –  A.L Apr 15 at 1:33
1  
@n.1 it takes the characters at positions b to c in the variable a –  professorfish Apr 15 at 11:45
2  
@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 –  DigitalTrauma Apr 15 at 16:47
2  
@DigitalTrauma oh I forgot even though I keep using it in my Bash golfs –  professorfish Apr 15 at 17:14

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)))
share|improve this answer
1  
Can use l=len and r=range to reduce those functions further. –  TyrantWave Apr 15 at 9:56
1  
+1 for optimized slowness –  DigitalTrauma Apr 15 at 17:01

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)
share|improve this answer
    
@DigitalTrauma Can you give me an example for that issue? –  lambruscoAcido Apr 14 at 23:25
    
I got it: I also considered all the permutations of the letters. Sigh - so the reality is easier. Thanks... –  lambruscoAcido Apr 14 at 23:28
    
atechny doesn't change one letter. This solution does something unrelated to the question. –  xfix Apr 15 at 5:22
    
+1. looks like it fits the spec better now ;-) –  DigitalTrauma Apr 15 at 17:02
    
A complete program would be nice, not just function. –  swish Apr 16 at 9:53

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.

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

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
share|improve this answer

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"
]
share|improve this answer

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.

share|improve this answer
    
You don't account for removal or adding a character. –  swish Apr 16 at 0:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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