Zainspirowany tym .

Agatha Stephendale, studentka drugiego roku, która naprawdę interesuje się grafiką rastrową, rozpoczęła kurs algebry liniowej. Teraz wyobraża sobie matryce jako prostokąty, ale w swoim artystycznym umyśle przywiązuje do nich prostokąty i próbuje obliczyć wzdłuż nich ślady. W rzeczywistości chce obliczyć ślady wszystkich macierzy, nie tylko kwadratowych.

Ponieważ Agatha jest artystką, wie, jak rysować linie w swoim ulubionym edytorze obrazów, a ten drugi wykorzystuje algorytm Bresenhama do kreślenia linii. Sprawdziła nawet Wikipedię i znalazła pseudokod:

 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

(Zauważ, że ten pseudokod działa tylko na zboczach mniejszych niż 1; w przypadku wysokich siatek należy wykonać podobną obróbkę, ale z zapętleniem y. Zobacz te sekcje dla dwóch przypadków.)

Agata wyobraża sobie macierz jako prostokąt, rysuje w niej linię ukośną, a algorytm Bresenhama określa, które elementy macierzy należą do przekątnej. Następnie bierze ich sumę i właśnie to chce wdrożyć w jak najmniejszej liczbie bajtów, ponieważ jest biedną studentką i nie może sobie pozwolić na dyski twarde o dużej pojemności do przechowywania swojego kodu.

Zadanie

Biorąc pod uwagę macierz A , zwróć sumę elementów, które leżą na zrasteryzowanej głównej przekątnej (od górnego lewego do dolnego prawego), gdzie to ostatnie jest określone przez algorytm liniowy Bresenhama. To znaczy, zakładając, że macierz reprezentuje siatkę m × n , narysuj linię na tej siatce od A [1, 1] do A [m, n] przy użyciu algorytmu Bresenhama i weź sumę wszystkich elementów na linii. Zauważ, że w przypadku macierzy 1 × N i N × 1 cała macierz staje się własną przekątną (ponieważ w ten sposób rysuje się linię od pierwszego elementu pierwszego rzędu do ostatniego elementu ostatniego rzędu).

Dane wejściowe: macierz rzeczywista (może być macierzą 1 × 1, macierzą rzędów, macierzą kolumny lub macierzą prostokątną). Wyjście: liczba.

Zauważ, że niektóre źródła (np. Pseudokod Wikipedii powyżej) używają sprawdzania warunku error≥0.5, podczas gdy inne źródła używają error>0.5. Powinieneś użyć pierwotnie zaksięgowanej ( error≥0.5), ale jeśli alternatywa error>0.5jest krótsza w kodzie, możesz ją zaimplementować (ponieważ jest to kod golfowy), ale wyraźnie o tym wspomnij . Zobacz przypadek testowy 4.

Zasady wyzwania

• Formaty we / wy są elastyczne. Macierz może składać się z kilku wierszy liczb rozdzielanych spacjami oddzielonych znakami nowego wiersza lub tablicy wektorów wierszowych lub tablicy wektorów kolumnowych itp.
• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
• Do odpowiedzi mają zastosowanie standardowe reguły , więc możesz używać STDIN / STDOUT, funkcji / metody z odpowiednimi parametrami i zwracanymi typami, pełnych programów.
• Domyślne luki są zabronione.

Przypadki testowe

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

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

4. [[1,2,3,4,5],[6,7,8,9,10]]→ 1+2+8+9+10(stosując ≥warunek błędu) → wyjście: 30.

Jeśli jednak krótsze byłoby użycie ścisłej nierówności >w kodzie, to dozwolone dane wyjściowe są 1+2+3+9+10=25, ale należy o tym wspomnieć osobno.

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

6. [[-0.3,0.5]]→ wyjściowa: 0.2.

7. [[3.1],[2.9]]→ wyjściowa: 6.

8. [[-5]]→ wyjściowa: -5.

Więcej informacji o algorytmie Bresenhama

• http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm - zbiór algorytmów dla różnych języków;
• https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html - ładne wyjaśnienie przedstawiające różne przypadki stoków;
• https://en.wikipedia.org/wiki/Bresenham%27s_line_alameterm ;

Galaretka , 25 bajtów

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

Wypróbuj online!

SmileBASIC, 101 99 bajtów

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

Początkowo myślałem o użyciu funkcji GLINE do narysowania linii, ale wydaje się, że nie używa ona prawidłowego algorytmu. Jednak GTRI nie wydaje się działać,

Przypadki testowe 4 wyjścia 30.

Dane wejściowe to tablica 2D w formie [Y, X] wraz z szerokością / wysokością (nie ma możliwości sprawdzenia wymiarów tablicy, tylko całkowita liczba elementów).

JavaScript (ES6), 110 103 bajty

Dane wyjściowe 25dla 4. przypadku testowego.

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)

Wypróbuj online!

Lub 88 bajtów, jeśli przyjmowanie wymiarów macierzy jako danych wejściowych jest dozwolone.

Python 3.X, 269 bajtów

Z danymi wejściowymi jako rozdzielanymi przecinkami rzędami liczb rozdzielanych spacjami.

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)

Przed golfem:

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 bajtów

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

Pełny program, poproś użytkownika o wprowadzenie danych (wyskakujące okno dialogowe), a następnie wydrukuj dane wyjściowe na ekranie.

Wystarczy narysować linię na ekranie i obliczyć wynik. Używaj ścisłej nierówności.

Obsługuje tylko rozmiar matrycy do rozmiaru płótna FMSLogo (około 500 × 500)

Nieskluczony kod:

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