23
\$\begingroup\$

Background

An L-shape is defined as a polyomino which can be made by extending two rectangular legs in orthogonal directions from a full square (called a pivot). The size of the square should be at least 1, and the lengths of the two legs should also be at least 1.

These are some examples of L-shapes:

Pivot size 1, two leg lengths 2 and 4
#
#
#####

Pivot size 2, two leg lengths 1 and 3
#####
#####
   ##

These are not:

Does not have two orthogonal nonempty legs
####

The pivot is not a square
##
####

One of the legs is not rectangular
#####
####
##
##

Has three legs instead of two
#####
#####
  ##

Has four legs instead of two
  #
#######
  #
  #

Cannot identify a pivot and two legs
##
 ##

Contains one or more holes
#####
# ###
#####
# #
###

Is not a polyomino (the shape is disconnected)
##  #
#  ##

Challenge

Given a zero-one matrix, determine if the ones form a single L-shape.

You should handle inputs containing any amount of margins on all four sides (including no-margin cases), and detect L-shapes in any of the four orientations. For example, the output must be True if the input is any of these:

0 0 1 1 1 1 0
0 0 1 1 1 1 0
0 0 1 1 0 0 0

1 1 1
0 0 1
0 0 0

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0

0 0 0 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0
0 0 0 0 0 0
0 0 0 0 0 0

and False if given any of these:

1

0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

1 0 1
0 0 0
1 0 0

0 0 0 1
0 1 1 1
0 0 1 0
0 0 0 0

0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 1 1 1 0 0

1 1 0 0
1 1 1 1

You can choose any reasonable representation of a matrix, and you can assume that the input is always rectangular. You can also choose the two values to represent 0 and 1 respectively.

For output, you can choose to

  1. output truthy/falsy using your language's convention (swapping is allowed), or
  2. use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Shortest code in bytes wins.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Suggest testcase: "001\n111\n000\n001" -> false \$\endgroup\$ – tsh Jan 27 at 2:22
  • \$\begingroup\$ I guess it's not possible to take a list of integers as input (with the shape binary-encoded) because a left margin of 0's could not be passed this way. Is that correct? \$\endgroup\$ – Arnauld Jan 27 at 8:46
  • 3
    \$\begingroup\$ Unless I'm mistaken, a full left/right margin of 0s doesn't affect whether the input is true/false, so inputting as a list of integers should be possible (for example) by stripping margins which are fully zero \$\endgroup\$ – caird coinheringaahing Jan 27 at 10:23
  • 3
    \$\begingroup\$ @cairdcoinheringaahing But that'd take away part of the challenge. E.g. just trimming alone costs me 10 bytes. \$\endgroup\$ – Adám Jan 27 at 10:49
  • 2
    \$\begingroup\$ Please add test cases with extra margins. \$\endgroup\$ – Adám Jan 27 at 13:57

14 Answers 14

8
\$\begingroup\$

05AB1E, 31 30 17 bytes

ø‚O0δÚDWδåsεÔg<}Q

Try it online or verify all test cases.

Explanation:

ø            # Zip/transpose the (implicit) input-matrix, swapping rows/columns
 ‚           # Pair it together with the (implicit) input-matrix
  O          # Take the sum of each row of both matrices
             # Remove any leading/trailing rows/columns of 0s:
    δ        #  Map over both the inner lists of row-sums:
   0 Ú       #   And trim all leading/trailing 0s
      D      # Duplicate it
             # Check if the pivot is a square:
       W     #  Get the flattened minimum (without popping)
        δ    #  Map over both lists of row-sums:
         å   #   And check if this minimum is present in the row-sums
             #  (this will result in [1,1] if the minimum sum is present in both the
             #   row-sums and column-sums, which means the pivot is a square)
             # Check if the matrix forms an L-shape:
      s      #  Swap so the duplicated pair of row-sums is at the top again
       ε     #  Map over both inner lists:
        Ô    #   Connected uniquify the sums
         g   #   Pop and push the length
          <  #   And decrease this by 1
       }     #  Close the map
             #  (this will result in [1,1] if the matrix forms an L-shape, which means
             #   the lengths were 2 for both the row-sums and column-sums after the
             #   connected uniquify)
             # Check that all four values are truthy:
        Q    #  Check if both pairs are equal
             # (after which the result is output implicitly)

NOTE: the Q would also incorrectly result in truthy if both pairs are \$[1,0]\$ for example, but there isn't any test case where both pairs would be the same apart from the truthy \$[1,1]\$ test cases. (If there were, we could have used «P - merge; check if all four are truthy - instead.) The reason why the pairs can never be the same except for the truthy test cases:

  1. We check if the flattened minimum of the sums is present in both inner lists. Since we took the minimum from the lists, this can only ever result in \$[1,1]\$, \$[0,1]\$, or \$[1,0]\$ (this will also result in \$[1,1]\$ if the input-matrix is empty).
  2. The εÔg<} will however not result in \$[1,1]\$ for empty matrices, nor will it ever result in \$[0,1]\$ or \$[1,0]\$. For either the sums of rows or columns to result in \$0\$, it would mean all values in those rows/columns are equal, but this implicitly means the same applies vice-versa and it's a rectangle matrix of the same values. The εÔg<} can only result in:
    • \$[-1,-1]\$: which meant the input was empty, or only contained \$0\$s (try it online);
    • \$[0,0]\$: which meant the input-matrix was a rectangle of \$1\$s, after we've trimmed all leading/trailing \$0\$s (try it online);
    • \$[1,1]\$: our expected truthy result for L-shaped matrices (try it online);
    • or larger than \$[1,1]\$ - i.e. \$[1,3]\$, \$[2,4]\$, etc.: if the input-matrix contained gaps in one or multiple of the rows/columns (try it online).
\$\endgroup\$
7
\$\begingroup\$

J, 51 48 79 bytes

(1-'10+1'rxin'012'{~2,@,.],|:)*1&#.(,~&{:-:,&(0{#/.~)+0{,)&(|.^:({.>{:)@-.&0)+/

Try it online!

+31 thanks to Bubbler for catching a bug not revealed by the original cases

NOTE: All test cases are passing again when I run locally on j902, but this now fails on TIO due to a J regex bug on linux/TIO.

Consider the column and row sums of:

11111 = 5
11111 = 5
00011 = 2 (count of 2s is 1)
-----
22233
(count of 2s is 3)

as well as the count of the smallest number in each: 2 in this case.

The insight is:

2 + (column count of 2s) = 5
2 + (row    count of 2s) = 3

and this fact is basically all you need to solve it. The rest is mechanics and likely the J could be golfed a bit more. I'll try to do that and improve this explanation tomorrow.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Brilliant idea, though it fails with this input [1 0 1] [0 0 0] [1 0 0], which is indistinguishable from an L-tromino after deleting all zeros from sums. \$\endgroup\$ – Bubbler Jan 27 at 7:11
  • \$\begingroup\$ Thanks. I added an explicit check to return 0 if the pattern 10+1 exists in any column or row. I think with that the logic is correct now. Lmk if you see any remaining issues. I'll try to re-golf tonight. \$\endgroup\$ – Jonah Jan 27 at 12:41
6
+50
\$\begingroup\$

JavaScript (V8), 500 bytes

Lots of golfing possible.

M=>{R=M.map(m=>m.join``);if(R.find(r=>r.match(/10+1/)))return;o = [];for(i=n=0;i<R[L="length"];i++)if((r=R[i]).includes`1`){if(n)return;n=0;o.push([r.indexOf`1`,r.lastIndexOf`1`])}else{if(o[L])n=1;else continue}if(o.every(r=>r[0]==o[0][0])){}else if(o.every(r=>r[1]==o[0][1]))o=o.map(r=>[R[0][L]-r[1],R[1][L]-r[0]]);else return;d=[];for(i=0;i<o[L];i++){if(o[i][1]!=(d[0]||0)[0])d.unshift([o[i][1],1]);else d[0][1]++}return d[L]== 2&&(d[0][1]==o[0][1]-o[0][0]+1||d[1][1]==o[o[L]-1][1]-o[o[L]-1][0]+1)}

Try it online!

Outputs truthy/falsy. Inputs as a multidimensional array of 0 and 1.

Explanation:

  1. Join into rows, and do a regex to check for lines that have two vertical parts (10+1, which can't be L shapes)
  2. Create a list of the first and last index of each 1 for every line containing a 1, and return a falsy value immediately if there's a line with no 1s between two that have ones (which can't be L shapes)
  3. If the "stem" of the L is on the right, flip it horizontally
  4. Make a list of each group of lines where the width of the 1s is the same, and note its height
  5. Check if there are two of these sections (i.e., ensure it's not a rectangle or an E/F/jagged thingy)
  6. Check if the width of the stroke is the same horizontally and vertically

Ungolfed:

f = (matrix) => {
    var rows = matrix.map(m => m.join(""));
    
    if (rows.find(r => r.match(/10+1/)))
        return false;
    
    var o = [];
    var n;
    
    for (var r, i = 0; i < rows.length; i++) {
        r = rows[i];
        
        if (r.includes("1")) {
            if (n)
                return false;
            
            n = false;
            
            o.push([r.indexOf("1"), r.lastIndexOf("1")]);
        } else {
            if (o.length)
                n = true;
            else
                continue;
        }
    }
    
    if (o.every(r => r[0] == o[0][0])) {
    } else if (o.every(r => r[1] == o[0][1])) {
        o = o.map(r => [rows[0].length - r[1], rows[1].length - r[0]]);
    } else {
        return false;
    }
    
    var d = [];
    
    for (i = 0; i < o.length; i++) {
        if (o[i][1] != (d[0]||0)[0])
            d.unshift([o[i][1], 1]);
        else
            d[0][1]++;
    }
    
    return d.length == 2 && (d[0][1] == o[0][1] - o[0][0] + 1 || d[1][1] == o[o.length - 1][1] - o[o.length - 1][0] + 1);
}
```
\$\endgroup\$
6
\$\begingroup\$

APL (Dyalog Extended), 48 bytes (SBCS)

Anonymous tacit prefix function. Takes Boolean (0/1) matrix with 0s indicating the shape. Requires 0-based indexing.

{(=/⍵-⍥⍴e)∧i≡,e←(⊂∘⊃+∘⍳∘|1+⊃∘⌽-⊃)i←⍸⍵}1⍉⍤⌂deb⍣2⊢

Try it online!

0⁠ with 0 as left argument and the unmodified argument as right argument:

 …⍣2 repeat twice

  …⍤⌂debdelete ending (leading and trailing) blanks (1s), then:

    transpose (so we end up deleting the top and bottom blank rows too)

{} apply the following lambda, with representing its argument:

⍸⍵indices where there are 1s

i← save as i

() apply the following tacit function to that:

   the [index of the] first [blank]

  …- subtract that from:

   ⊃∘ the [index of the] first of the:

     reversed [indices of blanks, i.e. the index of the last blank]

  1+ increment that [to get inclusive range]

  ∘| take the absolute value of that [getting the absolute range], then:

   ∘⍳ get the indices of that range, then:

    …+ add that to:

     ⊂∘ the whole of…

       [index of the] first [blank, giving a matrix of indices of the entire supposed blank area]

e← save as e

, ravel into a list of indices

i≡ identical to the actual list of indices of blanks?

()∧ and…

  e considering the argument and the matrix of supposed blanks…

   -⍥ are the differences in…

     shapes [between heights and widths]

  =/ equal? [i.e. does the height-difference match the width-difference?]

\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES6),  175  166 bytes

Expects a list of binary strings.

m=>m.map(M=r=>(M|=v='0b'+r|0,m&=v||~0,v),m=~0).map(v=>v?(b=v+(v&-v))&b-1?3:v^m?2^v<M:1:0).join``.match(`^0*(1+${s=(g=m=>m?2+g(m&m-1):'')(m)}|${s}1+)0*$`)&&M*2&M/2&m^m

Try it online!

How?

Step 1

We first convert the input matrix \$m[\:]\$ into a list of integers. At the same time, we compute the bit mask \$M\$ of all rows OR'd together and the bit mask \$m\$ of all non-empty rows AND'd together.

m.map(M =                  // start with M zero'ish
  r =>                     // for each row r in m[]:
  ( M |= v = '0b' + r | 0, //   turn r into an integer v by parsing it as binary
                           //   and update M by doing M = M OR v
    m &= v || ~0,          //   if v is not equal to 0, update m by doing m = m AND v
    v                      //   yield v as the actual value for the map()
  ),                       //
  m = ~0                   //   start with all bits set in m
)                          // end of map()

If the shape is valid:

  • \$m\$ is the pattern for the vertical leg
  • \$M\$ is the pattern for the horizontal leg
  • the list returned by map() contains only \$m\$, \$M\$ and optional \$0\$'s

Example:

 input     | bin -> dec |  M |  m
-----------+------------+----+-----
 "0000000" |      0     |  0 | ~0
 "0100000" |     32     | 32 | 32
 "0100000" |     32     | 32 | 32
 "0111110" |     62     | 62 | 32
 "0000000" |      0     | 62 | 32

Step 2

We convert the list into a string of digits, using \$0\$ for empty rows, \$1\$ for rows equal to \$m\$, \$2\$ for rows equal to \$M\$, or \$3\$ for invalid rows.

.map(v =>                  // for each value v in the list:
  v ?                      //   if v is not equal to 0:
    (b = v + (v & -v))     //     if adding to v the least significant bit set in v
    & b - 1 ?              //     results in more than one bit set:
      3                    //       this is an invalid row where at least one 0
                           //       breaks a pattern of consecutive 1's
    :                      //     else:
      v ^ m ?              //       if v is not equal to m:
        2 ^                //         yield 2 if v = M
        v < M              //         or yield 3 if v != M (invalid)
      :                    //       else (v = m):
        1                  //         yield 1
  :                        //   else (empty row):
    0                      //     yield 0
)                          // end of map()
.join``                    // join all digits

Step 3

We build a regular expression to test whether the string is valid.

.match(                    // test the resulting string:
  "^0*(" +                 //   optional leading 0's
                           //   followed by either:
  "1+" +                   //     one or several 1's
  ( s =                    //     followed by as many 2's as the number of bits set
    ( g = m =>             //     in m
        m ?                //
          2 + g(m & m - 1) //     this string of 2's is computed with the recursive
        :                  //     function g and saved in s
          ''               //
    )(m)                   //
  ) +                      //
  "|" +                    //   or:
  s + "1+" +               //     as many 2's as the number of bits set
                           //     in m, followed by one or several 1's
  ")0*$"                   //   followed by optional trailing 0's
)                          // end of match()

Step 4

Finally, we make sure that \$m\$ and \$M\$ form a right angle.

Either \$m\text{ AND }(M\times 2)\$ or \$m\text{ AND }\lfloor M/2\rfloor\$ must be different from \$m\$:

M * 2 & M / 2 & m ^ m
\$\endgroup\$
4
\$\begingroup\$

Julia, 175 170 bytes

a->try
r=rotr90
for _=1:4
while sum(a[1,:])<1
a=a[2:end,:]end
a=r(a)end
for _=1:4
a=r(a,a[end])end
a[a[1]]
while sum(a)>0
a[a[a[:,1],:]]
a=a[2:end,2:end]end
a[1]catch
end

Try it online!

returns 0 if L-shaped and nothing otherwise

It's probably not the most efficient approch but I'm glad I could match the javascript answer

Ungolfed version

function f(a)
    try
        # remove margins
        for _=1:4
            while sum(a[1,:])<1
                a=a[2:end,:]
            end
            a=rotr90(a)
        end

        # rotate `a[end]` times, meaning until a[end]==0
        for _=1:4
            a=rotr90(a,a[end])
        end
        a[a[1]] # check that a[1]!=0, by erroring if a[1]==0
        
        while sum(a)>0
            a[a[1,:]] # check that first line and col are all ones
            a[a[:,1]]
            a=a[2:end,2:end] # remove first line an col
        end
        a[1] # check that a is not empty (errors if empty)
    catch
        nothing
    end
end

Try it online!

\$\endgroup\$
4
+50
\$\begingroup\$

APL (Dyalog Unicode), 44 bytes

thanks @Adám for the ⍸⍣¯1 trick

(⊂a)∊(⍉¨⊢,⌽¨)⍣2≥∘i¨⍳⌈/,i←⌊/↑⍳⍴a←⍸⍣¯1(⊢-⌊/)⍸⎕

Try it online!

⍸⍣¯1(⊢-⌊/)⍸ trim surrounding 0s

≥∘i¨⍳⌈/,i←⌊/↑⍳⍴a generate L-shapes

(⍉¨⊢,⌽¨)⍣2 add reflections

(⊂a)∊ test if the (trimmed) input is among them

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

APL (Dyalog Unicode), 104 bytes

{i←0⋄{(~×/1=,⍵)∧(⍴⍵)≡+/¨1⌷¨(⍉⍵)⍵}⌽∘⍉⍣{(~⊃⌽⊖⍺)∨i=4⊣i+←1}{×≢⍵:⍵⋄,0}p∧⌿⍵∧/⍨p←⌊/0~⍨+/⍵}{(¯1+⌊⌿c)↓⍵↑⍨⌈⌿c←↑⍸⍵}

Try it online!

A train of two dfns which takes a matrix of 0's and 1's as argument.

Can be simplified a lot using Jonah's idea.

It simplifies the matrix like so:

#####
##### →  ####
   ##       #

rotates it to put the corner at the top left:

##
#
#
#

and then checks if the first row and first column match its shape.

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

Retina, 112 bytes

^\s+¶|¶\s+$

/^( .*¶)+ .*$/+m`^ 

/^(.* ¶)+.* $/+m` $

/^#* /&G^`
/(?m)^ /&V`
/^##+(¶#.*)+/+`^#+¶#|(¶)#
$1
^\s+$

Try it online! Link includes test suite with header that extracts the #-based test cases from the input and automatically right-pads them. Explanation:

^\s+¶|¶\s+$

/^( .*¶)+ .*$/+m`^ 

/^(.* ¶)+.* $/+m` $

Remove any margins. Annoyingly, this costs almost 50% of the code size.

/^#* /&G^`

If the first line contains a space then reverse the rows.

/(?m)^ /&V`

If the first column contains a space then reverse each line.

/^##+(¶#.*)+/+`

Repeat while the there are at least two rows and columns of which the first of each only contains #s...

^#+¶#|(¶)#
$1

... completely delete the first row and column.

^\s+$

Check that the entire L was deleted.

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

Wolfram Language (Mathematica), 107 105 101 100 bytes

FreeQ[#|r/@#,#|r@#&@{z={y=0...}...,d:{a:y,o=1..,b:o,y}..,{a:y,b:o,y}..,z}/;+b==Length@!d]&
r=Reverse

Try it online!

The pattern identifies a vertically reflected L shape. Reversing it checks for another vertical reflection (upright); #|r/@# checks for horizontal reflection.

{                               (* L pattern: *)
 z={y=0...}...,                 (*  zero or more leading zero-lines, followed by *)
 d:{a:y,o=1..,b:o,y}..,         (*  a column of 1s, wider than *)
 {a:y,b:o,y}..,                 (*  another column of 1s, left-aligned with the first column, *)
 z                              (*  and zero or more trailing zero-lines, *)
}/;+b==Length@!d                (* such that the width of the second column is equal to the height of the first. *)
\$\endgroup\$
2
\$\begingroup\$

Python 3.9 + NumPy, 167 bytes

lambda a:min(c:=(a:=a[[slice(min(i),max(i)+1)for i in a.nonzero()]]).sum(0))-min(r:=a.sum(1))|len(c)-max(r)|sum((a[:-1]^a[1:]).any(1))*sum((a[:,:-1]^a[:,1:]).any(0))-1

Expected input is a 2D numpy array of 0/1 (or False/True) values.

Returns falsey for L shape, truthy for not L shape.

Explanation:

First remove the "margin" / 0 column and row vectors around the input if there is any.

Then for both axes:

  • Check that the row/column vector only changes once when going along that axis (this ensures that there are only 2 unique ones (one for the leg parallel, and one for the leg perpendicular), and these are all next to each other)
  • Take the sum along the axis. There should only be 2 unique values. The smaller one is the width of the leg perpendicular to the axis. Check that the two widths are the same

Then check that the width of both legs is the same

And then check that the length of one of the legs is the entire length of the array

Ungolfed + test runner (since TIO doesn't have numpy):

def is_L_shape(a):
    # Remove zero vectors surrounding a
    a = a[tuple(slice(min(i), max(i)+1) for i in a.nonzero())]

    # Check columns have L-like sums
    col_sums = a.sum(0)
    col_width = min(col_sums)
    cols_in_order = sum(~(a[:,:-1]==a[:,1:]).all(0)) == 1  # Only one column should be different from the next

    # Check rows have L-like sums
    row_sums = a.sum(1)
    row_width = min(row_sums)
    rows_in_order = sum(~(a[:-1]==a[1:]).all(1)) == 1  # Only one row should be different from the next

    # Check that the legs span the entire column/row
    col_correct_length = col_sums.max() == len(row_sums)
    # row_correct_length = row_sums.max() == len(col_sums)

    return col_width == row_width and col_correct_length and cols_in_order and rows_in_order

# Test runner
f = \
lambda a:...

def run_test(s):
    import numpy as np
    s = s.strip('\n')
    if s.endswith('!'): s = s[:-1]
    a = np.row_stack([np.array(list(map(ord, line))) for line in s.split('!\n')]) == ord('#')
    is_L = not f(a)
    print(np.array(a, dtype=int), 'is an L' if is_L else 'is not an L', 'as expected' if bool(is_L) == bool(expected) else '(failure)' + '!\n'*20, end='\n\n')

expected = True

run_test('''
#    !
#    !
#####!
''')

run_test('''
#####!
#####!
   ##!
''')

run_test('''
  #### !
  #### !
  ##   !
''')

run_test('''
###!
  #!
   !
''')

run_test('''
      !
      !
  #   !
  ##  !
      !
      !
''')

run_test('''
   ## !
##### !
##### !
      !
      !
''')

expected = False

run_test('''
####!
''')

run_test('''
##  !
####!
''')

run_test('''
#####!
#### !
##   !
##   !
''')

run_test('''
#####!
#####!
  ## !
''')

run_test('''
  #    !
#######!
  #    !
  #    !
''')

run_test('''
## !
 ##!
''')

run_test('''
#####!
# ###!
#####!
# #  !
###  !
''')

run_test('''
##  #!
#  ##!
''')

run_test('''
    !
 ## !
 ## !
    !
''')

run_test('''
# #!
   !
#  !
''')

run_test('''
       !
  #    !
 ####  !
''')

run_test('''
###!
# #!
## !
''')

run_test('''
###!
   !
###!
## !
## !
''')

run_test('''
### !
### !
### !
   #!
   #!
''')

run_test('''
## !
## !
  #!
''')

run_test('''
## !
## !
  #!
  #!
''')

run_test('''
#########!
#########!
''')
run_test('''
#!
''')
run_test('''
###!
''')
\$\endgroup\$
3
  • \$\begingroup\$ Unfortunately it looks like this doesn't quite work. The code says that [[1,1,1],[1,0,1],[1,1,0]] is an L. I think that just row and column sums don't give enough information to tell whether the shape is an L. \$\endgroup\$ – xnor Jan 28 at 1:33
  • \$\begingroup\$ @xnor Fixed by ensuring two unique entire rows instead of two unique sums across rows/columns (for a cost of +19 for now) \$\endgroup\$ – Artyer Jan 28 at 2:00
  • \$\begingroup\$ Does that work for something like 110/110/001? \$\endgroup\$ – xnor Jan 28 at 2:01
2
\$\begingroup\$

Perl 5 (cperl), 338 bytes

sub L{($w,$h,$v,$m)=@_;join$/,map{$x=$_;join'',map$_<=$w|($m?$x>$h-$w:$x<=$w)|0,1..$v}1..$h}
sub r{my($i,@r);map/\n/?($i=0):$r[$i++]=~s/^/$_/,pop()=~/./gs;join$/,@r}
sub d{my$_=pop;/.*/;length$&,0+split$/}
sub f{$s=pop;map$s=r($s)=~s,^(0+\n)+,,r,1..4;@m=map{$m=$_;map$m=r($m),1..4}map{L(@L=($_,d($s))),L(@L,1)}1..min(d($s))-1;grep/$s/,@m}

Try it online!

Creates all possible L's with all possible rotations and mirrors up to the dimensions of the input (with all 0-margins shaved off). Sees if any of those L's is equal to the shaved input.

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

Charcoal, 69 bytes

FLθFL§θ⁰F⌊⟦ικ⟧F⁻ιλF⁻κλF²F²⁼θEθEρ¬∨∨∨‹ςμ›ςι∨‹τν›τκ‹λ⌊⟦⎇π⁻ςμ⁻ις⎇ξ⁻τν⁻κτ

Try it online! Link is to verbose version of code. Works by enumerating all possible L shapes on the original grid looking for a match. So many nested loops, I've actually used the t variable for the first time ever. This is an important milestone, since there are no trivial loop variables left. Outputs a Charcoal boolean, i.e. - if the shape was an L, nothing if not. Explanation:

FLθFL§θ⁰

Loop over all potential bottom right corners of the rectangle enclosing the L shape. (Zero values will be trivially excluded as there won't be room for a pivot.)

F⌊⟦ικ⟧

Loop over all potential pivot sizes. (Obviously there must be room for the pivot in both dimensions as it is square.)

F⁻ιλF⁻κλ

Loop over all potential top left corners of the enclosing rectangle.

F²F²

Loop over all orientations of the L within the rectangle.

⁼θEθEρ¬∨∨∨‹ςμ›ςι∨‹τν›τκ‹λ⌊⟦⎇π⁻ςμ⁻ις⎇ξ⁻τν⁻κτ

Recreate the L based on the specification, eliminating all points (v, t) outside the rectangle (m, n) - (i, k) (inclusive) but also all points which are more than l away from at least one of the appropriate adjacent edges for the given orientation, and see if that equals the original input.

Here is an example of an enumerated L shape. In this figure, i is 5, k is 11, l is 3, m is 2, n is 5, and p is 1 (for top) and x is 0 (for right) for the position of the pivot.

+-----n-----k
|
|
m     ----+++
|     ----+++
|     ----+++
i         |||
\$\endgroup\$
1
\$\begingroup\$

Scala, 249 185 180 bytes

Seq.iterate(_,8)(_.transpose.map(_.reverse)dropWhile(!_.toSet(1)))drop 4 exists{m=>Set(m,m.transpose).flatMap(_.dropWhile(!_.toSet(0)).map(_.reverse.dropWhile(_<1)).toSet).size==1}

Try it online!

This is shamefully long. It takes a List[List[Int]] as input (even though the type is Seq[Seq[Int]] => Boolean). The result is a Boolean.

Explanation

Then we make a Seq of length 8 by repeatedly rotating the matrix clockwise (t(_)map(_.reverse)) and then dropping empty rows at the beginning (dropWhile(!_.toSet(1))).

Seq.iterate(_, 8)(t(_)map(_.reverse)dropWhile(!_.toSet(1)))

Just applying it 4 times would be enough to trim on all sides, but we also want all orientations. We first drop 4 so only trimmed matrices remain. Then we use exists to check if any of them meet a certain condition. However, this function won't work for all orientations, it'll only work for upside-down L's (that's why all 4 orientations were generated):

#####
#####
##

First, we make a Set out of m and its transpose, and for both of them, we drop the rows at the start that only contain #'s. For the rest of the rows in both, we reverse them and strip leading zeroes, then deduplicate them using toSet. The results for both m and its transpose are combined because we used flatMap, and then we make sure there is exactly one element. Thus, we eliminate legless shapes (less than one element) and shapes with extraneous #'s (more than one element).

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