introduction
"Muhuhuhahahah!" Le savant fou rit. "Tu es pris au piège dans mon propre petit jeu!"
Devant vous se trouve une fosse mortelle de serpents, tandis que derrière vous se trouve un gouffre sans fond. Il n'y a aucune issue, vous êtes coincé!
"Deux pas devant vous est la fosse aux serpents, et deux pas derrière vous est l'abîme. Mais! Avant de vous déplacer, vous DEVEZ écrire une séquence de pas, en avant et en arrière, et me les donner. Mais! Parce que je Je me sens un peu mal aujourd'hui, je peux vous faire prendre, au lieu de chaque étape, chaque nétape, où nest inférieure à la longueur de votre séquence!
Choisissez judicieusement, maintenant. "
Quel est le nombre maximum de mesures que vous pouvez prendre avant votre mort imminente?
Tâche
L'intro ci-dessus est une torsion de la conjecture de divergence d'Erd , qui s'est récemment avérée vraie (si vous voulez en savoir plus à ce sujet, allez à cette vidéo , par James Grime - j'ai "volé" la question de torsion de lui).
La réponse à l'intro est des 11étapes, mais je n'irai pas trop en profondeur avec une preuve. La réponse, si la distance entre vous et les deux "dangers" était des 3étapes, est des 1160étapes, bien que cela ne soit pas encore validé correctement.
Votre tâche consiste à créer un programme qui génère la plus longue séquence d'étapes que vous pouvez réaliser pour un plus grand x, où xest le nombre d'étapes entre vous et les deux "dangers". Votre programme doit prendre une entrée pour x, et produire une séquence valide pour cela x.
Aux fins de ce défi, +représente un pas en avant et -un pas en arrière.
Ainsi, une sortie pour une entrée 2est:
+--+-++--++
Ce qui fonctionne, peu importe ce que nle savant fou choisit. Pour notre défi, x = 5.
REMARQUE: Ce défi n'est pas une dupe de ce défi ou de ce défi , car mon défi se concentre sur la sortie, par opposition au code lui-même - en d'autres termes, ce n'est pas un défi de golf de code. En plus de cela, ces défis sont basés sur x = 3, qui a déjà une limite supérieure établie.
Règles:
- Tout votre programme devrait correspondre à votre réponse. Cependant, s'il ne convient pas, veuillez fournir un référentiel Github supplémentaire, ou quelque chose de similaire.
- Vous pouvez mettre à jour à la fois votre réponse et votre programme, si vous pouvez obtenir un meilleur score en optimisant votre code - mais ce faisant, vous devez tout mettre à jour dans la liste ci-dessous.
- Dans votre réponse, vous devez avoir:
- Votre programme, dans son intégralité, ou un lien vers un référentiel GH hébergeant votre code
- Le nombre de pas générés - ce sera votre score final .
- Vous devez également fournir une version en ligne de la séquence dans un Pastebin, ou quelque chose de similaire. C'est pour que nous puissions vérifier votre réponse.
- La dernière fois que votre score final a été mis à jour, je n'ai donc pas à vérifier votre historique
- Vous ne pouvez PAS coder en dur des séquences au préalable.
- Votre programme doit fonctionner pour tous
x(oùxest le nombre d'étapes entre vous et le puits et le gouffre), mais vous n'avez qu'à fournir le score pourx = 5.
La réponse avec le plus grand score gagne!
la source
nétape, où sentrouve un nombre inférieur à la taille de votre séquence.x=5nécessiterait une percée majeure qui mériterait d'être publiée. Considérez que le maximum de 1160 pour ax=3été prouvé et publié en 2014 et aucune autre valeur n'est connue. .Réponses:
Rust, score = 4997216, time = 2017-07-12 00:18 UTC
Cela améliore le meilleur résultat que j'ai pu trouver dans la littérature, qui était 1148805 (Ronan Le Bras, Carla P. Gomes, Bart Selman, On the Erdős Discrepancy Problem , 2014), par un facteur de 4,3.
Séquence de sortie de longueur 4997216
Code source sur GitHub
Fonctionnement
Le programme accepte la différence maximale comme argument (il s'agit de x - 1 dans la langue du défi, pour s'aligner sur la convention mathématique la plus courante). Il produit des sorties incrémentielles dans un format légèrement compressé qui ressemble à ceci pour x = 3:
où
addsignifie ajouter une séquence de signes à la fin de la séquence en cours,deletesignifie supprimer un certain nombre de signes de la fin de la séquence en cours etlengthaffirme la longueur de la séquence en cours. Ce schéma évite la production de plusieurs gigaoctets de résultats intermédiaires à mesure que des séquences de plus en plus longues sont découvertes. Vous pouvez extraire le meilleur résultat jusqu'à présent avec le programme Python suivant:Comment ça fonctionne
Il y a environ mille lignes de code ici, donc cela ne sera qu'un aperçu très approximatif.
Nous limitons la recherche à des séquences complètement multiplicatives (celles avec f ( a · b ) = f ( a ) · f ( b )), car cela signifie que nous n'avons qu'à nous préoccuper de délimiter les sommes partielles pour n = 1, et les partielles les sommes pour n ≥ 2 satisferont automatiquement la même borne.
Pour toute sous-chaîne f ( i + 1),…, f ( j ) d'une séquence de signes partiellement attribuée (de sorte que chaque élément est «+», «-» ou inconnu), définissez danger + ( i , j ) comme étant deux fois le nombre de '+' moins la longueur j - i (pour plus de commodité, nous autorisons i à être aussi petit que - x + 2 et supposons f (- x + 3) = ⋯ = f (0) = '+' pour Cet objectif). Définissez le danger - ( i , j ) de la même manière. Ensuite, la borne sur les sommes partielles pour n= 1 équivaut à la condition que chaque fois que i ≡ j ≡ x (mod 2), danger + ( i , j ) ≤ x - 2 et danger - ( i , j ) ≤ x - 2.
Nous construisons une structure de données incrémentielle qui prend en charge les requêtes à temps constant pour la sous-chaîne la plus dangereuse, avec des mises à jour logarithmiques. Il fonctionne en associant quatre valeurs:
avec chaque chaîne de longueur 2, chaque autre chaîne de longueur 4, chaque quatrième chaîne de longueur 8, etc. Les valeurs associées à une chaîne plus longue peuvent être calculées en temps constant à partir des valeurs associées à ses deux moitiés.
Cette structure, augmentée de quelques informations auxiliaires, nous permet d'effectuer très rapidement la propagation de contraintes et la détection de conflits sur des séquences partielles. Nous l'utilisons pour faire une recherche de type CDCL , avec propagation d'unité, niveaux de décision et retour en arrière non chronologique (mais sans apprentissage de clause, pour l'instant), pour des séquences complètes de plus en plus longues.
À chaque étape de la recherche, nous devinons le premier signe non attribué. L'heuristique utilisée pour faire cette supposition est très importante pour éviter beaucoup de retours en arrière; nous utilisons f (3 · k ) = - f ( k ), f (3 · k + 1) = '+', f (3 · k + 2) = '-'.
Résultats
Les différences de recherche 0, 1 et 2 trouvent immédiatement les séquences optimales complètement multiplicatives de longueur 0, 9 et 246.
La recherche de l'écart 3 est bloquée en quelques secondes à 41319, ce qui est assez loin de la séquence optimale complètement multiplicative connue de longueur 127645 trouvée par Le Bras et al., 2014 (et une extension non multiplicative très légèrement plus longue de la longueur 130000 trouvée peu de temps après ), mais bien meilleure que la séquence la plus connue avant celle de la longueur 17000 .
La recherche de divergence 4 améliore la séquence la plus longue plus ou moins continuellement pendant environ cinq minutes jusqu'à ce qu'elle se bloque à 4997216. La meilleure séquence connue de longueur 1148805 = 9 · 127645 a été développée à partir de la séquence de divergence 3 en remplaçant chaque signe s par + - - + - ++ - s . Autant que je sache, les séquences aussi longues sont trop difficiles à résoudre pour un solveur SAT général (mais peut-être vous, cher lecteur, pouvez-vous me prouver le contraire!).
Je pense que je devrai ajouter une sorte de clause d'apprentissage à mon programme pour surmonter ces obstacles.
La séquence sous forme de bitmap 2187 × 2285
(Cliquez pour voir en pleine résolution.)
la source
Haskell , score = 9020, temps = 2017-06-09 00:52 UTC
Essayez-le en ligne!
Cette note (9 n - 1 - 1) ⋅11 / 8 pour tous les n . Voici les premières sorties:
la source