Contexte

De nombreux langages de programmation ésotériques n'ont pas de nombres intégrés aux littéraux, vous devez donc les calculer au moment de l'exécution; et dans beaucoup de ces cas, la représentation numérique peut être très intéressante. Nous avons déjà eu du mal à représenter les nombres pour Underload. Ce défi consiste à représenter les nombres dans SNUSP modulaire . (Notez que vous n'avez pas besoin d'apprendre SNUSP pour relever ce défi - toutes les informations dont vous avez besoin se trouvent dans les spécifications - mais vous pourriez trouver l'arrière-plan intéressant.)

La tâche

Aux fins de ce défi, un certain nombre modulaire SNUSP est une chaîne formée à partir des caractères @, +et =, à l' exception que le dernier caractère est un #, et que l'avant - dernier caractère doit être +ou =(il ne peut pas être @). Par exemple, les numéros valides comprennent @+#, ==#et @@+@=#; des exemples de numéros non valides comprennent +=, @@#et +?+#.

La valeur d'un numéro SNUSP modulaire est calculée récursivement comme suit:

• # a une valeur de 0 (c'est le cas de base).
• Si le nombre a la forme =x, pour n'importe quelle chaîne x, sa valeur est égale à la valeur de x.
• Si le nombre a la forme +x, pour n'importe quelle chaîne x, sa valeur est égale à la valeur de x, plus 1.
• Si le nombre a la forme @cx, pour tout caractère unique cet toute chaîne x, sa valeur est égale à la valeur de x, plus la valeur de cx.

Pour ce défi, vous devez écrire un programme qui prend un entier non négatif en entrée et génère une chaîne qui est le plus petit nombre SNUSP modulaire possible qui a une valeur égale à l'entrée.

Clarifications

• Il est tout à fait possible qu'il y ait plus d'une chaîne avec la même valeur, et en particulier, pour certains entiers, il y aura une égalité pour le numéro SNUSP modulaire le plus court avec cette valeur. Dans un tel cas, vous pouvez sortir n'importe quel nombre impliqué avec la cravate.
• Il n'y a aucune restriction sur l'algorithme que vous utilisez pour trouver le nombre; par exemple, forcer des chaînes et les évaluer est une tactique légale, mais il en va de même pour réduire l'espace de recherche.
• Comme d'habitude sur PPCG, votre soumission peut être soit un programme complet soit une fonction (choisissez celle qui est la plus concise dans votre langue).
• Ce n'est pas un problème de gestion des formats d'entrée et de sortie, vous pouvez donc utiliser tous les moyens raisonnables pour entrer un entier non négatif et sortir une chaîne. Il existe un guide complet sur les méta , mais les méthodes juridiques les plus couramment utilisées incluent les arguments / retours de fonction, les arguments de ligne de commande et les entrées / sorties standard.

Cas de test

Voici les représentations les plus courtes des premiers nombres:

• 0 :#
• 1 :+#
• 2 :++#
• 3 : +++#ou@++#
• 4 : ++++#ou +@++#ou@=++#
• 5 : @+++#ou@@++#
• 6 : +@+++#ou +@@++#ou @=+++#ou @=@++#ou@@=++#
• 7 : @++++#ou@+@++#
• 8 : @@+++#ou@@@++#
• 9 : +@@+++#ou +@@@++#ou @+++++#ou @++@++#ou @+@=++#ou @@=+++#ou@@=@++#
• 10 : @=@+++#ou @=@@++#ou @@@=++#( c'est un cas de test assez important à vérifier , comme toutes les réponses possibles incluent =)
• 11 : @+@+++#ou @+@@++#ou @@++++#ou@@+@++#
• 12 : +@+@+++#ou +@+@@++#ou +@@++++#ou +@@+@++#ou @=+@+++#ou @=+@@++#ou @=@=+++#ou @=@=@++#ou @=@@=++#ou @@=++++#ou @@=+@++#ou ou@@=@=++#
• 13 : @@@+++#ou@@@@++#
• 14 : +@@@+++#ou +@@@@++#ou @=@++++#ou @=@+@++#ou @@+++++#ou @@++@++#ou@@+@=++#
• 15 : @+@++++#ou @+@+@++#ou @@=@+++#ou @@=@@++#ou @@@=+++#ou@@@=@++#

En cas d'essai plus grande, la sortie de l' entrée 40 doit être @@@=@@+++#, @@@=@@@++#, @@@@=@+++#, ou @@@@=@@++#.

Condition de victoire

En tant que défi de code-golf , le gagnant est l'entrée la plus courte, mesurée en octets.

Oracle SQL 11.2, 341 262 octets

WITH e AS(SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4),n(s,v,p,c,i)AS(SELECT'#',0,0,e,1 FROM e UNION ALL SELECT c||s,DECODE(c,'+',1,'@',p,0)+v,v,e,i+1 FROM n,e WHERE i<11)CYCLE s SET y TO 1 DEFAULT 0 SELECT s FROM n WHERE:1=v AND rownum=1;

Ancienne version

WITH e AS(SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4),n(s,v,p,c) AS(SELECT'#',0,0,e FROM e UNION ALL SELECT s||c,CASE c WHEN'+'THEN 1 WHEN'='THEN 0 WHEN'@'THEN p ELSE 0 END+v,v,e FROM n,e WHERE LENGTH(s)<10)CYCLE s SET y TO 1 DEFAULT 0 SELECT MIN(REVERSE(s))KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s))FROM n WHERE v=:1;

: 1 le nombre à représenter en SNUSP modulaire

Non golfé:

WITH e AS (SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4),  
n(s,v,p,c,i) AS                   
(
  SELECT '#',0,0,e,1 FROM e
  UNION ALL
  SELECT s||c
       , DECODE(c,'+',1,'@',p,0)+v 
       , v
       , e
       , i+1
  FROM n,e
  WHERE i<11
) CYCLE s SET y TO 1 DEFAULT 0
SELECT s FROM n WHERE:1=v AND rownum=1;

Créez d'abord une vue avec 3 lignes, une pour chaque symbole utilisé pour représenter les nombres, moins # qui n'est utilisé qu'à la fin de la chaîne:

SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4;    

Ensuite, la vue récursive n génère chaque chaîne possible avec ces 3 symboles, les concatène à # et les évalue.

Les paramètres sont:

s: la représentation SNUSP modulaire du nombre évalué
v: la valeur décimale de s calculée par l'itération précédente
p: v calculée par l'itération i-2
c: le symbole suivant à concaténer à s
i: la longueur de s, uniquement nécessaire pour se débarrasser de deux LONGUEUR () à des fins de golf

DECODE(c,'+',1,'@',p,0)+v 

Si le dernier symbole est +, ajoutez 1
Si c'est @, ajoutez la valeur de l'itération i-2
Sinon, le symbole est soit # soit =. v est initialisé avec 0 dans la partie init de la vue récursive, donc le nouveau v est égal au v précédent dans les deux cas.

WHERE i<11

Chaque chaîne possible avec les 3 symboles est calculée, cette partie assure que la requête ne s'exécute pas avant le gros crunch.

CYCLE s SET y TO 1 DEFAULT 0

Puisqu'il n'y a pas de règle pour la construction des chaînes, des doublons sont liés. Étant dans une vue récursive, Oracle interprète ces doublons comme des cycles et génère une erreur si le cas n'est pas explicitement pris en charge.

SELECT s FROM n WHERE:1=v AND rownum=1;

Renvoie la première représentation SNUSP modulaire qui correspond au nombre décimal entré comme paramètre: 1

Dans mes tests, cette première ligne est toujours l'une des représentations les plus courtes.

Dans le cas où votre base de données n'agirait pas de la même manière, cette dernière clause devrait être remplacée par

SELECT MIN(s)KEEP(DENSE_RANK FIRST ORDER BY i)FROM n WHERE:1=v

JavaScript (ES6), 100 octets

n=>eval("for(a=[['#',0,0]];[[s,t,p],...a]=a,t-n;)a.push(['='+s,t,t],['+'+s,t+1,t],['@'+s,t+p,t]);s")

Algorithme de recherche simple en largeur par force brute.

Pyth, 41 octets

L?b+ytb@[yttb001)Chb0+hfqQyTs^L"+@="UhQ\#

Suite de tests

Comment ça fonctionne:

Il y a deux parties. Une fonction récursive qui calcule la valeur d'une expression SNUSP sans le suivi #et une routine de force brute.

Évaluation:

L?b+ytb@[yttb001)Chb0
L                        Define the function y(b) as follows
 ?b                      If b is nonempty
   +ytb                  The sum of y(tail(b)) and   # tail(b) = b[1:]
   @[       )            The element in the list at location
   Chb                   Character values of the first character.
                         Modular indexing means that 
                         + -> 3
                         @ -> 0
                         = -> 1
                         Index 2 is filler.
    [yttb001)            @ adds y(tail(tail(b)). Tail suppresses the error when
                         called on an empty list, so this treats @# as zero, but
                         this can't lead to problems because removing the @ will
                         always make the expression shorter.
                         + adds 1, = adds 0.
 0                       If b is the empty string, return 0

Force brute:

+hfqQyTs^L"+@="UhQ\#
               UhQ      0 ... Q     # Q is the input
        ^L"+@="         Map that list to all strings formed from the characters
                        "+@=", with that many characters.
       s                Concatenate
  fqQyT                 Filter for strings which evaluate to the input
 h                      Take the first success, which is the shortest due to
                        the order the strings were generated.
+                 \#    Add a '#' and output

CJam, 58

ri:M;'#0_]]{_{M&}#_)!}{;{~[2,+1$f+"@=+"\]z\f+\af.+~}%}w=0=

Force brute, avec un peu d'inspiration dans la réponse de Neil. Essayez-le en ligne

Version efficace, 107

ri0"#"a{_{:B\:A={'=A0j+}{A(B={'+B0j+}{AB>{BAB-j_N={'@\+}|}N?}?}?}{;_(0j'+\+a\,1>_W%.{j}Na-'@\f++{,}$0=}?}2j

Essayez-le en ligne

Cela utilise une programmation dynamique.

Haskell , 89 86 octets

ÉDITER:

• -3 octets: la fermeture éclair était plus courte que l'indexation.

Une autre solution de force brute qui s'est soldée par une grande inspiration de la réponse de Neil. (Bien qu'il fonctionnait plus comme le Pyth d'Isaacg avant que le golf ne présente le l.)

f n=[s|(a,_,s)<-l,a==n]!!0
l=(0,0,"#"):[(a+c,a,d:s)|(a,b,s)<-l,(c,d)<-zip[0,1,b]"=+@"]

Essayez-le en ligne!

• f est la fonction principale, qui prend un entier et renvoie une chaîne.
• lest une liste infinie de tuples (a,b,s), les représentations les plus courtes en spremier, ainsi que leur valeur aet la valeur bde la représentation avec le premier caractère supprimé. (comme d'autres l'ont également noté / remarqué, il est inoffensif de traiter ce dernier comme 0 pour #.)
• Les éléments lautres que le premier sont générés récursivement avec une compréhension de liste. dest le caractère à ajouter pour sgénérer une nouvelle représentation dans la liste, et «c» est l'incrément correspondant à a.