29
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Two more (albeit slightly redundant) cases within the example: the first 6 (again) as there is a 5 five positions to it's right; or the second 7 (again) as there is a 6 six positions to it's left. \$\endgroup\$ – Jonathan Allan Sep 21 '16 at 19:19
  • \$\begingroup\$ 1. On my phone the title appears to be "Find the largest number positions away from an". 2. The condition stated is that there exists some k such that (a property that doesn't depend on k). It surely must be wrong. \$\endgroup\$ – Peter Taylor Sep 22 '16 at 7:22
  • \$\begingroup\$ @PeterTaylor "this" in "this element" refers to k. \$\endgroup\$ – Taemyr Sep 22 '16 at 8:13
  • 1
    \$\begingroup\$ @Taemyr, that doesn't make sense for two reasons: firstly, because k is not stated to be an element; and secondly because we're asked to "find the largest element satisfying" the condition, so "this element" has an antecedent outside the condition. \$\endgroup\$ – Peter Taylor Sep 22 '16 at 8:28
  • 2
    \$\begingroup\$ Maybe you could avoid all confusion by saying "find the largest element k such that" and then use k instead of this element in the definition? \$\endgroup\$ – Martin Ender Sep 22 '16 at 11:43

23 Answers 23

3
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Hmm, not sure what the policy about this is, but you now have two different approaches in separate answers, in the same program language by the same user. Wouldn't it be more advisable to put both 9- and 10-byte snippets in the same answer, since it's the same programming language and both by you? I can understand multiple answers in the same programming language by multiple users, but I personally think different approaches by the same user in the same programming language would be better suited as edits. Just my opinion. \$\endgroup\$ – Kevin Cruijssen Sep 22 '16 at 7:23
  • 5
    \$\begingroup\$ That was my first meta question, and the consensus seemed to be that different approaches should be posted in different answers. In this case, my approaches don't have anything but the maximum at the end in common, so I went for a separate post. \$\endgroup\$ – Dennis Sep 22 '16 at 7:29
8
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ You probably use it all the time, but I only just noticed "wrap stack in a list". Neat. \$\endgroup\$ – GreenAsJade Sep 23 '16 at 2:04
  • \$\begingroup\$ @GreenAsJade: Yeah it's one of the commands I use the most :) \$\endgroup\$ – Emigna Sep 23 '16 at 6:08
7
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Since you're not using x, it should be shorter to define a function in z and compose in zip[0..]. \$\endgroup\$ – xnor Sep 22 '16 at 4:14
6
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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

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

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.

\$\endgroup\$
  • \$\begingroup\$ I'm loving these excel golfs - who'd'a thought!! \$\endgroup\$ – GreenAsJade Sep 23 '16 at 2:06
4
\$\begingroup\$

JavaScript (ES6), 61 bytes

a=>Math.max(...a.filter((_,i)=>a.some((e,j)=>e==i-j|e==j-i)))
\$\endgroup\$
4
\$\begingroup\$

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

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

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
\$\endgroup\$
  • \$\begingroup\$ }# is the same as @. Also, if you rearrange the last bit to ,-kb+bk you can remove the last k since Pyth auto-inserts it. \$\endgroup\$ – PurkkaKoodari Sep 22 '16 at 5:12
  • \$\begingroup\$ @Pietu1998 Thanks. I didn't know about the implicit fill for enumerate; does that work for any other map-type functions? \$\endgroup\$ – TheBikingViking Sep 22 '16 at 15:51
  • \$\begingroup\$ Works for any lambda, it autofills the rest of any lambda with the first lambda variable. \$\endgroup\$ – PurkkaKoodari Sep 22 '16 at 16:15
3
\$\begingroup\$

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).
\$\endgroup\$
  • \$\begingroup\$ The behaviour of function YT has changed in release 20.2.2. Now it uses 1 input by default (which is more useful in general). While that would save you 1 byte here (remove t before YT), it can't be exploited because the change in the language postdates the challenge. But it has the effect that your answer is no longer valid in the new release, which is now live in TIO \$\endgroup\$ – Luis Mendo Jul 21 '17 at 22:17
  • \$\begingroup\$ You can either edit the linked code and leave a note, or use this link to the to MATL Online interpreter, which supports older releases. Unfortunately you also need to update the other links. Sorry for the inconvenience \$\endgroup\$ – Luis Mendo Jul 21 '17 at 22:17
  • \$\begingroup\$ Irrespective of that, you can save 1 byte replacing n: by f \$\endgroup\$ – Luis Mendo Jul 21 '17 at 22:18
2
\$\begingroup\$

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}
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Input format is flexible by default. You can take v as a column vector, just state that in the answer. Also, you replace find by ~~ to save two more bytes \$\endgroup\$ – Luis Mendo Sep 22 '16 at 10:47
  • \$\begingroup\$ @LuisMendo Thanks, I edited the post to incorporate your suggestions! \$\endgroup\$ – Nick Alger Sep 22 '16 at 11:04
  • \$\begingroup\$ For different languages (or a significantly different approach in the same language) you should post another answer. There's a MATL chatroom should you have any questions regarding the language \$\endgroup\$ – Luis Mendo Sep 22 '16 at 12:12
  • \$\begingroup\$ BTW, due to a bug in MATL's toeplitz (YT), it uses two inputs (not one) by default \$\endgroup\$ – Luis Mendo Sep 22 '16 at 12:13
  • \$\begingroup\$ Ok cool. I translated it to MATL and posted another answer here: codegolf.stackexchange.com/a/94183/42247 \$\endgroup\$ – Nick Alger Sep 22 '16 at 13:34
1
\$\begingroup\$

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.

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

Scala, 94 bytes

a=>a.zipWithIndex.filter(p=>a.zipWithIndex.exists(x=>x._1==Math.abs(p._2-x._2))).unzip._1.max
\$\endgroup\$
1
\$\begingroup\$

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;
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need x & y. Just reuse one of them(-2). Also i don't think you can set r in a huge ternary-if because you always have to test both cases, left and right. \$\endgroup\$ – mrco Sep 23 '16 at 10:38
  • 1
    \$\begingroup\$ @mrco Thanks, removed the ,y. And I indeed came to the same conclusion regarding the single ternary if. Of course it is possible, but you'll do the check twice making it a lot longer. \$\endgroup\$ – Kevin Cruijssen Sep 23 '16 at 11:09
1
\$\begingroup\$

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;}
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! :) \$\endgroup\$ – Martin Ender Sep 23 '16 at 22:09
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ you can use .map instead of .each \$\endgroup\$ – Cyoce Sep 23 '16 at 20:58
  • \$\begingroup\$ also (x) if (y) can be replaced with (y)&&(x) \$\endgroup\$ – Cyoce Sep 23 '16 at 20:59
  • \$\begingroup\$ You can use a<<b instead of a+=[b] \$\endgroup\$ – Sherlock9 Sep 24 '16 at 7:02
  • \$\begingroup\$ @Sherlock9 I forgot about << . Using a+=[b] didn't work with Cyoce's suggestion using &&. Now it does, thanks! \$\endgroup\$ – Tony S. Sep 24 '16 at 22:39
1
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\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.