22
\$\begingroup\$

This is the ASCII version of this challenge. The initial post was separated per request by Martin Ender

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 ASCII art, with input corresponding to which term. Since a triangle of side length 1 (1 character) is impossible to represent nicely in ASCII, the side lengths have been dilated by a factor of 2. Thus, the triangle of side length 1 is actually represented like so:

 /\
/__\

So, for example, if the input was 5 (the 5th term), the output should be:

   /\
  /  \
 /    \
/______\
\      /\
 \    /__\ 
  \  /\  /
   \/__\/

The first 5 terms were 1, 1, 1, 2, 2, so the triangle had side lengths 2, 2, 2, 4, 4 due to dilation. Another example for input 8:

     __________
   /\          /\
  /  \        /  \
 /    \      /    \
/______\    /      \
\      /\  /        \
 \    /__\/          \
  \  /\  /            \
   \/__\/______________\
    \                  /
     \                /
      \              /
       \            /
        \          /
         \        /
          \      /
           \    /
            \  /
             \/

Rules

  • You must print the result, and input must be an integer corresponding to term number
  • Trailing and leading newlines are allowed, trailing spaces after lines are allowed also
  • 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 prints the result
  • Rotations of the output are allowed, in 60 degree multiples, but the size of the triangles must remain the same, along with the 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\$
  • 1
    \$\begingroup\$ my language Turtlèd can take base 10 input, and process it fine, but this challenge would be so much easier if it took input as unary. would that be allowed? \$\endgroup\$ – Destructible Lemon Jan 1 '17 at 23:42
  • 1
    \$\begingroup\$ @DestructibleWatermelon Yes. The input just has to be integer, in some kind of form. \$\endgroup\$ – Andrew Li Jan 1 '17 at 23:44
  • \$\begingroup\$ cool. I'll start working on it now \$\endgroup\$ – Destructible Lemon Jan 1 '17 at 23:46
  • 3
    \$\begingroup\$ wait actually it's still really hard \$\endgroup\$ – Destructible Lemon Jan 1 '17 at 23:58
13
\$\begingroup\$

Befunge, 871 836 798 bytes

&00p45*:10p20p030p240p050p060p9010gp9110gp1910gp1-91+10gpv
<v-g03+g06*2g041g055_v#!:%6:p06p05+p04g05g06:g04<p*54+292<
->10g:1\g3+:70p110gv >:5- #v_550g:01-\2*40g+1-30g
/\110:\-g03:\1:g055 _v#!-4:<vp01:-1g01-g03-1\-
^1<v07+1:g07< p08p < >:1-#v_550g:01-\40g+60g+1-30g-50g>v
 _0>p80gp:5-|v1\+66\:p\0\9:$<:p02:+1g02-g03+g06-\g04\1:<
0v|-g00:+1$$<>\p907^>p:!7v>3-#v_550g:30g+:30p1\0\-
1>10g+::0\g3-:70p\0^^07<v<>50#<g::30g+:30p-1-01-\
v >\$0gg> :1+10gg1- #v_^>0g10gg*+\:!2*-70g2+10gv>:#->#,"_"$#1_:1#<p
+1+g03$_^#`gg011+3:+3<g07\+*2+*`0:-\gg01+5g07:g<>1#,-#*:#8>#4_$#:^#
>55+,p30g40p10gg10g1>#v_
#v:#p0$#8_:$#<g!#@_0^ >
 >>:180gg`>>#|_:2+80gg:!v
3+^g\0p08:<vgg08+2::+3<$_100p1-v>g,\80gg+\80gp:2+90g:!01p\80gp
!#^_80g:1+^>\180gg`+!#^_20g80g`
5*g10!g09p04-1-\0\+g04:gg08:p09<^3`0:gg08+1:::$$_1#!-#\\:,#\<g

Try it online!

As is often the case with Befunge, the trick is coming up with an algorithm that allows us to render the pattern from top to bottom, since it's just not feasible to render it into memory first with the limited space available.

The way this works is by first building up a simple data structure representing the edges needed to draw the spiral. The second stage then parses that structure from top to bottom, rendering the edge fragments required for each line of output.

Using this technique, we can support up to n=15 in the reference implementation before we start having overflow issue in the 8-bit memory cells. Interpreters with a larger cell size should be able to support up to n=25 before running out of the memory.

\$\endgroup\$
  • \$\begingroup\$ that is very impressive... but do you find you are able to read these programs? lol to me it looks so random. how does it build the data structure? what kind of data structure does it use? thanks! \$\endgroup\$ – don bright Mar 5 '17 at 23:33
1
\$\begingroup\$

go, 768 bytes

func 卷(n int){
    数:=0
    p:=[]int{1,1,1}
    for i:=3;i<n;i++ {p=append(p,p[i-2]+p[i-3])}
    宽:=p[len(p)-1]*10+10
    素:=make([]int,宽*宽)
    for 数=range 素 {素[数]=32}
    for i:=0;i<数;i+=宽 {素[i]=10}
    态:=[]int{1,1,宽/2,宽/2,92}
    表:=[70]int{}
    s:="SRSQTSPQQ!QOQP~QQQQQQSQR~ORQR!OPOPTSQRQ$QPPQNQPPPXQQQQQQRRQXQRRRNOQPQ$"
    for i:=range s {表[i]=int(s[i])-33-48}
    表[49],表[59]=48,48
    for i:=0;i<4*n;i++ {
        梴:=p[i/4]*2
        if 态[1]==0 {梴=梴*2-2}
        for k:=0;k<梴;k++ {
            址:=(态[2]+态[3]*宽)%len(素)
            if 素[址]==32 {素[址]=态[4]}
            态[2]+=态[0]
            态[3]+=态[1]
        }
        数=((态[0]+1)*2+态[1]+1)*5
        if i%4>2 {数+=35}
        for k:=0;k<5;k++ {态[k]+=表[数+k]}
    }
    for i:=0;i<宽*宽;i++ {fmt.Printf("%c",rune(素[i]))}
}

This is of course not optimal, but it's not a bad start. I know it's probably a bit simple for the golfing standards, but it was fun and I hope it's not minded if I leave some notes to future self.

How it works

Basically I simulate a 'drawing turtle' like in LOGO on an ASCII pixel grid, but the turtle can only do these three commands:

rt   - right turn, turn 120 degrees right (1/3 of a Turn)
rth  - right turn half, turn  60 degrees right (1/6 of a Turn)
fd n - forward, go forward n steps, drawing a trail of _, /, or \

Now for each triangle, I go like this, where P is 2x the nth Padovan number:

fd P
rt
fd P
rt 
fd P
rt
fd P
rth

The fourth 'fd' means I am re-tracing the first side of each triangle. This helps get back to a nice starting point for the next triangle. The half-right-turn makes sure that the next triangle will be in the proper orientation.


To golf the turtle I store 5 state variables in array 态 : x position, y position, x velocity, y velocity, and 'drawing rune'. At each animation frame, x+= x velocity, y += y velocity, and the rune is drawn.

Then I set up table 表 which tells how to actually perform the turn. The turn code is tricky because of the way ASCII art works. It is not a straightforward movement like on a pixel display. The direction of the turtle, determined by x and y velocity, determine the changes necessary to get the turn to look proper.

To turn, it looks at the current x and y velocity, and combines them into an index.

xv = x velocity, yv = y velocity. 
i.e. a turtle facing down and to the right has 
xv of 1, and yv of 1. It can only face 6 
different directions. Formula is (xv+1)*2+yv+1

xv  yv    index
-1  -1    0
-1   0    1
-1   1    2
 1  -1    4
 1   0    5
 1   1    6

This index is used to lookup a set of 5 values in table 表. Those 5 values in table 表 are then added to each of the 5 variables in state 态. The turtle is then effectively turned, and ready for the next 'fd'.

For rth, half the right turn, there is a separate section of the 表 table. It is offset by 7*5, or 35, entries from the first table in 表.

Lastly I did some simple encoding of the table's integers into an ascii string.

I know I could 'save bytes' by removing the Hanzi but like I said, this is not optimal and there is more golfing possible... I will remove them when there is no other possible optimization. Those Hanzi actually have meaning loosely based on their actual meaning, and even though I don't know Chinese, it helps me think about the program.

数  index number
宽  screen width
素  pixel data
梴  length of side of triangle
态  current state
址  address of pixel
表  state transition table

To test the code you will need full golang file, with this header

package main
import "fmt"

and this footer

func main ()  {
    for i := 0; i<15; i++ {
       卷(i)
    }
}

thanks

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