4 "cell_type": "markdown",
7 "# Machine interpreter\n",
11 "Three registers, `a`, `b`, and `c`. \n",
12 "Program counter, `pc`.\n",
13 "Unlimited memory in numbered addresses, completely separate from program storage.\n",
15 "Each register and memory location can hold 8-byte integers (Java `long`s).\n",
17 "Machine carries out the instruction at location `pc`. After it's executed, `pc` increments by 1.\n",
19 "`jmp` and `jpz` override this normal change in `pc`.\n",
21 "| Instruction | Description |\n",
22 "|:------------|:------------|\n",
23 "| `inc r` | increment contents of register `r` |\n",
24 "| `dec r` | decrement contents of register `r` |\n",
25 "| `set r i` | set contents of register `r` to literal value `i` |\n",
26 "| `cpy r s` | copy contents of register `r` into register `s` | \n",
27 "| `sto r m` | store contents of register `r` into memory location `m` |\n",
28 "| `ld r m` | load contents of memory location `m` into register `r` |\n",
29 "| `jmp i` | jump to instruction `i` places forward |\n",
30 "| `jpz r i` | jump to instruction `i` places forward if<br>register `r` contains zero, otherwise continue to next instruction |\n",
32 "For `jmp` and `jpz`, `i` is relative to the current instruction. `i` can be negative to jump to earlier places in the program. `i`=1 is a no-op, `i`=0 causes an infinite loop."
43 "def new_machine():\n",
44 " return {'pc': 0, \n",
48 " 'instructions': []}"
59 "def show_machine(machine):\n",
60 " return ', '.join('{}: {}'.format(sk, machine[int(sk) if sk.isnumeric() else sk]) \n",
61 " for sk in sorted(str(k) for k in machine)\n",
62 " if sk != 'instructions')"
73 "def inc(reg, machine):\n",
74 " machine[reg] += 1\n",
86 "def dec(reg, machine):\n",
87 " machine[reg] -= 1\n",
99 "def jmp(addr, machine):\n",
100 " machine['pc'] += addr"
105 "execution_count": 6,
111 "def jpz(reg, addr, machine):\n",
112 " if machine[reg] == 0:\n",
113 " machine['pc'] += addr\n",
115 " machine['pc'] += 1"
120 "execution_count": 7,
126 "def set_literal(reg, literal, machine):\n",
127 " machine[reg] = literal\n",
128 " machine['pc'] += 1"
133 "execution_count": 8,
139 "def cpy(from_reg, to_reg, machine):\n",
140 " machine[to_reg] = machine[from_reg]\n",
141 " machine['pc'] += 1"
146 "execution_count": 9,
152 "def sto(reg, addr, machine):\n",
153 " machine[addr] = machine[reg]\n",
154 " machine['pc'] += 1"
159 "execution_count": 10,
165 "def ld(reg, addr, machine):\n",
166 " if addr in machine:\n",
167 " machine[reg] = machine[addr]\n",
169 " machine[reg] = 0\n",
170 " machine['pc'] += 1"
175 "execution_count": 11,
181 "instruction_table = {'inc': inc, 'dec': dec, 'jmp': jmp,\n",
182 " 'jpz': jpz, 'set': set_literal, 'cpy': cpy,\n",
183 " 'sto': sto, 'ld': ld}\n",
184 "numeric_args_table = {'jmp': [0], 'jpz': [1], 'set': [1], 'sto': [1], 'ld': [1]}"
189 "execution_count": 12,
195 "def parse(instruction):\n",
196 " words = instruction.split()\n",
197 " instr = words[0]\n",
198 " args = words[1:]\n",
199 " if instr in numeric_args_table:\n",
200 " for p in numeric_args_table[instr]:\n",
201 " args[p] = int(args[p])\n",
202 " return instruction_table[instr], args"
207 "execution_count": 13,
213 "{'a': 2, 'b': 1, 'c': 0, 'instructions': [], 'pc': 3}"
216 "execution_count": 13,
218 "output_type": "execute_result"
222 "m = new_machine()\n",
224 "cargs = ['a', 'b']\n",
232 "execution_count": 14,
238 "def program_from_instructions(prog, machine):\n",
239 " machine['instructions'] = [parse(instr) for instr in prog]"
244 "execution_count": 15,
250 "def program_from_listing(listing, machine):\n",
251 " labelled_instructions = [i.strip() for i in listing.split('\\n') \n",
253 " if not i.strip().startswith('#')]\n",
254 " instructions = replace_labels(labelled_instructions)\n",
255 " program_from_instructions(instructions, machine)"
260 "execution_count": 16,
266 "def replace_labels(listing):\n",
268 " for n, i in enumerate(listing):\n",
270 " locations[i.split(':')[0]] = n\n",
272 " unlabelled_listing = []\n",
273 " for n, i in enumerate(listing):\n",
274 " instr = i.split()\n",
276 " instr = i.split(':')[1].split()\n",
278 " instr = i.split()\n",
280 " for term in instr:\n",
281 " if term in locations:\n",
282 " terms += [str(locations[term] - n)]\n",
284 " terms += [term]\n",
285 " transformed_instr = ' '.join(terms)\n",
286 " unlabelled_listing += [transformed_instr]\n",
288 " return unlabelled_listing "
293 "execution_count": 17,
302 "execution_count": 17,
304 "output_type": "execute_result"
308 "'fred: inc a'.split(':')[1].split()"
313 "execution_count": 18,
318 "output_type": "stream",
330 "program = \"\"\"\n",
340 "labelled_instructions = [i.strip() for i in program.split('\\n') if i.strip() if not i.strip().startswith('#')]\n",
341 "instructions = replace_labels(labelled_instructions)\n",
342 "print('\\n'.join(instructions))"
347 "execution_count": 19,
353 "def run(machine, initial_state=None, trace=False):\n",
354 " if initial_state:\n",
355 " machine.update(initial_state)\n",
356 " while machine['pc'] < len(machine['instructions']):\n",
358 " print(show_machine(machine))\n",
359 " cmd, args = machine['instructions'][machine['pc']]\n",
360 " cmd(*args, machine)"
365 "execution_count": 20,
371 "def execute(listing, initial_state=None, trace=False):\n",
372 " m = new_machine()\n",
373 " program_from_listing(listing, m)\n",
374 " run(m, initial_state=initial_state, trace=trace)\n",
380 "execution_count": 21,
389 " 'instructions': [(<function __main__.inc>, ['a']),\n",
390 " (<function __main__.inc>, ['a']),\n",
391 " (<function __main__.cpy>, ['a', 'b']),\n",
392 " (<function __main__.inc>, ['a'])],\n",
396 "execution_count": 21,
398 "output_type": "execute_result"
402 "program = \"\"\"\n",
413 "execution_count": 22,
422 " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
423 " (<function __main__.dec>, ['a']),\n",
424 " (<function __main__.inc>, ['b']),\n",
425 " (<function __main__.sto>, ['b', 1]),\n",
426 " (<function __main__.jpz>, ['a', 2]),\n",
427 " (<function __main__.jmp>, [-4])],\n",
432 "execution_count": 22,
434 "output_type": "execute_result"
438 "program = \"\"\"\n",
446 "# m = new_machine()\n",
447 "# program_from_listing(program, m)\n",
449 "execute(program, initial_state={'c': 20})"
454 "execution_count": 23,
463 " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
464 " (<function __main__.dec>, ['a']),\n",
465 " (<function __main__.inc>, ['b']),\n",
466 " (<function __main__.sto>, ['b', 1]),\n",
467 " (<function __main__.jpz>, ['a', 2]),\n",
468 " (<function __main__.jmp>, [-4])],\n",
473 "execution_count": 23,
475 "output_type": "execute_result"
479 "program = \"\"\"\n",
487 "execute(program, initial_state={'c': 20})"
492 "execution_count": 24,
501 " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
502 " (<function __main__.set_literal>, ['b', 0]),\n",
503 " (<function __main__.dec>, ['a']),\n",
504 " (<function __main__.jpz>, ['b', 3]),\n",
505 " (<function __main__.dec>, ['b']),\n",
506 " (<function __main__.jmp>, [2]),\n",
507 " (<function __main__.inc>, ['b']),\n",
508 " (<function __main__.jpz>, ['a', 3]),\n",
509 " (<function __main__.jmp>, [-6])],\n",
513 "execution_count": 24,
515 "output_type": "execute_result"
519 "program = \"\"\"\n",
530 "# m = new_machine()\n",
531 "# program_from_listing(program, m)\n",
533 "execute(program, initial_state={'c': 5})"
538 "execution_count": 25,
547 " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
548 " (<function __main__.set_literal>, ['b', 0]),\n",
549 " (<function __main__.dec>, ['a']),\n",
550 " (<function __main__.jpz>, ['b', 3]),\n",
551 " (<function __main__.dec>, ['b']),\n",
552 " (<function __main__.jmp>, [2]),\n",
553 " (<function __main__.inc>, ['b']),\n",
554 " (<function __main__.jpz>, ['a', 2]),\n",
555 " (<function __main__.jmp>, [-6])],\n",
559 "execution_count": 25,
561 "output_type": "execute_result"
565 "# b holds parity of number in c: (c % 2)\n",
566 "program = \"\"\"\n",
577 "# m = new_machine()\n",
578 "# program_from_listing(program, m)\n",
580 "execute(program, initial_state={'c': 5})"
585 "execution_count": 26,
591 "'1: 8, a: 0, b: 1, c: 8, pc: 11'"
594 "execution_count": 26,
596 "output_type": "execute_result"
600 "# c holds floor(a/2)\n",
601 "program = \"\"\"\n",
614 "# m = new_machine()\n",
615 "# program_from_listing(program, m)\n",
617 "show_machine(execute(program, initial_state={'a': 17}))"
622 "execution_count": 27,
628 "'a: 4, b: 0, c: 12, pc: 9'"
631 "execution_count": 27,
633 "output_type": "execute_result"
638 "program = \"\"\"\n",
641 " # start of main loop\n",
649 " # end of program \n",
653 "# m = new_machine()\n",
654 "# program_from_listing(program, m)\n",
656 "show_machine(execute(program, initial_state={'a': 4}))"
661 "execution_count": 28,
667 "'1: 0, a: 0, b: 0, c: 27, pc: 11'"
670 "execution_count": 28,
672 "output_type": "execute_result"
677 "program = \"\"\"\n",
680 "loop: jpz b end \n",
683 "smul: jpz a emul\n",
691 "m = new_machine()\n",
692 "program_from_listing(program, m)\n",
694 "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
699 "execution_count": 29,
704 "output_type": "stream",
721 "labelled_instructions = [i.strip() for i in program.split('\\n') if i.strip() if not i.strip().startswith('#')]\n",
722 "instructions = replace_labels(labelled_instructions)\n",
723 "print('\\n'.join(instructions))"
728 "execution_count": 30,
734 "'1: 0, a: 0, b: 0, c: 10, pc: 13'"
737 "execution_count": 30,
739 "output_type": "execute_result"
744 "program = \"\"\"\n",
749 "loop: jpz b end \n",
752 "smul: jpz a emul\n",
760 "m = new_machine()\n",
761 "program_from_listing(program, m)\n",
763 "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
768 "execution_count": 31,
773 "output_type": "stream",
792 "labelled_instructions = [i.strip() for i in program.split('\\n') \n",
794 " if not i.strip().startswith('#')]\n",
795 "instructions = replace_labels(labelled_instructions)\n",
796 "print('\\n'.join(instructions))"
801 "execution_count": 32,
807 "'1: 0, a: 52, b: 0, c: 0, pc: 48'"
810 "execution_count": 32,
812 "output_type": "execute_result"
816 "# Collatz. a initially holds value, but location 1 is used to store the current value as we're going along.\n",
817 "# Location 2 holds number of steps taken\n",
818 "# Location 3 holds max value reached\n",
819 "program = \"\"\"\n",
824 " # if a is one, finish, \n",
829 " # find parity of a\n",
840 " # b == 0 means a even; b == 1 means a odd\n",
843 " # c holds a * 3 + 1\n",
870 "maxc: jpz c this\n",
878 " # end of program \n",
884 "# m = new_machine()\n",
885 "# program_from_listing(program, m)\n",
887 "show_machine(execute(program, initial_state={'a': 7}))"
892 "execution_count": 33,
901 "execution_count": 33,
903 "output_type": "execute_result"
912 "execution_count": 34,
918 "def max_collatz(start):\n",
933 "execution_count": 35,
942 "execution_count": 35,
944 "output_type": "execute_result"
953 "execution_count": 36,
962 "execution_count": 36,
964 "output_type": "execute_result"
968 "max([(max_collatz(i), i) for i in range(1, 1000)])"
973 "execution_count": 41,
982 "execution_count": 41,
984 "output_type": "execute_result"
988 "max([(max_collatz(i), i) for i in range(1, 10)])"
993 "execution_count": 37,
1027 " (27, 0, 9232),\n",
1031 " (31, 0, 9232),\n",
1041 " (41, 0, 9232),\n",
1047 " (47, 0, 9232),\n",
1054 " (54, 0, 9232),\n",
1055 " (55, 0, 9232),\n",
1062 " (62, 0, 9232),\n",
1063 " (63, 0, 9232),\n",
1071 " (71, 0, 9232),\n",
1073 " (73, 0, 9232),\n",
1082 " (82, 0, 9232),\n",
1083 " (83, 0, 9232),\n",
1091 " (91, 0, 9232),\n",
1094 " (94, 0, 9232),\n",
1095 " (95, 0, 9232),\n",
1097 " (97, 0, 9232),\n",
1102 "execution_count": 37,
1104 "output_type": "execute_result"
1109 "for i in range(1, 100):\n",
1110 " m = execute(program, initial_state={'a': i})\n",
1111 " c = max_collatz(i)\n",
1113 " ans += [(i, m[1], c)]\n",
1118 "cell_type": "code",
1119 "execution_count": 38,
1125 "'1: 0, a: 250504, b: 0, c: 0, pc: 48'"
1128 "execution_count": 38,
1130 "output_type": "execute_result"
1134 "show_machine(execute(program, initial_state={'a': 937}))"
1138 "cell_type": "code",
1139 "execution_count": 40,
1144 "output_type": "stream",
1146 "1 loop, best of 3: 38.6 s per loop\n"
1152 "show_machine(execute(program, initial_state={'a': 937}))"
1156 "cell_type": "code",
1157 "execution_count": 39,
1163 "# labelled_instructions = [i.strip() for i in program.split('\\n') \n",
1164 "# if i.strip() \n",
1165 "# if not i.strip().startswith('#')]\n",
1166 "# instructions = replace_labels(labelled_instructions)\n",
1167 "# print('\\n'.join(instructions))\n",
1168 "# open('07-program.txt', 'w').write('\\n'.join(instructions))"
1172 "cell_type": "code",
1173 "execution_count": null,
1183 "display_name": "Python 3",
1184 "language": "python",
1188 "codemirror_mode": {
1192 "file_extension": ".py",
1193 "mimetype": "text/x-python",
1195 "nbconvert_exporter": "python",
1196 "pygments_lexer": "ipython3",