4
\$\begingroup\$

As the trip through the solar system on your way to rescue Santa gets a little droll, so perhaps some optimizations to your Intcode Computer are in order. Namely, making it as small as possible because you've got nothing better to do with your time.

Check out Advent of Code if you haven't already, the guy that makes the puzzles is amazing; Day 11 blew my mind. I might be cribbing the specs for the Intcode Computer, but why not challenge people to minify it?

Here are the specifications for an Intcode Computer:

Links to the day where the specifications are introduced will be included. These pages will contain example programs to use as test cases as well as supplemental explanation, as I presume I don't have to explain what it means to "read from" or "write to" a memory address.

  • An Intcode program is a list of integers (for example, 1,0,0,3,99). To run one, start by looking at the first integer (called position 0) this will be the opcode (enumerated below). Following an opcode will be its arguments (if any, each opcode will detail how many). Entries may take programs in any reasonable format, including how to handle any input to an Intcode program.
  • Intcode Computers have an instruction pointer that, after executing an instruction moves forward a number of positions based on the opcode (1 plus the number of arguments). (Day 2)
  • Each parameter of an instruction is handled based on its parameter mode. The rightmost two digits of an opcode indicate the opcode itself, while the remaining digits (read from right to left) indicate the argument mode (how the literal value of the argument is handled). (Day 5)
    • 0 is position mode. Read from the position indicated; eg. mem[a]
    • 1 is immediate mode. Read as a literal value; eg. a
      • Parameters that an instruction writes to will never be in immediate mode.
    • 2 is relative mode. Read from the position indicated by adding the RelativeCounter to the value; eg. mem[a+r]
  • Intcode Computers have a RelativeCounter which is a value that is used as an offset for relative mode arguments. This value starts at 0 (during which, relative mode acts identically to position mode). (Day 9)
    • The RelativeCounter may hold a negative value.
  • The computer's available memory should be much larger than the initial program. Memory beyond the initial program starts with the value 0 and can be read or written like any other memory. (It is invalid to try to access memory at a negative address, though.)
  • The computer should have support for large numbers and negative numbers; longs are sufficient.

Opcodes:

Arguments will be noted as A, B, etc. where A is the first argument, B is the second, and so on.

  • 1: Adds A and B and stores the result in C
  • 2: Multiplies A and B and stores the result in C
  • 3: Reads an integer from input and stores the result in A
  • 4: Outputs the value read from A
  • 5: Jump-if-true. If A is non-zero, it sets the instruction pointer to the value of B
  • 6: Jump-if-equal. If A is zero, it sets the instruction pointer to the value B
  • 7: Less than. If A is less than B, it stores 1 in the position given by C. Otherwise, it stores 0
  • 8: Equals. If A is equal to B, it stores 1 in the position given by C. Otherwise, it stores 0
  • 9 Adjusts the RelativeCounter by the value of A. The relative base increases (or decreases, if the value is negative) by the value of the parameter.
  • 99: Terminates the program
  • Other opcodes are invalid.

Opcode & paramater mode detail

Taken from Day 5:

ABCDE
 1002

DE - two-digit opcode,      02 == opcode 2
 C - mode of 1st parameter,  0 == position mode
 B - mode of 2nd parameter,  1 == immediate mode
 A - mode of 3rd parameter,  0 == position mode,
                                  omitted due to being a leading zero

Test cases

[3,9,8,9,10,9,4,9,99,-1,8] Using position mode, consider whether the input is equal to 8; output 1 (if it is) or 0 (if it is not).
[3, 3, 1107, -1, 8, 3, 4, 3, 99 ] Using immediate mode, consider whether the input is less than 8; output 1 (if it is) or 0 (if it is not). (From Day 5)
[109, 1, 204, -1, 1001, 100, 1, 100, 1008, 100, 16, 101, 1006, 101, 0, 99] takes no input and produces a copy of itself as output.
[1102, 34915192, 34915192, 7, 4, 7, 99, 0] should output a 16-digit number.
[104, 1125899906842624, 99] should output the large number in the middle. (From Day 9)
[109, -1, 4, 1, 99] outputs -1
[109, -1, 104, 1, 99] outputs 1
[109, -1, 204, 1, 99] outputs 109
[109, 1, 9, 2, 204, -6, 99] outputs 204
[109, 1, 109, 9, 204, -6, 99] outputs 204
[109, 1, 209, -1, 204, -106, 99] outputs 204
[109, 1, 3, 3, 204, 2, 99] outputs the input
[109, 1, 203, 2, 204, 2, 99] outputs the input (From Reddit regarding Day 9)
[3, 11, 3, 12, 1, 11, 12, 9, 104, 0, 99] takes two inputs and outputs their sum

Day 9 features a self-test program that will output opcodes that do not appear to be operating correctly, provided that your Intcomputer is fully functional to Day 5 specifications. It is very long and contains per-user unique code relevant to part 2's puzzle, as such it is not included here.

Day 7, Day 11, Day 13, Day 15, Day 17, Day 19, Day 21, and Day 23 all contain Intcode programs as well (as does, presumably, Day 25 if the pattern holds).

And remember, this is ! But that only applies to the Intcode Computer itself, any auxillary code to handle executing it is not counted towards your score.

A Helpful Hint

When testing your intcode computer, it is very helpful to run the diagnostic program. Here's a copy for those without an AOC account.

Sometimes, your program will constantly output 203 when running this program. That means that opcode 03 doesn't work when placed in "relative mode". Quite a few of us on the CGCC Discord were experiencing this issue.

For information on how to fix this, read here

\$\endgroup\$
  • 3
    \$\begingroup\$ Esolangs page \$\endgroup\$ – Lyxal Dec 25 '19 at 3:40
  • 2
    \$\begingroup\$ @Jono2906 Of course it has one. I didn't even think to look. \$\endgroup\$ – Draco18s no longer trusts SE Dec 25 '19 at 3:41
  • 1
    \$\begingroup\$ Also, where's my rewritten intcode interpreter when I need it! Probably on my home computer. \$\endgroup\$ – Lyxal Dec 25 '19 at 3:43
  • 1
    \$\begingroup\$ @tsh All of the puzzles in Advent of Code terminate with 99. Other opcodes are considered an error (meaning, the implementation is wrong). And yes, the decimal digits. 21002 is opcode 2 with parameter modes 0, 1, and 2. \$\endgroup\$ – Draco18s no longer trusts SE Dec 25 '19 at 18:07
  • 1
    \$\begingroup\$ @Arnauld Some of the Advenet of Code puzzles require piping more than one input in, starting with Day 7 (where you need to run 5 copies, with the output of the last copy creating a feedback loop back to the first copy). I'll see about crafting a simple test case that reads two input values. \$\endgroup\$ – Draco18s no longer trusts SE Dec 25 '19 at 18:10
3
\$\begingroup\$

Python 3, 480 476 474 418 416 bytes

-56 bytes thanks to Value Ink

def a(c,i,o):
 p=g=r=0;c+=[0]*9999
 def v(b):r;x=c[p+b];return eval(["c[x]","x","c[x+r]"][m[b]])
 def s(b,e):c[c[p+b]+r*(m[b]>1)]=e
 while g!=99:
  g=c[p];m=[0]*4;k,g=g//100,g%100;n=1
  while k:k,m[n]=k//10,k%10;n+=1
  if g<3or 6<g<9:x,y=v(1),v(2);s(3,[x==y,x+y,x*y,x<y][g&3]);p+=4
  if g==3:s(1,i());p+=2
  if g==4:o(v(1));p+=2
  if g==5:p=v(2)if v(1)else p+3
  if g==6:p=p+3 if v(1)else v(2)
  if g==9:r+=v(1);p+=2

Takes as input the code, an input function (called with no arguments whenever the code requests input), and an output function (called with one argument, the value just output, whenever the program outputs something). I included all of the test cases given in the TIO link.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ you can shorten you long if block by indexing a list with g and then calling exec on the result. \$\endgroup\$ – Post Rock Garf Hunter Dec 26 '19 at 16:55
  • 1
    \$\begingroup\$ @WheatWizard That doesn't work because exec doesn't overwrite local variables when run in a function in Python 3. \$\endgroup\$ – pppery Dec 26 '19 at 17:10
  • \$\begingroup\$ Since the commands for g in 1,2,7,8 are so similar, I believe you can wrap them together like so: if g<3or 6<g<9:x,y=v(1),v(2);s(3,[x==y,x+y,x*y,x<y][g&3]);p+=4 for 418 bytes. (TIO link was too long to post in this comment) \$\endgroup\$ – Value Ink Dec 26 '19 at 20:55
  • \$\begingroup\$ @Jono2906 You're passing input to the program incorrectly; the program expects the given input function to return a number, and your input function is returning a string. I'm honestly surprised that that doesn't result in a traceback somewhere. \$\endgroup\$ – pppery Dec 26 '19 at 21:06
  • \$\begingroup\$ @pppery Ah. I see. \$\endgroup\$ – Lyxal Dec 26 '19 at 21:06
2
\$\begingroup\$

JavaScript (V8),  234  230 bytes

Expects ([program], [input]), where input is ordered from last to first. Prints to stdout.

f=(P,i,p=r=0)=>(n=P[p++])-99&&([A,B]=(g=n=>o--?[(v=P[p++],k=n%10|0)-1?P[v+=k>1&&r]||0:v,...g(n/10)]:[])(n/100,o=~-(n%=10)%6>>1||3),n<4?P[v]=n<2?A+B:n<3?A*B:i.pop():n<5?print(A):n<7?!A^n>5?0:p=B:n<9?P[v]=n<8?A<B:A==B:r+=A,f(P,i,p))

Try it online!

How?

The implementation is rather straightforward, except the computation of the number of parameters for a command \$n \le 9\$, for which we use the following formula:

(n - 1) % 6 >> 1 || 3

Which gives:

 n | -1 | %6 | >>1 | ||3 | action
---+----+----+-----+-----+--------------
 1 |  0 |  0 |  0  |  3  | A+B -> P[C]
 2 |  1 |  1 |  0  |  3  | A*B -> P[C]
 3 |  2 |  2 |  1  |  1  | input -> A
 4 |  3 |  3 |  1  |  1  | output A
 5 |  4 |  4 |  2  |  2  | p=B if A!=0
 6 |  5 |  5 |  2  |  2  | p=B if A==0
 7 |  6 |  0 |  0  |  3  | A<B  -> P[C]
 8 |  7 |  1 |  0  |  3  | A==B -> P[C]
 9 |  8 |  2 |  1  |  1  | r+=A

Commented

Helper function

\$g\$ is a helper function that retrieves \$o\$ parameters according to the upper digits of the current command, which are passed in \$n\$.

g = n =>                        // n = command / 100
  o-- ?                         // decrement o; if it was not equal to 0:
    [                           //   update the list of parameters
      (                         //
        v = P[p++],             //     v = next value read from the program
        k = n % 10 | 0          //     k = floor(n mod 10)
      ) - 1 ?                   //     if k is not equal to 1:
        P[v += k > 1 && r]      //       read P[v] if k = 0 or P[v + r] if k = 2
        || 0                    //       if undefined, use 0 instead
      :                         //     else:
        v,                      //       immediate mode: use v
      ...g(n / 10)              //     recursive call with n / 10
    ]                           //   end of update
  :                             // else:
    []                          //   stop recursion

Main function

f = (                           // f is a recursive function taking:
  P,                            //   P[] = program
  i,                            //   i[] = input
  p = r = 0                     //   p = program pointer, r = relative counter
) =>                            //
  (n = P[p++]) - 99 && (        // read the next command n and stop if it's 99; otherwise:
    [A, B] = g(                 //   retrieve the first 2 parameters A and B (the latter
                                //   may be undefined) by invoking g:
      n / 100,                  //     pass n / 100
      o = ~-(n %= 10) % 6 >> 1  //     set o = number of parameters for this command,
          || 3                  //             using the formula described above
    ),                          //   end of call to g
    n < 4 ?                     //   if n is less than 4:
      P[v] =                    //     update P[v]:
        n < 2 ? A + B           //       if n = 1, store A + B
              : n < 3 ? A * B   //       if n = 2, store A * B
                      : i.pop() //       if n = 3, store the next input
    :                           //   else:
      n < 5 ?                   //     if n = 4:
        print(A)                //       output A
      :                         //     else:
        n < 7 ?                 //       if n = 5 or n = 6:
          !A ^ n > 5 ? 0        //         jump if (A == 0) XOR (n == 6) is false
                     : p = B    //
        :                       //       else:
          n < 9 ?               //         if n = 7 or n = 8:
            P[v] =              //           update P[v]:
              n < 8 ? A < B     //             test A < B if n = 7
                    : A == B    //             or A == B if n = 8
          :                     //         else:
            r += A,             //           update r
    f(P, i, p)                  //   recursive call for the next command
  )                             // end
\$\endgroup\$
1
\$\begingroup\$

AWK, 285 283 bytes

{for(split(i,v);o<99;r+=o>8?x:0){o=$++p;a=int(o/100)%10;b=int(o/1000)%10;w=$++p+1+!!a*r;x=--a?$w:$p;y=$++p+1+!!b*r;y=--b?$y:$p;z=$++p+1+!(o<10^4)*r;o%=100;if(o~3)$w=v[++j];if(o~4)printf"%.f\n",x;if(o~/1|2|7|8/)$z=o<2?x+y:o<3?x*y:o<8?x<y:x==y;else{--p;p=o~5?x?y:p:o~6?!x?y:p:p-1}}}

Try it online!

This essentially works by treating the input fields as the locations in memory, instead of initializing an array to store the program.

An extra 3 bytes (included in score) are required for the -F, switch, which sets the comma as the field separator.

Usage examples

<code> stands for the program posted above.

Interpret an Intcode program stored in a file named intcode.txt:

awk -F, '<code>' intcode.txt

Interpret an Intcode program using a Here-string:

awk -F, '<code>' <<< 9,1,204,-1,2205,-1,8,99,0

Pass a value as input:

awk -F, -v i=1 '<code>' intcode.txt

Pass multiple input values:

awk -F, -v i=1,2,3 '<code>' intcode.txt
New contributor
rootbeersoup is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\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.