Isso foi escrito como parte do primeiro envio periódico de quebra-cabeças de programação Premier .
O jogo
Uma palavra inicial e final do mesmo tamanho é fornecida. O objetivo do jogo é alterar uma letra na palavra inicial para formar uma palavra válida diferente, repetindo esta etapa até que a palavra final seja alcançada, usando o menor número possível de etapas. Por exemplo, dadas as palavras TREE e FLED, a saída seria:
TREE
FREE
FLEE
FLED
2
Especificações
- Os artigos da Wikipedia para OWL ou SOWPODS podem ser um ponto de partida útil na lista de palavras.
- O programa deve oferecer suporte a duas maneiras de selecionar as palavras inicial e final:
- Especificado pelo usuário via linha de comando, stdin ou qualquer outro que seja adequado ao seu idioma de escolha (apenas mencione o que você está fazendo).
- Selecionando 2 palavras aleatoriamente no arquivo.
- As palavras inicial e final, assim como todas as palavras intermediárias, devem ter o mesmo comprimento.
- Cada etapa deve ser impressa em sua linha.
- A linha final da sua saída deve ser o número de etapas intermediárias necessárias para obter entre as palavras inicial e final.
- Se não for possível encontrar uma correspondência entre as palavras inicial e final, a saída deve consistir em 3 linhas: a palavra inicial, a palavra final e a palavra OY.
- Inclua a notação Big O para sua solução em sua resposta
- Inclua 10 pares de palavras iniciais e finais exclusivas (com suas saídas, é claro) para mostrar as etapas que seu programa produz. (Para economizar espaço, enquanto o programa deve produzi-los em linhas individuais, você pode consolidá-los em uma única linha para postagem, substituindo novas linhas por espaços e vírgula entre cada execução.
Objetivos / Critérios de vitória
- A solução Big O mais rápida / melhor, que produzir as etapas intermediárias mais curtas após uma semana, vencerá.
- Se um empate resultar do critério Big O, o código mais curto vencerá.
- Se ainda houver um empate, a primeira solução a atingir sua revisão mais rápida e mais rápida vencerá.
Testes / Saída de Amostra
DIVE
DIME
DAME
NAME
2
PEACE
PLACE
PLATE
SLATE
2
HOUSE
HORSE
GORSE
GORGE
2
POLE
POSE
POST
PAST
FAST
3
Validação
Estou trabalhando em um script que pode ser usado para validar a saída.
Será:
- Verifique se cada palavra é válida.
- Certifique-se de que cada palavra seja exatamente 1 letra diferente da palavra anterior.
Não vai:
- Verifique se o menor número de etapas foi usado.
Depois que eu tiver escrito isso, é claro que atualizarei este post. (:
code-challenge
word-puzzle
1p5
Rebecca Chernoff
fonte
fonte
HOUSE
paraGORGE
seja relatada como 2. Sei que existem 2 palavras intermediárias, então faz sentido, mas o número de operações seria mais intuitivo.The fastest/best Big O solution producing the shortest interim steps after one week will win.
como você não pode garantir que a solução mais rápida seja a que utiliza menos etapas, você deve fornecer uma preferência, se uma solução usar menos etapas, mas atingir a meta mais tarde.BAT
eCAT
terei zero etapas, certo?Respostas:
Como o comprimento está listado como critério, eis a versão em golf com 1681 caracteres (provavelmente ainda pode ser melhorada em 10%):
A versão ungolfed, que usa nomes e métodos de pacotes e não dá avisos ou estende classes apenas para aliasá-los, é:
Como você pode ver, a análise dos custos de execução é
O(filelength + num_words * hash + V * n * (n + hash) + E * hash)
. Se você aceitar minha suposição de que uma inserção / pesquisa de tabela de hash é tempo constante, é issoO(filelength + V n^2 + E)
. As estatísticas particulares dos gráficos em SOWPODS significam queO(V n^2)
realmente dominaO(E)
a maiorian
.Saídas de amostra:
IDOLA, IDOLS, IDYLS, ODYLS, ODALS, OVALS, OVELS, FORNOS, EVENS, ETENS, STENS, SKENS, PELE, SPINS, SPINE, SPINE, 13
WICCA, PROSY, OY
BRINY, BRINCES, TRINS, MOEDAS, CHARNES, Fios, Bocejos, YAWPS, YAPPS, 7
GALES, GASES, GASTOS, GESTS, GESTE, GESSE, DESSE, 5
SURES, DURES, DUNES, DINES, DINGS, DINGY, 4
LUZ, LUZ, BIGHT, BIGOT, BIGOS, BIROS, GIROS, GIRNS, GURNS, GUANS, GUANA, RUANA, 10
SARGE, SERGE, SERRE, SERRS, SEERS, veados, tintureiros, OYERS, OVERS, OVELS, OVALS, ODALS, ODYLS, IDYLS, 12
CHAVES, PRIMEIROS SOCORROS, CERVEJAS, CERVEJAS, BRERE, BREME, CREME, CREPE, 7
Este é um dos 6 pares com o caminho mais curto e mais longo:
GAINEST, FAINEST, FAIREST, SAIREST, SAIDEST, SADDEST, MADDEST, MIDDEST, MILDEST, WILDEST, WILIEST, WALIEST, WANIEST, CANIEST, CANTEST, CONCURSO, CONFEST, CONFESS, CONFERS, CONKERS, COOKERS, COOPERS, COPPERS, POPPERS, POPPERS PAPÉIS, PAPOILAS, POPSIES, MOPSIES, MOUSIES, MOUSSES, POUSSES, PLUSSES, PLISSES, PRISSES, PRESSES, PREASES, UREASES, UREASES, UNEASES, UNCASES, UNCASED, UNBASED, UNBATED, UNMATED, UNMETED, UNMEWED, ENDEWED, ENDEWED ÍNDICES, INDENES, RECENTES, INCENTES, INFESTS, INFESTS, INFECTES, INJETOS, 56
E um dos pares de 8 letras solúveis no pior dos casos:
ENROBANDO, DESENVOLVENDO, DESENVOLVENDO, DESENVOLVENDO, DESENVOLVENDO, DESENVOLVENDO, ENCAGINDO, ENRAGANDO, ENRACANDO, ENLACANDO, DESENVOLVENDO, INCLINANDO, ATRAVÉS, SPLAYING, SPRAYING, STRAYING, STROYING, STROKING, STOUM, STOUM CRIANÇAS, CRISPIS, CRISPINOS, CRISPENS, CRISPERS, CRIMPERS, CRAMPERS, CLAMPERS, CLASPERS, CLASHERS, SLASHERS, SLATHERS, SLITHERS, SMITHERS, SMOTHERS, SOOTHERS, SOUTHERS, MOUTHERS, MOUCHERS, SOUTCHERS, PACHECERS, PACHECERS, PACHECERS, PENCHERS, PACHECERS ALMOÇOS, LÍQUIDOS, LÍQUIDOS, LINCHETS, 52
Agora que acho que tenho todos os requisitos da questão fora do caminho, minha discussão.
Para um CompSci, a pergunta obviamente se reduz ao menor caminho em um gráfico G, cujos vértices são palavras e cujas bordas conectam palavras diferentes em uma letra. Gerar o gráfico com eficiência não é trivial - na verdade, tenho uma ideia que preciso revisitar para reduzir a complexidade a O (V n hash + E). A maneira como faço isso envolve a criação de um gráfico que insere vértices extras (correspondentes a palavras com um caractere curinga) e é homeomórfico para o gráfico em questão. Eu considerei usar esse gráfico em vez de reduzir para G - e suponho que, do ponto de vista do golfe, eu deveria ter feito - com base em que um nó curinga com mais de 3 arestas reduz o número de arestas no gráfico e o o pior caso padrão de tempo de execução dos algoritmos de caminho mais curto é
O(V heap-op + E)
.No entanto, a primeira coisa que fiz foi executar algumas análises dos gráficos G para comprimentos de palavras diferentes, e descobri que eles são extremamente escassos para palavras de 5 ou mais letras. O gráfico de 5 letras possui 12478 vértices e 40759 arestas; adicionar nós de link torna o gráfico pior. No momento em que você tem até 8 letras, há menos bordas que nós e 3/7 das palavras estão "distantes". Rejeitei essa ideia de otimização por não ser realmente útil.
A idéia que se mostrou útil foi examinar a pilha. Posso dizer honestamente que implementei alguns montes moderadamente exóticos no passado, mas nenhum tão exótico quanto esse. Uso a estrela A (já que C não oferece nenhum benefício, dada a pilha que estou usando) com a heurística óbvia do número de letras diferentes do alvo, e um pouco de análise mostra que a qualquer momento não há mais do que três prioridades diferentes na pilha. Quando ponho um nó cuja prioridade é (custo + heurística) e olho para seus vizinhos, há três casos que estou considerando: 1) o custo do vizinho é custo + 1; a heurística do vizinho é heurística-1 (porque a letra que muda se torna "correta"); 2) custo + 1 e heurística + 0 (porque a letra que muda muda de "errado" para "ainda errado"; 3) custo + 1 e heurística + 1 (porque a letra que muda passa de "correta" para "errada"). Então, se eu relaxar o vizinho, vou inseri-lo na mesma prioridade, prioridade + 1 ou prioridade + 2. Como resultado, posso usar uma matriz de 3 elementos de listas vinculadas para o heap.
Devo adicionar uma observação sobre minha suposição de que as pesquisas de hash são constantes. Muito bem, você pode dizer, mas e os cálculos de hash? A resposta é que eu os estou amortizando:
java.lang.String
armazena em cache o seuhashCode()
, de modo que o tempo total gasto na computação de hashes éO(V n^2)
(na geração do gráfico).Há outra mudança que afeta a complexidade, mas a questão de saber se é uma otimização ou não depende de suas suposições sobre estatísticas. (A IMO colocar "a melhor solução Big O" como critério é um erro, porque não há uma melhor complexidade, por um motivo simples: não há uma única variável). Essa alteração afeta a etapa de geração do gráfico. No código acima, é:
É isso
O(V * n * (n + hash) + E * hash)
. Mas aO(V * n^2)
parte vem da geração de uma nova seqüência de caracteres de n caracteres para cada link e da computação do seu código de hash. Isso pode ser evitado com uma classe auxiliar:Então a primeira metade da geração do gráfico se torna
Usando a estrutura do código hash, podemos gerar os links
O(V * n)
. No entanto, isso tem um efeito indireto. Inerente à minha suposição de que as pesquisas de hash são tempo constante, é uma suposição que comparar objetos para igualdade seja barato. No entanto, o teste de igualdade do Link estáO(n)
no pior caso. O pior caso é quando temos uma colisão de hash entre dois links iguais gerados a partir de palavras diferentes - isto é, ocorreO(E)
vezes na segunda metade da geração do gráfico. Fora isso, exceto no improvável evento de colisão de hash entre links não iguais, estamos bem. Então, nós trocamosO(V * n^2)
porO(E * n * hash)
. Veja meu ponto anterior sobre estatísticas.fonte
Java
Complexidade : ?? (Eu não tenho um diploma CompSci, por isso gostaria de receber ajuda nesse assunto.)
Entrada : Forneça Par de palavras (mais de 1 par, se desejar) na linha de comando. Se nenhuma linha de comando for especificada, serão escolhidas 2 palavras aleatórias distintas.
fonte
System.nanoTime()
.c no unix
Usando o algoritmo dijkstra.
Uma grande fração do código é uma implementação de árvore n-ária, que serve para manter
Quem estiver interessado em ver como ele funciona provavelmente deve ler
findPath
,process
eprocessOne
(e seus comentários associados). E talvezbuildPath
ebuildPartialPath
. O resto é contabilidade e andaimes. Várias rotinas usadas durante o teste e desenvolvimento, mas não na versão "produção", foram mantidas.Eu estou usando
/usr/share/dict/words
em minha caixa de Mac OS 10.5, que tem tantas entradas longas, esotéricos que deixá-lo correr completamente aleatoriamente gera um monte deOY
s.Alguma saída:
A análise de complexidade não é trivial. A pesquisa é um aprofundamento iterativo de dois lados.
W
.S_min = (<number of different letter>-1)
porque, se tivermos apenas uma letra, pontuamos a alteração em 0 etapas intermediárias. É difícil quantificar o máximo, veja a execução TRICKY-SWOOSH acima. Cada metade da árvore seráS/2-1
aS/2
B
.Portanto, o número mínimo de operações está próximo
2 * (S/2)^B * W
, não muito bom.fonte
O(|V|+|E|)
vez deO(|E|+|V| log |V|)
?