The matrix has U

Question

Given a matrix of size at least ×ばつ3 formed by positive integers, determine if it contains at least one "U" pattern, defined as

+ + + - - - + +
+ + - N - N - +
+ + - N - N - +
+ + - N N N - +
+ + + - - - + +

where

• N is the same number, repeated in those seven positions
• - (optional) represents any number different than N. Each - can be a different number
• + (optional) represents any number. Each + can be a different number.

The amount of + and - entries obviously depends on the size of the matrix. In particular, some - may not exist because the pattern is adjacent to a matrix border. The above representation corresponds to a ×ばつ8 matrix.

The pattern must have the specified orientation. Reflections or rotations are not valid.

Test cases

Truthy

• Pattern with N=8:

   3 4 7 5 6 5 4 8
   8 7 3 8 5 8 2 4
   9 9 9 8 7 8 1 3
   4 5 3 8 8 8 3 6
   6 8 9 2 3 2 1 4
  

• Same pattern with some N values nearby:

   3 4 7 5 6 5 8 8
   8 7 3 8 5 8 2 4
   9 9 9 8 7 8 1 3
   4 5 3 8 8 8 3 6
   6 8 8 2 3 2 1 4
  

• Pattern with N=3, touching a matrix border:

   7 5 4 7 5 4 5 6
   7 1 5 3 5 3 6 3
   3 5 3 3 9 3 2 3
   3 1 2 6 7 3 3 3
   4 5 2 8 9 6 8 4 
  

• Pattern with N=4, touching a matrix corner:

   4 1 4 6
   4 3 4 3 
   4 4 4 5
   7 5 3 5
  

• Two patterns, with N=5 and N=9:

   6 7 9 4 5 6 7
   5 2 5 9 8 9 8
   5 1 5 9 6 9 3
   5 5 5 9 9 9 4
   8 7 6 1 3 2 5
  

• Pattern with N=3, and broken pattern with 1:

   1 2 1 2 3 2 3
   1 2 1 2 3 2 3
   1 1 1 1 3 3 3
  

• Numbers can be greater than 9; here N=25:

   23 56 34 67 34 3
   34 25 4 25 48 49
   24 25 97 25 56 56
   12 25 25 25 32 88
  

• Minimalistic case, N=2:

   2 1 2
   2 5 2
   2 2 2
  

Falsy

• Nothing special here:

   7 8 6 5 4
   3 4 5 6 3
   3 5 6 4 4
   7 8 9 3 2
  

• Rotated or reflected patterns are not valid:

   9 9 9 3 7 7 7 5
   4 4 9 2 7 8 7 6
   9 9 9 8 7 9 7 4
  

• Some - entry spoils the pattern

   9 5 5 6 5
   3 8 5 9 5
   2 9 5 5 5
  

• Some - entry spoils the pattern, even if the result would be a "U" with longer horns

   7 8 5 2 5
   9 2 5 6 5
   3 8 5 9 5
   2 9 5 5 5
  

• Minimalistic case, no pattern

   9 9 9
   9 8 9
   9 9 9 
  

Additional rules

• You can choose to output:
  • Any two distinct values/arrays/strings... depending on whether the matrix contains the specified pattern or not; or
  • Anything truthy if the matrix contains the specified pattern, and anything falsy otherwise. The specific truthy and falsy values/arrays/strings... can be different for different inputs.
• The code should work in theory for matrices of arbitrarily large size, containing arbitrarily large numbers. In practice, it is acceptable if the program is limited by time, memory or data-type restrictions.
• Input and output are flexible as usual. Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
• Shortest code in bytes wins.

• tsh: Suggest testcase: 1 2 1 2 3 2 3/ 1 2 1 2 3 2 3/ 1 1 1 1 3 3 3 a broken 1 with a valid 3.
• Luis Mendo: @tsh Good idea! Edited
• Arnauld: Somewhat related.
• Abigail: Can there be 0's in the input? Negative numbers? The examples suggest not.
• Luis Mendo: @Abigail No, only positive integers (it's stated in the first line)

Answer 1

JavaScript (ES7), (削除) 124 110 (削除ここまで) 105 bytes

Returns a Boolean value.

m=>m.some((r,y)=>r.some((v,x)=>(g=n=>n--?v==(m[y+~-(n/5)]||0)[x+n%5-1]^144140166590/3**n%3&&g(n):1)(24)))

Try it online!

How?

For each reference cell of value \$v\$ at \$(x,y)\$ in the input matrix \$m\$, we test 24 neighbor cells.

The constant \144140166590ドル\$ is \111210001101011010121112ドル_3\$ in base 3. By reversing the digits and rearranging them into a 5x5 matrix, this gives:

$$\begin{pmatrix}2&1&1&1&2\\ 1&\color{red}0&1&0&1\\ 1&0&1&0&1\\ 1&0&0&0&1\\ 2&1&1&1&-\end{pmatrix}$$

where:

• the cell in red is the reference cell
• \0ドル\$ means that this cell must be equal to \$v\$
• \1ドル\$ means that this cell must be different from \$v\$
• \2ドル\$ means that we don't care

The bottom-right cell of the matrix is ignored, but it should be a \2ドル\$ anyway (for we don't care).

The \$n\$-th cell to test (0-indexed) is the cell whose coordinates are:

$$\big(x+(n\bmod 5)-1,y+\lfloor n/5\rfloor-1\big)$$

The corresponding value in the above matrix is given by:

$$V=\left\lfloor\frac{144140166590}{3^n}\right\rfloor\bmod 3$$

We do a bitwise XOR between the cell comparison test and \$V\$:

 is equal | V | XOR | success?
----------+-----+-----+--------------------------
 0 | 0 | 0 | no (should be equal)
 1 | 0 | 1 | yes
----------+-----+-----+--------------------------
 0 | 1 | 1 | yes
 1 | 1 | 0 | no (should be different)
----------+-----+-----+--------------------------
 0 | 2 | 2 | yes \__ always
 1 | 2 | 3 | yes / ≠ 0

If all 24 tests are successful, we've found a valid U.

Answer 2

Julia 0.6, (削除) 78 (削除ここまで) 75 bytes

x->any(n->7∈conv2(reshape(digits(287035908958,3)-1,5,5),1÷-~abs(x-n)),x)

Try it online!

Uses 2D-convolution to find the pattern encoded in the magic constant. The constant is derived via base 3 digits similarly to Arnauld's answer, but with 0 and 2 swapped. This way, after subtracting 1, we get the following correspondence: N = 1, '+' = 0, '-' = -1.

The input matrix is transformed to N = 1, everything else = 0. After convolution, the middle cell of the found pattern will accumulate a total of 7 (for the number of N's in the U-shape). If any of required N's is missing, the sum will not reach 7, and if an N (= 1) is present in the forbidden position, it will gain a negative contribution due to the multiplication by -1 in the pattern.

• Luis Mendo: Nice! Convolution is the way I've seen this problem from the beginning

Answer 3

APL (Dyalog Extended), (削除) 62 (削除ここまで) (削除) 51 (削除ここまで) 45 bytes (SBCS)

-6 based on fireflame241's solution.

⍲,(⍱{'GILNQRS'≡⎕A[⍸,⍵]~'AEUY'}⌺5 5⍤=) ̈∘⊂0⍪0,⊢

Try it online!

• Luis Mendo: Lots of funny faces in the code as usual ⍨ ö ¨∘
• Adám: @LuisMendo Well, it'd only add one byte.
• Luis Mendo: I have added a new test case (which now appears second); in case you want to include it
• Adám: @LuisMendo I'm a bit busy. Feel free to edit my post.
• Luis Mendo: Done. I added the new case and another one that was missing

Answer 4

Charcoal, 58 bytes

⊙θ∧‹1κ⊙ι∧‹1μ⬤θ⬤ν∨‹3+↔−ξ⊖κ↔−ρ⊖μ==λπ∧›2↔−ξ⊖κ∨=1↔−ρ⊖μ∧=ξκ=ρ⊖μ

Try it online! Link is to verbose version of code. Takes input as an array and outputs a Charcoal boolean, i.e. - if it contains U, nothing if not. Explanation:

⊙θ∧‹1κ

Find a valid bottom row where:

⊙ι∧‹1μ

Find a valid right column where:

⬤θ⬤ν

All elements of the array must satisfy:

∨‹3+↔−ξ⊖κ↔−ρ⊖μ

The element has a Manhattan distance from the centre of the U of more than 3, or...

==λπ

... the equality of the element with the outer element matches:

∧›2↔−ξ⊖κ

The vertical distance of the element from the centre of the U is less than 2, and...

∨=1↔−ρ⊖μ

... the horizontal distance of the element from the centre of the U is exactly 1, or...

∧=ξκ=ρ⊖μ

... the element is the bottom centre of the U.

Answer 5

APL (Dyalog Extended), 62 bytes

{{∨/∊({7 9 12 14 17 18 19≡1 5 21 25~⍨⍸,⍵}⌺5 5) ̈(,⍵)= ̈⊂⍵}0⍪0,⍵}

Try it online! (includes the new test case).

My first APL golf! Returns a 1 if there is a U, or 0 otherwise.

• Adám: Nice idea in the inner dfn. I've borrowed and golfed it a bit. However, only 1 is truthy in APL, so you should replace +/ with ∨/
• fireflame241: @Adám Fixed. Smart use of the alphabet in yours

Answer 6

J, 68 bytes

Builds up 16 U's with the 16 possible combinations of 0 and 1 in the corners, then looks for them in the position matrix of each number.

[:+./@,(0 4 4|.#:20 20 28(,4 4&#:)"p./i.16)E."2/[:(="{~,)4|:@|.@,&_]

Try it online!