Find the largest number n positions away from n

Question

_{A sequel to this question.}

Task

Given an array of positive integers, find the largest element k for which:

There exists some positive integer distance n, so that the element in the array located n places to the left or right from k equals n.

The array is guaranteed to contain at least one element satisfying this condition.

The shortest code (in bytes) wins. You may choose whichever I/O format you like.

Example

Given the input

[4, 6, 7, 9, 3, 6, 5, 7, 2]

The eligible values are:

• The 4, as there is a 7 located 7 positions to its right
• The first 6, as there is a 3 located 3 positions to its right
• The 3, as there is a 4 located 4 positions to its left
• The 5, as there is a 2 located 2 positions to its right
• The second 7, as there is a 3 located 3 positions to its left.

Of these values, the largest is 7.

Test cases

[1, 13] → 13
[2, 9, 8, 3, 72, 2] → 8
[5, 28, 14, 5, 6, 3, 4, 7] → 14
[1, 3, 5, 15, 4, 1, 2, 6, 7, 7] → 7
[5, 1, 3, 5, 2, 5, 5, 8, 5, 1, 5, 1, 2, 3] → 5
[5, 12, 2, 5, 4, 7, 3, 3, 6, 2, 10, 5, 5, 5, 4, 1, 8, 5] → 10

Answer 1

Jelly, 9 bytes

Jạþ`=ḅa¹Ṁ

Try it online! or verify all test cases.

How it works

Jạþ`=ḅa¹Ṁ  Main link. Argument: A (array)

J          Indices; yield [1, ..., len(A)].
   `       Use the previous return value as left and right argument:
 ạþ        Absolute difference table; take the absolute value of the difference
           of each pair of indices, yielding a 2D array.
    =      Compare each absolute difference with the corresponding item of A.
     ḅ     Base; convert each Boolean list from base i to integer, where i is the
           corresponding item of A. The value of i is not important; we only care
           if the list contains a 1, which will result in a non-zero integer.
       ¹   Identity; yield A.
      a    Logical AND; replace non-zero values with the corresponding items of A.
        Ṁ  Take the maximum.

Answer 2

05AB1E, 21 bytes

vyN+Ny-})¹gL<Ãv¹yè})Z

Explanation

v      }               # for each num in input
 yN+                   # push index + num
    Ny-                # push index - num
        )              # wrap stack in a list
         ¹gL<Ã         # remove indices outside the range of input
              v¹yè})   # get list of elements in input at the remaining indices
                    Z  # get max

Try it online!

Answer 3

Haskell, 61 57 55 bytes

f x=maximum[a|(n,a)<-x,(i,b)<-x,b==abs(n-i)]
f.zip[0..]

Usage example: (f.zip[0..]) [5,28,14,5,6,3,4,7] -> 14.

(More or less) a direct implementation of the definition: for each index n of the input list x keep a := x!!n if there's an index i where b := x!!i equals abs(n-i). Find the maximum.

Edit: @xnor saved two bytes. Thanks!

Answer 4

Jelly, 10 bytes

,N+JFfJị¹Ṁ

Try it online! or verify all test cases.

How it works

,N+JFfJị¹Ṁ  Main link. Argument: A (array)

,N          Pair A with -A (element-wise negative).
   J        Yield the indices of A [1, ..., len(A)].
  +         Add the elements of A (and their negatives) with the corr. indices.
    F       Flatten the resulting 2D array.
     fJ     Filter indices; remove invalid indices (not in [1, ..., len(A)]) from
            the generated array. The result is the list of all indices of eligible
            elements of A.
       ị¹   Retrieve the corresponding elements of A.
         Ṁ  Take the maximum.

Answer 5

Python 3, 85 80 72 Bytes

lambda l,e=enumerate:max(i for p,i in e(l)for s,j in e(l)if j==abs(s-p))

Edit: -8 Bytes thanks to @Dennis

Answer 6

EXCEL: 32 30 bytes

=MAX(IF(A:A-ROW(A:A)<0,A:A,0))

I still cannot believe I got it to be this short...

How to use:
paste this into ANY cell EXCEPT the cells of column A. After pasting, while still editing, press control+shift+enter to correctly enter it.
put your values into column A, 1 value per cell (as per CSV entry).

If you want to find out how this works, I've posted an additional tip in my Tips for golfing in Excel question.

Answer 7

JavaScript (ES6), 61 bytes

a=>Math.max(...a.filter((_,i)=>a.some((e,j)=>e==i-j|e==j-i)))

Answer 8

Perl, 45 bytes

Includes +2 for -ap

Give numbers on a line on STDIN:

largest.pl <<< "5 12 2 5 4 7 3 3 6 2 10 5 5 5 4 1 8 5"

largest.pl:

#!/usr/bin/perl -ap
($_)=sort{$b-$a}map@F[$^P=$n-$_,$n+++$_],@F

One more byte can be gained by replacing ^P by the literal control character, but that leads to a warning on STDERR on recent perls.

Assumes largest number + array length < 2^32

Answer 9

Pyth, 19 17 bytes

Thanks to @Pietu1998 for -2 bytes

eS@LQ@UQs.e,-kb+b

A program that takes input of a list on STDIN and prints the result.

Try it online

How it works

eS@LQ@UQs.e,-kb+b  Program. Input: Q
         .e        Map over Q (implicit input fill) with elements as b and indices as k:
            -kb     k-b
               +b   k+b (Implicit fill with k)
           ,        2-element list of those (possible indices)
        s          Flatten that
      UQ           Yield [0, 1, 2, 3..., len(Q)-1]
     @             Filter the flattened list by presence in the above, removing invalid
                   indices
  @LQ              Index into Q at those indices
 S                 Sort that
e                  Yield the last element of that, giving the maximum
                   Implicitly print

Answer 10

MATL, 13 Bytes

ttn:tYTq=a)X>

Input must be a column vector. I.e., input is semicolon-separated like [1;2;3], or comma separated with a transpose tick at the end like [1,2,3]'.

Try it online!

All test cases: (A), (B), (C), (D), (E), (F)

Thanks to Suever for suggestions in the MATL chatroom to save 2 characters.

Explanation:

The overall strategy is the same as my Octave/MATLAB answer, where the basic concept is explained: https://codegolf.stackexchange.com/a/94161/42247

The specific code in this MATL answer is built up as follows:

The core of the method is the construction of the Toeplitz matrix whose ij'th entry is abs(i-j). We first construct the Toeplitz matrix with entries abs(i-1)+1 with MATL's toeplitz command YT as follows:

n:tYT % Equivalent to @(v)toeplitz(1:length(v))

To see how this works, let us call the input vector to this code snippet 'v'. The 'n' finds the length of v, then ':' constructs the vector 1:length(v). Next the 't' makes another copy of 1:length(v) on the stack; this extra copy is needed due to a well-known bug in the YT function in MATL (the MATL equivalent of toeplitz()), wherein it expects two copies of the input instead of 1. Then YT takes the two copies of this vector 1:length(v) off the stack, and makes the abs(i-j)+1 Toeplitz matrix from them.

Now we need to subtract 1 from this matrix to get the Toeplitz matrix with entries abs(i-j), and find the ij locations where this abs(i-j) Toeplitz matrix is equal to the matrix of all column vectors containing column-copies of the input vector v. This is done as follows:

t n:tYT q=
% t [code] q= is equivalent to @(v) [code](v)-1 == v

The first 't' makes an extra copy of the input and stores it on the stack. The 'n:tYT' makes the toeplitz matrix as described earlier and outputs it into the stack. Then 'q' subtracts 1 from the Toeplitz matrix, and '=' does the elementwise equality comparison between the abs(i-j) matrix and the vector whose columns are copies of the input. Note that by comparing a column vector to a matrix, we are implicitly taking advantage of MATLAB/MATL's operator broadcasting rules (the column vector in the comparison gets copied to make a matrix without issuing any commands).

Finally, we need to find the row indices i where there is a column j such that the ij'th entry in the matrix difference constructed above equals 1, then get the value of the input vector corresponding to these indices, then take the maximum. This in the following three steps:

1) Find the indices for any row that contains a nonzero:

tn:tYTq= a
% [code] a is equivalent to @(v) any([code](v))

2) Extract the elements of the input vector corresponding to those indices:

t tn:tYTq= a ) X>
% t [code] ) is equivalent to @(v) v([code](v)]

3) Find and return the maximum element:

t tn:tYTq= a ) X>
% [code] X> is equivalent to @(v) max(v).

Answer 11

Ruby, 66 bytes

->a{i=-1;a.map{|e|i+=1;[a[j=i+e]||0,a[0>(k=i-e)?j:k]||0].max}.max}

Answer 12

Octave / MATLAB, 40 Bytes

@(v)max(v(any(toeplitz(1:nnz(v))-v==1)))

Input must be a column vector.

Thanks to Luis Mendo for suggestions saving 3 bytes (see comment)

Thanks to Suever for suggestions saving 4 more bytes (replacing ~~(sum()) with any())

Explanation:

Given an input vector v, this problem is equivalent to finding all solutions i,j of the following discrete equation,

abs(i-j) = v(i),   i,j both in 1..k,

where abs() is the absolute value function. Each v(i) for which this equation is solved is one of the candidate solutions which we can maximize over.

As a discrete function of i and j, all possibilities for the left hand side can be arranged in the toeplitz matrix that looks something like this:

[0, 1, 2, 3, 4]
[1, 0, 1, 2, 3]
[2, 1, 0, 1, 2]    <--- abs(i-j)
[3, 2, 1, 0, 1]
[4, 3, 2, 1, 0]

And since the right hand side doesn't depend on i, all possibilities for it can be arranged into a matrix where the columns are all copies of the input,

[v(1), v(1), v(1), v(1), v(1)]
[v(2), v(2), v(2), v(2), v(2)]
[v(3), v(3), v(3), v(3), v(3)]   <--- v(i)
[v(4), v(4), v(4), v(4), v(4)]
[v(5), v(5), v(5), v(5), v(5)]

To find all solutions to the equation, we subtract these two matrices and find the locations where there is a zero. The rows where there is a zero correspond to the desired indices i's where there is a j such that abs(i-j) = v(i).

Other tricks:

• It takes less characters to construct the absolute value function plus one, abs(i-j)+1, then check for locations where the difference is 1, rather than construct the true (unshifted) absolute value function.
• Uses automatic operator broadcasting to implicitly make column copies of v
• Gets the length of the input via nnz() instead of length(), which works since the inputs are said to be positive in the problem statement.

Answer 13

Mathematica, 69 bytes

Max@MapIndexed[{If[#2[[1]]>#,a[[#2-#]],{}],a[[#2+#]]~Check~{}}&,a=#]&

Anonymous function. Takes a list of integers as input and returns an integer as output. Ignore any messages generated.

Answer 14

Scala, 94 bytes

a=>a.zipWithIndex.filter(p=>a.zipWithIndex.exists(x=>x._1==Math.abs(p._2-x._2))).unzip._1.max

Answer 15

PHP, 128 Bytes

<?foreach(($i=$_GET[i])as$k=>$v){$k-$v<0?:!($i[$k-$v]>$m)?:$m=$i[$k-$v];if($k+$v<count($i))if($i[$k+$v]>$m)$m=$i[$k+$v];}echo$m;

Answer 16

Java 7, 125 123 bytes

int c(int[]a){int r=0,i=0,l=a.length,x;for(;i<l;r=l>(x=i+a[i])?a[x]>r?a[x]:r:r,r=(x=i-a[i++])>0?a[x]>r?a[x]:r:r);return r;}

2 bytes saved thanks to @mrco.

Ungolfed (sort of) & test code:

Try it here.

class M{
  static int c(int[] a){
    int r = 0,
        i = 0,
        l = a.length,
        x;
    for(; i < l; r = l > (x = i + a[i])
                      ? a[x] > r
                         ? a[x]
                         : r
                      : r,
                 r = (x = i - a[i++]) > 0
                      ? a[x] > r
                         ? a[x]
                         : r
                      : r);
    return r;
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 1, 13 }));
    System.out.println(c(new int[]{ 2, 9, 8, 3, 72, 2 }));
    System.out.println(c(new int[]{ 5, 28, 14, 5, 6, 3, 4, 7 }));
    System.out.println(c(new int[]{ 1, 3, 5, 15, 4, 1, 2, 6, 7, 7 }));
    System.out.println(c(new int[]{ 5, 1, 3, 5, 2, 5, 5, 8, 5, 1, 5, 1, 2, 3 }));
    System.out.println(c(new int[]{ 5, 12, 2, 5, 4, 7, 3, 3, 6, 2, 10, 5, 5, 5, 4, 1, 8, 5 }));
  }
}

Output:

13
8
14
7
5
10

Answer 17

Ruby 56 bytes

My smallest ruby solution.

->n{x=[];i=0;n.map{|v|x<<n[v+i]&&v+i<n.size;i+=1};x.max}

Pretty easy to test in rails console

a = ->n{x=[];i=0;n.map{|v|x<<n[v+i]&&v+i<n.size;i+=1};x.max}
a[[1, 13]
=> 13
a[[2, 9, 8, 3, 72, 2]]
=> 8
a[[5, 12, 2, 5, 4, 7, 3, 3, 6, 2, 10, 5, 5, 5, 4, 1, 8, 5]]
=> 10

This started at 63 bytes, thanks for the suggestions to help trim it down!

Answer 18

Java, 118 bytes

int f(int[]a){int t=0,i,j,z=0,l=a.length;while(t<l*l){i=t/l;j=t++%l;z=a[i]>z&&((i<j?j-i:i-j)==a[j])?a[i]:z;}return z;}

Answer 19

Python, 58 bytes

Based on Tony S.'s Ruby answer. This answer works in Python 2 and 3. Golfing suggestions welcome.

lambda n:max([n[i+v]for i,v in enumerate(n)if i+v<len(n)])

Ungolfing

def f(array):
    result = []
    for index, value in enumerate(array):
        if index + value < len(array):
            result.append(array[index + value])
    return max(result)

Answer 20

Actually, 17 bytes

This answer is an Actually port of my Python answer. Golfing suggestions welcome. Try it online!

;╗ñ♂Σ⌠╜l>⌡░⌠╜E⌡MM

Ungolfing

         Implicit input L.
;╗       Duplicate L and save a copy of L to register 0.
ñ        enumerate() the other copy of L.
♂Σ       sum() all the pairs of [index, value of n]. Call this list Z.
⌠...⌡░   Push values of Z where the following function returns a truthy value. Variable v_i.
  ╜        Push L from register 0.
  l        Push len(L).
  >        Check if len(L) > v_i.
⌠...⌡M   Map the following function over Z_filtered. Variable i.
  ╜        Push L from register 0.
  E        Take the ith index of L.
M        max() the result of the map.
         Implicit return.

Answer 21

Clojure, 68 bytes

#(apply max(map(fn[i](get % i 0))(flatten(map-indexed(juxt - +)%))))

For example (map-indexed (juxt - +) [3 4 1 2]) is ([-3 3] [-3 5] [1 3] [1 5]) (index +/- its value), these are used to look-up values from the original vector (out-of-range defaulting to 0) and the max value is found. Still feels a bit verbose but at least I got to use juxt :)

Answer 22

T-SQL(sqlserver 2016), 132 bytes

Golfed:

;WITH C as(SELECT value*1v,row_number()over(order by 1/0)n FROM STRING_SPLIT(@,','))SELECT max(c.v)FROM C,C D WHERE abs(D.n-C.n)=D.v

Ungolfed:

DECLARE @ varchar(max)='2, 9, 8, 3, 72, 2'

;WITH C as
(
  SELECT
    value*1v,
    row_number()over(order by 1/0)n
  FROM
    STRING_SPLIT(@,',')
)
SELECT
  max(c.v)
FROM
  C,C D
WHERE
  abs(D.n-C.n)=D.v

Fiddle

Answer 23

JavaScript (ES6), 56 54 bytes

let f =
    
l=>l.map((n,i)=>m=Math.max(m,l[i+n]|0,l[i-n]|0),m=0)|m

console.log(f([1, 13])); // → 13
console.log(f([2, 9, 8, 3, 72, 2])); // → 8
console.log(f([5, 28, 14, 5, 6, 3, 4, 7])); // → 14
console.log(f([1, 3, 5, 15, 4, 1, 2, 6, 7, 7])); // → 7
console.log(f([5, 1, 3, 5, 2, 5, 5, 8, 5, 1, 5, 1, 2, 3])); // → 5
console.log(f([5, 12, 2, 5, 4, 7, 3, 3, 6, 2, 10, 5, 5, 5, 4, 1, 8, 5])); // → 10