6
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 position0)
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 at0
(during which, relative mode acts identically to position mode). (Day 9)- The
RelativeCounter
may hold a negative value.
- The
- 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;
long
s 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
: AddsA
andB
and stores the result inC
2
: MultipliesA
andB
and stores the result inC
3
: Reads an integer from input and stores the result inA
4
: Outputs the value read fromA
5
: Jump-if-true. IfA
is non-zero, it sets the instruction pointer to the value ofB
6
: Jump-if-equal. IfA
is zero, it sets the instruction pointer to the valueB
7
: Less than. IfA
is less thanB
, it stores1
in the position given byC
. Otherwise, it stores0
8
: Equals. IfA
is equal toB
, it stores1
in the position given byC
. Otherwise, it stores0
9
Adjusts the RelativeCounter by the value ofA
. 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 code-golf! 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
3Esolangs page – Lyxal – 2019-12-25T03:40:52.990
2@Jono2906 Of course it has one. I didn't even think to look. – Draco18s no longer trusts SE – 2019-12-25T03:41:59.643
1Also, where's my rewritten intcode interpreter when I need it! Probably on my home computer. – Lyxal – 2019-12-25T03:43:26.123
"The rightmost two digits of an opcode indicate the opcode itself" Do you mean decimal digits? – tsh – 2019-12-25T08:01:45.787
May
RelativeCounter
be negative during execution? – tsh – 2019-12-25T08:48:58.690Do programs always be terminated by opcode 99? Or could they be terminated by setting instruction pointer out of bound? In another word, may I assume the instruction pointer would always be valid (in the range of 0 ~ program.length - 1)? – tsh – 2019-12-25T09:11:58.370
Are we supposed to support multiple inputs? It seems like there's no test case for that. – Arnauld – 2019-12-25T17:29:54.007
1@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 modes0
,1
, and2
. – Draco18s no longer trusts SE – 2019-12-25T18:07:59.7731@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. – Draco18s no longer trusts SE – 2019-12-25T18:10:26.077
1
@tsh Missed your other comment earlier: yes, it may be. But negative memory addresses don't exist. Day 9, For example, given a relative base of 50, a relative mode parameter of -7 refers to memory address
– Draco18s no longer trusts SE – 2019-12-25T21:37:51.09050 + -7 = 43.
... It is invalid to try to access memory at a negative address, though.