Find the box by its corners

Question

Given a matrix of integers \$M\$ and a list of four integers \$L\$, find the sub-matrix \$N\$ whose corners are given by \$L\$ and return the sum of its elements.

Suppose you're given the list \$L = [-8, -3, 2, 9]\$ and the following matrix \$M\$. The numbers in the list are highlighted in blue to illustrate:

$$ \begin{bmatrix}0 & 2 & -7 & -5 & -6\\ 6 & \boldsymbol{\color{blue}{-3}} & 4 & -2 & \boldsymbol{\color{blue}{9}}\\ -9 & 1 & 8 & -1 & -8\\ 3 & \boldsymbol{\color{blue}{2}} & -4 & 2 & \boldsymbol{\color{blue}{-8}} \end{bmatrix} $$

Your task is to sum the elements in the sub-matrix \$N\$ described by those four corners, in other words the sum of all of the blue numbers below:

$$ \begin{bmatrix}0 & 2 & -7 & -5 & -6\\ 6 & \boldsymbol{\color{blue}{-3}} & \color{blue}{4} & \color{blue}{-2} & \boldsymbol{\color{blue}{9}}\\ -9 & \color{blue}{1} & \color{blue}{8} & \color{blue}{-1} & \color{blue}{-8}\\ 3 & \boldsymbol{\color{blue}{2}} & \color{blue}{-4} & \color{blue}{2} & \boldsymbol{\color{blue}{-8}} \end{bmatrix} $$

In this case the sum (by sheer coincidence) is \$0\$.

Input

Input will consist of a matrix \$M\$ and a list \$L\$ in any convenient format. The matrix may contain duplicate numbers and may even have duplicates of the numbers in \$L\$ but there will be only one sub-matrix whose corners are the numbers in \$L\$.

The numbers in \$L\$ may be in any order and will not necessarily correspond to the order of the corners of \$N\$. The numbers in \$L\$ might not be unique.

\$M\$ will always have at least two rows and two columns. \$N\$ will also always be at least \$2 \times 2\$.

Output

The output should be a single integer—the sum of the elements of \$N\$—in any convenient format.

Rules

• Default I/O rules and standard rules apply. Standard loopholes are forbidden.

• This is code-golf; shortest solution in bytes wins.

Test cases

Input:

M =  6  9 -7  3
     8 -1 -6 -4
     2 -7  7 -7
    -1  4  7  9

L = -1  8 -7  2

Output: 2

Input:

M =  2  5 -7  4 -6
    -4 -2  2  0 -6
     1 -4  5  7  6
     3  2 -7 -6 -4

L =  6 -6  2  5

Output: 14

Input:

M =  9  6  4  7
     5  0 -3 -2
     8 -4 -7  9

L =  7  8  9  9

Output: 32

M =  1  2  3
     2  3  2
     3  2  1

L =  1  3  3  1

Output: 19

Answer 1

R 4.1, 188 bytes 120 bytes 97 bytes

I have wanted to answer a code golf question for a while and this seemed perfect for trying in R. These approaches are both functions which expect a matrix and a vector as arguments.

v2.1, 97 bytes entirely thanks to Giuseppe

Attempt this online.

\(m,l,`+`=sort,`-`=sample){while(!all(+l==+m[i<-nrow(m)-2,j<-ncol(m)-2]))1
sum(m[i:i[2],j:j[2]])}

How?

I can't take any credit for this awesome set of improvements posted in the comments but I will try to explain them - hopefully I will do them justice. The most significant changes seem to be:

1. Replacement of s=sort,e=sample with `+`=sort,`-`=sample. It would never have occurred to me to try this and I am amazed and slightly horrified that R allows it, but obviously these operators don't require brackets meaning we can do nrow(m)-2 rather than s(nrow(m),2) (and the same for ncol). The backticks in the definition cost 4 bytes but it saves us 3 bytes each time. Total: -2 bytes.

2. Doing the assignment when we subset m, allowing us to replace the verbose {i=e(nrow(m),2);j=e(ncol(m),2);!all(s(l)==s(m[i,j]))} with !all(+l==+m[i<-nrow(m)-2,j<-ncol(m)-2]) (which makes my head hurt because - now means sample(). This is this trick - assigning a variable to the environment while using it in a function (in this case the function being `[`). -15 bytes.

3. Replacing m[i[1]:i[2],j[1]:j[2]] (ugh so many square brackets) with m[i:i[2],j:j[2]]. This generates a warning that it will only use the first element (which is what we want), and the output is the same. -6 bytes.

Great improvements which I will try to get my brain to store in the code golf part and not allow to leak into the writing R code for work part... Thanks Gisuseppe :).

v2.0, 120 bytes

Attempt this online.

f=\(m,l,s=sort,e=sample){while({i=e(nrow(m),2);j=e(ncol(m),2);!all(s(l)==s(m[i,j]))})m[i,j]
sum(m[i[1]:i[2],j[1]:j[2]])}

How?

Inspired by Jonah's excellent approach in J, I realised it was unnecessary to start with the apparently reasonable step of subsetting the matrix to those indices which match the input list. This method just randomly picks four corners, checks if when sorted they match the sorted input vector, and if so takes the sum of the "box" bounded by the corners. Once again, highly inefficient and will scale horrendously. But it is shorter than my original approach.

Both answers use the do-while loop trick set out by Giuseppe to evaluate i and j in the loop condition, so we can refer to them in the while condition without having to define them both before the loop and in the loop body.

v1.0, 188 bytes

Attempt this online

f=\(m,l){z=arrayInd(which(m%in%l),dim(m))
a=apply
while({i=sample(nrow(z),4);any(colSums((z[i,]*c(1,-1))))|is.list(a(z[i,],2,unique))})0
r=a(z[i,],2,range)
sum(m[r[1,1]:r[2,1],r[1,2]:r[2,2]])
}

How?

This is a highly computationally inefficient approach that does one reasonable thing and then is based on random guessing. Initially, it creates a 2-column matrix of the indices of the values in the input matrix which match the input list.

Then it randomly selects four rows from that matrix (each of which is an x,y coordinate) until the following conditions are satisfied:

1. The second two coordinates subtracted from the first two coordinates give (0,0).
2. There are exactly 2 unique x and y values.

This means (as we started with indices which match the input) that we have the bounds of the "box" - at which point we can select the desired values and sum them.

This is my first response to a code golf question ever. I am sure the answer can be improved and am keen for suggestions. Also if I have made a mistake - whether a fatal error of logic or how the input is allowed -- please let me know.

Answer 2

MATL, 53 52 bytes

xZyXH:2XN!"@XJxHP:2XN!"&GJ@3$)leSwS=?2GJ@,wX{:]3$)ss

Try it online! Or verfy all test cases.

Answer 3

Brachylog, 20 bytes

⟨{szs}{⟨hzt⟩ⁱ²cp}⟩c+

Try it online!

Takes a list [M, L] through the input variable and yields the box sum through the output variable.

    s                   Take a substring of
   z                    a transposed
  s                     substring
⟨{   }{         }⟩      of the matrix, for which
         z              zipping
       ⟨h t⟩            the first element with the last element
            ⁱ²          twice results in a list
              c         which concatenated
               p        is a permutation of L.
                  c+    Concatenate the rows, and sum.

Answer 4

JavaScript (ES6), 152 bytes

Expects (L)(M).

L=>M=>(g=(x,y,X,Y)=>M.map((r,j)=>r.map((v,i)=>1/Y?j<y|j>Y|i<x|i>X?0:t+=v:X?[X[x],v,X[i],r[x]].sort()+''==L.sort()&i>x&j>y&&g(x,y,i,j):g(i,j,r))))(t=0)|t

Try it online!

How?

In order to limit the number of map() loops, we use just two of them within a recursive function which processes up to 3 passes:

1. We unconditionally consider each cell as a possible top-left corner.
2. We test whether we've found the 4 requested corners.
3. We compute the sum of the sub-matrix.

Commented

L => M =>                 // L[] = corner list, M[] = matrix
( g = (x, y, X, Y) =>     // g is a recursive function
  M.map((r, j) =>         // for each row r[] at position j in M[]:
    r.map((v, i) =>       //   for each value v at position i in r[]:
      1 / Y ?             //     if Y is defined, this is the 3rd pass:
        j < y | j > Y |   //       if j is invalid
        i < x | i > X ?   //       or i is invalid:
          0               //         do nothing
        :                 //       else:
          t += v          //         add v to t
      :                   //     else:
        X ?               //       if X is defined, this is the 2nd pass:
          [ X[x],         //         build a vector
            v,            //         consisting of the 4 corners
            X[i],         //         (note that we have X = M[y])
            r[x]          //
          ].sort()        //         sort this vector
          + ''            //         and coerce it to a string
          == L.sort()     //         if it's equal to L[] (also sorted)
          & i > x & j > y //         and the sub-matrix is at least 2x2,
          &&              //         then:
            g(x, y, i, j) //           process the 3rd pass
        :                 //       else:
          g(i, j, r)      //         it's the 1st pass: process the 2nd one
    )                     //   end of inner map()
  )                       // end of outer map()
)(t = 0)                  // initial call to g(); start with t = 0
| t                       // return t

Answer 5

Python3, 222 Bytes:

from itertools import*
S=sorted
R=range
def f(B,e):
 for x,X,y,Y in product(*[R(len(B))]*2,*[R(len(B[0]))]*2):
  if S([B[x][y],B[x][Y],B[X][y],B[X][Y]])==S(e)and x<X and y<Y:return sum(map(sum,[i[y:Y+1]for i in B[x:X+1]]))

Try it online!

Answer 6

J, ^{75 72 71 70 68} 66 bytes

+/@,@;@((-:&(/:~)"1(;/-#:i.4)&{&>)#])&,[:g@|:&>g=.[:;@,<@(1}.<\)\.

Try it online!

This takes all submatrices, filters them based on whether their 4 corners sorted matches the target sorted, and returns the sum.

The two parts that required the most experimentation to golf were:

• (;/-#:i.4)&{ The phrase to pull the 4 corners from a matrix. It generates the numbers 0 through 3 in binary, negates the ones, and uses those as a 2d index for "take" {:
  • 0 0 top left corner
  • 0 _1 top right corner
  • _1 0 bottom left corner
  • _1 _1 bottom right corner
• [:g@|:&>g=.[:;@,<@(1}.<\)\. The phrase to generate all submatrixes. It has two parts:
  • <@(1}.<\)\. First we generate all possible heights for valid full width rectangles. We do this by calculating all prefixes of all suffixes, deleting the first element of each prefix list, because it has dimension 1. [:;@, is a technicality required to keep the list flat. Note that we also save this phrase as g...
  • [:g@|:&> We now reapply g to the transpose of every result from the first step, generating all the possible widths for each possible height. Together, these step generate all possible widths for every possible height rectangle, accounting for all possible submatrices.

Answer 7

Python 3, 134 bytes

f=lambda m,l,n=4,s=sorted:m*n>[]and[f(m[1:],l)|f([*zip(*m[::-1])],l,n-1),sum(sum(m,()))][s(m[x][y]for x in(0,-1)for y in(0,-1))==s(l)]

Try it online!

Recursively removes edges from the matrix until a solution is found.

Answer 8

Charcoal, 60 bytes

ＦＬθＦιＦＬ⌊θＦλ«≔⟦⟧ζＦ⟦ικ⟧Ｆ⟦λμ⟧⊞槧θνξ¿⬤⁺ζη⁼№ζν№ηνＩΣＥ✂θκ⊕ι¹Σ✂νμ⊕λ

Try it online! Link is to verbose version of code. Explanation:

ＦＬθＦι

Loop over all possible row ranges.

ＦＬ⌊θＦλ«

Loop over all possible column ranges.

≔⟦⟧ζＦ⟦ικ⟧Ｆ⟦λμ⟧⊞槧θνξ

Get the corners of the submatrix.

¿⬤⁺ζη⁼№ζν№ην

If this multiset equals the input list, then...

ＩΣＥ✂θκ⊕ι¹Σ✂νμ⊕λ

Output the sum of the submatrix.

57 bytes using the newer version of Charcoal on ATO:

ＦＬθＦιＦＬ⌊θＦλ«≔ΣＥ⟦ικ⟧Ｅ⟦λμ⟧§§θνπζ¿⬤⁺ζη⁼№ζν№ηνＩΣＥ✂θκ⊕ι¹Σ✂νμ⊕λ

Attempt This Online! Link is to verbose version of code. Saves 3 bytes by being able to flatten the nested array obtained when extracting the corners of N.

Answer 9

Jelly, 20 bytes

ẆZẆ$€ẎØ.p¤œịœ|ƑɗƇṪFS

Try it online!

Dyadic link taking \$M\$ on the left and \$L\$ on the right.

Ẇ                       Get all contiguous sublists of the matrix,
  Ẇ                     get all contiguous sublists of
 Z                      the transpose of
   $€                   each sublist,
     Ẏ                  and concatenate into a single list of submatrices.
               ɗƇ       Filter by:
          œị            Multidimensional-index into the submatrix with
        p               the Cartesian product of
      Ø.                [0, 1]
         ¤              with itself;
              Ƒ         is it unchanged by
            œ|          multiset union with L?
                 Ṫ      Keep only the largest passing submatrix,
                  FS    and flatten and sum it.

Answer 10

05AB1E, 38 bytes

U˜āãε`"€üÿø€üÿ".V}€`€`ʒÁ2£øÁ2£˜{X{Q}˜O

Inputs in the order \$L,M\$.

Try it online or verify all test cases.

Explanation:

U             # Pop the first (implicit) input-list and store it in variable `X`
˜             # Flatten the second (implicit) input-matrix
 ā            # Push a list in the range [1,length] (without popping the list)
  ã           # Create all possible pairs of this list with the cartesian product
ε             # Map over each pair:
 `            #  Pop and push them both separated to the stack
  "€üÿø€üÿ"   #  Push this string, where both `ÿ` are filled with the two values
           .V #  Evaluate and execute it as 05AB1E code:
   €          #   Map over each row of the (implicit) input-matrix
    üA        #    Convert it into overlapping lists of size A
      ø       #   Zip/transpose; swapping rows/columns
       €      #   Map over each the list of lists
        üB    #    Convert it into overlapping lists of size B
}             # Close the map
 €`€`         # Flatten two levels down so we have a list of blocks of various sizes
ʒ             # Filter this list of AxB blocks by:
 Á2£øÁ2£      #  Convert the current AxB block to a 2x2 block of its corners:
 Á            #   Rotate the rows once towards the right
  2£          #   Then only keep the first two rows
    ø         #   Zip/transpose; swapping rows/columns
     Á        #   Rotate the list of pairs towards the right again
      2£      #   Keep the first two pair
 ˜            #  Flatten this block of corners
  {           #  Sort it from lowest to highest
   X          #  Push the first input from variable `X`
    {         #  Sort it as well
     Q        #  Check if these two lists are the same
}˜            # After the filter: flatten the only remaining block to a single list
  O           # Sum its values together
              # (after which this sum is output implicitly as result)

Some minor notes:

1. ā leaves the flattened list on the stack, which will affect the first iteration of the map. But since this is the 1x1 block anyway, it doesn't affect the final result.
2. The üN builtin will result in an empty list if N exceeds the list's length, so it doesn't matter that ˜ā will also try to make blocks of 20x20 for a 4x5 input matrix.
3. Because we use Á2£øÁ2£ to get our 2x2 block of corners from an AxB block, it doesn't matter that there are 1x1 or 3x1 blocks among (which could for example have caused issues for the final test case).