24
\$\begingroup\$

There is a network of up to 26 nodes (named A to Z or a to z as per your wish). Every pair of nodes may be connected or disconnected. A node may be connected to at most 4 other nodes. Your task is to draw the network in a 2D diagram. Input will be given such that this task is possible (see more constraints in output section).


Format

Input

  • Pairs of letters (A to Z or a to z as per your wish). They are not sorted in any order.
  • Optional - number of pairs

Output

  • An ASCII drawing that shows the actual links between the nodes. Nodes are given by a to z or A to Z. Use - for horizontal links and | for vertical links. Links may be of any (non-zero) length but they should be straight horizontal/vertical lines that do not bend. Spaces can be added provided they don't disfigure the picture.

You may not use built-ins that help in layout of the graph. Other graph-related built-ins may be allowed (though solutions without built-ins would be more appreciated). Shortest code wins.


Sample data

Input

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

Output

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

Input

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

Output

A - B ----- F
|   |       |
D - C - H - G
\$\endgroup\$
  • 1
    \$\begingroup\$ I consider that my previous questions have been sufficiently answered, but note that the new test case is wrong because the first line is H A and that edge isn't in the given output. Edit: problem identified and fixed. \$\endgroup\$ – Peter Taylor Jan 27 '16 at 14:32
  • 2
    \$\begingroup\$ Maybe change it to "First (working) code wins"? ;-) Seriously, this is challenging on its own, even without golfing... \$\endgroup\$ – Marco13 Jan 28 '16 at 13:59
  • \$\begingroup\$ @Marco13 That would most likely get the challenge closed as off topic. \$\endgroup\$ – Dennis Jan 28 '16 at 14:49
  • \$\begingroup\$ @ghosts_in_the_code Please don't use flags to ask moderators questions. If you need feedback on something, there's always The Nineteenth Byte. \$\endgroup\$ – Dennis Jan 28 '16 at 14:51
  • \$\begingroup\$ @Dennis ok, sorry. I've never been on chat before, so I don't know how it works. \$\endgroup\$ – ghosts_in_the_code Jan 28 '16 at 14:53
3
\$\begingroup\$

CJam, 142

You didn't ask for an optimal, deterministic or fast solution, so here you go:

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*

Try it online

This generates random coordinates for each letter and tests if the layout is acceptable (edge letters lining up and no intersections), until it is. It gets mind-numbingly slow as you add more edges.

The two D letters in the code specify the maximum x and y coordinates; I picked D (=13) because I think it should be sufficient for all cases, feel free to prove me wrong. But you can change them to other values to speed up the program, e.g. the 2nd example should finish within a minute or two if you use 3 and 4 instead.

\$\endgroup\$
  • \$\begingroup\$ I didn't ask for a fast solution, but maybe I should have asked for a deterministic one. But now that the question has been up for so long, I won't change it. \$\endgroup\$ – ghosts_in_the_code Apr 14 '17 at 6:10
  • \$\begingroup\$ @ghosts_in_the_code it shouldn't be too hard to make it deterministic - try all combinations of coordinates. But it would probably be longer and much slower, and eat a lot of memory too. \$\endgroup\$ – aditsu Apr 14 '17 at 6:50
3
\$\begingroup\$

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

Takes input as commandline arguments, e.g.:

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

Nowhere near competitive with aditsu's answer by size, but much more efficient!

This will brute-force all possible solutions, but will quickly recognise failure as it goes. For the two test cases, it finishes almost immediately, and it seems to only take a few seconds on more awkward inputs. It also has no limitation to the accepted node names (though you can't name one space, | or -) and has no limit on the number of nodes (as long as all names fit in a byte, so the practical limit is 252 nodes, and it will get slow long before reaching that many).

There's plenty of scope for speeding this up; a lot of short-circuit exiting was lost to the golfing, and there's parts which could be moved out of hot-loops. Also some observations of symmetry can dramatically reduce the positioning of the first 2 nodes, among other things.


Breakdown:

#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
}
\$\endgroup\$
  • \$\begingroup\$ Finally! It's been 2 months. I personally am not in favour for golfing such an answer, I was only required to, by the people of this site. \$\endgroup\$ – ghosts_in_the_code Apr 15 '17 at 2:34
  • \$\begingroup\$ @ghosts_in_the_code if you don't want code golf there are plenty of other objective winning criteria you can use (though obviously, you can't change this challenge now it's been posted). Time-based examples would be: fastest to generate results on specific hardware (e.g. particular EC2 instance / raspberry pi / etc.), most compact output for a battery of tests within a time limit, largest network supported from a battery of tests within a time limit (e.g. a day, allowing flexibility on the specific hardware). Try using the sandbox next time; people can help you pick an objective. \$\endgroup\$ – Dave Apr 15 '17 at 5:41

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.