Evaluate Index of Multidimensional Coordinates

9

A collection of N dimensional coordinates are provided. An example is below:

{2,3,4}

This can be thought of as a 3 dimensional array with 2x's, 3y's and 4z's; there may be any number of dimensions. In the example, there are 24 total nodes. Each node can be indexed using {x,y,z}. To access the 5th node, the provided indices would be {0, 1, 0} based on the table below.

## | x y z
     0 1 2
-----------
0  | 0 0 0
1  | 0 0 1
2  | 0 0 2
3  | 0 0 3
4  | 0 1 0
5  | 0 1 1
6  | 0 1 2
7  | 0 1 3
8  | 0 2 0
...
23 | 1 2 3

The purpose of this application is to work backwards to determine an index if given a node number.

If asked for the "y" index of the 8th node, the program should print "2".

With the following input provided:

{2,3,4}|8|1
<List of Coordinates>|<Node>|<Index>

The following should be printed:

2

You can assume that the input will be provided in some convenient manner in your language of choice and does not require bounds checking. For example you may assume that the provided index of choice ("y" in the example) is valid with respect to the provided coordinates. You may use 0 or 1 based indexing; the example presumes 0 based.

This is sort of the reverse of this question: Index of a multidimensional array

Mark Johnson

Posted 2017-05-04T22:33:43.080

Reputation: 387

1Perhaps add a few test cases – Luis Mendo – 2017-05-04T23:14:55.793

1Can we let the coordinates run from 1 to x instead of 0 to x-1? So node #0 would be (1,1,1) and node #23 (2,3,4). – nimi – 2017-05-05T15:55:05.070

@nimi Yes, 1 based indexing is fine. – Mark Johnson – 2017-05-06T15:17:43.620

Answers

4

MATL, 8 bytes

PiX[vPi)

This uses 1-based indexing for the node and for the dimensions. So the first nodes are 1, 2 etc; and the "x" dimension is 1, "y" is 2 etc.

Try it online!

Explanation

The key is to use function X[ (corresponding to ind2sub in Matlab or Octave), which converts a linear index into multidimensional indices. However, the order of dimensions if the opposite as defined in the challenge, so P (flip) is needed before calling the function, and again after concatenating (v) its ouputs.

P    % Implicit input: size as a row vector. Flip
i    % Input: node (linear) index
X[   % Convert from linear index to multidimensional indices. Produces
     % as many outputs as entries there are in the size vector
v    % Concatenate all outputs into a column vector
P    % Flip
i    % Input: dimension
)    % Index: select result for that dimension. Implicitly display

Luis Mendo

Posted 2017-05-04T22:33:43.080

Reputation: 87 464

3

Haskell, 45 bytes

(#) takes three arguments and returns an integer, use as [2,3,4]#8$1.

l#n=(zipWith mod(scanr(flip div)n$tail l)l!!)

Try it online!

How it works

  • l is the list of coordinates, n the node number. l#n is a function that takes the final index i.
  • Given the example list [2,3,4] and node 8, first the list's tail is taken, giving [3,4]. Then this is scanned from the right, dividing the node number by each element consecutively, giving the list [0,2,8].
  • Then the list [0,2,8] and the original l=[2,3,4] are zipped with the modulus operator, giving [0,2,0].
  • At last the !! list indexing operator is partially applied, with the resulting function ready to be given the final index.

Ørjan Johansen

Posted 2017-05-04T22:33:43.080

Reputation: 6 914

3

Haskell, 38 30 29 28 bytes

l#n=(mapM(\x->[1..x])l!!n!!)

This uses 0-based indices and coordinates starting at 1. Try it online!

Turn each dimension x of the input into a list [1..x], e.g. [2,3,4] -> [[1,2],[1,2,3],[1,2,3,4]]. mapM makes a list of all possible n-tuples where the first element is taken from the first list, etc. Two times !! to index the n-tuple and dimension.

Edit: @Ørjan Johansen saved 8 9 bytes. Thanks!

nimi

Posted 2017-05-04T22:33:43.080

Reputation: 34 639

Ooh, clever! But mapM id.map f=mapM f. And (`take`[0..]) is shorter. – Ørjan Johansen – 2017-05-05T20:41:23.470

@ØrjanJohansen: 8 bytes, that's massive! Thanks a lot! Still waiting for an answer of the OP if 1-based coordinates are allowed. – nimi – 2017-05-05T21:27:13.293

Also, l#n=(mapM(`take`[0..])l!!n!!) is shorter. (Incidentally you didn't need the f=, functions can be anonymous. Oh, I guess you aren't counting it.) – Ørjan Johansen – 2017-05-05T21:56:14.837

@ØrjanJohansen: Thanks again. The f= was a copy and paste error from TIO. – nimi – 2017-05-05T22:55:54.473

3

APL (Dyalog Classic), 5 bytes

⎕⌷⎕⊤⎕

No, you're not missing a font. That's how it's supposed to look.

This is a REPL program that takes input from STDIN: the node number, the dimensions, and the index (in that order). The latter can be 0- or 1-based, depending on the value of ⎕IO.

Try it online!

How it works

Multidimensional array indexing is essentially mixed base conversion, so does what the first part of the challenge asks for. Each occurrence of reads and evals a line from STDIN, so

      ⎕ ⊤ ⎕
⎕:
      8
⎕:
      2 3 4
0 2 0

Finally, takes the element at the specified index. The leftmost reads the third and last input from STDIN and

      ⎕ ⌷ (0 2 0)
⎕:
      1
2

Dennis

Posted 2017-05-04T22:33:43.080

Reputation: 196 637

Mixed base conversion strikes again! – Adám – 2017-05-06T22:04:09.303

2

Brachylog, 25 23 bytes

tT&bhH&h{>ℕ}ᵐ:H≜ᶠ⁾t:T∋₎

Try it online!

The second argument is 1-indexed, the other 2 are 0 indexed.

Explanation

tT                          Input = [_, _, T]
  &bhH                      Input = [_, H, T]
      &h{>ℕ}ᵐ               Create a list where each element is between 0 and the
                              corresponding element in the first element of the Input
             :H≜ᶠ⁾          Find the first H possible labelings of that list
                  t         Take the last one
                   :T∋₎     Output is the T'th element

Fatalize

Posted 2017-05-04T22:33:43.080

Reputation: 32 976

1

Jelly, 7 6 bytes

Œp⁴ị⁵ị

Try it online!

This uses 1-indexing for input and output.

How it works

Œp⁴ị⁵ị
Œp      Cartesian product of the first input
        numbers are converted to 1-based ranges
  ⁴ị    index specified by second input
    ⁵ị  index specified by third input

Leaky Nun

Posted 2017-05-04T22:33:43.080

Reputation: 45 011

1

Mathematica, 26 23 bytes

Array[f,#,0,Or][[##2]]&

Using 1-based indexing for input, and 0-based indexing for output.

Why Or? Because it is the shortest built-in function with the attribute Flat.

Example:

In[1]:= Array[f,#,0,Or][[##2]]&[{2,3,4},9,2]

Out[1]= 2

alephalpha

Posted 2017-05-04T22:33:43.080

Reputation: 23 988

1

APL (Dyalog), 6 bytes

To get 0-based indexing, ⎕IO←0, which is default on many systems. Prompts for dimensions, then enclosed list of (node,coordinate).

⎕⊃↑,⍳⎕

Try it online!

 prompt for dimensions

 generate an array of that shape with each item being the indices for that item

, ravel (make into list of indices)

 convert one level of depth to an additional level of rank

⎕⊃ prompt for enclosed list of (node,coordinate) and use that to pick an element from that

Adám

Posted 2017-05-04T22:33:43.080

Reputation: 37 779

0

Octave, 63 bytes

function z=f(s,n,d)
[c{nnz(s):-1:1}]=ind2sub(flip(s),n);z=c{d};

Port of my MATL answer.

Try it online!

Luis Mendo

Posted 2017-05-04T22:33:43.080

Reputation: 87 464

0

Pyth, 12 bytes

@.n]@*FUMQEE

Try it online!

How it works

@.n]@*FUMQEE
       UMQ    map each element in the first input to
              [0,1,...,that element]
     *F       reduce by Cartesian product
    @     E   obtain index at second input
 .n]          listify and flatten
@          E  obtain index at third input

Leaky Nun

Posted 2017-05-04T22:33:43.080

Reputation: 45 011

0

R, 52 bytes

function(x,y,z,n,i)expand.grid(1:z,1:y,1:x)[n,4-i]-1

returns an anonymous function, 1-indexed.

for the example. expand.grid generates the list, but the first argument varies the fastest, so we have to input them in reverse order, i.e., z,y,x. Then we can simply index [n,4-i], where 4-i is necessary for the reversed order, and subtract 1 to ensure they run from 0:(x-1), etc.

Try it online!

Giuseppe

Posted 2017-05-04T22:33:43.080

Reputation: 21 077

0

Java, 77 bytes

int f(int[]a,int m,int n){for(int i=a.length-1;i>n;m/=a[i--]);return m%a[n];}

Try it online!

Leaky Nun

Posted 2017-05-04T22:33:43.080

Reputation: 45 011

0

JavaScript (ES6), 44 bytes

(a,n,i,g=j=>a[++j]?g(j)/a[j]|0:n)=>g(i)%a[i]

Ungolfed:

(a,n,i)=>a.reduceRight(([n,...a],e)=>[n/e|0,n%e,...a],[n])[i+1]

Sadly reduce is two bytes longer:

(a,n,i)=>a.reduce((r,d,j)=>j>i?r/d|0:r,n)%a[i]

Neil

Posted 2017-05-04T22:33:43.080

Reputation: 95 035

Looks like we came up with the same idea \o/

– Leaky Nun – 2017-05-06T00:56:58.497

@LeakyNun Well, it's not surprising really, given how the indexing works. – Neil – 2017-05-06T01:02:03.983

0

Python 3, 57 bytes

lambda a,m,n:f(a[:-1],m//a[-1],n)if len(a)-n else m%a[-1]

Try it online!

Fork of my Java answer.

Leaky Nun

Posted 2017-05-04T22:33:43.080

Reputation: 45 011