Inspirado por isso .

Agatha Stephendale, uma estudante do segundo ano que realmente gosta de gráficos raster, fez um curso de álgebra linear. Agora ela imagina matrizes como retângulos, mas, em sua mente artística, ela anexa linhas diagonais a esses retângulos e tenta calcular traços ao longo deles. Na verdade, ela deseja calcular traços de todas as matrizes, não apenas quadradas.

Como Agatha é uma artista, ela sabe desenhar linhas em seu editor de imagens favorito, e o último usa o algoritmo de Bresenham para traçar linhas. Ela até checou a Wikipedia e encontrou o pseudocódigo:

 function line(x0, y0, x1, y1)
     real deltax := x1 - x0
     real deltay := y1 - y0
     real deltaerr := abs(deltay / deltax)    // Assume deltax != 0 (line is not vertical),
           // note that this division needs to be done in a way that preserves the fractional part
     real error := 0.0 // No error at start
     int y := y0
     for x from x0 to x1 
         plot(x,y)
         error := error + deltaerr
         while error ≥ 0.5 then
             y := y + sign(deltay) * 1
             error := error - 1.0

(Observe que esse pseudocódigo funciona apenas para declives inferiores a 1; para grades altas, um tratamento semelhante deve ser feito, mas com um loop over y. Consulte esta seção para os dois casos.)

Agatha imagina uma matriz como um retângulo, desenha uma linha diagonal e o algoritmo de Bresenham determina quais elementos de uma matriz pertencem à diagonal. Então ela pega a soma deles, e é isso que ela quer implementar no menor número de bytes possível, porque ela é uma estudante pobre e não pode permitir HDDs de grande capacidade para armazenar seu código.

Tarefa

Dada uma matriz A , retorne a soma dos elementos que estão na diagonal principal rasterizada (da parte superior esquerda para a parte inferior direita), onde a última é determinada pelo algoritmo de linha de Bresenham. Ou seja, supondo que a matriz represente uma grade m × n , desenhe uma linha nessa grade de A [1, 1] a A [m, n] usando o algoritmo de Bresenham e pegue a soma de todos os elementos na linha. Observe que, para matrizes 1 × N e N × 1 , a matriz inteira se torna sua própria diagonal (porque é assim que se desenha uma linha do primeiro elemento da primeira linha até o último elemento da última linha).

Entrada: uma matriz real (pode ser uma matriz 1 × 1 , uma matriz de linhas, uma matriz de colunas ou uma matriz retangular). Saída: um número.

Observe que algumas fontes (por exemplo, o pseudocódigo da Wikipedia acima) usam a verificação de condição error≥0.5, enquanto outras fontes usam error>0.5. Você deve usar o postado originalmente ( error≥0.5), mas se a alternativa error>0.5for mais curta no seu código, você poderá implementá-lo (já que este é um código de golfe), mas mencione-o explicitamente . Veja o caso de teste 4.

Regras do desafio

• Os formatos de E / S são flexíveis. Uma matriz pode ser várias linhas de números delimitados por espaço, separados por novas linhas, ou uma matriz de vetores de linha ou uma matriz de vetores de coluna etc.
• Isso é código-golfe , então a resposta mais curta em bytes vence.
• As regras padrão se aplicam à sua resposta, para que você possa usar STDIN / STDOUT, funções / método com os parâmetros adequados e programas completos do tipo retorno.
• As brechas padrão são proibidas.

Casos de teste

1. [[1,2,3],[4,5,6],[7,8,9]]→ 1+5+9→ saída: 15.

2. [[1,2,3,4],[5,6,7,8]]→ 1+2+7+8→ saída: 18.

3. [[1,2,3,4,5,6],[7,8,9,10,11,12],[13,14,15,16,17,18],[19,20,21,22,23,24]]→ 1+8+9+16+17+24→ saída: 75.

4. [[1,2,3,4,5],[6,7,8,9,10]]→ 1+2+8+9+10(usando a ≥condição de erro) → saída: 30.

No entanto, se for mais curto usar a desigualdade estrita >no seu código, a saída permitida é 1+2+3+9+10=25, mas você deve mencioná-la separadamente.

5. [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]→ 1+5+8+12→ saída: 26.

6. [[-0.3,0.5]]→ saída: 0.2.

7. [[3.1],[2.9]]→ saída: 6.

8. [[-5]]→ saída: -5.

Mais informações sobre o algoritmo de Bresenham

• http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm - uma coleção de algoritmos para diferentes idiomas;
• https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html - uma boa explicação apresentando diferentes casos de declives;
• https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm ;

Gelatina , 25 bytes

ZXL>LƲ¡µLḶ÷’Ɗ×XL’Ɗær0ị"OS

Experimente online!

SmileBASIC, 101 99 bytes

DEF D A,W,H
GCLS
GTRI.,0,0,0,W-1,H-1FOR I=0TO W*H-1=I MOD W
S=S+A[I/W,M]*!!GSPOIT(M,I/W)NEXT?S
END

Inicialmente, pensei em usar a função GLINE para desenhar uma linha, mas ela não parece usar o algoritmo correto. No entanto, GTRI não parece trabalho,

O caso de teste 4 gera 30.

A entrada é uma matriz 2D no formato [Y, X], juntamente com a largura / altura (não há como verificar as dimensões de uma matriz, apenas o número total de elementos).

JavaScript (ES6), 110 103 bytes

Saídas 25para o 4º caso de teste.

a=>(X=a[x=y=0].length-1,Y=1-a.length,g=e=>a[y][x]+(x-X|y+Y&&g(e+(e*2>Y&&++x&&Y)+(e*2<X&&++y&&X))))(X+Y)

Experimente online!

Ou 88 bytes, se aceitar as dimensões da matriz como entrada.

Python 3.X, 269 bytes

Com entrada como linhas delimitadas por vírgula de números delimitados por espaço.

import math;c=math.ceil;a=[[float(k)for k in q.split(" ")]for q in input().split(",")];_=len;m=lambda f,t,x,y,e,d:sum(x[0]for x in a)if 2>_(a[0])else m(*[0]*4,*[(_(a)-1)/(_(a[0])-1)]*2)if f else m(f,t+a[y][x],x+1,y+c(e-0.5),e+d-c(e-0.5),d)if x<_(a[0])else t;m(1,*[0]*5)

Pré-golfe:

def line(a):
   if len(a[0])<2: return sum([x[0] for x in a])
   e = d = abs((len(a)-1)/(len(a[0])-1))
   y=t=0
   for x in range(len(a[0])): 
       t += a[y][x]
       f = ceil(e-0.5)
       y += f
       e += d-f
   return t

FMSLogo , 136 bytes

make 1 rl
setxy -1+count :1 -1+count last :1
pu home
make 9 0
foreach :1[foreach ?[if
0=last pixel[make 9 :9+?]fd 1]setxy xcor+1 0]pr :9

Programa completo, solicite a entrada do usuário (pop-up da caixa de diálogo) e imprima a saída na tela.

Basta desenhar uma linha na tela e calcular a saída. Use uma desigualdade estrita.

Isso suporta apenas o tamanho da matriz até o tamanho da tela do FMSLogo (cerca de 500 × 500)

Código não destruído:

Make "input ReadList
SetXY (-1+Count :input) (-1+Count Last :input)
PenUp
Home
Make "sum 0
ForEach :input[
    ForEach ?[
        If 0=Last Pixel[
            Make "sum :sum+?
        ]
        Forward 1
    ]
    SetXY XCor+1 0
]
Print :sum