21
\$\begingroup\$

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 
    

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

APL (Dyalog Extended), 62 51 45 bytes (SBCS)

-6 based on fireflame241's solution.

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

Try it online!

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Lots of funny faces in the code as usual ö ¨∘ \$\endgroup\$ – Luis Mendo Jun 26 at 10:53
  • 1
    \$\begingroup\$ @LuisMendo Well, it'd only add one byte. \$\endgroup\$ – Adám Jun 26 at 11:26
  • \$\begingroup\$ I have added a new test case (which now appears second); in case you want to include it \$\endgroup\$ – Luis Mendo Jun 26 at 13:06
  • \$\begingroup\$ @LuisMendo I'm a bit busy. Feel free to edit my post. \$\endgroup\$ – Adám Jun 26 at 13:06
  • \$\begingroup\$ Done. I added the new case and another one that was missing \$\endgroup\$ – Luis Mendo Jun 26 at 13:13
16
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
9
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ Nice! Convolution is the way I've seen this problem from the beginning \$\endgroup\$ – Luis Mendo Jun 26 at 18:05
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 ∨/ \$\endgroup\$ – Adám Jun 26 at 11:24
  • \$\begingroup\$ @Adám Fixed. Smart use of the alphabet in yours \$\endgroup\$ – fireflame241 Jun 27 at 1:34
3
\$\begingroup\$

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!

| improve this answer | |
\$\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.