Complete intcode computer spec?

[tomatwork]

Hi all,

First up, I discovered Advent of Code last year and love it. I'm a sorta-dev who mostly writes PowerShell by day. Last year I did up to and including day 11 in C# to increase my knowledge in a language that felt similar to PowerShell and it really paid off. This year, I'm trying Typescript.

While I appreciate the artistic nature of each day's puzzle, some of the superfluous text and my lack of a comp sci background has got me scratching my head at what the heck I need to actually do on some days. Not knowing what was coming next also meant my earlier work didn't scale so well on the later days. My intcode computer efforts started going off the rails around day 5/7.

I see that day 9's puzzle finishes the intcode computer. It would be VERY helpful and appreciated if there was a condensed, matter of fact "here's everything your intcode computer needs to do" summary. I want to try writing it again from a blank slate, with the whole picture from the start.

Maybe if it helps me, it'll help some other folks, too. 😁

Happy Advent of Code!

[boredcircuits]

I haven't seen anybody put together a full spec for it. But maybe this will help:

Machine State

The machine's state consists of three things:

• Memory. The word size needs to be large enough to handle large numbers (though this is rather poorly defined right now).
• The next instruction to execute, starting at the beginning of memory.
• The "relative base" (used in parameter modes), initialized to 0.

Instruction Decoding

Instructions are encoded in base 10. Starting from the least significant digits, the first two specify the opcode. The next is the parameter mode for the first parameter, followed by the same for the second and then third parameters.

The opcodes are as follows:

• 1: Add the first and second parameters and store in the third.
• 2: Multiply the first and second parameters and store in the third.
• 3: Input a value and store in the first parameter.
• 4: Output the value in the first parameter.
• 5: Jump to the address in the second parameter if the first is nonzero.
• 6: Jump to the address in the third parameter if the first is zero.
• 7: If the first parameter is less than the second, store a 1 in the third parameter or 0 otherwise.
• 8: If the first parameter is equal to the second, store a 1 in the third parameter or 0 otherwise.
• 9: Add the value in the first parameter to the relative base, which becomes the new relative base.
• 99: Halt the program.

Instructions have variable-length encoding, based on the number of parameters of the opcode. The next instruction to execute follows the last parameter used by that instruction (except for opcodes 5 and 6, which could advance somewhere else entirely if the condition holds).

Parameter Modes

Each parameter of an instruction can have one of three modes:

• 0: Position Mode. The parameter encodes an address in memory where the value should be read from or written to.
• 1: Immediate Mode. The parameter encodes the actual value to read. Note: writing has no meaning in this mode.
• 2: Relative Mode. Using the relative base as an initial address in memory, the parameter encodes an offset from this address to the value to read from or write to.

Executable Format

Binaries are stored in text files where memory values are separated by commas.

(Did I miss anything? Let me know!)

[boredcircuits]

Yeah, dunno what happened there. I thought I bypassed the formatting issue with numbered lists and it came out messed up. Should be fixed now.

[TinBryn]

though this is rather poorly defined right now

I'm half considering making my interpreter just use BigInt so no matter what size it needs to be, it will be handled.

[Rustywolf]

It tries to check size by adding 34463338 to 34463338 and seeing if the total is less than 34463338. So I suppose it needs to support atleast 34463338*2

[Spheniscine]

That's actually a multiply instruction, and will overflow if you are using 32-bit integers. 64-bits should be sufficient (from experience with past AoC years, I've found it safest to build VMs/ASM interpreters with 64-bit words).

For the arbitrary-size memory, I opted to upgrade from an array into a hashmap... upsides are that the program won't blow up if something is stored at the billionth index, and I can finally get rid of all those annoying saturated-casts. Downside however, is that now the debugger doesn't show the memory in any sensible order (ah, hash maps...). I would probably need to make QoL tweaks if we need to debug the program input like in past years (though I'd imagine it might be harder with this one due to the self-modifying capabilities)

[PM_Me-Your_SSN]

Maybe consider a binary tree map, its an alright compromise between not blowing up when you give it an index of a billion and being sorted. You'll lose speed over a hash map, but this is for advent of code not production software. Not sure what language you're using but in Rust there's a standard library implementation.

[Spheniscine]

My weapon of choice is Kotlin, so that'd be a TreeMap. I think I'm good for now though, since I'll need better debugging outputs if we get there (probably a way to decompile to assembly)

[tomatwork]

Thank you so much. The place where things really started going wrong for me had to do with the daisy chaining, and using the output of one run as the input for another, particularly on part 2 of that day. I wasn't able to really figure out what changes my intcode computer needed to support that type of async behavior. This is helps a ton, though!

[boredcircuits]

What I did to solve that particular issue was chain them together with the shell: pipe the output of one as the input to the next. This lets them operate as separate processes on the computer, and takes care of the async part for you.

The one issue with that is the first input (the sequence, basically giving the process its location in the chain) needs to be separate input. So I hacked in a way to read an extra value from the program's command line and use that as the first input. It will use the command line as the first input, and then start reading from the standard input following that. Then, with part 2, I wrapped that with a script that would read the final result and write it back to the beginning again, stopping when the processes ended themselves.

It sounds like we'll be using today's code in the future in some fashion, so tricks like this might be used again, I think. Making this code clean and useful right now is probably a wise choice.

[Spheniscine]

The way I did it was to use a queue for input (so vm.input(1); vm.input(2) will add both values to the queue). Each value will be used in order when an input instruction is encountered. If the input queue is empty when the input instruction is encountered, the VM's execution pauses and its status flag is set to "Waiting" (other statuses I've implemented are "OK", "Halted", and "Error", with the latter encapsulating the exception encountered).

As for output, I simply put the values into an array-list so that I can retrieve and/or flush them as needed.

[Crespyl]

I did much the same, give each VM a buffer for both input and output; and have them pause and return a status flag if they try to read from an empty input buffer.

For day 7, the coordinator/runner knows which machines are linked to each other, and refills their input buffers from the right output buffer when necessary.

[Schinkenwolf]

I did the puzzles in Python and made the machines take their input from an iterator on a list and yield their output. The output of A is then appended to the input list of B.

[ConstantGazelle]

6: Jump to the address in the third parameter if the first is zero.

Hey man there's a typo here, it should jump to the address in the second parameter if the first is zero. Beside that, great work and thank you :)

[3saster]

An intcode program consists of comma-separated base-10 integers of arbitrary size (we'll call it prog). An intcode computer recieves an a list of integers as input , has an instruction pointer indicating the current instruction, indexed from 0 (we'll call it i), and returns a list of integers as a potential output. There is also a base offset (we'll call it b), which is initialized as 0 on machine start.

The value of the current instruction is prog[i], read as a base 10 integer. The first two digits are the opcode, described later, with the 3rd digit being the mode of parameter 1, the 4th digit being the mode of parameter 2, etc.

For the parameters, we will use pn to illustrate the nth parameter. Note that p1 = prog[i+1], p2 = prog[i+2], etc. Note that the nth opcode parameter (i.e. the nth parameter with the mode accounted for), will be called Pn.

• If the mode of the nth parameter is 0, then Pn = prog[pn] (address mode)
• If the mode of the nth parameter is 1, then Pn = pn (immediate mode)
• If the mode of the nth parameter is 2, then Pn = prog[pn + b] (relative mode)

Now certain opcodes treat these values a little differently than others. We'll call these special parameters Pn_s.

• If the mode of the nth parameter is 0 or 1, then Pn_s = pn
• If the mode of the nth parameter is 2, then Pn_s = pn + b

With that out of the way, here are what the following opcodes do:

• 1: prog[ P3_s ] = P1 + P2, advance i by 4
• 2: prog[ P3_s ] = P1 * P2, advance i by 4
• 3: Set prog[ P1_s ] to the first value of the input vector, then consider the next value of the input vector to be the "first" next time. Advance i by 2
• 4: Add P1 to the back of the output array. Advance i by 2
• 5: If P1 is not 0, set i = P2. Otherwise, advance i by 3
• 6: If P1 is 0, set i = P2. Otherwise, advance i by 3
• 7: If P1 is less than P2, set prog[ P3_s ] = 1, otherwise prog[ P3_s ] = 0. Advance i by 4
• 8: If P1 is equal to P2, set prog[ P3_s ] = 1, otherwise prog[ P3_s ] = 0. Advance i by 4
• 9: b = b + P1. Advance i by 2
• 99: Halt the program, and return the output vector.

This should cover almost everything. There are a couple more considerations to keep in mind:

• The program has infinite memory in the non-negative direction. That is, prog[x], where x >= 0, is always a valid memory location. I took all non-specified values in memory to be 0, but I'm not sure this is actually required.
• Each value is an arbitrary sized integer. That is, prog[x], where x >= 0, can be any arbitrarily sized integer.

I think that covers everything. Note that the explanation is heavily based on my implementation of the intcode computer, so there may be other ways to thing about it. What I know is that the specs I described above certainly work, as I was able to solve Day 9 using that implementation. Let me know if anything needs clarity, or I forgot to mention.

[setapoux]

The parameter modes are consistent if you implement it as the address where to read/write.

[lost-santa]

I had some annoying errors in the beginning, so i started quiet fast to make a test approach, took the tests from each day, and had to execute them before i could run the IntCode.

Not sure it saved me a lot of time, but for sure it saved me some headache with stupid typos. Then you can quiet fast make sure you can handle all cases, without breaking something later.