### Communities

tag:snake search within a tag
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
created:<1w created < 1 week ago
post_type:xxxx type of post
Challenges

# Determine if a polyomino is "prime"

+2
−0

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.

Why does this post require moderator attention?
Why should this post be closed?

Holes and test cases (3 comments)
Can the polynominos be mirrored? (5 comments)

+1
−0

# 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)>;


Attempt This Online!

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

Why does this post require moderator attention?