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
2 comment threads
3 comment threads