18
\$\begingroup\$

Introduction

Forte is a very peculiar esoteric language based on the concept of modifying the values of numbers. In Forte numbers are not constants but variables, you can use the LET instruction to assign new values to them.

For example, after executing LET 2=4-1 from now on 2 assumes the value of 3, which means that whenever the value 2 comes up in an expression it is instead "replaced" by 3. The expression (1+1)*2 would now evaluate to 9.

This instruction in Forte is used both for storing information and for flow control (lines are numbered and by changing the value of their numbers you can determine the order of their execution). In this challenge we will not deal with this second aspect.

The challenge

You are required to write an interpreter for a simplified subset of Forte's LET expressions.

You will receive as input a series of lines following this grammar:

<line>::= <number>=<expression>

<expression>::= <number>|<expression>+<number>

Note: this grammar is not valid Forte because it lacks line numbers, LET, and parentheses (which are always mandatory)

That is, you will only need to deal with computing summations and assigning values to numbers. Parentheses won't be present in the input, and each expression will need to be evaluated from left to right: beware that partial results are affected by redefinitions!

Numbers will always be non-negative integers, up to the limit of your language's native integer type (or 2^32, whichever is higher).

For each line you should output the result of the expression and assign this result to the (possibly reassigned) value of the first number, which will affect how the following lines will be interpreted.

This is , the shortest code (in bytes) wins!

Other rules

  • The input format is flexible, you can for example take a single string with newlines, a list of strings, a list of lists of numbers... The same goes for the output, as long as it's clear what's the result of each expression in the input.
  • You may submit either a function, a full program, or a solution to be run in a REPL environment calling it once for each line.
  • Standard loopholes are forbidden, in particular you can't call an external Forte interpreter in your code.

Examples

These are all part of the same input. After each line the expected output relative to that line is shown, sometimes with a comment indicating relevant reassignments (not part of the required output).

5=4
4
6=5
4        # 5 -> 4
7=1+2+5
7
7=5+2+1
4        # Order of operations matters! 5+2 -> 4+2 -> 6 -> 4
18=5+6+7
12
5=3
3        # Remember: 5 -> 4
10=6+4
3        # 6 -> 4 -> 3, 3+3 = 6 -> 3
\$\endgroup\$
  • \$\begingroup\$ Is 0 a valid number? \$\endgroup\$ – orlp Apr 9 '17 at 9:09
  • \$\begingroup\$ @orlp 0 is valid ("Numbers will always be non-negative integers") \$\endgroup\$ – Leo Apr 9 '17 at 9:16
  • \$\begingroup\$ Should we accept any arithmetic operators? \$\endgroup\$ – bacchusbeale Apr 9 '17 at 9:19
  • \$\begingroup\$ @bacchusbeale No, just summation. \$\endgroup\$ – Leo Apr 9 '17 at 9:21
  • \$\begingroup\$ Is there any particular maximum number, or is it as big as the language's native integer type is? Also, it would be invalid output to return a list of numbers, one of which is the result, right? (such as printing the dictionary/map for which number goes to which number) \$\endgroup\$ – zgrep Apr 13 '17 at 11:47
4
\$\begingroup\$

Jelly, 28 bytes

®y$ÐL
ṪÇ+Ç¥/Ṅ;®⁸Ǥ;©
⁸©ḷƓÇ€¤

Try it online!

This is one of the few Jelly programs where it seems to be terser to take input from standard input. It's a full program (writing a function would have been shorter but is banned by PPCG rules, because it wouldn't run correctly the second time). The input format looks like this:

[[5,[4]],[6,[5]],[7,[1,2,5]],[7,[5,2,1]],[18,[5,6,7]],[5,[3]],[10,[6,4]]]

Explanation

Helper function 1Ŀ (translate an integer to its value)

®y$ÐL
   ÐL   Repeatedly, until there are no further changes,
  $       apply the following unary function to {the input}:
 y          replace values using the mapping table
®             stored in the register.
        {Then return the eventual result.}

Rather conveniently, this helper function will work correctly either on a single value, or a list of values, due to the way y is defined. If more than one mapping is given for a single value, we take the first mapping from the table. The mapping table is stored in the register (which is basically just a variable; Jelly only has one variable).

Helper function 2Ŀ (evaluate one LET instruction)

ṪÇ+Ç¥/Ṅ;®⁸Ǥ;©
Ṫ               On the last element of {the input},
 Ç              Run 1Ŀ,
     /          left fold it via
    ¥             the following binary function:
  +                 add {the two arguments}
   Ç                and run 1Ŀ on {the result},
      Ṅ         write {the result} (and a newline) to standard output,
       ;®       append the value of the register,
            ;   prepend
           ¤      the following value:
         ⁸          {the input, without its last element}
          Ç         with 1Ŀ run on it
             ©  and store that value in the register {and return it}.

We don't really want a return value here; we're just running this for its side effects (updating the register and outputting the assigned value). Jelly functions always return a value, though, so we just let the mapping table get returned, as that's tersest.

Main program

⁸©ḷƓÇ€¤
 ©       Initialize the mapping table
⁸        with the empty string (which is also the empty list)
  ḷ      then evaluate and discard
      ¤  the following value:
   Ɠ       a line from standard input, parsed into a data structure
    Ç€     with each element transformed via 2Ŀ
         {and leave the empty string to be printed implicitly}

Normally, would give us the first command-line argument when run in this context, but there isn't one (we're taking input from standard input), so it runs in an alternative mode that gives us the null string. The need to initialise the register (from its default value of 0, which crashes y) means that we can't mention the user's input implicitly, meaning that it's as cheap to take it from standard input (Ɠ) as it would be to take it from a command line argument (³ or ), and being able to access the alternative use of means that the unusual (for Jelly) form of input is actually a byte shorter.

It's possible this is improvable. I still haven't figured out why the second line needs to say ⁸Ǥ; rather than just ;@Ç – the two should be equivalent, as far as I understand Jelly, given the lack of use of µ/ð/ø – but the latter crashes for some reason. Likewise, there are various other ways to rearrange the program without losing bytes, so it's possible that I've missed a way to make things a bit shorter.

Incidentally, changing the in the last line to ; gives you an interesting look into the internal workings of the program, as it'll then output the "history of the register" that's implicitly output by the return values of 2Ḷ.

\$\endgroup\$
5
\$\begingroup\$

Perl 5, 92 bytes

90 bytes of code + -pl flags.

sub f{($b=$h{$a=pop}//$a)!=$a?f($b):$a}s%(\d+)\+(\d+)%f($1)+f$2%e&&redo;/=/;$_=$h{f$`}=f$'

Try it online!

I use the hashtable %h to store the mapping between numbers.
The function (sub) f returns the number to which its input map (or its input if it's mapped to no number): $h{$a=pop} retrieves the number toward which the input maps. If it's none, thanks to //$a, the value of ($b=$h{$a=pop}//$a) is the input ($a). We make sure that this values isn't the input itself to not loop infinitely (!=$a). Then, we either recursively call f or return the input.
The main program consists of two steps:
- s%(\d+)\+(\d+)%f($1)+f$2%e&&redo evaluates the first addition on the right side, while there is still an addition: it replaces x+y by the result of the evaluation of f(x)+f(y).
- /=/;$_=$h{f$`}=f$' does the assignment: /=/ allows to access the left side with $` and the right side with $', then $h{f$`}=f$' does the assignment. And we also assign it to $_ that is implicitly printed after each line.

\$\endgroup\$
5
\$\begingroup\$

JavaScript (Node.js), 81 bytes

v=x=>(v[x]=v[x]||x,v[x]-x?v(v[x]):x)
f=x=>l=>v[v(x)]=l.reduce((p,x)=>v(v(x)+p),0)

Try it online!

Receives input by calling f with the value to assign to, then calling the result of that with an array of values to add together. (i.e. f(5)([4])) Repeat for multiple lines.

v is used as a function to compute the actual current value of a number, and also as an object to store the actual values. First v[x]=v[x]||x ensures that v[x] is defined. v[x]-x performs a comparison to determine whether this is the actual number or not. If the number does not map to itself, v(v[x]) recursively tries again, otherwise return x.

f performs the calculation and assignment, curried to save one byte, where the second call returns the computed value.

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

Haskell, 116 113 108 106 bytes

(#)=until=<<((==)=<<)
e?((n,s):r)|m<-foldl1(\a b->e#(e#a+e#b))s=m:(\x->last$m:[e#x|x/=e#n])?r
e?r=[]
(id?)

Try it online! Each equation 4=3+1+5 is notated as tuple (4,[3,1,5]). The anonymous function (id?) takes a list of such tuples and returns a list of all intermediate results.

# is a function to find a fixpoint of a given function e and a start value x.

The function ? takes an evaluation function e and recursively solves each equation.foldl1(\a b->e#(e#a+e#b))s evaluates the right hand side of an equation and saves the result to m, e.g. for 4=3+1+5 it computes eval(eval(eval 3 + eval 1) + eval 5), where each eval is a fix point application of e. Then the eval function is modified to take the new assignment of n into account: (\x->last$m:[e#x|x/=e#n]) which is the same as \x -> if x == eval n then m else eval x.

The initial evaluation function is id which maps each integer to itself.


Thanks to Ørjan Johansen for a shorter fixpoint function, saving 2 bytes!

\$\endgroup\$
  • \$\begingroup\$ Nice job! By the way you are required to return all intermediate results, so you can drop last. \$\endgroup\$ – Leo Apr 9 '17 at 9:31
  • 2
    \$\begingroup\$ (#)e=until((==)=<<e)e or (#)=until=<<((==)=<<) is shorter. \$\endgroup\$ – Ørjan Johansen Apr 10 '17 at 0:58
  • \$\begingroup\$ @ØrjanJohansen Thanks alot! \$\endgroup\$ – Laikoni Apr 13 '17 at 7:11
3
\$\begingroup\$

oK, 48 bytes

a:[];s:{*(a@x;x)^0N}/;f:{a[s@x]:y:{s@x+y}/s'y;y}

Usage: f[5;1 2 3] / 5=1+2+3

Try it online!


If you don't mind having an upper limit to the numbers you can use, such as only using numbers 0 through 998, then the following suffices (41 bytes ± a few depending on the maximum):

a:!999;s:(a@)/;f:{a[s@x]:y:{s@x+y}/s'y;y}

Explanation:

; separates three definitions.

a is a dictionary/map of numbers. In the first case, it's an actual, empty dictionary [], in the second case it's a list of the numbers 0 to 998.

s is a function that finds the "resulting" number when given a number. The / on the end of the function means that it will apply itself to its own output until the output stops changing.

The last bit, f, means that:

f:{                      } /function called f, input number x, list y
                    s'y    /apply s to every number in the list
                   /       /fold through the list
            {s@x+y}        /    sum the two numbers, apply s
   a[s@x]:                 /set the s(x) to map to the final sum
          y:           ;y  /redefine y to be the final sum, then return it
\$\endgroup\$
3
\$\begingroup\$

Python 3, 146 132 130 bytes

14 bytes saved thanks to @Dada
2 bytes saved thanks to @mbomb007

d={}
g=lambda x:d.get(x)and x!=d[x]and g(d[x])or x
def f(t):
 for n,(s,*r)in t:
  for b in r:s=g(g(s)+g(b))
  d[g(n)]=s;yield g(n)

Try it online!

Receives input as tuples of equations [x = y + z + w as (x, (y, z, w))], outputs via generator.

\$\endgroup\$
  • \$\begingroup\$ Can you show an invocation example so it can be tested? \$\endgroup\$ – Leo Apr 9 '17 at 11:20
  • 1
    \$\begingroup\$ @Leo added TIO. \$\endgroup\$ – Uriel Apr 9 '17 at 11:46
  • 1
    \$\begingroup\$ g could probably be written g=lambda x:d.get(x)and d[x]!=x and g(d[x])or x. And I think you can use 1 space to indent instead of 2. That should get you to [132 bytes](Try it online!). \$\endgroup\$ – Dada Apr 9 '17 at 17:33
  • 1
    \$\begingroup\$ @Dada thanks! too bad they don't have half-space indent :P \$\endgroup\$ – Uriel Apr 9 '17 at 17:53
  • 1
    \$\begingroup\$ No half-space indent, but another neat trick is using a single tab instead of two spaces. As long as indentations are different, Python is happy (you could for example use space-tab and tab-space as indentations on additional nested levels). This can save you two bytes :) \$\endgroup\$ – Leo Apr 9 '17 at 18:21

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.