Dibuja una red de nodos

24

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).


Formato

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.


Data de muestra

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
fantasmas_en_el_código
fuente
1
Considero que mis preguntas anteriores han sido suficientemente respondidas, pero tenga en cuenta que el nuevo caso de prueba es incorrecto porque la primera línea está H Ay ese borde no está en la salida dada. Editar: problema identificado y solucionado.
Peter Taylor
2
¿Quizás cambiarlo a "Primero gana el código (de trabajo)"? ;-) En serio, esto es un desafío por sí solo, incluso sin jugar al golf ...
Marco13
@ Marco13 Lo más probable es que el desafío se cierre como fuera de tema.
Dennis
@ghosts_in_the_code Por favor, no use banderas para hacer preguntas a los moderadores. Si necesita comentarios sobre algo, siempre está el decimonoveno byte .
Dennis
@ Dennis ok, lo siento. Nunca he estado en el chat antes, así que no sé cómo funciona.
ghosts_in_the_code

Respuestas:

3

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.

aditsu
fuente
No pedí una solución rápida, pero tal vez debería haber pedido una solución determinista. Pero ahora que la pregunta ha estado por tanto tiempo, no la cambiaré.
ghosts_in_the_code
@ghosts_in_the_code no debería ser demasiado difícil hacerlo determinista: pruebe todas las combinaciones de coordenadas. Pero probablemente sería más largo y mucho más lento, y también consumiría mucha memoria.
aditsu
3

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
}
Dave
fuente
¡Finalmente! Han pasado 2 meses. Personalmente, no estoy a favor de dar una respuesta de golf, solo la gente de este sitio me lo exigió.
ghosts_in_the_code
@ghosts_in_the_code si no quieres el golf de código, hay muchos otros criterios para ganar objetivos que puedes usar (aunque obviamente, no puedes cambiar este desafío ahora que se ha publicado). Los ejemplos basados ​​en el tiempo serían: el más rápido para generar resultados en hardware específico (por ejemplo, instancia EC2 particular / raspberry pi / etc.), la salida más compacta para una batería de pruebas dentro de un límite de tiempo, la red más grande compatible con una batería de pruebas dentro de un límite de tiempo (por ejemplo, un día, lo que permite flexibilidad en el hardware específico). Intenta usar el sandbox la próxima vez; la gente puede ayudarte a elegir un objetivo.
Dave