Zeichnen Sie ein Netzwerk von Knoten

24

Es gibt ein Netzwerk von bis zu 26 Knoten (benannt Anach Zoder anach zIhrem Wunsch). Jedes Knotenpaar kann verbunden oder getrennt werden. Ein Knoten darf mit maximal 4 anderen Knoten verbunden sein. Ihre Aufgabe ist es, das Netzwerk in einem 2D-Diagramm zu zeichnen. Die Eingabe erfolgt so, dass diese Aufgabe möglich ist (weitere Einschränkungen finden Sie im Abschnitt Ausgabe).


Format

Eingang

  • Buchstabenpaare ( Anach Zoder anach zIhrem Wunsch). Sie sind in keiner Reihenfolge sortiert.
  • Optional - Anzahl der Paare

Ausgabe

  • Eine ASCII-Zeichnung, die die tatsächlichen Verbindungen zwischen den Knoten zeigt. Die Knoten werden durch gegeben azu zoder Azu Z. Verwenden Sie -für horizontale Links und |für vertikale Links. Verknüpfungen können eine beliebige Länge (ungleich Null) haben, sie sollten jedoch gerade horizontale / vertikale Linien sein , die nicht gebogen werden . Leerzeichen können hinzugefügt werden, sofern sie das Bild nicht verunstalten.

Sie können möglicherweise keine integrierten Funktionen verwenden, die beim Layout des Diagramms hilfreich sind. Möglicherweise sind auch andere grafische integrierte Funktionen zulässig (Lösungen ohne integrierte Funktionen wären jedoch wünschenswerter). Kürzester Code gewinnt.


Beispieldaten

Eingang

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

Ausgabe

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

Eingang

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

Ausgabe

A - B ----- F
|   |       |
D - C - H - G
ghosts_in_the_code
quelle
1
Ich bin der Meinung, dass meine vorherigen Fragen ausreichend beantwortet wurden, beachte jedoch, dass der neue Testfall falsch ist, da die erste Zeile H Aund diese Kante nicht in der angegebenen Ausgabe enthalten sind. Bearbeiten: Problem identifiziert und behoben.
Peter Taylor
2
Vielleicht in "Erster (funktionierender) Code gewinnt" ändern? ;-) Im Ernst, das ist eine Herausforderung für sich, auch ohne Golf zu spielen ...
Marco13
@ Marco13 Das würde die Herausforderung höchstwahrscheinlich als Off-Topic abschließen.
Dennis
@ghosts_in_the_code Bitte verwenden Sie keine Flags, um Fragen von Moderatoren zu stellen. Wenn Sie Feedback zu etwas benötigen, gibt es immer das neunzehnte Byte .
Dennis
@ Tennis ok, sorry. Ich war noch nie im Chat, daher weiß ich nicht, wie es funktioniert.
Ghosts_in_the_code

Antworten:

3

CJam, 142

Sie haben nicht nach einer optimalen, deterministischen oder schnellen Lösung gefragt.

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*

Probieren Sie es online aus

Dies generiert zufällige Koordinaten für jeden Buchstaben und prüft, ob das Layout akzeptabel ist (Kantenbuchstaben aneinandergereiht und keine Schnittpunkte), bis es ist. Es wird langsam, je mehr Kanten hinzugefügt werden.

Die beiden DBuchstaben im Code geben die maximalen x- und y-Koordinaten an. Ich habe D(= 13) gewählt, weil ich denke, dass es für alle Fälle ausreichen sollte. Zögern Sie nicht, mir das Gegenteil zu beweisen. Sie können sie jedoch auf andere Werte ändern, um das Programm zu beschleunigen. Das zweite Beispiel sollte beispielsweise innerhalb von ein oder zwei Minuten abgeschlossen sein, wenn Sie stattdessen 3 und 4 verwenden.

aditsu
quelle
Ich habe nicht nach einer schnellen Lösung gefragt, aber vielleicht hätte ich nach einer deterministischen Lösung fragen sollen. Aber jetzt, da die Frage so lange offen ist, werde ich es nicht ändern.
ghosts_in_the_code
@ghosts_in_the_code es sollte nicht zu schwer sein, es deterministisch zu machen - probiere alle Kombinationen von Koordinaten. Aber es wäre wahrscheinlich länger und viel langsamer und würde auch viel Gedächtnis fressen.
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();}

Übernimmt Eingaben als Kommandozeilenargumente, zB:

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

Nirgends konkurrenzfähig mit Aditsus Antwort nach Größe, aber viel effizienter!

Dies wird alle möglichen Lösungen brachial erzwingen, aber Fehler schnell erkennen, wie es geht. In den beiden Testfällen wird es fast sofort beendet, und bei schwierigeren Eingaben scheint es nur ein paar Sekunden zu dauern. Es gibt auch keine Beschränkung für die akzeptierten Knotennamen (obwohl Sie nicht ein Leerzeichen |oder benennen können -) und es gibt keine Beschränkung für die Anzahl der Knoten (solange alle Namen in ein Byte passen, beträgt die praktische Beschränkung also 252 Knoten). und es wird langsam werden, lange bevor es so viele erreicht).

Es gibt viel Spielraum, um dies zu beschleunigen. Viele Kurzschlussverluste gingen beim Golfen verloren und es gibt Teile, die aus den Hot-Loops entfernt werden können. Einige Beobachtungen der Symmetrie können unter anderem die Positionierung der ersten beiden Knoten drastisch reduzieren.


Nervenzusammenbruch:

#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
quelle
Endlich! Es ist 2 Monate her. Ich persönlich bin nicht dafür, eine solche Antwort zu geben, die nur von den Leuten dieser Seite verlangt wurde.
ghosts_in_the_code
@ghosts_in_the_code Wenn du kein Code-Golf willst, gibt es viele andere objektive Gewinnkriterien, die du verwenden kannst (obwohl du diese Herausforderung offensichtlich jetzt nicht ändern kannst, da sie veröffentlicht wurde). Zeitbasierte Beispiele wären: am schnellsten Ergebnisse auf einer bestimmten Hardware zu generieren (z. B. bestimmte EC2-Instanz / Himbeer-Pi / usw.), kompakteste Ausgabe für eine Testbatterie innerhalb eines Zeitlimits, größtes Netzwerk, das von einer Testbatterie innerhalb eines Zeitraums unterstützt wird Zeitlimit (z. B. ein Tag, um Flexibilität auf der spezifischen Hardware zu ermöglichen). Versuchen Sie es beim nächsten Mal mit der Sandbox. Menschen können Ihnen bei der Auswahl eines Ziels helfen.
Dave