Les nombres entre parenthèses offrent un moyen simple d'exprimer de grands nombres entiers en utilisant uniquement le crochet gauche, l'espace et le crochet droit ( [ ]).
Un numéro de parenthèse est défini comme une chaîne d'une ou plusieurs paires de parenthèses correspondantes [...]appelées morceaux , chacune séparée de ses voisins par zéro ou plusieurs espaces.
Le nombre d'espaces entre chaque bloc définit l' hyperopération entre eux. Aucun espace signifie addition, 1 espace signifie multiplication, 2 espaces signifie exponentiation, 3 espaces signifie tétration , etc. La hausse hyperopération d'ordre ont priorité, si tétration se produit avant exponentiation, exponentiation se produit avant la multiplication, etc. Ils sont également droit associatif, donc a^b^cest calculé comme a^(b^c). (Mais a^b*cc'est toujours (a^b)*c.)
Chaque bloc peut être vide ( []) ou contenir un autre numéro de parenthèse. Les blocs vides ont la valeur 0. Les blocs non vides ont la valeur de leur numéro de parenthèse contenu plus 1.
Exemples: ( ^^est la tétration, ^^^est la pentation )
[[]]a la valeur 1 car il est 0 ([]) incrémenté de 1[[[]]]a la valeur 2 mais il en est de même[[]][[]]puisque les deux ([[]]) sont ajoutés[[[]]] [[[[]]] [[[[]]]]][[[]]]a la valeur 20 = (2 * ((2 ^ 3) +1)) + 2[[[]]] [[[[]]]]a la valeur 65536 = 2 ^^^ 3 = 2 ^^ (2 ^^ 2) = 2 ^^ 4 == 2 ^ (2 ^ (2 ^ 2))[[[[]]]] [[[]]] [[]]a la valeur 7625597484987 = 3 ^^^ (2 ^^^ 1) = 3 ^^^ 2 = 3 ^^ 3 = 3 ^ (3 ^ 3)
Dans les numéros de parenthèses valides:
- Il n'y aura jamais d'espaces de début ou de fin.
- Il y aura toujours au moins une paire de supports correspondants.
- Tous les supports gauche auront un support droit correspondant.
- Un espace n'apparaîtra jamais directement à droite
[ni à gauche de]. - La valeur est toujours un entier non négatif.
Défi
Notez qu'il peut y avoir de nombreux formulaires pour un numéro de parenthèse qui donnent la même valeur. [[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]et les [[[]]] [[[[]]]]deux représentent 16, mais ce dernier est beaucoup plus court.
Votre défi consiste à écrire un algorithme qui tente de trouver la représentation du numéro de parenthèse la plus courte d'une valeur donnée. Par exemple, je pense que le moyen le plus court de représenter 16 est d'utiliser 17 caractères [[[]]] [[[[]]]].
Score (mis à jour)
Soit S l'ensemble des entiers de 1 à 256 (inclus) ainsi que les dix valeurs suivantes:
8191 13071 524287 2147483647 1449565302 1746268229 126528612 778085967 1553783038 997599288
(Les 4 premiers sont des nombres premiers de Mersenne, les autres sont aléatoires.)
La soumission qui génère le plus petit ensemble de numéros de parenthèses pour tout dans S gagnera. Votre score est la somme des longueurs de vos numéros de parenthèse pour toutes les valeurs en S (plus petit est meilleur).
Avec votre code, veuillez soumettre une liste de vos numéros de support pour tous les S , la commande exacte n'est pas très importante. par exemple:
1=[[]]
2=[[[]]]
3=[[[[]]]]
...
2147483647=[...]
...
(Je sais que ce n'est pas la méthode de notation optimale mais je ne suis pas configuré pour exécuter un tas de tests heuristiques aléatoires sur chaque soumission. Désolé :()
Règles
- Vous ne pouvez coder en dur aucun numéro de parenthèse en plus des solutions incrémentielles triviales (
[], [[]], [[[]]], ...). Votre programme doit en fait rechercher des représentations optimales et courtes. (Bien que les résultats puissent être sous-optimaux.) - Votre algorithme devrait fonctionner pour tous les entiers non négatifs inférieurs à 2 147 483 648 (2 ^ 31). Vous ne pouvez pas se concentrer spécifiquement sur les valeurs de S .
- Pour toute entrée particulière, votre algorithme devrait fonctionner en au plus 10 minutes sur un ordinateur moderne décent (~ processeur 2,5 GHz, ~ 6 Go de RAM).
- Dans la chance (apparemment) rare d'égalité, la soumission la plus votée gagne.
- Si vous copiez une autre solution ou la révisez sans attribution, vous serez disqualifié.
la source
Réponses:
Python 11455b
Cette solution adopte une approche gourmande pour trouver des moyens de décomposer les nombres premiers, plutôt qu'une approche exhaustive. J'ai besoin de 9875b pour 1-256 par rapport à 8181 pour la solution probablement optimale de Martin dans cet espace.
Un tableau plus grand des résultats de multiplication et d'exponentiation donne de légères améliorations dans les cas de test plus grands. La solution ci-dessous a pris environ 7 minutes. L'augmentation de la durée d'exécution au-delà de 30 minutes a un impact minimal sur la sortie.
Comme Martin, j'ai eu un problème de priorité. Ma solution en restreignant la sélection des opérations n'est peut-être pas optimale.
Production:
la source
Mathematica
Remarque: Cet algorithme ne pourra jamais se rapprocher des plus grands nombres de tests. J'aurais besoin d'une approche substantiellement différente, je vais donc laisser les choses telles quelles pour que les autres vérifient leurs chiffres inférieurs. Vous pouvez considérer cette soumission comme non valide.
Voici un début pour les 256 premiers numéros (les autres ont été ajoutés après que j'ai commencé, et j'ai probablement besoin de trouver une solution distincte pour ceux-ci)
La longueur totale des 256 premiers chiffres est de 7963 caractères. Je ne sais pas si c'est optimal.
En ignorant l'ajout, les résultats pour 8191 et 13071 ont été trouvés en quelques secondes et 524387 en quelques minutes comme
à 164 caractères ensemble.
Voici le code:
J'ai utilisé une recherche exhaustive jusqu'à l'exponentiation. Il n'y a pas de tétration ou d'opérations d'ordre supérieur. J'ai juste essayé les opérations d'ordre supérieur manuellement, et il n'y a qu'une poignée de combinaisons qui donnent en fait des nombres inférieurs à 2 31 , donc j'ai juste codé en dur celles qui fonctionnent.
Edit: Ma solution précédente ne s'est pas souciée de la priorité, elle a simplement mis les choses ensemble.
Maintenant, je pense que mon nouveau code corrige cela,mais aucun des 256 premiers numéros n'a changé, ni 8191 (qui était valide avant, j'ai vérifié) ... et il est trop tard pour moi de dire maintenant si mon code l'a réellement corrigé . J'aurai un autre regard demain et ajouterai également une explication, car maintenant avec la vérification de la priorité, c'est un peu compliqué (j'espère que cela devrait réduire le temps de recherche cependant).Edit: D'accord, il y avait quelques bugs comme prévu. Je pense que je l'ai corrigé maintenant, augmentant la longueur totale pour 1 - 256 à 7963 . Je ne suis pas sûr que cela soit optimal plus longtemps, car il pourrait être possible de trouver des solutions plus courtes à partir de pièces sous-optimales si elles permettent des opérations d'ordre supérieur. Une explication suivra lorsque j'arriverai à nettoyer un peu le code.
la source
Python 9219b
Ceci est ma deuxième entrée. Je suis parti de zéro et j'ai essayé un nouvel arrangement des données, y compris en utilisant le package blist pour les listes triées et les dictés, et quelques nouvelles approches pour trouver de grandes solutions. Je pense que j'ai un 1-256 optimal. L'augmentation du temps d'exécution de 30 s à 4 m a raccourci les gros cas de test d'environ 30 octets.
Production:
7944b pour 1-256
1275b pour les grandes caisses
la source