Using nonstandard evaluation to simulate a register machine

[This article was first published on Higher Order Functions, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

I recently completed all 25 days of Advent of Code 2017, an annual
series of recreational programming puzzles. Each day describes a programming
puzzle and illustrates a handful of simple examples of the problem. The puzzle
then requires the participant to solve a much, much larger form of the problem.

For five or so of the puzzles, I used nonstandard evaluation to implement my
solution. As I previously wrote, nonstandard evaluation is a way of
bottling up magic spells (lines of R code) and changing how or where they are
cast (evaluated). I chose to use special evaluation not because it was the
easiest or most obvious solution but because I wanted to develop my skills with
computing on the language. In this post, I work through one of the examples
where I used nonstandard evaluation to write an interpreter for a simple
machine.

Puzzle description

Day 8 requires us to simulate the state
of a register machine as it receives a series of instructions.

Each instruction consists of several parts: the register to modify, whether to
increase or decrease that register’s value, the amount by which to increase or
decrease it, and a condition. If the condition fails, skip the instruction
without modifying the register. The registers all start at 0. The instructions
look like this:

b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10

[…]

You might also encounter <= (less than or equal to) or != (not equal to).
However, the CPU doesn’t have the bandwidth to tell you what all the registers
are named, and leaves that to you to determine.

What is the largest value in any register after completing the
instructions in your puzzle input?

If I squint long enough at the register instructions, I can basically
see R code.

<span class="c1"># b inc 5 if a > 1</span><span class="w">
</span><span class="n">b</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">></span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">5</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">b</span><span class="w">

</span><span class="c1"># a inc 1 if b < 5</span><span class="w">
</span><span class="n">a</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">b</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="m">5</span><span class="p">)</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">1</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">a</span><span class="w">

</span><span class="c1"># c dec -10 if a >= 1</span><span class="w">
</span><span class="n">c</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">>=</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">-10</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">c</span><span class="w">

</span><span class="c1"># c inc -20 if c == 10</span><span class="w">
</span><span class="n">c</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">c</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="m">10</span><span class="p">)</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">-20</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">c</span><span class="w">
</span>

If we can set up a way to convert the machine instructions into R code, R will
handle the job of looking up values, modifying values and evaluating the logic
and if statements. In other words, if we can convert register instructions
into R code, the problem simplifies into something like running an R script.

And that’s a good strategy, because we have a lot of instructions to process.
Each user receives some unique (I think) input for each problem, and my problem
input contains 1,000 instructions.

<span class="n">library</span><span class="p">(</span><span class="n">magrittr</span><span class="p">)</span><span class="w">
</span><span class="n">full_input</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="s2">"https://raw.githubusercontent.com"</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">file.path</span><span class="p">(</span><span class="s2">"tjmahr"</span><span class="p">,</span><span class="w"> </span><span class="s2">"adventofcode17"</span><span class="p">,</span><span class="w"> </span><span class="s2">"master"</span><span class="p">,</span><span class="w"> 
            </span><span class="s2">"inst"</span><span class="p">,</span><span class="w"> </span><span class="s2">"input08.txt"</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">readr</span><span class="o">::</span><span class="n">read_lines</span><span class="p">()</span><span class="w">

</span><span class="nf">length</span><span class="p">(</span><span class="n">full_input</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] 1000</span><span class="w">

</span><span class="n">head</span><span class="p">(</span><span class="n">full_input</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] "kd dec -37 if gm <= 9"   "x dec -715 if kjn == 0" </span><span class="w">
</span><span class="c1">#> [3] "ey inc 249 if x < 722"   "n dec 970 if t > 3"     </span><span class="w">
</span><span class="c1">#> [5] "f dec -385 if msg > -3"  "kd dec -456 if ic <= -8"</span><span class="w">
</span>

Our strategy for simulating the register machine will have the following steps:

  • Parsing a register instruction
  • Creating an R expression from an instruction
  • Evaluating an R expression inside of a register machine
  • Changing the evaluation rules to adapt to the quirks of this problem

Parsing the register instructions with regular expressions

The instructions have a very simple grammar. Here is how I would tag the first
few lines of my problem input.

[target] [verb] [num1] if [s1] [op] [num2]
      kd    dec    -37 if   gm   <=     9
       x    dec   -715 if  kjn   ==     0
      ey    inc    249 if    x    <   722
       n    dec    970 if    t    >     3
       f    dec   -385 if  msg    >    -3

We can parse these lines using regular expressions. Regular expressions are an
incredibly powerful language for processing text using pattern-matching rules. I
will walk through each of the regular expression patterns used to parse an
instruction.

To match the verbs, we can use the or | operator, so
(inc|dec) matches inc or dec. We can also match the six different
comparison operators using | too. In the code below, I put the patterns in
parentheses so that they will be treated as a single group.

<span class="n">re_verb</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="s2">"(inc|dec)"</span><span class="w">
</span><span class="n">re_op</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="s2">"(>|<|==|!=|>=|<=)"</span><span class="w">
</span>

A register name is just a sequence of letters. The special character \w
matches any word character; that is, it matches uppercase/lowercase letters,
digits and underscores. The (token)+ suffix matches 1 or more
repetitions of a token. Putting these two together, \w+ will match 1 or
more adjacent word characters. That pattern in principle could matches things
beside register names (like numbers) but the instruction format here is so
constrained that it’s not a problem.

<span class="c1"># We have to double the backslashes when using them in R strings</span><span class="w">
</span><span class="n">re_name</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="s2">"(\\w+)"</span><span class="w">
</span>

Numbers are just integers, and sometimes they are negative. A number here
is an optional - plus some digits. The special character \d matches any
digit from 0 to 9, so \d+ matches 1 or more successive digits. We can use
the (token)? suffix to match an optional token. In our case,
-?\d+ will match a sequence of digits and match leading hyphen if one is
present.

<span class="n">re_number</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="s2">"(-?\\d+)"</span><span class="w">
</span>

Each pattern in parentheses is a matching group, and the function str_match()
from the stringr package will return a matrix
with a column for each matched group. I also include an extra set of
parentheses around the condition in the if statement to also match the whole
condition as well as its parts.

<span class="c1"># Combine the sub-patterns together</span><span class="w">
</span><span class="n">re</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">sprintf</span><span class="p">(</span><span class="s2">"%s %s %s if (%s %s %s)"</span><span class="p">,</span><span class="w"> </span><span class="n">re_name</span><span class="p">,</span><span class="w"> </span><span class="n">re_verb</span><span class="p">,</span><span class="w"> 
              </span><span class="n">re_number</span><span class="p">,</span><span class="w"> </span><span class="n">re_name</span><span class="p">,</span><span class="w"> </span><span class="n">re_op</span><span class="p">,</span><span class="w"> </span><span class="n">re_number</span><span class="p">)</span><span class="w">
</span><span class="n">re</span><span class="w">
</span><span class="c1">#> [1] "(\\w+) (inc|dec) (-?\\d+) if ((\\w+) (>|<|==|!=|>=|<=) (-?\\d+))"</span><span class="w">

</span><span class="n">text</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="s2">"b inc 5 if a > 1"</span><span class="w">
</span><span class="n">stringr</span><span class="o">::</span><span class="n">str_match</span><span class="p">(</span><span class="n">text</span><span class="p">,</span><span class="w"> </span><span class="n">re</span><span class="p">)</span><span class="w">
</span><span class="c1">#>      [,1]               [,2] [,3]  [,4] [,5]    [,6] [,7] [,8]</span><span class="w">
</span><span class="c1">#> [1,] "b inc 5 if a > 1" "b"  "inc" "5"  "a > 1" "a"  ">"  "1"</span><span class="w">

</span><span class="c1"># Column 5 matches the subgroups in columns 6, 7 and 8 as a single </span><span class="w">
</span><span class="c1"># group because of the extra grouping parentheses after the `if`.</span><span class="w">
</span>

We can package this step into a function that takes an instruction’s
text and returns a list with the labelled parts of that instruction.

<span class="n">parse_instruction</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">text</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">stopifnot</span><span class="p">(</span><span class="nf">length</span><span class="p">(</span><span class="n">text</span><span class="p">)</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w">
  </span><span class="n">re</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="s2">"(\\w+) (inc|dec) (-?\\d+) if ((\\w+) (>|<|==|!=|>=|<=) (-?\\d+))"</span><span class="w">
  
  </span><span class="n">text</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">stringr</span><span class="o">::</span><span class="n">str_match</span><span class="p">(</span><span class="n">re</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">as.list</span><span class="p">()</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">setNames</span><span class="p">(</span><span class="nf">c</span><span class="p">(</span><span class="s2">"instruction"</span><span class="p">,</span><span class="w"> </span><span class="s2">"target"</span><span class="p">,</span><span class="w"> </span><span class="s2">"verb"</span><span class="p">,</span><span class="w"> </span><span class="s2">"num1"</span><span class="p">,</span><span class="w">
               </span><span class="s2">"cond"</span><span class="p">,</span><span class="w"> </span><span class="s2">"s1"</span><span class="p">,</span><span class="w"> </span><span class="s2">"op"</span><span class="p">,</span><span class="w"> </span><span class="s2">"num2"</span><span class="p">))</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">str</span><span class="p">(</span><span class="n">parse_instruction</span><span class="p">(</span><span class="n">text</span><span class="p">))</span><span class="w">
</span><span class="c1">#> List of 8</span><span class="w">
</span><span class="c1">#>  $ instruction: chr "b inc 5 if a > 1"</span><span class="w">
</span><span class="c1">#>  $ target     : chr "b"</span><span class="w">
</span><span class="c1">#>  $ verb       : chr "inc"</span><span class="w">
</span><span class="c1">#>  $ num1       : chr "5"</span><span class="w">
</span><span class="c1">#>  $ cond       : chr "a > 1"</span><span class="w">
</span><span class="c1">#>  $ s1         : chr "a"</span><span class="w">
</span><span class="c1">#>  $ op         : chr ">"</span><span class="w">
</span><span class="c1">#>  $ num2       : chr "1"</span><span class="w">
</span>

Creating R code

Next, we need to convert some strings into R code. We can do this with
rlang::parse_expr(). It takes a string and creates an R expression,
something I’ve described as a kind of bottled up magic spell: An
expression captures magic words (code) allow us to manipulate or cast (evaluate)
them.

<span class="n">code</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">rlang</span><span class="o">::</span><span class="n">parse_expr</span><span class="p">(</span><span class="s2">"print('hello')"</span><span class="p">)</span><span class="w">
</span><span class="n">code</span><span class="w">
</span><span class="c1">#> print("hello")</span><span class="w">

</span><span class="n">code</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">rlang</span><span class="o">::</span><span class="n">parse_expr</span><span class="p">(</span><span class="s2">"if (a > 1) b + 5 else b"</span><span class="p">)</span><span class="w">
</span><span class="n">code</span><span class="w">
</span><span class="c1">#> if (a > 1) b + 5 else b</span><span class="w">
</span>

The format of the instructions is relatively straightforward. We can fill
in a template with the parts of the parsed line. Because inc/dec are just
addition and subtraction, we replace them with the appropriate math operations.

<span class="n">create_r_instruction</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">parsed</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">parsed</span><span class="o">$</span><span class="n">math</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">parsed</span><span class="o">$</span><span class="n">verb</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="s2">"inc"</span><span class="p">)</span><span class="w"> </span><span class="s2">"+"</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="s2">"-"</span><span class="w">
  </span><span class="n">code</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">sprintf</span><span class="p">(</span><span class="s2">"if (%s) %s %s %s else %s"</span><span class="p">,</span><span class="w"> </span><span class="n">parsed</span><span class="o">$</span><span class="n">cond</span><span class="p">,</span><span class="w"> 
                  </span><span class="n">parsed</span><span class="o">$</span><span class="n">target</span><span class="p">,</span><span class="w"> </span><span class="n">parsed</span><span class="o">$</span><span class="n">math</span><span class="p">,</span><span class="w"> </span><span class="n">parsed</span><span class="o">$</span><span class="n">num1</span><span class="p">,</span><span class="w"> 
                  </span><span class="n">parsed</span><span class="o">$</span><span class="n">target</span><span class="p">)</span><span class="w">
  </span><span class="n">rlang</span><span class="o">::</span><span class="n">parse_expr</span><span class="p">(</span><span class="n">code</span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">r_code</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="s2">"b inc 5 if a > 1"</span><span class="w"> </span><span class="o">%>%</span><span class="w">
  </span><span class="n">parse_instruction</span><span class="p">()</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">create_r_instruction</span><span class="p">()</span><span class="w">

</span><span class="n">r_code</span><span class="w">
</span><span class="c1">#> if (a > 1) b + 5 else b</span><span class="w">
</span>

Create the register machine

We have to figure out where we want to evaluate the generated R code. We
create a register object to hold the values. The object will just be a list()
with some extra metadata. This object will be the location where the R code
is evaluated.

<span class="n">create_register_machine</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">...</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">initial</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="nf">list</span><span class="p">(</span><span class="n">...</span><span class="p">)</span><span class="w">
  </span><span class="n">data</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="nf">c</span><span class="p">(</span><span class="n">initial</span><span class="p">,</span><span class="w"> </span><span class="nf">list</span><span class="p">(</span><span class="n">.metadata</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nf">list</span><span class="p">()))</span><span class="w">
  </span><span class="n">structure</span><span class="p">(</span><span class="n">data</span><span class="p">,</span><span class="w"> </span><span class="n">class</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nf">c</span><span class="p">(</span><span class="s2">"register_machine"</span><span class="p">,</span><span class="w"> </span><span class="s2">"list"</span><span class="p">))</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="c1"># Give the machines a pretty print method</span><span class="w">
</span><span class="n">print.register_machine</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">utils</span><span class="o">::</span><span class="n">str</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w">
  </span><span class="nf">invisible</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">create_register_machine</span><span class="p">()</span><span class="w">
</span><span class="c1">#> List of 1</span><span class="w">
</span><span class="c1">#>  $ .metadata: list()</span><span class="w">
</span><span class="c1">#>  - attr(*, "class")= chr [1:2] "register_machine" "list"</span><span class="w">
</span>

For now, we can initialize registers by using named arguments to the function.

<span class="n">create_register_machine</span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">0</span><span class="p">,</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">0</span><span class="p">)</span><span class="w">
</span><span class="c1">#> List of 3</span><span class="w">
</span><span class="c1">#>  $ a        : num 0</span><span class="w">
</span><span class="c1">#>  $ b        : num 0</span><span class="w">
</span><span class="c1">#>  $ .metadata: list()</span><span class="w">
</span><span class="c1">#>  - attr(*, "class")= chr [1:2] "register_machine" "list"</span><span class="w">
</span>

Evaluating code inside of the machine

So far, we have:

  • A way to analyze register instructions and convert them into R code
  • An object that holds register values

Now, we need to evaluate an expression inside of the register. We will use
tidy evaluation; the function eval_tidy() lets us evaluate an
R expression inside of a data object.

<span class="n">r_code</span><span class="w">
</span><span class="c1">#> if (a > 1) b + 5 else b</span><span class="w">

</span><span class="c1"># b + 5</span><span class="w">
</span><span class="n">r</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_register_machine</span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">4</span><span class="p">,</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">7</span><span class="p">)</span><span class="w">
</span><span class="n">rlang</span><span class="o">::</span><span class="n">eval_tidy</span><span class="p">(</span><span class="n">r_code</span><span class="p">,</span><span class="w"> </span><span class="n">data</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">r</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] 12</span><span class="w">

</span><span class="c1"># just b</span><span class="w">
</span><span class="n">r</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_register_machine</span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">0</span><span class="p">,</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">7</span><span class="p">)</span><span class="w">
</span><span class="n">rlang</span><span class="o">::</span><span class="n">eval_tidy</span><span class="p">(</span><span class="n">r_code</span><span class="p">,</span><span class="w"> </span><span class="n">data</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">r</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] 7</span><span class="w">
</span>

Now, we need to actually do something. We need to update the register machine
using the value from the evaluated instruction. Otherwise, the machine will just
read expressions and forget everything it’s read.

To update the machine, we have to determine the register to update. Fortunately,
our generated code always ends with an else branch that has the target
register.

<span class="n">r_code</span><span class="w">
</span><span class="c1">#> if (a > 1) b + 5 else b</span><span class="w">
</span>

If we can pull out that symbol after the else, we will have the name of
register to update in the machine. Because the code is so formulaic, we can just
extract the symbol directly using the code’s abstract syntax tree (AST).
pryr::call_tree() shows the AST for an expression.

<span class="n">pryr</span><span class="o">::</span><span class="n">call_tree</span><span class="p">(</span><span class="n">r_code</span><span class="p">)</span><span class="w">
</span><span class="c1">#> \- ()</span><span class="w">
</span><span class="c1">#>   \- `if</span><span class="w">
</span><span class="c1">#>   \- ()</span><span class="w">
</span><span class="c1">#>     \- `></span><span class="w">
</span><span class="c1">#>     \- `a</span><span class="w">
</span><span class="c1">#>     \-  1</span><span class="w">
</span><span class="c1">#>   \- ()</span><span class="w">
</span><span class="c1">#>     \- `+</span><span class="w">
</span><span class="c1">#>     \- `b</span><span class="w">
</span><span class="c1">#>     \-  5</span><span class="w">
</span><span class="c1">#>   \- `b</span><span class="w">
</span>

We can extract elements from the tree like elements in a list by selecting
indices.

<span class="c1"># The numbers match one of the slashs at the first level of indentation</span><span class="w">
</span><span class="n">r_code</span><span class="p">[[</span><span class="m">1</span><span class="p">]]</span><span class="w">
</span><span class="c1">#> `if`</span><span class="w">
</span><span class="n">r_code</span><span class="p">[[</span><span class="m">2</span><span class="p">]]</span><span class="w">
</span><span class="c1">#> a > 1</span><span class="w">

</span><span class="c1"># We can crawl down subtrees too</span><span class="w">
</span><span class="n">r_code</span><span class="p">[[</span><span class="m">2</span><span class="p">]][[</span><span class="m">2</span><span class="p">]]</span><span class="w">
</span><span class="c1">#> a</span><span class="w">

</span><span class="c1"># But what we want is the last branch from the `if` level</span><span class="w">
</span><span class="n">r_code</span><span class="p">[[</span><span class="m">4</span><span class="p">]]</span><span class="w">
</span><span class="c1">#> b</span><span class="w">
</span>

If we convert the symbol into a string, we can look it up in the register using
the usual list lookup syntax.

<span class="n">r</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_register_machine</span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">4</span><span class="p">,</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">7</span><span class="p">)</span><span class="w">
</span><span class="n">target</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">rlang</span><span class="o">::</span><span class="n">as_string</span><span class="p">(</span><span class="n">r_code</span><span class="p">[[</span><span class="m">4</span><span class="p">]])</span><span class="w">
</span><span class="n">r</span><span class="p">[[</span><span class="n">target</span><span class="p">]]</span><span class="w">
</span><span class="c1">#> [1] 7</span><span class="w">
</span>

We can also use list lookup syntax with assignment to modify the register.

<span class="n">r</span><span class="p">[[</span><span class="n">target</span><span class="p">]]</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">rlang</span><span class="o">::</span><span class="n">eval_tidy</span><span class="p">(</span><span class="n">r_code</span><span class="p">,</span><span class="w"> </span><span class="n">data</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">r</span><span class="p">)</span><span class="w">
</span><span class="n">r</span><span class="w">
</span><span class="c1">#> List of 3</span><span class="w">
</span><span class="c1">#>  $ a        : num 4</span><span class="w">
</span><span class="c1">#>  $ b        : num 12</span><span class="w">
</span><span class="c1">#>  $ .metadata: list()</span><span class="w">
</span><span class="c1">#>  - attr(*, "class")= chr [1:2] "register_machine" "list"</span><span class="w">
</span>

Let’s wrap these steps into a function.

<span class="n">eval_instruction</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">register_machine</span><span class="p">,</span><span class="w"> </span><span class="n">instruction</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">target</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">rlang</span><span class="o">::</span><span class="n">as_string</span><span class="p">(</span><span class="n">instruction</span><span class="p">[[</span><span class="m">4</span><span class="p">]])</span><span class="w">
  </span><span class="n">register_machine</span><span class="p">[[</span><span class="n">target</span><span class="p">]]</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">rlang</span><span class="o">::</span><span class="n">eval_tidy</span><span class="p">(</span><span class="w">
    </span><span class="n">expr</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">instruction</span><span class="p">,</span><span class="w"> 
    </span><span class="n">data</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">register_machine</span><span class="p">)</span><span class="w">
  </span><span class="n">register_machine</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">create_register_machine</span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">2</span><span class="p">,</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">0</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">eval_instruction</span><span class="p">(</span><span class="n">r_code</span><span class="p">)</span><span class="w">
</span><span class="c1">#> List of 3</span><span class="w">
</span><span class="c1">#>  $ a        : num 2</span><span class="w">
</span><span class="c1">#>  $ b        : num 5</span><span class="w">
</span><span class="c1">#>  $ .metadata: list()</span><span class="w">
</span><span class="c1">#>  - attr(*, "class")= chr [1:2] "register_machine" "list"</span><span class="w">

</span><span class="n">create_register_machine</span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">2</span><span class="p">,</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">0</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="c1"># For quick testing, we pass in quoted expressions</span><span class="w">
  </span><span class="n">eval_instruction</span><span class="p">(</span><span class="nf">quote</span><span class="p">(</span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">></span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">100</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">b</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="c1"># Should not run</span><span class="w">
  </span><span class="n">eval_instruction</span><span class="p">(</span><span class="nf">quote</span><span class="p">(</span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">5</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">b</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="c1"># Should run</span><span class="w">
  </span><span class="n">eval_instruction</span><span class="p">(</span><span class="nf">quote</span><span class="p">(</span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">></span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">10</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">a</span><span class="p">))</span><span class="w">
</span><span class="c1">#> List of 3</span><span class="w">
</span><span class="c1">#>  $ a        : num 12</span><span class="w">
</span><span class="c1">#>  $ b        : num -100</span><span class="w">
</span><span class="c1">#>  $ .metadata: list()</span><span class="w">
</span><span class="c1">#>  - attr(*, "class")= chr [1:2] "register_machine" "list"</span><span class="w">
</span>

Time for some extra nonstandard evaluation

The code so far only works if the machine already has registers that match the
registers in an instruction. Otherwise, we raise an error.

<span class="n">create_register_machine</span><span class="p">()</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">eval_instruction</span><span class="p">(</span><span class="nf">quote</span><span class="p">(</span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">></span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">100</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">b</span><span class="p">))</span><span class="w">
</span><span class="c1">#> Error in overscope_eval_next(overscope, expr): object 'a' not found</span><span class="w">

</span><span class="c1"># "Overscope" is the tidy evaluation term for the data context, so failing to</span><span class="w">
</span><span class="c1"># find the name in the data is failing to find the name in the overscope.</span><span class="w">
</span>

To solve the problem, we could study the 1,000 lines of input beforehand,
extract the register names, initialize them to 0 and then evaluate the
instructions.1 Or… or… we could procrastinate and only
initialize a register name to 0 when the machine encounters a name it doesn’t
recognize. If, for some reason, our machine received instructions
one at a time, like over a network connection, then the procrastinated approach
seems even more reasonable.

This latter strategy will involve some very nonstandard evaluation. I
emphasize the “very” because we are changing one of the fundamental rules of R
evaluation
:smiling_imp:. R throws an error if you ask it to evaluate the name
of a variable that doesn’t exist. But here we are going to detect those missing
variables and set them to 0 before they get evaluated.

To find the brand-new register names, we can inspect the call tree and find the
names of the registers. We already know where the target is. The other place
where names show up is in the condition of the if statement.

<span class="n">pryr</span><span class="o">::</span><span class="n">call_tree</span><span class="p">(</span><span class="n">r_code</span><span class="p">)</span><span class="w">
</span><span class="c1">#> \- ()</span><span class="w">
</span><span class="c1">#>   \- `if</span><span class="w">
</span><span class="c1">#>   \- ()</span><span class="w">
</span><span class="c1">#>     \- `></span><span class="w">
</span><span class="c1">#>     \- `a</span><span class="w">
</span><span class="c1">#>     \-  1</span><span class="w">
</span><span class="c1">#>   \- ()</span><span class="w">
</span><span class="c1">#>     \- `+</span><span class="w">
</span><span class="c1">#>     \- `b</span><span class="w">
</span><span class="c1">#>     \-  5</span><span class="w">
</span><span class="c1">#>   \- `b</span><span class="w">

</span><span class="n">extract_register_names</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">instruction</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">reg_target</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">rlang</span><span class="o">::</span><span class="n">as_string</span><span class="p">(</span><span class="n">instruction</span><span class="p">[[</span><span class="m">4</span><span class="p">]])</span><span class="w">
  </span><span class="n">reg_condition</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">rlang</span><span class="o">::</span><span class="n">as_string</span><span class="p">(</span><span class="n">instruction</span><span class="p">[[</span><span class="m">2</span><span class="p">]][[</span><span class="m">2</span><span class="p">]])</span><span class="w">
  </span><span class="nf">list</span><span class="p">(</span><span class="n">target</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">reg_target</span><span class="p">,</span><span class="w">
       </span><span class="n">registers</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">unique</span><span class="p">(</span><span class="nf">c</span><span class="p">(</span><span class="n">reg_target</span><span class="p">,</span><span class="w"> </span><span class="n">reg_condition</span><span class="p">))</span><span class="w">
  </span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">extract_register_names</span><span class="p">(</span><span class="nf">quote</span><span class="p">(</span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o">></span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">100</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">b</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">str</span><span class="p">()</span><span class="w">
</span><span class="c1">#> List of 2</span><span class="w">
</span><span class="c1">#>  $ target   : chr "b"</span><span class="w">
</span><span class="c1">#>  $ registers: chr [1:2] "b" "a"</span><span class="w">

</span><span class="c1"># Just returns unique names</span><span class="w">
</span><span class="n">extract_register_names</span><span class="p">(</span><span class="nf">quote</span><span class="p">(</span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">b</span><span class="w"> </span><span class="o">></span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">100</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">b</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">str</span><span class="p">()</span><span class="w">
</span><span class="c1">#> List of 2</span><span class="w">
</span><span class="c1">#>  $ target   : chr "b"</span><span class="w">
</span><span class="c1">#>  $ registers: chr "b"</span><span class="w">
</span>

We can define a helper function which checks for missing names—names that
yield NULL values when we try to retrieve them—and initializes them to 0.

<span class="n">initialize_new_registers</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">register_machine</span><span class="p">,</span><span class="w"> </span><span class="n">registers</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">each_register</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">registers</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
    </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="nf">is.null</span><span class="p">(</span><span class="n">register_machine</span><span class="p">[[</span><span class="n">each_register</span><span class="p">]]))</span><span class="w"> </span><span class="p">{</span><span class="w">
      </span><span class="n">register_machine</span><span class="p">[[</span><span class="n">each_register</span><span class="p">]]</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="m">0</span><span class="w">
    </span><span class="p">}</span><span class="w">
  </span><span class="p">}</span><span class="w">
  </span><span class="n">register_machine</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="c1"># Before</span><span class="w">
</span><span class="n">r</span><span class="w">
</span><span class="c1">#> List of 3</span><span class="w">
</span><span class="c1">#>  $ a        : num 4</span><span class="w">
</span><span class="c1">#>  $ b        : num 12</span><span class="w">
</span><span class="c1">#>  $ .metadata: list()</span><span class="w">
</span><span class="c1">#>  - attr(*, "class")= chr [1:2] "register_machine" "list"</span><span class="w">

</span><span class="n">initialize_new_registers</span><span class="p">(</span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="nf">c</span><span class="p">(</span><span class="s2">"a"</span><span class="p">,</span><span class="w"> </span><span class="s2">"b"</span><span class="p">,</span><span class="w"> </span><span class="s2">"w"</span><span class="p">,</span><span class="w"> </span><span class="s2">"a"</span><span class="p">,</span><span class="w"> </span><span class="s2">"s"</span><span class="p">,</span><span class="w"> </span><span class="s2">"j"</span><span class="p">))</span><span class="w">
</span><span class="c1">#> List of 6</span><span class="w">
</span><span class="c1">#>  $ a        : num 4</span><span class="w">
</span><span class="c1">#>  $ b        : num 12</span><span class="w">
</span><span class="c1">#>  $ .metadata: list()</span><span class="w">
</span><span class="c1">#>  $ w        : num 0</span><span class="w">
</span><span class="c1">#>  $ s        : num 0</span><span class="w">
</span><span class="c1">#>  $ j        : num 0</span><span class="w">
</span><span class="c1">#>  - attr(*, "class")= chr [1:2] "register_machine" "list"</span><span class="w">
</span>

Finally, we update our evaluation function to do this step automatically. I’m
also going to add some code to record the value of the maximum register whenever
an instruction is evaluated because, ummm, that’s the whole point of puzzle.

<span class="n">eval_instruction</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">register_machine</span><span class="p">,</span><span class="w"> </span><span class="n">instruction</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="c1"># Set any new registers to 0</span><span class="w">
  </span><span class="n">registers</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">extract_register_names</span><span class="p">(</span><span class="n">instruction</span><span class="p">)</span><span class="w">
  </span><span class="n">register_machine</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">initialize_new_registers</span><span class="p">(</span><span class="w">
    </span><span class="n">register_machine</span><span class="p">,</span><span class="w"> </span><span class="n">registers</span><span class="o">$</span><span class="n">registers</span><span class="p">)</span><span class="w">
  
  </span><span class="c1"># Evaluate instruction</span><span class="w">
  </span><span class="n">register_machine</span><span class="p">[[</span><span class="n">registers</span><span class="o">$</span><span class="n">target</span><span class="p">]]</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">rlang</span><span class="o">::</span><span class="n">eval_tidy</span><span class="p">(</span><span class="w">
    </span><span class="n">expr</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">instruction</span><span class="p">,</span><span class="w"> 
    </span><span class="n">data</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">register_machine</span><span class="p">)</span><span class="w">
  
  </span><span class="c1"># Find the maximum value</span><span class="w">
  </span><span class="n">register_names</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">setdiff</span><span class="p">(</span><span class="nf">names</span><span class="p">(</span><span class="n">register_machine</span><span class="p">),</span><span class="w"> </span><span class="s2">".metadata"</span><span class="p">)</span><span class="w">
  </span><span class="n">current_max</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="nf">max</span><span class="p">(</span><span class="n">unlist</span><span class="p">(</span><span class="n">register_machine</span><span class="p">[</span><span class="n">register_names</span><span class="p">]))</span><span class="w">
  </span><span class="n">register_machine</span><span class="o">$</span><span class="n">.metadata</span><span class="o">$</span><span class="n">max</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">current_max</span><span class="w">
  </span><span class="n">register_machine</span><span class="w">
</span><span class="p">}</span><span class="w">
</span>

Let’s try four instructions from a clean slate.

<span class="n">create_register_machine</span><span class="p">()</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="c1"># b gets 5</span><span class="w">
  </span><span class="n">eval_instruction</span><span class="p">(</span><span class="nf">quote</span><span class="p">(</span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">d</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">5</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">b</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="c1"># c gets 10</span><span class="w">
  </span><span class="n">eval_instruction</span><span class="p">(</span><span class="nf">quote</span><span class="p">(</span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">b</span><span class="w"> </span><span class="o">></span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">10</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">c</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="c1"># b gets 5 more</span><span class="w">
  </span><span class="n">eval_instruction</span><span class="p">(</span><span class="nf">quote</span><span class="p">(</span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">5</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">b</span><span class="p">))</span><span class="w">
</span><span class="c1">#> List of 5</span><span class="w">
</span><span class="c1">#>  $ .metadata:List of 1</span><span class="w">
</span><span class="c1">#>   ..$ max: num 10</span><span class="w">
</span><span class="c1">#>  $ b        : num 10</span><span class="w">
</span><span class="c1">#>  $ d        : num 0</span><span class="w">
</span><span class="c1">#>  $ c        : num 10</span><span class="w">
</span><span class="c1">#>  $ a        : num 0</span><span class="w">
</span><span class="c1">#>  - attr(*, "class")= chr [1:2] "register_machine" "list"</span><span class="w">
</span>

Now, for the moment of truth… Let’s process all 1,000 instructions.

<span class="n">r</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_register_machine</span><span class="p">()</span><span class="w">

</span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">each_instruction</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">full_input</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">parsed</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">each_instruction</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">parse_instruction</span><span class="p">()</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">create_r_instruction</span><span class="p">()</span><span class="w">
  </span><span class="n">r</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">eval_instruction</span><span class="p">(</span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">parsed</span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">r</span><span class="w">
</span><span class="c1">#> List of 27</span><span class="w">
</span><span class="c1">#>  $ .metadata:List of 1</span><span class="w">
</span><span class="c1">#>   ..$ max: num 4832</span><span class="w">
</span><span class="c1">#>  $ kd       : num -2334</span><span class="w">
</span><span class="c1">#>  $ gm       : num -4239</span><span class="w">
</span><span class="c1">#>  $ x        : num -345</span><span class="w">
</span><span class="c1">#>  $ kjn      : num -1813</span><span class="w">
</span><span class="c1">#>  $ ey       : num 209</span><span class="w">
</span><span class="c1">#>  $ n        : num -764</span><span class="w">
</span><span class="c1">#>  $ t        : num 2997</span><span class="w">
</span><span class="c1">#>  $ f        : num 4468</span><span class="w">
</span><span class="c1">#>  $ msg      : num -3906</span><span class="w">
</span><span class="c1">#>  $ ic       : num -263</span><span class="w">
</span><span class="c1">#>  $ zv       : num -599</span><span class="w">
</span><span class="c1">#>  $ gub      : num 2025</span><span class="w">
</span><span class="c1">#>  $ yp       : num -2530</span><span class="w">
</span><span class="c1">#>  $ lyr      : num -2065</span><span class="w">
</span><span class="c1">#>  $ j        : num 3619</span><span class="w">
</span><span class="c1">#>  $ e        : num -4230</span><span class="w">
</span><span class="c1">#>  $ riz      : num 863</span><span class="w">
</span><span class="c1">#>  $ lzd      : num 4832</span><span class="w">
</span><span class="c1">#>  $ ucy      : num -3947</span><span class="w">
</span><span class="c1">#>  $ i        : num 3448</span><span class="w">
</span><span class="c1">#>  $ omz      : num -3365</span><span class="w">
</span><span class="c1">#>  $ djq      : num 392</span><span class="w">
</span><span class="c1">#>  $ bxy      : num 1574</span><span class="w">
</span><span class="c1">#>  $ tj       : num 1278</span><span class="w">
</span><span class="c1">#>  $ y        : num 1521</span><span class="w">
</span><span class="c1">#>  $ m        : num 2571</span><span class="w">
</span><span class="c1">#>  - attr(*, "class")= chr [1:2] "register_machine" "list"</span><span class="w">
</span>

:star: Ta-da! The maximum register value is 4,832. Problem solved!

And then the rules change

Advent of Code problems come in two parts, and we don’t learn the question
behind Part 2 until we complete Part 1. In this case, after submitting our
solution for Part 1, we receive the following requirement:

To be safe, the CPU also needs to know the highest value held in any
register during this process
so that it can decide how much memory to allocate
to these operations.

Accounting for this twist requires a small change to the evaluation code. We
add another metadata variable to track the highest value ever stored in a
register.

<span class="n">eval_instruction</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">register_machine</span><span class="p">,</span><span class="w"> </span><span class="n">instruction</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="c1"># Set any new registers to 0</span><span class="w">
  </span><span class="n">registers</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">extract_register_names</span><span class="p">(</span><span class="n">instruction</span><span class="p">)</span><span class="w">
  </span><span class="n">register_machine</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">initialize_new_registers</span><span class="p">(</span><span class="w">
    </span><span class="n">register_machine</span><span class="p">,</span><span class="w"> </span><span class="n">registers</span><span class="o">$</span><span class="n">registers</span><span class="p">)</span><span class="w">
  
  </span><span class="c1"># Evaluate instruction</span><span class="w">
  </span><span class="n">register_machine</span><span class="p">[[</span><span class="n">registers</span><span class="o">$</span><span class="n">target</span><span class="p">]]</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">rlang</span><span class="o">::</span><span class="n">eval_tidy</span><span class="p">(</span><span class="w">
    </span><span class="n">expr</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">instruction</span><span class="p">,</span><span class="w"> 
    </span><span class="n">data</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">register_machine</span><span class="p">)</span><span class="w">
  
  </span><span class="c1"># Find the maximum value</span><span class="w">
  </span><span class="n">register_names</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">setdiff</span><span class="p">(</span><span class="nf">names</span><span class="p">(</span><span class="n">register_machine</span><span class="p">),</span><span class="w"> </span><span class="s2">".metadata"</span><span class="p">)</span><span class="w">
  </span><span class="n">current_max</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="nf">max</span><span class="p">(</span><span class="n">unlist</span><span class="p">(</span><span class="n">register_machine</span><span class="p">[</span><span class="n">register_names</span><span class="p">]))</span><span class="w">
  </span><span class="n">register_machine</span><span class="o">$</span><span class="n">.metadata</span><span class="o">$</span><span class="n">max</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">current_max</span><span class="w">
  
  </span><span class="c1"># Create the max-ever value if necessary</span><span class="w">
  </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="nf">is.null</span><span class="p">(</span><span class="n">register_machine</span><span class="o">$</span><span class="n">.metadata</span><span class="o">$</span><span class="n">max_ever</span><span class="p">))</span><span class="w"> </span><span class="p">{</span><span class="w">
    </span><span class="n">register_machine</span><span class="o">$</span><span class="n">.metadata</span><span class="o">$</span><span class="n">max_ever</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="m">0</span><span class="w">
  </span><span class="p">}</span><span class="w">
  
  </span><span class="c1"># Maybe update the max-ever value</span><span class="w">
  </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">register_machine</span><span class="o">$</span><span class="n">.metadata</span><span class="o">$</span><span class="n">max_ever</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">current_max</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
    </span><span class="n">register_machine</span><span class="o">$</span><span class="n">.metadata</span><span class="o">$</span><span class="n">max_ever</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">current_max</span><span class="w">
  </span><span class="p">}</span><span class="w">
  
  </span><span class="n">register_machine</span><span class="w">
</span><span class="p">}</span><span class="w">
</span>

Admittedly, eval_instruction() is starting to get bloated. Conceptually, we
could probably the break this function down into three functions: pre-evaluation
steps, evaluation, and post-evaluation steps.2 But this is good
enough for now.

We run the instructions again to get the updated metadata.

<span class="n">r</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_register_machine</span><span class="p">()</span><span class="w">

</span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">each_instruction</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">full_input</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">parsed</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">each_instruction</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">parse_instruction</span><span class="p">()</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">create_r_instruction</span><span class="p">()</span><span class="w">
  </span><span class="n">r</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">eval_instruction</span><span class="p">(</span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">parsed</span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">r</span><span class="o">$</span><span class="n">.metadata</span><span class="w">
</span><span class="c1">#> $max</span><span class="w">
</span><span class="c1">#> [1] 4832</span><span class="w">
</span><span class="c1">#> </span><span class="w">
</span><span class="c1">#> $max_ever</span><span class="w">
</span><span class="c1">#> [1] 5443</span><span class="w">
</span>

:star2: And boom! Another problem solved.

eval(thoughts, envir = this_problem)

I like this kind of nonstandard evaluation approach for converting problems into
R code, but it’s mostly useful when the problem describes a series of
instructions that can be parsed and evaluated. For problems like this register
machine simulation, the nonstandard evaluation route is straightforward. But
it’s also a viable problem-solving strategy when the “machine” or the
“instructions” are subtler, as in
this problem about simulating “dance” moves.

Odds are, you’ll never have to write an interpreter for a toy machine or
language. Nevertheless, here are some R functions that we used for this
puzzle that are helpful in other contexts:

  • stringr::str_match() to extract all the groups in a regular
    expression at once.
  • rlang::parse_expr() to convert a string of text into an R expression.
  • pryr::call_tree() to visualize an expression’s syntax tree and
    expression[[i]][[j]] to pluck out symbols from locations in a tree.
  • rlang::as_string() to convert a symbol into a string.
  • rlang::eval_tidy() to evaluate an expression inside of a data
    context.

  1. That actually would be pretty easy. Get a dataframe with
    purrr::map_df(full_input, parse_instruction). Find the unique register
    names. Create a list of 0’s with those names. Use do.call() to call
    create_register_machine() with that list. With no special evaluation
    trickery, this approach is closer to the idea of “just running R code”. 

  2. If all I did for a living was write code to simulate machines
    or toy languages, I might try to formalize this custom evaluation process
    with pre-evaluation and post-evaluations “hooks” that could be arguments
    to a custom evaluation function. I’m just brainstorming though. 

To leave a comment for the author, please follow the link and comment on their blog: Higher Order Functions.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)