Find the shortest representation of a number in Modular SNUSP

Question

Background

Many esoteric programming languages don't have numbers built in at literals, so you have to calculate them at runtime; and in many of these cases, the number representation can be quite interesting. We've already had a challenge about representing numbers for Underload. This challenge is about representing numbers in Modular SNUSP. (Note that you don't need to learn SNUSP in order to complete this challenge – all the information you need is in the specification – but you might find the background interesting.)

The task

For the purpose of this challenge, a Modular SNUSP number is a string formed out of the characters @, +, and =, except that the last character is a #, and that the penultimate character must be + or = (it cannot be @). For example, valid numbers include @+#, ==#, and @@+@=#; examples of invalid numbers include +=, @@#, and +?+#.

The value of a Modular SNUSP number is calculated recursively as follows:

• # has a value of 0 (this is the base case).
• If the number has the form =x, for any string x, its value is equal to the value of x.
• If the number has the form +x, for any string x, its value is equal to the value of x, plus 1.
• If the number has the form @cx, for any single character c and any string x, its value is equal to the value of x, plus the value of cx.

For this challenge, you must write a program that takes a nonnegative integer as input, and outputs a string that's the shortest possible Modular SNUSP number that has a value equal to the input.

Clarifications

• It's entirely possible that there will be more than one string with the same value, and in particular, for some integers there will be a tie for the shortest Modular SNUSP number with that value. In such a case, you may output any of the numbers involved wit the tie.
• There's no restriction on the algorithm you use to find the number; for example, brute-forcing strings and evaluating them is a legal tactic, but so is doing something cleverer to reduce the search space.
• As usual on PPCG, your submission may be either a full program or a function (pick whichever is more concise in your language).
• This isn't a problem about handling input and output formats, so you can use any reasonable means to input a nonnegative integer and output a string. There's a full guide on meta, but the most commonly used legal methods include function arguments/returns, command line arguments, and standard input/standard output.

Test cases

Here are the shortest representations of the first few numbers:

• 0: #
• 1: +#
• 2: ++#
• 3: +++# or @++#
• 4: ++++# or +@++# or @=++#
• 5: @+++# or @@++#
• 6: +@+++# or +@@++# or @=+++# or @=@++# or @@=++#
• 7: @++++# or @+@++#
• 8: @@+++# or @@@++#
• 9: +@@+++# or +@@@++# or @+++++# or @++@++# or @+@=++# or @@=+++# or @@=@++#
• 10: @=@+++# or @=@@++# or @@@=++# (this is a fairly important test case to check, as all the possible answers include =)
• 11: @+@+++# or @+@@++# or @@++++# or @@+@++#
• 12: +@+@+++# or +@+@@++# or +@@++++# or +@@+@++# or @=+@+++# or @=+@@++# or @=@=+++# or @=@=@++# or @=@@=++# or @@=++++# or @@=+@++# or @@=@=++#
• 13: @@@+++# or @@@@++#
• 14: +@@@+++# or +@@@@++# or @=@++++# or @=@+@++# or @@+++++# or @@++@++# or @@+@=++#
• 15: @+@++++# or @+@+@++# or @@=@+++# or @@=@@++# or @@@=+++# or @@@=@++#

As a larger test case, the output from input 40 should be @@@=@@+++#, @@@=@@@++#, @@@@=@+++#, or @@@@=@@++#.

Victory condition

As a code-golf challenge, the winner is the shortest entry, measured in bytes.

Answer 1

Oracle SQL 11.2, 341 262 bytes

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;

Old 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 the number to represent in Modular SNUSP

Un-golfed :

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;

First create a view with 3 lines, one for each symbol used to represent numbers, minus # which is only used at the end of the string :

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

Then the recursive view n generates every string possible with those 3 symbols, concatenates them to # and evaluates them.

The parameters are :

s : the Modular SNUSP representation of the number being evaluated
v : the decimal value of s computed by the previous iteration
p : v computed by the i-2 iteration
c : the next symbol to concatenate to s
i : the length of s, only needed to get rid of two LENGTH() for golfing purpose

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

If the last symbol is + then add 1
If it is @ add the value of the i-2 iteration
Else the symbol is either # or =. v is initialised with 0 in the init part of the recursive view, so the new v is equal to the previous v in either case.

WHERE i<11

Every string possible with the 3 symbols is computed, this part insure that the request does not run until the big crunch.

CYCLE s SET y TO 1 DEFAULT 0

Since there is no rule to the construction of the strings, duplicates are bound to arise. Being in a recursive view Oracle interprets those duplicates as cycles and throw an error if the case is not explicitly taken care of.

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

Returns the first Modular SNUSP representation that evaluate to the decimal number entered as parameter :1

In my tests that first line is always one of the shortest representations.

In the case your database would not act in the same way, then that last clause should be replaced with

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

Answer 2

JavaScript (ES6), 100 bytes

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")

Simple brute-force breadth-first search algorithm.

Answer 3

Pyth, 41 bytes

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

Test suite

How it works:

There are two parts. A recursive function which calculates the value of a SNUSP expression without the trailing #, and a brute force routine.

Evalutaion:

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

Brute force:

+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

Answer 4

CJam, 58

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

Brute force, with a little inspiration from Neil's answer. Try it online

Efficient version, 107

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

Try it online

This uses dynamic programming.

Answer 5

Haskell, 89 86 bytes

EDIT:

• -3 bytes: zipping was shorter than indexing.

Another brute force solution which ended up with a lot of inspiration from Neil's answer. (Although it worked more like isaacg's Pyth before golfing introduced the 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]"=+@"]

Try it online!

• f is the main function, which takes an integer and returns a string.
• l is an infinite list of tuples (a,b,s), shortest representations s first, together with their value a and the value b of the representation with the first char stripped. (as others have also noted/noticed, it's harmless to treat the latter as 0 for #.)
• The elements of l other than the first one are generated recursively with a list comprehension. d is the character that is to be prepended to s to generate a new representation in the list, and 'c' is the corresponding increment to a.