6
\$\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\$
  • \$\begingroup\$ I'm a little confused. The goal is a program that can print all triominos through all hexominos? \$\endgroup\$ – Casey Apr 24 '11 at 19:25
  • \$\begingroup\$ Actually you need to write program that takes number and outputs all polyominoes of that number. \$\endgroup\$ – ralu Apr 24 '11 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 '11 at 20:12
  • 1
    \$\begingroup\$ You forgot the T tetromino. I take it you mean "one-sided" polyominos? \$\endgroup\$ – Keith Randall Apr 24 '11 at 21:38
  • \$\begingroup\$ It's polyominoes, not polynomials :D \$\endgroup\$ – Lowjacker Apr 25 '11 at 21:39
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\$
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\$
  • \$\begingroup\$ @Ventero: Thanks. Wasn't sure whether it would give an advantage, since the bitmap is split in 10 parts. \$\endgroup\$ – Lowjacker Apr 24 '11 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 '11 at 6:47
  • \$\begingroup\$ Where are missing reflections? \$\endgroup\$ – ralu Apr 25 '11 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 '11 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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