12
\$\begingroup\$

The Challenge

Given a grid of numbers (10 <= N <= 99) Return number with the highest sum of the four numbers adjacent to it; that is the numbers above, below, right, and left of the number, but not itself.

  1. The number itself does not count, only its four neighbors.
  2. A number on the edge should be treated as though the missing number is a 0.
  3. I will design the test to avoid ties.
  4. Numbers will not repeat.
  5. This is .

Example

Given

56 98 32 96
12 64 45 31
94 18 83 71

Return

18

A Real Test

Given

98 95 67 66 57 16 40 94 84 37
87 14 19 34 83 99 97 78 50 36
18 44 29 47 21 86 24 15 91 61
60 41 51 26 10 58 11 62 55 71
42 85 56 12 46 81 93 65 49 77
89 13 74 39 54 76 92 33 82 90
96 88 70 79 80 28 25 20 75 68
38 63 17 72 53 48 73 30 45 69
64 35 32 31 23 43 22 52 27 59

Return

13

Given

82 43 79 81 94 36 17 64 58
24 52 13 87 70 18 28 61 69
16 99 75 21 50 44 89 90 51
49 80 63 31 54 65 41 55 38
67 91 76 78 23 86 83 14 73
46 68 62 77 34 48 20 74 10
33 35 26 97 59 66 25 37 32
12 92 84 27 85 56 22 40 45
96 15 98 53 39 30 88 71 29
60 42 11 57 95 19 93 72 47

Return

15
\$\endgroup\$
  • 1
    \$\begingroup\$ "A number on the edge can be treated as though the missing number is a 0." - That implies we have a choice as to how to handle numbers on an edge of the grid. Can we therefore choose to wrap around to the other side of the grid? \$\endgroup\$ – Shaggy Jun 20 '18 at 13:55
  • \$\begingroup\$ @Shaggy No. That might change the expected result. Let's all do it the same way. Text updated s/can/should/ \$\endgroup\$ – Umbrella Jun 20 '18 at 14:37
  • 2
    \$\begingroup\$ waiting for the inevitable MATL answer \$\endgroup\$ – Fatalize Jun 20 '18 at 14:39
  • \$\begingroup\$ I notice most of the solutions mutate the input in some way. Is that conventional here? My (yet to be posted) solution includes the bytes required to mutate the input and I'm wondering why many others do not. \$\endgroup\$ – Umbrella Jun 20 '18 at 19:15
  • 1
    \$\begingroup\$ @Umbrella We generally don't care if the input gets modified. We're interested in short code, not clean code. So long as the output is right, we tend to be pretty permissive. \$\endgroup\$ – Mnemonic Jun 21 '18 at 2:37

11 Answers 11

9
\$\begingroup\$

MATL, 20 15 13 12 bytes

t1Y6Z+tuX>=)

Saved 5 bytes thanks to Emigna, 2 thanks to Giuseppe, and another thanks to Luis Mendo.
Try it online!

Explanation

t1Y6Z+tuX>=)
t                  Duplicate the (implicit) input.
 1Y6               Push the array [0 1 0; 1 0 1; 0 1 0].
    Z+             Convolve with the input.
       uX>         Get the maximum unique element...
      t   =        ... and compare elementwise.
           )       Index into the input.
\$\endgroup\$
6
\$\begingroup\$

APL (Dyalog Unicode), 31 27 26 24 23 bytesSBCS

-2 thanks to Cows quack. -1 thanks to ngn.

Anonymous tacit prefix function. Takes a matrix as argument. Assumes ⎕IO (Index Origin) to be 0, which is default on many systems.

{⊃⍒,(+/--/)⊢∘,⌺3 3⊢⍵}⊃,

Try it online!

, ravel (flatten) the input

{}⊃ pick an element from that according to the result of the following function:

⊢⍵ yield the argument (separates 3 3 from )

 …⌺3 3 apply the following function to each 3-by-3 neighbourhood:

  ⊢∘, ignore the edge-information in favour of the ravelled (flattened) neighbourhood

  () apply the following tacit function to those

   -/ the alternating sum (lit. right-associative minus reduction)

   +/- subtract that from the sum (this gives the sum of every other element)

, ravel (flatten) that (the neighbourhood sums)

 produce the indices which would sort that

 pick the first (i.e. the index of the highest sum)

\$\endgroup\$
  • \$\begingroup\$ That was fast. Did you come prepared? ;) \$\endgroup\$ – Umbrella Jun 20 '18 at 14:52
  • 3
    \$\begingroup\$ @Umbrella No, I just use a programming language which is quick to program in. \$\endgroup\$ – Adám Jun 20 '18 at 15:07
  • 3
    \$\begingroup\$ How's this {⊃⍒,{+/1↓⍉4 2⍴⍵}⌺3 3⊢⍵}⊃,? Edit: or even {⊃⍒,{⊢/+⌿4 2⍴⍵}⌺3 3⊢⍵}⊃, \$\endgroup\$ – Cows quack Jun 20 '18 at 15:47
  • \$\begingroup\$ @Cowsquack I always forget that trick. \$\endgroup\$ – Adám Jun 20 '18 at 16:21
  • 2
    \$\begingroup\$ -1 byte: {⊃⍒,(+/--/)⊢∘,⌺3 3⊢⍵}⊃, \$\endgroup\$ – ngn Jun 20 '18 at 17:29
5
\$\begingroup\$

Jelly, 22 bytes

;€0ZṙØ+SṖ
,ZÇ€Z+$/ŒMœị

Try it online!

Not having convolution built-ins like MATL and Dyalog Forgetting your language has convolution built-ins (thank you @dylnan) hurts, but we can do sort of okay without them, partially thanks to ŒM and œị. First, a helper function to compute neighbors in just one direction, which incidentally transposes the input:

;€0Z         Append a zero to each row, then transpose.
    ṙØ+S     Rotate by +1 and −1 (Ø+ = [1,-1]) and sum these.
        Ṗ    Pop the last row.

Visually, the computation is:

1 2 3   ;€0   1 2 3 0   Z   1 4 7   ṙØ+     2 5 8   0 0 0     S   2  5  8   Ṗ   2  5  8
4 5 6  ————→  4 5 6 0  ——→  2 5 8  ————→  [ 3 6 9 , 1 4 7 ]  ——→  4 10 16  ——→  4 10 16
7 8 9         7 8 9 0       3 6 9           0 0 0   2 5 8         2  5  8       2  5  8
                            0 0 0           1 4 7   3 6 9         4 10 16

Interpretation: cell (x, y) of this result is the sum of cell (y, x)'s horizontal neighbors. (For example, here we see that f(A)[2,3] = 16 = 7 + 9 = A[3,1] + A[3,3].)

Then, the main function:

,ZÇ€            Pair the input with its transpose and apply helper to both.
    Z+$/        Fold by Z+, i.e., turn [X,Y] into transpose(X)+Y.
                Now we've summed the horizontal and vertical neighbors for each cell.
        ŒM      Find the 2D index of the maximal value.
          œị    2D-index (into the original input).
\$\endgroup\$
  • 1
    \$\begingroup\$ What about æc? \$\endgroup\$ – dylnan Jun 20 '18 at 16:38
  • \$\begingroup\$ oh, I didn't know about it :) I'm too busy to golf more so feel free to write an answer using it. \$\endgroup\$ – Lynn Jun 20 '18 at 17:13
5
\$\begingroup\$

Jelly, 18 bytes

5BæcµḊṖ)
ZÇZ+ÇŒMœị

Try it online!

The helper function finds the neighbors of each element in each row. The main function does this to the rows and the columns then finds the element that has the maximum neighborhood sum.

5BæcµḊṖ)
5B           bin(5): 1,0,1
  æc         Convolve with [[1,2,9],[other rows]] (for example): [[1,2,10,2,9],...]
    µ        New chain.
       )     Apply this to each element:
     Ḋ       Remove the first element.
      Ṗ      Remove the last element.
             Gives [[2,10,2],...]

ZÇZ+ÇŒMœị   
Z            Zip the matrix
 Ç           Apply helper function
  Z          Zip again. Yields the sum of the vertical neighbors of each element.
   +         Add:
    Ç        The sum of each element's horizontal neighbors.
     ŒM      Find the multidimensional index of the maximal element.
       œị    Index back into the original matrix.
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 58 bytes

Im@Last[Union@@ListConvolve[{a={0,1,0},{1,I,1},a},#,2,0]]&

Convolve the matrix with \$ \left( \begin{smallmatrix} 0 & 1 & 0 \\ 1 & i & 1 \\ 0 & 1 & 0 \end{smallmatrix} \right) \$, take the element with the largest real part, and take its imaginary part.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 127 bytes

def f(a):n=len(a[0]);b=sum(a,[])+[0]*n;print b[max(range(len(b)-n),key=lambda i:b[i-1]*(i%n>0)+b[i+1]*(i%n<n-1)+b[i-n]+b[i+n])]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Stencil, 1 + 10 = 11 bytes (non-competing)

Command-line option: 1 compute 1 generation

y⊃⍨⊃⍒,
+/N

Try it online!

y from the flattened original input
⊃⍨ pick
 the first
 in descending order
, of the flattened

+/ sums of
N the von neumanN neighbourhoods without selves

\$\endgroup\$
  • \$\begingroup\$ Of course there's a language with a one character built-in for the neighbors. \$\endgroup\$ – Umbrella Jun 20 '18 at 17:39
  • 1
    \$\begingroup\$ To be fair, its sole purpose is to solve these kinds of problems. \$\endgroup\$ – Adám Jun 20 '18 at 17:54
  • \$\begingroup\$ Why is it non-competing? \$\endgroup\$ – Kevin Cruijssen Jun 21 '18 at 6:58
  • 1
    \$\begingroup\$ @KevinCruijssen I added y to the language when I saw that it needed easier access to the original input. Before that, you had to write (,⍎'input') instead of y. \$\endgroup\$ – Adám Jun 21 '18 at 7:33
  • 1
    \$\begingroup\$ @Adám Ah ok, yeah, then it indeed is non-competing. Hadn't noticed the challenge was posted yesterday. If it was an old challenge, non-competing because the language (or language version) is newer doesn't make it non-competing anymore in the current meta. \$\endgroup\$ – Kevin Cruijssen Jun 21 '18 at 7:39
2
\$\begingroup\$

JavaScript (ES6), 94 bytes

a=>a.map(p=m=(r,y)=>p=r.map((v,x)=>(s=~r[x-1]+~p[x]+~(a[y+1]||0)[x]+~r[x+1])>m?v:(m=s,o=v)))|o

Try it online!

How?

Instead of looking for the maximum of the sum of the 4 neighbors, we look for the minimum m of the sum s of their one-complements. This allows us to process undefined values just like zeros, because:

~undefined === -1
~0 === -1

The inner map() is written in such a way that it does not alter the content of the row r. Therefore, we can save its result in p in order to test top neighbors in the next iteration.

We use:

  • ~r[x-1] for the left cell
  • ~r[x+1] for the right cell
  • ~p[x] for the top cell
  • ~(a[y+1]||0)[x] for the bottom cell
\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 43 40 bytes

{(,/x)@*>,/(+g@+x)+(g:{(+':x)-|-':|x})x}

Try it online!

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

Java 8, 187 bytes

m->{int r=0,l=m.length,i=l,L,j,S=0,s;for(;i-->0;)for(L=j=m[i].length;j-->0;)if((s=(i<1?0:m[i-1][j])+(i<l-1?m[i+1][j]:0)+(j<1?0:m[i][j-1])+(j<L-1?m[i][j+1]:0))>S){S=s;r=m[i][j];}return r;}

Try it online.

Explanation:

m->{                           // Method with integer-matrix parameter and integer return
  int r=0,                     //  Result-integer, starting at 0
      l=m.length,              //  Amount of rows
      i=l,                     //  Rows index integer
      L,                       //  Amount of columns
      j,                       //  Column index integer
      S=0,                     //  Largest sum of four cells
      s;                       //  Current sum of four cells
  for(;i-->0;)                 //  Loop over the rows
    for(L=j=m[i].length;j-->0;)//   Inner loop over the columns
      if((s=                   //    Set the current sum to: the sum of:
           (i<1?0:m[i-1][j])   //     Value of the cell to the left, or 0 if out of bounds
          +(i<l-1?m[i+1][j]:0) //     Value of the cell to the right, or 0 if out of bounds
          +(j<1?0:m[i][j-1])   //     Value of the cell down, or 0 if out of bounds
          +(j<L-1?m[i][j+1]:0))//     Value of the cell up, or 0 if out of bounds
         >S){                  //    If this current sum is larger than the largest sum:
        S=s;                   //     Replace the largest sum with this current sum
        r=m[i][j];}            //     And set the result to the current cell
  return r;}                   //  Return the result
\$\endgroup\$
1
\$\begingroup\$

Javascript ES6, 170 bytes

c=g=>{s=0;n=0;f=m=>m||[];for(i=0;i<g.length;i++)for(j=0;j<g[i].length;j++){s=~~f(g[i-1])[j]+~~f(g[i+1])[j]+~~f(g[i])[j-1]+~~f(g[i])[j+1];b=s>n?g[i][j]+!(n=s):b;}return b}
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! Your code seems to assume that the input is stored in a variable named g, which is not allowed. You should write either a full program that reads the input or a function (which is usually and by far the preferred way in JS). \$\endgroup\$ – Arnauld Jun 21 '18 at 6:59
  • 1
    \$\begingroup\$ @Arnauld Thank you ! I fixed the code \$\endgroup\$ – Jean-Philippe Leclerc Jun 21 '18 at 14:18
  • \$\begingroup\$ You may consider adding a TIO link to make it easier to test. (I removed the 2nd test case to have the link fit in a comment.) \$\endgroup\$ – Arnauld Jun 21 '18 at 14:24

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.