Największe forum w sieci o nazwie postcount ++ postanowiło stworzyć nową grę forum. W tej grze celem jest opublikowanie słowa, ale słowo musi mieć jedną literę dodaną, usuniętą lub zmienioną. Twój szef chciał, żebyś napisał program, który zna to słowo, oraz słownik UNIX, gdy pracujesz dla firmy, która ma bardziej inteligentne forum z bardziej inteligentnymi grami forum i chce zniszczyć konkurencję (hej, to twój szef, nie rób tego dyskutuj z nim, i tak dostajesz dużo gotówki z pracy).

Twój program otrzyma dwa argumenty, słowo i słownik. Ponieważ użytkownik zarządzający programem (tak, użytkownik, twoja firma nie ma zasobów do uruchamiania botów) nie jest doskonały, powinieneś normalizować sprawę w obu przypadkach. Słowa w słowniku mogą zawierać litery ASCII (zarówno wielkie, jak i małe, ale należy je zignorować podczas porównania), myślniki, apostrofy i niesekwencyjne spacje na środku. Nie będą dłuższe niż 78 znaków. Musisz wygenerować listę słów, które zostałyby zaakceptowane w grze, aby przerwać zabawę ludziom, którzy myślą o słowach ręcznie.

To jest przykład oczekiwanego programu, sprawdzający podobne słowa do golf.

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

/usr/share/dict/wordsZnajduje się lista słów, z przerwą po każdej linii. Możesz to łatwo odczytać na przykład za pomocą fgets ().

Firma, w której pracujesz, nie ma zbyt wielu kart dziurkaczy (tak, jest rok 2014 i nadal używają kart dziurkaczy), więc nie marnuj ich. Napisz możliwie najkrótszy program. Aha, i zostałeś poproszony o nieużywanie wbudowanych lub zewnętrznych implementacji odległości Levenshteina lub jakiegokolwiek podobnego algorytmu. Coś o Not Invented Here lub backdoorach, które najwyraźniej dostawca wstawił do języka (nie masz na to dowodów, ale nie rozmawiasz z szefem). Więc jeśli chcesz odległość, będziesz musiał ją wprowadzić sam.

Możesz używać dowolnego języka. Nawet z kartami dziurkowanymi firma ma dostęp do najnowocześniejszych języków programowania, takich jak Cobol Ruby lub Haskell lub cokolwiek zechcesz. Mają nawet GolfScript, jeśli uważasz, że jest dobry do manipulacji ciągami (być może nie wiem ...).

Zwycięzca otrzymuje ode mnie 15 punktów reputacji i prawdopodobnie wiele innych punktów od społeczności. Inne dobre odpowiedzi otrzymają 10 punktów, a także punkty od społeczności. Słyszałeś, że punkty są bezwartościowe, ale najprawdopodobniej zastąpią dolary w 2050 roku. Nie zostało to jednak potwierdzone, ale i tak warto zdobyć punkty.

GolfScript, 59 znaków

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

Jasne, GolfScript jest świetny do manipulacji ciągami!

GolfScript nie jest tak dobry w obsłudze argumentów I / O lub argumentów wiersza poleceń. Tak więc, program ten oczekuje na otrzymanie wszystkich danych wejściowych poprzez stdin: pierwsza niepusta linia jest uważana za słowo docelowe, podczas gdy pozostałe linie powinny zawierać słownik. W systemie uniksowym możesz uruchomić ten kod, np .:

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

W moim systemie Ubuntu Linux dane wyjściowe powyższego polecenia są następujące:

goff
wolf
gold
golfs
goof
gulf

Zauważ, że wszystkie słowa są konwertowane na małe litery, a wszelkie duplikaty są eliminowane; dlatego, w przeciwieństwie do twoich danych wyjściowych, moje nie wymienia Wolfi wolfosobno. Na podstawie opisu wyzwania zakładam, że jest to do przyjęcia.

Ponadto kod jest bardzo powolny, ponieważ używa dość brutalnej siły i nie stosuje nawet oczywistych optymalizacji, takich jak sprawdzenie, czy długość słowa kandydującego odpowiada długości słowa docelowego ± 1. Mimo to udaje mu się przez pełną, niefiltrowaną /usr/share/dict/wordslistę w ... um ... Dam ci znać, kiedy się skończy, OK?

^{Edycja: OK, zajęło to około 25 minut, ale zakończyło się.}

Bash + coreutils, 99 bajtów

Albo całkowicie źle zrozumiałem pytanie (odpowiedź @ lambruscoAcido daje bardzo różne wyniki ), albo jest to dość prosta aplikacja wyrażenia regularnego:

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

Wynik:

$ ./similar.sh golf / usr / share / dict / words
Goff
złoto
golf
golfa
głupi
Zatoka
Wilk
Wilk
$ 

Python 3, 291 znaków

Bardzo proste, a zatem niezbyt sprytne. Ale z dużą plątaniną generatora i zoptymalizowaną powolnością. Ponieważ nie chcesz pozostawić przydzielonego czasu obliczeniowego nieużywanego, prawda?

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

Scala - 403 130

[Zaktualizowano]: całkowicie zaktualizowany, ponieważ poprzednie rozwiązanie pozwalało również na permutowane litery. Nie używa wyrażeń regularnych ani żadnych wbudowanych narzędzi.

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

Nie golfowany:

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
}

Stosowanie:

f("golf", io.Source.fromFile("/usr/share/dict/words").getLines.toList)

Python, 174 znaków:

Szybko i na temat.

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

Przykład:

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

Wynik:

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

Podejrzewam, że plik słów OS X zawiera po prostu więcej wpisów.

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

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

Niegolfowany (z kilkoma komentarzami):

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

Przykład użycia (przetestowany w Rebol 3 na 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

Poniżej znajduje się parsereguła stworzona w celu dopasowania podobnych słów do golfa :

[
    skip "golf"
  | "golf" skip
  | skip "o" "l" "f"
  | "olf"
  | "g" skip "l" "f"
  | "glf"
  | "g" "o" skip "f"
  | "gof"
  | "g" "o" "l" skip
  | "gol"
]

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]

Myślę, że całkiem wydajne. Lubię też, jak dobrze grało w golfa w Pythonie.