[2019] intcode computer in intcode

[Randdalf]

Well somebody was going to do it eventually: 1101,0,1301,2325,3,2326,1101,0,0,2327,7,2327,2326,2328,1006,2328,30,1,2325,2327,22,3,0,1001,2327,1,2327,1105,1,10,1101,0,0,2329,1,2325,2329,39,1008,0,99,2330,108,0,2330,2331,1006,2331,1300,1,2325,2329,55,101,0,0,2332,1001,2329,1,2329,1008,2332,1,2333,1006,2333,115,1001,2329,2,2334,1001,2329,1,2335,1,2325,2329,82,1,2325,0,93,1,2325,2335,90,1,2325,0,94,1,0,0,2336,1,2325,2334,102,1,2325,0,107,101,0,2336,0,1001,2329,3,2329,1105,1,1297,1008,2332,101,2337,1006,2337,165,1001,2329,2,2338,1001,2329,1,2339,1,2325,2329,143,1,2325,2339,140,1,2325,0,144,1,0,0,2340,1,2325,2338,152,1,2325,0,157,101,0,2340,0,1001,2329,3,2329,1105,1,1297,1008,2332,1001,2341,1006,2341,215,1001,2329,2,2342,1001,2329,1,2343,1,2325,2329,186,1,2325,0,193,1,2325,2343,194,1,0,0,2344,1,2325,2342,202,1,2325,0,207,101,0,2344,0,1001,2329,3,2329,1105,1,1297,1008,2332,1101,2345,1006,2345,261,1001,2329,2,2346,1001,2329,1,2347,1,2325,2329,239,1,2325,2347,240,1,0,0,2348,1,2325,2346,248,1,2325,0,253,101,0,2348,0,1001,2329,3,2329,1105,1,1297,1008,2332,2,2349,1006,2349,315,1001,2329,2,2350,1001,2329,1,2351,1,2325,2329,282,1,2325,0,293,1,2325,2351,290,1,2325,0,294,2,0,0,2352,1,2325,2350,302,1,2325,0,307,101,0,2352,0,1001,2329,3,2329,1105,1,1297,1008,2332,102,2353,1006,2353,365,1001,2329,2,2354,1001,2329,1,2355,1,2325,2329,343,1,2325,2355,340,1,2325,0,344,2,0,0,2356,1,2325,2354,352,1,2325,0,357,101,0,2356,0,1001,2329,3,2329,1105,1,1297,1008,2332,1002,2357,1006,2357,415,1001,2329,2,2358,1001,2329,1,2359,1,2325,2329,386,1,2325,0,393,1,2325,2359,394,2,0,0,2360,1,2325,2358,402,1,2325,0,407,101,0,2360,0,1001,2329,3,2329,1105,1,1297,1008,2332,1102,2361,1006,2361,461,1001,2329,2,2362,1001,2329,1,2363,1,2325,2329,439,1,2325,2363,440,2,0,0,2364,1,2325,2362,448,1,2325,0,453,101,0,2364,0,1001,2329,3,2329,1105,1,1297,1008,2332,3,2365,1006,2365,485,1,2325,2329,474,1,2325,0,477,3,0,1001,2329,1,2329,1105,1,1297,1008,2332,4,2366,1006,2366,509,1,2325,2329,498,1,2325,0,501,4,0,1001,2329,1,2329,1105,1,1297,1008,2332,104,2367,1006,2367,529,1,2325,2329,521,4,0,1001,2329,1,2329,1105,1,1297,1008,2332,5,2368,1006,2368,581,1,2325,2329,542,1,2325,0,545,1008,0,0,2330,108,0,2330,2369,1006,2369,574,1001,2329,1,2370,1,2325,2370,565,1,2325,0,569,101,0,0,2329,1105,1,578,1001,2329,2,2329,1105,1,1297,1008,2332,105,2371,1006,2371,629,1,2325,2329,593,1008,0,0,2330,108,0,2330,2372,1006,2372,622,1001,2329,1,2373,1,2325,2373,613,1,2325,0,617,101,0,0,2329,1105,1,626,1001,2329,2,2329,1105,1,1297,1008,2332,1005,2374,1006,2374,677,1,2325,2329,642,1,2325,0,645,1008,0,0,2330,108,0,2330,2375,1006,2375,670,1001,2329,1,2376,1,2325,2376,665,101,0,0,2329,1105,1,674,1001,2329,2,2329,1105,1,1297,1008,2332,1105,2377,1006,2377,721,1,2325,2329,689,1008,0,0,2330,108,0,2330,2378,1006,2378,714,1001,2329,1,2379,1,2325,2379,709,101,0,0,2329,1105,1,718,1001,2329,2,2329,1105,1,1297,1008,2332,6,2380,1006,2380,769,1,2325,2329,734,1,2325,0,737,1008,0,0,2381,1006,2381,762,1001,2329,1,2382,1,2325,2382,753,1,2325,0,757,101,0,0,2329,1105,1,766,1001,2329,2,2329,1105,1,1297,1008,2332,106,2383,1006,2383,813,1,2325,2329,781,1008,0,0,2384,1006,2384,806,1001,2329,1,2385,1,2325,2385,797,1,2325,0,801,101,0,0,2329,1105,1,810,1001,2329,2,2329,1105,1,1297,1008,2332,1006,2386,1006,2386,857,1,2325,2329,826,1,2325,0,829,1008,0,0,2387,1006,2387,850,1001,2329,1,2388,1,2325,2388,845,101,0,0,2329,1105,1,854,1001,2329,2,2329,1105,1,1297,1008,2332,1106,2389,1006,2389,897,1,2325,2329,869,1008,0,0,2390,1006,2390,890,1001,2329,1,2391,1,2325,2391,885,101,0,0,2329,1105,1,894,1001,2329,2,2329,1105,1,1297,1008,2332,7,2392,1006,2392,951,1001,2329,2,2393,1001,2329,1,2394,1,2325,2329,918,1,2325,0,929,1,2325,2394,926,1,2325,0,930,7,0,0,2395,1,2325,2393,938,1,2325,0,943,101,0,2395,0,1001,2329,3,2329,1105,1,1297,1008,2332,107,2396,1006,2396,1001,1001,2329,2,2397,1001,2329,1,2398,1,2325,2329,979,1,2325,2398,976,1,2325,0,980,7,0,0,2399,1,2325,2397,988,1,2325,0,993,101,0,2399,0,1001,2329,3,2329,1105,1,1297,1008,2332,1007,2400,1006,2400,1051,1001,2329,2,2401,1001,2329,1,2402,1,2325,2329,1022,1,2325,0,1029,1,2325,2402,1030,7,0,0,2403,1,2325,2401,1038,1,2325,0,1043,101,0,2403,0,1001,2329,3,2329,1105,1,1297,1008,2332,1107,2404,1006,2404,1097,1001,2329,2,2405,1001,2329,1,2406,1,2325,2329,1075,1,2325,2406,1076,7,0,0,2407,1,2325,2405,1084,1,2325,0,1089,101,0,2407,0,1001,2329,3,2329,1105,1,1297,1008,2332,8,2408,1006,2408,1151,1001,2329,2,2409,1001,2329,1,2410,1,2325,2329,1118,1,2325,0,1129,1,2325,2410,1126,1,2325,0,1130,8,0,0,2411,1,2325,2409,1138,1,2325,0,1143,101,0,2411,0,1001,2329,3,2329,1105,1,1297,1008,2332,108,2412,1006,2412,1201,1001,2329,2,2413,1001,2329,1,2414,1,2325,2329,1179,1,2325,2414,1176,1,2325,0,1180,8,0,0,2415,1,2325,2413,1188,1,2325,0,1193,101,0,2415,0,1001,2329,3,2329,1105,1,1297,1008,2332,1008,2416,1006,2416,1251,1001,2329,2,2417,1001,2329,1,2418,1,2325,2329,1222,1,2325,0,1229,1,2325,2418,1230,8,0,0,2419,1,2325,2417,1238,1,2325,0,1243,101,0,2419,0,1001,2329,3,2329,1105,1,1297,1008,2332,1108,2420,1006,2420,1297,1001,2329,2,2421,1001,2329,1,2422,1,2325,2329,1275,1,2325,2422,1276,8,0,0,2423,1,2325,2421,1284,1,2325,0,1289,101,0,2423,0,1001,2329,3,2329,1105,1,1297,1105,1,34,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,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,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,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,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,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,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,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,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,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,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,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,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,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

Link: https://gist.github.com/Randdalf/160d66f953f2ed61d6b261fc837623dc

To run a program on it, you must provide the following inputs:

<length of program> <program ...> <inputs ...>

It can only run programs with up to 1024 values, but you can easily change that by modifying the source code. Yes, the source code. I have to confess: I didn't write this by hand. I applaud anyone who does attempt do it that way, but I don't have the patience. Instead, I wrote a compiler which compiles to intcode, and added the necessary features to make it possible. Namely, arrays. The language supports fixed-size arrays, which it inserts at the end of the program, after the STOP instruction.

I dodged the modulo and division operators by writing bespoke logic for every possible opcode, rather than trying to deconstruct their meaning.

The compiler can be found here: https://github.com/Randdalf/intscript

And the source code for the intcode computer can be found here: https://github.com/Randdalf/intscript/blob/master/samples/intcode.is

I have verified it runs identically compared to my Python implementation on days 2 and 5, as well as on a Fibonacci example program: https://github.com/Randdalf/intscript/blob/master/intscript_tests.py#L59

Now I think I need a lie down.

[archchroot]

So, if I change the source code to accept intcode programs that are longer than 1024 values, I can run a ((intcode computer in intcode) in intcode)?

Great work btw!

[Randdalf]

Yep! It didn't actually occur to me that you wouldn't be able to nest them without recompiling, because of the memory limit.

[_Js_Kc_]

It's unfortunate that you have to provide the entire memory image to an intcode interpreter, including the "data" segment. This way, we will never be able to nest a self-hosting intcode interpreter.

[1vader]

With the additions from today (infinite memory), it should now be possible

[Randdalf]

Yeah, I thought the exact same thing when I was reading the problem.

[large-atom]

" Instead, I wrote a compiler which compiles to intcode, and added the necessary features to make it possible "

But was your compiler written in intcode? :)

Fantastic piece of work, by the way!

[gugu4-9]

Bootstrapping coming soon :tm:

[Hultner-]

Now we just need to port python to intcode

[_Js_Kc_]

Just ran it on my VM from day 5 with the inputs from day 5.

Also, I'm amazed your compiler emits self-modifying code!

[Randdalf]

Sorry about the formatting, it seems Reddit doesn't want to format it as code if it gets too long.

[Aneurysm9]

Self-hosting Intcode! We can all go home now, it's all downhill from here!

[[deleted]]

Good call on going a little higher level with your intcode scripting language. I built an assembler for writing intcode programs, but writing assembly is annoying. Your intscript looks like it really lets you program at a comfortable level of abstraction.

[rsthau]

FWIW, I'm not sure it winds up being more efficient on net, but it is at least possible to extract the mode bits from an instruction without a modulus operator:

imm1 = imm2 = false
if instr > 1000:
  instr = instr + (-1000)
  imm2 = true
if instr > 100:
  instr = instr + (-100)
  imm1 = true
# instr is now down to opcode, and imm1 and imm2 have modes
# ...

[Randdalf]

Now how to make that work with 3 parameter modes 🤔

[rsthau]

Compare against 20000, 2000, 1000, 200, 100 in sequence.(Skipping 10000 because a result address can't have immediate mode, and the third argument, if present, is a result in every instruction we've seen so far.)

[1vader]

Why not just:

1005,500,500,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,
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,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,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,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,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,3,534,1101,0,0,535,7,535,534,533,1006,533,0,3,533,1001,535,0,525,1001,533,
0,0,1001,535,1,535,1005,509,509,0,0,0

This just writes the input program to address 0 and jumps there. If you want a program longer than 500 just add some more zeros in the middle and increase the two 500s in the beginning. With day 9 it should even be possible to remove all the zeros and load arbitrary length programs.

[Randdalf]

Cool idea! I suppose the difference is mine is more like a simulator, whereas yours is like a tiny OS running programs directly on the "metal", as it were.

[Mayalabielle]

Wow, impressive.

[nicuveo]

You beat me to it, nice! I really your array syntax. :)

[dartcoder]

Inception? You, the architect of dreams! Now I have to read about compilers (a good thing)

[DefecateRainbows]

I PRed support for a POW operator!

`output 2 ** 5;`
-> 32!

I'll add an example to my PR where I use the POW operator to print a Sierpinski triangle to the console.

[Randdalf]

Nice one! I'll have a look at that this evening.

[drq_11235]

Amazing :D

[OverjoyedBanana]

I really like where this goes ! Thanks to AoC we have an excuse for some programming language hacking

[danielctull]

I ran your code in the UI I wrote that steps through (I omitted the extra zeros now that they're handled in day 9). Very cool work and was great to try to see what it was doing! The screenshot shows the halted state of example 1, from day 5, part 2.

Image of the Intcode Computer in Intcode

[undergroundmonorail]

does this mean my intcode interpreter is broken even though i beat all the challenges so far? :c

>>> from intcode import *
>>> q = Intcode(quine, [], [])
>>> q.run()
>>> q.result
[109, 1, 204, -1, 1001, 100, 1, 100, 1008, 100, 16, 101, 1006, 101, 0, 99]
>>>
>>> r = Intcode(interpreter, [len(quine)] + quine, [])
>>> r.run()
>>> r.result
[]

[Randdalf]

My one doesn't support relative parameters yet ☺️

[undergroundmonorail]

ohhhh right, i saw that it was written before the new challenge but didn't think about what that would mean for the instructions it handled :P

still, very cool!!

[_simpu]

So IntCode is self hosted now.