{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "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": 2,
     "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": 3,
   "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": 4,
   "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": 5,
   "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": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cast_spell(spells[0], initial_state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "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": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "initial_state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "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": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s2 = cast_spell(spells[2], initial_state)\n",
    "cast_spell(spells[3], s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "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 spell['name'] == 'Magic missile' and state['cast'] and state['cast'][-1] == 'Drain':\n",
    "            add_this_spell = False\n",
    "        if add_this_spell:\n",
    "            valid_spells += [spell]\n",
    "    return valid_spells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "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": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "valid_spells(spells, initial_state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "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": 58,
     "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": 59,
   "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": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "valid_spells(spells, s3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'boss_hp': -2, 'cost': 73, 'name': 'Drain', 'pc_hp': 2}]"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s4 = cast_spell(spells[1], s3)\n",
    "valid_spells(spells, s4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "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": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s4 = cast_spell(spells[0], s3)\n",
    "valid_spells(spells, s4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "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": 13,
   "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": 44,
   "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": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "boss_turn(s3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "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": 45,
     "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": 46,
   "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": 46,
     "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": 47,
   "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": 47,
     "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": 48,
   "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": 48,
     "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": 49,
   "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": 49,
     "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": 50,
   "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": 50,
     "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": 51,
   "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": 51,
     "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": 22,
   "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": 23,
   "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": 30,
   "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": 30,
     "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": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1587, 2908)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(agenda), len(closed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'armour': 0,\n",
       " 'boss_damage': 9,\n",
       " 'boss_hp': 0,\n",
       " 'cast': ['Poison',\n",
       "  'Recharge',\n",
       "  'Shield',\n",
       "  'Poison',\n",
       "  'Drain',\n",
       "  'Recharge',\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": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "agenda = [initial_state]\n",
    "closed = []\n",
    "while agenda:\n",
    "        current_state = agenda[0]\n",
    "        new_states = []\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 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": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(165616, 0)"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(agenda), len(closed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "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": 32,
   "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": 32,
     "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": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(872, 2354)"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(agenda), len(closed)"
   ]
  },
  {
   "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
}