Hay una red de hasta 26 nodos (nombre Ade Zo apara zsegún su deseo). Cada par de nodos puede estar conectado o desconectado. Un nodo puede estar conectado como máximo a otros 4 nodos. Su tarea es dibujar la red en un diagrama 2D. La entrada se dará de manera tal que esta tarea sea posible (ver más restricciones en la sección de salida).

Entrada

• Pares de letras ( Aa Z, o aa zsegún su deseo). No están ordenados en ningún orden.
• Opcional - número de pares

Salida

• Un dibujo ASCII que muestra los enlaces reales entre los nodos. Los nodos están dados por ato zo Ato Z. Úselo -para enlaces horizontales y |para enlaces verticales. Los enlaces pueden tener cualquier longitud (distinta de cero) pero deben ser líneas rectas horizontales / verticales que no se doblen . Se pueden agregar espacios siempre que no desfiguren la imagen.

No puede usar elementos integrados que ayuden en el diseño del gráfico. Se pueden permitir otras funciones integradas relacionadas con gráficos (aunque las soluciones sin funciones integradas serían más apreciadas). El código más corto gana.

Entrada

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

Salida

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

Entrada

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

Salida

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

CJam, 142

No solicitó una solución óptima, determinista o rápida, así que aquí tiene:

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*

Pruébalo en línea

Esto genera coordenadas aleatorias para cada letra y prueba si el diseño es aceptable (letras de borde alineadas y sin intersecciones), hasta que lo sea. Se vuelve increíblemente lento a medida que agrega más bordes.

Las dos Dletras en el código especifican las coordenadas máximas xey; Elegí D(= 13) porque creo que debería ser suficiente para todos los casos, no dudes en demostrarme que estoy equivocado. Pero puede cambiarlos a otros valores para acelerar el programa, por ejemplo, el segundo ejemplo debería terminar dentro de un minuto o dos si usa 3 y 4 en su lugar.

C, 813 bytes

#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();}

Toma datos como argumentos de la línea de comandos, por ejemplo:

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

¡Nada competitivo con la respuesta de aditsu por tamaño, pero mucho más eficiente!

Esto impondrá la fuerza bruta a todas las soluciones posibles, pero reconocerá rápidamente el fracaso a medida que avanza. Para los dos casos de prueba, finaliza casi de inmediato, y parece que solo toma unos segundos en entradas más incómodas. Tampoco tiene limitación para los nombres de nodo aceptados (aunque no puede nombrar un espacio, |o- ) y no tiene límite en el número de nodos (siempre que todos los nombres quepan en un byte, por lo que el límite práctico es 252 nodos, y se ralentizará mucho antes de llegar a tantos).

Hay muchas posibilidades para acelerar esto; Se perdieron muchas salidas de cortocircuito en el golf, y hay partes que se pueden sacar de los circuitos calientes. Además, algunas observaciones de simetría pueden reducir drásticamente el posicionamiento de los primeros 2 nodos, entre otras cosas.

Descompostura:

#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
}