Dado inteiro positivo n > 2
. Nós o convertemos em uma matriz da seguinte maneira:
- Se for igual para
2
retornar uma matriz vazia - Caso contrário, crie uma matriz de todos
n
os fatores primos classificados de forma crescente, então cada elemento substitua por seu índice na sequência de números primos e, finalmente, converta cada elemento em matriz
Por exemplo, vamos converter o número 46
em matriz. Em primeiro lugar, converta-o na matriz de seus principais fatores:
[2, 23]
Number 23
é o 9
primeiro primo, então substitua 2
por array vazio e 23
por [9]
. A matriz agora se torna:
[[], [9]]
Os fatores primos de 9
são 3
e 3
, portanto:
[[], [3, 3]]
Faça o mesmo para ambos 3
:
[[], [[2], [2]]]
E finalmente:
[[], [[[]], [[]]]]
Agora, para codificá-lo, simplesmente substituímos cada colchete aberto por 1
cada colchete e 0
, em seguida, removemos todos os zeros finais e soltamos um 1
do final. Este é o nosso número binário. Usando o exemplo acima:
[ ] [ [ [ ] ] [ [ ] ] ]
| | | | | | | | | | | |
| | | | | | | | | | | |
V V V V V V V V V V V V
1 0 1 1 1 0 0 1 1 0 0 0
Agora basta soltar os três últimos zeros e o último 1
. O número passa a 10111001
ser 185
decimal. Essa é a saída esperada. Observe que, na matriz, os colchetes de conversão binária da matriz principal não estão incluídos.
Entrada
Número inteiro positivo n
maior que 2
.
Saída
Inteiro codificado n
.
Regras e formato IO
- Aplicam-se regras padrão.
- A entrada pode ser string ou número (mas no caso de string, ela deve estar na base 10).
- A saída pode ser sequência ou número (mas, no caso de sequência, deve estar na base 10).
- Isso é código-golfe , a resposta mais curta em bytes vence!
Casos de teste
Mais casos de teste, mediante solicitação.
3 ---> 1
4 ---> 2
5 ---> 3
6 ---> 5
7 ---> 6
8 ---> 10
9 ---> 25
10 ---> 11
10000 ---> 179189987
10001 ---> 944359
10002 ---> 183722
10003 ---> 216499
10004 ---> 2863321
10005 ---> 27030299
10006 ---> 93754
10007 ---> 223005
10008 ---> 1402478
2
pois os envios não são necessários para lidar com isso.Respostas:
Casca ,
3531302926252422201915 bytes-7 bytes graças a @Zgarb!
Economizou 4 bytes extras, indiretamente, graças ao Zgarb
Experimente online!
Explicação
fonte
φ
, o ponto de correção lambda!`:0:1
pode ser`Jḋ2
.Geléia ,
22 2019 bytes-1 graças a Erik the Outgolfer (zeros de cauda de ambos os lados
t
, e não da direitaœr
)Um link monádico que pega um número inteiro maior que 2 e retorna um número inteiro maior que 0 (2 também retornaria 0 conforme a especificação original).
Experimente online!
Quão?
Isso quase exatamente replica a descrição fornecida, apenas com alguma manipulação ordinal para a criação da matriz binária ...
fonte
Python 2 ,
212177 bytesExperimente online!
A falta de componentes principais realmente prejudica a contagem de bytes e atinge o tempo limite no TIO com números primos maiores. Usos xnor 's verificação primality.
Python 2 + gmpy2 , 175 bytes
Experimente online!
Esta versão não atinge o tempo limite nos casos de teste maiores (ou seja, 10000 - 10008).
fonte
Mathematica,
125119 bytesUsa uma abordagem ligeiramente diferente; converte índices primos em
{1, index, 0}
e 2 em{1, 0}
.Experimente na Wolfram Sandbox
Uso:
fonte
Geléia , 35 bytes
Experimente online!
fonte
J,
747366 bytesExperimente online!
Esta é uma verdadeira bagunça que certamente precisa de mais golfe (por exemplo, remoção da definição explícita da função). Eu acho que o boxe que eu faço é especialmente o que está trazendo o número de bytes, já que eu realmente não sei o que estou fazendo lá (foram muitas tentativas e erros). Além disso, estou bastante certo de que há alguns built-ins que eu estou esquecendo (por exemplo, eu me sinto como
_2,~_1,
, provavelmente, tem um built-in).Explicação (ungolfed)
Preâmbulo
Sente-se com força, porque essa não será uma breve explicação. Ironicamente, uma linguagem concisa foi combinada com uma pessoa detalhada.
Vou dividir isso em algumas funções
encode
codifica o número inteiro usando _1 e _2 em vez de [e]convert
converte uma lista de _1 e _2 em uma lista de 1 e 0drop
descarta o último 1 e zeros à direitadecode
converte de uma lista binária em um númeroVou percorrer uma amostra de 46, que expressa no formato não destruído, está concluída
Codificar
Há muito o que explicar aqui.
Observe que a definição de função explícita
3 : '[function]'
avalia a função como se estivesse no REPL com o argumento correto substituindo todas as instâncias dey
(isso significa que eu posso evitar ter que usar caps ([:
), atops (@
) e ats (@:
) ao custo de alguns bytes).Aqui está o que parece para cada iteração sucessiva na entrada de 46
Esta função utiliza advers (
::
) para aninhar os valores entre "colchetes" (os colchetes usados aqui são -1 e -2). Basicamente, toda vez que fatoramos e convertemos em índices de números primos, _1 é anexado e _2, que atuam como colchetes. Quando a função é chamada nesses elementos, apenas os retorna como estão, poisq:
ocorrerá um erro ao tentar fatorar um número negativo. É também uma sorte queq:
faz não erro na tentativa de fatorar 1 e em vez disso retorna a matriz vazia (como desejado).Converter
Converter é muito mais simples. Apenas remove todo o boxe, assim como o primeiro elemento, e depois converte tudo em 1s e 0s (simplesmente adicionando 2)
Solta
Isso inverte a lista, localiza o primeiro e, em seguida, descarta todos os valores até aquele, e inverte a lista novamente.
Decodificar
Decodificar é a função
#.
interna que pega uma lista de 1s e 0s e a converte em um número binário.fonte
Retina ,
244227225 bytesExperimente online!
Essa é uma abordagem direta, seguindo o algoritmo demonstrado na pergunta. A geração de índice principal é de complexidade exponencial, portanto, o tempo limite para entradas maiores
Explicação:
fonte
Haskell ,
162160155 bytesExperimente online!
Explicação:
r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]]
define uma lista infinita de tuplas de primos e seus índices:[(1,2),(2,3),(3,5),(4,7),(5,11),(6,13), ...]
.A função
(%)
pega essa listar
e um númeron
e converte o número na representação inversa da matriz de fatores. Isso é feito avançandor
até encontrarmos um primo que se dividen
. Em seguida, de forma recursiva determinar a representação do índice deste nobre e coloque-a0
e1
e preceder a representaçãon
dividida pela prime.Pois
n=46
, isso gera a lista[0,0,0,1,1,0,0,1,1,1,0,1]
da qual os zeros à esquerda (snd.span(<1)
) e os próximos1
(tail
) são descartados. Depois que a lista é convertida para um número decimal multiplicando elemento-wise com uma lista de potências de dois e somando-se a lista resultante:sum.zipWith((*).(2^))[0..]
.fonte
JavaScript, 289 bytes
Os bytes são a soma do código JavaScript sem quebras de linha após as vírgulas (inseridas apenas para melhor formatação e legibilidade) (256 bytes) e os caracteres adicionais para a opção de linha de comando, necessária ao usar o Chrome (33 bytes).
E uma versão mais longa e melhor legível:
Algumas breves explicações:
f
é um algoritmo de fatoração recursivo da cauda puramente funcional.c
conta em que localr
o número primop
ocorre na sequência de números primos e retorna[]
(sep=2
er=1
) ou fatora e processa outrosr
por meio de recursão.h
é uma função auxiliar pequena que, infelizmente, é necessária comomap
chama a função fornecida comnumberOfCurrentElement
o segundo ewholeArray
o terceiro argumento, substituindo, assim, os valores padrão fornecidosc
se passarmos diretamente essa função (levei algum tempo para resolver essa armadilha; substituirh
por sua definição levaria alguns bytes a mais).s
transforma a matriz gerada em uma sequência. Nós usamos emblank
vez de0
para que possamos usartrim()
emo
.o
é a função a ser chamada com o valor de entradai
que retorna a saída. Ele gera a representação de string binária exigida pela especificação e a converte em um número (decimal).Editar: é necessário iniciar o Chrome
chrome --js-flags="--harmony-tailcalls"
para ativar a otimização da recursão da cauda (consulte https://v8project.blogspot.de/2016/04/es6-es7-and-beyond.html ). Isso também requer o uso do modo estrito.O teste a seguir mostra que a computação é um pouco lenta para alguns valores (o mais longo é de mais de seis segundos
10007
no meu computador). Curiosamente, sem a otimização da recursão da cauda, o cálculo é muito mais rápido (sobre o fator 5) quando não há excesso de pilha.fonte
tinylisp , 209 bytes
A última linha é uma função sem nome que calcula a codificação especificada. Experimente online!
Versão pré-golfe
Este é o código que eu tinha antes de começar a jogar:
fonte
05AB1E , 18 bytes
Experimente online!
Explicação:
fonte