Introdução
"Muhuhuhahahah!" O cientista louco ri. "Você está preso no meu próprio joguinho!"
À sua frente há um poço mortal de cobras, enquanto atrás de você há um abismo sem fundo. Não há saída, você está preso!
"Dois passos à sua frente é o poço das cobras, e dois passos atrás de você é o abismo. Mas! Antes de você se mover, DEVE escrever uma sequência de passos, para a frente e para trás, e dê-os para mim. Mas! Porque eu Estou me sentindo um pouco mal hoje, posso fazer você dar, em vez de cada passo, cada npasso, onde né menor que a duração da sua sequência!
Escolha sabiamente, agora. "
Qual é o número máximo de etapas que você pode executar antes de sua morte iminente?
Tarefa
A introdução acima é uma torção na conjectura de discrepância de Erdő , que recentemente se provou verdadeira (se você quiser entender mais sobre isso, vá a este vídeo , por James Grime - eu "roubei" a questão da torção dele).
A resposta para a introdução são as 11etapas, mas não vou me aprofundar muito na prova. A resposta, se a distância entre você e os dois "perigos" foram 3passos, são 1160passos, embora isso ainda não esteja validado adequadamente.
Sua tarefa é criar um programa que gere a maior seqüência de etapas possível para uma maior x, onde xestá o número de etapas entre você e os dois "perigos". Seu programa deve receber uma entrada xe gerar uma sequência válida para isso x.
Para os propósitos deste desafio, +representa um passo adiante e -representa um passo atrás.
Portanto, uma saída para uma entrada 2é:
+--+-++--++
O que funciona, não importa o que no cientista louco escolha. Para o nosso desafio x = 5.
OBSERVAÇÃO: Esse desafio não é um engodo desse desafio ou deste desafio , pois meu desafio se concentra na saída, em oposição ao próprio código - em outras palavras, não é um desafio de golfe de código. Além disso, esses desafios se baseiam x = 3, que já possui um limite superior estabelecido.
Regras:
- Todo o seu programa deve caber na sua resposta. No entanto, se não se encaixar, forneça um repositório Github adicional ou algo semelhante.
- Você pode atualizar sua resposta e seu programa, se conseguir uma pontuação melhor otimizando seu código - mas, ao fazer isso, você deve atualizar tudo na lista abaixo.
- Na sua resposta, você deve ter:
- Seu programa, na íntegra, ou um link para um repositório GH que hospeda seu código
- A quantidade de etapas geradas - essa será sua pontuação final .
- Você também deve fornecer uma versão online da sequência em um Pastebin, ou algo semelhante. Isso é para que possamos verificar sua resposta.
- A última vez que sua pontuação final foi atualizada, por isso não preciso verificar seu histórico
- Você NÃO pode codificar sequências previamente.
- Seu programa deve funcionar para todos
x(ondexestá o número de etapas entre você e o poço e o abismo), mas você só precisa fornecer a pontuaçãox = 5.
A resposta com a maior pontuação ganha!
fonte
netapas, ondenhouver qualquer número abaixo do tamanho da sequência.x=5exigiria uma grande inovação que seria digna de publicação. Considere que o máximo de 1160 parax=3foi provado e publicado em 2014 e nenhum valor adicional é conhecido. .Respostas:
Ferrugem, pontuação = 4997216, tempo = 12/07/2017 00:18 UTC
Isso melhora o melhor resultado que pude encontrar na literatura, que foi 1148805 (Ronan Le Bras, Carla P. Gomes, Bart Selman, Sobre o problema da discrepância de Erdős , 2014), por um fator de 4,3.
Sequência de saída de comprimento 4997216
Código fonte no GitHub
Corrida
O programa aceita a discrepância máxima como argumento (este é x - 1 no idioma do desafio, para alinhar com a convenção matemática mais comum). Produz saídas incrementais em um formato ligeiramente compactado, semelhante a este para x = 3:
onde
addsignifica anexar uma sequência de sinais ao final da sequência atual,deleteremover um certo número de sinais do final da sequência atual elengthafirmar o comprimento da sequência atual. Esse esquema evita a produção de muitos gigabytes de resultados intermediários à medida que sequências cada vez maiores são descobertas. Você pode extrair o melhor resultado até agora com o seguinte programa Python:Como funciona
Existem cerca de mil linhas de código aqui, portanto, essa será apenas uma visão geral bastante aproximada.
Limitamos a busca a sequências completamente multiplicativas (aquelas com f ( a · b ) = f ( a ) · f ( b )), porque isso significa que precisamos apenas nos preocupar em limitar as somas parciais para n = 1 e as parciais as somas para n ≥ 2 satisfarão o mesmo limite automaticamente.
Para qualquer substring f ( i + 1),…, f ( j ) de uma sequência de sinais parcialmente atribuída (para que cada elemento seja '+', '-' ou desconhecido), defina o perigo + ( i , j ) como duas vezes o número de '+' menos o comprimento j - i (por conveniência, permitimos que eu seja tão pequeno quanto - x + 2 e assumimos que f (- x + 3) = ⋯ = f (0) = '+' para este propósito). Definir perigo - ( i , j ) da mesma forma. Então o limite em somas parciais para n= 1 é equivalente à condição de que, sempre que i ≡ j ≡ x (modificação 2), perigo + ( i , j ) ≤ x - 2 e perigo - ( i , j ) ≤ x - 2.
Construímos uma estrutura de dados incremental que suporta consultas de tempo constante para a substring com maior perigo, com atualizações de tempo logarítmicas. Ele funciona associando quatro valores:
com todas as cordas de comprimento 2, todas as outras cordas de comprimento 4, todas as quartas cordas de comprimento 8, e assim por diante. Os valores associados a uma cadeia mais longa podem ser calculados em tempo constante a partir dos valores associados às suas duas metades.
Essa estrutura, aumentada com algumas informações auxiliares, permite executar a propagação de restrições e a detecção de conflitos em seqüências parciais muito rapidamente. Nós o usamos para fazer uma pesquisa do tipo CDCL , com propagação de unidade, níveis de decisão e retorno não cronológico (mas sem aprendizado de cláusulas, por enquanto), para sequências completas de comprimentos cada vez maiores.
Em cada etapa da pesquisa, fazemos um palpite para o primeiro sinal não atribuído. A heurística usada para fazer esse palpite é muito importante para evitar muitos retrocessos; usamos f (3 · k ) = - f ( k ), f (3 · k + 1) = '+', f (3 · k + 2) = '-'.
Resultados
As discrepâncias de pesquisas 0, 1 e 2 encontram imediatamente as seqüências multiplicativas completas ideais de comprimento 0, 9 e 246.
A pesquisa de discrepância 3 fica presa em segundos em 41319, o que é bastante distante da sequência ótima multiplicativa ideal de comprimento 127645 encontrada por Le Bras et al., 2014 (e uma extensão não multiplicativa de comprimento 130000 encontrada um pouco mais longa, encontrada pouco tempo depois. ), mas muito melhor que a sequência mais conhecida anterior à do comprimento 17000 .
A busca discrepância 4 melhora a mais longa sequência mais ou menos continuamente por cerca de cinco minutos até que ele fica preso em 4997216. A melhor sequência previamente conhecida de comprimento 1148805 = 9 · 127645 foi ampliado a partir da sequência discrepância 3, substituindo todos os sinais s com + - - + - ++ - s . Até onde eu sei, seqüências tão longas são muito difíceis para um solucionador geral de SAT melhorar razoavelmente diretamente (mas talvez você, caro leitor, possa provar que estou errado!).
Espero que precise adicionar algum tipo de cláusula de aprendizado ao meu programa para superar essas barreiras.
A sequência como um bitmap de 2187 × 2285
(Clique para ver em resolução total.)
fonte
Haskell , pontuação = 9020, tempo = 09-06-2017 00:52 UTC
Experimente online!
Esta pontuação (9 n - 1 - 1) ⋅11 / 8 para todos os n . Aqui estão as primeiras saídas:
fonte