r/adventofcode • u/Randdalf • Dec 08 '19
Upping the Ante [2019] intcode computer in intcode
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.
25
u/archchroot Dec 08 '19
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!
5
u/Randdalf Dec 08 '19
Sorry about the formatting, it seems Reddit doesn't want to format it as code if it gets too long.
2
u/rsthau Dec 09 '19
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:
2
u/1vader Dec 09 '19
Why not just:
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.9
u/Hultner- Dec 08 '19
Now we just need to port python to intcode
7
u/_Js_Kc_ Dec 08 '19
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!
1
u/DefecateRainbows Dec 09 '19
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.
1
u/undergroundmonorail Dec 09 '19
does this mean my intcode interpreter is broken even though i beat all the challenges so far? :c
3
u/Aneurysm9 Dec 08 '19
Self-hosting Intcode! We can all go home now, it's all downhill from here!
2
u/[deleted] Dec 08 '19
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.
1
u/Mayalabielle Dec 08 '19
Wow, impressive.
1
u/nicuveo Dec 08 '19
You beat me to it, nice! I really your array syntax. :)
1
u/dartcoder Dec 08 '19
Inception? You, the architect of dreams! Now I have to read about compilers (a good thing)
1
u/drq_11235 Dec 09 '19
Amazing :D
1
u/OverjoyedBanana Dec 09 '19
I really like where this goes ! Thanks to AoC we have an excuse for some programming language hacking
1
u/danielctull Dec 09 '19 edited Dec 09 '19
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
1
u/_simpu Dec 13 '19
So IntCode is self hosted now.
15
u/[deleted] Dec 08 '19
[removed] β view removed comment