Narysuj sieć węzłów

24

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


Format

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.


Przykładowe dane

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
ghosts_in_the_code
źródło
1
Uważam, że na moje poprzednie pytania udzielono wystarczającej odpowiedzi, ale zauważ, że nowy przypadek testowy jest nieprawidłowy, ponieważ pierwsza linia jest, H Aa tej krawędzi nie ma w podanym wyniku. Edycja: problem zidentyfikowany i naprawiony.
Peter Taylor
2
Może zmień go na „Wygrywa pierwszy (działający) kod”? ;-) Poważnie, jest to wyzwanie samo w sobie, nawet bez gry w golfa ...
Marco13
@ Marco13 Najprawdopodobniej zamknie to wyzwanie jako nie na temat.
Dennis
@ghosts_in_the_code Nie używaj flag do zadawania pytań moderatorom. Jeśli potrzebujesz informacji na temat czegoś, zawsze jest Dziewiętnasty bajt .
Dennis
@Dennis ok, przepraszam. Nigdy wcześniej nie rozmawiałem na czacie, więc nie wiem, jak to działa.
ghosts_in_the_code

Odpowiedzi:

3

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.

aditsu
źródło
Nie prosiłem o szybkie rozwiązanie, ale może powinienem był poprosić o rozwiązanie deterministyczne. Ale teraz, gdy pytanie było tak długo, nie zmienię go.
ghosts_in_the_code
@ghosts_in_the_code nie powinno być zbyt trudne, aby uczynić go deterministycznym - wypróbuj wszystkie kombinacje współrzędnych. Ale prawdopodobnie byłby dłuższy i znacznie wolniejszy, a także zjadłby dużo pamięci.
aditsu
3

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
}
Dave
źródło
Wreszcie! Minęły 2 miesiące. Osobiście nie jestem zwolennikiem grania w golfa na taką odpowiedź, czego wymagali tylko ludzie z tej strony.
ghosts_in_the_code
@ghosts_in_the_code, jeśli nie chcesz kodu golfa, istnieje wiele innych obiektywnych kryteriów wygranej, których możesz użyć (choć oczywiście nie możesz zmienić tego wyzwania, ponieważ zostało opublikowane). Przykładami opartymi na czasie byłyby: najszybsze generowanie wyników na określonym sprzęcie (np. Konkretna instancja EC2 / raspberry pi / itp.), Najbardziej kompaktowe wyjście dla zestawu testów w określonym czasie, największa sieć obsługiwana z zestawu testów w ciągu limit czasu (np. dzień, co pozwala na elastyczność na konkretnym sprzęcie). Spróbuj użyć piaskownicy następnym razem; ludzie mogą pomóc ci wybrać cel.
Dave