8
\$\begingroup\$

Your mission, should you choose to accept it, is to input a series of point pairs that form a graph, like this:

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

You must then output an ASCII visualization of the graph.

For example, A,B C,A C,D could be:

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

Edit: As per the comments, here are some input constraints:

  • each node has at most 5 connections (+20 if you can handle more)
  • the graph is planar, i.e. no lines cross (+200 if you can handle even one crossover!)
  • there are at most 16 nodes (+20 if you can handle more)

Your score is 999 - (your code length) + (any bonuses).

Start your engines :)

\$\endgroup\$
  • \$\begingroup\$ code-golf, code-challenge, or what ? And what is/are the winning criterion/criteria ? \$\endgroup\$ – Paul R May 15 '13 at 10:27
  • \$\begingroup\$ code-golf /10char \$\endgroup\$ – Soham Chowdhury May 15 '13 at 10:28
  • 1
    \$\begingroup\$ Is the graph guaranteed to be planar? Is the ASCII representation required to be planar? (If so, this is quite a challenging task). \$\endgroup\$ – Peter Taylor May 15 '13 at 10:48
  • 1
    \$\begingroup\$ @SohamChowdhury: Planar means it can be drawn without crossing lines. \$\endgroup\$ – marinus May 15 '13 at 11:06
  • 2
    \$\begingroup\$ This is an extremely broad and hard challenge at the moment. Tools such as graphviz and search.cpan.org/~tels/Devel-Graph-0.12/lib/Devel/Graph.pm have been designed for this kind of job. I also tried doing something similar in the past but failed. Extra rules that the graph is planar and nodes have at most 4 connections would make this a much more sensible code golf challenge. \$\endgroup\$ – shiona May 15 '13 at 11:14
7
\$\begingroup\$

Python 3, 168 chars, Score = 999- 168 + 240 = 1071

Just shortening Keith Randalls great answer.

  1. In Python 3, print is a function, and therefore can be abbreviated by p=print. Saves 3 * (4 - 1) - 8 = 1 character.

  2. In Python 3, input is used instead of raw_input, saves 4 characters.

  3. Instead of ' '*len(V) you can use ' '*80 (or something similar). This leads to an increased number of trailing spaces, but who cares... if it saves another 4 characers!

  4. Now it gets interesting: Instead of strings, use lists! This makes the updating of S much easier, but complicates printing somewhat. I'll call the list T so I'll not confuse it with the string S from marinus.

  5. Let's start by turning the vertices into a list, not a space-seperated string, which saves 4 characters. The output line T has to become a list (T=[' ']*40), which costs 2 characters.

  6. The printing of the current line T becomes 5 characters longer: I need brackets to concatenate the lists of strings correctly, I need two more - characters (because x and y are only about half as large now), and I need a * to make the print function take the elements of the list as seperate arguments and print them out seperated by spaces (and not as a list!). (This step was hard.)

  7. The current line can be updated with a simple T[x]=T[y]="|" instead of S=S[:x]+'|'+S[x+1:y]+'|'+S[y+1:], which saves 19 characters.

  8. For printing T again, and for the final spaced printing of the vertices, asterisks are needed, which costs 2 characters.

  9. And just while I am typing this, I see that there is no harm in having an unconnected invisible vertex (' '). This allows to create the set of vertices much shorter, saving 4 more characters.

Altogether, the saving is 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)

Example showing the effect of 9.: input A,B A,C leads to output

+-----+                                                                        
|     |                                                                        
+---+ |                                                                        
|   | |                                                                        
A   C B
\$\endgroup\$
  • 1
    \$\begingroup\$ I originally had S and T as lists, but in python 2 you need the ''.join() garbage which made it longer. I didn't know that *T thing existed in python3. Next golf... \$\endgroup\$ – Keith Randall May 16 '13 at 23:12
18
\$\begingroup\$

APL (171 166 162 chars, all bonuses: 999 - 171 166 162 + 20 + 20 + 200 = 1068 1073 1077)

This is the longest golfed APL program I've written so far. This might be slightly cheating, but there's nothing in the question that actually disallows this. What I'm doing is putting all the nodes on a vertical line and drawing the graph as an arc diagram. It is obviously still a graph though.

It still took me a few hours.

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

The nodes must be single uppercase letters, so it supports 26 nodes maximum. It can handle crossed lines, and each node can have as many connections as the display will handle.

Example output:

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                                                 
\$\endgroup\$
  • \$\begingroup\$ That's roughly what I was thinking of doing (and may yet do). Only obvious short way of handling it. \$\endgroup\$ – Peter Taylor May 15 '13 at 19:16
  • 3
    \$\begingroup\$ It's a mystery to me how people write APL. +1 \$\endgroup\$ – Soham Chowdhury May 17 '13 at 10:06
7
\$\begingroup\$

Python, 195 chars, score = 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

Each edge gets a row. S is a string with the vertical connections we need to keep as we build the graph.

Here are some sample input/output:

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

and stolen from marinus:

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.