# Polyomino generator

Write a program that prints the shapes of one-sided polyominoes.

Given input 4 (tetrominos), a sample output would be:

 *   *         *     *
*   *    **   **   **  *
**   **   **    *   *  ***  ****


You are not restricted with respect to orientation, ordering or layout as long as polyominoes are not connected and not duplicated. (E.g. you can print the shapes in a column rather than a row)

Provide code that inputs a number from 3 to 6 and outputs the one-sided polyominoes of that size. The expected number of polyominoes output are 2, 7, 18, and 60 for 3, 4, 5, and 6 as inputs respectively.

Shortest code wins, present your solution for number 4.

• I'm a little confused. The goal is a program that can print all triominos through all hexominos? – Casey Apr 24 '11 at 19:25
• Actually you need to write program that takes number and outputs all polyominoes of that number. – ralu Apr 24 '11 at 20:02
• @ralu Could you please clarify that in your post? The "Provide code that accepts number from 3 to 6 and displays proper polyomino" bit makes it seem like you only want triominos-hexominos. – Casey Apr 24 '11 at 20:12
• You forgot the T tetromino. I take it you mean "one-sided" polyominos? – Keith Randall Apr 24 '11 at 21:38
• It's polyominoes, not polynomials :D – Lowjacker Apr 25 '11 at 21:39

## Python, 398 392 chars

n=input()
r=range
T=lambda P:set(p-min(p.real for p in P)-min(p.imag for p in P)*1j for p in P)
A=[]
for i in r(1<<18):
P=[k%3+k/3*1j for k in r(18)if i>>k&1]
C=set(P[:1])
for x in P:[any(p+1j**k in C for k in r(4))and C.add(p)for p in P]
P=T(P)
if not(C^P or P in A or len(P)-n):
for y in r(4):print''.join(' *'[y+x*1j in P] for x in r(6))
A+=[T([p*1j**k for p in P])for k in r(4)]


Polyominos are represented as sets of complex numbers representing the cells of the polyomino. For example, T takes a polyomino and translates it so the minimum real and imaginary coordinates are 0.

The outer loop iterates through all 2^18 3x6 grids, generating a potential polyomino P, making sure P is connected (by computing C, the part of the polyomino connected to P[0]), checking that P isn't in the list A of previously found polyominos, and verifying that P has exactly n cells. Any new polyomino is added to A in all 4 rotations.

It takes two minutes or so to run to completion. Here's the result for n=4:

**
*
*

*
**
*

**
**

*
**
*

*
*
**

*
**
*

****

• This is just Printing out **** when I try it. And n is a string so I get unsupported operand… error on line 10. Do you know how to fix it? – BERA Jun 23 '20 at 6:26

## Ruby, 266241 320 (227 without reflections)

Given the input restrictions, it's easier to just use a bitmap of all the polyominos.

puts [%w[13 3],%w[1vqxip 1s9b3b],%w[1j85qxc81ax0oxld 1db08aq5w1vdul13 172qaw25hgn8jn5t],%w[5l91ancci09g0iuurrdbkbrsl58jjiodia8irxlivoufjjse42o4l8hlcz 3qbvfj70ksz14cngk9exust0w1qjshykauo6yvyyn3j6oefyy1xc58hsoj 26c0102a8vw34q88pktwlkepxzcslicg6ydtrz4zhyyutd4bukh73187qb]][gets.hex-3].map{|n|n.to_i(36).to_s(2).tr'10','* '}


Old version (outputs just the free polyominoes):

puts [%w[13 3],%w[9iz3 a5z],%w[cfu9zai70z b3tsb0pge1 12t8eks810j],%w[5wgmz704fjqc593xfwrmkwb7k0j9ztr31v fr8weq5t88qdxp93hit2fh8899qcbr2a9f 10r578ajcw2n15dwywsm0ep601kiv41cco3]][gets.hex-3].map{|n|n.to_i(36).to_s(2).tr'10','* '}


Output for n=4:

** **  *    *  ****  **   *
**  ** *** ***      **  ***

• @Ventero: Thanks. Wasn't sure whether it would give an advantage, since the bitmap is split in 10 parts. – Lowjacker Apr 24 '11 at 23:47
• Use %w notation to save about 10 characters (e.g. %w[13 3]). Also, since the input is a single digit, you can use gets.hex to save another char. – Nabb Apr 25 '11 at 6:47
• Where are missing reflections? – ralu Apr 25 '11 at 16:40
• @ralu: I've added them, but if you want the reflections, you should say so in the question. – Lowjacker Apr 25 '11 at 19:29

### Golfscript, 221 chars

Also 221 bytes. Inspired by Lowjacker's approach, but moderately different in actual implementation (and produces one-sided rather than two-sided polyominos).

Because some of the characters used, while valid Unicode codepoints (and one byte each in UTF-8), are non-printable, I present the base-64 encoding of the script:

fidAQEAVRRVALVs9TUZFUwhgA0BrdjVXGm4VOl8aDgMZfBdoVQQzNk0YLQ9eXCciBhwQH0ADDW9E
KlomSXgoLBxxI1oEeB9XPm51GF43bHBKQzl3WQ5vXTJCTABfEz4bJBlaWX0XL2QVDF5ZXFw5BxpF
IzNUKmUtYwEEfQEKckMSbjAlQmhYHShQaAtjK1QFbnt5WQokFkNkHgNlL35cXCU6Hj8nIkAiLz0x
MjdiYXNlIDRiYXNlWzNdL3tbKVxbMl0vLi0xJUAqXXt7eyIgKiI9fSVuK30vbn0vfS8=


And the script itself with the magic strings substituted:

~"@@@Magic@strings@go@here""@"/=127base 4base[3]/{[)\[2]/.-1%@*]{{{" *"=}%n+}/n}/}/


Example execution:

\$ golfscript.rb poly.gs <<<"4"
****

***
*

*
***

**
**

***
*

**
**

**
**