13
\$\begingroup\$

Gelatin is a worse version of Jelly. It is a tacit programming language that always takes a single integer argument and that has 7 (or maybe 16) commands. You are to take in a Gelatin program and its argument and output the result.

Gelatin

Gelatin programs will always match the following regex:

^[+_DSa\d~]*$

i.e. they will only contain +_DSa0123456789~ characters. The commands in Gelatin are:

  • Digits return their value (0 is \$0\$, 1 is \$1\$ etc.) Digits are stand alone, so 10 represents \$1\$ and \$0\$, not \$10\$
  • a returns the argument passed to the Gelatin program
  • D takes a left argument and returns it minus one (decremented)
  • S takes a left argument and returns its square
  • + takes a left and a right argument and returns their sum
  • _ takes a left and a right argument and returns their difference (subtract the right from the left)
  • ~ is a special command. It is always preceded by either + or _ and it indicates that the preceding command uses the same argument for both the left and the right.

Each command - aside from ~ - in Gelatin has a fixed arity, which is the number of arguments it takes. Digits and a have an arity of \$0\$ (termed nilads), D and S have an arity of \$1\$ (termed monads, no relation) and + and _ have an arity of \$2\$ (termed dyads)

If + or _ is followed by a ~, however, they become monads. This affects how the program is parsed.

Tacit languages try to avoid referring to their arguments as much as possible. Instead, they compose the functions in their code so that, when run, the correct output is produced. How the functions are composed depends on their arity.

Each program has a "flow-through" value, v and an argument ω. v is initially equal to ω. We match the start of the program against one of the following arity patterns - earliest first, update v and remove the matched pattern from the start. This continues until the program is empty:

  • 2, 1: This is a dyad d, followed by a monad M. First, we apply the monad to ω, yielding M(ω). We then update v to be equal to d(v, M(ω)).
  • 2, 0: This is a dyad d, followed by a nilad N. We simply update v to be d(v, N)
  • 0, 2: The reverse of the previous pattern, v becomes d(N, v)
  • 2: The first arity is a dyad d, and it's not followed by either a monad or a nilad as it would've been matches by the first 2. Therefore, we set v to be d(v, ω)
  • 1: The first arity is a monad M. We simply set v to be M(v)

For example, consider the program +S+~_2_ with an argument 5. The arities of this are [2, 1, 1, 2, 0, 2] (note that +~ is one arity, 1). We start with v = ω = 5:

  • The first 2 arities match pattern 2, 1 (+S), so we calculate S(ω) = S(5) = 25, then calculate v = v + S(ω) = 5 + 25 = 30
  • The next arity matches pattern 1 (+~). +~ means we add the argument to itself, so we double it. Therefore, we apply the monad to v, updating it to v = v + v = 30 + 30 = 60
  • The next arity pattern is 2, 0 (_2), which just subtracts 2, updating v to v = v - 2 = 60 - 2 = 58
  • Finally, the last arity pattern is 2 (_), meaning we update v to be v = v - ω = 58 - 5 = 53.
  • There are now no more arity patterns to match, so we end the program

At the end of the program, Gelatin outputs the value of v and terminates.

In a more general sense, +S+~_2_ is a function that, with an argument \$\omega\$, calculates \$2(\omega + \omega^2) - 2 - \omega = 2\omega^2 + \omega - 2\$.


You are to take a string representing a Gelatin program, using the characters specified above, and a positive integer \$\omega\$ and output the result of running the Gelatin program with an argument of \$\omega\$

You may assume that the arities of the program will always fit one of the 5 patterns (so nothing like S1S (1, 0, 1) will appear), and that the flow-through value will never exceed your language's integer bounds. The output may be negative.

This is so the shortest code in bytes wins

Test cases

Program         ω              out
+S              7              56            
_aSS+           20             20            
++DDDS+1_       15             1750          
_S              13             -156          
D0+             12             11            
_+~SSS++__S++a  6              1679598       
_++a            17             34            
a+_6D           20             33            
D+_+_aD         17             15  
                5              5
DD              8              6              
+_aa+S+SS+_+    4              6404           
+9+S_           19             370            
_DDD+_a+_3_4D_  13             -9             
SS_SD+          15             50414          
+~D_~_          7              -7             
D_a+S           10             99             
_S+aD+4         1              4              
+_a+            3              6   
_aD+60+         13             5   

This is a program that randomly generates \$n\$ Gelatin programs, along with random inputs and the intended outputs

\$\endgroup\$
5
  • \$\begingroup\$ Brownie points for beating or matching my 16 byte Jelly answer \$\endgroup\$ – caird coinheringaahing Apr 26 at 22:41
  • \$\begingroup\$ Next challenge: given an integer \$n\$, output the smallest Gelatin program that outputs \$n\$. \$\endgroup\$ – Arnauld Apr 27 at 14:44
  • 3
    \$\begingroup\$ @Arnauld Almost :P \$\endgroup\$ – caird coinheringaahing Apr 27 at 14:45
  • \$\begingroup\$ Oh! I was just editing my comment to take ω into account but ... nevermind. :-p \$\endgroup\$ – Arnauld Apr 27 at 14:46
  • \$\begingroup\$ These brand knock-offs are getting out of hand… \$\endgroup\$ – xigoi Apr 28 at 6:35
10
\$\begingroup\$

JavaScript (ES6),  306 ... 227  226 bytes

Expects (program)(ω).

s=>g=(v,w=v,n=0,h=_=>(O={a:w,'+':"x+y",_:"x-y",S:"x*x",D:"x-1",'+~':"x*2",'_~':"0"}[c=(s+'a').match(/.~?/g)[n++]]||+c)[2]>O?2:O>g)=>(I=h(i=h(E=(o,x,y)=>eval(o)),o=O),o)?g(i?E(o,v,I?I-2?E(O,w):w:O):I?E(O,o,v):v,w,n-=i==I|i&1):v

Try it online!

Commented

Header and helper function h

s =>                 // outer function taking the program string s
g = (                // g = inner recursive function taking:
  v,                 //   v = current output value
  w = v,             //   w = initial value of v (aka ω)
  n = 0,             //   n = pointer in the command stream
  h = _ => (         //   h is a helper function which turns the next
                     //   command into a JS code snippet or an integer,
                     //   along with the arity of the command:
    O = {            //     1) command:
      a   : w,       //       'a' : use w
      '+' : "x+y",   //       '+' : add y to x
      _   : "x-y",   //       '_' : subtract y from x
      S   : "x*x",   //       'S' : square x
      D   : "x-1",   //       'D' : decrement x
      '+~': "x*2",   //       '+~': double x
      '_~': "0"      //       '_~': yield 0
    }[               //
      c = (s + 'a')  //       append an explicit 'a' command at the end
      .match(/.~?/g) //       split the commands (either "x" or "x~")
      [n++]          //       load the next command into c
    ]                //
    || +c            //       if the above is undefined, use +c (it's a digit)
  )                  //     2) arity of the command:
  [2] > O ? 2        //       dyad if the 3rd character is 'y'
          : O > g    //       monad if it's a code snippet, or nilad otherwise
) =>                 //

Body of g

( I =                // (O, I) = (2nd command, 2nd arity)
  h( i =             // (o, i) = (1st command, 1st arity)
    h( E =           // E is a helper function
      (o, x, y) =>   //   which takes o, x, y
        eval(o)      //   and evaluates o in this local context
    ),               //
    o = O            //
  ),                 //
  o                  // we eventually test o
) ?                  // if o is defined:
  g(                 //   do a recursive call to g:
    i ?              //     if the 1st command is not a nilad:
      E(             //       v = result of a call to E with:
        o,           //         the 1st command
        v,           //         x = v
        I ?          //         if the 2nd command is not a nilad:
          I - 2 ?    //           if the 2nd command is a monad:
            E(O, w)  //             y = result of the 2nd command as a monad
          :          //           else (the 2nd command is a dyad):
            w        //             y = w
        :            //         else:
          O          //           y = O
      )              //       end of call
    :                //     else (the 1st command is a nilad):
      I ?            //       if the 2nd command is not a nilad:
        E(O, o, v)   //         v = result of the 2nd command as a dyad
      :              //       else:
        v,           //         v is left unchanged
    w,               //     pass w unchanged
    n -=             //     decrement n if only one command was 'consumed':
      i == I | i & 1 //       i.e. if i = I or i is odd
  )                  //   end of recursive call
:                    // else:
  v                  //   we're done: return the final output value
\$\endgroup\$
2
  • \$\begingroup\$ You can save 1 byte by defining an extra function for calling E(o,v,<something>): s=>g=(v,a=(w=v,s+'a').match(/.~?/g),F=(v,n=1)=>g(v,a.slice(n)),E=(o,x,y)=>eval(o),h=n=>[q={a:w,'+':"x+y",_:"x-y",S:"x*x",D:"x-1",'+~':"x*2",'_~':"x*0"}[s=a[n]]||+s,q[2]>q?2:q>g],G=p=>E(o,v,p),[o,i]=h(0),[O,I]=h(1))=>a+a?i?i-2?F(G()):I?I-2?F(G(E(O,w)),2):F(G(w)):F(G(O),2):I?F(E(O,o,v),2):F(v):v is 294 bytes. \$\endgroup\$ – A username Apr 27 at 12:35
  • \$\begingroup\$ @Ausername Thanks for the suggestion. But I rewrote this part entirely. \$\endgroup\$ – Arnauld Apr 27 at 12:39
9
\$\begingroup\$

Jelly, 15 bytes

⁾D’y“S²a⁸~`”yKv

Try it online!

⁾D’y               Substitute D for Jelly's decrement builtin.
                   (This is done alone because ’ is a string terminator.)
    “      ”y      Substitute
     S²            S for square,
       a⁸          a for left argument,
         ~`        and ~ for reuse argument.
                   (+ and _ are already plus and minus.)
             K     Join the program on spaces to split up multi-digit numbers,
              v    and evaluate it as Jelly with the right argument as its sole argument.
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Ah, substituting twice, clever! I had this \$\endgroup\$ – caird coinheringaahing Apr 26 at 23:05
  • 1
    \$\begingroup\$ @cairdcoinheringaahing It didn't even occur to me that you'd need ¤ for a single substitution--I figured I shaved a byte off you by thinking to use K :P \$\endgroup\$ – Unrelated String Apr 26 at 23:08
6
\$\begingroup\$

Charcoal, 147 bytes

Nθ≔θζF⁺⪫⪪⪫⪪S+~¦d¦_~¦z¦i«≡№DSdiz++__鲫F⁼²Lυ⊞υθF²⊞υ⎇⊖Lυζι»¹«≔⎇υθζε≡ιD≦⊖εS≦×εεd≦⊗εz≦⁻εε⎚¿υ⊞υε≔εζ»⊞υ⎇⁼aιθIι¿‹²Lυ«≔⎇⁼+§υ¹⁺§υ⁰§υ²⁻§υ⁰§υ²ζ≔…⟦ζι⟧⁻Lυ³υ»»Iζ

Try it online! Link is to verbose version of code. Takes the argument as the first input and the script as the second input. Explanation:

Nθ≔θζ

Input the argument and copy it to the flow-though value.

F⁺⪫⪪⪫⪪S+~¦d¦_~¦z¦i«

Transform the script by replacing the +~ and _~ operators with single-byte operators and appending the identity operator (in case the script ends with a dyadic operator). Loop over each operator.

≡№DSdiz++__ι

See how many arguments this operator expects.

²«F⁼²Lυ⊞υθF²⊞υ⎇⊖Lυζι»

If this is a dyad, then if there is already a dyad on the stack then push the argument as its RHS. Push the flow-through value and the dyad, ensuring that the dyad is between its operands. Note that the flow-through value is incorrect if there is already a dyad on the stack but that will be fixed up later.

¹«≔⎇υθζε≡ιD≦⊖εS≦×εεd≦⊗εz≦⁻εε⎚¿υ⊞υε≔εζ»

If this is a monad, then get either the flow-through value or the argument (depending on whether there is a dyad on the stack), apply the monad to it, then save it to the flow-through value or the stack (again depending on whether there is a dyad on the stack).

⊞υ⎇⁼aιθIι

Otherwise push either the argument (if this is an a operator) or the numeric value of the digit to the stack, assuming that the next operator is a dyad.

¿‹²Lυ«

If we now have a dyad with both its arguments on the stack, then:

≔⎇⁼+§υ¹⁺§υ⁰§υ²⁻§υ⁰§υ²ζ

Update the flow-through value with the result of the dyad.

≔…⟦ζι⟧⁻Lυ³υ

If there were in fact two dyads on the stack, then recalculate the stack with the new flow-through value and the current dyad, otherwise clear the stack.

»»Iζ

Once the script has been processed output the final flow-through value.

\$\endgroup\$
3
\$\begingroup\$

Pip, 129 bytes

YaLRqR"+~_~_"<>2;^"TZ-"`\W\w?|[A-Z]|..`Y V$0R['^.XU`([A-Z]|^.)$`][`&y``&a`]R(^"DSTZ").CXX'Y.[B.vB.'*.B"2*".B0]R`\W$`_.yR`^\W`y._y

Try it online!

How?

We're basically going to use a translate-and-eval approach. Unlike Jelly (cough), Pip's execution model is rather different from Gelatin's, so the translation takes some work. We are fortunate in some ways: 0-9 and + can be used as they are, and so can a if we take the input number as a command-line argument.

Ya

Copy the input number into y, which will be our flow-through value.

qR"+~_~_"<>2;^"TZ-"

Read the Gelatin program from stdin and make some substitutions: +~ -> T (for Twice, since x+x = 2*x), _~ -> Z (for Zero, since x-x = 0), and _ -> - (so we can eval it later). After these substitutions, we have two dyads (+ and -), four monads (D, S, T, and Z), and eleven nilads (0 through 9, plus a). Note that all monads are capital letters. Note also that both dyads are symbols, whereas all monads and nilads are alphanumeric.

LR  ...  `\W\w?|[A-Z]|..`

Parse the arity patterns with regex and loop over all matches. The first branch \W\w? matches a dyad followed by a monad, nilad, or nothing; the second branch [A-Z] matches a single monad; and the third branch .. matches two characters, which in practice is the only remaining case, a nilad followed by a dyad.

$0R['^.XU`([A-Z]|^.)$`][`&y``&a`]

Starting from the arity pattern stored in the match variable $0, we make some more replacements. This stage adds the right argument for monads and for solitary dyads: A monad at the beginning of the pattern must be pattern 1; its argument should be y, the flow-through value. After that replacement, any other monad (pattern 2,1) or any other single character (pattern 2) should have a right argument of a, the input number.

...  R(^"DSTZ").CXX'Y.[B.vB.'*.B"2*".B0]

Next, we replace monads with the appropriate Pip expressions: Dx (here x represents the right argument, either y or v) becomes Yx-1; Sx becomes Yx*x; Tx becomes Y2*x; and Zx becomes Y0. (The Y enforces correct precedence of operations in the 2,1 pattern.)

...  R`\W$`_.yR`^\W`y._

Finally, we fill in the missing argument of each dyad. An operator at the end of the pattern is a dyad with a left argument (pattern 0,2), so its right argument should be y, the flow-through value. An operator at the beginning of the pattern is a dyad with a right argument (pattern 2,0 or 2,1 or 2), so its left argument should be `y.

Y V  ...

Evaluate the resulting expression as Pip code, and store the result back into y.

y

After the loop, output the final value of y.

\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Unicode), 193 bytes (SBCS)

B M N←'(?<!⍨)([+_])' '(D|S|⍨[+_])' '[0-9⍵]'
_←-⍨
S←×⍨
D←¯1∘+
{(⍎'{','⍵}',⍨'.'⎕R' \0 '⌽(B,M)(B,N)(∊'('N')'B)(∊B'(?!'N'|'M')')⎕R')⊢\1)⍵\2((' ')⊢\0(' ')⊢⍨\2\1(' ')⊢\0⍵('⊢'a' '(.)~'⎕R'⍵' '⍨\1'⊢⍺)⍵}

Try it online!

Takes the program on the left and the argument on the right. I figured this'd be easy with APL's trains and regex, but apparently not ⍨.

⍝ Regexes (regices?) for dyads (B), monads (M), and nilads (N)
B M N←'(?<!⍨)([+_])' '(D|S|⍨[+_])' '[0-9⍵]'
_←-⍨ ⍝ The _ dyad (flipped because APL is RTL)
S←×⍨ ⍝ The S monad (multiply with itself)
D←¯1∘+ ⍝ The D monad (add -1 to decrement)

The actual function:

{(⍎'{','⍵}',⍨'.'⎕R' \0 '⌽(B,M)(B,N)(∊'('N')'B)(∊B'(?!'N'|'M')')⎕R')⊢\1)⍵\2((' ')⊢\0(' ')⊢⍨\2\1(' ')⊢\0⍵('⊢'a' '(.)~'⎕R'⍵' '⍨\1'⊢⍺)⍵}

First 'a' '(.)~'⎕R'⍵' '⍨\1'⊢⍺ replaces a with and +~ and _~ with ⍨+ and ⍨_. This is just to make life simpler later. The next part is

(B,M)(B,N)(∊'('N')'B)(∊B'(?!'N'|'M')')⎕R')⊢\1)⍵\2((' ')⊢\0(' ')⊢⍨\2\1(' ')⊢\0⍵('

This may look like a mess, but it's actually pretty simple:

  • The pattern BM (dyad, monad) becomes ((M⍵)B⊢), but reversed.
  • The pattern BN (dyad, nilad) becomes (NB⊢), but reversed.
  • The pattern NB (nilad, dyad) becomes (NB⍨⊢), but reversed.
  • The pattern B (dyad not followed by a nilad or monad) becomes (⍵B⊢), but reversed.
  • Monads not preceded by dyads are left as is.

This is pretty much an exact translation of the rules in the question. After this, reverses everything because unlike Jelly, APL goes from right to left (this is also why _ takes its arguments reversed). Then '.'⎕R' \0 ' puts a space on each side of each character so that APL doesn't throw up the result thinking SD is a single token. Then the result r is turned into {r⍵} and evaluated to obtain a dfn. This function is applied to the outer function's right argument, .

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.