Ex1: Breadth-First Search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Breadth-First Search in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### You are required to solve the following search problem in Python using a breadth-first approach, by adding in code at the places marked \"insert code here\"\n",
    "\n",
    "* Each state is represented by an integer\n",
    "\n",
    "* For a state $k$, the two successor states are $2k$ and $2k+1$ (in this order)\n",
    "\n",
    "* Starting at initial state 1, the goal is to reach state 1024.\n",
    "\n",
    "This code makes use of the class <code>deque</code> in the <code>collections package</code>.  You may need to look up the appropriate member functions to add and remove frontier elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The goal node of 1024 has been reached.\n",
      "Breadth-first search terminated after 1023 steps\n",
      "\n",
      "Size of frontier at termination is 511\n"
     ]
    }
   ],
   "source": [
    "# [INSERT CODE HERE] Initial state\n",
    "state = 1\n",
    "\n",
    "# [INSERT CODE HERE] Define the goal here\n",
    "goal = 1024\n",
    "\n",
    "# Frontier\n",
    "from collections import deque\n",
    "frontier = deque([state])\n",
    "\n",
    "# Step counter\n",
    "steps = 0\n",
    "\n",
    "# Breadth-first search algorithm (continue while there are nodes in the frontier)\n",
    "while frontier:\n",
    "    # [INSERT CODE HERE] Implement a breadth-first search to reach the goal state from the initial state.\n",
    "    # The search should terminate once the goal is reached.\n",
    "    # Remember to increment the step counter to keep track of how many steps the search takes!\n",
    "    # You will need to modifu the placeholder code below.\n",
    "    \n",
    "    #If the goal state has been reached, break the loop\n",
    "    if state == goal:\n",
    "        print('The goal node of',current_node,'has been reached.')\n",
    "        break\n",
    "        \n",
    "    #Get the current node\n",
    "    state = frontier.popleft()\n",
    "    \n",
    "    #Generate successor nodes of the current node\n",
    "    left_child, right_child = [state*2, state*2 + 1]\n",
    "    \n",
    "    #Iterate through all the successor nodes\n",
    "    for child in [left_child, right_child]:\n",
    "        \n",
    "        #Record successor generation as individual steps\n",
    "        steps += 1\n",
    "        \n",
    "        #BFS also carries out goal test when each child is generated\n",
    "        if child == goal:\n",
    "            state = goal\n",
    "            break\n",
    "        \n",
    "        #If not goal node, add child to frontier\n",
    "        else:\n",
    "            frontier.append(child)\n",
    "\n",
    "\n",
    "# [INSERT CODE HERE] Find the length of the frontier by changing the line below.\n",
    "frontier_size = len(frontier)\n",
    "    \n",
    "\n",
    "print(\"Breadth-first search terminated after %d steps\\n\" % steps)\n",
    "print(\"Size of frontier at termination is %d\" % frontier_size)"
   ]
  }
 ],
 "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.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}