Inspirado por esto .

Agatha Stephendale, una estudiante de segundo año que está realmente interesada en los gráficos de trama, ha tomado un curso de álgebra lineal. Ahora imagina matrices como rectángulos, pero en su mente artística, une líneas diagonales a esos rectángulos e intenta calcular trazas a lo largo de ellos. De hecho, ella quiere calcular trazas de todas las matrices, no solo las cuadradas.

Como Agatha es artista, sabe cómo dibujar líneas en su editor de imágenes favorito, y este último utiliza el algoritmo de Bresenham para trazar líneas. Incluso revisó Wikipedia y encontró el 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

(Tenga en cuenta que este pseudocódigo funciona solo para pendientes de menos de 1; para cuadrículas altas, se debe hacer un tratamiento similar, pero con un bucle y. Consulte esta sección para los dos casos).

Agatha imagina una matriz como un rectángulo, dibuja una línea diagonal en ella y el algoritmo de Bresenham determina qué elementos de una matriz pertenecen a la diagonal. Luego toma su suma, y ​​esto es lo que quiere implementar en el menor número de bytes posible porque es una estudiante pobre y no puede permitirse HDD de gran capacidad para almacenar su código.

Tarea

Dada una matriz A , devuelve la suma de los elementos que se encuentran en la diagonal principal rasterizada (de arriba a la izquierda a la derecha a la derecha), donde esta última está determinada por el algoritmo de línea de Bresenham. Es decir, suponiendo que la matriz representa una cuadrícula m × n , dibuje una línea en esa cuadrícula desde A [1, 1] a A [m, n] usando el algoritmo de Bresenham, y tome la suma de todos los elementos en la línea. Tenga en cuenta que para las matrices 1 × N y N × 1 , toda la matriz se convierte en su propia diagonal (porque así es como se dibujaría una línea desde el primer elemento de la primera fila hasta el último elemento de la última fila).

Entrada: una matriz real (puede ser una matriz 1 × 1 , una matriz de fila, una matriz de columna o una matriz rectangular). Salida: un número.

Tenga en cuenta que algunas fuentes (p. Ej., El pseudocódigo de Wikipedia anterior) usan la verificación de condición error≥0.5, mientras que otras usan error>0.5. Debe usar el publicado originalmente ( error≥0.5), pero si la alternativa error>0.5es más corta en su código, entonces se le permite implementarlo (ya que esto es código golf), pero mencione explícitamente . Ver caso de prueba 4.

Reglas de desafío

• Los formatos de E / S son flexibles. Una matriz puede ser varias líneas de números delimitados por espacios separados por líneas nuevas, o una matriz de vectores de fila, o una matriz de vectores de columna, etc.
• Este es el código de golf , por lo que la respuesta más corta en bytes gana.
• Se aplican reglas estándar para su respuesta, por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados y programas completos de tipo retorno.
• Las lagunas predeterminadas están prohibidas.

Casos de prueba

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

2. [[1,2,3,4],[5,6,7,8]]→ 1+2+7+8→ salida: 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→ salida: 75.

4. [[1,2,3,4,5],[6,7,8,9,10]]→ 1+2+8+9+10(usando la ≥condición de error) → salida: 30.

Sin embargo, si fuera más corto usar la desigualdad estricta >en su código, entonces el resultado permitido es 1+2+3+9+10=25, pero debe mencionarlo por separado.

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

6. [[-0.3,0.5]]→ salida: 0.2.

7. [[3.1],[2.9]]→ salida: 6.

8. [[-5]]→ salida: -5.

Más información sobre el algoritmo de Bresenham

• http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm : una colección de algoritmos para diferentes idiomas;
• https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html : una buena explicación con diferentes casos para pendientes;
• https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm ;

Jalea , 25 bytes

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

Pruébalo en línea!

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

Originalmente pensé en usar la función GLINE para dibujar una línea, pero no parece usar el algoritmo correcto. Sin embargo, GTRI no parecen funcionar,

Caso de prueba 4 salidas 30.

La entrada es una matriz 2D en forma [Y, X], junto con el ancho / alto (no hay forma de verificar las dimensiones de una matriz, solo el número total de elementos).

Javascript (ES6), 110 103 bytes

Salidas 25para el cuarto caso de prueba.

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)

Pruébalo en línea!

O 88 bytes si se permite tomar las dimensiones de la matriz como entrada.

Python 3.X, 269 bytes

Con entrada como filas delimitadas por comas de números delimitados por espacios.

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)

Pre-golf:

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 al usuario la entrada (cuadro de diálogo emergente) y luego imprima el resultado en la pantalla.

Simplemente dibuje una línea en la pantalla y calcule la salida. Usa desigualdad estricta.

Esto solo admite tamaños de matriz hasta el tamaño del lienzo de FMSLogo (aproximadamente 500 × 500)

Código sin golf:

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