Os números de colchete fornecem uma maneira simples de expressar números inteiros grandes usando apenas colchete esquerdo, espaço e colchete direito ( [ ]).
Um número de colchete é definido como uma sequência de um ou mais pares de colchetes [...]chamados chunks , cada um separado dos vizinhos por zero ou mais espaços.
O número de espaços entre cada pedaço define a hiperoperação entre eles. Nenhum espaço significa adição, 1 espaço significa multiplicação, 2 espaços significa exponenciação, 3 espaços significa tetração e assim por diante. As hiperoperações de ordem superior têm precedência; portanto, a tetração ocorre antes da exponenciação, a exponenciação ocorre antes da multiplicação, etc. Elas também são associativas à direita, e a^b^csão computadas como a^(b^c). (Mas a^b*cainda é (a^b)*c.)
Cada pedaço pode estar vazio ( []) ou conter outro número de colchete. Os pedaços vazios têm o valor 0. Os pedaços não vazios têm o valor do seu número de colchete contido mais 1.
Exemplos: ( ^^é tetração, ^^^é pentação )
[[]]tem o valor 1 porque é 0 ([]) incrementado por 1[[[]]]tem valor 2, mas o mesmo acontece[[]][[]]desde que os dois ([[]]) são adicionados[[[]]] [[[[]]] [[[[]]]]][[[]]]tem o valor 20 = (2 * ((2 ^ 3) +1)) + 2[[[]]] [[[[]]]]tem o valor 65536 = 2 ^^^ 3 = 2 ^^ (2 ^^ 2) = 2 ^^ 4 == 2 ^ (2 ^ (2 ^ 2))[[[[]]]] [[[]]] [[]]tem valor 7625597484987 = 3 ^^^ (2 ^^^ 1) = 3 ^^^ 2 = 3 ^^ 3 = 3 ^ (3 ^ 3)
Em números de colchete válidos:
- Nunca haverá espaços à esquerda ou à direita.
- Sempre haverá pelo menos um par de colchetes correspondentes.
- Todos os colchetes esquerdos terão um colchete direito correspondente.
- Um espaço nunca aparecerá diretamente à direita
[ou à esquerda de]. - O valor é sempre um número inteiro não negativo.
Desafio
Observe que pode haver muitos formulários para um número de colchete que dão o mesmo valor. [[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]e [[[]]] [[[[]]]]ambos representam 16, mas o último é muito mais curto.
Seu desafio é escrever um algoritmo que tente encontrar a menor representação de número de colchete de um determinado valor. Por exemplo, acredito que a maneira mais curta de representar 16 é com 17 caracteres como [[[]]] [[[[]]]].
Pontuação (atualizada)
Seja S o conjunto de números inteiros de 1 a 256 (inclusive), além dos dez valores a seguir:
8191 13071 524287 2147483647 1449565302 1746268229 126528612 778085967 1553783038 997599288
(Os quatro primeiros são primos de Mersenne, o resto é aleatório.)
A submissão que gerar o menor conjunto de números de colchetes para tudo em S vencerá. Sua pontuação é a soma dos comprimentos dos números de colchetes para todos os valores em S ( quanto menor, melhor).
Com seu código, envie uma lista de seus números de colchete para todos os números S , a ordem exata não é muito importante. por exemplo:
1=[[]]
2=[[[]]]
3=[[[[]]]]
...
2147483647=[...]
...
(Eu sei que esse não é o método de pontuação ideal, mas não estou configurado para executar vários testes heurísticos aleatórios em cada envio. Desculpe :()
Regras
- Você não pode codificar nenhum número de colchete além das soluções incrementais triviais (
[], [[]], [[[]]], ...). Seu programa deve realmente estar procurando representações otimamente curtas. (Embora os resultados possam ser abaixo do ideal.) - Seu algoritmo deve funcionar para todos os números inteiros não negativos abaixo de 2.147.483.648 (2 ^ 31). Você não pode se concentrar especificamente sobre os valores em S .
- Para qualquer entrada em particular, seu algoritmo deve rodar no máximo 10 minutos em um computador moderno decente (~ processador de 2,5 Ghz, ~ 6 GB de RAM).
- Na (aparentemente) rara chance de empate, a finalização mais votada vence.
- Se você copiar outra solução ou revisá-la sem atribuição, será desqualificado.
fonte
Respostas:
Python 11455b
Esta solução adota uma abordagem gananciosa para encontrar maneiras de quebrar os números primos, em vez de uma abordagem exaustiva. Preciso de 9875b para 1-256 em comparação com 8181 para a solução provavelmente ótima de Martin nesse espaço.
Uma tabela maior de resultados de multiplicação e exponenciação produz pequenas melhorias nos casos de teste maiores. A solução abaixo levou cerca de 7 minutos. Aumentar o tempo de execução além de 30 minutos tem um impacto mínimo na saída.
Eu, como Martin, tive um problema com precedência. Minha solução para restringir a seleção de operações pode não ser a ideal.
Resultado:
fonte
Mathematica
Nota: Esse algoritmo nunca poderá chegar nem perto dos números de teste maiores. Eu precisaria de uma abordagem substancialmente diferente, portanto, deixarei como está para outros verificarem seus números mais baixos. Você pode considerar este envio inválido.
Aqui está um começo para os primeiros 256 números (os outros foram adicionados depois que eu comecei, e provavelmente preciso encontrar uma solução separada para eles)
O comprimento total dos primeiros 256 números é 7963 caracteres. Não sei se isso é ótimo.
Ignorando a adição, os resultados para 8191 e 13071 foram encontrados em alguns segundos e 524387 em alguns minutos, como
com 164 caracteres juntos.
Aqui está o código:
Eu usei uma pesquisa exaustiva até a exponenciação. Não há operações de ordem ou de ordem superior. Eu apenas tentei as operações de ordem superior manualmente, e há apenas algumas combinações que realmente produzem números abaixo de 2 31 , então eu apenas codifiquei as que funcionam.
Edit: Minha solução anterior não se preocupou com precedência, apenas jogou as coisas juntas.
Agora, acho que meu novo código corrige isso,mas nenhum dos primeiros 256 números mudou, nem o 8191 (que era válido antes, verifiquei) ... e é muito tarde para eu dizer agora se meu código realmente o corrigiu. . Vou dar outra olhada amanhã e também adicionar uma explicação, porque agora com a verificação de precedência é um pouco complicado (espero que deva reduzir o tempo de pesquisa).Edit: Ok, houve alguns bugs conforme o esperado. Acho que o corrigi agora, aumentando o comprimento total de 1 a 256 para 7963 . Não tenho certeza se isso é ideal por mais tempo, porque pode ser possível encontrar soluções mais curtas de partes abaixo do ideal se elas permitirem operações de ordem superior. Uma explicação se seguirá quando eu conseguir limpar um pouco o código.
fonte
Python 9219b
Esta é a minha segunda entrada. Comecei do zero e tentei um novo arranjo dos dados, incluindo o uso do pacote blist para listas e ditados classificados e algumas novas abordagens para encontrar grandes soluções. Eu acho que tenho um 1-256 ideal. O aumento do tempo de execução de 30s para 4m reduziu os grandes casos de teste em cerca de 30 bytes.
Resultado:
7944b para 1-256
1275b para os casos grandes
fonte