X-Git-Url: https://git.njae.me.uk/?p=advent-of-code-15.git;a=blobdiff_plain;f=advent22.ipynb;fp=advent22.ipynb;h=f08ab26105f2b12fac8caf66463dc4fe71c35dfc;hp=0000000000000000000000000000000000000000;hb=2b7dc1356209b2a6c81145be47e20aa1480ad080;hpb=1dbbda35a8b4d52d61bb12cafd5cbc1eb360206f

diff --git a/advent22.ipynb b/advent22.ipynb
new file mode 100644
index 0000000..f08ab26
--- /dev/null
+++ b/advent22.ipynb
@@ -0,0 +1,848 @@
+{
+ "cells": [
+  {
+   "cell_type": "code",
+   "execution_count": 5,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "import copy"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 7,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[{'boss_hp': -4, 'cost': 53, 'name': 'Magic missile'},\n",
+       " {'boss_hp': -2, 'cost': 73, 'name': 'Drain', 'pc_hp': 2},\n",
+       " {'cost': 113,\n",
+       "  'name': 'Shield',\n",
+       "  'ongoing': [{'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7}]},\n",
+       " {'cost': 173,\n",
+       "  'name': 'Poison',\n",
+       "  'ongoing': [{'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3}]},\n",
+       " {'cost': 229,\n",
+       "  'name': 'Recharge',\n",
+       "  'ongoing': [{'mana': 101},\n",
+       "   {'mana': 101},\n",
+       "   {'mana': 101},\n",
+       "   {'mana': 101},\n",
+       "   {'mana': 101}]}]"
+      ]
+     },
+     "execution_count": 7,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "spells = [\n",
+    "    {'name': 'Magic missile', 'cost': 53, 'boss_hp': -4},\n",
+    "    {'name': 'Drain', 'cost': 73, 'boss_hp': -2, 'pc_hp': 2},\n",
+    "    {'name': 'Shield', 'cost': 113, 'ongoing': [{'armour': 7}] * 6},\n",
+    "    {'name': 'Poison', 'cost': 173, 'ongoing': [{'boss_hp': -3}] * 6},\n",
+    "    {'name': 'Recharge', 'cost': 229, 'ongoing': [{'mana': 101}] * 5}]\n",
+    "spells"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 153,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [],
+   "source": [
+    "initial_state = {'pc_hp': 50, 'mana': 500, 'boss_hp': 58, 'boss_damage': 9, 'ongoing': [], \n",
+    "                 'spent': 0, 'cast': []}"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 154,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def cast_spell(spell, state):\n",
+    "    new_state = copy.deepcopy(state)\n",
+    "    new_state['mana'] -= spell['cost']\n",
+    "    new_state['spent'] += spell['cost']\n",
+    "    new_state['cast'] += [spell['name']]\n",
+    "    if 'boss_hp' in spell:\n",
+    "        new_state['boss_hp'] += spell['boss_hp']\n",
+    "    if 'pc_hp' in spell:\n",
+    "        new_state['pc_hp'] += spell['pc_hp']\n",
+    "    if 'ongoing' in spell:\n",
+    "        new_state['ongoing'] += [spell['ongoing']]\n",
+    "    return new_state"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 155,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'boss_damage': 9,\n",
+       " 'boss_hp': 54,\n",
+       " 'cast': ['Magic missile'],\n",
+       " 'mana': 447,\n",
+       " 'ongoing': [],\n",
+       " 'pc_hp': 50,\n",
+       " 'spent': 53}"
+      ]
+     },
+     "execution_count": 155,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "cast_spell(spells[0], initial_state)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 156,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'boss_damage': 9,\n",
+       " 'boss_hp': 58,\n",
+       " 'cast': [],\n",
+       " 'mana': 500,\n",
+       " 'ongoing': [],\n",
+       " 'pc_hp': 50,\n",
+       " 'spent': 0}"
+      ]
+     },
+     "execution_count": 156,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "initial_state"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 157,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'boss_damage': 9,\n",
+       " 'boss_hp': 58,\n",
+       " 'cast': ['Shield', 'Poison'],\n",
+       " 'mana': 214,\n",
+       " 'ongoing': [[{'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7}],\n",
+       "  [{'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3}]],\n",
+       " 'pc_hp': 50,\n",
+       " 'spent': 286}"
+      ]
+     },
+     "execution_count": 157,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "s2 = cast_spell(spells[2], initial_state)\n",
+    "cast_spell(spells[3], s2)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 97,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def valid_spells(spells, state):\n",
+    "    valid_spells = []\n",
+    "    for spell in spells:\n",
+    "        add_this_spell = True\n",
+    "        if spell['cost'] > state['mana']:\n",
+    "            add_this_spell = False\n",
+    "        if 'ongoing' in spell:\n",
+    "            for s in spell['ongoing'][0]:\n",
+    "                for status in state['ongoing']:\n",
+    "                    if s in status[0]:\n",
+    "                        add_this_spell = False\n",
+    "        if add_this_spell:\n",
+    "            valid_spells += [spell]\n",
+    "    return valid_spells"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 98,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[{'boss_hp': -4, 'cost': 53, 'name': 'Magic missile'},\n",
+       " {'boss_hp': -2, 'cost': 73, 'name': 'Drain', 'pc_hp': 2},\n",
+       " {'cost': 113,\n",
+       "  'name': 'Shield',\n",
+       "  'ongoing': [{'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7}]},\n",
+       " {'cost': 173,\n",
+       "  'name': 'Poison',\n",
+       "  'ongoing': [{'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3}]},\n",
+       " {'cost': 229,\n",
+       "  'name': 'Recharge',\n",
+       "  'ongoing': [{'mana': 101},\n",
+       "   {'mana': 101},\n",
+       "   {'mana': 101},\n",
+       "   {'mana': 101},\n",
+       "   {'mana': 101}]}]"
+      ]
+     },
+     "execution_count": 98,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "valid_spells(spells, initial_state)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 158,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'boss_damage': 9,\n",
+       " 'boss_hp': 58,\n",
+       " 'cast': ['Shield', 'Poison'],\n",
+       " 'mana': 214,\n",
+       " 'ongoing': [[{'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7}],\n",
+       "  [{'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3}]],\n",
+       " 'pc_hp': 50,\n",
+       " 'spent': 286}"
+      ]
+     },
+     "execution_count": 158,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "s2 = cast_spell(spells[2], initial_state)\n",
+    "s3 = cast_spell(spells[3], s2)\n",
+    "s3"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 159,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[{'boss_hp': -4, 'cost': 53, 'name': 'Magic missile'},\n",
+       " {'boss_hp': -2, 'cost': 73, 'name': 'Drain', 'pc_hp': 2}]"
+      ]
+     },
+     "execution_count": 159,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "valid_spells(spells, s3)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 48,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def boss_turn(state):\n",
+    "    new_state = apply_ongoing(state)\n",
+    "    if new_state['boss_hp'] > 0:\n",
+    "        new_state['pc_hp'] -= max(new_state['boss_damage'] - new_state['armour'], 1)\n",
+    "    return new_state"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 67,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def apply_ongoing(state):\n",
+    "    new_state = copy.deepcopy(state)\n",
+    "    new_state['armour'] = 0\n",
+    "    new_state['ongoing'] = []\n",
+    "    for status in state['ongoing']:\n",
+    "        for k in status[0]:\n",
+    "            new_state[k] += status[0][k]\n",
+    "        if len(status) > 1:\n",
+    "            new_state['ongoing'] += [status[1:]]\n",
+    "    return new_state"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 160,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'armour': 7,\n",
+       " 'boss_damage': 9,\n",
+       " 'boss_hp': 55,\n",
+       " 'cast': ['Shield', 'Poison'],\n",
+       " 'mana': 214,\n",
+       " 'ongoing': [[{'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7},\n",
+       "   {'armour': 7}],\n",
+       "  [{'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3}]],\n",
+       " 'pc_hp': 48,\n",
+       " 'spent': 286}"
+      ]
+     },
+     "execution_count": 160,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "boss_turn(s3)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 161,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'armour': 0,\n",
+       " 'boss_damage': 8,\n",
+       " 'boss_hp': 10,\n",
+       " 'cast': ['Poison'],\n",
+       " 'mana': 77,\n",
+       " 'ongoing': [[{'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3}]],\n",
+       " 'pc_hp': 2,\n",
+       " 'spent': 173}"
+      ]
+     },
+     "execution_count": 161,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "test_state_1 = {'pc_hp': 10, 'mana': 250, 'boss_hp': 13, 'boss_damage': 8, 'ongoing': [], 'spent': 0, 'cast': []}\n",
+    "s2 = cast_spell([s for s in spells if s['name'] == 'Poison'][0], test_state_1)\n",
+    "s3 = boss_turn(s2)\n",
+    "s3"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 162,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'armour': 0,\n",
+       " 'boss_damage': 8,\n",
+       " 'boss_hp': 0,\n",
+       " 'cast': ['Poison', 'Magic missile'],\n",
+       " 'mana': 24,\n",
+       " 'ongoing': [[{'boss_hp': -3}, {'boss_hp': -3}, {'boss_hp': -3}]],\n",
+       " 'pc_hp': 2,\n",
+       " 'spent': 226}"
+      ]
+     },
+     "execution_count": 162,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "s4 = apply_ongoing(s3)\n",
+    "s5 = cast_spell([s for s in spells if s['name'] == 'Magic missile'][0], s4)\n",
+    "s6 = boss_turn(s5)\n",
+    "s6"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 163,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'armour': 0,\n",
+       " 'boss_damage': 8,\n",
+       " 'boss_hp': 14,\n",
+       " 'cast': ['Recharge'],\n",
+       " 'mana': 122,\n",
+       " 'ongoing': [[{'mana': 101}, {'mana': 101}, {'mana': 101}, {'mana': 101}]],\n",
+       " 'pc_hp': 2,\n",
+       " 'spent': 229}"
+      ]
+     },
+     "execution_count": 163,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "test_state_2 = {'pc_hp': 10, 'mana': 250, 'boss_hp': 14, 'boss_damage': 8, 'ongoing': [], 'spent': 0, 'cast': []}\n",
+    "s2 = cast_spell([s for s in spells if s['name'] == 'Recharge'][0], test_state_2)\n",
+    "s3 = boss_turn(s2)\n",
+    "s3"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 164,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'armour': 7,\n",
+       " 'boss_damage': 8,\n",
+       " 'boss_hp': 14,\n",
+       " 'cast': ['Recharge', 'Shield'],\n",
+       " 'mana': 211,\n",
+       " 'ongoing': [[{'mana': 101}, {'mana': 101}],\n",
+       "  [{'armour': 7}, {'armour': 7}, {'armour': 7}, {'armour': 7}, {'armour': 7}]],\n",
+       " 'pc_hp': 1,\n",
+       " 'spent': 342}"
+      ]
+     },
+     "execution_count": 164,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "s4 = apply_ongoing(s3)\n",
+    "s5 = cast_spell([s for s in spells if s['name'] == 'Shield'][0], s4)\n",
+    "s6 = boss_turn(s5)\n",
+    "s6"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 165,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'armour': 7,\n",
+       " 'boss_damage': 8,\n",
+       " 'boss_hp': 12,\n",
+       " 'cast': ['Recharge', 'Shield', 'Drain'],\n",
+       " 'mana': 340,\n",
+       " 'ongoing': [[{'armour': 7}, {'armour': 7}, {'armour': 7}]],\n",
+       " 'pc_hp': 2,\n",
+       " 'spent': 415}"
+      ]
+     },
+     "execution_count": 165,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "s7 = apply_ongoing(s6)\n",
+    "s8 = cast_spell([s for s in spells if s['name'] == 'Drain'][0], s7)\n",
+    "s9 = boss_turn(s8)\n",
+    "s9"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 166,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'armour': 7,\n",
+       " 'boss_damage': 8,\n",
+       " 'boss_hp': 9,\n",
+       " 'cast': ['Recharge', 'Shield', 'Drain', 'Poison'],\n",
+       " 'mana': 167,\n",
+       " 'ongoing': [[{'armour': 7}],\n",
+       "  [{'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3},\n",
+       "   {'boss_hp': -3}]],\n",
+       " 'pc_hp': 1,\n",
+       " 'spent': 588}"
+      ]
+     },
+     "execution_count": 166,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "s10 = apply_ongoing(s9)\n",
+    "s11 = cast_spell([s for s in spells if s['name'] == 'Poison'][0], s10)\n",
+    "s12 = boss_turn(s11)\n",
+    "s12"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 167,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'armour': 0,\n",
+       " 'boss_damage': 8,\n",
+       " 'boss_hp': -1,\n",
+       " 'cast': ['Recharge', 'Shield', 'Drain', 'Poison', 'Magic missile'],\n",
+       " 'mana': 114,\n",
+       " 'ongoing': [[{'boss_hp': -3}, {'boss_hp': -3}, {'boss_hp': -3}]],\n",
+       " 'pc_hp': 1,\n",
+       " 'spent': 641}"
+      ]
+     },
+     "execution_count": 167,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "s13 = apply_ongoing(s12)\n",
+    "s14 = cast_spell([s for s in spells if s['name'] == 'Magic missile'][0], s13)\n",
+    "s15 = boss_turn(s14)\n",
+    "s15"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 90,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def finished(state):\n",
+    "    return state['boss_hp'] <= 0 or state['pc_hp'] <= 0\n",
+    "\n",
+    "def victory(state):\n",
+    "    return finished(state) and state['pc_hp'] > 0\n",
+    "\n",
+    "def defeat(state):\n",
+    "    return finished(state) and state['pc_hp'] <= 0"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 125,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [],
+   "source": [
+    "def ahistoric(state):\n",
+    "    return {k: state[k] for k in state if k != 'cast'}"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 186,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'armour': 7,\n",
+       " 'boss_damage': 9,\n",
+       " 'boss_hp': 0,\n",
+       " 'cast': ['Poison',\n",
+       "  'Recharge',\n",
+       "  'Drain',\n",
+       "  'Poison',\n",
+       "  'Recharge',\n",
+       "  'Shield',\n",
+       "  'Poison',\n",
+       "  'Magic missile',\n",
+       "  'Magic missile'],\n",
+       " 'mana': 241,\n",
+       " 'ongoing': [[{'boss_hp': -3}, {'boss_hp': -3}]],\n",
+       " 'pc_hp': 1,\n",
+       " 'spent': 1269}"
+      ]
+     },
+     "execution_count": 186,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "agenda = [initial_state]\n",
+    "closed = []\n",
+    "while agenda:\n",
+    "        current_state = agenda[0]\n",
+    "        new_states = []\n",
+    "        if ahistoric(current_state) not in closed:\n",
+    "            closed += [ahistoric(current_state)]\n",
+    "            # print(current_state)\n",
+    "            if victory(current_state):\n",
+    "                # return current_state\n",
+    "                break\n",
+    "            for spell in valid_spells(spells, current_state):\n",
+    "                s2 = cast_spell(spell, current_state)\n",
+    "                if victory(s2):\n",
+    "                    new_states += [s2]\n",
+    "                else:\n",
+    "                    s3 = boss_turn(s2)\n",
+    "                    if victory(s3):\n",
+    "                        new_states += [s3]\n",
+    "                    if not finished(s3):\n",
+    "                        new_states += [apply_ongoing(s3)]\n",
+    "        # print(new_states)\n",
+    "        states_to_add = [s for s in new_states \n",
+    "                         if ahistoric(s) not in closed\n",
+    "                         if len(s['cast']) <= 50]\n",
+    "        agenda = sorted(states_to_add + agenda[1:], key=lambda s: s['spent'])\n",
+    "        # agenda = new_states + agenda[1:]\n",
+    "current_state"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "#Part 2"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 182,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def player_bleed(state):\n",
+    "    new_state = copy.deepcopy(state)\n",
+    "    new_state['pc_hp'] -= 1\n",
+    "    return new_state"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 185,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'armour': 0,\n",
+       " 'boss_damage': 9,\n",
+       " 'boss_hp': -1,\n",
+       " 'cast': ['Poison',\n",
+       "  'Recharge',\n",
+       "  'Shield',\n",
+       "  'Poison',\n",
+       "  'Recharge',\n",
+       "  'Shield',\n",
+       "  'Poison',\n",
+       "  'Magic missile',\n",
+       "  'Magic missile'],\n",
+       " 'mana': 201,\n",
+       " 'ongoing': [[{'boss_hp': -3}]],\n",
+       " 'pc_hp': 12,\n",
+       " 'spent': 1309}"
+      ]
+     },
+     "execution_count": 185,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "agenda = [initial_state]\n",
+    "closed = []\n",
+    "while agenda:\n",
+    "        current_state = agenda[0]\n",
+    "        new_states = []\n",
+    "        if ahistoric(current_state) not in closed:\n",
+    "            closed += [ahistoric(current_state)]\n",
+    "            # print(current_state)\n",
+    "            if victory(current_state):\n",
+    "                # return current_state\n",
+    "                break\n",
+    "            for spell in valid_spells(spells, current_state):\n",
+    "                s2 = cast_spell(spell, current_state)\n",
+    "                if victory(s2):\n",
+    "                    new_states += [s2]\n",
+    "                else:\n",
+    "                    s3 = boss_turn(s2)\n",
+    "                    if victory(s3):\n",
+    "                        new_states += [s3]\n",
+    "                    s4 = player_bleed(s3)\n",
+    "                    if not finished(s4):\n",
+    "                        new_states += [apply_ongoing(s4)]\n",
+    "        # print(new_states)\n",
+    "        states_to_add = [s for s in new_states \n",
+    "                         if ahistoric(s) not in closed\n",
+    "                         if len(s['cast']) <= 50]\n",
+    "        agenda = sorted(states_to_add + agenda[1:], key=lambda s: s['spent'])\n",
+    "        # agenda = new_states + agenda[1:]\n",
+    "current_state"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": []
+  }
+ ],
+ "metadata": {
+  "kernelspec": {
+   "display_name": "Python 3",
+   "language": "python",
+   "name": "python3"
+  },
+  "language_info": {
+   "codemirror_mode": {
+    "name": "ipython",
+    "version": 3
+   },
+   "file_extension": ".py",
+   "mimetype": "text/x-python",
+   "name": "python",
+   "nbconvert_exporter": "python",
+   "pygments_lexer": "ipython3",
+   "version": "3.4.3"
+  }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 0
+}