IDA_STAR_on_Cube V2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "identical-bumper",
   "metadata": {},
   "source": [
    "## import libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "usual-jefferson",
   "metadata": {},
   "outputs": [],
   "source": [
    "from math_helper import Point, Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "entire-failure",
   "metadata": {},
   "source": [
    "## Create my IDA*\n",
    "### Define heuristic function"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "simplified-butter",
   "metadata": {},
   "source": [
    "###### Sub goal states: we can improve for better generalization "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "skilled-looking",
   "metadata": {},
   "outputs": [],
   "source": [
    "def h(cube):\n",
    "   \n",
    "    \"\"\"\n",
    "    the list of color has 54 elements. \n",
    "    For the easy goal of solving Up face, we only look at the first 9 elements. \n",
    "    \"\"\"\n",
    "    simple_distance = 0\n",
    "#     this is the heuristic \n",
    "\n",
    "    \"\"\"\n",
    "    cube_str looks like:\n",
    "            UUU                       0  1  2\n",
    "            UUU                       3  4  5\n",
    "            UUU                       6  7  8\n",
    "        LLL FFF RRR BBB      9 10 11 12 13 14 15 16 17 18 19 20\n",
    "        LLL FFF RRR BBB     21 22 23 24 25 26 27 28 29 30 31 32\n",
    "        LLL FFF RRR BBB     33 34 35 36 37 38 39 40 41 42 43 44\n",
    "            DDD                      45 46 47\n",
    "            DDD                      48 49 50\n",
    "            DDD                      51 52 53\n",
    "    Note that the back side is mirrored in the horizontal axis during unfolding.\n",
    "    Each 'sticker' must be a single character.\n",
    "    \"\"\"\n",
    "    \"\"\"\n",
    "    first sub goal is the easiest. Let's make the Up Face correct\n",
    "    Now hardcoding U_list, Later we'll make the code more generalized. \n",
    "    \"\"\"\n",
    "    \n",
    "    for i in range(9):\n",
    "            if(cube._color_list()[i] != \"U\"):\n",
    "                simple_distance+=1\n",
    "        \n",
    "    return simple_distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "adjacent-exposure",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    DLU\n",
      "    RRD\n",
      "    FFU\n",
      "BBL DDR BRB LDL\n",
      "RBF RUU LFB DDU\n",
      "FBR BBR FUD FLU\n",
      "    DLU\n",
      "    ULF\n",
      "    LFR\n"
     ]
    }
   ],
   "source": [
    "cube = Cube(\"    DLU\\n\"\n",
    "            \"    RRD\\n\"\n",
    "            \"    FFU\\n\"\n",
    "            \"BBL DDR BRB LDL\\n\"\n",
    "            \"RBF RUU LFB DDU\\n\"\n",
    "            \"FBR BBR FUD FLU\\n\"\n",
    "            \"    DLU\\n\"\n",
    "            \"    ULF\\n\"\n",
    "            \"    LFR\")   \n",
    "print(cube)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "solved-screen",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h(cube)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bound-lover",
   "metadata": {},
   "source": [
    "### successor function to find the next state/node"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "processed-damages",
   "metadata": {},
   "source": [
    "#### create maneuver list\n",
    "###### Maneuver list is flexible and later we can expand this list. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "irish-intervention",
   "metadata": {},
   "outputs": [],
   "source": [
    "maneuver_list = []\n",
    "maneuver_list.append(Cube.L)\n",
    "maneuver_list.append(Cube.Li)\n",
    "maneuver_list.append(Cube.R)\n",
    "maneuver_list.append(Cube.Ri)\n",
    "maneuver_list.append(Cube.U)\n",
    "maneuver_list.append(Cube.Ui)\n",
    "maneuver_list.append(Cube.D)\n",
    "maneuver_list.append(Cube.Di)\n",
    "maneuver_list.append(Cube.F)\n",
    "maneuver_list.append(Cube.Fi)\n",
    "maneuver_list.append(Cube.B)\n",
    "maneuver_list.append(Cube.Bi)\n",
    "maneuver_list.append(Cube.M)\n",
    "maneuver_list.append(Cube.Mi)\n",
    "maneuver_list.append(Cube.E)\n",
    "maneuver_list.append(Cube.Ei)\n",
    "maneuver_list.append(Cube.S)\n",
    "maneuver_list.append(Cube.Si)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "forward-platform",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "list"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(maneuver_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "interracial-uniform",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(maneuver_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "romance-journalist",
   "metadata": {},
   "outputs": [],
   "source": [
    "def successors(node):\n",
    "    \"\"\"\n",
    "    node is a Cube instance. \n",
    "    \"\"\"\n",
    "    cube_ini = Cube(node) \n",
    "    cube_rlt = Cube(node)\n",
    "    ls_successor = []\n",
    "    \n",
    "    for i in range(18):        \n",
    "        maneuver_list[i](cube_ini)\n",
    "        cube_rlt = Cube(cube_ini)\n",
    "        ls_successor.append(cube_rlt)\n",
    "        del cube_ini\n",
    "        cube_ini = Cube(node)\n",
    "        \n",
    "    return sorted(ls_successor, key = lambda x:h(x))\n",
    "\n",
    "\n",
    "# need to revisit the action functions to make the for loop work    \n",
    "#     for action in maneuver_list:\n",
    "#         cube_next = action(cube_ini) \n",
    "#         ls_successor.append(cube_next)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "liberal-stuff",
   "metadata": {},
   "outputs": [],
   "source": [
    "node = Cube(\"    UUU\\n\"\n",
    "            \"    UUU\\n\"\n",
    "            \"    UUU\\n\"\n",
    "            \"LLL FFF RRR BBB \\n\"\n",
    "            \"LLL FFF RRR BBB \\n\"\n",
    "            \"LLL FFF RRR BBB \\n\"\n",
    "            \"    DDD\\n\"\n",
    "            \"    DDD\\n\"\n",
    "            \"    DDD\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "violent-expert",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    UUU\n",
      "    UUU\n",
      "    UUU\n",
      "LLL FFF RRR BBB\n",
      "LLL FFF RRR BBB\n",
      "LLL FFF RRR BBB\n",
      "    DDD\n",
      "    DDD\n",
      "    DDD\n"
     ]
    }
   ],
   "source": [
    "print(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "cubic-testing",
   "metadata": {},
   "outputs": [],
   "source": [
    "ls_test = successors(node) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "smooth-philippines",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "list"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(ls_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "excited-olive",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(ls_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "consistent-termination",
   "metadata": {},
   "source": [
    "### IDA* search function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "comic-tackle",
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(path, g, bound):\n",
    "    node = path[-1]\n",
    "    f = g + h(node)\n",
    "    if(f > bound):\n",
    "        return f\n",
    "    if(h(node)==0):\n",
    "        return -1\n",
    "\n",
    "    Min = 5\n",
    "    for succ in successors(node):\n",
    "        if succ not in path:\n",
    "            path.append(succ)\n",
    "            t = search(path, g+1, bound)\n",
    "            if(t == -1):\n",
    "                return -1\n",
    "            if(t < Min):\n",
    "                Min = t;\n",
    "            path.pop()\n",
    "\n",
    "    return Min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "steady-innocent",
   "metadata": {},
   "outputs": [],
   "source": [
    "path = [cube]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "honest-visibility",
   "metadata": {},
   "outputs": [],
   "source": [
    "node = path[-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "tested-muslim",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = 0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "chinese-repair",
   "metadata": {},
   "outputs": [],
   "source": [
    "bound = 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "leading-elements",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "minute-underwear",
   "metadata": {},
   "outputs": [],
   "source": [
    "f = g + h(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "worthy-platform",
   "metadata": {},
   "outputs": [],
   "source": [
    "test_min =search(path, g, bound) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "ideal-manitoba",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_min"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "thousand-cache",
   "metadata": {},
   "source": [
    "### wrapping up"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "electronic-danger",
   "metadata": {},
   "source": [
    "###### code from online source. Not best. I need to improve it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "north-sending",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ida_star(root):\n",
    "    bound = h(root)\n",
    "    path = [root]\n",
    "\n",
    "    while(True):\n",
    "        t = search(path, 0, bound)\n",
    "        if(t == -1):\n",
    "            return (path, bound)\n",
    "        if(t > 70):\n",
    "            return ([], bound)\n",
    "\n",
    "        bound = t"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "armed-merit",
   "metadata": {},
   "source": [
    "## Test cases\n",
    "### Case 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "radical-script",
   "metadata": {},
   "outputs": [],
   "source": [
    "root = Cube(\"    UUU\\n\"\n",
    "            \"    UUU\\n\"\n",
    "            \"    LLL\\n\"\n",
    "            \"LLD FFF URR BBB\\n\"\n",
    "            \"LLD FFF URR BBB\\n\"\n",
    "            \"LLD FFF URR BBB\\n\"\n",
    "            \"    RRR\\n\"\n",
    "            \"    DDD\\n\"\n",
    "            \"    DDD\") "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "missing-pavilion",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 60 ms, sys: 0 ns, total: 60 ms\n",
      "Wall time: 59.9 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "(path, bound) = ida_star(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "traditional-steering",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step 0\n",
      "    UUU\n",
      "    UUU\n",
      "    LLL\n",
      "LLD FFF URR BBB\n",
      "LLD FFF URR BBB\n",
      "LLD FFF URR BBB\n",
      "    RRR\n",
      "    DDD\n",
      "    DDD\n",
      "step 1\n",
      "    UUU\n",
      "    UUU\n",
      "    UUU\n",
      "LLL FFF RRR BBB\n",
      "LLL FFF RRR BBB\n",
      "LLL FFF RRR BBB\n",
      "    DDD\n",
      "    DDD\n",
      "    DDD\n"
     ]
    }
   ],
   "source": [
    "step = 0\n",
    "for p in path:\n",
    "    print('step', step)\n",
    "    step += 1\n",
    "    print(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "arctic-boutique",
   "metadata": {},
   "source": [
    "### Case 2 very slow... "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "accompanied-arizona",
   "metadata": {},
   "outputs": [],
   "source": [
    "root2= Cube(\"    DBU\\n\"\n",
    "            \"    LBU\\n\"\n",
    "            \"    FLD\\n\"\n",
    "            \"BFR UDR FRR BDL\\n\"\n",
    "            \"DLL BUU BRR BDF\\n\"\n",
    "            \"DLL BFF LRR BRF\\n\"\n",
    "            \"    UUU\\n\"     \n",
    "            \"    UFD\\n\"\n",
    "            \"    LFD\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "amber-issue",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 13min 39s, sys: 68 ms, total: 13min 39s\n",
      "Wall time: 13min 38s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "(path, bound) = ida_star(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "anticipated-method",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step 0\n",
      "    DBU\n",
      "    LBU\n",
      "    FLD\n",
      "BFR UDR FRR BDL\n",
      "DLL BUU BRR BDF\n",
      "DLL BFF LRR BRF\n",
      "    UUU\n",
      "    UFD\n",
      "    LFD\n",
      "step 1\n",
      "    FBU\n",
      "    FBU\n",
      "    LLD\n",
      "DDB DDR FRR BDL\n",
      "LLF LUU BRR BDU\n",
      "LLR FFF LRR BRU\n",
      "    UUU\n",
      "    BFD\n",
      "    BFD\n",
      "step 2\n",
      "    FBU\n",
      "    FBU\n",
      "    FBL\n",
      "DDD RUF URR BDL\n",
      "LLL DUF URR BDU\n",
      "LLL DLF URR BRU\n",
      "    BFR\n",
      "    BFD\n",
      "    BFD\n",
      "step 3\n",
      "    UBU\n",
      "    UBU\n",
      "    LBL\n",
      "LLD FUF URR BDB\n",
      "LLD FUF URR BDB\n",
      "LLD FLF URR BRB\n",
      "    RFR\n",
      "    DFD\n",
      "    DFD\n",
      "step 4\n",
      "    UUU\n",
      "    UUU\n",
      "    LLL\n",
      "LLD FFF URR BBB\n",
      "LLD FFF URR BBB\n",
      "LLD FFF URR BBB\n",
      "    RRR\n",
      "    DDD\n",
      "    DDD\n",
      "step 5\n",
      "    UUU\n",
      "    UUU\n",
      "    UUU\n",
      "LLL FFF RRR BBB\n",
      "LLL FFF RRR BBB\n",
      "LLL FFF RRR BBB\n",
      "    DDD\n",
      "    DDD\n",
      "    DDD\n"
     ]
    }
   ],
   "source": [
    "step = 0\n",
    "for p in path:\n",
    "    print('step', step)\n",
    "    step += 1\n",
    "    print(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "suffering-sailing",
   "metadata": {},
   "outputs": [],
   "source": [
    "root3 = Cube(\"    UUU\\n\"\n",
    "            \"    UUU\\n\"\n",
    "            \"    LLL\\n\"\n",
    "            \"LLD FFF URR BBB\\n\"\n",
    "            \"LLD FFF URR BBB\\n\"\n",
    "            \"LLD FFF URR BBB\\n\"\n",
    "            \"    RRR\\n\"\n",
    "            \"    DDD\\n\"\n",
    "            \"    DDD\")   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "familiar-maldives",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 60 ms, sys: 0 ns, total: 60 ms\n",
      "Wall time: 60.8 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "(path3, bound3) = ida_star(root3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "tutorial-milwaukee",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bound3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "indirect-version",
   "metadata": {},
   "source": [
    "### Case 4\n",
    "perfect_cube --> apply 2 Li actions, and F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "associate-charter",
   "metadata": {},
   "outputs": [],
   "source": [
    "    DUU\n",
    "    DUU\n",
    "    LLL\n",
    "LLU BBB DRR BBF\n",
    "LLD FFF URR BBF\n",
    "LLD FFF URR BBF\n",
    "    RRR\n",
    "    UDD\n",
    "    UDD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "collectible-samuel",
   "metadata": {},
   "outputs": [],
   "source": [
    "root4 = Cube(\"   DUU\\n\"\n",
    "            \"    DUU\\n\"\n",
    "            \"    LLL\\n\"\n",
    "            \"LLU BBB DRR BBF\\n\"\n",
    "            \"LLD FFF URR BBF\\n\"\n",
    "            \"LLD FFF URR BBF\\n\"\n",
    "            \"    RRR\\n\"     \n",
    "            \"    UDD\\n\"\n",
    "            \"    UDD\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "written-linux",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 136 ms, sys: 4 ms, total: 140 ms\n",
      "Wall time: 137 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "(path4, bound4) = ida_star(root4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "arbitrary-final",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bound4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "progressive-following",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(path4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "governmental-teens",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step 0\n",
      "    DUU\n",
      "    DUU\n",
      "    LLL\n",
      "LLU BBB DRR BBF\n",
      "LLD FFF URR BBF\n",
      "LLD FFF URR BBF\n",
      "    RRR\n",
      "    UDD\n",
      "    UDD\n",
      "step 1\n",
      "    DUU\n",
      "    DUU\n",
      "    DUU\n",
      "LLL BFF RRR BBF\n",
      "LLL BFF RRR BBF\n",
      "LLL BFF RRR BBF\n",
      "    UDD\n",
      "    UDD\n",
      "    UDD\n",
      "step 2\n",
      "    FUU\n",
      "    FUU\n",
      "    FUU\n",
      "LLL DFF RRR BBU\n",
      "LLL DFF RRR BBU\n",
      "LLL DFF RRR BBU\n",
      "    BDD\n",
      "    BDD\n",
      "    BDD\n",
      "step 3\n",
      "    UUU\n",
      "    UUU\n",
      "    UUU\n",
      "LLL FFF RRR BBB\n",
      "LLL FFF RRR BBB\n",
      "LLL FFF RRR BBB\n",
      "    DDD\n",
      "    DDD\n",
      "    DDD\n"
     ]
    }
   ],
   "source": [
    "step = 0\n",
    "for p in path4:\n",
    "    print('step', step)\n",
    "    step += 1\n",
    "    print(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "answering-eligibility",
   "metadata": {},
   "source": [
    "### Case 5\n",
    "perfect_cube --> apply 2 Li actions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "planned-green",
   "metadata": {},
   "outputs": [],
   "source": [
    "root5 = Cube(\"   DUU\\n\"\n",
    "            \"    DUU\\n\"\n",
    "            \"    DUU\\n\"\n",
    "            \"LLL BFF RRR BBF\\n\"\n",
    "            \"LLL BFF RRR BBF\\n\"\n",
    "            \"LLL BFF RRR BBF\\n\"\n",
    "            \"    UDD\\n\"     \n",
    "            \"    UDD\\n\"\n",
    "            \"    UDD\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "enhanced-criterion",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 160 ms, sys: 0 ns, total: 160 ms\n",
      "Wall time: 158 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "(path5, bound5) = ida_star(root5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "dental-rebound",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step 0\n",
      "    DUU\n",
      "    DUU\n",
      "    DUU\n",
      "LLL BFF RRR BBF\n",
      "LLL BFF RRR BBF\n",
      "LLL BFF RRR BBF\n",
      "    UDD\n",
      "    UDD\n",
      "    UDD\n",
      "step 1\n",
      "    FUU\n",
      "    FUU\n",
      "    FUU\n",
      "LLL DFF RRR BBU\n",
      "LLL DFF RRR BBU\n",
      "LLL DFF RRR BBU\n",
      "    BDD\n",
      "    BDD\n",
      "    BDD\n",
      "step 2\n",
      "    UUU\n",
      "    UUU\n",
      "    UUU\n",
      "LLL FFF RRR BBB\n",
      "LLL FFF RRR BBB\n",
      "LLL FFF RRR BBB\n",
      "    DDD\n",
      "    DDD\n",
      "    DDD\n"
     ]
    }
   ],
   "source": [
    "step = 0\n",
    "for p in path5:\n",
    "    print('step', step)\n",
    "    step += 1\n",
    "    print(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "fundamental-extra",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bound5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "weighted-gates",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(path5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "monthly-corps",
   "metadata": {},
   "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.6.13"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "295px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}