# Whose neighbours are hostile?

## Introduction

For the purposes of this challenge, we will define the neighbours of an element $E$ in a square matrix $A$ (such that $E=A_{i,j}$) as all the entries of $A$ that are immediately adjacent diagonally, horizontally or vertically to $E$ (i.e. they "surround" $E$, without wrapping around).

For pedants, a formal definition of the neighbours of $A_{i,\:j}$ for an $n\times n$ matix $A$ is (0-indexed): $$N_{i,\:j}=\{A_{a,\:b}\mid(a,b)\in E_{i,\:j}\:\cap\:([0,\:n)\:\cap\:\Bbb{Z})^2\}$$ where $$E_{i,\:j}=\{i-1,\:i,\:i+1\}\times \{j-1,\:j,\:j+1\} \text{ \\ } \{i,\:j\}$$

Let's say that the element at index $i,\:j$ lives in hostility if it is coprime to all its neighbours (that is, $\gcd(A_{i,\:j},\:n)=1\:\forall\:n\in N_{i,\:j}$). Sadly, this poor entry can't borrow even a cup of sugar from its rude nearby residents...

Enough stories: Given a square matrix $M$ of positive integers, output one of the following:

• A flat list of elements (deduplicated or not) indicating all entries that occupy some indices $i,j$ in $M$ such that the neighbours $N_{i,\:j}$ are hostile.
• A boolean matrix with $1$s at positions where the neighbours are hostile and $0$ otherwise (you can choose any other consistent values in place of $0$ and $1$).
• The list of pairs of indices $i,\:j$ that represent hostile neighbourhoods.

Reference Implementation in Physica – supports Python syntax as well for I/O. You can take input and provide output through any standard method and in any reasonable format, while taking note that these loopholes are forbidden by default. This is code-golf, so the shortest code in bytes (in every language) wins!

Moreover, you can take the matrix size as input too and additionally can take the matrix as a flat list since it will always be square.

## Example

Consider the following matrix:

$$\left(\begin{matrix} 64 & 10 & 14 \\ 27 & 22 & 32 \\ 53 & 58 & 36 \\ \end{matrix}\right)$$

The corresponding neighbours of each element are:

i j – E  -> Neighbours                          | All coprime to E?
|
0 0 – 64 -> {10; 27; 22}                        | False
0 1 – 10 -> {64; 14; 27; 22; 32}                | False
0 2 – 14 -> {10; 22; 32}                        | False
1 0 – 27 -> {64; 10; 22; 53; 58}                | True
1 1 – 22 -> {64; 10; 14; 27; 32; 53; 58; 36}    | False
1 2 – 32 -> {10; 14; 22; 58; 36}                | False
2 0 – 53 -> {27; 22; 58}                        | True
2 1 – 58 -> {27; 22; 32; 53; 36}                | False
2 2 – 36 -> {22; 32; 58}                        | False


And thus the output must be one of the following:

• {27; 53}
• {{0; 0; 0}; {1; 0; 0}; {1; 0; 0}}
• {(1; 0); (2; 0)}

## Test cases

Input –> Version 1 | Version 2 | Version 3

[[36, 94], [24, 69]] ->
[]
[[0, 0], [0, 0]]
[]
[[38, 77, 11], [17, 51, 32], [66, 78, 19]] –>
[38, 19]
[[1, 0, 0], [0, 0, 0], [0, 0, 1]]
[(0, 0), (2, 2)]
[[64, 10, 14], [27, 22, 32], [53, 58, 36]] ->
[27, 53]
[[0, 0, 0], [1, 0, 0], [1, 0, 0]]
[(1, 0), (2, 0)]
[[9, 9, 9], [9, 3, 9], [9, 9, 9]] ->
[]
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
[]
[[1, 1, 1], [1, 1, 1], [1, 1, 1]] ->
[1, 1, 1, 1, 1, 1, 1, 1, 1] or [1]
[[1, 1, 1], [1, 1, 1], [1, 1, 1]]
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
[[35, 85, 30, 71], [10, 54, 55, 73], [80, 78, 47, 2], [33, 68, 62, 29]] ->
[71, 73, 47, 29]
[[0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1]]
[(0, 3), (1, 3), (2, 2), (3, 3)]

• Borrowing stuff from hostile neighbors? For some reason, this reminds me of Jeff Minter's game Hover Bovver... – Arnauld Sep 16 '18 at 13:17
• Can we take the matrix size as input? – Delfad0r Sep 17 '18 at 5:32
• @Delfad0r I always forget to mention that. Yes, you may take the matrix size as input. – Mr. Xcoder Sep 17 '18 at 7:19

# APL (Dyalog), 17 bytes

1=⊢∨(×/∘,↓)⌺3 3÷⊢


Try it online! (credits to ngn for translating the test cases to APL)

### Brief explanation

(×/∘,↓)⌺3 3 gets the product of each element with its neighbours.

Then I divide by the argument ÷⊢, so that each entry in the matrix has been mapped to the product of its neighbors.

Finally I take the gcd of the argument with this matrix ⊢∨, and check for equality with 1, 1=

Note, as with ngn's answer, this fails for some inputs due to a bug in the interpreter.

# JavaScript (ES6), 121 bytes

Returns a matrix of Boolean values, where false means hostile.

m=>m.map((r,y)=>r.map((v,x)=>[...'12221000'].some((k,j,a)=>(g=(a,b)=>b?g(b,a%b):a>1)(v,(m[y+~-k]||0)[x+~-a[j+2&7]]||1))))


Try it online!

### How?

The method used to isolate the 8 neighbors of each cell is similar to the one I described here.

### Commented

m =>                            // m[] = input matrix
m.map((r, y) =>               // for each row r[] at position y in m[]:
r.map((v, x) =>             //   for each value v at position x in r[]:
[...'12221000']           //     we consider all 8 neighbors
.some((k, j, a) =>        //     for each k at position j in this array a[]:
( g = (a, b) =>         //       g is a function which takes 2 integers a and b
b ?                 //       and recursively determines whether they are
g(b, a % b)       //       coprime to each other
:                   //       (returns false if they are, true if they're not)
a > 1             //
)(                      //       initial call to g() with:
v,                    //         the value of the current cell
(m[y + ~-k] || 0)     //         and the value of the current neighbor
[x + ~-a[j + 2 & 7]]  //
|| 1                  //         or 1 if this neighbor is undefined
))))                          //         (to make sure it's coprime with v)


# MATL, 22 bytes

tTT1&Ya3thYC5&Y)Zd1=A)


Input is a matrix. Output is all numbers with hostile neighbours.

### Explanation with worked example

Consider input [38, 77, 11; 17, 51, 32; 66, 78, 19] as an example. Stack contents are shown bottom to top.

t         % Implicit input. Duplicate
% STACK: [38, 77, 11;
17, 51, 32;
66, 78, 19]
[38, 77, 11;
17, 51, 32;
66, 78, 19]
TT1&Ya    % Pad in the two dimensions with value 1 and width 1
% STACK: [38, 77, 11;
17, 51, 32;
66, 78, 19]
[1,  1,  1,  1,  1;
1,  38, 77, 11, 1;
1,  17, 51, 32, 1;
1,  66, 78, 19, 1
1,  1,  1,  1,  1]
3thYC     % Convert each sliding 3×3 block into a column (in column-major order)
% STACK: [38, 77, 11;
17, 51, 32;
66, 78, 19]
[ 1,  1,  1,  1, 38, 17,  1, 77, 51;
1,  1,  1, 38, 17, 66, 77, 51, 78;
1,  1,  1, 17, 66,  1, 51, 78,  1;
1, 38, 17,  1, 77, 51,  1, 11, 32;
38, 17, 66, 77, 51, 78, 11, 32, 19;
17, 66,  1, 51, 78,  1, 32, 19,  1;
1, 77, 51,  1, 11, 32,  1,  1,  1;
77, 51, 78, 11, 32, 19,  1,  1,  1;
51, 78,  1, 32, 19,  1,  1,  1,  1]
5&Y)      % Push 5th row (centers of the 3×3 blocks) and then the rest of the matrix
% STACK: [38, 77, 11;
17, 51, 32;
66, 78, 19]
[38, 17, 66, 77, 51, 78, 11, 32, 19]
[ 1,  1,  1,  1, 38, 17,  1, 77, 51;
1,  1,  1, 38, 17, 66, 77, 51, 78;
1,  1,  1, 17, 66,  1, 51, 78,  1;
1, 38, 17,  1, 77, 51,  1, 11, 32;
17, 66,  1, 51, 78,  1, 32, 19,  1;
1, 77, 51,  1, 11, 32,  1,  1,  1;
77, 51, 78, 11, 32, 19,  1,  1,  1;
51, 78,  1, 32, 19,  1,  1,  1,  1]
Zd        % Greatest common divisor, element-wise with broadcast
% STACK: [38, 77, 11;
17, 51, 32;
66, 78, 19]
[1,  1,  1,  1,  1,  1,  1,  1,  1;
1,  1,  1,  1, 17,  6, 11,  1,  1;
1,  1,  1,  1,  3,  1,  1,  2,  1;
1,  1,  1,  1,  1,  3,  1,  1,  1;
1,  1,  1,  1,  3,  1,  1,  1,  1;
1,  1,  3,  1,  1,  2,  1,  1,  1;
1, 17,  6, 11,  1,  1,  1,  1,  1;
1,  1,  1,  1,  1,  1,  1,  1,  1]
1=        % Compare with 1, element-wise. Gives true (1) or false (0)
% STACK: [38, 77, 11;
17, 51, 32;
66, 78, 19]
[1, 1, 1, 1, 1, 1, 1, 1, 1;
1, 1, 1, 1, 0, 0, 0, 1, 1;
1, 1, 1, 1, 0, 1, 1, 0, 1;
1, 1, 1, 1, 1, 0, 1, 1, 1;
1, 1, 1, 1, 0, 1, 1, 1, 1;
1, 1, 0, 1, 1, 0, 1, 1, 1;
1, 0, 0, 0, 1, 1, 1, 1, 1;
1, 1, 1, 1, 1, 1, 1, 1, 1]
A         % All: true (1) for columns that do not contain 0
% STACK: [38, 77, 11;
17, 51, 32;
66, 78, 19]
[1, 0, 0, 0, 0, 0, 0, 0, 1]
)         % Index (the matrix is read in column-major order). Implicit display
% [38, 19]

• Will this work if the matrix is bigger than 3x3? – Robert Fraser Sep 17 '18 at 4:42
• @RobertFraser Yes, the procedure does not depend on matrix size. See last test case for example – Luis Mendo Sep 17 '18 at 9:23

# APL (Dyalog Classic), 23 22 bytes

-1 byte thanks to @H.PWiz

{∧/1=1↓∨∘⊃⍨1⌈4⌽,⍵}⌺3 3


Try it online!

doesn't support matrices smaller than 3x3 due to a bug in the interpreter

• @H.PWiz that's very smart, do you wanna post it as your own? – ngn Sep 16 '18 at 18:03
• Sure, you can also use (⊃∨⊢) -> ∨∘⊂⍨ I think – H.PWiz Sep 16 '18 at 18:04

# Jelly, 24 bytes

Hmm, seems long.

ỊẠ€T
ŒJ_€Ç€ḟ"J$ịFg"FÇịF  A monadic Link accepting a list of lists of positive integers which returns a list of each of the values which are in hostile neighbourhoods (version 1 with no de-duplication). Try it online! Or see a test-suite. ### How? ỊẠ€T - Link 1: indices of items which only contain "insignificant" values: list of lists Ị - insignificant (vectorises) -- 1 if (-1<=value<=1) else 0 € - for €ach: Ạ - all? T - truthy indices ŒJ_€Ç€ḟ"J$ịFg"FÇịF - Main Link: list of lists of positive integers, M
ŒJ                  - multi-dimensional indices
               - use as right argument as well as left...
€                -   for €ach:
_                 -     subtract (vectorises)
€             - for €ach:
J          -   range of length -> [1,2,3,...,n(elements)]
"           -   zip with:
ḟ            -     filter discard (remove the index of the item itself)
F       - flatten M
ị        - index into (vectorises) -- getting a list of lists of neighbours
F    - flatten M
"     - zip with:
g      -   greatest common divisor
F - flatten M
ị  - index into


# Python 2, 182177 166 bytes

lambda a:[[all(gcd(t,a[i+v][j+h])<2for h in[-1,0,1]for v in[-1,0,1]if(h|v)*(i+v>-1<j+h<len(a)>i+v))for j,t in E(s)]for i,s in E(a)]
from fractions import*
E=enumerate


Try it online!

Outputs a list of lists with True/False entries.

m?n|l<-[0..n-1]=[a|i<-l,j<-l,a<-[m!!i!!j],2>sum[1|u<-l,v<-l,(i-u)^2+(j-v)^2<4,gcd(m!!u!!v)a>1]]

The function ? takes the matrix m as a list of lists and the matrix size n`; it returns the list of entries in hostility.