8
\$\begingroup\$

A polyiamond of size \$n\$ is a contiguous shape formed by joining \$n\$ equilateral triangles side by side.

Your output should consist of two distinct characters, plus whitespace as necessary (▲ and ▼ work great!). Trailing whitespace is acceptable. You may use any other characters - but you may count ▲▼ as 1 byte each regardless of code page. If you use other characters, you must indicate which character corresponds to the up-facing triangle and which to the down-facing triangle.

You may not output duplicates - rotations and reflections of the same polyiamond are considered the same.

n=1:

n=2: ▲▼

Note that

▼
▲

is not a valid polyiamond - which is why the distinct characters are necessary!

n=3

▲▼▲

n=4

 ▲
▲▼▲

▲▼▲▼

▲▼▲
▼

Challenge

  • You may either take no input and output polyiamonds indefinitely or take a number \$n\$ as input and output all distinct polyiamonds of size \$n\$.
  • Standard rules apply. The shortest code wins.
\$\endgroup\$
7
  • \$\begingroup\$ Why doesn’t n=3 include an L shape? \$\endgroup\$
    – Jonah
    Apr 14 at 19:00
  • \$\begingroup\$ @Jonah Because that would be a rotation/reflection of the single polytriomino already there. \$\endgroup\$ Apr 14 at 19:02
  • \$\begingroup\$ oh duh... as soon as tried it on an actual triangular grid it's obvious.... \$\endgroup\$
    – Jonah
    Apr 14 at 19:08
  • 3
    \$\begingroup\$ The last 2 outputs for n=4 are identical under rotation. (There are only 3 ways to add a triangle to the n=3 triangle: on the end, on the short side, or on the long side.) Note that these shapes are called polyiamonds en.wikipedia.org/wiki/Polyiamond \$\endgroup\$ Apr 15 at 1:23
  • 2
    \$\begingroup\$ So, is the number of expected outputs A000577? (Illustrations up to n=9) \$\endgroup\$
    – Arnauld
    Apr 15 at 10:12

1 Answer 1

5
\$\begingroup\$

Ruby, 277 bytes

f=->p=[[2]],s=1{w=45;q=[]
p.map{|a|t=(?.*~-w+$/)*s;a.map{|k|t[k]="AV"[k%2]};$><<t
(s*3).times{|i|a.index(d=[-1,1,w*~0**e=a[i/3]][i%3]+e)||(c=a+[d];r=[]
12.times{|j|c=c.map!{|k|j%2<1?k%w*2+~k:k/w+k%w*w-(k/w+k%w)/2*~-w}.sort!.map{|m|m-c[0]/2*2+20}
r<<c*1}
q<<r.min)}}
f[q&q,s+1]}

Try it online!

First golfed version. Runs indefinitely

Ruby, 316 bytes

f=->n,p=[[2]],s=1{w=n*4+1
p.map{|a|t=(?.*~-w+$/)*s;a.map{|k|t[k]="AV"[k%2]};puts t,$/}
s<n&&(q=[]
p.map{|a|(s*3).times{|i|d=[-1,1,w*~0**e=a[i/3]][i%3]+e
a.index(d)||(c=a+[d];r=[]
12.times{|j|c=c.map!{|k|j%2<1?k%w+~(k/w)*w:(k/w+k%w*w)-(k/w+k%w)/2*~-w}.sort!.map{|m|m-(c[0]&-2)+n*2};r<<c*1}
q<<r.min)}}
f[n,q&q,s+1])
}

Try it online!

This is a first working version, drawing heavily on my answer to Sticky polyhexes

It's a function, taking the max size as input. Letting the code run indefinitely would probably be shorter.

Explanation

The code is a function taking one required and 2 optional inputs as follows:

  • n max size of polyiamond
  • p an array of polyiamonds
  • s the size of the polyiamonds in the array.

If p and s are not given it is assumed that s=1 and p contains the polyiamond [2] as a seed.

The board is w characters wide in the x direction and for calculation purposes is infinite in the y direction. Polyiamonds are represented as arrays of integers, one per triangle, of the form d=x+wy. It's important that w be odd, since this means that the oddness or evenness of d will determine whether upward pointing A or downward pointing V will be displayed. Therefore w is chosen as n*4+1.

The first task is to display the polyiamonds fed to the function as arguments. It is assumed that up to s lines may be needed to display these. This version uses . as a background, so the number of lines can be conveniently used to count the number of triangles in the polyiamond if this is not obvious.

If s<n we have not finished so we need to generate the list of polyiamonds of one size greater. To do this we start an empty array and run through all polyiamonds a in the input p. We take each triangle e in a and generate new triangles at e+1,e-1 and e+/-w. To determine the correct sign for the last of these, -1 (represented as ~0 due to Ruby priority rules) is raised to the power e. If the new triangle is already in a it is an overlap and can be rejected. If it is not in a we have increased the size of the polyiamond, so we form a new polyiamond c.

We apply 12 symmetry operations to c (see below) forming an array r and add the lexically lowest one to q. Once the process is finished for all polyiamonds in p we find the intersection q&q of q with itself to eliminate duplicates and then call f again with the new list of polyiamonds of size s+1.

Symmetry

The most challenging part was working out the symmetry operations. These are actually done at 45 degrees to my answer to the sticky polyhexes question above. The triangle grid can be considered as two interpenetrating hex grids, one of all upward pointing triangles and the other of all downward pointing triangles, so it's similar but different.

All 12 symmetries can be generated by alternating two reflections. The first (parallel to a triangle edge) is a negation of the y axis. But rather than a change of sign, a bitflip of the y coordinate is employed. This changes the oddness/evennness of all triangles, causing the symbol to flip at the same time.

k = k%w+~(k/w)*w

The second (perpendicular to a triangle edge)is a transposition of the x and y axes. However a skew correction term is required, since opposite corners of a diamond VA are 2 units across in the x direction and 1 unit down in the y direction. Therefore the half the manhattan distance from the origin x+y/2 is calculated and coordinates are adjusted by -w-1 times this, causing a skew in a northeasterly direction.

k = (k/w+k%w*w)-(k/w+k%w)/2*~-w

Overall this looks like this:

  start pattern        flip vertical    flip diagonal  skew correction  
  012 AVA                543 AVA        50 AV          501 AVA
  543 VAV     ----->     012 VAV   -->  41 VA   -->    432 VAV
                                        32 AV
\$\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.