8
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ I'm a little confused. The goal is a program that can print all triominos through all hexominos? \$\endgroup\$
    – Casey
    Apr 24, 2011 at 19:25
  • \$\begingroup\$ Actually you need to write program that takes number and outputs all polyominoes of that number. \$\endgroup\$
    – ralu
    Apr 24, 2011 at 20:02
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Casey
    Apr 24, 2011 at 20:12
  • 1
    \$\begingroup\$ You forgot the T tetromino. I take it you mean "one-sided" polyominos? \$\endgroup\$ Apr 24, 2011 at 21:38
  • \$\begingroup\$ It's polyominoes, not polynomials :D \$\endgroup\$
    – Lowjacker
    Apr 25, 2011 at 21:39

3 Answers 3

6
\$\begingroup\$

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:

**    
*     
*     

*     
**    
*     

**    
**    


 *    
**    
*     

*     
*     
**    

*     
**    
 *    

****  
\$\endgroup\$
1
  • \$\begingroup\$ 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? \$\endgroup\$
    – BERA
    Jun 23, 2020 at 6:26
3
\$\begingroup\$

Ruby, 266 241 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:

** **  *    *  ****  **   *
**  ** *** ***      **  ***
\$\endgroup\$
4
  • \$\begingroup\$ @Ventero: Thanks. Wasn't sure whether it would give an advantage, since the bitmap is split in 10 parts. \$\endgroup\$
    – Lowjacker
    Apr 24, 2011 at 23:47
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Nabb
    Apr 25, 2011 at 6:47
  • \$\begingroup\$ Where are missing reflections? \$\endgroup\$
    – ralu
    Apr 25, 2011 at 16:40
  • 1
    \$\begingroup\$ @ralu: I've added them, but if you want the reflections, you should say so in the question. \$\endgroup\$
    – Lowjacker
    Apr 25, 2011 at 19:29
1
\$\begingroup\$

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"
****


***
*

*
***

**
**


***
 *


**
 **

 **
**
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.