Espiral de Fibonacci

37

Seu objetivo é gerar uma espiral de Fibonacci com números.

Amostra

Exemplo de entrada / saída

1 -> 1

2 -> 1 1

3 -> 1 1
     2 2
     2 2

6 -> 8 8 8 8 8 8 8 8 5 5 5 5 5
     8 8 8 8 8 8 8 8 5 5 5 5 5
     8 8 8 8 8 8 8 8 5 5 5 5 5
     8 8 8 8 8 8 8 8 5 5 5 5 5
     8 8 8 8 8 8 8 8 5 5 5 5 5
     8 8 8 8 8 8 8 8 1 1 3 3 3
     8 8 8 8 8 8 8 8 2 2 3 3 3
     8 8 8 8 8 8 8 8 2 2 3 3 3

Entrada de 9

Entrada A entrada pode ser obtida através de STDIN ou argumento de função. Será um número único

Saída A saída pode ser de STDOUT ou o valor de retorno de uma função. Deve ser uma única string.

Espaço em branco extra no final da linha não é permitido. A saída pode conter dígitos, linhas de alimentação (novas linhas) e espaços.

A orientação não importa, isso significa rotações e reflexões. Desde que siga um padrão espiral de Fibonacci válido.

Números com diferentes quantidades de dígitos (por exemplo, 1 e 13) devem estar alinhados à direita. Pode ser necessário adicionar um espaço no início de uma linha para que tudo possa se alinhar.

1   1                          1   1
100 100  should actually be  100 100

Você pode ver um exemplo aqui


Este é o pelo que o código mais curto em bytes vence!

Downgoat
fonte
4
Desafio relacionado (e um relógio muito legal) #
Sp3000
Numbers with different amounts of digits (e.g. 1 and 13) should be aligned to the left side of the digit a space may need to be added to the very beginning of a line so everything can line up.Parece que pode ser mais claro em duas frases.
Trichoplax
Parece que, nos exemplos, você deseja alinhar o dígito mais à direita de cada número, mas "alinhado ao lado esquerdo do dígito" soa como o oposto.
Trichoplax
Você pode esclarecer "o espaço em branco circundante não é permitido"? Em particular - o espaço em branco inicial ou final nas linhas é aceitável?
MtnViewMark
O Matlab imprime a saída em stdout por padrão. É aceitável ter uma saída do tipo numérico (em oposição à saída do tipo string) que é automaticamente impressa no stdout?
Luis Mendo

Respostas:

15

APL, 23

{a,⍴⍨2⍴⊃⍴a←⌽⍉⍵}⍣(⎕-1)⍪1

Explicação:

⍪1               this creates a 1x1 matrix containing just 1
{..}⍣(⎕-1)     the power operator (⍣) repeats the function {} user input - 1 times
a,⍴⍨2⍴⊃⍴a←⌽⍉⍵   the function being iterated rotates the matrix and appends the next matrix to it.

Experimente em tryapl.org

Moris Zucca
fonte
11
Se você pesquisar aqui, muitos já tiveram sua dúvida antes. Aqui está, por exemplo, a resposta da @Tobia: * O Dyalog APL suporta um conjunto de caracteres herdado que possui os símbolos da APL mapeados para os valores superiores de 128 bytes. Portanto, um programa APL que usa apenas caracteres ASCII e símbolos APL pode ser considerado como bytes == chars.
Moris Zucca
Ok, então, vou retirar meu comentário.
gar
11
@MorisZucca Observe, porém, que alguns caracteres (como ou ) estão ausentes desse conjunto de caracteres e não podem ser usados ​​quando você deseja evocar essa regra.
FUZxxl
11
É verdade que "key" e "rank" são implementações mais recentes e existem de fato apenas na versão Unicode do interpretador Dyalog que eu uso. A versão Classic deve usar o equivalente de comando. O mesmo se aplica a ⍠ (⎕OPT) também, por exemplo. Portanto, geralmente penso que, se eu puder escrever na versão Dyalog Classic, é seguro dizer que é 1 byte por caractere. Corrija-me se eu estiver errado. E obrigado pelo comentário.
Moris Zucca
8

Matlab, 84 bytes

Uma função é usada. A saída está em stdout.

function f(N)
s=0;t=1;y=1;for n=2:N
u=s+t;s=t;t=u;y=[rot90(y) t*ones(t)];end;disp(y)

Exemplos:

>> f(1)
     1
>> f(2)
     1     1
>> f(3)
     1     2     2
     1     2     2
>> f(6)
     5     5     5     5     5     8     8     8     8     8     8     8     8
     5     5     5     5     5     8     8     8     8     8     8     8     8
     5     5     5     5     5     8     8     8     8     8     8     8     8
     5     5     5     5     5     8     8     8     8     8     8     8     8
     5     5     5     5     5     8     8     8     8     8     8     8     8
     3     3     3     1     1     8     8     8     8     8     8     8     8
     3     3     3     2     2     8     8     8     8     8     8     8     8
     3     3     3     2     2     8     8     8     8     8     8     8     8
>> f(7)
     8     8     8     8     8     8     8     8    13    13    13    13    13    13    13    13    13    13    13    13    13
     8     8     8     8     8     8     8     8    13    13    13    13    13    13    13    13    13    13    13    13    13
     8     8     8     8     8     8     8     8    13    13    13    13    13    13    13    13    13    13    13    13    13
     8     8     8     8     8     8     8     8    13    13    13    13    13    13    13    13    13    13    13    13    13
     8     8     8     8     8     8     8     8    13    13    13    13    13    13    13    13    13    13    13    13    13
     8     8     8     8     8     8     8     8    13    13    13    13    13    13    13    13    13    13    13    13    13
     8     8     8     8     8     8     8     8    13    13    13    13    13    13    13    13    13    13    13    13    13
     8     8     8     8     8     8     8     8    13    13    13    13    13    13    13    13    13    13    13    13    13
     5     5     5     5     5     1     2     2    13    13    13    13    13    13    13    13    13    13    13    13    13
     5     5     5     5     5     1     2     2    13    13    13    13    13    13    13    13    13    13    13    13    13
     5     5     5     5     5     3     3     3    13    13    13    13    13    13    13    13    13    13    13    13    13
     5     5     5     5     5     3     3     3    13    13    13    13    13    13    13    13    13    13    13    13    13
     5     5     5     5     5     3     3     3    13    13    13    13    13    13    13    13    13    13    13    13    13

Matlab, 78 bytes

function y=f(N)
s=0;t=1;y=1;for n=2:N
u=s+t;s=t;t=u;y=[rot90(y) t*ones(t)];end

O mesmo que acima, exceto que o recurso de um Matlab é explorado, ou seja, ele exibe automaticamente a saída da função (como uma string) no stdout. Isso evita a conversão em string na abordagem acima.

f(6)
ans =
     5     5     5     5     5     8     8     8     8     8     8     8     8
     5     5     5     5     5     8     8     8     8     8     8     8     8
     5     5     5     5     5     8     8     8     8     8     8     8     8
     5     5     5     5     5     8     8     8     8     8     8     8     8
     5     5     5     5     5     8     8     8     8     8     8     8     8
     3     3     3     1     1     8     8     8     8     8     8     8     8
     3     3     3     2     2     8     8     8     8     8     8     8     8
     3     3     3     2     2     8     8     8     8     8     8     8     8
Luis Mendo
fonte
contente de ver algumas soluções Matlab :-)
Hoki
@Hoki Thanks! :-)
Luis Mendo
7

Python 2, 121 bytes

a,b=0,1;L=[]
exec"a,b=b,a+b;L=zip(*L[::-1])+[[a]*a]*a;"*input()
for r in L:print" ".join("%*d"%(len(str(a)),x)for x in r)

As regras relaxadas sobre rotações tornam isso muito mais simples.

Não usei backticks no lugar str(a)daqui, porque não tenho certeza se temos mais espaços à esquerda do que o necessário, se chegarmos a longos períodos. Embora, mesmo se estivéssemos, o uso em asi seria mais curto de qualquer maneira.

Sp3000
fonte
7

Ruby, 243 242 236 233 222 170 130 bytes

s,l,r=0,1,[]
gets.to_i.times{s+=l
l=s-l
s.times{r<<[s]*s}
r=r.transpose.reverse}
r.map{|w|puts w.map{|c|"%#{s.to_s.size}s"%c}*" "}
Addison
fonte
11
Bom golfe! Você pode salvar alguns caracteres na linha 4, convertendo as t==valuecondições em t>value. Por exemplo,(t=x%4)>2?s.times{r<<[s]*s}:t>1?s.times{r.map!{|w|w.unshift s}}:t>0?s.times{r.unshift [s]*s}:r.map!{|w|w+=[s]*s}}
Cristian Lupascu
6

Python - 189 179 174

n=int(input())
f=[1,1]
while len(f)<n:f+=[f[-1]+f[-2]]
o=[[]]
for i in f:o=(list(zip(*o)))[::-1]+[[i]*i]*i
for x in o:print(' '.join(str(y).rjust(len(str(f[-1])))for y in x))
faubi
fonte
6

J, 36 bytes

1&(($~,~)@(1{$@]),.|:@|.@])&(,.1)@<:

Uso:

   (1&(($~,~)@(1{$@]),.|:@|.@])&(,.1)@<:) 6
8 8 8 8 8 8 8 8 5 5 5 5 5
8 8 8 8 8 8 8 8 5 5 5 5 5
8 8 8 8 8 8 8 8 5 5 5 5 5
8 8 8 8 8 8 8 8 5 5 5 5 5
8 8 8 8 8 8 8 8 5 5 5 5 5
8 8 8 8 8 8 8 8 1 1 3 3 3
8 8 8 8 8 8 8 8 2 2 3 3 3
8 8 8 8 8 8 8 8 2 2 3 3 3

Método:

A função gira o quadrado atual e adiciona o novo quadrado ao atual uma input-1vez. O tamanho do quadrado e os valores do elemento são reunidos a partir do tamanho do retângulo anterior.

Explicação do código:

1&(           loop
    ($~,~)      new square with size and elements
    @(1{$@])    with the size of the second dimension of the current rectangle
    ,.          attached to
    |:@|.@]     rotated current rectangle
)&(,.1)       starting the loop with matrix 1
@<:           looping input-1 times

Experimente online aqui.

randomra
fonte
6

Haskell, 183 176 171 163 bytes

import Data.List
s t=map((t>>[l t])++)t
e 1=[[1]];e n=s.reverse.transpose$e$n-1
f=g.e
g m=unlines$map(>>=((show$l m)#).show)m
a#b|l a<l b=b;a#b=a#(' ':b)
l=length

A função é f, que pega um número e retorna uma única string:

λ: putStr $ f 8
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21  5  5  5  5  5  8  8  8  8  8  8  8  8
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21  5  5  5  5  5  8  8  8  8  8  8  8  8
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21  5  5  5  5  5  8  8  8  8  8  8  8  8
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21  5  5  5  5  5  8  8  8  8  8  8  8  8
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21  5  5  5  5  5  8  8  8  8  8  8  8  8
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21  3  3  3  1  1  8  8  8  8  8  8  8  8
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21  3  3  3  2  2  8  8  8  8  8  8  8  8
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21  3  3  3  2  2  8  8  8  8  8  8  8  8
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 13 13 13 13 13 13 13 13 13 13 13 13 13
MtnViewMark
fonte
5

Pitão, 34 bytes

jbmsm.[hl`lhZ`k\ d=Zu+_CGmmlGGGQ]]

Surpreendentemente, mais da metade do código é impressão / preenchimento, em vez de gerar a matriz.

A geração da matriz é realmente simples, no entanto, consiste em uma transposição e reversão e adição de N linhas contendo N cópias de N, onde N é o número atual de linhas.

Exemplo de saída para 7:

  5  5  5  5  5  8  8  8  8  8  8  8  8
  5  5  5  5  5  8  8  8  8  8  8  8  8
  5  5  5  5  5  8  8  8  8  8  8  8  8
  5  5  5  5  5  8  8  8  8  8  8  8  8
  5  5  5  5  5  8  8  8  8  8  8  8  8
  3  3  3  1  1  8  8  8  8  8  8  8  8
  3  3  3  2  2  8  8  8  8  8  8  8  8
  3  3  3  2  2  8  8  8  8  8  8  8  8
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
 13 13 13 13 13 13 13 13 13 13 13 13 13
orlp
fonte
4

Perl, 289 277 257 bytes

@f=(0,1);push@f,$f[-1]+$f[-2]while(@f<=$ARGV[0]);$d=1+length$f[-1];shift@f;map{$v=$f[$_];$t=sprintf("%${d}d",$v)x$v;$_%4||map{unshift@s,$t}1..$v;$_%4==3&&map{$_.=$t}@s;$_%4==2&&map{push@s,$t}1..$v;$_%4==1&&map{$_=$t.$_}@s;}0..$#f;$\=$/;for(@s){s/^ //;print}
Ruth Franklin
fonte
4

K, 48 bytes

{{`0:1_',/'(1+#$|//x)$x}(x-1){+|x,\:t#t:#x}/,,1}

E em ação:

  {{`0:1_',/'(1+#$|//x)$x}(x-1){+|x,\:t#t:#x}/,,1}7
 8  8  8  8  8  8  8  8  5  5  5  5  5
 8  8  8  8  8  8  8  8  5  5  5  5  5
 8  8  8  8  8  8  8  8  5  5  5  5  5
 8  8  8  8  8  8  8  8  5  5  5  5  5
 8  8  8  8  8  8  8  8  5  5  5  5  5
 8  8  8  8  8  8  8  8  1  1  3  3  3
 8  8  8  8  8  8  8  8  2  2  3  3  3
 8  8  8  8  8  8  8  8  2  2  3  3  3
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 13 13 13 13 13 13

Pode ainda haver boas oportunidades para jogar golfe.

O programa consiste basicamente em duas partes - gerando a matriz concatenada e formatando-a para saída. O primeiro é bastante simples:

  {(x-1){+|x,\:t#t:#x}/,,1}5
(3 3 3 2 2
 3 3 3 2 2
 3 3 3 1 1
 5 5 5 5 5
 5 5 5 5 5
 5 5 5 5 5
 5 5 5 5 5
 5 5 5 5 5)

Começando com uma matriz 1x1 contendo 1, construa um vetor T de comprimento T onde T é o comprimento da matriz inicial na primeira dimensão ( t#t:#x) e anexe-o a cada linha da matriz original ( x,\:). Inverter e transpor o resultado ( +|) gira 90 graus. Fazemos isso N-1 vezes.

A formatação é bastante desajeitada, porque a abordagem natural de K para imprimir uma matriz não alinhará as colunas numéricas da maneira que precisamos:

{`0:1_',/'(1+#$|//x)$x}

A idéia básica é pegar o elemento máximo da matriz ( |//x), convertê-lo em uma string (unária $), pegar seu comprimento mais um ( 1+#) e depois formatar os elementos da matriz para as strings alinhadas à direita desse tamanho. Em seguida, para arrumar, junte essas strings ( ,/') e solte o espaço inicial resultante ( 1_').

JohnE
fonte
4

CJam, 48 bytes

1saali({z{W%}%_0=,__sa*a*+}*_W=W=,):U;{USe[}f%N*

Experimente online

A parte principal da geração do padrão parece razoavelmente direta. Gire o retângulo criado até o momento e adicione um quadrado de valores na parte inferior.

O código para preencher o resultado parece terrível, no entanto. Tentei várias combinações de operadores fe :para aplicar o preenchimento à lista aninhada, mas nada funcionou. Se alguém tiver sugestões melhores, será bem-vindo.

1s    First value. Using string for values so that we can pad them in the end.
aa    Wrap it twice. Data on stack will be a list of lists (list of lines).
li    Get input.
(     Decrement, since we seeded the list at n=1.
{     Loop over n.
  z     Transpose...
  {W%}% ... and reverse all lines, resulting in a 90 degree rotation.
  _0=,  Get length of line, which is the size of square we need to add.
  __    Create two copies of size.
  sa    Convert one size to string, and wrap it in array.
  *     Replicate it size times. This is one line.
  a     Wrap the line...
  *     ... and replicate it size times. The square of new values is done.
  +     Add the list of lines to the previous list of lines.
}*    End of loop over n.
_W=W= Get last value produced.
,)    Take its length, and increment it. This is the output field width.
:U;   Store the field width in variable, and pop it. This is ugly.
{     Start of block applied to all values.
  U     Field width stored in variable.
  S     Space.
  e[    Pad left.
}f%   End of block applied to all values.
N*    Join lines with newline.
Reto Koradi
fonte
A reversão de todas as linhas pode ser feita com Wf%. Além disso, você seria capaz de fazer algo assim {Se[}ff%em vez de :U;{USe[}f%para o preenchimento? (Que podem não funcionar como é, eu não posso pensar por ele agora.)
Esolanging Fruit
2

Pitão, 29 bytes

Vu+C_GmmlGGGQ\]Yjdm.\[l`lN`d\ N

Demonstração.

Se o preenchimento fosse livre / implícito, como no APL, ou a saída da matriz fosse permitida, isso seria 14 bytes:

u+C_GmmlGGGQ]Y
isaacg
fonte
2

Ruby, 129 bytes

Eu editei a outra resposta em ruby, mas minha alteração mais recente não está sendo aceita ou algo assim, então aqui está:

s,r=0,[[1]]
gets.to_i.times{s+=r[0][0]
r=(r+[[s]*s]*s).transpose.reverse}
r.map{|w|puts w.map{|c|"%#{r[0][s].to_s.size}s"%c}*' '}
user2251284
fonte
11
Bem-vindo ao PPCG! As melhorias no golfe geralmente são rejeitadas por aqui (se suas outras sugestões foram aceitas e devem ter sido uma supervisão), porque elas devem ser postadas nos comentários para o autor revisar. Consulte esta meta post para obter o raciocínio por trás dessa política.
Martin Ender
Obrigado pela informação, faz sentido. Comentar é o que eu teria feito originalmente, mas não tinha pontos de reputação suficientes para comentar, mas farei no futuro. Feliz golfe!
user2251284
1

ES6, 248 bytes

n=>(f=(n,o=n)=>Array(n).fill(o),g=n=>n<3?[f(n,1)]:(a=g(n-2)).reverse().concat(f(l=a[0].length,f(l))).map((e,i,a)=>f(a.length).concat(e.reverse())),a=g(n),s=' '.repeat(l=` ${a[0][0]}`.length),a.map(a=>a.map((e,i)=>(s+e).slice(!i-1)).join``).join`\n`)

Onde \nrepresenta um caractere literal de nova linha.

Irritantemente, a formatação ocupa uma grande parte do código.

fé uma função auxiliar que cria uma matriz preenchida. É usado principalmente para criar os quadrados preenchidos, mas também dobra facilmente para produzir os casos base para a recursão.

gé o principal grunhido. Ele gera recursivamente a última, mas uma solução, gira-a 180 graus e acrescenta os próximos dois quadrados.

Neil
fonte