# Dijkstra's Challenge

## Presented in honor of APL as an interactive tool turning 50 this year

### Background

Ken [Iverson] presented his paper Formalism in Programming Languages in August 1963 at a Working Conference on Mechanical Language Structures, Princeton, N.J. The list of conferees is full of famous and soon-to-be famous names, and a few future Turing Award winners (Backus, Curry, Dijkstra, Floyd, Iverson, Newell, Perlis, Wilkes). The paper also records the discussion that occurred after the presentation, ending with an exchange between Ken and [Edsger] Dijkstra, in which Ken’s reply to Dijkstra’s question was a one-liner.

### Challenge

How would you represent a more complex operation, for example, the sum of all elements of a matrix M which are equal to the sum of the corresponding row and column indices?

Write a snippet or expression (no need for a full program or function) to calculate the sum of each element in a given integer matrix which is equal to the sum of its indices. Or, as FryAmTheEggman puts it: given a matrix M with elements aij return the sum of each aij where aij = i + j.

You may assume the matrix already being in a variable or memory location, or you may take it as an argument or input. You may use either 0 or 1 based indices.

### Test cases




0 for empty matrix

2


0 for 0 based indices or 2 for 1-based

1 5 2
9 4 2
5 9 6


2 for 0 based or 10 for 1 based

 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


6 for 0 based or 3 for 1 based

### Anecdote

Iverson's answer was ++/(M = ¹ ⨢ ¹)//M, which is neither valid in the Iverson Notation as defined in A Programming Language, nor in what eventually became APL. In Iverson notation, it would have been +/(M = ¹(μ(M)) ⨢ ¹(ν(M)))/M. In the very first versions of APL it was +/(,M=(⍳1↑⍴M)∘.+⍳1↓⍴M)/,M.

• in which Ken’s reply to Dijkstra’s question was a one-liner. But then that one-liner was wrong? – Luis Mendo Jul 19 '16 at 14:52
• Do I need to output it or print it out, or can I just write down the expression as a snippet? – Leaky Nun Jul 19 '16 at 15:01
• @LuisMendo No, Iverson was actively designing the language, and at that iteration, his one-liner was correct. "APL" became famous with the publishing of the book A Programming Language, but at the time of publishing, the second expression was needed. Neither of these notations were ever implemented to be machine-executable. – Adám Jul 19 '16 at 15:04
• @LeakyNun Write a snippet or expression to calculate – Adám Jul 19 '16 at 15:05
• @Adám Thanks. It makes more sense now – Luis Mendo Jul 19 '16 at 15:06

# APL, 13 12 bytes

1 byte thanks to @jimmy23013.

1-indexed.

The array is stored in the variable m.

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


Try it online!

Based on the answer in J, which is a language based on APL.

In TryAPL, to key in: +/memc1+/1irm

With the array: +/memc1+/1irm [ 2 4 r 3 21 3 3 3 21 3 1

### Explanation

+/∊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

• Finally, I was waiting for this one. – Adám Jul 19 '16 at 15:23
• I'm not sure the "To key in:" is a good idea. It only applies to TryAPL and RIDE, but not to the main product. At least you can explain that  means "APL key". – Adám Jul 19 '16 at 15:24
• +/∊m∩¨+/¨⍳⍴m. – jimmy23013 Jul 19 '16 at 15:34
• @jimmy23013 That's really good! – Adám Jul 19 '16 at 16:12

# MATL, 1514 10 bytes

3#fbb+y=*s


The input has rows separated by ;. For example: [1 5 2; 9 4 2; 5 9 6]. 1-based indexing is used.

### Explanation

I'll use the example with input [3 -1 3 3; 3 -1 3 1] in the explanation.

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


## JavaScript, 49 46 bytes

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


Edit: Saved 3 bytes thanks to @MartinEnder pointing out that snippets are allowed.

## Retina, 46 bytes

Byte count assumes ISO 8859-1 encoding.

\d+
$* M!(?<=(\S* |.*¶)*)(?<-1>1)+\b(?(1)1) 1  Input uses space and linefeed separators to represent the matrix. Indices are 0-based. Try it online! ### Explanation Not quite the kind of challenge Retina was made for, but it's doing surprisingly well... :) Stage 1: Substitution \d+$*


This simply expands all the integers in the string as unary numbers using 1 as the unary digit. Negative numbers like -3 will simply become things like -111.

Stage 2: Match

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


Due to the ! option, this prints all the matches of the given regex. Said regex uses balancing groups to check whether the current number is the same as the sum of its indices.

To do that, we first determine the sum of indices with the lookbehind (?<=(\S* |.*¶)*). This adds one capture for each number in front of the current one on the same line (via \S* ) as well as one capture for each line in front of the current one (via .*¶) to group 1. Hence, we get the zero-based sum of indices as a result.

Then we try to match the entire next number while removing captures from this stack with (?<-1>1)+\b. And then we make the match fail if any captures are left on group 1 with (?(1)1) to ensure equality.

Note that negative numbers are never matched, because the lookbehind cannot get past the - in front of list of 1s and the (?<-1>1)+ can't match it either.

This gives us a list of all the unary numbers which equal the sum of their indices.

Stage 3: Match

1


We end with another match stage, but without the ! option, this just counts the number of matches, which both sums all the unary numbers from the previous result and also converts that sum back to decimal.

• Can you use unary as input? – Leaky Nun Jul 19 '16 at 15:04
• @LeakyNun Don't know, I've kinda been trying to avoid it. It just seems too hacky, especially since Retina has no trouble with the conversion any more. – Martin Ender Jul 19 '16 at 15:07

# Jelly, 1514 10 bytes

1-indexed.

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


Try it online!

Verify all testcases at once. (Slightly modified.)

• I'm not sure if it works, but can you do J€ instead of L€R€? – Adnan Jul 19 '16 at 14:52
• Oh my God, you're a genius. – Leaky Nun Jul 19 '16 at 14:53

# Python 2 - 60 57 bytes

It's a code snippet, so it would be a few more bytes if I actually returned the value, I guess. e=enumerate;sum(i*(x+y==i)for x,r in e(a)for y,i in e(r))

Thanks for the help Leaky Num :-)

Quick explanation. a is an array holding numbers. Simply iterate through indexes and sum up all values where the value equals the sum of the index.

# R, 24 bytes

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


1-based.
Test cases:

> M<-matrix(nrow=0,ncol=0)
> M
<0 x 0 matrix>
> sum(M[M==row(M)+col(M)])
 0
> M<-matrix(2,nrow=1,ncol=1)
> M
[,1]
[1,]    2
> sum(M[M==row(M)+col(M)])
 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)])
 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)])
 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)])
 3


# J, 15 bytes

$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  • Not only shortest until now; +1 for doing it in an Iverson language. – Adám Jul 19 '16 at 13:30 ## CJam, 2321 20 bytes Thanks to Peter Taylor for saving 3 bytes. ee{~_@f-_,,.=.*~}%1b  Expects the matrix to be on the stack and leaves the sum instead. Indices are zero-based in either case. Test it here. • You can save a couple with _,, instead of the inner ee and . for the inner loop: ee{~_,,@f+1$.=.*~}%1b – Peter Taylor Jul 19 '16 at 13:57
• @PeterTaylor Ah neat, thank you. :) – Martin Ender Jul 19 '16 at 13:59
• In fact, there's one more, by doing a kind of meet-in-the-middle: ee{~_@f-_,,.=.*~}%1b – Peter Taylor Jul 19 '16 at 14:07

# k4, 24 bytes

Assumes the matrix is stored in m.

+//7h$m*m=(!#m)+/:\:!#*m  This is one of those puzzles where the simplifications involved in designing k from APL (and J) really hurt—k’s ! is the equivalent of APL’s ⍳ but only works on vectors, so I have to assemble the matrix of indices myself; inner product is one character in APL but five in k; and I lose three characters to handling the empty matrix properly because k doesn’t have strongly-typed matrices. • On the other hand, you have a powerful language which is much more consistent, and with much fewer primitives to learn. – Adám Jul 24 '16 at 8:24 # Pyth, 14 bytes 0-indexed. ss.e.e*ZqZ+kYb  Test suite. ## PowerShell v2+, 43 bytes %{$j=0;$_|%{$o+=$_*($_-eq$i+$j++)};$i++};$o


As a snippet. Usage is to explicitly pipe the matrix to this (see examples below). Assumes that $i, and $o are either null or zero at the start (I've explicitly set them as such in the examples below), and utilizes 0-index.

Does a foreach loop on each row of the matrix. We set $j to 0, and then go through each element of the row in another loop $_|%{...}. Each inner loop, we increment $o by the current element multiplied by a Boolean ($_-eq$i+$j++), meaning if that Boolean is $TRUE, it'll be 1, otherwise 0. Then we exit the inner loop, increment $i, and start the next row. Finally, we leave $o on the pipeline at the end. ### Examples 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  # Ruby, 63 bytes With z as a two-dimensional array of numbers: s=0;z.each_index{|i|z[i].each_index{|j|s+=i+j if z[i][j]==i+j}}  Not terribly exciting at all. If z is a flattened array with x and y having the sizes of the arrays, such as: x=z.size y=z.size z=z.flatten  Then we have this monstrousity - perhaps more ruby-ish with it's fancy products and zips, but actually larger: (1..x).to_a.product((1..y).to_a).zip(z).inject(0){|s,n|s+(n+n==n+2?n:0)}  • Perhaps there is a fancier array or enumerator method that would shorten it, I haven't found it yet, but I'd love to see it. – David Ljung Madison Stellar Jul 20 '16 at 4:06 ## Actually, 21 bytes ñi╗ñ"i╜+@;(=*"£MiMΣ  Try it online! Thanks to Leaky Nun for making me stop being lazy and finally write this. This uses 0-indexed matrices, and takes input as a nested list. Explanation: ñi╗ñ"i╜+@;(=*"£MiMΣ ñ enumerate input i╗ñ"i╜+@;(=*"£MiM 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  # Matlab/Octave, 48 bytes 1-indexed. Will not handle the first test case because [1:0] has size 1x0 for some reason sum(sum(M.*(M-[1:size(M,1)]'-[1:size(M,2)]==0)))  Tested in Octave 3. Full program: M =  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)))  • Welcome to PPCG! In Octave you can do sum((M.*(M-[1:size(M,1)]'-[1:size(M,2)]==0))(:)). Also, I think you can change ==0 by and initial ~ to further reduce byte count. Finally, note that you need to handle all test cases or else the question should be deleted – Luis Mendo Jul 20 '16 at 15:13 # Lua, 70 bytes 1-indexed. 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: it works for ragged arrays! Input stored in a, output stored in s. # Full program: 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}})  # PHP, 59 bytes foreach($a as$y=>$r)foreach($r as$x=>$v)$s+=($v==$x+$y)*$v;


expects array $a defined; must be empty or 2-dimensional, 0-indexed. calculates sum to$s (previously 0 or undefined - 0 equals NULL)
insert +2 before final ) for 1-indexed behaviour

Happy Birthday APL!

functions and test suite

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, [], 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));
}


# Brachylog, 15 bytes

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


Try it 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.


# Wolfram Language (Mathematica), 42 bytes

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


Try it online!

1-indexed.

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*)
`