One Letter Swap

Question

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.

Answer 1

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
$ 

Answer 2

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.}

Answer 3

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)))

Answer 4

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.

Answer 5

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)

Answer 6

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

Answer 7

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"
]

Answer 8

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.