CCM0128 - Computação II (2025i)

Estude inicialmente o enunciado do Web Exercise 4.2.12, Anagrams, de IntroCS,

http://introcs.cs.princeton.edu/java/42sort/

Note que este exercício está sugerido na seção sobre ordenação de IntroCS.  De fato, há uma solução baseada somente em ordenação, e você deve achar interessante descobrir essa solução. Este exercício ocorre também como Web Exercise 1.4.12 em Algs4:

https://algs4.cs.princeton.edu/14analysis/

Sua solução deste exercício deve usar, obrigatoriamente e de forma essencial, tabelas de símbolos para encontrar os conjuntos de anagramas.  Use a classe ST.java.  

Ademais, há alguns requisitos adicionais que seu programa deve satisfazer.  Esses requisitos são descritos a seguir.

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.txt dado abaixo.  Seu programa deve comportar-se da seguinte forma:

$ java-introcs Anagrams < exemplo.txt
+ 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.txt, 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.txt
+ ascent secant stance
$ java-introcs Anagrams 4 < exemplo.txt
$

Formato 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.

Verificação.  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.

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.

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 aos tempos neste arquivo.  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());

Veja o arquivo experiments.txt para verificar o formato esperado da saída.

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.

Para a classe String do Java, veja:

https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/String.html

Sugestões

(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.

(3) Para os detalhes da classe SET<Key>, veja

https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/SET.html

Entrega.  Entregue apenas seu programa Anagrams.java.