Подтвердить что ты не робот

Code golf: найти все анаграммы

Слово anagram, если буквы в этом слове могут быть перегруппированы, чтобы сформировать другое слово.

Задача:

  • Самый короткий исходный код по количеству символов, чтобы найти все наборы анаграмм с учетом списка слов.
  • Пробелы и новые строки должны считаться символами
  • Используйте линейку кодов

    --------- 10 -------- 20 -------- 30 -------- 40 -------- 50- ------- 60 -------- 70 -------- 80 -------- 90 -------- 100 ------ -110 ------- 120

Вход:

a список слов из stdin с каждым словом, разделенным новой строкой.

например.

A
A's
AOL
AOL's
Aachen
Aachen's
Aaliyah
Aaliyah's
Aaron
Aaron's
Abbas
Abbasid
Abbasid's

Вывод:

Все наборы анаграмм, причем каждый набор разделяется отдельной строкой.

Пример выполнения:

./anagram < words
marcos caroms macros
lump plum's
dewar wader's
postman tampons
dent tend
macho mocha
stoker stroke's
hops posh shop
chasity scythia
...

У меня есть решение 149 char perl, которое я выложу, как только опубликует еще несколько человек:)

Удачи!

РЕДАКТИРОВАТЬ: Уточнения

  • Предположим, что анаграммы нечувствительны к регистру (т.е. буквы верхнего и нижнего регистра эквивалентны)
  • Должны быть напечатаны только наборы с более чем 1 элементом.
  • Каждый набор анаграмм следует печатать только один раз
  • Каждое слово в наборе анаграмм должно появляться только один раз

EDIT2: Дополнительные разъяснения

  • Если два слова отличаются только капитализацией, они должны быть свернуты в одно и то же слово, и вам решать, какая схема капитализации использовать для спящего слова
  • набор слов должен заканчиваться только в новой строке, если каждое слово разделено каким-либо образом, например. разделенные запятыми или разделенные пробелы. Я понимаю, что некоторые языки имеют встроенные методы печати массива, поэтому это должно позволить вам воспользоваться этим, если оно не выводит массивы, разделенные пробелами.
4b9b3361

Ответ 1

Powershell, 104 97 91 86 83 символа

[email protected]{};$input|%{$k["$([char[]]$_|%{$_+0}|sort)"][email protected]($_)}
$k.Values|?{$_[1]}|%{"$_"}

Обновление для нового требования (+8 символов):

Чтобы исключить слова, которые отличаются только капитализацией, мы могли бы просто удалить дубликаты (без учета регистра) из списка ввода, т.е. $input|sort -u, где -u означает -unique. sort имеет значение по умолчанию:

[email protected]{};$input|sort -u|%{$k["$([char[]]$_|%{$_+0}|sort)"][email protected]($_)} 
$k.Values|?{$_[1]}|%{"$_"} 

Объяснение [char[]]$_|%{$_+0}|sort -part

Это ключ для записи хеш-таблицы, в которой хранятся анаграммы слова. Моим первоначальным решением было: $_.ToLower().ToCharArray()|sort. Тогда я обнаружил, что мне не нужен ToLower() для ключа, так как поиск в хэш-таблице нечувствителен к регистру.

[char[]]$_|sort был бы идеальным, но сортировка символов для ключа должна быть нечувствительной к регистру (иначе Cab и abc будут храниться под разными ключами). К сожалению, sort не учитывает регистр символов (только для строк).

Нам нужно [string[]][char[]]$_|sort, но я нашел более короткий способ преобразования каждой строки char в строку, которая заключается в том, чтобы приложить к ней что-то еще, в этом случае целое число 0, следовательно [char[]]$_|%{$_+0}|sort. Это не влияет на порядок сортировки, и фактический ключ заканчивается чем-то вроде: d0 o0 r0 w0. Это не очень, но это делает работу:)

Ответ 2

Perl, 59 символов

chop,$_{join'',sort split//,lc}.="$_ "for<>;/ ./&&say for%_

Обратите внимание, что для этого требуется Perl 5.10 (для функции say).

Ответ 3

Haskell, 147 символов

предыдущие размеры: 150 159 chars

import Char
import List
x=sort.map toLower
g&a=g(x a).x
main=interact$unlines.map unwords.filter((>1).length).groupBy((==)&).sortBy(compare&).lines

Эта версия на 165 символов удовлетворяет новым, уточненным правилам:

import Char
import List
y=map toLower
x=sort.y
g&f=(.f).g.f
w[_]="";w a=show a++"\n"
main=interact$concatMap(w.nubBy((==)&y)).groupBy((==)&x).sortBy(compare&x).lines

Эта версия обрабатывает:

  • Слова на входе, которые отличаются только случаем, должны считаться только одним словом
  • Вывод должен быть одним набором анаграмм на строку, но допустима дополнительная пунктуация

Ответ 4

Ruby, 94 символа

h={};(h[$_.upcase.bytes.sort]||=[])<<$_ while gets&&chomp;h.each{|k,v|puts v.join' 'if v.at 1}

Ответ 5

Python, 167 символов, включает ввод/вывод

import sys
d={}
for l in sys.stdin.readlines():
 l=l[:-1]
 k=''.join(sorted(l)).lower()
 d[k]=d.pop(k,[])+[l]
for k in d:
 if len(d[k])>1: print(' '.join(d[k]))

Без входного кода (т.е. если мы принимаем список слов уже в списке w), это всего 134 символа:

d={}
for l in w:
 l=l[:-1]
 k=''.join(lower(sorted(l)))
 d[k]=d.pop(k,[])+[l]
for k in d:
 if len(d[k])>1: print(' '.join(d[k]))

Ответ 6

AWK - 119

{split(toupper($1),a,"");asort(a);s="";for(i=1;a[i];)s=a[i++]s;x[s]=x[s]$1" "}
END{for(i in x)if(x[i]~/ .* /)print x[i]}

AWK не имеет функции join, такой как Python, или она может быть короче...

Предполагается, что в верхнем и нижнем регистре используются разные.

Ответ 7

С++, 542 символа

#include <iostream>
#include <map>
#include <vector>
#include <boost/algorithm/string.hpp>
#define ci const_iterator
int main(){using namespace std;typedef string s;typedef vector<s> vs;vs l;
copy(istream_iterator<s>(cin),istream_iterator<s>(),back_inserter(l));map<s, vs> r;
for (vs::ci i=l.begin(),e=l.end();i!=e;++i){s a=boost::to_lower_copy(*i);
sort(a.begin(),a.end());r[a].push_back(*i);}for (map<s,vs>::ci i=r.begin(),e=r.end();
i!=e;++i)if(i->second.size()>1)*copy(i->second.begin(),i->second.end(),
ostream_iterator<s>(cout," "))="\n";}

Ответ 8

Python, O (n ^ 2)

import sys;
words=sys.stdin.readlines()
def s(x):return sorted(x.lower());
print '\n'.join([''.join([a.replace('\n',' ') for a in words if(s(a)==s(w))]) for w in words])