Гольф кода: найдите все анаграммы
Слово является анаграммой, если буквы в том слове могут быть перестроены для формирования другого слова.
Задача:
- Самый короткий исходный код счетчиком символов для нахождения всех наборов анаграмм, учитывая список слов.
- Пробелы и новые строки должны считаться как символы
Используйте линейку кода
---------10--------20--------30--------40--------50--------60--------70--------80--------90--------100-------110-------120
Вход:
список слов от 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's plum's
dewar's wader's
postman tampons
dent tend
macho mocha
stoker's stroke's
hops posh shop
chasity scythia
...
У меня есть 149 символьных решений для жемчуга, которые я отправлю, как только еще несколько человек отправляют :)
Развлекайтесь!
Править: Разъяснения
- Предположите, что анаграммы нечувствительны к регистру (т.е. прописные и строчные буквы эквивалентны),
- Только наборы больше чем с 1 объектом должны быть распечатаны
- Каждый набор анаграмм должен только быть распечатан однажды
- Каждое слово в наборе анаграммы должно только произойти однажды
EDIT2: больше разъяснений
- Если два слова отличаются только по капитализации, они должны быть свернуты в то же слово, и Вам решать который план капитализации использовать для свернутого слова
- наборы слов только должны закончиться в новой строке, пока каждое слово разделяется в некотором роде, например, запятая, разделенная, или разделенное пространство допустимо. Я понимаю, что некоторым языкам встроили быстрые методы печати массива, таким образом, это должно позволить Вам использовать в своих интересах это, если это не производит разделенные массивы пространства.
8 ответов
Powershell, 104 97 91 86 83 символа
$k=@{};$input|%{$k["$([char[]]$_|%{$_+0}|sort)"]+=@($_)}
$k.Values|?{$_[1]}|%{"$_"}
Обновление для нового требования ( +8 символов):
Чтобы исключить слова, которые отличаются только заглавными буквами, мы могли бы просто удалить дубликаты (без учета регистра) из входного списка, то есть $ input | sort -u , где ] -u означает -unique . sort по умолчанию не учитывает регистр:
$k=@{};$input|sort -u|%{$k["$([char[]]$_|%{$_+0}|sort)"]+=@($_)}
$k.Values|?{$_[1]}|%{"$_"}
Объяснение [char []] $ _ |% {$ _ + 0} | sort -part
ключ для записи хеш-таблицы, под которой хранятся анаграммы слова. Мое первоначальное решение было: $ _. ToLower (). ToCharArray () | sort . Затем я обнаружил, что мне не нужен ToLower () для ключа, поскольку поиск в хеш-таблице нечувствителен к регистру.
[char []] $ _ | sort было бы идеально, но сортировка символов для ключа должна быть без учета регистра ( в противном случае Cab и abc будут храниться под разными ключами).К сожалению, sort не учитывает регистр символов (только для строк).
Что нам нужно, так это [string []] [char []] $ _ | sort , но я нашел более короткий способ преобразования каждого символа в строку, который заключается в соединении с ним чего-то еще, в данном случае целое число 0 , следовательно, [char []] $ _ |% {$ _ + 0} | sort . Это не влияет на порядок сортировки, и фактический ключ выглядит примерно так: d0 o0 r0 w0 . Это некрасиво, но работает :)
Ruby, 94 символа
h={};(h[$_.upcase.bytes.sort]||=[])<<$_ while gets&&chomp;h.each{|k,v|puts v.join' 'if v.at 1}
Perl, 59 символов
chop,$_{join'',sort split//,lc}.="$_ "for<>;/ ./&&say for%_
Обратите внимание, что для этого требуется Perl 5.10 (для функции say).
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, иначе она могла бы быть короче ...
Он принимает прописные и строчные буквы как разные.
Haskell, 147 символов
предыдущие размеры: 150 159 символов
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
Эта версия обрабатывает:
- Слова во входных данных, которые различаются только регистром, должны считаться только одним словом
- На выходе должна быть одна анаграмма, установленная на строку, но допустимо использование дополнительных знаков препинания.
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])
C ++, 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";}
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]))