Dijkstra's Challenge

Question

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 a_ij return the sum of each a_ij where a_ij = 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.

Answer 1

MATL, 15 14 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.

Try it online! Or verify all test cases.

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

Answer 2

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: +/m`em`c`1+/`1`i`rm

With the array: +/m`em`c`1+/`1`i`rm `[ 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

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

Answer 4

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.

Answer 5

Jelly, 15 14 10 bytes

4 bytes thanks to Adnan.

1-indexed.

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

Try it online!

Verify all testcases at once. (Slightly modified.)

Answer 6

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.

Answer 7

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)])
[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

Answer 8

CJam, 23 21 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.

Answer 9

J, 15 bytes

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

Uses zero-based indexing and assumes the matrix is already stored in variable M.

Explanation

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

Answer 10

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.

Answer 11

Pyth, 14 bytes

0-indexed.

ss.e.e*ZqZ+kYb

Test suite.

Answer 12

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

Answer 13

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[0].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[0][0]+n[0][1]==n[1]+2?n[1]:0)}

Answer 14

Actually, 21 bytes

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

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╜+@;(=*"£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

Answer 15

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 = [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)))

Answer 16

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.

Answer 17

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

Answer 18

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

Answer 19

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