34
\$\begingroup\$

Introduction

Similar to the Fibonacci Sequence, the Padovan Sequence (OEIS A000931) is a sequence of numbers that is produced by adding previous terms in the sequence. The initial values are defined as:

P(0) = P(1) = P(2) = 1

The 0th, 1st, and 2nd terms are all 1. The recurrence relation is stated below:

P(n) = P(n - 2) + P(n - 3)

Thus, it yields the following sequence:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, ...

Using these numbers as side lengths of equilateral triangles yields a nice spiral when you place them all together, much like the Fibonacci Spiral:

enter image description here

Image courtesy of Wikipedia


Task

Your task is to write a program that recreates this spiral by graphical output, with input corresponding to which term.

Rules

  • Your submission must be able to handle at least up to the 10th term (9)
  • Your submission must be a full program or function that takes input and displays a graphical result (either outputs an image or graphs, etc)
  • You must show proof of your graphical output in your submission
  • Rotations of the output are allowed, in 60 degree multiples, with the same representation
  • Going counter-clockwise is also allowed
  • Standard loopholes are forbidden

You may assume that input will be >0 and that correct format of input will be given.

Scoring

This is , so the shortest code in bytes wins. Happy New Years everyone!

\$\endgroup\$
  • \$\begingroup\$ Is trailing space after lines allowed? \$\endgroup\$ – Pavel Jan 1 '17 at 2:37
  • \$\begingroup\$ @Pavel Yes. Let me add that \$\endgroup\$ – Andrew Li Jan 1 '17 at 2:38
  • \$\begingroup\$ Does the output have to be identical to the example or are reflections and rotations (multiples of 60 degrees) allowed? \$\endgroup\$ – Level River St Jan 1 '17 at 3:28
  • \$\begingroup\$ @LevelRiverSt I would allow that. Let me clarify that in the post. \$\endgroup\$ – Andrew Li Jan 1 '17 at 3:30
  • 3
    \$\begingroup\$ Not a fan of allowing both ASCII art and graphical output in the same challenge. They're very very different tasks, and mixing them together makes answers solving the two different possibilities completely incomparable. It would be better to have two separate challenges, one for ASCII art and one for graphical output. \$\endgroup\$ – Martin Ender Jan 1 '17 at 22:58
12
\$\begingroup\$

Mathematica, 119 108 bytes

Thanks to Martin Ender for saving 11 bytes!

±n_:=If[n<4,1,±(n-2)+±(n-3)];Graphics@Line@ReIm@Accumulate@Flatten@{0,z=I^(2/3),±# z^(#+{2,4,1})&~Array~#}&@

Unnamed function taking a positive integer argument (1-indexed) and returning graphics output. Example output for the input 16:

enter image description here

Developed simulataneously with flawr's Matlab answer but with many similarities in design—even including the definition I^(2/3) for the sixth root of unity! Easier-to-read version:

1  (±n_:=If[n<4,1,±(n-2)+±(n-3)];
2   Graphics@Line@ReIm@
3   Accumulate@Flatten@
4   {0,z=I^(2/3),±# z^(#+{2,4,1})&~Array~#}
5  ])&

Line 1 defines the Padovan sequence ±n = P(n). Line 4 creates a nested array of complex numbers, defining z along the way; the last part ±# z^(#+{2,4,1})&~Array~# generates many triples, each of which corresponds to the vectors we need to draw to complete the corresponding triangle (the ±# controls the length while the z^(#+{2,4,1}) controls the directions). Line 3 gets rid of the list nesting and then calculates running totals of the complex numbers, to convert from vectors to pure coordinates; line 2 then converts complex numbers to ordered pairs of real numbers, and outputs the corresponding polygonal line.

\$\endgroup\$
  • 1
    \$\begingroup\$ nevermind that part was just me being stupid. \$\endgroup\$ – Martin Ender Mar 7 '17 at 22:44
9
\$\begingroup\$

Matlab, 202 190 bytes

N=input('');e=i^(2/3);f=1/e;s=[0,e,1,f,-e,e-2];l=[1,1,1,2];M=N+9;T=[l,2:M-3;2:M+1;3:M+2];for k=5:N;l(k)=l(k-2)+l(k-3);s(k+2)=s(k+1)+e*l(k);e=e*f;end;T=[T;T(1,:)];plot(s(T(:,1:N)));axis equal

Output for N=19 (1-based indexing):

enter image description here

Explanation

The rough idea is basically working with complex numbers. Then the edges of the triangles point always in the direction of a sixth root of unity.

N=input('');                         % Fetch input
e=i^(2/3);                           % 6th root of unity
f=1/e;                               %  "
s=[0,e,1,f,-e,e-2];                  % "s" is a list of vertices in the order as the spiral is defined
l=[1,1,1,2];                         % "l" is a list of edge-lengths of the triangles
for k=5:N;                           % if we need more values in "l"/"s" we calculate those
    l(k)=l(k-2)+l(k-3);
    s(k+2)=s(k+1)+e*l(k);
    e=e*f;
end;
M=N+9;
T=[[1,1,1,2,2:M-3];2:M+1;3:M+2]';    % this matrix describes which vertices from s are needed for each triangle (the cannonical way how meshes of triangles are stored)
trimesh(T(1:N,:),real(s),imag(s));   % plotting the mesh, according to "T"
axis equal
\$\endgroup\$
  • \$\begingroup\$ Nice job! Is there any possibility of an explanation? \$\endgroup\$ – Andrew Li Jan 1 '17 at 22:24
  • \$\begingroup\$ explanation added! \$\endgroup\$ – flawr Jan 1 '17 at 22:35
  • \$\begingroup\$ really like the use of complex numbers here. \$\endgroup\$ – don bright Mar 8 '17 at 5:12
7
\$\begingroup\$

PHP + SVG , 738 Bytes

<?php
$a=[1,1,1];
for($i=0;$i<99;)$a[]=$a[$i]+$a[++$i];
$d=$e=$f=$g=$x=$y=0;
$c=[333,999];
$z="";
foreach($a as$k=>$v){
if($k==$_GET['n'])break;
$h=$v/2*sqrt(3);
if($k%6<1){$r=$x+$v/2;$s=$y+$h;$t=$r-$v;$u=$s;}
if($k%6==1){$r=$x-$v/2;$s=$y+$h;$t=$x-$v;$u=$y;}
if($k%6==2){$r=$x-$v;$s=$y;$t=$r+$v/2;$u=$y-$h;}
if($k%6==3){$r=$x-$v/2;$s=$y-$h;$t=$r+$v;$u=$s;}
if($k%6==4){$r=$x+$v/2;$s=$y-$h;$t=$r+$v/2;$u=$y;}
if($k%6>4){$r=$x+$v;$s=$y;$t=$r-$v/2;$u=$y+$h;}
$d=min([$d,$r,$t]);
$e=max([$e,$r,$t]);
$f=min([$f,$s,$u]);
$g=max([$g,$s,$u]); 
$p="M$x,{$y}L$r,{$s}L$t,{$u}Z";
$z.="<path d=$p fill=#{$c[$k%2]} />";
$x=$r;
$y=$s;
}
?>
<svg viewBox=<?="$d,$f,".($e-$d).",".($g-$f)?> width=100% height=100%>
<?=$z?>
</svg>

Output for 16

<svg viewBox=-53,-12.124355652982,75.5,42.435244785437 width=100% height=100%>
<path d=M0,0L0.5,0.86602540378444L-0.5,0.86602540378444Z fill=#333 /><path d=M0.5,0.86602540378444L0,1.7320508075689L-0.5,0.86602540378444Z fill=#999 /><path d=M0,1.7320508075689L-1,1.7320508075689L-0.5,0.86602540378444Z fill=#333 /><path d=M-1,1.7320508075689L-2,0L0,0Z fill=#999 /><path d=M-2,0L-1,-1.7320508075689L0,0Z fill=#333 /><path d=M-1,-1.7320508075689L2,-1.7320508075689L0.5,0.86602540378444Z fill=#999 /><path d=M2,-1.7320508075689L4,1.7320508075689L0,1.7320508075689Z fill=#333 /><path d=M4,1.7320508075689L1.5,6.0621778264911L-1,1.7320508075689Z fill=#999 /><path d=M1.5,6.0621778264911L-5.5,6.0621778264911L-2,-8.8817841970013E-16Z fill=#333 /><path d=M-5.5,6.0621778264911L-10,-1.7320508075689L-1,-1.7320508075689Z fill=#999 /><path d=M-10,-1.7320508075689L-4,-12.124355652982L2,-1.7320508075689Z fill=#333 /><path d=M-4,-12.124355652982L12,-12.124355652982L4,1.7320508075689Z fill=#999 /><path d=M12,-12.124355652982L22.5,6.0621778264911L1.5,6.0621778264911Z fill=#333 /><path d=M22.5,6.0621778264911L8.5,30.310889132455L-5.5,6.0621778264911Z fill=#999 /><path d=M8.5,30.310889132455L-28.5,30.310889132455L-10,-1.7320508075689Z fill=#333 /><path d=M-28.5,30.310889132455L-53,-12.124355652982L-4,-12.124355652982Z fill=#999 /></svg>

\$\endgroup\$
  • 1
    \$\begingroup\$ Two small things to golf: $k%6==0 can be $k%6<1 and $k%6==5 can be $k%6>4. \$\endgroup\$ – Kevin Cruijssen Mar 7 '17 at 16:16
4
\$\begingroup\$

Python 3, 280, 262 bytes

18 bytes saved thanks to ovs

Golfed:

import turtle
P=lambda n:n<4or P(n-3)+P(n-2)
N=int(input())
M=9
t=turtle.Turtle()
Q=range
R=t.right
L=t.left
F=t.forward
S=[P(x)*M for x in Q(N,0,-1)]
A=S[0]
F(A)
R(120)
F(A)
R(120)
F(A)
L(120)
i=1
while i<N:
 A=S[i]
 for j in Q(3):F(A);L(120)
 F(A)
 L(60)
 i+=1

Same thing with some comments:

import turtle

# P(n) returns nth term in the sequence
P=lambda n:n<4or P(n-3)+P(n-2)

# M: scales the triangle side-length
M=9
# N: show triangles from 1 to (and including) N from sequence
N=int(input())
t=turtle.Turtle()
Q=range
R=t.right # R(a) -> turn right "a" degrees
L=t.left  # L(a) -> turn left "a" degrees
F=t.forward # F(l) -> move forward "l" units

# S: M*P(N),M*P(N-1), ... M*P(1)
S=[P(x)*M for x in Q(N,0,-1)]

# draw the largest triangle
A=S[0]
F(A)
R(120)
F(A)
R(120)
F(A)
L(120)
i=1

# draw the next N-1 smaller triangles
while i<N:
 A=S[i]
 for j in Q(3):F(A);L(120)
 F(A)
 L(60)
 i+=1

Screenshot for N=9:

N=9

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

dwitter 151

s=(n)=>{P=(N)=>N<3||P(N-3)+P(N-2)
for(a=i=0,X=Y=500,x.moveTo(X,Y);i<n*4;i++)k=9*P(i/4),x.lineTo(X+=C(a)
*k,Y+=S(a)*k),x.stroke(),a+=i%4>2?1.047:2.094}

can be tested on http://dwitter.net (use fullscreen)

enter image description here

basic idea is logo turtle, golfed. stole the P() func from above!

i imagine more could be golfed by recursion but this is not bad.

\$\endgroup\$
1
\$\begingroup\$

LOGO, 119 bytes

to s:n
make"x 10
make"y:x
make"z:y
bk:z
repeat:n[lt 60
fw:z
rt 120
fw:z
bk:z
make"w:y+:z
make"z:y
make"y:x
make"x:w]end

To use, do something like this:

reset
lt 150
s 12

Sample output (can't embed because it's not HTTPS and it failed to upload to imgur)

\$\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.