ASCII-Visualisierung eines Diagramms

8

Ihre Mission besteht darin, eine Reihe von Punktpaaren einzugeben, die ein Diagramm bilden, wie folgt:

A, BC, AB, AA, DA, EF, GC, G.

Anschließend müssen Sie eine ASCII-Visualisierung des Diagramms ausgeben.

Zum Beispiel A,B C,A C,Dkönnte sein:

A-----------------B
 \                
  \                  
   C---------D

Bearbeiten: Gemäß den Kommentaren gibt es hier einige Eingabeeinschränkungen:

  • Jeder Knoten hat höchstens 5 Verbindungen (+20, wenn Sie mehr verarbeiten können)
  • Der Graph ist planar, dh es kreuzen sich keine Linien (+200, wenn Sie auch nur eine Überkreuzung verarbeiten können!)
  • Es gibt höchstens 16 Knoten (+20, wenn Sie mehr verarbeiten können)

Ihre Punktzahl beträgt 999 - (Ihre Codelänge) + (alle Boni) .

Starten sie ihre Motoren :)

Soham Chowdhury
quelle
code-golf, code-challengeOder was? Und was ist / sind das Gewinnkriterium / die Gewinnkriterien?
Paul R
code-golf/ 10char
Soham Chowdhury
1
Ist der Graph garantiert planar? Muss die ASCII-Darstellung planar sein? (Wenn ja, ist dies eine ziemlich herausfordernde Aufgabe).
Peter Taylor
1
@SohamChowdhury: Planar bedeutet, dass es gezeichnet werden kann, ohne Linien zu kreuzen.
Marinus
2
Dies ist derzeit eine äußerst breite und schwierige Herausforderung. Tools wie graphviz und search.cpan.org/~tels/Devel-Graph-0.12/lib/Devel/Graph.pm wurden für diese Art von Arbeit entwickelt. Ich habe in der Vergangenheit auch versucht, etwas Ähnliches zu tun, bin aber gescheitert. Zusätzliche Regeln, dass der Graph planar ist und die Knoten höchstens 4 Verbindungen haben, würden dies zu einer viel sinnvolleren Code-Golf-Herausforderung machen.
Shiona

Antworten:

7

Python 3, 168 Zeichen, Punktzahl = 999-168 + 240 = 1071

Nur Keith Randalls gute Antwort verkürzen .

  1. In Python 3 printist eine Funktion und kann daher mit abgekürzt werden p=print. Speichert den 3 * (4 - 1) - 8 = 1Charakter.

  2. Wird in Python 3 inputanstelle von raw_input4 Zeichen verwendet.

  3. Anstelle von können ' '*len(V)Sie verwenden ' '*80(oder etwas ähnliches). Dies führt zu einer erhöhten Anzahl von Leerzeichen, aber wen interessiert das schon ... wenn es weitere 4 Zeichen spart!

  4. Jetzt wird es interessant: Verwenden Sie anstelle von Zeichenfolgen Listen! Dies Serleichtert das Aktualisieren erheblich, erschwert jedoch das Drucken etwas. Ich werde die Liste anrufen, Tdamit ich sie nicht mit der Zeichenfolge Svon Marinus verwechsle .

  5. Beginnen wir damit, die Eckpunkte in eine Liste umzuwandeln, nicht in eine durch Leerzeichen getrennte Zeichenfolge, die 4 Zeichen speichert. Die Ausgabezeile Tmuss zu einer Liste ( T=[' ']*40) werden, die 2 Zeichen kostet.

  6. Das Drucken der aktuellen Zeile T wird 5 Zeichen länger: Ich benötige Klammern, um die Listen der Zeichenfolgen korrekt zu verketten, ich benötige zwei weitere -Zeichen (da x und y jetzt nur etwa halb so groß sind) und ich brauche a *, damit die printFunktion ausgeführt wird die Elemente der Liste als separate Argumente und drucken sie getrennt durch Leerzeichen aus (und nicht als Liste!). (Dieser Schritt war schwer .)

  7. Die aktuelle Zeile kann mit einem einfachen T[x]=T[y]="|"statt aktualisiert werden S=S[:x]+'|'+S[x+1:y]+'|'+S[y+1:], wodurch 19 Zeichen gespeichert werden.

  8. Zum Terneuten Drucken und zum endgültigen Drucken der Scheitelpunkte in Abständen werden Sternchen benötigt, die 2 Zeichen kosten.

  9. Und gerade während ich dies schreibe, sehe ich, dass es nicht schadet, einen nicht verbundenen unsichtbaren Scheitelpunkt zu haben ( ' '). Auf diese Weise können Sie die Scheitelpunkte viel kürzer erstellen und 4 weitere Zeichen sparen.

Insgesamt ist die Einsparung 1 + 4 + 4 + 4 - 2 - 5 + 19 - 2 + 4 = 27.

R=input()
p=print
V=list(set(R)-{','})
T=[' ']*40
for e in R.split():x,y=sorted(map(V.index,e[::2]));p(*T[:x]+["+"+"--"*(y-x-1)+"-+"]+T[y+1:]);T[x]=T[y]="|";p(*T)
p(*V)

Beispiel für die Wirkung von 9.: Eingang A,B A,Cführt zu Ausgang

+-----+                                                                        
|     |                                                                        
+---+ |                                                                        
|   | |                                                                        
A   C B
Setzen Sie Monica wieder ein
quelle
1
Ich hatte ursprünglich S und T als Listen, aber in Python 2 brauchst du den ''.join()Müll, der es länger gemacht hat. Ich wusste nicht, dass das *TDing in Python3 existiert. Nächster Golf ...
Keith Randall
19

APL ( 171 166 162 Zeichen, alle Boni: 999 - 171 166 162 + 20 + 20 + 200 = 1068 1073 1077)

Dies ist das längste Golf-APL-Programm, das ich bisher geschrieben habe. Dies mag leicht betrügen, aber es gibt nichts in der Frage, was dies tatsächlich verbietet. Ich setze alle Knoten auf eine vertikale Linie und zeichne den Graphen als Bogendiagramm. Es ist offensichtlich immer noch eine Grafik.

Ich habe noch ein paar Stunden gebraucht.

V←' '⍴⍨99,⍨2×⍴P←∪,C←(2,⍨2÷⍨⍴G)⍴G←G/⍨⎕A∊⍨G←⍞⋄V[2×⍳⍴P;50]←P⋄M←1⋄G←⍴D←{⍵[⍋⍵]}¨↓P⍳C⋄{V[A B←⍵;L←50+M×⌽⍳G]∘←'-'⋄V[A+⍳B-A;⊃L]∘←'|'⋄V[⍵;⊃L]∘←'+'⋄M×←¯1⋄G-←1}¨2×D[⍒|-/↑D]⋄V

Die Knoten müssen aus einfachen Großbuchstaben bestehen, sodass maximal 26 Knoten unterstützt werden. Es kann gekreuzte Linien verarbeiten, und jeder Knoten kann so viele Verbindungen haben, wie das Display verarbeiten kann.

Beispielausgabe:

A,B C,A C,D

      +-A--+                                              
      |    |                                              
      +-B  |                                              
           |                                              
        C+-+                                              
         |                                                
        D+   

A,B C,A B,A A,D A,E F,G C,G

          +--A-+-+-+                                           
          |    | | |                                           
          |  B-+ | |                                           
          |      | |                                           
        +-+--C   | |                                           
        |        | |                                           
        |    D---+ |                                           
        |          |                                           
        |    E-----+                                           
        |                                                      
        |   +F                                                 
        |   |                                                  
        +---+G                                                 


 T,H E,Q U,I C,K B,R O,W N,F O,X J,U M,P S,O V,E R,T H,E L,A Z,Y D,O G,S

               +---+----------T                                                 
               |   |                                                            
               |   +-------+--H                                                 
               |           |                                                    
               |           +--E---------+-------+                               
               |                        |       |                               
               |              Q---------+       |                               
               |                                |                               
               |     +--------U---------------+ |                               
               |     |                        | |                               
               |     +--------I               | |                               
               |                              | |                               
               |              C-------+       | |                               
               |                      |       | |                               
               |              K-------+       | |                               
               |                              | |                               
               |       +------B               | |                               
               |       |                      | |                               
               +-------+------R               | |                               
                                              | |                               
             +----------------O-----+-----+-+ | |                               
             |                      |     | | | |                               
             |                W-----+     | | | |                               
             |                            | | | |                               
             |           +----N           | | | |                               
             |           |                | | | |                               
             |           +----F           | | | |                               
             |                            | | | |                               
             |                X-----------+ | | |                               
             |                              | | |                               
             |                J-------------|-+ |                               
             |                              |   |                               
             |                M---+         |   |                               
             |                    |         |   |                               
             |                P---+         |   |                               
             |                              |   |                               
             |   +------------S-------------+   |                               
             |   |                              |                               
             |   |            V-----------------+                               
             |   |                                                              
             |   |            L-+                                               
             |   |              |                                               
             |   |            A-+                                               
             |   |                                                              
             |   |           +Z                                                 
             |   |           |                                                  
             |   |           +Y                                                 
             |   |                                                              
             +---|------------D                                                 
                 |                                                              
                 +------------G                                                 
Marinus
quelle
Das ist ungefähr das, woran ich gedacht habe (und vielleicht noch tun werde). Nur offensichtliche kurze Art, damit umzugehen.
Peter Taylor
3
Es ist mir ein Rätsel, wie Leute APL schreiben. +1
Soham Chowdhury
7

Python, 195 Zeichen, Punktzahl = 999 - 195 + 20 + 200 + 20 = 1044

R=raw_input()
V=' '.join(set(R)-set(' ,'))
S=' '*len(V)
for e in R.split():x,y=sorted(map(V.index,e[::2]));print S[:x]+'+'+'-'*(y-x-1)+'+'+S[y+1:];S=S[:x]+'|'+S[x+1:y]+'|'+S[y+1:];print S
print V

Jede Kante bekommt eine Reihe. S ist eine Zeichenfolge mit den vertikalen Verbindungen, die wir beim Erstellen des Diagramms beibehalten müssen.

Hier sind einige Beispiele für die Eingabe / Ausgabe:

A,B C,A B,A A,D A,E F,G C,G
+---+        
|   |        
+-+ |        
| | |        
+---+        
| | |        
+-------+    
| | |   |    
+-----+ |    
| | | | |    
| | | | | +-+
| | | | | | |
| +-------+ |
| | | | | | |
A C B E D G F

und von Marinus gestohlen:

T,H E,Q U,I C,K B,R O,W N,F O,X J,U M,P S,O V,E R,T H,E L,A Z,Y D,O G,S
                +-----------------------+          
                |                       |          
      +-----------------------+         |          
      |         |             |         |          
      |       +-----------------------+ |          
      |       | |             |       | |          
  +---------------+           |       | |          
  |   |       | | |           |       | |          
  | +-------------------------------+ | |          
  | | |       | | |           |     | | |          
  | | |       | | |       +---------------+        
  | | |       | | |       |   |     | | | |        
  | | |     +---------------+ |     | | | |        
  | | |     | | | |       | | |     | | | |        
  | | |     | | | |       +---------------------+  
  | | |     | | | |       | | |     | | | |     |  
  | | |     | | | | +-----------------+ | |     |  
  | | |     | | | | |     | | |     | | | |     |  
  | | |     | | | | | +---------+   | | | |     |  
  | | |     | | | | | |   | | | |   | | | |     |  
  | | |     | | | | | |   +-------+ | | | |     |  
  | | |     | | | | | |   | | | | | | | | |     |  
  | | +-------------------------------------+   |  
  | | |     | | | | | |   | | | | | | | | | |   |  
  | | |     | | | | | |   | | | | | +---+ | |   |  
  | | |     | | | | | |   | | | | | | | | | |   |  
  | | +---------+ | | |   | | | | | | | | | |   |  
  | | |     | | | | | |   | | | | | | | | | |   |  
+-----------------------+ | | | | | | | | | |   |  
| | | |     | | | | | | | | | | | | | | | | |   |  
| | | |     | | | | | | | | | | | | | | | | | +---+
| | | |     | | | | | | | | | | | | | | | | | | | |
| | | | +-----------------+ | | | | | | | | | | | |
| | | | |   | | | | | | | | | | | | | | | | | | | |
| | | | | +-----------------------+ | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | |
A C B E D G F I H K J M L O N Q P S R U T W V Y X Z
Keith Randall
quelle