Esse desafio de código fará com que você calcule o número de maneiras de atingir começando em usando mapas do formato (com um número inteiro não negativo) e fazendo isso no número mínimo de etapas.
(Observe, isso está relacionado à sequência OEIS A307092 .)
Exemplo
Por exemplo, porque são necessários três mapas e há duas seqüências distintas de três mapas que enviarão de a :
Resultando em ou .
Valores de exemplo
f(2) = 1 (via [])
f(3) = 1 (via [0])
f(4) = 1 (via [1])
f(5) = 1 (via [1,0])
f(12) = 2 (via [0,2] or [2,1])
f(13) = 2 (via [0,2,0] or [2,1,0], shown above)
f(19) = 1 (via [4,0])
f(20) = 2 (via [1,2] or [3,1])
f(226) = 3 (via [2,0,2,1,0,1], [3,2,0,0,0,1], or [2,3,0,0,0,0])
f(372) = 4 (via [3,0,1,0,1,1,0,1,1], [1,1,0,2,0,0,0,1,1], [0,2,0,2,0,0,0,0,1], or [2,1,0,2,0,0,0,0,1])
Desafio
O desafio é produzir um programa que use um número inteiro como entrada e produza o número de caminhos distintos de a por meio de um número mínimo de mapas no formato .
Isso é código-golfe , e o menor número de bytes vence.
code-golf
sequence
combinatorics
Peter Kagey
fonte
fonte
^
símbolo denota exponenciação. Também poderia ser XOR (por exemplo, C usa^
para XOR bit a bit).x -> x + x^j
Respostas:
Gelatina , 16 bytes
Experimente online!
Um programa completo tomando como argumenton e retornando o número de maneiras de alcançar n usando o comprimento mínimo do caminho. Ineficiente para n maior .
fonte
JavaScript (ES6),
111 ... 8480 bytesRetorna true em vez de1 para n = 2 .
Experimente online!
Comentado
fonte
Haskell ,
7875 bytesEssa implementação usa uma pesquisa pela primeira vez na "árvore" de todos os mapeamentos necessários iterativamente
x -> x + x^j
.Experimente online!
Explicação
fonte
05AB1E , 17 bytes
Experimente online!
fonte
Python 2 , 72 bytes
Experimente online!
fonte
Perl 5 (
-lp
), 79 bytesTIO
fonte
CJam (27 bytes)
Demonstração online
Aviso: isso consome muita memória muito rapidamente.
Dissecação:
Os bônus
2
s (para lidar com o caso especial de entrada2
, porque oswhile
loops são mais caros que osdo-while
loops) significam que o tamanho da lista cresce muito rápido e o uso de expoentes atén-1
significa que os valores dos números maiores na lista aumentam muito rápido.fonte
Haskell , 65 bytes
Experimente online!
A primeira pesquisa de flawr do golfe . Eu também tentei voltar atrás
n
, mas era mais longo:73 bytes
Experimente online!
fonte
R ,
78bytesExperimente online!
Usando uma Pesquisa simplificada de amplitude inicial
Código desenrolado com explicação:
Versão mais curta com enorme alocação de memória (falhando em casos maiores):
R ,
7069 bytesExperimente online!
-1 byte graças a @RobinRyder
fonte
!(a<-sum(x==n))
pode ser!{a=sum(x==n)}
de -1 byte nos dois casos.Pitão , 24 bytes
Experimente online!
Isso deve produzir a saída correta, mas é muito lento (o caso de teste 372 atinge o tempo limite no TIO). Eu poderia reduzi-lo substituindo
.lQ2
porQ
, mas isso tornaria o tempo de execução horrendo.Explicação
fonte