# The matrix has U

Given a matrix of size at least 3×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 5×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


• 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.
• 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.
– tsh
Jun 26, 2020 at 10:15
• @tsh Good idea! Edited Jun 26, 2020 at 10:20
• Jun 26, 2020 at 10:58
• Can there be 0's in the input? Negative numbers? The examples suggest not. Jun 29, 2020 at 19:42
• @Abigail No, only positive integers (it's stated in the first line) Jun 29, 2020 at 23:22

# 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.

# 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.

• Nice! Convolution is the way I've seen this problem from the beginning Jun 26, 2020 at 18:05

# APL (Dyalog Extended), 6251 45 bytes (SBCS)

-6 based on fireflame241's solution.

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


Try it online!

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

# Charcoal, 58 bytes

⊙θ∧‹¹κ⊙ι∧‹¹μ⬤θ⬤ν∨‹³⁺↔⁻ξ⊖κ↔⁻ρ⊖μ⁼⁼λπ∧›²↔⁻ξ⊖κ∨⁼¹↔⁻ρ⊖μ∧⁼ξκ⁼ρ⊖μ


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:

⊙θ∧‹¹κ


Find a valid bottom row where:

⊙ι∧‹¹μ


Find a valid right column where:

⬤θ⬤ν


All elements of the array must satisfy:

∨‹³⁺↔⁻ξ⊖κ↔⁻ρ⊖μ


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:

∧›²↔⁻ξ⊖κ


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

∨⁼¹↔⁻ρ⊖μ


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

# 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.

• 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 ∨/
[:+./@,(0 4 4|.#:20 20 28(,4 4&#:)"p./i.16)E."2/[:(="{~,)4|:@|.@,&_]