"\n",
"## Instructions\n",
"\n",
- "Four registers, `a`, `b`, `c`, and `d`.\n",
- "Program counter, `pc`.\n",
+ "After a good day sightseeing, it's back to the hotel and time for some refreshment. Unfortunately, the minibar in your room refuses to open. It's been hacked, with some ransomware! You'll need to provide the correct unlock code so you can get a nice, cold drink.\n",
"\n",
- "Each register can hold 8-byte integers (Java `long`s).\n",
+ "You could pay a large chunk of bitcoin, or you could defeat the ransomware some other way. \n",
"\n",
- "Machine carries out the instruction at location `pc`. After it's executed, `pc` increments by 1.\n",
+ "You quickly find the schematics of the minibar lock. It's a fairly simple machine. It has four registers, `a`, `b`, `c`, `d`, and a special purpose `pc` register for the program counter. Each register can hold a 64-bit value (far bigger than any number in the programs you'll be running). You can assume all registers hold zero when the program starts.\n",
"\n",
- "`jmp` and `jpz` override this normal change in `pc`.\n",
+ "On each clock tick, the machine executes the instruction pointed to by the `pc`, then increments `pc`. The machine halts when the machine tries to read from a location beyond the end of the program.\n",
+ "\n",
+ "The machine has only a few instructions. They're listed by handy mnemonics:\n",
"\n",
"| Instruction | Description |\n",
"|:------------|:------------|\n",
"| `jmp i` | jump to instruction `i` places forward |\n",
"| `jpz r i` | jump to instruction `i` places forward if<br>register `r` contains zero, otherwise continue to next instruction |\n",
"\n",
- "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."
+ "The `jmp` and `jpz` instructions jump relative to the current instruction, overriding the normal change in `pc`. `jmp -1` would jump back to the previous instruction; `jpz a 2` would skip the next instruction if register `a` contains zero.\n",
+ "\n",
+ "Before you start execution of a program, you can set the values of some registers.\n",
+ "\n",
+ "For example, this program multiplies the values in the a and b registers, leaving the result in the c register:\n",
+ "\n",
+ "```\n",
+ "set c 0\n",
+ "cpy a d\n",
+ "jpz b 8\n",
+ "dec b\n",
+ "cpy d a\n",
+ "jpz a 4\n",
+ "inc c\n",
+ "dec a\n",
+ "jmp -3\n",
+ "jmp -7\n",
+ "set d 0\n",
+ "```\n",
+ "\n",
+ "# Part 1\n",
+ "\n",
+ "You think you've worked out how to generate the code wanted by the ransomware. The program is given in `07-program.txt`, one instruction per line. \n",
+ "\n",
+ "Starting with register `a` holding 7, and all other registers holding zero, what does register `a` contain when the program finishes?"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "It seems your guess of 7 as the starting value was wrong.\n",
+ "\n",
+ "# Part 2\n",
+ "\n",
+ "The program is still given in `07-program.txt`, one instruction per line. \n",
+ "\n",
+ "Starting with register `a` holding 937, and all other registers and memory locations holding zero, what does register `a` contain when the program finishes?"
]
},
{
},
{
"cell_type": "code",
- "execution_count": 45,
+ "execution_count": 13,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 13,
+ "execution_count": 14,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 53,
+ "execution_count": 15,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 14,
+ "execution_count": 16,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 15,
+ "execution_count": 17,
"metadata": {},
"outputs": [
{
"['inc', 'a']"
]
},
- "execution_count": 15,
+ "execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 47,
+ "execution_count": 18,
"metadata": {},
"outputs": [
{
},
{
"cell_type": "code",
- "execution_count": 49,
+ "execution_count": 19,
"metadata": {},
"outputs": [
{
},
{
"cell_type": "code",
- "execution_count": 17,
+ "execution_count": 20,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 18,
+ "execution_count": 21,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 19,
+ "execution_count": 22,
"metadata": {},
"outputs": [
{
" 'pc': 4}"
]
},
- "execution_count": 19,
+ "execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 20,
+ "execution_count": 23,
"metadata": {},
"outputs": [
{
" 'pc': 5}"
]
},
- "execution_count": 20,
+ "execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 21,
+ "execution_count": 24,
"metadata": {},
"outputs": [
{
" 'pc': 5}"
]
},
- "execution_count": 21,
+ "execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 22,
+ "execution_count": 25,
"metadata": {},
"outputs": [
{
" 'pc': 10}"
]
},
- "execution_count": 22,
+ "execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 71,
+ "execution_count": 26,
"metadata": {},
"outputs": [
{
" 'pc': 9}"
]
},
- "execution_count": 71,
+ "execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 64,
+ "execution_count": 27,
"metadata": {},
"outputs": [
{
},
{
"cell_type": "code",
- "execution_count": 65,
+ "execution_count": 28,
"metadata": {},
"outputs": [
{
"'a: 0, b: 1, c: 8, d: 0, pc: 10'"
]
},
- "execution_count": 65,
+ "execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 66,
+ "execution_count": 29,
"metadata": {},
"outputs": [
{
},
{
"cell_type": "code",
- "execution_count": 25,
+ "execution_count": 30,
"metadata": {},
"outputs": [
{
"'a: 4, b: 0, c: 12, d: 0, pc: 9'"
]
},
- "execution_count": 25,
+ "execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 67,
+ "execution_count": 31,
"metadata": {},
"outputs": [
{
"'a: 0, b: 0, c: 27, d: 0, pc: 11'"
]
},
- "execution_count": 67,
+ "execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 68,
+ "execution_count": 32,
"metadata": {},
"outputs": [
{
},
{
"cell_type": "code",
- "execution_count": 27,
+ "execution_count": 33,
"metadata": {},
"outputs": [
{
},
{
"cell_type": "code",
- "execution_count": 28,
+ "execution_count": 34,
"metadata": {},
"outputs": [
{
"'a: 2, b: 0, c: 10, d: 2, pc: 13'"
]
},
- "execution_count": 28,
+ "execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 29,
+ "execution_count": 35,
"metadata": {},
"outputs": [
{
},
{
"cell_type": "code",
- "execution_count": 30,
+ "execution_count": 36,
"metadata": {},
"outputs": [
{
"'a: 52, b: 0, c: 0, d: 0, pc: 48'"
]
},
- "execution_count": 30,
+ "execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 31,
+ "execution_count": 37,
"metadata": {},
"outputs": [
{
"40"
]
},
- "execution_count": 31,
+ "execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 32,
+ "execution_count": 38,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 33,
+ "execution_count": 39,
"metadata": {},
"outputs": [
{
"52"
]
},
- "execution_count": 33,
+ "execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 34,
+ "execution_count": 40,
"metadata": {},
"outputs": [
{
"(250504, 937)"
]
},
- "execution_count": 34,
+ "execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 36,
+ "execution_count": 41,
"metadata": {
"scrolled": true
},
"[]"
]
},
- "execution_count": 36,
+ "execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 37,
+ "execution_count": 42,
"metadata": {},
"outputs": [
{
- "ename": "KeyboardInterrupt",
- "evalue": "",
- "output_type": "error",
- "traceback": [
- "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
- "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
- "\u001b[0;32m<ipython-input-37-a9f4d977edea>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mshow_machine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mexecute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mprogram\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minitial_state\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m{\u001b[0m\u001b[0;34m'a'\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m937\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
- "\u001b[0;32m<ipython-input-18-d22f089366e4>\u001b[0m in \u001b[0;36mexecute\u001b[0;34m(listing, initial_state, trace)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0mm\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnew_machine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0mprogram_from_listing\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlisting\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0mrun\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mm\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minitial_state\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0minitial_state\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtrace\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mtrace\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 5\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
- "\u001b[0;32m<ipython-input-17-5478d48920ba>\u001b[0m in \u001b[0;36mrun\u001b[0;34m(machine, initial_state, trace)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0minitial_state\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0mmachine\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mupdate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minitial_state\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0;32mwhile\u001b[0m \u001b[0mmachine\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'pc'\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmachine\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'instructions'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 5\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mtrace\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mshow_machine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmachine\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
- "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
- ]
+ "data": {
+ "text/plain": [
+ "'a: 250504, b: 0, c: 0, d: 0, pc: 48'"
+ ]
+ },
+ "execution_count": 42,
+ "metadata": {},
+ "output_type": "execute_result"
}
],
"source": [
},
{
"cell_type": "code",
- "execution_count": null,
- "metadata": {},
+ "execution_count": 43,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# labelled_instructions = [i.strip() for i in program.split('\\n') \n",
},
{
"cell_type": "code",
- "execution_count": 58,
+ "execution_count": 44,
"metadata": {},
"outputs": [
{
" 'pc': 4}"
]
},
- "execution_count": 58,
+ "execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 59,
+ "execution_count": 45,
"metadata": {},
"outputs": [
{
},
{
"cell_type": "code",
- "execution_count": 55,
+ "execution_count": 46,
"metadata": {},
"outputs": [
{
" 'pc': 4}"
]
},
- "execution_count": 55,
+ "execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 61,
+ "execution_count": 47,
"metadata": {},
"outputs": [
{
" 'pc': 14}"
]
},
- "execution_count": 61,
+ "execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 62,
+ "execution_count": 48,
"metadata": {},
"outputs": [
{
projects / ou-summer-of-code-2017.git / blobdiff