Крупнейший форум в Интернете под названием postcount ++ решил создать новую форумную игру. В этой игре цель состоит в том, чтобы опубликовать слово, но слово должно быть добавлено, удалено или изменено. Ваш босс хотел, чтобы вы написали программу, которая получит слово, и словарь UNIX, поскольку вы работаете в компании, которая имеет более интеллектуальный форум с более интеллектуальными играми на форумах и хочет уничтожить конкурентов (эй, это ваш босс, не надо обсудить с ним, вы получите много денег с вашей работы в любом случае).

Ваша программа получит два аргумента, слово и словарь. Поскольку пользователь, управляющий программой (да, пользователь, у вашей компании нет ресурсов для запуска ботов) не идеален, вам следует нормализовать ситуацию в обоих случаях. Слова в словаре могут иметь буквы ASCII (как в верхнем, так и в нижнем регистре, но это следует игнорировать при сравнении), тире, апострофы и непоследовательные пробелы в середине. Они не будут длиннее 78 символов. Вы должны вывести список слов, которые будут приняты в игре, чтобы развлечь людей, которые думают о словах вручную.

Это пример вашей ожидаемой программы, проверяющей похожие слова на golf.

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

/usr/share/dict/wordsСписок слов, с разрывом строки после каждого. Вы можете легко прочитать это, например, с помощью fgets ().

Компания, в которой вы работаете, не имеет много перфокарт (да, это 2014, и они все еще используют перфокарты), поэтому не тратьте их впустую. Напишите как можно более короткую программу. О, и вас попросили не использовать встроенную или внешнюю реализацию расстояния Левенштейна или любой подобный алгоритм. Что-то о не изобретенном здесь или бэкдорах, которые, по-видимому, продавец вставил в язык (у вас нет доказательств этого, но вы не обсуждаете это со своим боссом). Так что, если вам нужно расстояние, вам придется реализовать его самостоятельно.

Вы можете свободно использовать любой язык. Даже с перфокартами у компании есть доступ к самым современным языкам программирования, таким как Cobol Ruby или Haskell, или что угодно. У них даже есть GolfScript, если вы думаете, что он хорош для манипуляции со строками (я не знаю, возможно ...).

Победитель получает 15 очков репутации от меня и, вероятно, множество других очков от сообщества. Другие хорошие ответы получат 10 баллов, а также баллы от сообщества. Вы слышали, что очки бесполезны, но, скорее всего, они заменят доларов в 2050 году. Однако это не подтвердилось, но в любом случае неплохо получать очки.

GolfScript, 59 символов

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

Конечно, GolfScript является большим для работы со строками!

В GolfScript не очень хорошо получается обрабатывать файловый ввод / вывод или аргументы командной строки. Таким образом, эта программа ожидает получить весь свой ввод через stdin: первая непустая строка считается целевым словом, а остальные строки должны содержать словарь. В системе Unixish вы можете запустить этот код, например, с помощью:

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

На моем компьютере с Ubuntu Linux вывод команды выше:

goff
wolf
gold
golfs
goof
gulf

Обратите внимание, что все слова преобразуются в нижний регистр, а любые дубликаты удаляются; Таким образом, в отличие от вашего примера вывода, мой не перечисляет Wolfи wolfотдельно. Исходя из вашего описания вызова, я предполагаю, что это приемлемо.

Кроме того, код очень медленный, так как он использует подход довольно грубой силы и не использует даже очевидных оптимизаций, таких как проверка того, что длина слова-кандидата совпадает с длиной целевого слова ± 1. Тем не менее, он действительно может пойти через полный, нефильтрованный /usr/share/dict/wordsсписок в ... хм ... я дам вам знать, когда он закончится, хорошо?

^{Изменить: ОК, это заняло около 25 минут, но это закончилось.}

Bash + coreutils, 99 байт

Либо я полностью неправильно понял вопрос ( ответ @ lambruscoAcido дает совершенно разные результаты ), либо это довольно простое приложение регулярного выражения:

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

Выход:

$ ./simil.sh golf / usr / share / dict / words
Гофф
золото
гольф
гольфы
Лох
залив
волк
волк
$ 

Python 3, 291 символов

Очень простой и, следовательно, не очень умный. Но с большим вкусным клубком генератора и оптимизированной медлительностью. Потому что вы не хотите оставлять выделенное время вычислений неиспользованным, не так ли?

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

Скала - 403 130

[Обновлено]: полностью обновлено, поскольку прежнее решение также допускает перестановочные буквы. Не использует регулярные выражения или какие-либо встроенные инструменты.

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
}

Использование:

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

Python, 174 символа:

Быстро и точно.

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

Пример:

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

Выход:

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

Я предполагаю, что файл слов OS X просто имеет больше записей.

Хаскелл - 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

Реболь - 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 (с некоторыми комментариями):

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

Пример использования (протестировано в Rebol 3 на 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

Ниже приводится parseправило, созданное для сопоставления похожих слов с гольфом :

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

Я думаю, довольно эффективно. Кроме того, мне нравится, насколько хорошо это игра в гольф на Python.