18
\$\begingroup\$

Chaim Goodman-Strauss, Craig Kaplan, Joseph Myers and David Smith found the following simple (both objectively and subjectively) polygon that tiles the plane, but only aperiodically:

Indeed they found a one-parameter family of such aperiodic monotiles or "einsteins". The edges of all tiles in this family meet at 90° or 120° and are made out of two distinct lengths:

Let \$a\$ and \$b\$ be nonnegative real numbers and define the following turtle graphics commands:

  • \$A,B\$: move forwards by \$a\$ or \$b\$ respectively (blue and purple edges in the image above)
  • \$L,R\$: turn left or right by 90° respectively
  • \$S,T\$: turn left or right by 60° respectively

Then the aperiodic tile \$T(a,b)\$ associated with \$a\$ and \$b\$ is traced by the command sequence $$ASAR\ BSBR\ ATAL\ BTBR\ ATAL\ BTBBTBR$$ It is clear that \$T(a,b)\$ is similar to \$T(ka,kb)\$ for any scaling constant \$k\$, so we can reduce the number of parameters to one by defining $$T(p)=T(p,1-p)\qquad0\le p\le1$$ The tile in this challenge's first picture – the "hat" of the GKMS paper – is \$T\left(\frac{\sqrt3}{\sqrt3+1}\right)\$. \$T(0)\$, \$T(1)\$ and \$T(1/2)\$ admit periodic tilings, but the first two of these exceptions are polyiamonds and play a central role in the proof that \$T(p)\$ for all other \$p\in[0,1]\$ is aperiodic.

Task

Given a real number \$p\$ satisfying \$0\le p\le1\$, draw \$T(p)\$ as defined above.

  • The image can be saved to a file or piped raw to stdout in any common image file format, or it can be displayed in a window.
  • The polygon may be drawn in any orientation and may be flipped from the schematic above (though of course the aspect ratio must not be changed). It may be filled with any colour or pattern and may optionally be outlined with any colour, but the polygon's boundary must be clear.
  • Raster images must be at least 400 pixels wide, and an error of 2 pixels/1% is allowed.

This is ; fewest bytes wins.

Test cases

\$p\$ \$T(p)\$
0
0.2
\$\frac1{\sqrt3+1}=\$
0.36602540378443865
0.5
\$\frac{\sqrt3}{\sqrt3+1}=\$
0.6339745962155613
0.8
1
\$\endgroup\$
1
  • \$\begingroup\$ +1 for the design on each tile. FYI, $\frac1{\sqrt3+1}$ can be simplified to $\frac{\sqrt3-1}2$, and $\frac{\sqrt3}{\sqrt3+1}$ to $\frac{3-\sqrt3}2$. \$\endgroup\$
    – Rosie F
    Mar 24, 2023 at 7:37

7 Answers 7

11
\$\begingroup\$

JavaScript (ES6), 150 bytes

-10 thanks to @Neil

Generates a SVG.

with(Math)f=p=>`<svg viewBox="-1 -1 9 9"><path d="M0 0${"0354105723572".replace(/./g,v=>`l${(d=v&4?p:1-p)*cos(a+=PI/=v%4*5%9-3)} ${d*sin(a)}`,a=0)}">`

Try it online!

Move encoding

Each move is encoded with a 3-bit value \$v\$ stored as a single decimal digit.

Bit: 2 1 0
     | \_/
     |  |
     |  +--> rotation angle a (00: -π/3, 01: π/2, 10: -π/2, 11: π/3)
     +-----> distance d (p if set, 1-p otherwise)

We use the expression \$\big(((v\bmod 4)\times 5)\bmod 9\big)-3\$ to convert \$v\$ into the divisor of \$\pi\$:

 v mod 4 | *5 | mod 9 | -3
---------+----+-------+----
    0    |  0 |   0   | -3
    1    |  5 |   5   |  2
    2    | 10 |   1   | -2
    3    | 15 |   6   |  3

This is implemented as Math.PI/=v%4*5%9-3. Although Math.PI is read-only, this is a valid syntax which (fortunately!) doesn't modify the value of \$\pi\$ and is one byte shorter than using parentheses.

Drawing

Once we have \$d\$ and \$a\$, we compute \$(dx,dy)\$ with:

$$dx=d\times\cos(a)\\dy=d\times\sin(a)$$

and append a statement l dx dy to the SVG path.

Animated output

with(Math)f=p=>`<svg viewBox="-1 -1 9 9"><path d="M0 0${"0354105723572".replace(/./g,v=>`l${(d=v&4?p:1-p)*cos(a+=PI/=v%4*5%9-3)} ${d*sin(a)}`,a=0)}">`

k = 0; setInterval(_ => { p = 0.5 + 0.5 * Math.cos(k += 0.04); document.body.innerHTML = `<p style="margin-bottom:-40px">p = ${p.toFixed(2)}</p>` + f(p); }, 20)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Can't you use l instead of L and then you don't need x or y, saving you 10 bytes? \$\endgroup\$
    – Neil
    Mar 25, 2023 at 6:35
  • \$\begingroup\$ @Neil Not sure whether I've used l before, but I totally forgot about it anyway. Thank you! \$\endgroup\$
    – Arnauld
    Mar 25, 2023 at 8:07
  • \$\begingroup\$ I'ts a pitty there seems to be no implementation of/polyfill for the SVG Bearing path command b. Since it has been removed from the 2.0 spec, I am not sure it will ever become a reality. \$\endgroup\$
    – ccprog
    Mar 28, 2023 at 20:49
5
\$\begingroup\$

Logo, 133 bytes

to s:a:n:m
fw:a*150
rt:n*60-60
fw:a*150
rt:m*90-90
end
to t:a
s 1-:a 2 2
s:a 0 2
s 1-:a 0 2
s:a 2 0
s 1-:a 2 2
s:a 2 0
s 1-:a 2 1
end

Unfortunately the online logo resource I used to use is no longer available, but you can paste the code into the textbox on https://rmmh.github.io/papert/static/ and run it. (Also paste the following code to actually get anything to run.)

clear
t 0.5

(Substitute your desired value for 0.5.)

\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 112 bytes

(q=1-#;r=Pi/2;t=Pi/3;AnglePath@MapThread[List,{{#,#,q,q,#,#,q,q,#,#,q,2 q,q},{0,-t,r,-t,r,t,-r,t,r,t,-r,t,t}}])&

Try it online!

With TIO output is a list of vertices.
With Mathematica desktop:

data = {0.0, 0.2, 0.366, 0.444, 0.5, 0.634, 0.8, 1.0};
Multicolumn[
 Row@{#, Graphics[{Blue, Polygon@g@#}]} & /@ data, 4]

enter image description here

\$\endgroup\$
2
  • \$\begingroup\$ great! code to show it dynamically k = 0; Dynamic[p = 0.5 + 0.5 Cos[k += 4*10^(-100)]; Row[{Row[{"p = ", NumberForm[p, {Infinity, 2}]}], Graphics[{Blue, Polygon@g@p}, ImageSize -> {Automatic, 100}]}], UpdateInterval -> 4*10^(15)] \$\endgroup\$
    – 138 Aspen
    Mar 30, 2023 at 8:59
  • \$\begingroup\$ this is a related post in WOLFRAM COMMUNITY \$\endgroup\$
    – 138 Aspen
    Mar 30, 2023 at 11:34
4
\$\begingroup\$

Python, 123 118 bytes

from turtle import*
def t(a):
 m=13609645555;reset()
 while m:fd([1-a,a][m>>2&1]*150);rt((m%4*5%9-3)*30);m>>=3
 home()

The magic number stores every combination of turtle forward and turn command in three bits:

  • the highest bit says whether to use fd(a) or fd(1-a)
  • the lower two select a right turn by a computation similar to that of Arnauld

The double forward motion would break that rhythm. To avoid that, the drawing is started at the point immediately after, and as the final move it is implemented with home().

enter image description here

\$\endgroup\$
2
\$\begingroup\$

R, 111 100 97 bytes

function(p,t=utf8ToInt("GEUSKMYSKMDYSG"),u=t%%4-2,`?`=cumsum)plot(?((u>0)-u*p)*1i^?t%%7/3-1,,"l")

Try it at rdrr.io

'Roll-your-own' turtle-graphics-like approach using complex numbers: less than half the length of the TurtleGraphics-package approach below.

How? We use the code M=LA, E=RA, S=RB, U=SA, Y=TA, G=SB, K=TB, D=TAA. The Utf8 codepoints (t) modulo-3 minus 1 (%%4-2) then give -1, -2 or 1 to indicate step-lengths of p,2p or 1-p, decoded using (u>0)-u*p. The Utf8 codepoints modulo-7, divided by 3, minus 1 give -1, -2/3, 2/3 and 1 corresponding to the powers of i to turn the correct number of degrees.
We then just take the cumulative sum and plot lines joining all the points on the complex plane.


R + TurtleGraphics, 256 254 bytes

function(p,f="forward(x",g="left(x",`+`=function(i,j)sub("x",j*10,i))eval(parse(t=paste("turtle",c("init(",c(f+p,f+(1-p),g+9,g+27,g+6,g+30)[c(1,5,1,4,2,5,2,4,1,6,1,3,w<-c(2,6,2),4,1,6,1,3,w,w,4)],"hide()"),sep="_",collapse=");")))
library(TurtleGraphics)

Try it at rdrr.io*

*The rdrr.io output isn't perfect, but you can scroll to the bottom to see the image of the tile. On my local installation, the output of gkms(0.6) is this:

enter image description here

\$\endgroup\$
2
\$\begingroup\$

LOGO, 74 73 72 bytes

Answering 3 months after the original post, but the shortest answer so far.

online interpreter at https://www.calormen.com/jslogo/

TO h :p repeat 14[fd(:p-(#%4%3>0))*200rt(3-#%2)*30*-1^(1149/2^#%2>1)]end

clear screen and call the function by adding the following below the function declaration:

cs
h 0.634

use ht and st to hide and show the turtle.

LOGO is an obvious choice for this challenge, but has some issues. Firstly, the iteration number (available in #) is 1-indexed. Secondly, arithmetic is done in real numbers - hence of use of the > to truncate an expression to 0 or 1, as the int and logic operators are rather verbose.

An interesting feature is use of sidelength expressions p and p-1. The negative sidelength p-1 instead of 1-p means that these sides get drawn with the turtle moving backwards. As each change of sidelength occurs at a 90 degree rotation, this can be compensated for by performing the 90 degree rotations in the opposite direction.

The shape is condidered to have 14 sides with one 0 deg vertex, seven 60 deg vertices and six 90 deg vertices. We start at the 0 deg vertex facing in a northward direction, so the shape is rotated 60 degrees anticlockwise from the orientation in the question.

The rotations alternate between 60 deg and 90 deg at each turn, and the length expressions alternate between p-1 and p at every second turn. We start with the turtle facing north and go south (backwards) -(p-1) then southwest -(p-1) leaving the turtle facing northeast after moving backwards in a generally clockwise direction. To continue moving in a clockwise sense we now turn the turtle 90 degrees LEFT (northwest) and continue in a forward direction by distance p.

We follow the pattern in the question (shifted so that the 0 deg rotation occurs at the beginning/end) with the following substitution to encode the direction of rotation:

S=1 T=0 L=0 R=1
BTBR ASAR BSBR ATAL BTBR ATAL BTB
 0 1  1 1  1 1  0 0  0 1  0 0  0

This in reverse gives the constant 1000111110 to which we append an extra digit 1 giving 10001111101=1149, as the fact that # is 1-indexed means we start by dividing by 2 on the first iteration.

The expression 1149/2^# always gives a noninteger when taken mod 2 because the real arithmetic does not discard fractional digits. Hence we can test for a 1 bit using >1 (strictly greater than 1.)

Commented code

TO h :p 
  repeat 14[                       ;iterate through sides #=1 through #=14 
    fd(:p-(#%4%3>0))*200           ;forward p if #%4 = 0 or 3, back 1-p if #%4 = 1 or 2. Scale factor 200
    rt(3-#%2)*30*-1^(1149/2^#%2>1) ;turn 90 if # even, 60 if # odd. direction given by -1^(0 or 1)
  ]                                ;decode the direction in binary from constant 1149 by dividing by 2^# and taking mod 2
end       
\$\endgroup\$
1
\$\begingroup\$

Desmos, 168 bytes

n=[1...14]
m=\cos(1.6n)+2
s(x)=\sum^n_{i=1}x[i]
a=s(\frac\pi{[.5,2,-2,3,2,3,-2,3,2,-3,2,-3,2,3]})
f(p)=\operatorname{polygon}(s([1-p,p][m]\cos(a)),s([1-p,p][m]\sin(a)))

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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