Calcular a altura de uma árvore de raiz

8

Introdução

Uma árvore de raiz , também conhecida como árvore compactada trie ou prefixo compactado, é uma estrutura de dados semelhante a uma árvore para armazenar um conjunto de cadeias. As bordas da árvore são rotuladas por cadeias não vazias e cada nó é terminal ou não terminal. As strings que a árvore contém são exatamente os rótulos de todos os caminhos, da raiz ao nó do terminal. A árvore deve estar na forma normal definida pelas seguintes condições:

  • Todos os nós não-raiz não-terminais têm pelo menos dois filhos.
  • Para cada nó, todas as arestas de saída têm primeiros caracteres diferentes.

Por exemplo, aqui está a árvore de raiz que contém o conjunto ["test", "testing", "tested", "team", "teams", "technical", "sick", "silly"], (N)representando um nó não terminal e (T)um nó terminal:

-(N)-te-(N)-st-(T)-ing-(T)
  |      |      | 
  |      |      +-ed-(T)
  |      |
  |      +-am-(T)-s-(T)
  |      |
  |      +-chnical-(T)
  |
  +-si-(N)-ck-(T)
        |
        +-lly-(T)

Nesse desafio, sua tarefa é calcular a altura da árvore, considerando as seqüências de caracteres como entrada.

Entrada

Sua entrada é uma lista não vazia de cadeias de letras ASCII em minúsculas. Não conterá duplicatas, mas pode estar em qualquer ordem. Pode conter a cadeia vazia. Você pode receber a entrada em qualquer formato razoável.

Resultado

Sua saída deve ser o comprimento do caminho raiz-a-folha mais longo na árvore de raiz correspondente, medida no número de nós que ela contém.

No exemplo acima, a saída correta é 4, correspondendo aos caminhos

(N)-te-(N)-st-(T)-ing-(T)
(N)-te-(N)-st-(T)-ed-(T)
(N)-te-(N)-am-(T)-s-(T)

que contêm 4 nós.

Outros exemplos

Aqui estão mais alguns exemplos de árvores de raiz:

[""]
-(T)

["","fuller"]
-(T)-fuller-(T)

["","full","fuller"]
-(T)-full-(T)-er-(T)

["full","fuller"]
-(N)-full-(T)-er-(T)

["full","filler"]
-(N)-f-(N)-ull-(T)
        |
        +-iller-(T)

Regras e pontuação

Você pode escrever um programa completo ou uma função. Isso é código de golfe, portanto, a menor contagem de bytes vence.

Você pode usar qualquer built-in ou bibliotecas que desejar, mas lembre-se de incluir todos os imports etc. em sua contagem de bytes. Bibliotecas de terceiros - aquelas que não estão incluídas na instalação padrão do seu idioma - são permitidas, mas devem ser listadas no cabeçalho separadamente, por exemplo, Python + pytrie0.2, 60 bytes .

Casos de teste

[""] -> 1
["fuller"] -> 2
["","fuller"] -> 2
["","full","fuller"] -> 3
["full","fuller"] -> 3
["full","filler"] -> 3
["full","filler","filter"] -> 4
["full","filler","fi","filter"] -> 5
["test","testing","tested","team","teams","technical","sick","silly"] -> 4
["a","aaaa","aabbaa","aabbaab","abaaa","aab","aabbb","aabba"] -> 8
["dbdbaca","ab","a","caaabaaa","adbbabdb","dbdbdbaca","dbbadbacaba","db"] -> 4
["db","dbbdbb","dbaa","cabcacaa","","acaabcacab","b","abaaaca","bacaaaaa"] -> 3
["aabaabdbb","bacaabadbbdb","abb","aabaa","ab","bcadbb","adbbcaaadbbb","caaa","bbdbcacadbab","dbbdbdb"] -> 4
["bbcaaabbbabbcadbbacadbbdbdb","b","bbbbaaaaaababa","ca","bb","bdbbacadbbdbbdbbababaacaca","abbaabbabcabaaa","bbbacacacabcacacabaaabb","bbcaaaab","bbbbcaacaadbcaaa","babbabcadbdbacacabbcacab","abcabbbaacadbcadb","bbcabbcadbcacaacaadbadbcaadb","dbbbdbbdbacaabbacabcadbdbacaca","bbaabdbdb","cabcadbbbadbadbbaadbcaca","adbadbadbdbcacadbdbbcaadbcaca","abaabbcab","aaabcaabcaab","bacacabcacaacadbadbb"] -> 6
Zgarb
fonte
No seu primeiro exemplo, eu sinto que "sou" deve ser seguido por um nó com dois filhos, um com - "" - (T) e o outro com - "s" - (T). (Compare com "lento" / "lentamente" no segundo exemplo da página a que você vinculou.) Porém, isso não afetará o comprimento do caminho mais longo da raiz para a folha.
Greg Martin
@GregMartin A página da Wikipedia tem uma implementação ligeiramente diferente. Eu sinto que este é mais natural e, como você disse, não afeta a altura.
Zgarb 2/16/16

Respostas:

2

JavaScript (Firefox 30-57), 137 bytes

f=(a,b=["",...a],s=new Set(b.map(w=>w[0])))=>b.length>1?(s.size>1)+Math.max(...(for(c of s)f(a,[for(w of b)if(w&&w[0]==c)w.slice(1)]))):1

Deve haver algo errado com o meu algoritmo, pois eu pareço ter um caso especial com um parâmetro de string vazio.

Neil
fonte
Na minha solução de referência, a string vazia também é um caso especial. É porque o nó raiz tem suas próprias regras.
Zgarb
Eu também tive que fazer um caso especial, mas esse caso especial é apenas um caractere na minha solução (o .no final da primeira linha).
Martin Ender
1

Retina , 69 55 bytes

O avanço de linha à direita é significativo.

m`.(?<=(?=\D*^\1(?!\2))\D*^(.*)(.))|^.
:$&
T`w
O`
A-2`

Entrada é uma lista separada por avanço de linha.

O desempenho pode ser aumentado significativamente inserindo um \Aantes do último \Dna primeira linha.

Explicação

Um nó é inserido em uma palavra em três lugares:

  • O início.
  • Depois de qualquer prefixo mais longo compartilhado com outra palavra. Ou seja, um prefixo compartilhado após o qual as duas palavras diferem.
  • O fim.

Na Retina, tende a ser mais curto para produzir N+1quando você conta as Ncoisas, então estamos ignorando a que está no final. No entanto, para o caso da entrada vazia, também teremos que ignorar o início, porque começo e fim são os mesmos.

Para fazer a contagem real, inserimos :em todos os lugares onde há um nó. Então, simplesmente encontramos o número máximo de :em uma palavra e retornamos mais 1. Aqui está como o código faz isso:

m`.(?<=(?=\D*^\1(?!\2))\D*^(.*)(.))|^.
:$&

Isso detecta todos os nós. Corresponde a um personagem. Em seguida, entra em um lookbehind que captura esse caractere em grupo 2e o prefixo antes dele em grupo 1. Em seguida, ele vai todo o caminho para o início da cadeia para iniciar um lookahead, que verifica se ele pode encontrar o lugar prefixo onde ele está não seguido pelo caractere capturado. Se encontrarmos essa correspondência, inserimos um :na frente do caractere. Também combinamos o primeiro caractere da palavra atual para inserir a :no início das palavras não vazias.

T`w

Isso remove todas as letras e deixa apenas o :.

O`

Isso classifica as linhas, trazendo a profundidade máxima até o fim.

A-2`

Isso descarta tudo, exceto a última linha.

E a linha vazia no final conta o número de correspondências vazias nessa linha, que é uma a mais que o número de dois pontos nela.

Experimente online! (A primeira linha ativa um conjunto de testes separado por avanço de linha, onde cada caso de teste usa separação por vírgula.)

Martin Ender
fonte