17
\$\begingroup\$

Introduction

Let's observe the following square, consisting only of the digits 0 - 9:

1034
4167
8414
3542

The outer shell of this square is:

1034
4  7
8  4
3542

It contains zeros, so we need to peel off the outer shell, leaving:

16
41

The outer shell of this square is:

16
41

It does not contain any zeros and is therefore a non-contaminated square. So basically, the definition of a non-contaminated square is when the outer shell of the square contains no zeros.

The Task

Given a square of digits (containing only non-negative integers) in any reasonable format, output the largest non-contaminated square by constantly peeling off the outer shell, in any reasonable format.

Test cases

Test case 1:

Input         Output

1234          1234
2345          2345
3456          3456
4567          4567

Test case 2:

Input         Output

123           123
204           204
346           346

Test case 3:

Input         Output

101           1
010           
101           

Test case 4:

Input         Output

000           (none)
000
000

This is , so the submission with the least amount of bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Can't I make the example 416\n841\n354\n (bottom-left corner)? \$\endgroup\$ – Leaky Nun May 15 '16 at 15:57
  • \$\begingroup\$ Well, you said "largest non-contaminated square" \$\endgroup\$ – Leaky Nun May 15 '16 at 16:06
  • \$\begingroup\$ Is error allowed? \$\endgroup\$ – Leaky Nun May 15 '16 at 16:40
  • \$\begingroup\$ @KennyLau You mean at the last test case? Yes, as long as it doesn't output 0 or something like that. \$\endgroup\$ – Adnan May 15 '16 at 17:10
  • 2
    \$\begingroup\$ "Square of numbers" would be better stated as "square of digits" \$\endgroup\$ – Mego May 15 '16 at 23:47

10 Answers 10

6
\$\begingroup\$

Jelly, 19 16 bytes

Fœ^F}P
ḊṖZµ⁺⁸ßç?

Try it online! or verify all test cases.

How it works

ḊṖZµ⁺⁸ßç?  Main link. Argument: M (2D list)

Ḋ          Dequeue; remove the first row.
 Ṗ         Pop; remove the last row.
  Z        Zip; transpose rows with columns.
   µ       Combine the chain to the left into a link.
    ⁺      Copy the link, executing it twice.
           The copy removes the first and last column and restores the orientation.
       ç?  If the helper link returns a non-zero integer:
     ⁸       Return M unmodified.
      ß      Else, recursively call the main link on the "peeled" M.


Fœ^F}P     Helper link. Arguments: P ("peeled" M), M (unmodified)

F          Flatten P.
   F}      Flatten M.
 œ^        Perform multiset symmetric difference, removing the elements of P from
           the elements of M, respecting multiplicities, leaving precisely the
           elements of the outer shell.
     P     Return the product of the remaining elements.
\$\endgroup\$
8
\$\begingroup\$

JavaScript, 105 97 bytes

Saved 8 bytes thanks to @Patrick Roberts!

l=a=>a.slice(1,-1)
p=a=>l(a).map(l)
c=a=>a.join``.replace(/[^0]/g,"")
s=a=>c(p(a))<c(a)?s(p(a)):a

Defines function s, which returns a 2D array of integers when provided a 2D array of integers as input.

How it Works

  • function l: given an array a, returns a copy without its first and last indexes.

  • function p: given a 2D array a, calls l to remove the first and last row, then for each remaining row calls l to remove the fist and last column. This performs the onion peeling.

  • function c: given a 2D array a, returns a string that only contains the 0s in the stringified form of a.

  • function s: given a 2D array a, calls c on the peeled form of the array given by p, and on the array itself. Compares these strings lexicographically to determine if the peeled form has less 0s than the original. If it does, then the original is contaminated, so call s recursively on the peeled form. Otherwise return the original.

\$\endgroup\$
7
\$\begingroup\$

Retina, 60 57 bytes

Byte count assumes ISO 8859-1 encoding. The trailing linefeed is significant.

+`(?<=(?=.*0|[^_]+(¶0|0¶|0.*$))^[^_]*)(^.+¶|¶.+$|.?\b.?)

Try it online!

Explanation

Due to the trailing linefeed, this finds all matches of the regex after the ` and removes them from the input. Due to the leading + this is done repeatedly until the output stops changing (which will be because the regex will stop matching).

As for the regex itself, it consists of two parts:

(?<=(?=.*0|[^_]+(¶0|0¶|0.*$))^[^_]*)

This part checks whether there's a 0 anywhere in the outer shell. It does this by moving the regex engine's "cursor" to the beginning of the string with a lookbehind (we use [^_] to match both digits and linefeeds):

(?<=...^[^_]*)

And then from that position we use a lookahead to find a 0 either in the first line, adjacent to a linefeed, or in the last line:

(?=.*0|[^_]+(¶0|0¶|0.*$))

Then the actual match will consist either of the first line (including its trailing linefeed), the last line (including its leading linefeed) or the first or last character of a line, where we abuse the word boundary \b as a beginning/end of line anchor:

(^.+¶|¶.+$|.?\b.?)
\$\endgroup\$
6
\$\begingroup\$

MATL, 26 21 bytes

t"t5LY)y5LZ)h?}6Lt3$)

Input is in the following format

[1 0 3 4; 4 1 6 7; 8 4 1 4; 3 5 4 2]

So the other four test cases are

[1 2 3 4; 2 3 4 5; 3 4 5 6; 4 5 6 7]
[1 0 1; 0 1 0; 1 0 1]
[1 2 3; 2 0 4; 3 4 6]
[0 0 0; 0 0 0; 0 0 0]

The program errors in the last test case, but produces the correct output (which is nothing). Thanks to @Dennis for noticing!

Try it online!. Or verify all test cases (this includes wrapping code).

Explanation

This iterates as many times as the number of columns in the input matrix, which is more than enough. At each iteration, the shell is removed or kept depending on its values.

t            % Take a matrix as input. Duplicate
"            % For each column (i.e. repeat that many times)
  t5LY)      %   Duplicate top of the stack. Extract first and last rows
  y5LZ)      %   Duplicate the element below the top. Extract first and last columns
  h          %   Concatenate the two arrays into a row vector
  ?          %   If all its entries are non-zero: do nothing
  }          %   Else
    6Lt3$)   %     Get the central part
             % End if, end for. Implicitly display
\$\endgroup\$
5
\$\begingroup\$

Pyth, 19 bytes

.W}\0.-`H`JutCPG2HJ

Test suite

.W}\0.-`H`JutCPG2HJ
.W                     While the first function returns true, apply the second
                       function, starting with the input.
           u    2H     Apply the following twice to the input:
              PG       Remove the last row
             C         Transpose
            t          Remove the first row
                       This removes the outermost shell.
          J            Save it to J
         `             Stringify the matrix
       `H              Stringify the input
     .-                Multiset difference
  }\0                  Check if there is a '0' in the resulting string.
                  J    If that succeeds, update the current value to J.
                       When it fails, return the current value.
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 74 bytes

f=s=>/^.*0|0\n|\n0|0.*$/.test(s)?f(s.replace(/^.*\n?|.(.*).|\n.*$/g,"$1")):s

Takes input in the form of a string with newlines separating each row (but no leading or trailing newline). Explanation: /^.*0|0\n|\n0|0.*$/ is a regexp that matches contaminated squares, while /^.*\n?|.(.*).|\n.*$/ matches that parts of the square that need to be deleted, except for the (.*) which needs to be kept. (This is shorter than looking ahead or behind for the newline character.)

\$\endgroup\$
4
\$\begingroup\$

Perl 5, 63 + 3 = 66 bytes

$_=<>;s/\A.*\n?|^.|.$|\n.*\Z//mg while/\A.*0|0$|^0|0.*\Z/;print

Requires the -0 flag. Input should not contain a trailing newline character.

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

Pyke, 29 bytes

"D3lt%sBR,"2*ER3*I
/)tOmtmOr;

Try it here!

Also 29 bytes

QeQhQmhQme]4sBI
/)QtOmtmO=Qr;

Try it here!

\$\endgroup\$
  • 2
    \$\begingroup\$ I get errors in both links. Do we need to do anything before pressing "run"! \$\endgroup\$ – Luis Mendo May 15 '16 at 20:31
  • \$\begingroup\$ I should probably have mentioned that there will always be an error when ran. The output is on the second line somewhere (It is actually printed and not part of the error message) \$\endgroup\$ – Blue May 15 '16 at 22:15
2
\$\begingroup\$

Pyth, 31 30 bytes

L+hbeb.W!*F+1iRTs+yHyMHPtmPtdZ

Test suite. (The last testcase errors)

Improvement: made part the outer-loop extractor a function (L+hbeb).

Previous 31-byte version:

.W!*F+1iRTs++hHm+hdedHeHPtmPtdZ

How it works:

The code is basically: while the product of the outershell is zero, peel it.

Let us analyze the main code (Q is implicit here):

.W<lambda:H><lambda:Z>Q

Start from Q (input), while first lambda, perform second lambda.

The first part would be the lambda in H:

!*F+1iRTs++hHm+hdedHeH

The second part would be the lambda in Z:

PtmPtdZ

The first part

!*F+1iRTs++hHm+hdedHeH

Let us analyze this:

s++hHm+hdedHeH

s++             Concatenate:
   hH              1. the first row
     m+hdedH       2. the first and last item of each row
            eH     3. the last row

Since Pyth uses prefix notation, this would then get evaluated:

!*F+1iRT

     iRT  Convert each to integer
 *F+1     Product
!         Negate. If any element of the outer shell is zero, this would return 1.

The second part

PtmPtdZ
  mPtdZ   the inner of each row
Pt        the inner rows
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 78 bytes

NestWhile[#[[a=2;;-2,a]]&,#,Count[{#[[b={1,-1}]],#[[;;,b]]},0,3]>0&]~Check~{}&

Anonymous function, takes input as a matrix. Ignore any errors that may result during execution.

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