E08 Anagramas
Neste exercício, você resolverá novamente o Web Exercise 4.2.12, Anagrams, de IntroCS,
http://introcs.cs.princeton.edu/java/42sort/
Sua solução deve usar, obrigatoriamente e de forma essencial, tabelas de símbolos para encontrar os conjuntos de anagramas. Ademais, há alguns requisitos adicionais nessa versão desse exercício (veja detalhes abaixo).
Seu programa deve chamar-se Anagrams.java. Seu programa deve receber uma lista de palavras na entrada padrão e deve encontrar os anagramas na lista dada. Por exemplo, considere o arquivo exemplo.in dado abaixo. Seu programa deve comportar-se da seguinte forma:
$ java-introcs Anagrams < exemplo.in
+ aboard abroad
+ ascent secant stance
$
Note que cada linha da saída começa com '+' e contém uma lista de anagramas, com cada anagrama precedido por um espaço. A palavra "starch", que não tem anagrama em exemplo.in, não aparece na saída. Seu programa deve também poder receber um inteiro como argumento de linha de comando. Ao receber um inteiro \(k\), seu programa deve imprimir apenas as linhas que contêm pelo menos $k$ anagramas. Assim, a execução sem argumento de linha de comando é equivalente à execução com argumento $2$. Seguem mais duas execuções de Anagrams.java:
$ java-introcs Anagrams 3 < exemplo.in
+ ascent secant stance
$ java-introcs Anagrams 4 < exemplo.in
$
Ordem da saída. Vamos adotar o seguinte formato rígido para a saída:
(1) As palavras em cada linha devem estar ordenadas em ordem alfabética.
(2) As linhas devem estar ordenadas em ordem alfabética de acordo com a primeira palavra de cada linha: se a linha $l_1$ começa com a palavra $p_1$ e a linha $l_2$ começa com a palavra $p_2$ e $p_1$ vem antes de $p_2$ em ordem alfabética, então $l_1$ deve ocorrer antes de $l_2$ em sua saída.
O programa IsSorted.java abaixo pode ser usado para verificar se a saída de seu programa segue o formato descrito acima (IsSorted.java não verifica se cada linha contém somente anagramas, como exigido neste exercício).
Entrada. Você pode supor que a entrada é constituída de strings separados por espaços e assim você pode ler a entrada assim:
String[] words = StdIn.readAllStrings();
Ordem alfabética. Por simplicidade, neste exercício, interpretamos "ordem alfabética" como a ordem definida pelo método compareTo() da classe String.
Complexidade. Seu programa deve ter complexidade \(O(N\log N)\), onde $N$ é o número de palavras na entrada. (Nesta análise de complexidade, supomos que as palavras na entrada têm tamanho $O(1)$.) Você pode verificar seu programa com as entradas
https://www.ime.usp.br/~yoshi/DATA/5+6_letter_words/words5.txt
https://www.ime.usp.br/~yoshi/DATA/5+6_letter_words/sgb-words5.txt
https://www.ime.usp.br/~yoshi/DATA/5+6_letter_words/words6.txt
https://www.ime.usp.br/~yoshi/DATA/500k_words
https://www.ime.usp.br/~yoshi/DATA/Pwords
As saídas correspondentes aos arquivos acima seguem abaixo.
Generator.java. Você pode usar o programa Generator.java dado abaixo para gerar instância maiores e assim verificar experimentalmente a complexidade de seu algoritmo. Generator.java usa um objeto do tipo SET<String> para evitar duplicações em sua saída. Para a API do tipo SET<Key>, veja
https://introcs.cs.princeton.edu/java/44st/
https://introcs.cs.princeton.edu/java/code/javadoc/SET.html
Note que, em particular, existe o método min() nessa API.
Observação. Executando seu programa nas palavras em 500k_words, a saída deverá conter, por exemplo, as linhas
+ Anglo-chinese shoe-cleaning
+ actuator's autocrat's
+ alumna's manual's
+ aspirant's partisan's
+ self-catering self-creating self-reacting
Na classe String, existe o método de instância toLowerCase(), que será útil neste exercício. Você pode conferir a API da classe String na página
https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/String.html
Exemplos de execução. Exemplos de execução são dados no arquivo experiments.txt. Note que espera-se que seus tempos de execução sejam, grosso modo, comparáveis. Neste arquivo, o MD5 das saídas são dados para que você possa comparar as saídas obtidas com suas saídas. Em sistemas GNU/Linux, você pode calcular o MD5 usando o programa md5sum. No macOS, você pode usar o programa md5.
Tempos de execução. Seu programa deve ser tal que, quando o usuário fornece um inteiro $k$ e mais um outro parâmetro qualquer na linha de comando, são calculados os tempos que o programa levou para (a) ler a entrada, (b) calcular os conjuntos de anagramas, e (c) produzir a saída. Para tanto, basta seu programa conter linhas como
boolean printTimes = args.length > 1;
// ...
Stopwatch sw = new Stopwatch();
// trecho sendo cronometrado
if (printTimes)
System.err.println("Time to ... : " + sw.elapsedTime());
Dica ofuscada. Você deve primeiro descobrir qual é o "truque" para decidir eficientemente se duas palavras são anagrama uma da outra (se as palavras têm comprimento $l$, é possível decidir em tempo $O(l\log l)$). Lembre que existe o método toCharArray() na classe String e que uma das formas do construtor de String recebe um array de caracteres como argumento.
Sugestões. Sugere-se fortemente o seguinte:
(1) Coloque as palavras que constituem um conjunto de anagramas em um conjunto de strings (isto é, em um objeto de tipo SET<String>). Organize o conjunto de tais "conjuntos de anagramas" em uma tabela de símbolos de tipo ST<String, SET<String>>, usando uma chave "adequada".
(2) Para montar a saída na ordem exigida, use uma outra tabela de símbolos de tipo ST<String, SET<String>> com os conjuntos de anagramas computados, mas agora indexado por uma outra chave.
Entrega. Entregue apenas seu programa Anagrams.java.
- 3 de diciembre de 2023, 19:52
- 3 de diciembre de 2023, 19:52