Deadfish est l'un des langages de programmation non complets de Turing les plus connus. Il n'a qu'un seul accumulateur (qui commence à 0) pour stocker des données et seulement quatre commandes:
i - Increment the accumulator
s - Square the accumulator
d - Decrement the accumulator
o - Output the accumulator
Un programme Deadfish peut ressembler à:
iiisdo
Et cela imprimerait:
8
Le défi
Créez un programme qui entrera un nombre et affichera le code Deadfish pour afficher le nombre (ou créez une fonction qui prend le nombre en paramètre et renvoie le code). Il doit fonctionner pour tout entier de 0à255
Objectif
Essayez de faire votre code faire le code le plus court possible pour générer le nombre donné. Par exemple:
iiiiiiiiio
et
iiiso
chaque impression 9, mais la seconde est plus courte.
Notation
Ton score est:
The number of characters in your source code +
The sum of the lengths of your output for all numbers from 1-255
-100 if the language you chose is Deadfish :)
Le score le plus bas gagne!
Dans le défi d'origine, je n'avais que la somme de 6 nombres (9,17,99,100 et 123). Cela venait de moi qui voulait ne pas faire tester tout le monde pour chaque numéro, et je voulais que le code le plus court soit pertinent. Ensuite, j'ai réalisé que les programmeurs sont bons pour créer des scripts pour tester des choses comme ça, et je préfère que ce soit un concours pour le meilleur algorithme avec le golf comme bris d'égalité.
C'est pourquoi j'ai changé cela, comme l'a suggéré Martin Büttner.
la source
16^2 = 0ou16^2 = 256ou16^2 = error?-1OU256, il est réinitialisé0. Mais si vous atteignez un nombre supérieur à celui256de la quadrature, il reste inchangé, par exemple17^2 = 289. (voir la page esolang)Réponses:
Perl,
132131 octets + 2036 octets = 2167Comprend +2 pour
-lpExécuter avec le numéro cible sur STDIN, par exemple
deadfish.pl:
Le grep est un filtre pour contraindre un peu l'explosion exponentielle (bien que ce programme ait encore besoin de 2 Go pour les cas difficiles). Il fonctionne également sans mais je ne peux pas l'exécuter sur mon matériel comme ça, sauf pour les cas faciles. Mais en principe, ce
110=108+2programme d'octets fonctionne aussi:Liste de sortie:
la source
ES6 JavaScript 2126 + 311 = score de 2437
Semi-commenté:
Cela profite du fait que dans Deadfish, vous pouvez imprimer plusieurs caractères.
Exemple:
10compile àiodolaquelle est "imprimer un, décrémenter, imprimer zéro".Usage:
Voici les données json de sortie:
Cela a été généré par ce code:
qui imprime
result = (the result)etc =la chose ci-dessus.Cela obtient un score remarquablement élevé malgré sa simplicité. Il recherche le carré parfait le plus proche, calcule la racine carrée de ce carré parfait, ajoute «s» et incrémente / décrémente de manière appropriée.
Ancienne version qui n'utilisait pas le fait que "10" = "imprimer un, imprimer zéro"
la source
dopération - si elle diminue à-1, elle est réinitialisée à0, non255.opasse; il sort l'accumulateur et une nouvelle ligne.iodosorties1\n0\n, non10.o. De nombreux compilateurs (dans différentes langues) n'impriment pas non plus une nouvelle ligne avecoMathematica,
254165 caractères + 3455 = 3620Moins de golf:
Je pense que les chiffres obtenus sont optimaux. Cela effectue une recherche en premier sur les 256 numéros, en gardant une trace de la manière la plus courte trouvée pour représenter chaque numéro. La recherche construit une sorte de table de correspondance dans la fonction
gqui est ensuite appliquée à l'entrée.Pour référence, voici les 255 résultats:
la source
n > 256nonn ≥ 256. Et cela est également conforme à la page esolang: "Bien que le commentaire dans la mise en œuvre C indique/* Make sure x is not greater then [sic] 256 */, la mise en œuvre définit la valeur à zéro si et seulement sivalue == -1 || value == 256."d, ce qui devrait afficher 0.C, code 433 + sortie 3455 = 3888
C ++, code 430 + sortie 3455 = 3885
Et maintenant pour quelque chose de complètement différent.
J'ai utilisé la sortie de la réponse Mathematica de Martin (mise à jour le 23 octobre car elle était incorrecte pour 240+ auparavant). Ma sortie est les mêmes 3455 caractères. J'ai analysé les modèles dans la sortie et découvert que [0,255] peut être représenté par cette séquence:
isssis oudsssiou 0-16dsoL'étape suivante a été de construire soigneusement ces cinq colonnes (à
ctraversgdans le code ci-dessous). J'ai utilisé des nombres négatifs pour indiquerdau lieu deidans les colonneseetg. Ensuite, il s'avère que les résultats fonctionnent principalement comme un compteur dans lagcolonne, car chaque ligne enusupprime généralement undou en ajoute un parirapport à la ligne précédente (v). Il y a 15 exceptions, qui sont stockées dansx(les index) etb(les cinq colonnes, regroupées dans un entier qui ne nécessite que 14 bits pour stocker le maximum10832).Par exemple, la première "exception" est la toute première ligne, où nous voulons zéro caractère en dehors de la fin
o. Donc ,x[0]est0etb[0]est544, qui , lorsqu'il est décompressé (style « little endian », puisquegest la colonne de comptage){ 32, 0, 4, 0, 0 }. Nous soustrayons toujours 32 deget 4 deepour que les champs binaires non signés fonctionnent (c'est-à-dire que ces deux colonnes représentent conceptuellement des nombres négatifs lorsque celadest requis au lieu dei, mais dans l'implémentation, les valeurs sont décalées pour éviter des nombres négatifs réels).Voici un tableau montrant comment fonctionnent les dix premiers nombres (les blancs sont des zéros):
Vous pouvez voir que la
gplupart du temps, juste incrémente de un pour chaque nouvelle ligne, mais certaines lignes (0, 4, 8, ..., que j'espérais trouver brièvement dans OEIS) "réinitialiser" la séquence, ce qui signifiegprend une nouvelle valeur et au moins une autre colonne est également modifiée.Le nombre de caractères de code exclut les espaces, sauf le retour à la ligne obligatoire avant chaque
#et l'espace aprèsunsignedetint. Vous pouvez enregistrer 3 caractères en compilant en C ++ au lieu de C, en remplaçant<stdio.h>par<cstdio>et*(int*)&upar(int&)u.Un fait amusant sur ce code: une version antérieure utilisait un tableau de 256 unions au lieu de juste
uetv. Cette version a provoqué GCC 4.7.2 pour générer une erreur de compilation interne! GCC 4.9 l'a corrigé, cependant, et le code ci-dessus fonctionne avec l'une ou l'autre version.la source
for(...)parscanf- cela diminuerait le nombre de caractères).#include, et peut-être pourriez-vous rendre l'structintérieurunionsans nom.forboucle est toujours requise en raison de la façon dont je calcule le résultat. Ce plus dénommant la structure a sauvé 5 caractères; 2 autres ont été sauvés en changeant==pour>et enlever la nouvelle ligne de fuite. :) Le programme n'est pleinement valide qu'en C99, carmainne renvoie pas explicitement de valeur; la suppression des#includerésultats entraîne une erreur pour l'scanf()instant.256.Haskell,
220021772171 = 2036 + 135cela fonctionne en ayant une liste infinie de tous les programmes de poissons morts, triés par leur longueur, accompagnés de l'état interne et de la sortie. la fonction
frecherche dans la liste et renvoie la première entrée qui correspond.cette approche permet de multiplier
odans chaque code résultant, mais ne la limite pas à l'impression de tous les chiffres séparément ou à l'impression du nombre entier à la fois. par exemple, ici 216 a le code deiiosso.Edit:
selon la spécification, lorsque l'état est 256 (mais pas 257), il est transformé en 0. maintenant mon code en tient compte. par exemple, 160 est
iissoso.cela a quelques problèmes d'efficacité; car
lest une liste de niveau supérieur, dont tous les élémentslqui ont été évalués restent en mémoire, et donc le runtime sera probablement à court de mémoire à un moment donné.pour calculer le score, j'ai fait une version équivalente mais moins gourmande en mémoire.
mon code plus efficace fonctionne en recalculant la liste sur chaque application de
f, afin que le garbage collector puisse jeter la partie déjà recherchée de la liste. en un sens, il s'agit d'une recherche en premier lieu utilisant la paresse.le code plus efficace ajoute également quelques contraintes supplémentaires aux éléments de la liste - il filtre tous les codes qui contiennent
idoudi, ou contient unslorsque l'état est inférieur à 2.Modifier:
J'ai déplacé la
gfonction du niveau supérieur vers une fonction d'aidef', doncgfiltre maintenant les codes qui imprimaient quelque chose qui n'est pas un préfixe de notre numéro souhaité. maintenant le code est beaucoup plus rapide.le code le plus efficace:
notez que le code plus efficace n'aura pas les mêmes résultats car les programmes traversent tous les codes possibles dans un ordre différent. cependant, ils sortiront des codes de la même longueur. aussi, le fait de basculer
c:xavecx++[c]rend les programmes équivalents.avec ce code, j'ai pu calculer tous les programmes
520,81 secondes.Modifier:
apparemment, c'est la meilleure réponse! je l'ai remarqué tout à l'heure, loin de quand cela a été demandé ...
Les resultats:
la source
Picat 516 + 2060 = 2576
Il s'agit d'une version quelque peu modifiée du programme Sergey Dymchenko . Cette version produit des programmes de poissons morts plus compacts.
Pour autant que j'ai compris la phrase "longueurs de sorties", cela signifie que je dois additionner la sortie sans les caractères de nouvelle ligne.
Utilisation:
1-255 Codes:
Performance:
Version du programme pour mesurer le temps:
Résultat:
Sortie complète:
la source
ioiol'imprimerait"12"et non"11"JavaScript (E6) 141 + 3455 = 3596
La fonction récursive recherchant la racine carrée la plus proche, mais en évitant 16 car 16 * 16 = 256 sera changée en 0. Beaucoup d'autres réponses n'obtiennent pas ce point.
Test dans la console FireFox / FireBug
Sortie
la source
Picat, code 242 + sortie 3455 = 3697
Voir http://picat-lang.org/ pour des informations sur Picat.
Moins de golf:
la source
Python 3 - 4286 + 168 = 4454
Pas trop grave, mais extrêmement simple. Trouve juste le meilleur en ajoutant à 0, un carré, un 4 e puissance
et un 8 ème puissance.EDIT: Golfé 75 octets, la 8 e puissance n'a rien fait
EDIT 2: Suppression de quelques octets afin de l'implémenter correctement
d. Le score a cependant augmenté.Python 3 - 2594 + 201 = 2795
Celui-ci utilise une sorte de recherche en profondeur pour trouver le programme le plus court. J'y ai ajouté des optimisations (inutiles?), Afin que je puisse obtenir le résultat; de cette façon, il n'a pas à exécuter autant de chemins. Pourrait essayer d'en supprimer certains. Ne bat pas le JS car il utilise des astuces intelligentes comme plusieurs
o.EDIT: Golfed off 93 bytes, j'avais apparemment un crapton de code inutile laissé là par le développement. A également supprimé tout ce que j'ai trouvé inutile jusqu'à présent. Me voici, JS.
EDIT 2: Golfed outre 8 octets. C'était
returninutile.EDIT 3: Golfé 5 octets supplémentaires. Maintenant que nous nous sommes débarrassés de celui-là, nous pourrions simplement mettre un
elifau lieu de l'autrereturn.EDIT 4: correction de la fonctionnalité de
d. La taille a augmenté de 1 octet, le score de quelques octets.la source
APL: 80 + 3456 = 3536
Explication: (corrigé après la note d'edc65, merci)
⍵ <4: ⍵⍴'i 'Si l'argument est inférieur à 3, répétez "i" autant de fois
(⌈, ⌊) ⍵ * .5 ⍵ est l'argument, prenez racine carrée et prenez le plafond et le sol
| ⍵-2 * ⍨ élever ces plafond et plancher à la puissance 2, supprimer l'argument et rendre positif
b ← ⊃ (>, <, =) / obtenir un vecteur booléen avec a> b, a
(⍵> 240) ⌽ Pour éviter d'aller à 256, faites "i" pour les nombres supérieurs à 240, au lieu de ^ 2
b / 'ids' utilise ce booléen pour prendre i, d ou s et l'ajouter à la solution avec,
, ∇ (-⊃b) + b [2] + ⍵ * ÷ 1 + 3⊃b Appeler récursivement la fonction avec l'argument -b 1 + b [2] élevé à la puissance (inverse de b [3] +1)
Peut compter la sortie avec:
¨ applique la fonction à chaque numéro 0-255
+ / ⊃, / ⍴¨ compte le nombre total d'éléments
Encore une fois, vous pouvez essayer tout ce qui précède sur TryApl.org
BTW: C'est 3456 et non 3455 parce que je considère 0 aussi, car je pense que le problème posait. Si c'est 1-255 alors le score est de 80 + 3455 = 3535
la source
Python 2712 = 2608 + 104
Code:
Utilisation:
0-255 Code:
la source
CJam,
2436 2392 22962173 ( 74 caractères + 2099)Ce qui se traduit par:
Tente d'optimiser la longueur du code Deadfish en choisissant le chemin le plus court pour atteindre chaque chiffre du nombre.
Merci Martin pour la traduction Unicode
Voici la liste complète des codes
Essayez-le en ligne ici:
la source
oimprime une nouvelle ligne. Tous les compilateurs imprimaient également sans nouvelle ligne.C printf("%d\n",x);C# Console.WriteLine(x)GO fmt.Println(x)pascal WRITELN(val);python print accumulator (no comma)bash echo $no;; (no -n)