# Determine if a polyomino is "prime"

An $n$-polyomino is a connected subset of the square tiling consisting of $n$ squares. We will not require that polyominos be simply connected, that is they can have holes.

We will say a $n$-polyomino is *prime* if it cannot be disected into disjoint $k$-polyominos for any 1<$k$<$n$. For example this square 4-polyomino:

```
XX
XX
```

can be dissected into two 2-polyominos, but this "T"-shaped 4-polyomino cannot:

```
XXX
X
```

The $k$-polyominos do not need to be equal for example:

```
XXXXX
X XX
```

This 8-polyomino can be subdivided into the two polyominos shown in the last examples. They are not equal but they are both 4-polyominos so the example is not prime.

Naturally if $n$ is a prime number all $n$-polyominos are prime, however as shown above there are prime $n$-polyominos where $n$ is not prime. Here are examples for the next couple composite numbers

### 6

```
X
XXXX
X
```

### 8

```
X
XXXXX
X X
```

### 9

```
XXXXXXXX
X
```

### 10

```
XXXXXX
X
XXX
```

### 12

```
XXXXXXXXX
X X
X
```

### 14

```
XXXXXXXXXXXX
X X
```

### 15

```
XXX
X X X
XXXXXX
X X
X
```

## Challenge

Given a polyomino as input output one consistent value if it is prime and another consistent distinct value if it is not prime.

This is code-golf the goal being to minimize the size of your source code as measured in bytes.

## 1 answer

# Rust, 425 bytes

```
|a:T|a.iter().any(|b|a.iter().any(|c|c!=b&&f(&a,&vec![*b],&vec![*c])));fn g(a:&T,b:&T,c:&T,e:(i8,i8))->bool{[(0,1),(1,0),(-1,0),(0,-1)].iter().any(|g|{let m=(e.0+g.0,e.1+g.1);a.contains(&m)&&!b.contains(&m)&&!c.contains(&m)&&f(a,&[vec![m],b.clone()].concat(),c)})}fn f(a:&T,b:&T,c:&T)->bool{if a.len()==b.len()+c.len(){b.len()>1&&c.len()>1}else{b.iter().any(|e|g(a,b,c,*e))||c.iter().any(|e|g(a,c,b,*e))}}type T=Vec<(i8,i8)>;
```

I'm not 100% clear on the challenge, but this seems to work

## 3 comment threads