Votre tâche consiste, avec un entier positif n
, à générer une expression égale au nombre n
.
Le problème est que: vous ne pouvez utiliser que le nombre 1
dans la sortie.
Les opérateurs à votre disposition sont:
+
,-
,*
Et/
/
est une division en virgule flottante (donc5/2 = 2.5
).
sqrt
(commes
)ceil
etfloor
(commec
etf
respectivement)!
(factoriel)- La factorielle, dans ce cas, ne fonctionne que pour les entiers positifs.
Vous êtes également autorisé à empiler 1
les éléments ensemble, donc quelque chose comme 11
est acceptable dans la sortie. Cependant, ils comptent comme le même nombre de 1
s qui est dans le nombre ( 11
compte donc comme 2 1
).
Vous devez également inclure des crochets dans la sortie afin que l'expression dans la sortie, lorsqu'elle est exécutée dans l'ordre des opérations, entraîne l'entrée. Ils ne comptent cependant pas comme des opérations.
Exemples:
- Entrée = 24, une sortie possible =
(1+1+1+1)!
- Entrée = 11, une sortie possible =
11
- Entrée = 5, une sortie possible =
c(s((1+1+1+1)!))
- Le plafond de la racine carrée de
24
is5
.
- Le plafond de la racine carrée de
Règles:
- Vous avez la garantie que l'entrée est un entier positif de
1
à2^31-1
. - Votre programme doit fonctionner pour tout entier positif jusqu’à
2^31-1
, même s’ils ne sont pas testés. - Votre programme doit terminer le traitement de toutes les sorties pour tous les nombres de l'ensemble en une heure.
- Les résultats pour chaque exécution du programme doivent être exactement les mêmes - également, pas de semences.
- Vous n'êtes autorisé à coder en dur les expressions que pour un maximum de 10 valeurs numériques.
- Vous n'êtes pas autorisé à avoir des nombres imaginaires n'importe où dans la sortie (donc non
s(some negative number)
). - Vous n'êtes pas non plus autorisé à avoir un nombre plus grand que
2^31-1
ou plus petit que-2^31+1
partout dans la sortie, même quand ils sontsqrt
ed ou/
ed (donc pas(((1+1+1)!)!)!
ou((1+1+1+1)!)!
).
Ensemble de nombres:
945536, 16878234, 32608778, 42017515, 48950830, 51483452, 52970263, 54278649, 63636656, 78817406, 89918907, 90757642, 95364861, 102706605, 113965374, 122448605, 126594161, 148064959, 150735075, 154382918, 172057472, 192280850, 194713795, 207721209, 220946392, 225230299, 227043979, 241011012, 248906099, 249796314, 250546528, 258452706, 276862988, 277140688, 280158490, 286074562, 308946627, 310972897, 322612091, 324445400, 336060042, 346729632, 349428326, 352769482, 363039453, 363851029, 392168304, 401975104, 407890409, 407971913, 425780757, 459441559, 465592122, 475898732, 482826596, 484263150, 506235403, 548951531, 554295842, 580536366, 587051904, 588265985, 588298051, 590968352, 601194306, 607771869, 618578932, 626776380, 667919873, 681786366, 689854904, 692055400, 697665495, 711608194, 734027104, 750869335, 757710567, 759967747, 777616154, 830071127, 833809927, 835873060, 836438554, 836945593, 863728236, 864158514, 871273503, 881615667, 891619600, 897181691, 918159061, 920521050, 924502226, 929983535, 943162304, 950210939, 950214176, 962610357, 974842859, 988572832
(Ce sont 100 nombres aléatoires de 1 à 1 milliard.)
Système de notation:
Votre score est déterminé comme suit:
- Votre programme sera testé contre les nombres aléatoires de l'ensemble.
- Vous devez fournir la sortie générée à l'aide des nombres aléatoires de l'ensemble (soit dans votre réponse, soit sous la forme d'un lien pastebin).
- Vous avez alors deux "scores": un score primaire et un score secondaire.
- Votre score primaire est
(no. of 1's in output)*(no. of operators in output)
. Si votre score primaire est le plus bas, vous gagnez. - Votre score secondaire correspond à l'heure de votre téléchargement, à l'heure GMT et à l'heure de 24 heures. Donc, si vous téléchargez votre programme le 12 septembre à 00h00 GMT, votre score est alors
12/09/2016, 00:00
(utilisezDD/MM/YYYY HH:MM
pour votre formatage).
- Votre score primaire est
Affichez votre score comme suit:
(language name)
Primary Score = (primary score)
Secondary Score = (secondary score)
(no. of 1's) `1`'s, (no. of operators) operators
Remplacez tous les éléments entre parenthèses par votre nom de langue, votre score primaire et votre score secondaire, respectivement.
Gagnant actuel:
Le gagnant actuel est @ChrisJefferson, qui a un score principal de 3,810,660
.
la source
Réponses:
C ++ 11
Autre petite mise à jour: faites beaucoup moins d’ajouts et essayez tous les nombres du formulaire A * B + C. Je crois que, dans le délai imparti, cela est assez proche de l’optimum, si vous utilisez uniquement
+
,*
et!
. Je laisse les autres opérateurs aux personnes ayant plus de temps que moi!Petite mise à jour: Faites un effort supplémentaire pour utiliser des factorielles et des nombres tels que 11 .... 111. Correction d'un bug que je ne comptais pas
!
dans mes coûtsNouveau résultat:
Score primaire = 3 810 660
Score secondaire = 12/09/2016 20:00
2532
1
s, 1505 opérateurs.Divers astuces mises en place. Mon programme commence par définir le programme le plus court pour toutes les factorielles et tous les nombres du formulaire 111..111 (je ne pense pas que cela enfreigne la règle du câblage, car ce sont les moyens les plus courts de créer ces nombres. Je pourrais réorganiser mon code donc je vérifie ces modèles dans ma programmation dynamique si vous voulez). Ensuite, faites une approche de programmation dynamique partielle en essayant différentes formes:
Malheureusement, je ne peux pas essayer tous les moyens de décomposer un nombre. Je choisis donc pour factoriel et 11 ... 11 d'essayer uniquement le nombre le plus proche, pour A + B d'essayer des options proches de A / 2 et pour A * B +. C pour essayer seulement assez petit comme.
Il serait facile d’étendre cela en essayant quelques-uns, en essayant de dépasser légèrement parfois (en particulier en A * B - C), mais j’aime bien essayer seulement de grandir.
En outre, il est très difficile d’optimiser la condition d’optimisation (je n’aime pas ça!), Car en principe, vous ne pouvez pas définir une «meilleure» valeur pour chaque nombre pris isolément, vous devez considérer votre ensemble de réponses globalement. (ce que je n'ai pas l'intention de faire).
Avertissement: Ce programme nécessite une machine 64 bits et environ 10 Go de mémoire (car je crée de manière inefficace un tableau géant pour tous les résultats partiellement calculés).
Programme:
Résultats:
la source
!
. Je pense que c'est 1632 opérateurs, pas 1407. (Ce qui conduit toujours à un bon score, cependant.)long maxval
Grumble GrumbleHaskell
Score primaire: 27242281
Score secondaire: 12/09/2016 09:01
11891
1
's, 2291 opérateursIl trouve fondamentalement le moyen le plus court de le faire en utilisant seulement + et -
Sortie:
la source
Python, score 17136288
score secondaire: 12/09/2016 08:53
(4784 et 3582 opérations)
Travaux en cours mais OP m'a demandé mon code actuel ...
Sortie - notez que
t
c’est la fonction factorielle, pour ne pas être confondu avecf
carfloor
si elle est utilisée - j’ai évalué chacune d’elles en utilisant la fonctiont
(ci-dessus) pour vérifier qu’elles sont toutes correctes:la source
t
s dans la sortie?JavaScript (ES6), 27212498, 2016-09-12 09: 46: 34Z
Utilise seulement + et -. Basé sur ma réponse à minimiser ceux-ci
la source
Python
Score primaire = 2214138604871819402525
Score secondaire = 12/09/2016, 07:53
Voici le code:
Juste pour faire rouler la balle.
Fondamentalement sorties
1+1+1...+1
, où le nombre de1
'dans l'expression en sortie est égal àn
.Au total, il y a
47054634305
1
des pour l'ensemble des nombres et des47054634205
opérateurs (qui sont tous+
).Je ne vais pas poster un pastebin ici, car vous avez compris l'idée.
la source
2**31-1
.n-1
? Ça fonctionne bien pour moi.awk
score primaire 46933701
score secondaire 12/09/2016 19:20
(6901 unités, 6801 ops)
Imprime simplement la représentation binaire calculée de gauche à droite.
Par exemple, 19 est 10011, ce qui est ((((( 1 ) * 2 + 0 ) * 2 + 0 ) * 2 + 1 ) * 2 + 1 ).
Je laisse juste le
+0
et écris le2
comme(1+1)
.J'étais juste curieux de savoir comment cette méthode marquerait.
Sortie:
la source
Python 3
Score primaire:
69720516
Score secondaire:
09:30 14/09/2016
Edit: utilise maintenant la multiplication pour réduire considérablement le score.
Cela fait un bon usage des factorielles et de la récursivité. Au total, le programme utilise:
5958
les uns11702
les opérateursIdeone ça!
la source
JAVA
Score primaire
1045978739
Score secondaire
12/09/2016 16:05
37193
1s
28123
operators
la source
1
au début de chacun(1*11*11*...*11)
.Emacs Lisp
Score primaire: 81638725
Score secondaire: 12/09/2016 09:35
Génère fondamentalement une somme sur le domaine (1, 11, 111, ...) qui équivaut à n.
la source
111+11+1+1
, n'est-ce pas? (Corrigez-moi si je me trompe.)1
s sur la totalité des 100 sorties et multiplié ce nombre par le nombre total d'+
opérations sur l'ensemble de la sortie?AWK , 15642720
Score secondaire = 30/05/2017, 21h11
Essayez-le en ligne!
Ceux-ci: 4590
Ops: 3408 Score primaire = 15642720 Score secondaire = 30.05.2017 à 21h11
la source