Find the largest N digit number in a W by H grid of digits

Question

Write a program or function that takes in a positive integer \$N\$ and a grid of decimal digits (\$0\$ to \$9\$) with width \$W\$ and height \$H\$ (which are also positive integers). You can assume that \$N\$ will be less than or equal to the larger of \$W\$ and \$H\$ (\$N \le \max(W,H)\$).

Print or return the largest contiguous \$N\$-digit number that appears horizontally or vertically in the grid, written in normal reading order or in reverse.

• Diagonal lines of digits are not considered.
• The grid does not wrap around, i.e. it does not have periodic boundary conditions.

For example, the \$3\times3\$ grid

928
313
049

would have 9 as the output for \$N = 1\$, 94 as the output for \$N = 2\$, and 940 as the output for \$N = 3\$.

The \$4\times3\$ grid

7423
1531
6810

would have 8 as the output for \$N = 1\$, 86 for \$N = 2\$, 854 for \$N = 3\$, and 7423 for \$N = 4\$.

The \$3\times3\$ grid

000
010
000

would have output 1 for \$N = 1\$, and 10 for N = 2 and N = 3 (010 is also valid for N = 3).

The \$1\times1\$ grid

0

would have output 0 for \$N = 1\$.

You can take the input in any convenient reasonable format. e.g. the grid could be a newline separated string of digits, or a multidimensional array, or a list of lists of digits, etc. Leading zeros are allowed in the output if they were part of the grid.

This is code-golf, so the shortest code in bytes wins, but I'll also award brownie points (i.e. more likely upvotes) for answers that can show that their algorithm is computationally efficient.

Answer 1

CJam, 39 36 35 34 bytes

qN/)i\[{zW%_}4*]ff{_,@e<ew:i}e_:e>

Just quickly, before @Dennis wakes up :P

Try it online.

Explanation

The basic algorithm is to take all four rotations of the grid and split each row into chunks of length N (or the row length, whichever's smaller). Then convert the chunks to ints and take the largest.

qN/             Split input by newlines, giving an array of lines
)i\             Drop N from the array and put at bottom
[        ]      Wrap in array...
 {    }4*         Perform 4 times...
  zW%_              Rotate grid anticlockwise and push a copy
                Note that this gives an array of 5 grids [CCW1 CCW2 CCW3 CCW4 CCW4]
ff{         }   For each grid row, mapping with N as an extra parameter...
   _,             Push length of row
     @e<          Take min with N
        ew        Split into chunks
          :i      Convert to ints
e_              Flatten that array
:e>             Take cumulative max

Answer 2

Pyth, 22 19 bytes

3 bytes thanks to Jakube.

seSs.:RQ.n,L_MdCB.z

Try it online.

If we are allowed to print leading zeroes, the code is 18 bytes:

eSs.:RQ.n,L_MdCB.z

Answer 3

Jelly, 12 bytes

ZU$4СẎṡ€ḌFṀ

Try it online!

This takes the grid as an \$W\times H\$ matrix of single digits.

The TIO Footer simply takes each input list and generates the outputs for each \$N = 1, 2, ...\$ up to either \$W\$ or \$H\$, depending on which is larger

How it works

ZU$4СẎṡ€ḌFṀ - Main link. Takes the matrix M on the left and N on the right
  $          - Group the previous 2 links together as a monad f(M):
Z            -   Transpose
 U           -   Reverse
   4С       - 4 times, run f(M) on M, updating M each time, and return all 4 results
               This yields M, Mᵀ with rows reversed, Mᵀ and M with rows reversed
      Ẏ      - Tighten into a list of lists
        €    - Over each:
       ṡ     -   Yield all overlapping sublists of length N
         Ḍ   - Convert back to integers
          F  - Flatten
           Ṁ - Maximum

Answer 4

05AB1E, 13 bytes

DÅ|«€ÂJ€Œ˜sùà

Try it online! Explanation:

D                 # duplicate matrix
 Å|               # get column vectors
   «              # join matrix with its column vectors
    €Â            # append reversed elements
      J           # join arrays into numbers
       €Œ˜        # Get all substrings
          sù      # Keep only those of required length
            à     # Get the largest value

Answer 5

Husk, 13 bytes

▲ṁX⁰Σ↑4¡om↔T²

Try it online!

The arguments are a bit finicky here.

Answer 6

Japt -h, 13 12 bytes

Takes the matrix as an array of lines. Includes leading 0s in the output, where applicable.

4Æ=z)mãVÃc ñ

Try it

4Æ=z)mãVÃc ñ    :Implicit input of array U & integer V
4Æ              :Map the range [0,4)
  =             :  Reassign to U
   z            :  Rotate 90° clockwise
    )           :  End reassignment
     m          :  Map
      ãV        :    Substrings of length V
        Ã       :End map
         c      :Flatten
           ñ    :Sort
                :Implicit output of last element