fundo
O mosaico de Fibonacci é um mosaico da linha (1D) usando dois segmentos: um curto, S e um longo, L (a razão de comprimento é a proporção áurea, mas isso não é relevante para esse desafio). Para que um ladrilho usando esses dois protótipos seja realmente um ladrilho de Fibonacci, as seguintes condições devem ser cumpridas:
- A lado a lado não deve conter a subsequência SS .
- A lado a lado não deve conter a LLL subsequente .
- Se um novo mosaico for composto executando todas as seguintes substituições, o resultado ainda deverá ser um mosaico de Fibonacci:
- LL → S
- S → L
- L → (string vazia)
Vejamos alguns exemplos:
SLLSLLSLLSLS
Parece um bloco válido, porque não contém dois * S * s ou três * L * s, mas vamos executar a composição:
LSLSLSLL
Ainda parece bom, mas se compormos isso de novo, obtemos
LLLS
que não é um mosaico válido de Fibonacci. Portanto, as duas seqüências anteriores também não eram válidas.
Por outro lado, se começarmos com
LSLLSLSLLSLSLL
e componha isso repetidamente para seqüências mais curtas
LSLLSLLS
LSLSL
LL
S
todos os resultados são inclinações válidas de Fibonacci, porque nunca obtemos SS ou LLL em lugar algum nessas cadeias.
Para uma leitura mais aprofundada, há uma tese que usa esse ladrilho como uma simples analogia 1D às inclinações de Penrose.
O desafio
Escreva um programa ou função que, dado um número inteiro não negativo N , retorne todos os blocos de Fibonacci válidos na forma de cadeias contendo N caracteres (sendo S
ou L
).
Você pode receber informações via argumento de função, STDIN ou ARGV e retornar ou imprimir o resultado.
Isso é código de golfe, a resposta mais curta (em bytes) vence.
Exemplos
N Output
0 (an empty string)
1 S, L
2 SL, LS, LL
3 LSL, SLS, LLS, SLL
4 SLSL, SLLS, LSLS, LSLL, LLSL
5 LLSLL, LLSLS, LSLLS, LSLSL, SLLSL, SLSLL
...
8 LLSLLSLS, LLSLSLLS, LSLLSLLS, LSLLSLSL, LSLSLLSL, SLLSLLSL, SLLSLSLL, SLSLLSLL, SLSLLSLS
LSLSL
->LL
?Respostas:
CJam,
706259 bytesLê de STDIN. Experimente online.
Exemplo de execução
Como funciona
A idéia é empurrar todas as strings de L e S do comprimento adequado, aplicar sucessivamente a transformação a cada uma até o resultado ser uma string vazia, concatenar as seqüências de strings e procurar as substrings proibidas.
fonte
GolfScript (86 bytes)
Esta é uma abordagem inflacionária: ele começa com
L
eS
e expande-los usando as regrasLL -> SLS
,L -> S
,S -> LL
, e esquerda ou à direitaS
pode ter umL
adicionado no limite de palavra.Demonstração online
fonte
Haskell, 217
Explicação:
Eu defino 4 funções:
f
pega um número inteiro e retorna o resultadoreplicateM n [L,S]
cria todas as permutações possíveis de[L,S]
com o comprimenton
filter s ...
filtrará esta lista (de listas) com a funçãos
r
reduz uma lista dada em 1 nível.Isso é feito simplesmente pela correspondência de padrões. Uma lista começando com 2
L
se tornará uma lista começando comS
o restante reduzidov
valida uma lista dada pelas regras dadas (no 3 L contínuo, no 2 S contínuo)se a lista começar com uma das 2 seqüências ilegais (L, L, L ou S, S), o resultado é
False
: uma lista vazia é válida e uma lista não-vazia é verificada novamente com o primeiro elemento removidos
verifica se uma lista e todas as listas reduzidas são válidas.Novamente: uma lista vazia é válida (e não pode ser reduzida mais).
Se a lista fornecida como argumento for válida, a lista será reduzida e o anúncio verificado
s
novamente.Caso contrário, o resultado é
False
fonte