^{Ceci est la version ASCII de ce défi . Le poste initial a été séparé par demande par Martin Ender}

introduction

Semblable à la séquence de Fibonacci, la séquence de Padovan ( OEIS A000931 ) est une séquence de nombres qui est produite en ajoutant des termes précédents dans la séquence. Les valeurs initiales sont définies comme:

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

Les 0e, 1er et 2e termes sont tous 1. La relation de récurrence est indiquée ci-dessous:

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

Ainsi, il donne la séquence suivante:

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

L'utilisation de ces nombres comme longueurs latérales de triangles équilatéraux produit une belle spirale lorsque vous les placez tous ensemble, un peu comme la spirale de Fibonacci:

^{Image reproduite avec l' aimable autorisation de Wikipedia}

Tâche

Votre tâche consiste à écrire un programme qui recrée cette spirale par l'art ASCII, avec une entrée correspondant à quel terme. Puisqu'un triangle de longueur latérale 1 (1 caractère) est impossible à représenter correctement en ASCII, les longueurs latérales ont été dilatées d'un facteur 2. Ainsi, le triangle de longueur latérale 1 est en fait représenté comme suit:

 /\
/__\

Ainsi, par exemple, si l'entrée était 5 (le 5ème terme), la sortie devrait être:

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

Les 5 premiers termes étaient 1, 1, 1, 2, 2, donc le triangle avait des longueurs latérales 2, 2, 2, 4, 4 en raison de la dilatation. Un autre exemple pour l'entrée 8:

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

Règles

• Vous devez imprimer le résultat et l'entrée doit être un entier correspondant au numéro du terme
• Les retours à la ligne de fin et de début sont autorisés, les espaces de fin après les lignes sont également autorisés
• Votre soumission doit être en mesure de traiter au moins jusqu'au 10e trimestre (9)
• Votre soumission doit être un programme ou une fonction complète qui accepte les données et imprime le résultat
• Les rotations de la sortie sont autorisées, par multiples de 60 degrés, mais la taille des triangles doit rester la même, ainsi que la représentation
• Aller dans le sens antihoraire est également autorisé
• Les failles standard sont interdites

Vous pouvez supposer que l'entrée sera> 0 et que le format correct de l'entrée sera donné.

Notation

Il s'agit de code-golf , donc le code le plus court en octets l'emporte. Bonne année à tous!

Befunge, 871 836 798 octets

&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

Essayez-le en ligne!

Comme c'est souvent le cas avec Befunge, l'astuce consiste à trouver un algorithme qui nous permet de rendre le motif de haut en bas, car il n'est tout simplement pas possible de le rendre en mémoire d'abord avec l'espace limité disponible.

La façon dont cela fonctionne consiste à construire d'abord une structure de données simple représentant les bords nécessaires pour dessiner la spirale. La deuxième étape analyse ensuite cette structure de haut en bas, rendant les fragments de bord requis pour chaque ligne de sortie.

En utilisant cette technique, nous pouvons prendre en charge jusqu'à n = 15 dans l'implémentation de référence avant de commencer à avoir un problème de débordement dans les cellules de mémoire 8 bits. Les interprètes avec une plus grande taille de cellule doivent pouvoir prendre en charge jusqu'à n = 25 avant de manquer de mémoire.

aller, 768 octets

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]))}
}

Ce n'est bien sûr pas optimal, mais ce n'est pas un mauvais début. Je sais que c'est probablement un peu simple pour les normes de golf, mais c'était amusant et j'espère que ça ne le dérange pas si je laisse quelques notes à moi-même.

Comment ça marche

Fondamentalement, je simule une «tortue de dessin» comme dans LOGO sur une grille de pixels ASCII, mais la tortue ne peut effectuer que ces trois commandes:

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 \

Maintenant, pour chaque triangle, je vais comme ceci, où P est 2x le nième nombre Padovan:

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

Le quatrième «fd» signifie que je retrace le premier côté de chaque triangle. Cela permet de revenir à un joli point de départ pour le prochain triangle. Le demi-virage à droite garantit que le prochain triangle sera dans la bonne orientation.

Pour jouer à la tortue, je stocke 5 variables d'état dans le tableau 态: position x, position y, vitesse x, vitesse y et «rune de dessin». À chaque image d'animation, x + = vitesse x, y + = vitesse y et la rune est dessinée.

Ensuite, j'ai mis en place la table 表 qui indique comment effectuer réellement le virage. Le code de tour est délicat en raison de la façon dont fonctionne l'art ASCII. Ce n'est pas un mouvement simple comme sur un affichage en pixels. La direction de la tortue, déterminée par la vitesse x et y, détermine les changements nécessaires pour que le virage soit correct.

Pour tourner, il examine la vitesse actuelle x et y et les combine en un 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

Cet index est utilisé pour rechercher un ensemble de 5 valeurs dans le tableau 表. Ces 5 valeurs du tableau 表 sont ensuite ajoutées à chacune des 5 variables de l'état 态. La tortue est ensuite efficacement retournée et prête pour le prochain «fd».

Pour rth, la moitié du virage à droite, il y a une section séparée du tableau 表. Il est compensé par 7 * 5, ou 35, entrées de la première table dans 表.

Enfin, j'ai fait un encodage simple des entiers de la table dans une chaîne ascii.

Je sais que je pourrais "économiser des octets" en supprimant le Hanzi mais comme je l'ai dit, ce n'est pas optimal et il y a plus de golf possible ... Je les supprimerai quand il n'y aura pas d'autre optimisation possible. Ces Hanzi ont en fait un sens vaguement basé sur leur signification réelle, et même si je ne connais pas le chinois, cela m'aide à penser au programme.

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

Pour tester le code, vous aurez besoin d'un fichier golang complet, avec cet en-tête

package main
import "fmt"

et ce pied de page

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

Merci