Il y a un réseau de jusqu'à 26 nœuds (nommés Aà Zou aà zselon votre souhait). Chaque paire de nœuds peut être connectée ou déconnectée. Un nœud peut être connecté à au plus 4 autres nœuds. Votre tâche consiste à dessiner le réseau dans un diagramme 2D. L'entrée sera donnée de telle sorte que cette tâche soit possible (voir plus de contraintes dans la section sortie).

Contribution

• Paires de lettres ( Aà Zou aà zselon votre souhait). Ils ne sont triés dans aucun ordre.
• Facultatif - nombre de paires

Sortie

• Un dessin ASCII qui montre les liens réels entre les nœuds. Les nœuds sont donnés par aà zou Aà Z. À utiliser -pour les liens horizontaux et |pour les liens verticaux. Les liens peuvent être de n'importe quelle longueur (non nulle) mais ils doivent être des lignes horizontales / verticales droites qui ne se plient pas . Des espaces peuvent être ajoutés à condition qu'ils ne défigurent pas l'image.

Vous ne pouvez pas utiliser des éléments intégrés qui aident à la présentation du graphique. D'autres modules intégrés liés aux graphiques peuvent être autorisés (bien que des solutions sans modules intégrés soient plus appréciées). Le code le plus court gagne.

Contribution

A B
B F
B L
F K
L K
K R
K S
R P
S J
S P
J A
T V
V N

Sortie

A - B - F   T - V
|   |   |       |
|   L - K - R   N
|       |   |
J ----- S - P

Contribution

H C
G H
A B
B F
B C
F G
C D
D A

Sortie

A - B ----- F
|   |       |
D - C - H - G

CJam, 142

Vous n'aviez pas demandé une solution optimale, déterministe ou rapide, alors voilà:

qN%Sf%::c_s_&:Aff#:E;{A{;[DmrDmr]2f*}%:C;E{Cf=~.-:*}%0m1{E{Cf=$~1$.-_:g:T\:+,1>\ff*\f.+T0="-|"=f+~}%CA.++:L2f<__&=!}?}gS25*a25*L{~2$4$=\tt}/N*

Essayez-le en ligne

Cela génère des coordonnées aléatoires pour chaque lettre et teste si la disposition est acceptable (lettres de bord alignées et pas d'intersections), jusqu'à ce qu'elle le soit. Cela devient incroyablement lent lorsque vous ajoutez plus de bords.

Les deux Dlettres du code spécifient les coordonnées maximales x et y; J'ai choisi D(= 13) car je pense que cela devrait être suffisant dans tous les cas, n'hésitez pas à me prouver le contraire. Mais vous pouvez les changer en d'autres valeurs pour accélérer le programme, par exemple le 2ème exemple devrait se terminer dans une minute ou deux si vous utilisez 3 et 4 à la place.

C, 813 octets

#include<map>
#include<set>
#include<cstdlib>
typedef int I;typedef char*C;I a,t,s,h;struct p{I x,y;}j,k;std::map<I,std::set<I>>l;std::map<I,p>g;C m,M="  |-";I L(I n,C q,C Q){j=g[n],h=1;for(I o:l[n])if(g.find(o)!=g.end())if(!(a=(k=g[o]).y==j.y)&&k.x^j.x)h=0;else for(I x=j.x,y=j.y,e=k.y*s+k.x,b,d=(k.x<j.x||k.y<j.y)?-1:1;a?x+=d:y+=d,(b=y*s+x)^e;m[b]=q[a])if(m[b]^Q[a]){h=0;break;}}I N(){for(auto i:g)for(I n:l[i.first])if(g.find(n)==g.end())return n;for(auto i:l)if(g.find(a=i.first)==g.end())return a;exit(puts(m));}I f(){for(I n=N(),x,y=0,b;y<s;y+=2)for(x=0;x<s;x+=2)m[b=y*s+x]==*M?g[n]={x,y},m[b]=n,L(n,M+2,M),h&&f(),L(n,M,M+2),m[b]=*M,g.erase(n):0;}I main(I c,C*v){for(;--c;l[a].insert(s),l[s].insert(a))a=v[c][0],s=v[c][1];t=l.size(),s=t|1;memset(m=(C)calloc(s,s),*M,s*s-1);for(a=1;a<s;++a)m[a*s-1]=10;f();}

Prend l'entrée comme arguments de ligne de commande, par exemple:

./network AB BF BL FK LK KR KS RP SJ SP JA TV VN

Nulle part plus compétitif avec la réponse d'Aditsu en termes de taille, mais beaucoup plus efficace!

Cela forcera toutes les solutions possibles, mais reconnaîtra rapidement l'échec au fur et à mesure. Pour les deux cas de test, il se termine presque immédiatement, et il semble ne prendre que quelques secondes sur des entrées plus maladroites. Il n'a également aucune limitation aux noms de nœuds acceptés (bien que vous ne puissiez pas nommer un espace, |ou -) et n'a pas de limite sur le nombre de nœuds (tant que tous les noms tiennent dans un octet, la limite pratique est donc de 252 nœuds, et cela ralentira longtemps avant d’atteindre ce nombre).

Il y a beaucoup de possibilités pour accélérer cela; beaucoup de courts-circuits sortis ont été perdus pour le golf, et il y a des pièces qui pourraient être retirées des boucles chaudes. Certaines observations de symétrie peuvent également réduire considérablement le positionnement des 2 premiers nœuds, entre autres.

Panne:

#include<map>
#include<set>
#include<cstdlib>
typedef int I;
typedef char*C;
I a,t,s,h;                // Variables shared between functions
struct p{I x,y;}          // Coord datatype
j,k;                      // Temporary coord references
std::map<I,std::set<I>>l; // Bidirectional multimap of node links
std::map<I,p>g;           // Map of nodes to positions
C m,                      // Rendered grid
M="  |-";                 // Lookup table for output characters

// Line rendering function
// Sets h to 1 if all lines are drawn successfully, or 0 if there is a blocker
I L(I n,C q,C Q){
  j=g[n],h=1;
  for(I o:l[n])                  // For each connection to the current node
    if(g.find(o)!=g.end())       // If the target node has been positioned
      if(!(a=(k=g[o]).y==j.y)&&k.x^j.x)h=0; // Fail if the nodes are not aligned
      else
        for(I x=j.x,y=j.y,             // Loop from node to target
          e=k.y*s+k.x,
          b,d=(k.x<j.x||k.y<j.y)?-1:1;
          a?x+=d:y+=d,(b=y*s+x)^e;
          m[b]=q[a])                   // Render character (| or -)
          if(m[b]^Q[a]){h=0;break;}    // Abort if cell is not blank
}

// Next node selection: finds the next connected node to try,
// or the next unconnected node if the current connected set is complete.
// Displays the result and exits if the entire graph has been rendered.
I N(){
  for(auto i:g)for(I n:l[i.first])  // Search for a connected node...
    if(g.find(n)==g.end())return n; // ...and return the first available
  for(auto i:l)                     // Else search for an unconnected node...
    if(g.find(a=i.first)==g.end())
      return a;                     // ...and return the first available
  exit(puts(m));                    // Else draw the grid to screen and stop
}

// Recursive brute-force implementation
I f(){
  for(I n=N(),x,y=0,b;y<s;y+=2) // Loop through all grid positions
    for(x=0;x<s;x+=2)
      m[b=y*s+x]==*M            // If the current position is available
       ?g[n]={x,y},             // Record the location for this node
        m[b]=n,                 // Render the node
        L(n,M+2,M),             // Render lines to connected nodes
        h&&f(),                 // If line rendering succeeded, recurse
        L(n,M,M+2),             // Un-render lines
        m[b]=*M,g.erase(n)      // Un-render node
       :0;
}

// Input parsing and grid setup
I main(I c,C*v){
  // Parse all inputs into a bidirectional multi-map
  for(;--c;l[a].insert(s),l[s].insert(a))a=v[c][0],s=v[c][1];
  t=l.size(),s=t|1; // Calculate a grid size
  // Allocate memory for the grid and render newlines
  memset(m=(C)calloc(s,s),*M,s*s-1);
  for(a=1;a<s;++a)m[a*s-1]=10;
  f(); // Begin recursive solving
}