Intcode Quine

about.md

The Intcode Quine

Intcode is a simple virtual machine language devised for the advent of code programming challenge. It is comprised of a sequence of integer values, separated by commas.

A quine is a program which outputs its own source code.

A Ruby VM implementation to run Intcode is available here: https://github.com/seanhandley/adventofcode2019/tree/master/ruby/vm

annotated_quine.rb

109,1,           # Increment relative-offset by 1
204,-1,          # Output contents of memory location at relative-offset minus 1
1001,100,1,100,  # Increment contents of location 100 by 1
1008,100,16,101, # Check if contents of location 100 equal 16, store result in 101
1006,101,0,      # Jump to position zero if value at location 101 is zero
99               # Halt

# Effectively, this program loops through each position it occupies in memory
# and outputs the contents of that location until it reaches the end.
# To do this, the program author knows the total program length is 16 elements,
# and uses two working locations to a) increment a loop counter and b) record
# whether the loop counter has reached 16.

# The following piece of Ruby demonstrates this conceptually:

@memory = [109, 1, 204, -1, 1001, 100, 1, 100, 1008, 100, 16, 101, 1006, 101, 0, 99]

i = 0
while i < 16
  puts @memory[i]
  i += 1
end

intcode.md

About Intcode Programs

A full intcode program contains instructions in the order in which they should be executed. An instruction is an opcode followed by its operands e.g.

1,2,4,6

This is the add instruction denoted by opcode1, followed by three operands: 2, 4, and 6.

A program starts with instruction pointer at position 0 and this pointer is updated after each instruction completes.

Data is stored in a single array using the same space as instructions i.e. all elements can be read from or written to.

Valid Opcodes

• 01 Add. Adds two numbers and stores the result.
• 02 Multiply. Multiplies two numbers and stores the result.
• 03 Read. Reads an input value and stores it.
• 04 Write. Outputs a value.
• 05 Jump if non-zero. If the first operand is non-zero, sets the instruction pointer to the second operand.
• 06 Jump if zero. If the first operand is zero, sets the instruction pointer to the second operand.
• 07 Less than. If the first operand is smaller than the second, output 1 to the location defined by the third operand, otherwise 0.
• 08 Equals. If the first operand is equal to the second, output 1 to the location defined by the third operand, otherwise 0.
• 09 Adjust relative base offset. Increment the relative base offset value by the value defined by the given operand.
• 99 Halt the program.

Addressing Modes

Operands can be referenced in three address modes:

1. Positional. The operand indicates the memory position from which to read the desired value.
2. Absolute. The operand itself is the desired value.
3. Relative. The operand is defined relative to a base offset i.e. operand is -1 and relative base offset is 10, so the location to read from is 9.

These modes are stored in the same value as the instruction's opcode.

The opcode is a two-digit number based only on the ones and tens digit of the value, that is, the opcode is the rightmost two digits of the first value in an instruction. Parameter modes are single digits, one per parameter, read right-to-left from the opcode: the first parameter's mode is in the hundreds digit, the second parameter's mode is in the thousands digit, the third parameter's mode is in the ten-thousands digit, and so on. Any missing modes are 0.

For example, consider the program 1002,4,3,4,33. Position 0 is the opcode 1002, positions 1 to 3 contain the operands 4, 3, and 4. Position 4 contains the value 33.

The first instruction, 1202,4,3,4, is a multiply instruction - the rightmost two digits of the first value, 02, indicate opcode 2, multiplication. Then, going right to left, the parameter modes are 0 (hundreds digit), 1 (thousands digit), and 0 (ten-thousands digit, not present and therefore zero):

ABCDE
 1202

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

The first operand is 4 in a relative address mode. If the relative base address is zero, then the address location will be 4, which contains 33 in the given example. If the relative base were higher, e.g. 10 then the address location would be 14 which in this program is empty and would be considered value 0.

run.log

[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 1
[c86198b2][2] READ ARG 0 from relative position 0
[c86198b2][2] OUTPUT 109
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 0 + 1 = 1
[c86198b2][4] WRITE 1 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 1 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 2
[c86198b2][2] READ ARG 0 from relative position 1
[c86198b2][2] OUTPUT 1
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 1 + 1 = 2
[c86198b2][4] WRITE 2 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 2 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 3
[c86198b2][2] READ ARG 0 from relative position 2
[c86198b2][2] OUTPUT 204
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 2 + 1 = 3
[c86198b2][4] WRITE 3 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 3 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 4
[c86198b2][2] READ ARG 0 from relative position 3
[c86198b2][2] OUTPUT -1
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 3 + 1 = 4
[c86198b2][4] WRITE 4 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 4 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 5
[c86198b2][2] READ ARG 0 from relative position 4
[c86198b2][2] OUTPUT 1001
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 4 + 1 = 5
[c86198b2][4] WRITE 5 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 5 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 6
[c86198b2][2] READ ARG 0 from relative position 5
[c86198b2][2] OUTPUT 100
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 5 + 1 = 6
[c86198b2][4] WRITE 6 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 6 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 7
[c86198b2][2] READ ARG 0 from relative position 6
[c86198b2][2] OUTPUT 1
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 6 + 1 = 7
[c86198b2][4] WRITE 7 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 7 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 8
[c86198b2][2] READ ARG 0 from relative position 7
[c86198b2][2] OUTPUT 100
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 7 + 1 = 8
[c86198b2][4] WRITE 8 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 8 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 9
[c86198b2][2] READ ARG 0 from relative position 8
[c86198b2][2] OUTPUT 1008
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 8 + 1 = 9
[c86198b2][4] WRITE 9 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 9 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 10
[c86198b2][2] READ ARG 0 from relative position 9
[c86198b2][2] OUTPUT 100
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 9 + 1 = 10
[c86198b2][4] WRITE 10 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 10 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 11
[c86198b2][2] READ ARG 0 from relative position 10
[c86198b2][2] OUTPUT 16
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 10 + 1 = 11
[c86198b2][4] WRITE 11 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 11 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 12
[c86198b2][2] READ ARG 0 from relative position 11
[c86198b2][2] OUTPUT 101
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 11 + 1 = 12
[c86198b2][4] WRITE 12 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 12 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 13
[c86198b2][2] READ ARG 0 from relative position 12
[c86198b2][2] OUTPUT 1006
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 12 + 1 = 13
[c86198b2][4] WRITE 13 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 13 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 14
[c86198b2][2] READ ARG 0 from relative position 13
[c86198b2][2] OUTPUT 101
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 13 + 1 = 14
[c86198b2][4] WRITE 14 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 14 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 15
[c86198b2][2] READ ARG 0 from relative position 14
[c86198b2][2] OUTPUT 0
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 14 + 1 = 15
[c86198b2][4] WRITE 15 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 15 == 16 = false
[c86198b2][8] WRITE 0 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 0 (jumping to loc 0)
[c86198b2][0] READ ARG 0 from absolute position 1
[c86198b2][0] RB 16
[c86198b2][2] READ ARG 0 from relative position 15
[c86198b2][2] OUTPUT 99
[c86198b2][4] READ ARG 0 from position 100
[c86198b2][4] READ ARG 1 from absolute position 6
[c86198b2][4] READ ARG 2 from position 100
[c86198b2][4] ADD 15 + 1 = 16
[c86198b2][4] WRITE 16 to 100
[c86198b2][8] READ ARG 0 from position 100
[c86198b2][8] READ ARG 1 from absolute position 10
[c86198b2][8] READ ARG 2 from position 101
[c86198b2][8] EQ 16 == 16 = true
[c86198b2][8] WRITE 1 to 101
[c86198b2][12] READ ARG 0 from position 101
[c86198b2][12] READ ARG 1 from absolute position 14
[c86198b2][12] JEZ loc 101 is 1 (no jump)
[c86198b2][15] HALT
[c86198b2][15] CORE DUMP: [109, 1, 204, -1, 1001, 100, 1, 100, 1008, 100, 16, 101, 1006, 101, 0, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 1]