SimpleAI_Search.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pip install simpleai"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from simpleai.search import SearchProblem\n",
    "\n",
    "GOAL = 'U WON'\n",
    "\n",
    "class SimpleSearchProblem(SearchProblem):\n",
    "    def actions(self, state):\n",
    "        if len(state) < len(GOAL):\n",
    "            return list(' ABCDEFGHIJKLMNOPQRSTUVWXYZ')\n",
    "        else:\n",
    "            return []\n",
    "\n",
    "    def result(self, state, action):\n",
    "        return state + action\n",
    "\n",
    "    def is_goal(self, state):\n",
    "        return state == GOAL\n",
    "    \n",
    "    def cost(self, state, action, state2):\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_problem = SimpleSearchProblem(initial_state='')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from simpleai.search.traditional import depth_first, \\\n",
    "    breadth_first, uniform_cost, \\\n",
    "        limited_depth_first, iterative_limited_depth_first\n",
    "\n",
    "result = depth_first(my_problem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "GOAL:  U WON\n",
      "Steps:\n",
      " [(None, ''), ('U', 'U'), (' ', 'U '), ('W', 'U W'), ('O', 'U WO'), ('N', 'U WON')]\n"
     ]
    }
   ],
   "source": [
    "print(\"GOAL: \", result.state)\n",
    "print(\"Steps:\\n\", result.path())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from simpleai.search.traditional import astar\n",
    "from simpleai.search import SearchProblem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def list_to_string(input_list):\n",
    "        return '\\n'.join(['-'.join(x) for x in input_list])\n",
    "def string_to_list(input_string):\n",
    "    return [x.split('-') for x in input_string.split('\\n')]\n",
    "def get_location(rows, input_element):\n",
    "    for i, row in enumerate(rows):\n",
    "        for j, item in enumerate(row):\n",
    "            if item == input_element:\n",
    "                return i, j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PuzzleSolver(SearchProblem):\n",
    "    def actions(self, cur_state):\n",
    "        rows = string_to_list(cur_state)\n",
    "        row_empty, col_empty = get_location(rows, 'e')\n",
    "        actions = []\n",
    "        if row_empty > 0:\n",
    "            actions.append(rows[row_empty - 1][col_empty])\n",
    "        if row_empty < 2:\n",
    "            actions.append(rows[row_empty + 1][col_empty])\n",
    "        if col_empty > 0:\n",
    "            actions.append(rows[row_empty][col_empty - 1])\n",
    "        if col_empty < 2:\n",
    "            actions.append(rows[row_empty][col_empty + 1])\n",
    "        return actions\n",
    "    def result(self, state, action):\n",
    "        rows = string_to_list(state)\n",
    "        row_empty, col_empty = get_location(rows, 'e')\n",
    "        row_new, col_new = get_location(rows, action)\n",
    "        rows[row_empty][col_empty], rows[row_new][col_new] = \\\n",
    "        rows[row_new][col_new], rows[row_empty][col_empty]\n",
    "        return list_to_string(rows)\n",
    "    def is_goal(self, state):\n",
    "        return state == GOAL\n",
    "    def heuristic(self, state):\n",
    "        rows = string_to_list(state)\n",
    "        distance = 0\n",
    "\n",
    "        rows_goal = string_to_list(GOAL)\n",
    "            \n",
    "        for number in '12345678e':\n",
    "            row_new, col_new = get_location(rows, number)\n",
    "            row_new_goal, col_new_goal = get_location(rows_goal, number)\n",
    "            distance += abs(row_new - row_new_goal) + abs(col_new - col_new_goal)\n",
    "        return distance\n",
    "    def print(self):\n",
    "        for i, (a, s) in enumerate(result.path()):\n",
    "            print()\n",
    "            if a == None:\n",
    "                print('Initial configuration')\n",
    "            elif i == len(result.path()) - 1:\n",
    "                print('After moving', a, 'into the empty space. Goal achieved!')\n",
    "            else:\n",
    "                print('After moving', a, 'into the empty space')\n",
    "            print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Final result that we want to achieve\n",
    "GOAL = '''\n",
    "1-2-3\n",
    "4-5-6\n",
    "7-8-e'''\n",
    "# Starting point\n",
    "INITIAL = '''\n",
    "1-e-2\n",
    "6-3-4\n",
    "7-5-8'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Initial configuration\n",
      "1-e-2\n",
      "6-3-4\n",
      "7-5-8\n",
      "\n",
      "After moving 2 into the empty space\n",
      "1-2-e\n",
      "6-3-4\n",
      "7-5-8\n",
      "\n",
      "After moving 4 into the empty space\n",
      "1-2-4\n",
      "6-3-e\n",
      "7-5-8\n",
      "\n",
      "After moving 3 into the empty space\n",
      "1-2-4\n",
      "6-e-3\n",
      "7-5-8\n",
      "\n",
      "After moving 6 into the empty space\n",
      "1-2-4\n",
      "e-6-3\n",
      "7-5-8\n",
      "\n",
      "After moving 1 into the empty space\n",
      "e-2-4\n",
      "1-6-3\n",
      "7-5-8\n",
      "\n",
      "After moving 2 into the empty space\n",
      "2-e-4\n",
      "1-6-3\n",
      "7-5-8\n",
      "\n",
      "After moving 4 into the empty space\n",
      "2-4-e\n",
      "1-6-3\n",
      "7-5-8\n",
      "\n",
      "After moving 3 into the empty space\n",
      "2-4-3\n",
      "1-6-e\n",
      "7-5-8\n",
      "\n",
      "After moving 6 into the empty space\n",
      "2-4-3\n",
      "1-e-6\n",
      "7-5-8\n",
      "\n",
      "After moving 4 into the empty space\n",
      "2-e-3\n",
      "1-4-6\n",
      "7-5-8\n",
      "\n",
      "After moving 2 into the empty space\n",
      "e-2-3\n",
      "1-4-6\n",
      "7-5-8\n",
      "\n",
      "After moving 1 into the empty space\n",
      "1-2-3\n",
      "e-4-6\n",
      "7-5-8\n",
      "\n",
      "After moving 4 into the empty space\n",
      "1-2-3\n",
      "4-e-6\n",
      "7-5-8\n",
      "\n",
      "After moving 5 into the empty space\n",
      "1-2-3\n",
      "4-5-6\n",
      "7-e-8\n",
      "\n",
      "After moving 8 into the empty space. Goal achieved!\n",
      "1-2-3\n",
      "4-5-6\n",
      "7-8-e\n"
     ]
    }
   ],
   "source": [
    "problem = PuzzleSolver(INITIAL)\n",
    "result = astar(problem)\n",
    "problem.print()"
   ]
  }
 ],
 "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.10.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}