Davon inspiriert .
Agatha Stephendale, eine Anfängerin, die sich wirklich für Rastergrafiken interessiert, hat einen Kurs in linearer Algebra belegt. Jetzt stellt sie sich Matrizen als Rechtecke vor, aber in ihrem künstlerischen Denken fügt sie diagonale Linien zu diesen Rechtecken hinzu und versucht, Spuren entlang dieser zu berechnen. Tatsächlich möchte sie die Spuren aller Matrizen berechnen, nicht nur der quadratischen.
Da Agatha Künstlerin ist, kann sie in ihrem bevorzugten Bildbearbeitungsprogramm Linien zeichnen. Letzteres verwendet den Bresenham-Algorithmus , um Linien zu zeichnen. Sie überprüfte sogar Wikipedia und fand den Pseudocode:
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
(Beachten Sie, dass dieser Pseudocode nur für Steigungen unter 1 funktioniert. Bei hohen Gittern sollte eine ähnliche Behandlung durchgeführt werden, jedoch mit einer Schleife y
. Siehe diesen Abschnitt für die beiden Fälle.)
Agatha stellt sich eine Matrix als Rechteck vor, zeichnet eine diagonale Linie darin und Bresenhams Algorithmus bestimmt, welche Elemente einer Matrix zur Diagonale gehören. Dann nimmt sie ihre Summe und dies ist es, was sie in so wenigen Bytes wie möglich implementieren möchte, weil sie ein armer Student ist und sich keine Festplatten mit hoher Kapazität leisten kann, um ihren Code zu speichern.
Aufgabe
Geben Sie bei einer Matrix A die Summe der Elemente zurück, die auf der gerasterten Hauptdiagonale liegen (von links oben nach rechts unten), wobei letztere durch den Bresenhamschen Linienalgorithmus bestimmt wird. Das heißt, unter der Annahme, dass die Matrix ein m × n- Gitter darstellt, zeichnen Sie auf diesem Gitter eine Linie von A [1, 1] bis A [m, n] unter Verwendung des Bresenham-Algorithmus und nehmen Sie die Summe aller Elemente auf der Linie. Beachten Sie, dass für 1 × N- und N × 1- Matrizen die gesamte Matrix zu einer eigenen Diagonale wird (da auf diese Weise eine Linie vom ersten Element der ersten Zeile zum letzten Element der letzten Zeile gezogen wird).
Eingabe: Eine reelle Matrix (kann eine 1 × 1- Matrix, eine Zeilenmatrix, eine Spaltenmatrix oder eine rechteckige Matrix sein). Ausgabe: eine Zahl.
Beachten Sie, dass einige Quellen (z. B. der obige Pseudocode der Wikipedia) die Bedingungsprüfung verwenden error≥0.5
, während andere Quellen diese verwenden error>0.5
. Sie sollten die ursprünglich veröffentlichte ( error≥0.5
) verwenden. Wenn die Alternative error>0.5
in Ihrem Code jedoch kürzer ist, können Sie sie implementieren (da dies Code Golf ist), erwähnen Sie sie jedoch ausdrücklich . Siehe Testfall 4.
Herausforderungsregeln
- E / A-Formate sind flexibel. Eine Matrix kann aus mehreren Zeilen von durch Leerzeichen getrennten Zahlen bestehen, die durch Zeilenumbrüche voneinander getrennt sind, oder aus einem Array von Zeilenvektoren oder einem Array von Spaltenvektoren usw.
- Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes.
- Für Ihre Antwort gelten Standardregeln. Daher dürfen Sie STDIN / STDOUT, Funktionen / Methoden mit den richtigen Parametern und vollständige Programme vom Rückgabetyp verwenden.
- Standardlücken sind verboten.
Testfälle
[[1,2,3],[4,5,6],[7,8,9]]
→1+5+9
→ Ausgang:15
.
[[1,2,3,4],[5,6,7,8]]
→1+2+7+8
→ Ausgang:18
.
[[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
→ Ausgang:75
.
[[1,2,3,4,5],[6,7,8,9,10]]
→1+2+8+9+10
(unter Verwendung der≥
Fehlerbedingung) → Ausgang:30
.
Wenn es jedoch kürzer wäre, die strenge Ungleichung >
in Ihrem Code zu verwenden, ist die Ausgabe zulässig. 1+2+3+9+10=25
Sie sollten sie jedoch separat erwähnen.
[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]
→1+5+8+12
→ Ausgang:26
.
[[-0.3,0.5]]
→ Ausgang:0.2
.[[3.1],[2.9]]
→ Ausgang:6
.[[-5]]
→ Ausgang:-5
.
Weitere Informationen zum Bresenham-Algorithmus
- http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm - eine Sammlung von Algorithmen für verschiedene Sprachen;
- https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html - eine nette Erklärung mit verschiedenen Fällen für Pisten;
- https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm ;
[[1,2,3,4,5],[6,7,8,9,10]]
.[[1,2],[3,4],[5,6],[7,8],[9,10]]
28
(mit≥
der erwarteten Implementierung) oder 27 (mit>
der optionalen Implementierung) sein.Antworten:
Gelee , 25 Bytes
Probieren Sie es online!
quelle
SmileBASIC,
10199 BytesUrsprünglich dachte ich daran, die GLINE-Funktion zum Zeichnen einer Linie zu verwenden, aber anscheinend wird nicht der richtige Algorithmus verwendet. Allerdings GTRI nicht zu funktionieren scheint,
Testfall 4 Ausgänge 30.
Die Eingabe ist ein 2D-Array in der Form [Y, X] zusammen mit der Breite / Höhe (es gibt keine Möglichkeit, die Abmessungen eines Arrays zu überprüfen, nur die Gesamtzahl der Elemente).
quelle
JavaScript (ES6),
110103 ByteAusgänge
25
für den 4. Testfall.Probieren Sie es online!
Oder 88 Bytes, wenn die Dimensionen der Matrix als Eingabe zulässig sind.
quelle
Python 3.X, 269 Bytes
Bei Eingabe als durch Kommas getrennte Zeilen mit durch Leerzeichen getrennten Zahlen.
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)
Vor dem Golfen:
quelle
c=math.ceil
das Programm länger werden ...[]
zwischen densum(..)
.a if c else b
kann oft seinc and a or b
.input("")
kann seininput()
.FMSLogo , 136 Bytes
Vollständiges Programm: Fordern Sie den Benutzer zur Eingabe auf (Popup-Dialogfeld) und drucken Sie die Ausgabe auf dem Bildschirm aus.
Zeichnen Sie einfach eine Linie auf dem Bildschirm und berechnen Sie die Ausgabe. Verwenden Sie eine strikte Ungleichung.
Dies unterstützt nur Matrixgrößen bis zur Leinwandgröße von FMSLogo (ca. 500 × 500).
Ungolfed-Code:
quelle