Marching Squares é um algoritmo de computação gráfica, usado para recuperar isocontours 2D a partir de uma grade de amostras (veja também, seu irmão mais velho, Marching Cubes, para configurações 3D). A idéia é processar cada célula da grade de forma independente e determinar os contornos que passam por essa célula com base nos valores em seus cantos.

A primeira etapa deste processo é determinar quais arestas são conectadas por contornos, com base em se os cantos estão acima ou abaixo do valor do contorno. Por uma questão de simplicidade, consideraremos apenas os contornos ao longo do valor 0, para que tenhamos interesse se os cantos são positivos ou negativos. Existem casos para distinguir:24 = 16

^{Fonte da imagem: Wikipedia}

A identificação de branco e preto realmente não importa aqui, mas, por definição, diga que branco é positivo e preto é negativo. Iremos ignorar casos em que um dos cantos é exatamente 0.

Os pontos de sela (casos 5 e 10) oferecem um pouco de dificuldade extra: não está claro quais diagonais devem ser usadas apenas olhando os cantos. Isso pode ser resolvido encontrando a média dos quatro cantos (ou seja, uma aproximação do valor central) e escolhendo as diagonais de modo que os contornos separem o centro dos cantos com o sinal oposto. Se a média for exata 0, qualquer um dos casos poderá ser escolhido.

Normalmente, esses 16 casos são simplesmente armazenados em uma tabela de pesquisa. Isso é ótimo para eficiência, mas é claro que preferimos que o código seja curto por aqui. Portanto, sua tarefa é executar esta etapa de pesquisa e imprimir uma representação ASCII do caso no menor código possível.

O desafio

Você recebe os valores dos quatro cantos (números inteiros diferentes de zero) em uma ordem fixa de sua escolha. Você deve então gerar o layout correto dos contornos, resolvendo corretamente os casos dos pontos de sela.

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e exibindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

A entrada pode ser obtida em qualquer formato conveniente de sequência ou lista.

Os 16 casos serão representados na arte ASCII usando um dos seguintes blocos 5x5:

o---o  o---o  o---o
|   |  |   |  | | |
|   |  |---|  | | |
|   |  |   |  | | |
o---o  o---o  o---o

o---o  o---o  o---o  o---o
|/  |  |  \|  |   |  |   |
|   |  |   |  |   |  |   |
|   |  |   |  |\  |  |  /|
o---o  o---o  o---o  o---o

o---o  o---o
|/  |  |  \|
|   |  |   |
|  /|  |\  |
o---o  o---o

Você não deve imprimir nenhum espaço em branco à esquerda ou à direita, mas pode imprimir uma única nova linha opcional.

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Casos de teste

Os casos de teste assumem que a entrada é fornecida em ordem superior esquerda , superior direita , inferior esquerda , inferior direita . Os casos de teste são apresentados em 9 grupos, um correspondente a cada uma das 9 representações dadas acima (na mesma ordem, começando na célula vazia, terminando com os dois pontos de sela).

[1, 2, 1, 3]
[-9, -2, -2, -7]

[4, 5, -1, -2]
[-1, -2, 3, 4]

[7, -7, 7, -7]
[-5, 5, -5, 5]

[1, -6, -4, -1]
[-2, 3, 3, 4]

[-1, 6, -4, -1]
[2, -3, 3, 4]   

[-1, -6, 4, -1]
[2, 3, -3, 4]

[-1, -6, -4, 1]
[2, 3, 3, -4]

[3, -8, -9, 2]
[-3, 8, 9, -2]

[8, -3, -2, 9]
[-8, 3, 2, -9]

Além disso, os seguintes casos de teste podem retornar um dos pontos de sela (sua escolha):

[1, -4, -2, 5]
[-1, 4, 2, -5]

Ruby, 201 180 176

Esta é uma função lambda anônima, a ser chamada da maneira mostrada no exemplo não destruído.

Isso não contém variáveis s. Na versão não destruída, uma expressão complexa é atribuída spara maior clareza, antes de ser usada. 4 bytes são salvos na versão em golf colocando-o em linha. A única outra diferença entre as versões é o espaço em branco e os comentários.

Se for aceitável retornar a saída como uma matriz de cinco seqüências de cinco caracteres, em vez de imprimir em stdout, mais um byte poderá ser salvo.

->a{p=t=0
4.times{|i|t+=a[i]*=a[3];p+=a[i]>>9&1<<i}
q=p==6&&t>0?19:'@AC@P*10'[p].ord
puts c='o---o',(0..2).map{|i|b=p*i==3?'|---|':'|   |';b[q%4]='|/|\|/'[q%4+(i&2)];q/=4;b},c}

Estou feliz com a análise da matriz, mas acho que pode haver maneiras mais curtas de formar a saída.

Todos os quatro elementos da matriz de entrada são multiplicados pelo último elemento. Isso garante que o último elemento seja positivo e reduz o número de casos de 16 para 8. Os elementos têm direito de 9 posições, para que todos os números positivos se tornem 0 e todos os números negativos se tornem -1 (pelo menos no intervalo de entrada dados nos casos de teste.) Eles são ANDed por1<<array index para fornecer um número binário de 3 bits indicando o padrão (na verdade 4 bits, mas como o último elemento é sempre positivo, o quarto bit é sempre zero).

Esse número de 0..7 é então alimentado em uma tabela de pesquisa (suspiro) para determinar quais caracteres de cada linha não são espaços em branco. É nesse estágio que são tratadas as duas telas diferentes para o estojo da sela, com uma alternativa ao número na tabela de pesquisa sendo usada se o total for positivo (a pergunta diz considerar a "média", mas como estamos apenas interessado no sinal, não importa se considerarmos o total.)

Esperamos que a maneira como a exibição da saída funcione seja clara a partir dos comentários no código.

ungolfed no programa de teste

f=->a{p=t=0
  4.times{|i|                      #for each number in the input
    t+=a[i]*=a[3];                   #multiply each number by a[3]; totalize the sum in t
    p+=a[i]>>9&1<<i                  #shift right to find if negative; AND with 1<<i to build index number for pattern 
  }                                #q is a 3-digit base 4 number indicating which character of each line is non-whitespace (if any). 
  q=p==6&&t>0?19:'@AC@P*10'[p].ord #It's encoded in the magic string, except for the case of saddles with a positive total, which is encoded by the number 19.
  s=(0..2).map{|i|                 #build an array of 3 strings, indexes 0..2
    b=p*i==3?'|---|':'|   |';        #IF p is 3 and we are on row 1, the string is |---| for the horizontal line case. ELSE it is |   |.
    b[q%4]='|/|\|/'[q%4+(i&2)];      #The numbers in q indicate which character is to be modified. The characters in the string indicate the character to replace with.
    q/=4;                            #If q%4=0, the initial | is replaced by | (no change.) i&2 shifts the string index appropriately for the last row.
    b                                #divide q by 4, and terminate the loop with the expression b so that this is the object loaded into array s.  
  }
puts c='o---o',s,c}                #print the array s, capped with "o---o" above and below.


[[1, 2, 1, 3],
[-9, -2, -2, -7],

[4, 5, -1, -2],
[-1, -2, 3, 4],

[7, -7, 7, -7],
[-5, 5, -5, 5],

[1, -6, -4, -1],
[-2, 3, 3, 4],

[-1, 6, -4, -1],
[2, -3, 3, 4],

[-1, -6, 4, -1],
[2, 3, -3, 4],

[-1, -6, -4, 1],
[2, 3, 3, -4],

[3, -8, -9, 2],
[-3, 8, 9, -2],

[8, -3, -2, 9],
[-8, 3, 2, -9],

[1, -4, -2, 5],
[-1, 4, 2, -5]].each{|k|f.call(k)}