ASCII-visualize um gráfico

8

Sua missão, se você optar por aceitá-la, é inserir uma série de pares de pontos que formam um gráfico, assim:

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

Você deve então gerar uma visualização ASCII do gráfico.

Por exemplo, A,B C,A C,Dpoderia ser:

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

Edit: Conforme os comentários, aqui estão algumas restrições de entrada:

  • cada nó tem no máximo 5 conexões (+20 se você puder lidar com mais)
  • o gráfico é plano, ou seja, nenhuma linha se cruza (+200 se você pode lidar com até uma passagem!)
  • existem no máximo 16 nós (+20 se você puder lidar com mais)

Sua pontuação é 999 - (o tamanho do seu código) + (qualquer bônus) .

Ligue seus motores :)

code-golf ascii-art graphical-output Soham Chowdhury
fonte
code-golf,, code-challengeou o que? E qual é / são os critérios / critérios vencedores?
Paul R
code-golf/ 10char
Soham Chowdhury
1
O gráfico é garantido como plano? A representação ASCII precisa ser plana? (Se sim, essa é uma tarefa bastante desafiadora).
Peter Taylor
1
@SohamChowdhury: Planar significa que pode ser desenhado sem cruzar linhas.
Marinus
2
Este é um desafio extremamente amplo e difícil no momento. Ferramentas como graphviz e search.cpan.org/~tels/Devel-Graph-0.12/lib/Devel/Graph.pm foram projetadas para esse tipo de trabalho. Eu também tentei fazer algo semelhante no passado, mas falhei. Regras extras que o gráfico é plano e os nós têm no máximo 4 conexões tornam esse desafio de golfe de código muito mais sensato.
shiona 15/05

Respostas:

7

Python 3, 168 caracteres, Pontuação = 999- 168 + 240 = 1071

Apenas encurtando a ótima resposta de Keith Randalls .

  1. No Python 3, printé uma função e, portanto, pode ser abreviada por p=print. Salva o 3 * (4 - 1) - 8 = 1personagem.

  2. No Python 3, inputé usado em vez de raw_input, salva 4 caracteres.

  3. Em vez de ' '*len(V)você pode usar ' '*80(ou algo semelhante). Isso leva a um aumento no número de espaços à direita, mas quem se importa ... se salvar outros 4 caracteres!

  4. Agora fica interessante: em vez de cadeias, use listas! Isso facilita muito a atualização S, mas complica um pouco a impressão. Vou ligar para a lista Tpara não confundi-la com a corda Sde marinus.

  5. Vamos começar transformando os vértices em uma lista, não em uma string separada por espaço, que salva 4 caracteres. A linha de saída Tprecisa se tornar uma lista ( T=[' ']*40), que custa 2 caracteres.

  6. A impressão da linha atual T se torna mais 5 caracteres: preciso de colchetes para concatenar as listas de strings corretamente, preciso de mais dois -caracteres (porque xey são apenas cerca da metade do tamanho agora) e preciso de uma função *para que a printfunção funcione os elementos da lista como argumentos separados e imprima-os separados por espaços (e não como uma lista!). (Esta etapa foi difícil .)

  7. A linha atual pode ser atualizada com um simples em T[x]=T[y]="|"vez de S=S[:x]+'|'+S[x+1:y]+'|'+S[y+1:], que salva 19 caracteres.

  8. Para imprimir Tnovamente e para a impressão final espaçada dos vértices, são necessários asteriscos, que custam 2 caracteres.

  9. E enquanto estou digitando isso, vejo que não há mal em ter um vértice invisível ( ' ') não conectado . Isso permite criar o conjunto de vértices muito mais curtos, economizando mais 4 caracteres.

Ao todo, a economia é 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)

Exemplo mostrando o efeito de 9 .: entrada A,B A,Cleva à saída

+-----+                                                                        
|     |                                                                        
+---+ |                                                                        
|   | |                                                                        
A   C B
Restabelecer Monica
fonte
1
Originalmente, eu tinha S e T como listas, mas no python 2 você precisa do ''.join()lixo que o tornou mais longo. Eu não sabia que *Tisso existia em python3. Próximo golfe ...
Keith Randall
19

APL ( 171 166 162 caracteres, todos os bônus: 999 - 171 166 162 + 20 + 20 + 200 = 1068 1073 1077)

Este é o programa APL mais longo que eu escrevi até agora. Isso pode ser um pouco trapaceiro, mas não há nada na pergunta que realmente não permita isso. O que estou fazendo é colocar todos os nós em uma linha vertical e desenhar o gráfico como um diagrama de arco. Obviamente, ainda é um gráfico.

Ainda me levou algumas horas.

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

Os nós devem ter letras maiúsculas simples, para suportar no máximo 26 nós. Ele pode manipular linhas cruzadas e cada nó pode ter tantas conexões quanto o monitor manipular.

Exemplo de saída:

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
fonte
Isso é aproximadamente o que eu estava pensando em fazer (e ainda posso fazer). Apenas uma maneira curta e óbvia de lidar com isso.
Peter Taylor
3
É um mistério para mim como as pessoas escrevem APL. +1
Soham Chowdhury
7

Python, 195 caracteres, pontuação = 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

Cada aresta recebe uma linha. S é uma string com as conexões verticais que precisamos manter ao construir o gráfico.

Aqui estão alguns exemplos de entrada / saída:

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

e roubado de 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
Keith Randall
fonte