Śledzenie macierzy dla dowolnej macierzy poprzez… rasteryzację linii Bresenhama

12

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:

wprowadź opis zdjęcia tutaj

 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 , 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.

Przypadek testowy 1

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

Przypadek testowy 2

  1. [[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.

Przypadek testowy 3

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

Przypadek testowy 4

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.

Przypadek testowy 5

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

Przypadek testowy 5

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

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

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

Więcej informacji o algorytmie Bresenhama

Andreï Kostyrka
źródło
Żądana przypadek testowy: [[1,2,3,4,5],[6,7,8,9,10]].
user202729
@ user202729 Dodano go, aby rozwiązać niejednoznaczność.
Andreï Kostyrka
Czy możemy uzyskać walizkę testową wyższą niż szeroką? Jak[[1,2],[3,4],[5,6],[7,8],[9,10]]
Giuseppe
@Giuseppe Catch. Zobacz teraz przypadek 5. Na przykład odpowiedź powinna brzmieć 28(z oczekiwaną implementacją) lub 27 (z >opcjonalną implementacją).
Andreï Kostyrka
Czy program może obsługiwać tylko macierze o ustalonym rozmiarze (powiedzmy 500 × 500)?
user202729,

Odpowiedzi:

3

Galaretka , 25 bajtów

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

Wypróbuj online!

użytkownik202729
źródło
Gdyby Jelly miał wbudowaną 1 lub 2 bajtową rundę do najbliższej liczby całkowitej, odpowiedź ta miałaby 23 lub 24 bajty.
user202729
3

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).

12Me21
źródło
1

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.

Arnauld
źródło
1

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
Budd
źródło
Wygląda na to, c=math.ceilże ten program wydłuży ...
user202729
Ponadto nie potrzebujesz []między sum(..). a if c else bczęsto może być c and a or b.
user202729,
input("")może być input().
user202729,
Również ... jaki jest format wejścia / wyjścia? Wydrukować na ekranie?
user202729,
1

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
użytkownik202729
źródło