CCM0128 - Computação II (2022i)

Word ladders.  Veja inicialmente o Web Exercise 4.1.11, Word ladders, de S&W (os programas WordLadder.java e IndexSET.java seguem abaixo). Para as origens de word ladders, inventadas dor Lewis Carroll, veja

https://en.wikipedia.org/wiki/Word_ladder

No Web Exercise 4.1.11 de S&W, há um grafo subjacente (um "word graph"): o grafo em que duas palavras são ligadas por uma aresta se elas têm o mesmo comprimento e diferem exatamente em uma letra. Um word ladder de uma palavra \(s\) para um palavra $t$ é um caminho mais curto nesse grafo.

Word graphs.  O programa WordGraphPlain.java abaixo monta word graphs. O programa WordComponentsPlain.java pode ser usado para verificar a estrutura de componentes desses grafos. Você pode encontrar word ladders usando WordLadderPlain.java, que é uma variante de WordLadder.java em que o word graph é construído usando-se WordGraphPlain.java.

Listas de palavras.  Em nossos exemplos, usamos as listas de palavras em

https://www.ime.usp.br/~yoshi/DATA/5+6_letter_words/

Usamos também a lista

https://www.ime.usp.br/~yoshi/DATA/Pwords

e os arquivos em

https://www.ime.usp.br/~yoshi/DATA/LEIPZIG/

O arquivo Pwords e os arquivos em LEIPZIG contêm palavras de comprimentos variados. Você pode separar essas palavras em listas de palavras de mesmo comprimento usando o programa FilterByLength.java.

Geração mais eficiente de word graphs.  Sua tarefa neste exercício é escrever uma versão mais eficiente de WordGraphPlain.java. Seu programa deve chamar-se WordGraph.java.

O programa WordComponents.java, que usa WordGraph.java em vez de WordGraphPlain.java, pode ser usado para conferir a estrutura de componentes dos grafos gerados por WordGraph.java. Naturalmente, com o mesmo conjunto de palavras, os programas WordComponents.java e WordComponentsPlain.java devem determinar a mesma estrutura de componentes.

O programa WordLadderDeluxe.java é o mesmo que WordLadderPlain.java, a menos do fato de WordLdderDeluxe.java usar WordGraph.java em vez de WordGraphPlain.java. Naturalmente, a diferença de desempenho de WordGraphPlain.java e de WordGraph.java também irá se manifestar ao se comparar WordLadderDeluxe.java e WordLadderPlain.java. Por outro lado, uma vez construído o word graph, as buscas de ladders (caminhos mais curtos no word graph) serão igualmente eficientes.

O desempenho esperado de seu programa WordGraph.java é como ilustrado nos exemplos de execução abaixo. Enquanto que WordGraphPlain.java é quadrático (por quê?), seu WordGraph.java deve ser linear.

Observação. Quando falamos da eficiência de WordGraph.java e de WordGraphPlain.java, referimo-nos à eficiência do construtor WordGraph() e do construtor WordGraphPlain().

Sugestão. Sejam $s$ e $t$ duas palavras diferentes de mesmo comprimento. Seja $s_i$ a palavra que obtemos de $s$ ao remover seu $i$-ésimo caractere, e defina $t_i$ de forma análoga. Note que $s$ e $t$ diferem exatamente no $i$-ésimo caractere se e só se $s_i=t_i$. Use, obrigatoriamente, tabelas de símbolos para montar o word graph de forma eficiente (não use ordenação).

Exemplos de execução

$ java-algs4 WordComponentsPlain < DATA/5+6_letter_words/words5.txt | head -n8
Time to produce wordgraph: 0.124
2415 vertices and 2740 edges
Ave degree: 2.269151138716356
758 components
aback
abase abash abate abuse agate agave amuse awash
abbas
abbey
abbot
abide abode above amide anode aside
abort about amort
abyss
$ java-algs4 WordComponents < DATA/5+6_letter_words/words5.txt | head -n8
Time to produce wordgraph: 0.076
2415 vertices and 2740 edges
Ave degree: 2.269151138716356
758 components
aback
abase abash abate abuse agate agave amuse awash
abbas
abbey
abbot
abide abode above amide anode aside
abort about amort
abyss
$
$ java-algs4 WordComponentsPlain < DATA/5+6_letter_words/words6.txt | head -n8
Time to produce wordgraph: 0.132
2891 vertices and 1182 edges
Ave degree: 0.8177101349014182
1966 components
abacus
abater
abduct
abject adject object
ablate ablaze oblate
aboard
abound around ground
abrade
$ java-algs4 WordComponents < DATA/5+6_letter_words/words6.txt | head -n8
Time to produce wordgraph: 0.086
2891 vertices and 1182 edges
Ave degree: 0.8177101349014182
1966 components
abacus
abater
abduct
abject adject object
ablate ablaze oblate
aboard
abound around ground
abrade
$
$ java-algs4 WordComponentsPlain < DATA/5+6_letter_words/sgb-words5.txt > /dev/null
Time to produce wordgraph: 0.372
5757 vertices and 14135 edges
Ave degree: 4.910543685947542
853 components
$ java-algs4 WordComponents < DATA/5+6_letter_words/sgb-words5.txt > /dev/null
Time to produce wordgraph: 0.129
5757 vertices and 14135 edges
Ave degree: 4.910543685947542
853 components
$

Desempenho.  A diferença de desempenho de WordComponents.java e WordComponentsPlain.java deve ser substancial, como ilustrado nos exemplos acima.

Entrega.  Você deve entregar apenas seu WordGraph.java.