Faire un alphabeTrie

31

Considérez la liste de mots triée alphabétiquement suivante:

balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom

Tous les mots commencent par bet les 5 premiers commencent par bal. Si nous regardons simplement les 2 premiers mots:

balderdash
ballet

on pourrait plutôt écrire:

balderdash
  +let

où le ' 'est utilisé lorsqu'un mot partage un préfixe avec le mot précédent; sauf pour le '+'caractère qui indique le DERNIER caractère où le deuxième mot partage un préfixe avec le mot précédent.

Il s'agit d'une sorte de visualisation «trie» : le parent est « bal», et a 2 descendants: 'derdash'et 'let'.

Avec une liste plus longue, comme:

balderdash
ballet
brooding

nous pouvons en outre utiliser le caractère pipe '|'pour préciser où se termine le préfixe partagé, comme suit:

balderdash
| +let
+rooding

et l'arbre équivalent aurait une racine d' 'b'avoir deux enfants: le sous-arbre ayant racine 'al'et et ses deux enfants 'derdash'et 'let'; et 'rooding'.

Si nous appliquons cette stratégie à notre liste d'origine,

balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom

nous obtenons une sortie qui ressemble à:

balderdash    
| +let     
|  +oonfish
|   | +ist 
|   +t     
+rooding   
   +m 

Si deux mots consécutifs de la liste n'ont pas de préfixe partagé, aucun caractère spécial n'est substitué; par exemple pour la liste:

broom
brood
crude
crumb

nous voulons la sortie:

broom
   +d
crude
  +mb

Contribution

Les mots dans l'entrée ne seront composés que de caractères alphanumériques (pas d'espaces ni de ponctuation); cela peut prendre la forme d'une liste de chaînes, d'une seule chaîne ou de toute autre approche raisonnable, tant que vous spécifiez le format choisi. Deux mots consécutifs ne seront pas identiques. La liste sera triée par ordre alphabétique.

Sortie

Votre sortie peut contenir des espaces de fin par ligne ou au total, mais aucun espace de début. Une liste de chaînes ou similaires serait également acceptable.

C'est du ; le code le plus court dans chaque langue conserve des droits de vantardise. Les interdictions habituelles contre les échappatoires s'appliquent.

Cas de test

Input:
apogee
apology
app
apple
applique
apply
apt

Output:
apogee     
 |+logy    
 +p        
 |+le      
 | +ique   
 | +y      
 +t        

Input:
balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom
donald
donatella
donna
dont
dumb

Output:
balderdash 
| +let     
|  +oonfish
|   | +ist 
|   +t     
+rooding   
   +m      
donald     
| |+tella  
| +na      
| +t       
+umb 
Chas Brown
la source
Qu'en est-il du cas où j'ai le mot ballaprès balloon. À quelle sortie devrions-nous nous attendre?
Don Thousand
@RushabhMehta Je suppose que vous auriez juste un +sous le premier o, mais je n'ai pas écrit le défi donc je ne suis pas certain.
Theo
5
@RushabhMehta Les mots sont triés par ordre alphabétique, donc cela ne se produira pas.
Neil
@Neil Oh bon point
Don Thousand
2
Les mots de l'entrée ne seront composés que de caractères alphanumériques : cela comprend-il vraiment des chiffres, ou vouliez-vous dire alphabétique?
Arnauld

Réponses:

11

Retina 0.8.2 , 58 57 octets

^((.*).)(?<=\b\1.*¶\1)
$.2$* +
m)+`^(.*) (.*¶\1[+|])
$1|$2

Essayez-le en ligne! Le lien comprend un cas de test. Edit: sauvé 1 octet grâce à @FryAmTheEggman soulignant que j'ai négligé un passage de \bà ^rendu possible par le m). Explication:

m)

Activez par ligne ^pour l'ensemble du programme.

^((.*).)(?<=^\1.*¶\1)
$.2$* +

Pour chaque mot, essayez de faire correspondre autant que possible le début du mot précédent. Remplacez la correspondance par des espaces, sauf le dernier caractère, qui devient a +.

+`^(.*) (.*¶\1[+|])
$1|$2

Remplacez à plusieurs reprises tous les espaces immédiatement au-dessus de +s ou |s par |s.

Neil
la source
@FryAmTheEggman En effet, j'ai ajouté le m)spécifiquement pour pouvoir le faire, donc je suis ennuyé d'avoir raté une instance.
Neil
Ugh, pourquoi est-ce que je me donne la peine de répondre aux commentaires si les gens vont juste les supprimer ...
Neil
9

JavaScript (ES6), 128 octets

Attend et renvoie une liste de listes de personnages.

a=>a.map((w,y)=>a[~y]=w.map(m=(c,x)=>(p=a[y-1]||0,m|=c!=p[x])?c:p[x+1]==w[x+1]?' ':(g=y=>a[y][x]<1?g(y+1,a[y][x]='|'):'+')(-y)))

Essayez-le en ligne!

Comment?

Les espaces et +les inscriptions peuvent être insérés en parcourant le premier au dernier mot dans l'ordre, mais |les inscriptions ne peuvent être insérées a posteriori qu'une fois +a identifié. Cela pourrait être réalisé en faisant deux passes distinctes, mais à la place, nous enregistrons un pointeur sur chaque entrée modifiée a[~y]afin de pouvoir la mettre à jour plus tard dans la même map()boucle.

En théorie, une solution de contournement plus simple consisterait à parcourir les mots dans l'ordre inverse et à inverser également la sortie à la fin du processus. Mais c'est un peu cher dans JS et je n'ai pas trouvé de moyen d'obtenir une version plus courte avec cette méthode.

a =>                           // a[] = input array
  a.map((w, y) =>              // for each word w at position y in a[]:
    a[~y] =                    //   save a pointer to the current entry in a[~y]
    w.map(m =                  //   initialize m to a non-numeric value
      (c, x) => (              //   for each character c at position x in w:
        p = a[y - 1] || 0,     //     p = previous word or a dummy object
        m |= c != p[x]         //     set m = 1 as soon as w differs from p at this position
      ) ?                      //     if w is no longer equal to p:
        c                      //       append c
      :                        //     else:
        p[x + 1] == w[x + 1] ? //       if the next characters are still matching:
          ' '                  //         append a space
        : (                    //       else:
            g = y =>           //         g() = recursive function to insert pipes
            a[y][x] < 1 ?      //           if a[y][x] is a space:
              g(               //             do a recursive call to g()
                y + 1,         //               with y + 1
                a[y][x] = '|'  //               and overwrite a[y][x] with a pipe
              )                //             end of recursive call
            :                  //           else:
              '+'              //             make the whole recursion chain return a '+'
                               //             which will be appended in the current entry
          )(-y)                //         initial call to g() with -y (this is ~y + 1)
    )                          //   end of map() over the characters
  )                            // end of map() over the words
Arnauld
la source
voudriez-vous regarder ma solution, je l'ai inventée moi-même mais elle rappelle votre solution. donc si c'est trop proche, vous pouvez le soumettre comme le vôtre (ou pas) et le supprimer ill :)
DanielIndie
@DanielIndie Pas de soucis. C'est assez différent.
Arnauld
2

JavaScript (Node.js) , 125 122 118 117 octets

a=>a.map((w,i)=>a[i]=w.map((T,k)=>+i&&l[k]==T?l[-~k]<w[-~k]?(g=_=>a[--i][k]<"+"?g(a[i][k]="|"):"+")():" ":(i=l=w,T)))

Essayez-le en ligne!

  • merci à @Arnauld pour les tests tio :)
DanielIndie
la source
1

Python, 263260 octets

- 3 octets grâce à Jonathan Frech

Code:

p=lambda t,f,g:"\n".join([(f[:-1]+"+"if(a!=min(t))*g else"")+a+p(t[a],(f+" "if len(t[a])>1or a==max(t)else f[:-1]+"| "),1)for a in t])if t else""
def a(t,x):
 if x:c=x[0];t[c]=c in t and t[c]or{};a(t[c],x[1:])
def f(*s):t={};[a(t,i)for i in s];return p(t,"",0)

Essayez-le en ligne!

Explication:

Cette solution crée un trie à partir des mots d'entrée et les analyse récursivement dans la sortie requise. La fonction a prend un tri t et une chaîne s et ajoute x à t. Les essais sont implémentés en tant que dictionnaires imbriqués. Chaque dictionnaire représente un nœud dans le trie. Par exemple, le dictionnaire représentant le trie généré par le premier cas de test ressemble à ceci:

{'b': {'a': {'l': {'d': {'e': {'r': {'d': {'a': {'s': {'h': {}}}}}}}, 'l': {'e': {'t': {}}, 'o': {'o': {'n': {'f': {'i': {'s': {'h': {}}}}, 'i': {'s': {'t': {}}}}}, 't': {}}}}}, 'r': {'o': {'o': {'d': {'i': {'n': {'g': {}}}}, 'm': {}}}}}}

La fonction p revient dans cette structure et génère la représentation sous forme de chaîne du trie attendue par le défi. La fonction f prend un tas de chaînes comme arguments, les ajoute toutes à un trie avec a, puis retourne le résultat de l'appel de p sur le trie.

Zachary Cotton
la source
1
252 octets possibles .
Jonathan Frech
1

C (gcc) , 165155 octets

Prend trois arguments:

  • char** a : un tableau de mots se terminant par null
  • char* m : un tableau de la longueur de chaque mot
  • int n : le nombre de mots du tableau
f(a,m,n,i,j)char**a,*m;{for(i=n;--i;)for(j=0;j<m[i]&j<m[i-1]&a[i][j]==a[i-1][j];j++)a[i][j]=a[i][j+1]^a[i-1][j+1]?43:++i<n&j<m[i]&a[i--][j]%81==43?124:32;}

Essayez-le en ligne!

Curtis Bechtel
la source
@Arnauld Bien sûr! Bien que ce ne soit pas ++i<n&j<m[i]&a[i--]un comportement indéfini? Puis-je compter sur gcc pour l'évaluer de gauche à droite?
Curtis Bechtel
Il s'agit très probablement d'un comportement non défini. Mais nous définissons les langues par leur implémentation, donc tant que cela fonctionne de manière cohérente avec cette version de gcc, je pense que ça va.
Arnauld
1

Perl 6 , 149 144 144 142 octets

{1 while s/(\n.*)\s(.*)$0(\+|\|)/$0|$1$0$2/;$_}o{$=({.[1].subst(/^(.+)<?{.[0].index($0)eq 0}>/,{' 'x$0.ords-1~'+'})}for '',|$_ Z$_).join("
")}

Essayez-le en ligne!

Je suis sûr que cela peut être joué un peu plus, d'autant plus que je ne suis pas un expert des regexes. Cela utilise à peu près le même processus que la réponse de Neil sur la rétine .

Jo King
la source
0

Python 2 , 191 octets

def f(w,r=['']):
 for b,c in zip(w[1:],w)[::-1]:
	s='';d=0
	for x,y,z in zip(r[0]+b,b,c+b):t=s[-1:];s=s[:-1]+[['+'*(s>'')+y,t+' |'[x in'+|']][y==z],t+y][d];d=d|(y!=z)
	r=[s]+r
 return[w[0]]+r

Essayez-le en ligne!

Chas Brown
la source
0

Rubis , 118 octets

->a{i=1;a.map{s="";a[i+=j=-1].chars{|c|a[i][j+=1]=i<0&&a[i-1][/^#{s+=c}/]?a[i+1][j]=~/[|+]/??|:?\s:c}[/[| ]\b/]&&=?+}}

Essayez-le en ligne!

Accepte un tableau de chaînes, sorties en modifiant le tableau d'entrée d'origine sur place.

Explication

La transformation de chaîne de base n'est pas trop complexe, mais pour insérer correctement les tuyaux verticaux, nous devons itérer dans l'ordre inverse, et puisque la reverseméthode est assez verbeuse, nous le ferons d'une manière plus délicate. Ici, nous utilisons mapjuste pour exécuter la boucle, laisser le premier mot seul, puis itérer à partir de la fin en utilisant des indices négatifs:

->a{
 i=1;                   #Initialize word indexer
 a.map{                 #Loop
  s="";                 #Initialize lookup string
  a[i+=j=-1]            #Initialize char indexer and decrement i
  .chars{|c|            #Loop through each char c of current word
   a[i][j+=1]=          #Mofify current word at position j 
    i<0&&               #If it's not the first word and
    a[i-1][/^#{s+=c}/]? #Word above matches current one from start to j
     a[i+1][j]=~/[|+]/? #Then if char below is | or +
      ?|:?\s:c          #Then set current char to | Else to Space Else leave as is
  }[/[| ]\b/]&&=?+      #Finally, replace Space or | at word boundary with +
 }
}
Kirill L.
la source