Dijkstra's Herausforderung

23

Präsentiert zu Ehren von APL als interaktives Tool zum 50. Geburtstag in diesem Jahr

Hintergrund

Ken [Iverson] präsentierte seine Arbeit Formalism in Programming Languages im August 1963 auf einer Arbeitskonferenz über mechanische Sprachstrukturen in Princeton, New Jersey (Backus, Curry, Dijkstra, Floyd, Iverson, Newell, Perlis, Wilkes). Das Papier zeichnet auch die Diskussion auf, die nach der Präsentation stattfand, und endete mit einem Austausch zwischen Ken und [Edsger] Dijkstra , in dem Kens Antwort auf die Frage von Dijkstra ein Einzeiler war.

Herausforderung

Wie würden Sie eine komplexere Operation darstellen, zum Beispiel die Summe aller Elemente einer Matrix M, die gleich der Summe der entsprechenden Zeilen- und Spaltenindizes sind?

Schreiben Sie ein Snippet oder einen Ausdruck (es ist kein vollständiges Programm oder eine vollständige Funktion erforderlich), um die Summe jedes Elements in einer gegebenen Ganzzahlmatrix zu berechnen, die der Summe seiner Indizes entspricht. Oder, wie FryAmTheEggman es ausdrückt: Wenn eine Matrix M mit Elementen a ij gegeben ist , wird die Summe von jedem a ij mit a ij = i + j zurückgegeben.

Sie können davon ausgehen, dass sich die Matrix bereits in einer Variablen oder einem Speicherort befindet, oder Sie können sie als Argument oder Eingabe verwenden. Sie können Indizes mit 0 oder 1 verwenden.

Testfälle

 

0 für leere Matrix

2

0für 0-basierte Indizes oder 2für 1-basierte

1 5 2
9 4 2
5 9 6

2für 0 basierend oder 10für 1 basierend

 0 3  0  4
 0 4  1  4
 4 3  1  2
-2 4 -2 -1

11

3 -1 3 3
3 -1 3 1

6für 0 basierend oder 3für 1 basierend

Anekdote

Iverson Antwort wurde ++ / ( M = ¹ ⨢ ¹) // M , das weder gültig in der ist Iverson Notation wie definiert in einer Programmiersprache , noch in dem, was APL wurde schließlich. In Iverson Notation, wäre es gewesen + / (haben M = ¹ ( μ ( M )) ⨢ ¹ ( ν ( M ))) / M . In den allerersten Versionen von APL war es +/(,M=(⍳1↑⍴M)∘.+⍳1↓⍴M)/,M.

Adam
quelle
in dem Kens Antwort auf Dijkstras Frage ein Einzeiler war. Aber dann war dieser Einzeiler falsch?
Luis Mendo
Muss ich es ausgeben oder ausdrucken oder kann ich den Ausdruck einfach als Snippet aufschreiben?
Undichte Nonne
2
@LuisMendo Nein, Iverson hat die Sprache aktiv gestaltet, und bei dieser Iteration stimmte sein Einzeiler. "APL" wurde mit der Herausgabe des Buches A P rogramming L Anguage berühmt , aber zum Zeitpunkt der Veröffentlichung war der zweite Ausdruck erforderlich. Keine dieser Notationen wurde jemals maschinenausführbar implementiert.
Adám
@LeakyNun Schreiben Sie ein Snippet oder einen Ausdruck zur Berechnung
Adám
@ Adám Danke. Es macht jetzt mehr Sinn
Luis Mendo

Antworten:

9

APL, 13-12 Bytes

1 Byte danke an @ jimmy23013.

1-indiziert.

Das Array wird in der Variablen gespeichert m.

+ /, m × m = + / ¨⍳⍴m
+ / ∊m∊¨ + / ¨⍳⍴m

Probieren Sie es online!

Basierend auf der Antwort in J , einer Sprache, die auf APL basiert.

Geben Sie in TryAPL Folgendes ein: +/m`em`c`1+/`1`i`rm

Mit dem Array: +/m`em`c`1+/`1`i`rm `[ 2 4 `r 3 `21 3 3 3 `21 3 1

Erläuterung

+/∊m∩¨+/¨⍳⍴m
           m    temp ← variable
          ⍴     temp ← shape of temp
         ⍳      temp ← a 2D array where each element is
                       the corresponding index. for the
                       example, this gives:
                       ┌───┬───┬───┬───┐
                       │1 1│1 2│1 3│1 4│
                       ├───┼───┼───┼───┤
                       │2 1│2 2│2 3│2 4│
                       └───┴───┴───┴───┘
      +/¨       each element in temp ← its sum
   m∩¨          temp ← intersect each element in temp with the variable
+/              temp ← sum of temp
Undichte Nonne
quelle
Schließlich wartete ich auf diesen.
Adám
Ich bin mir nicht sicher, ob "Eingeben:" eine gute Idee ist. Dies gilt nur für TryAPL und RIDE, nicht jedoch für das Hauptprodukt. Zumindest können Sie erklären, dass `dies "APL-Schlüssel" bedeutet.
Adám
1
+/∊m∩¨+/¨⍳⍴m.
Jimmy23013
@ jimmy23013 Das ist wirklich gut!
Adám
9

MATL , 15 14 10 Bytes

3#fbb+y=*s

Die Eingabe enthält durch getrennte Zeilen ;. Zum Beispiel: [1 5 2; 9 4 2; 5 9 6]. 1-basierte Indizierung wird verwendet.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Ich werde das Beispiel mit der Eingabe [3 -1 3 3; 3 -1 3 1]in der Erklärung verwenden.

3#f    % Three-output find: for all nonzero values of implicit input matrix, pushes
       % three column vectors with row indices, column indices, and values
       %   Stack contains: [1;2;1;2;1;2;1;2], [1;1;2;2;3;3;4;4], [3;3;-1;-1;3;3;3;1]
bb     % Bubble up twice: move vectors of row and column indices to top
       %   Stack contains: [3;3;-1;-1;3;3;3;1], [1;2;1;2;1;2;1;2], [1;1;2;2;3;3;4;4]
+      % Element-wise sum of top two arrays
       %   Stack contains: [3;3;-1;-1;3;3;3;1], [2;3;3;4;4;5;5;6]
y      % Duplicate the vector of nonzero values onto the top of the stack
       %   Stack contains: [3;3;-1;-1;3;3;3;1], [2;3;3;4;4;5;5;6], [3;3;-1;-1;3;3;3;1] 
=      % Element-wise equality test of top two arrays
       %   Stack contains: [3;3;-1;-1;3;3;3;1], [0;1;0;0;0;0;0;0]
*      % Element-wise multiply of top two arrays
       %   Stack contains: [0;3;0;0;0;0;0;0]
s      % Sum of array
       %   Stack contains: 3
Luis Mendo
quelle
6

JavaScript, 49 46 Bytes

a.map((b,i)=>b.map((c,j)=>r+=c==i+j&&c),r=0)|r

Bearbeiten: 3 Bytes dank @MartinEnder gespeichert, der darauf hinweist, dass Snippets zulässig sind.

Neil
quelle
5

Netzhaut , 46 Bytes

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.

\d+
$*
M!`(?<=(\S* |.*¶)*)(?<-1>1)+\b(?(1)1)
1

Die Eingabe verwendet Leerzeichen und Zeilenumbrüche zur Darstellung der Matrix. Indizes sind 0-basiert.

Probieren Sie es online!

Erläuterung

Nicht ganz die Herausforderung, für die Retina gemacht wurde, aber sie macht sich überraschend gut ... :)

Stufe 1: Substitution

\d+
$*

Dies erweitert einfach alle Ganzzahlen in der Zeichenfolge als unäre Zahlen, wobei 1als unäre Ziffer verwendet wird. Negative Zahlen wie -3werden einfach zu Dingen wie -111.

Stufe 2: Match

M!`(?<=(\S* |.*¶)*)(?<-1>1)+\b(?(1)1)

Aufgrund der !Option werden alle Übereinstimmungen der angegebenen Regex gedruckt. Said Regex prüft mit Hilfe von Bilanzkreisen , ob die aktuelle Zahl mit der Summe seiner Indizes übereinstimmt.

Dazu ermitteln wir zunächst die Summe der Indizes mit dem Lookbehind (?<=(\S* |.*¶)*). Dies fügt ein Capture für jede Nummer vor dem aktuellen Capture in derselben Zeile (Via \S* ) sowie ein Capture für jede Zeile vor dem aktuellen Capture (Via .*¶) zur Gruppe hinzu 1. Daher erhalten wir als Ergebnis die auf Null basierende Summe der Indizes.

Dann versuchen wir, die gesamte nächste Zahl abzugleichen, während wir Captures von diesem Stapel mit entfernen (?<-1>1)+\b. Und dann machen wir das Spiel nicht , wenn alle Aufnahmen auf Gruppe verbleibt 1mit (?(1)1)Gleichheit zu gewährleisten.

Beachten Sie, dass negative Zahlen niemals übereinstimmen, da der Lookbehind nicht über die -Liste vor 1s hinausgeht und (?<-1>1)+auch nicht übereinstimmt.

Dies gibt uns eine Liste aller unären Zahlen, die der Summe ihrer Indizes entsprechen.

Stufe 3: Spiel

1

Wir beenden mit einer weiteren Match-Phase, aber ohne die !Option zählt dies nur die Anzahl der Matches, die beide alle unären Zahlen des vorherigen Ergebnisses summieren und diese Summe ebenfalls in Dezimalzahlen umwandeln.

Martin Ender
quelle
Können Sie unary als Eingabe verwenden?
Undichte Nonne
@LeakyNun Weiß nicht, ich habe irgendwie versucht, es zu vermeiden. Es scheint einfach zu abgedreht zu sein, zumal Retina keine Probleme mehr mit der Konvertierung hat.
Martin Ender
4

Jelly, 15 14 10 Bytes

4 Bytes dank Adnan.

1-indiziert.

L € R € + "LR $ = ³ × ³FS 
L € R € +" LR $ = × ³FS
J € + "J = × ⁸FS

Probieren Sie es online!

Überprüfen Sie alle Testfälle auf einmal. (Leicht verändert.)

Undichte Nonne
quelle
Ich bin mir nicht sicher, ob es funktioniert, aber kannst du es J€stattdessen tun L€R€?
Adnan
1
Oh mein Gott, du bist ein Genie.
Undichte Nonne
4

Python 2 - 60 57 Bytes

Es ist ein Code-Snippet, also wären es ein paar Bytes mehr, wenn ich den Wert tatsächlich zurückgeben würde, denke ich. e=enumerate;sum(i*(x+y==i)for x,r in e(a)for y,i in e(r))

Danke für die Hilfe Leaky Num :-)

Schnelle Erklärung. aist ein Array, das Zahlen enthält. Durchlaufen Sie einfach die Indizes und addieren Sie alle Werte, bei denen der Wert der Summe des Index entspricht.

Jeremy
quelle
Oh, es hat nicht funktioniert.
Jeremy
Vielleicht möchten Sie den Link einfügen, den ich Ihnen gerade gegeben habe.
Undichte Nonne
4

R, 24 Bytes

sum(M[M==row(M)+col(M)])

1-basiert.
Testfälle:

> M<-matrix(nrow=0,ncol=0)
> M
<0 x 0 matrix>
> sum(M[M==row(M)+col(M)])
[1] 0
> M<-matrix(2,nrow=1,ncol=1)
> M
     [,1]
[1,]    2
> sum(M[M==row(M)+col(M)])
[1] 2
> M<-matrix(c(1,9,5,5,4,9,2,2,6),nrow=3)
> M
     [,1] [,2] [,3]
[1,]    1    5    2
[2,]    9    4    2
[3,]    5    9    6
> sum(M[M==row(M)+col(M)])
[1] 10
> M<-matrix(c(0,0,4,-2,3,4,3,4,0,1,1,-2,4,4,2,-1),nrow=4)
> M
     [,1] [,2] [,3] [,4]
[1,]    0    3    0    4
[2,]    0    4    1    4
[3,]    4    3    1    2
[4,]   -2    4   -2   -1
> sum(M[M==row(M)+col(M)])
[1] 11
> M<-matrix(c(3,3,-1,-1,3,3,3,1),nrow=2)
> M
     [,1] [,2] [,3] [,4]
[1,]    3   -1    3    3
[2,]    3   -1    3    1
> sum(M[M==row(M)+col(M)])
[1] 3
Plannapus
quelle
3

J, 15 Bytes

+/,M*M=+/&i./$M

Verwendet die nullbasierte Indexierung und geht davon aus, dass die Matrix bereits in der Variablen M gespeichert ist .

Erläuterung

+/,M*M=+/&i./$M
             $a  Get the shape of M
            /    Insert between the shape
         &i.     Create a range from 0 to each end exclusive
       +/        Forms a table which is the sum of each row and column index
     M=          1 if the element is equal to its index sum else 0
   M*            Multiply by their values
  ,              Flatten
+/               Reduce using addition to get the sum
Meilen
quelle
3
Nicht nur bis jetzt am kürzesten; +1 für das Ausführen in einer Iverson-Sprache.
Adám
3

CJam, 23 21 20 Bytes

Vielen Dank an Peter Taylor für das Speichern von 3 Bytes.

ee{~_@f-_,,.=.*~}%1b

Erwartet, dass sich die Matrix auf dem Stapel befindet, und belässt stattdessen die Summe. In beiden Fällen basieren die Indizes auf Null.

Teste es hier.

Martin Ender
quelle
Sie können ein Paar mit _,,anstelle der inneren eeund .für die innere Schleife speichern :ee{~_,,@f+1$.=.*~}%1b
Peter Taylor
@ PeterTaylor Ah ordentlich, danke. :)
Martin Ender
In der Tat gibt es eine weitere, indem Sie eine Art Meet-in-the-Middle:ee{~_@f-_,,.=.*~}%1b
Peter Taylor
3

k4, 24 Bytes

Angenommen, die Matrix ist in gespeichert m.

+//7h$m*m=(!#m)+/:\:!#*m

Dies ist eines dieser Rätsel, bei denen die Vereinfachungen beim Entwerfen von k aus APL (und J) wirklich weh tun - k !ist das Äquivalent von APL , funktioniert jedoch nur mit Vektoren. inneres Produkt ist ein Zeichen in APL, aber fünf in k; und ich verliere drei Zeichen, wenn ich mit der leeren Matrix richtig umgehe, weil k keine stark typisierten Matrizen hat.

Aaron Davies
quelle
2
Auf der anderen Seite haben Sie eine mächtige Sprache, die viel konsistenter und mit viel weniger zu lernenden Primitiven ist.
Adám
2

PowerShell v2 +, 43 Byte

%{$j=0;$_|%{$o+=$_*($_-eq$i+$j++)};$i++};$o

Als Ausschnitt. Die Matrix wird explizit dazu weitergeleitet (siehe Beispiele unten). Angenommen $i, und$o am Anfang entweder null oder null sind (ich habe sie in den folgenden Beispielen explizit als solche festgelegt), und verwendet den 0-Index.

Führt in jeder Zeile der Matrix eine foreach-Schleife aus. Wir setzen $jauf 0und durchlaufen dann jedes Element der Zeile in einer anderen Schleife $_|%{...}. Jede innere Schleife wird $oum das aktuelle Element multipliziert mit einem Booleschen Wert inkrementiert ($_-eq$i+$j++), was bedeutet, dass, wenn $TRUEes sich um einen Booleschen Wert handelt , dies auch der Fall 1ist 0. Dann verlassen wir die innere Schleife, inkrementieren $iund beginnen die nächste Reihe. Endlich gehen wir$o die Pipeline am Ende.

Beispiele

PS C:\Tools\Scripts\golfing> $o=0;$i=0;$j=0;@(@(3,-1,3,3),@(3,-1,3,1))|%{$j=0;$_|%{$o+=$_*($_-eq$i+$j++)};$i++};$o
6

PS C:\Tools\Scripts\golfing> $o=0;$i=0;$j=0;@(@(0,3,0,4),@(0,4,1,4),@(4,3,1,2),@(-2,4,-2,-1))|%{$j=0;$_|%{$o+=$_*($_-eq$i+$j++)};$i++};$o
11
AdmBorkBork
quelle
2

Ruby, 63 Bytes

Mit z als zweidimensionales Array von Zahlen:

s=0;z.each_index{|i|z[i].each_index{|j|s+=i+j if z[i][j]==i+j}}

Gar nicht so aufregend.

Wenn z ein abgeflachtes Array ist, wobei x und y die Größe der Arrays haben, wie z.

x=z.size
y=z[0].size
z=z.flatten

Dann haben wir diese Ungeheuerlichkeit - vielleicht rubinroter mit ihren ausgefallenen Produkten und Reißverschlüssen, aber tatsächlich größer:

(1..x).to_a.product((1..y).to_a).zip(z).inject(0){|s,n|s+(n[0][0]+n[0][1]==n[1]+2?n[1]:0)}
David Ljung Madison Stellar
quelle
Vielleicht gibt es eine schickere Array- oder Enumerator-Methode, die es verkürzen würde. Ich habe sie noch nicht gefunden, aber ich würde sie gerne sehen.
David Ljung Madison Stellar
2

Eigentlich 21 Bytes

ñ`i╗ñ"i╜+@;(=*"£Mi`MΣ

Probieren Sie es online!

Vielen Dank an Leaky Nun, dass ich aufgehört habe faul zu sein, und schreibe dies endlich.

Dies verwendet 0-indizierte Matrizen und nimmt Eingaben als verschachtelte Liste an.

Erläuterung:

ñ`i╗ñ"i╜+@;(=*"£Mi`MΣ
ñ                      enumerate input
 `i╗ñ"i╜+@;(=*"£Mi`M   for each (i, row) pair:
  i╗                     flatten, store i in register 0
    ñ                    enumerate the row
     "i╜+@;(=*"£M        for each (j, val) pair:
      i╜+                  flatten, add i to j
         @;(               make an extra copy of val, bring i+j back to top
            =              compare equality of i+j and val
             *             multiply (0 if not equal, val if they are)
                 i       flatten the resulting list
                    Σ  sum the values
Mego
quelle
2

Matlab / Octave, 48 Bytes

1-indiziert.

Wird den ersten Testfall nicht bearbeiten, weil er [1:0]aus irgendeinem Grund die Größe 1x0 hat

sum(sum(M.*(M-[1:size(M,1)]'-[1:size(M,2)]==0)))

Getestet in Oktave 3.

Volles Programm:

M = [2]
sum(sum(M.*(M-[1:size(M,1)]'-[1:size(M,2)]==0)))
M = [1 5 2; 9 4 2; 5 9 6]
sum(sum(M.*(M-[1:size(M,1)]'-[1:size(M,2)]==0)))
M = [ 0 3  0  4; 0 4  1  4; 4 3  1  2;-2 4 -2 -1]
sum(sum(M.*(M-[1:size(M,1)]'-[1:size(M,2)]==0)))
M = [ 3 -1 3 3; 3 -1 3 1]
sum(sum(M.*(M-[1:size(M,1)]'-[1:size(M,2)]==0)))
SpamBot
quelle
Willkommen bei PPCG! In Octave können Sie tun sum((M.*(M-[1:size(M,1)]'-[1:size(M,2)]==0))(:)). Ich denke auch, dass Sie ==0durch und initial ändern können, um die Byteanzahl ~weiter zu reduzieren. Schließlich beachten Sie, dass Sie alle Testfälle behandeln müssen, oder die Frage sollte gelöscht werden
Luis Mendo
1

Lua, 70 Bytes

1-indiziert.

s=0 for i=1,#a do for j=1,#a[i]do s=i+j==a[i][j]and s+i+j or s end end

Bonus: Es funktioniert für zerlumpte Arrays!

Eingabe gespeichert in a, Ausgabe gespeichert ins .

Volles Programm:

function Dijkstras_Challenge(a)
    s=0 for i=1,#a do for j=1,#a[i]do s=i+j==a[i][j]and s+i+j or s end end
    print(s)
end

Dijkstras_Challenge({})
Dijkstras_Challenge({{2}})
Dijkstras_Challenge({{1,5,2},{9,4,2},{5,9,6}})
Dijkstras_Challenge({{0,3,0,4},{0,4,1,4},{4,3,1,2},{-2,4,-2,-1}})
Dijkstras_Challenge({{3,-1,3,3},{3,-1,3,1}})
Undichte Nonne
quelle
1

PHP, 59 Bytes

foreach($a as$y=>$r)foreach($r as$x=>$v)$s+=($v==$x+$y)*$v;

erwartet, dass das Array $ a definiert ist; muss leer oder 2-dimensional, 0-indiziert sein.
berechnet Summe auf $ s (bisher 0 oder nicht definiert - 0 gleich NULL)
Einsatz +2vor dem endgültigen) für 1-indiziertes Verhalten

Alles Gute zum Geburtstag APL!

Funktionen und Testsuite

function f0($a) { foreach($a as$y=>$r)foreach($r as$x=>$v)$s+=($v==$x+$y)*$v;return $s|0; }
function f1($a) { foreach($a as$y=>$r)foreach($r as$x=>$v)$s+=($v==$x+$y+2)*$v;return $s|0;}
$samples = [
    [], 0, 0,
    [[2]], 0, 2,
    [[1,5,2],[9,4,2],[5,9,6]], 2, 10,
    [[0,3,0,4],[0,4,1,4],[4,3,1,2],[-2,4,-2,-1]],11,11,
    [[3,-1,3,3],[3,-1,3,1]],6,3
];
function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',cmp($e,$y)?'N':'Y',"</td></tr>";$h='';}
while($samples)
{
    $a=array_shift($samples);
    test($a,'B0:'.array_shift($samples),'B0:'.f0($a));
    test($a,'B1:'.array_shift($samples),'B1:'.f1($a));
}
Titus
quelle
1

Brachylog , 15 Bytes

{iiʰI-ʰ=∧Ihh}ᶠ+

Probieren Sie es online!

              +    The output is the sum of
{           }ᶠ     all possible results of
 i                 taking a row from the input with its index,
  i                taking an element with its index
   ʰ               from that row,
    I    Ihh       and outputting the element
       =∧          so long as the index of the row is equal to
     -ʰ            the value of the element minus its index within the row.
Nicht verwandte Zeichenfolge
quelle
1

Wolfram Language (Mathematica) , 42 Byte

ArrayRules/*Cases[p_~_~v_/;Tr@p==v:>v]/*Tr

Probieren Sie es online!

1-indiziert.

ArrayRules                                  (*Convert into a list of (position->value) Rules*)
          /*Cases[p_~_~v_/;Tr@p==v          (*select those where sum(position)==value*)
                                  :>v]/*Tr  (*and find the sum of those values*)
attinat
quelle