10
\$\begingroup\$

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 challenge, the winner is the shortest entry, measured in bytes.

\$\endgroup\$
  • 1
    \$\begingroup\$ = will optimally only occur as @=, right? \$\endgroup\$ – orlp Jan 15 '17 at 17:28
  • 3
    \$\begingroup\$ By the way, these kind of challenges are usually best posted as metagolf, as there hardly will be any interesting answer (just evaluate string and loop over all possible strings). \$\endgroup\$ – orlp Jan 15 '17 at 17:35
  • 3
    \$\begingroup\$ @orlp: I disagree, this challenge would be too easy as a metagolf, as finding an optimal answer is relatively easy, and metagolf doesn't place any other restrictions on the scoring. I'm expecting most of the answers here to be brute-force, but the specification is complex enough that brute force a) might not be shortest, and b) is likely to be interesting to golf in its own right. If you wanted a change in the victory condition, likely the only other interesting one is fastest-code, and that'd make more sense as a different challenge. \$\endgroup\$ – user62131 Jan 15 '17 at 17:55
  • \$\begingroup\$ We have also had a number golf challenge for Brain-flak as well \$\endgroup\$ – ASCII-only May 17 '17 at 5:29
3
+50
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ For 40 it returns "@@@@@@=++#" which evaluates to 42 \$\endgroup\$ – aditsu Jan 24 '17 at 17:18
  • \$\begingroup\$ Even for 12 it gives "@@@+++#" which evaluates to 13 \$\endgroup\$ – aditsu Jan 24 '17 at 17:54
  • \$\begingroup\$ Hmm, I think changing t<n to t-n might work... \$\endgroup\$ – Neil Jan 24 '17 at 19:34
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy