Gambarkan jaringan node

24

Ada jaringan hingga 26 node (bernama Ake Zatau ake zsesuai keinginan Anda). Setiap pasangan node dapat terhubung atau terputus. Sebuah node dapat terhubung ke paling banyak 4 node lainnya. Tugas Anda adalah menggambar jaringan dalam diagram 2D. Input akan diberikan sehingga tugas ini dimungkinkan (lihat lebih banyak kendala di bagian output).


Format

Memasukkan

  • Pasangan surat ( Ake Zatau ake zsesuai keinginan Anda). Mereka tidak diurutkan dalam urutan apa pun.
  • Opsional - jumlah pasangan

Keluaran

  • Gambar ASCII yang menunjukkan tautan aktual antara node. Node diberikan oleh ake zatau Ake Z. Gunakan -untuk tautan horisontal dan |untuk tautan vertikal. Tautan bisa memiliki panjang (non-nol) tetapi harus lurus / garis vertikal lurus yang tidak bengkok . Spasi dapat ditambahkan asalkan tidak merusak gambar.

Anda tidak boleh menggunakan bawaan yang membantu dalam tata letak grafik. Built-in terkait grafik lainnya mungkin diizinkan (meskipun solusi tanpa built-in akan lebih dihargai). Kode terpendek menang.


Contoh data

Memasukkan

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

Keluaran

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

Memasukkan

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

Keluaran

A - B ----- F
|   |       |
D - C - H - G
ghosts_in_the_code
sumber
1
Saya menganggap bahwa pertanyaan saya sebelumnya sudah cukup dijawab, tetapi perhatikan bahwa test case baru salah karena baris pertama H Adan edge tidak ada dalam output yang diberikan. Sunting: masalah diidentifikasi dan diperbaiki.
Peter Taylor
2
Mungkin mengubahnya menjadi "Pertama (bekerja) kode menang"? ;-) Serius, ini menantang sendiri, bahkan tanpa bermain golf ...
Marco13
@ Marco13 Itu kemungkinan besar akan membuat tantangan ditutup sebagai di luar topik.
Dennis
@ghosts_in_the_code Tolong jangan gunakan flag untuk mengajukan pertanyaan moderator. Jika Anda perlu umpan balik tentang sesuatu, selalu ada The Nineteenth Byte .
Dennis
@ Dennis ok, maaf. Saya belum pernah mengobrol sebelumnya, jadi saya tidak tahu cara kerjanya.
ghosts_in_the_code

Jawaban:

3

CJam, 142

Anda tidak meminta solusi yang optimal, deterministik atau cepat, jadi begini:

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*

Cobalah online

Ini menghasilkan koordinat acak untuk setiap huruf dan menguji jika tata letak dapat diterima (huruf tepi berbaris dan tidak ada persimpangan), sampai akhirnya. Pikiran menjadi mati rasa lambat ketika Anda menambahkan lebih banyak tepi.

Dua Dhuruf dalam kode menentukan koordinat x dan y maksimum; Saya memilih D(= 13) karena saya pikir itu sudah cukup untuk semua kasus, jangan ragu untuk membuktikan saya salah. Tetapi Anda dapat mengubahnya ke nilai lain untuk mempercepat program, misalnya contoh ke-2 akan selesai dalam satu atau dua menit jika Anda menggunakan 3 dan 4 sebagai gantinya.

aditsu
sumber
Saya tidak meminta solusi cepat, tetapi mungkin saya seharusnya meminta solusi deterministik. Tapi sekarang pertanyaannya sudah begitu lama, saya tidak akan mengubahnya.
ghosts_in_the_code
@ ghosts_in_the_code seharusnya tidak terlalu sulit untuk membuatnya menjadi deterministik - coba semua kombinasi koordinat. Tetapi mungkin akan lebih lama dan lebih lambat, dan memakan banyak memori juga.
aditsu
3

C, 813 byte

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

Mengambil input sebagai argumen commandline, misalnya:

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

Tidak ada yang bersaing dengan jawaban aditsu berdasarkan ukuran, tetapi jauh lebih efisien!

Ini akan memaksa semua solusi yang mungkin terjadi, tetapi akan segera mengenali kegagalan. Untuk dua kasus uji, hampir selesai dengan segera, dan tampaknya hanya membutuhkan beberapa detik pada input yang lebih canggung. Ini juga tidak memiliki batasan untuk nama-nama simpul yang diterima (meskipun Anda tidak dapat menyebutkan satu spasi, |atau -) dan tidak memiliki batasan pada jumlah node (selama semua nama sesuai dalam byte, sehingga batas praktisnya adalah 252 node, dan itu akan lambat jauh sebelum mencapai sebanyak itu).

Ada banyak ruang untuk mempercepat ini; banyak hubungan arus pendek hilang karena bermain golf, dan ada bagian yang bisa dipindahkan dari hot-loop. Juga beberapa pengamatan simetri dapat secara dramatis mengurangi posisi 2 node pertama, antara lain.


Kerusakan:

#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
sumber
Akhirnya! Sudah 2 bulan. Saya pribadi tidak mendukung untuk golf jawaban seperti itu, saya hanya diminta, oleh orang-orang dari situs ini.
ghosts_in_the_code
@ghosts_in_the_code jika Anda tidak ingin golf kode ada banyak kriteria pemenang objektif lain yang dapat Anda gunakan (meskipun jelas, Anda tidak dapat mengubah tantangan ini sekarang telah diposting). Contoh berdasarkan waktu adalah: tercepat untuk menghasilkan hasil pada perangkat keras tertentu (misalnya instance EC2 / raspberry pi / dll.), Sebagian besar output kompak untuk baterai pengujian dalam batas waktu, jaringan terbesar yang didukung oleh baterai tes dalam suatu batas waktu (misalnya sehari, memungkinkan fleksibilitas pada perangkat keras tertentu). Coba gunakan kotak pasir lain kali; orang dapat membantu Anda memilih tujuan.
Dave