Jest to sieć do 26 węzłów (nazwanych Ado Zlub ado zjak na swoje życzenie). Każda para węzłów może być połączona lub rozłączona. Węzeł może być podłączony maksymalnie do 4 innych węzłów. Twoim zadaniem jest narysowanie sieci na schemacie 2D. Dane wejściowe zostaną podane w taki sposób, aby to zadanie było możliwe (zobacz więcej ograniczeń w sekcji wyników).

Wkład

• Par liter ( Ado Zlub aproduktu z, jak na swoje życzenie). Nie są sortowane w żadnej kolejności.
• Opcjonalnie - liczba par

Wydajność

• Rysunek ASCII, który pokazuje rzeczywiste połączenia między węzłami. Węzły są nadawane przez ado zlub Ado Z. Użyj -do połączeń poziomych i |pionowych. Łącza mogą mieć dowolną (niezerową) długość, ale powinny być prostymi poziomymi / pionowymi liniami , które się nie wyginają . Można dodawać spacje, pod warunkiem że nie zniekształcają obrazu.

Nie możesz używać wbudowanych, które pomagają w układzie wykresu. Inne wbudowane wykresy mogą być dozwolone (chociaż rozwiązania bez wbudowanych rozwiązań byłyby bardziej docenione). Najkrótszy kod wygrywa.

Wkład

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

Wydajność

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

Wkład

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

Wydajność

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

CJam, 142

Nie prosiłeś o optymalne, deterministyczne lub szybkie rozwiązanie, więc proszę:

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*

Wypróbuj online

To generuje losowe współrzędne dla każdej litery i sprawdza, czy układ jest akceptowalny (litery na krawędzi w linii i bez przecięć), dopóki tak nie jest. Robi się przytłaczająco wolno, gdy dodajesz więcej krawędzi.

Dwie Dlitery w kodzie określają maksymalne współrzędne xiy; Wybrałem D(= 13), ponieważ uważam, że powinno wystarczyć we wszystkich przypadkach, nie krępuj się udowodnić, że się mylę. Ale możesz zmienić je na inne wartości, aby przyspieszyć program, np. Drugi przykład powinien zakończyć się w ciągu minuty lub dwóch, jeśli zamiast tego użyjesz 3 i 4.

C, 813 bajtów

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

Pobiera dane wejściowe jako argumenty wiersza poleceń, np .:

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

Nigdzie nie konkuruje z odpowiedzią aditsu według wielkości, ale jest o wiele bardziej wydajny!

To brutalnie wymusi wszystkie możliwe rozwiązania, ale szybko rozpozna porażkę. W dwóch przypadkach testowych kończy się niemal natychmiast i wydaje się, że zajmuje to tylko kilka sekund przy bardziej niezręcznych danych wejściowych. Nie ma również ograniczeń co do akceptowanych nazw węzłów (chociaż nie można nazwać jednej spacji |lub -) i nie ma ograniczenia liczby węzłów (o ile wszystkie nazwy mieszczą się w bajcie, więc praktyczny limit wynosi 252 węzłów, i na długo zwolni, zanim dojdzie do tylu).

Istnieje wiele możliwości przyspieszenia tego; gra w golfa utraciła wiele wyjść zwarciowych i są części, które można wyprowadzić z hot-loopów. Również niektóre obserwacje symetrii mogą drastycznie zmniejszyć, między innymi, położenie pierwszych 2 węzłów.

Awaria:

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