main.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a4f39263-e0bf-4915-94ca-39c5ee03c050",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import math\n",
    "import tracemalloc\n",
    "import pandas as pd\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a131565e-ae49-4192-bdbe-7ff513eb3a69",
   "metadata": {},
   "outputs": [],
   "source": [
    "def toNodeChilds(childs ,parent ):\n",
    "    nodeChilds = []\n",
    "    for i in range(len(childs)):\n",
    "        nodeChilds.append(Node(childs[i][0] , childs[i][1] , parent , parent.depth + 1 , parent.path_cost + 1))\n",
    "    return nodeChilds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "652da67e-ab6d-4e26-9950-24abf8f99f9d",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self , puzzle,prev , parent = None,depth = 0 , path_cost = 0):\n",
    "        self.key = puzzle\n",
    "        self.empty = self.key.index(0)\n",
    "        self.previous_movement = prev\n",
    "        self.parent = parent\n",
    "        self.depth = depth\n",
    "        self.path_cost = path_cost\n",
    "        self.heuristic = 0\n",
    "        self.fn = self.heuristic + self.path_cost\n",
    "    def set_childs(self):\n",
    "        list_temp = []\n",
    "        if self.empty > 2 and self.previous_movement != 'D':\n",
    "            temp = self.key.copy()\n",
    "            temp[self.empty] , temp[self.empty -3] = temp[self.empty - 3] , temp[self.empty]\n",
    "            list_temp.append((temp, 'U'))\n",
    "        if self.empty < 6 and self.previous_movement != 'U':\n",
    "            temp = self.key.copy()\n",
    "            temp[self.empty] , temp[self.empty + 3 ] = temp[self.empty + 3] , temp[self.empty]\n",
    "            list_temp.append((temp , 'D'))\n",
    "        if self.empty % 3 != 2 and self.previous_movement != 'L':\n",
    "            temp = self.key.copy()\n",
    "            temp[self.empty] , temp[self.empty + 1] = temp[self.empty+1] , temp[self.empty]\n",
    "            list_temp.append((temp , 'R'))\n",
    "        if self.empty % 3 != 0 and self.previous_movement != 'R':\n",
    "            temp = self.key.copy()\n",
    "            temp[self.empty] , temp[self.empty - 1] = temp[self.empty -1 ] , temp[self.empty]\n",
    "            list_temp.append((temp , 'L'))\n",
    "        self.childs = toNodeChilds(list_temp , self)\n",
    "    def manhattan_dist(self):\n",
    "        manhat_sum = 0\n",
    "        for i in range(1 , 9):\n",
    "            i_location = self.key.index(i)\n",
    "            index_difference = abs( i - i_location - 1)\n",
    "            manhat_sum += (index_difference // 3) + (index_difference % 3)\n",
    "        self.heuristic = manhat_sum\n",
    "        self.fn = self.heuristic + self.path_cost\n",
    "    def get_childs(self):\n",
    "        return self.childs\n",
    "    def get_prev(self):\n",
    "        return self.previous_movement\n",
    "    def get_puzzle(self):\n",
    "        return self.key\n",
    "    def get_parent(self):\n",
    "        return self.parent\n",
    "    def get_depth(self):\n",
    "        return self.depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e46a98e4-eb1e-4ad3-8cfb-59160a29d615",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self , puzzle):\n",
    "        self.goal = [1,2,3,4,5,6,7,8,0]\n",
    "        self.puzzle = puzzle\n",
    "        self.root = Node(self.puzzle , 'N')        \n",
    "    def DFS(self):\n",
    "        start = time.time()\n",
    "        stack = [self.root]\n",
    "        while stack != []:\n",
    "            popped = stack.pop()\n",
    "            popped.set_childs()\n",
    "            if popped.get_puzzle() == self.goal:\n",
    "                end = time.time()\n",
    "                moves = []\n",
    "                it = popped\n",
    "                while it != None:\n",
    "                    moves.append((it.key , it.previous_movement))\n",
    "                    it = it.get_parent()\n",
    "                for j in range(len(moves) -1 , -1 , -1):\n",
    "                    print(moves[j][0])\n",
    "                print('Action Sequence is : ' , end='')\n",
    "                act_seq = ''\n",
    "                for j in range(len(moves)-2 , -1 , -1):\n",
    "                    print(moves[j][1] , end= '')\n",
    "                    act_seq += moves[j][1]\n",
    "                print()\n",
    "                print(f'The time of running DFS algorithm is : {(end - start) * 1000:6f}ms')\n",
    "                return (act_seq , (end - start)*1000)\n",
    "            if popped.get_depth() < 22:\n",
    "                stack.extend(popped.get_childs())\n",
    "            \n",
    "    def IDS(self):\n",
    "        start = time.time()\n",
    "        for i in range(33):\n",
    "            stack = [self.root]\n",
    "            \n",
    "            while stack != []:\n",
    "                popped = stack.pop()\n",
    "                if popped.get_puzzle() == self.goal:\n",
    "                    end = time.time()\n",
    "                    moves = []\n",
    "                    it = popped\n",
    "                    while it != None:\n",
    "                        moves.append((it.key , it.previous_movement))\n",
    "                        it = it.get_parent()\n",
    "                    for j in range(len(moves) -1 , -1 , -1):\n",
    "                        print(moves[j][0])\n",
    "                    print('Action Sequence is : ' , end='')\n",
    "                    act_seq = ''\n",
    "                    for j in range(len(moves)-2 , -1 , -1):\n",
    "                        print(moves[j][1] , end= '')\n",
    "                        act_seq += moves[j][1]\n",
    "                    print()\n",
    "                    print(f'The time of running IDS algorithm is : {(end - start) * 1000:6f}ms')\n",
    "                    return (act_seq , (end - start)*1000)\n",
    "                if popped.get_depth() < i:\n",
    "                    stack.extend(popped.get_childs())\n",
    "                \n",
    "    def BFS(self):\n",
    "        start = time.time()\n",
    "        queue = [self.root]\n",
    "        while queue != []:\n",
    "            popped = queue.pop(0)\n",
    "            popped.set_childs()\n",
    "            if popped.get_puzzle() == self.goal:\n",
    "                moves =  [] \n",
    "                it = popped\n",
    "                while it != None:\n",
    "                    moves.append((it.key , it.previous_movement))\n",
    "                    it = it.get_parent()\n",
    "                for j in range(len(moves)-1 , -1 , -1):\n",
    "                    print(moves[j][0])\n",
    "                print('Action Sequence is : ' , end='')\n",
    "                act_seq = ''\n",
    "                for j in range(len(moves)-2 , -1 , -1):\n",
    "                    print(moves[j][1] , end= '')\n",
    "                    act_seq += moves[j][1]\n",
    "                print()\n",
    "                end = time.time()\n",
    "                print(f\"The time of running BFS algorithm is : {(end - start) * 1000:6f}ms\")\n",
    "                return (act_seq , (end - start)*1000)\n",
    "            queue.extend(popped.get_childs())\n",
    "    def A_star(self):\n",
    "        start = time.time()\n",
    "        queue = [self.root]\n",
    "        while queue != []:\n",
    "            popped = queue.pop(0)\n",
    "            popped.set_childs()\n",
    "            if popped.get_puzzle() == self.goal:\n",
    "                end = time.time()\n",
    "                moves =  [] \n",
    "                it = popped\n",
    "                while it != None:\n",
    "                    moves.append((it.key , it.previous_movement))\n",
    "                    it = it.get_parent()\n",
    "                for j in range(len(moves)-1 , -1 , -1):\n",
    "                    print(moves[j][0])\n",
    "                print('Action Sequence is : ' , end='')\n",
    "                act_seq = ''\n",
    "                for j in range(len(moves)-2 , -1 , -1):\n",
    "                    print(moves[j][1] , end= '')\n",
    "                    act_seq += moves[j][1]\n",
    "                print()\n",
    "                print(f\"The time of running A* algorithm is : {(end - start) * 1000:6f}ms\")\n",
    "                return [act_seq , (end - start)*1000]\n",
    "            for child in popped.get_childs():\n",
    "                child.manhattan_dist()\n",
    "                i = 0\n",
    "                while i < len(queue) and child.fn > queue[i].fn:\n",
    "                    i += 1\n",
    "                queue.insert(i , child)\n",
    "    def UCS(self):\n",
    "        start = time.time()\n",
    "        queue = [self.root]\n",
    "        while queue != []:\n",
    "            popped = queue.pop(0)\n",
    "            popped.set_childs()\n",
    "            if popped.get_puzzle() == self.goal:\n",
    "                end = time.time()\n",
    "                moves =  [] \n",
    "                it = popped\n",
    "                while it != None:\n",
    "                    moves.append((it.key , it.previous_movement))\n",
    "                    it = it.get_parent()\n",
    "                for j in range(len(moves)-1 , -1 , -1):\n",
    "                    print(moves[j][0])\n",
    "                print('Action Sequence is : ' , end='')\n",
    "                act_seq = ''\n",
    "                for j in range(len(moves)-2 , -1 , -1):\n",
    "                    print(moves[j][1] , end= '')\n",
    "                    act_seq += moves[j][1]\n",
    "                print()\n",
    "                print(f\"The time of running UCS algorithm is : {(end - start) * 1000:6f}ms\")\n",
    "                return \n",
    "            for child in popped.get_childs():\n",
    "                i = 0\n",
    "                while i < len(queue) and child.fn > queue[i].fn:\n",
    "                    i += 1\n",
    "                queue.insert(i , child)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ff7e18b7-8dcb-4c7c-9b01-7127bf25a441",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 4,3,1,0,7,2,8,5,6\n"
     ]
    }
   ],
   "source": [
    "puz = list(map(int , input().split(',')))\n",
    "tree = Tree(puz)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "69cbe413-4836-4e79-98c6-f8b86b541119",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 3, 1, 0, 7, 2, 8, 5, 6]\n",
      "[4, 3, 1, 7, 0, 2, 8, 5, 6]\n",
      "[4, 0, 1, 7, 3, 2, 8, 5, 6]\n",
      "[4, 1, 0, 7, 3, 2, 8, 5, 6]\n",
      "[4, 1, 2, 7, 3, 0, 8, 5, 6]\n",
      "[4, 1, 2, 7, 0, 3, 8, 5, 6]\n",
      "[4, 1, 2, 7, 5, 3, 8, 0, 6]\n",
      "[4, 1, 2, 7, 5, 3, 0, 8, 6]\n",
      "[4, 1, 2, 0, 5, 3, 7, 8, 6]\n",
      "[0, 1, 2, 4, 5, 3, 7, 8, 6]\n",
      "[1, 0, 2, 4, 5, 3, 7, 8, 6]\n",
      "[1, 2, 0, 4, 5, 3, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 0, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "Action Sequence is : RURDLDLUURRDD\n",
      "The time of running A* algorithm is : 0.000000ms\n",
      "memory usage is : 47605\n"
     ]
    }
   ],
   "source": [
    "tracemalloc.start()\n",
    "a_star = tree.A_star()\n",
    "memory = tracemalloc.get_traced_memory()[1]\n",
    "tracemalloc.stop()\n",
    "print(f'memory usage is : {memory}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f3bdab4c-d8ec-48e9-a7d8-c98a18d7f476",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 3, 1, 0, 7, 2, 8, 5, 6]\n",
      "[4, 3, 1, 7, 0, 2, 8, 5, 6]\n",
      "[4, 0, 1, 7, 3, 2, 8, 5, 6]\n",
      "[4, 1, 0, 7, 3, 2, 8, 5, 6]\n",
      "[4, 1, 2, 7, 3, 0, 8, 5, 6]\n",
      "[4, 1, 2, 7, 0, 3, 8, 5, 6]\n",
      "[4, 1, 2, 7, 5, 3, 8, 0, 6]\n",
      "[4, 1, 2, 7, 5, 3, 0, 8, 6]\n",
      "[4, 1, 2, 0, 5, 3, 7, 8, 6]\n",
      "[0, 1, 2, 4, 5, 3, 7, 8, 6]\n",
      "[1, 0, 2, 4, 5, 3, 7, 8, 6]\n",
      "[1, 2, 0, 4, 5, 3, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 0, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "Action Sequence is : RURDLDLUURRDD\n",
      "The time of running BFS algorithm is : 100.110531ms\n",
      "memory usage is : 2681683\n"
     ]
    }
   ],
   "source": [
    "tracemalloc.start()\n",
    "bfs = tree.BFS()\n",
    "memory = tracemalloc.get_traced_memory()[1]\n",
    "tracemalloc.stop()\n",
    "print(f'memory usage is : {memory}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "ead89073-c389-4749-823e-1053cf8d3c07",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 3, 1, 0, 7, 2, 8, 5, 6]\n",
      "[4, 3, 1, 7, 0, 2, 8, 5, 6]\n",
      "[4, 0, 1, 7, 3, 2, 8, 5, 6]\n",
      "[4, 1, 0, 7, 3, 2, 8, 5, 6]\n",
      "[4, 1, 2, 7, 3, 0, 8, 5, 6]\n",
      "[4, 1, 2, 7, 0, 3, 8, 5, 6]\n",
      "[4, 1, 2, 7, 5, 3, 8, 0, 6]\n",
      "[4, 1, 2, 7, 5, 3, 0, 8, 6]\n",
      "[4, 1, 2, 0, 5, 3, 7, 8, 6]\n",
      "[0, 1, 2, 4, 5, 3, 7, 8, 6]\n",
      "[1, 0, 2, 4, 5, 3, 7, 8, 6]\n",
      "[1, 2, 0, 4, 5, 3, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 0, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "Action Sequence is : RURDLDLUURRDD\n",
      "The time of running IDS algorithm is : 23.497105ms\n",
      "memory usage is : 16408\n"
     ]
    }
   ],
   "source": [
    "tracemalloc.start()\n",
    "ids = tree.IDS()\n",
    "memory = tracemalloc.get_traced_memory()[1]\n",
    "tracemalloc.stop()\n",
    "print(f'memory usage is : {memory}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "827c2a66-3768-4497-8005-316a4dab7a5d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 3, 1, 0, 7, 2, 8, 5, 6]\n",
      "[4, 3, 1, 7, 0, 2, 8, 5, 6]\n",
      "[4, 3, 1, 7, 2, 0, 8, 5, 6]\n",
      "[4, 3, 0, 7, 2, 1, 8, 5, 6]\n",
      "[4, 0, 3, 7, 2, 1, 8, 5, 6]\n",
      "[4, 2, 3, 7, 0, 1, 8, 5, 6]\n",
      "[4, 2, 3, 7, 1, 0, 8, 5, 6]\n",
      "[4, 2, 0, 7, 1, 3, 8, 5, 6]\n",
      "[4, 0, 2, 7, 1, 3, 8, 5, 6]\n",
      "[4, 1, 2, 7, 0, 3, 8, 5, 6]\n",
      "[4, 1, 2, 7, 5, 3, 8, 0, 6]\n",
      "[4, 1, 2, 7, 5, 3, 0, 8, 6]\n",
      "[4, 1, 2, 0, 5, 3, 7, 8, 6]\n",
      "[0, 1, 2, 4, 5, 3, 7, 8, 6]\n",
      "[1, 0, 2, 4, 5, 3, 7, 8, 6]\n",
      "[1, 2, 0, 4, 5, 3, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 0, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "Action Sequence is : RRULDRULDDLUURRDD\n",
      "The time of running DFS algorithm is : 1263.971806ms\n",
      "memory usage is : 69213103\n"
     ]
    }
   ],
   "source": [
    "tracemalloc.start()\n",
    "dfs = tree.DFS()\n",
    "memory = tracemalloc.get_traced_memory()[1]\n",
    "tracemalloc.stop()\n",
    "print(f'memory usage is : {memory}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "4428b3c2-b683-4f63-9da1-2f54d16383c5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 3, 1, 0, 7, 2, 8, 5, 6]\n",
      "[4, 3, 1, 7, 0, 2, 8, 5, 6]\n",
      "[4, 0, 1, 7, 3, 2, 8, 5, 6]\n",
      "[4, 1, 0, 7, 3, 2, 8, 5, 6]\n",
      "[4, 1, 2, 7, 3, 0, 8, 5, 6]\n",
      "[4, 1, 2, 7, 0, 3, 8, 5, 6]\n",
      "[4, 1, 2, 7, 5, 3, 8, 0, 6]\n",
      "[4, 1, 2, 7, 5, 3, 0, 8, 6]\n",
      "[4, 1, 2, 0, 5, 3, 7, 8, 6]\n",
      "[0, 1, 2, 4, 5, 3, 7, 8, 6]\n",
      "[1, 0, 2, 4, 5, 3, 7, 8, 6]\n",
      "[1, 2, 0, 4, 5, 3, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 0, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "Action Sequence is : RURDLDLUURRDD\n",
      "The time of running UCS algorithm is : 1943.580866ms\n",
      "memory usage is : 2101957\n"
     ]
    }
   ],
   "source": [
    "tracemalloc.start()\n",
    "ucs = tree.UCS()\n",
    "memory = tracemalloc.get_traced_memory()[1]\n",
    "tracemalloc.stop()\n",
    "print(f'memory usage is : {memory}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "93ce095a-4cad-4f3e-8471-cc2ffaadbd57",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}