28
\$\begingroup\$

Lower level languages, such as C and C++ actually have no concept of multidimensional arrays. (Other than vectors and dynamic arrays) When you create a multidimensional array with

int foo[5][10];

This is actually just syntactic sugar. What C really does is create a single contiguous array of 5 * 10 elements. This

foo[4][2]

is also syntactic sugar. This really refers to the element at

4 * 10 + 2

or, the 42nd element. In general, the index of element [a][b] in array foo[x][y] is at

a * y + b

The same concept applies to 3d arrays. If we have foo[x][y][z] and we access element [a][b][c] we are really accessing element:

a * y * z + b * z + c

This concept applies to n-dimensional arrays. If we have an array with dimensions D1, D2, D3 ... Dn and we access element S1, S2, S3 ... Sn the formula is

(S1 * D2 * D3 ... * Dn) + (S2 * D3 * D4 ... * Dn) + (S3 * D4 ... * Dn) ... + (Sn-1 * Dn) + Sn

The challenge

You must write a program or function that calculates the index of a multidimensional array according to the formula above. Input will be two arrays. The first array is the dimensions, and the second array is the indices. The length of these two arrays will always be equal and at least 1.

You can safely assume that every number in the arrays will be an non-negative integer. You can also assume that you will not get a 0 in the dimension array, although a 0 might be in the indices. You can also assume that indices will not be larger than the dimensions.

Test IO

Dimensions: [5, 10]
Indices: [4, 2]
Output: 42

Dimensions: [10, 10, 4, 62, 7]
Indices: [1, 2, 3, 4, 5]
Output: 22167

Dimensions: [5, 1, 10]
Indices: [3, 0, 7]
Output: 37

Dimensions: [6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
Indices: [3, 1, 5, 5, 3, 0, 5, 2, 5, 4]
Output: 33570178
\$\endgroup\$
  • 4
    \$\begingroup\$ So this is 0-based indexing, correct? Can we use 1-based indexing if that's more natural for our language of choice? \$\endgroup\$ – Alex A. May 8 '16 at 22:00
  • \$\begingroup\$ @AlexA. Yes, that's acceptable. \$\endgroup\$ – DJMcMayhem May 8 '16 at 22:39
  • 11
    \$\begingroup\$ Actually, what C 'really does' is create a single contiguous array of five elements of type int[10]. \$\endgroup\$ – user16488 May 9 '16 at 5:57
  • \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender May 9 '16 at 9:27
  • 1
    \$\begingroup\$ @Hurkyl Yes, but all of the integers in that array are still contiguous. It's just semantics. \$\endgroup\$ – DJMcMayhem May 9 '16 at 19:27

25 Answers 25

60
\$\begingroup\$

APL, 1 byte

Test it on TryAPL.

\$\endgroup\$
  • 21
    \$\begingroup\$ Well, that's it. We have a winner. Everyone else can go home now. \$\endgroup\$ – DJMcMayhem May 8 '16 at 22:40
  • 3
    \$\begingroup\$ Why... why does this work? o_O \$\endgroup\$ – Alex A. May 8 '16 at 22:44
  • 10
    \$\begingroup\$ @AlexA. Indexing a multidimensional array is essentially mixed base conversion. \$\endgroup\$ – Dennis May 8 '16 at 22:47
  • 21
    \$\begingroup\$ Oh, look, a hole in one while golfing! \$\endgroup\$ – Nic Hartley May 10 '16 at 21:03
  • 8
    \$\begingroup\$ Most of the time I come here for fun. Then there are times when I accidentally receive profound insights \$\endgroup\$ – slebetman May 11 '16 at 7:13
11
\$\begingroup\$

J, 2 bytes

#.

Where there's an APL, there's a J! Kind of. Takes dimensions as left arg and index as right arg. "Indexing a multidimensional array is essentially mixed base conversion."

\$\endgroup\$
11
\$\begingroup\$

JavaScript (ES6), 34 bytes

(d,a)=>a.reduce((r,i,j)=>r*d[j]+i)

Surely reduce must be better than map.

\$\endgroup\$
7
\$\begingroup\$

Python, 43 bytes

f=lambda x,y:x>[]and y.pop()+x.pop()*f(x,y)

Test it on Ideone.

\$\endgroup\$
  • 15
    \$\begingroup\$ Not only does Dennis solidly thrash all of us, but he does it in every. single. language. \$\endgroup\$ – DJMcMayhem May 9 '16 at 0:17
7
\$\begingroup\$

Jelly, 7 6 bytes

Ṇ;żḅ@/

Try it online! or verify all test cases.

How it works

Ṇ;żḅ@/  Main link. Arguments: D (list of dimensions), I (list of indices)

Ṇ       Yield 0, the logical NOT of D.
  ż     Zip D with I.
        If D = [10, 10, 4, 62, 7] and I = [1, 2, 3, 4, 5], this yields
        [[10, 1], [10, 2], [4, 3], [62, 4], [7, 5]].
 ;      Concatenate, yielding [0, [10, 1], [10, 2], [4, 3], [62, 4], [7, 5]].
   ḅ@/  Reduce by swapped base conversion to integer.
        [10, 1] in base    0 is    0 × 10 + 1 = 1.
        [10, 2] in base    1 is    1 × 10 + 2 = 12.
        [ 4, 3] in base   12 is   12 ×  4 + 3 = 51.
        [62, 4] in base   51 is   51 × 62 + 4 = 3166.
        [ 7, 5] in base 3166 is 3166 ×  7 + 5 = 22167.
\$\endgroup\$
6
\$\begingroup\$

Pyth, 10 bytes

e.b=+*ZNYC

Try it online: Demonstration or Test Suite

Using Horner's method to calculate the index.

\$\endgroup\$
5
\$\begingroup\$

MATL, 9 bytes

PiPZ}N$X]

This uses 1-based indexing (now allowed by the challenge), which is the natural choice in MATL.

To compare with the test cases in the challenge, add 1 to each entry in the input index vector, and subtract 1 from the output.

Try it online!

Explanation

The code is based on the builtin X] function, which converts multidimensional indices to a single, linear index (like Matlab or Octave's sub2ind function).

P      % Take dimension vector implicitly. Reverse
iP     % Take vector of indices. Reverse
Z}     % Split vector into its elements
N$X]   % Convert indices to linear index (`sub2ind` function). Implicitly display
\$\endgroup\$
5
\$\begingroup\$

Julia, 29 27 bytes

x%y=prod(x)÷cumprod(x)⋅y

Try it online!

\$\endgroup\$
5
\$\begingroup\$

MATL, 11 bytes

4L)1hPYpP*s

This uses 0-based indexing, as in the original challenge.

Try it online!

Explanation

The code explicitly does the required multiplications and additions.

4L)    % Take first input array implicitly. Remove its first entry
1h     % Append a 1
PYpP   % Cumulative product from right to left
*      % Take second input array implicitly. Multiply the two arrays element-wise
s      % Sum of resulting array. Implicitly display
\$\endgroup\$
4
\$\begingroup\$

Python, 85 bytes

lambda a,b:sum(b[i]*eval('*'.join(str(n)for n in a[i+1:])or'1')for i in range(len(a)))

I'll probably get my butt kicked by the better python golfers out there.

\$\endgroup\$
4
\$\begingroup\$

Python 3.5, 69

lambda d,i:sum(eval("*".join(map(str,[z,*d])))for z in i if d.pop(0))

Test here

\$\endgroup\$
  • \$\begingroup\$ Nice answer! Much better than mine. \$\endgroup\$ – DJMcMayhem May 8 '16 at 23:21
  • \$\begingroup\$ @DrGreenEggsandHamDJ I stole the eval method from your solution :) \$\endgroup\$ – Alexander Nigl May 8 '16 at 23:23
4
\$\begingroup\$

Haskell, 34 bytes

a#b=sum$zipWith(*)(0:b)$scanr(*)1a

Usage example: [10,10,4,62,7] # [1,2,3,4,5] -> 22167.

How it works:

      scanr(*)1a  -- build partial products of the first parameter from the right,
                  -- starting with 1, e.g. [173600,17360,1736,434,7,1]
    (0:b)         -- prepend 0 to second parameter, e.g. [0,1,2,3,4,5]
  zipWith(*)      -- multiply both lists elementwise, e.g. [0,17360,3472,1302,28,5]
sum               -- calculate sum
\$\endgroup\$
4
\$\begingroup\$

C++, 66 bytes

A quick macro:

#include<stdio.h>
#define F(d,i) int x d;printf("%d",&x i-(int*)x)

Use like:

int main(){
    F([5][1][10], [3][0][7]);
}

This may be a bit of an abuse of the rules. Creates an array with the given size, than checks to see how far the given indexes offset the pointer. Outputs to STDOUT.

This feels so dirty... But I just love the fact that this is valid.

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 27 bytes

#~FromDigits~MixedRadix@#2&

An unnamed function which takes the list of indices as the first argument and the list of dimensions second. Based on the same observation as Dennis's APL answer that computing the index is really just a mixed-base conversion.

\$\endgroup\$
3
\$\begingroup\$

Octave, 58 54 bytes

Thanks to @AlexA. for his suggestion, which removed 4 bytes

@(d,i)reshape(1:prod(d),flip(d))(num2cell(flip(i)){:})

Input and output are 1-based. To compare with the test cases, add 1 ot each entry in the input and subtract 1 from the output.

This is an anonymous function. To call it, assign it to a variable.

Try it here.

Explanation

This works by actually building the multidimensional array (reshape(...)), filled with values 1, 2, ... in linear order (1:prod(d)), and then indexing with the multidimensional index to get the corrresponding value.

The indexing is done by converting the input multidimensional index i into a cell array (num2cell(...)) and then to a comma-separated list ({:}).

The two flip operations are needed to adapt the order of dimensions from C to Octave.

\$\endgroup\$
  • \$\begingroup\$ why does reshape have a second pair of parenthesis isnt that non syntactic? \$\endgroup\$ – Abr001am May 9 '16 at 14:33
  • \$\begingroup\$ @Agawa001 Do you mean a second pair after reshape? That's non syntactic in Matlab, but accepted in Octave. It works as an index \$\endgroup\$ – Luis Mendo May 9 '16 at 14:35
  • \$\begingroup\$ oh Octave!! that must be better and more ergonomic than matlab , tha,ks for enlightenment. \$\endgroup\$ – Abr001am May 9 '16 at 14:42
  • \$\begingroup\$ @Agawa001 It can also lead to some confusion, though \$\endgroup\$ – Luis Mendo May 9 '16 at 15:03
  • \$\begingroup\$ A tip for anonymous functions in example code: I use @(...) ... in the first line of my code, followed by f = ans; in the second. This makes the length of the first line equal to the number of bytes to report. \$\endgroup\$ – bers May 11 '16 at 13:24
3
\$\begingroup\$

CJam, 7 bytes

0q~z+:b

Try it online!

How it works

0        e# Push 0 on the stack.
 q       e# Read and push all input, e.g., "[[10 10 4 62 7] [1 2 3 4 5]]".
  ~      e# Eval, pushing [[10 10 4 62 7] [1 2 3 4 5]].
   z     e# Zip, pushing [[10 1] [10 2] [4 3] [62 4] [7 5]].
    +    e# Concatenate, pushing [0 [10 1] [10 2] [4 3] [62 4] [7 5]]
     :b  e# Reduce by base conversion.
         e# [10 1] in base    0 is    0 * 10 + 1 = 1.
         e# [10 2] in base    1 is    1 * 10 + 2 = 12.
         e# [ 4 3] in base   12 is   12 *  4 + 3 = 51.
         e# [62 4] in base   51 is   51 * 62 + 4 = 3166.
         e# [ 7 5] in base 3166 is 3166 *  7 + 5 = 22167.
\$\endgroup\$
  • \$\begingroup\$ Give us a chance, Dennis! :D \$\endgroup\$ – HyperNeutrino May 11 '16 at 17:44
2
\$\begingroup\$

Haskell, 47 bytes

Two equal length solutions:

s(a:b)(x:y)=a*product y:s b y
s _ _=[]
(sum.).s

Called like: ((sum.).s)[4,2][5,10].

Here's an infix version:

(a:b)&(x:y)=a*product y:b&y
_ & _=[]
(sum.).(&)
\$\endgroup\$
2
\$\begingroup\$

Octave, 47/43/31 bytes

@(d,i)sub2ind(flip(d),num2cell(flip(i+1)){:})-1

Test it here.

Having said that, as it was asked in a comment, 1-based indexing was said to be OK when this is natural to the language being used. In this case, we can save 4 bytes:

@(d,i)sub2ind(flip(d),num2cell(flip(i)){:})

In analogy, I argue that if the objective of the code is to linearly index an array within that language, the whole flipping around and accounting for MATLAB/Octave's column major order should not be necessary, either. In that case, my solution becomes

@(d,i)sub2ind(d,num2cell(i){:})

Test that one here.

\$\endgroup\$
  • \$\begingroup\$ Hello, and welcome to PPCG! Great answer! \$\endgroup\$ – NoOneIsHere May 11 '16 at 14:07
1
\$\begingroup\$

Mathematica, 47 bytes

Fold[Last@#2#+First@#2&,First@#,Rest/@{##}]&

(Unicode is U+F3C7, or \[Transpose].) For this, I rewrote the expression as Dn(Dn-1( ⋯ (D3(D2S1 + S2) + S3) ⋯ ) + Sn-1) + Sn. Just Folds the function over both lists.

\$\endgroup\$
1
\$\begingroup\$

Actually, 13 bytes

;pX╗lr`╜tπ`M*

Try it online!

This program takes the list of indices as the first input and the list of dimensions as the second input.

Explanation:

;pX╗lr`╜tπ`M*
;pX╗            push dims[1:] to reg0
    lr`   `M    map: for n in range(len(dims)):
       ╜tπ        push product of last n values in reg0
            *   dot product of indices and map result
\$\endgroup\$
1
\$\begingroup\$

Racket 76 bytes

(λ(l i(s 0))(if(null? i)s(f(cdr l)(cdr i)(+ s(*(car i)(apply *(cdr l)))))))

Ungolfed:

(define f
  (λ (ll il (sum 0))
    (if (null? il)
        sum
        (f (rest ll)
           (rest il)
           (+ sum
              (* (first il)
                 (apply * (rest ll))))))))

Testing:

(f '(5 10) '(4 2))
(f '(10 10 4 62 7) '(1 2 3 4 5))
(f '(5 1 10) '(3 0 7))

Output:

42
22167
37
\$\endgroup\$
0
\$\begingroup\$

C#, 73 bytes

d=>i=>{int n=d.Length,x=0,y=1;for(;n>0;){x+=y*i[--n];y*=d[n];}return x;};

Full program with test cases:

using System;

namespace IndexOfAMultidimensionalArray
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<int[],Func<int[],int>>f= d=>i=>{int n=d.Length,x=0,y=1;for(;n>0;){x+=y*i[--n];y*=d[n];}return x;};

            int[] dimensions, indices;
            dimensions =new int[]{5, 10};
            indices=new int[]{4,2};
            Console.WriteLine(f(dimensions)(indices));      //42

            dimensions=new int[]{10, 10, 4, 62, 7};
            indices=new int[]{1, 2, 3, 4, 5};
            Console.WriteLine(f(dimensions)(indices));      //22167

            dimensions=new int[]{5, 1, 10};
            indices=new int[]{3, 0, 7};
            Console.WriteLine(f(dimensions)(indices));      //37

            dimensions=new int[]{6, 6, 6, 6, 6, 6, 6, 6, 6, 6};
            indices=new int[]{3, 1, 5, 5, 3, 0, 5, 2, 5, 4};
            Console.WriteLine(f(dimensions)(indices));      //33570178
        }
    }
}
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 39 bytes

->\d,\i{sum i.map:{[×] $_,|d[++$ ..*]}}

A rather naive golf here, just squished a anonymous sub.

Perl 6 has an anonymous state variable $ which is useful for creating a counter in a loop (eg, using post-increment $++ or pre-increment ++$). I pre-increment this state variable to increment the starting index of the dimension array slice inside a map.

Here's a ungolfed function that creates the sub-lists

sub md-index(@dim, @idx) {
    @idx.map(-> $i { $i, |@dim[++$ .. *] })
}
say md-index([10, 10, 4, 62, 7], [1, 2, 3, 4, 5]);
# OUTPUT: ((1 10 4 62 7) (2 4 62 7) (3 62 7) (4 7) (5))

Then it's just a matter of reducing the sub-lists with the multiplication (×) operator, and suming the results.

sub md-index(@dim, @idx) {
    @idx.map(-> $i { [×] $i, |@dim[++$ .. *] }).sum
}
say md-index([10, 10, 4, 62, 7], [1, 2, 3, 4, 5]);
# OUTPUT: 22167
\$\endgroup\$
0
\$\begingroup\$

Perl, 71 bytes

sub{$s+=$_[1][-$_]*($p*=$_[0][1-$_])for($p=$_[0][$s=0]=1)..@{$_[0]};$s}

Ungolfed:

sub {
    my $s = 0;
    my $p = 1;

    $_[0]->[0] = 1;
    for (1 .. @{$_[1]}) {
        $p *= $_[0]->[1 - $_];
        $s += $_[1]->[-$_] * $p;
    }

    return $s;
}
\$\endgroup\$
0
\$\begingroup\$

C++17, 133 115 bytes

-18 bytes for using auto...

template<int d,int ...D>struct M{int f(int s){return s;}int f(int s,auto...S){return(s*...*D)+M<D...>().f(S...);}};

Ungolfed:

template <int d,int ...D> //extract first dimension
struct M{
 int f(int s){return s;} //base case for Sn
 int f(int s, auto... S) { //extract first index 
  return (s*...*D)+M<D...>().f(S...); 
  //S_i * D_(i+1) * D(i+2) * ... + recursive without first dimension and first index
 }
};

Usage:

M<5,10>().f(4,2)
M<10,10,4,62,7>().f(1,2,3,4,5)

Alternative, only functions, 116 bytes

#define R return
#define A auto
A f(A d){R[](A s){R s;};}A f(A d,A...D){R[=](A s,A...S){R(s*...*D)+f(D...)(S...);};}

Ungolfed:

auto f(auto d){
  return [](auto s){
   return s;
  };
}
auto f(auto d, auto...D){
  return [=](auto s, auto...S){
    return (s*...*D)+f(D...)(S...);
  };
}

Usage:

f(5,10)(4,2)
f(10,10,10)(4,3,2)
f(10,10,4,62,7)(1,2,3,4,5)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.