sliderA_ finalPrototypee.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "sliderA*.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "qWL7GVJEDfAa",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#libraries to be used\n",
        "import numpy as np\n",
        "import math\n",
        "import copy\n",
        "import heapq"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ta0l3Z_jTsgJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class PriorityQueue:\n",
        "    def __init__(self):\n",
        "        self.elements = []\n",
        "    \n",
        "    def empty(self):\n",
        "        return len(self.elements) == 0\n",
        "    \n",
        "    def put(self, priority, item):\n",
        "        heapq.heappush(self.elements, (priority, item))\n",
        "    \n",
        "    def get(self):\n",
        "        return heapq.heappop(self.elements)\n",
        "    \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SgfuDRs1-vBM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#Grid class with all tiles positions and exact distance from\n",
        "#the start (gVal) and estimate distance to the goal plus gVal (fVal)\n",
        "class gridObj:\n",
        "  def __init__(self,tiles,index,gVal,fVal,parent):\n",
        "    self.tiles = tiles\n",
        "    self.index = index\n",
        "    self.gVal = gVal\n",
        "    self.fVal = fVal\n",
        "    self.parent = parent\n",
        "  \n",
        "  def __lt__(self,other):\n",
        "    valueF = self.gVal + self.fVal\n",
        "    valueO = other.gVal + other.fVal\n",
        "    if(valueF>valueO):\n",
        "      return 0\n",
        "    else:\n",
        "      return 1\n",
        "  \n",
        "  def setgVal(self,gVal):\n",
        "    self.gVal = gVal\n",
        "  \n",
        "  def setParent(self,parent):\n",
        "    self.parent = parent\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y8OZFF9GWa85",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#Creates a grid if it doesn't exist already and add it to the list of grids, else return the existing grid \n",
        "def createGrid(current,gVal,fVal,grids,parent):\n",
        "  if len(grids)>0:\n",
        "    for i in grids:\n",
        "      if ((i.tiles==current).all()):\n",
        "        return i\n",
        "  tempGrid = gridObj(current, len(grids), gVal, fVal, parent)\n",
        "  grids.append(tempGrid)\n",
        "  return tempGrid\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hsk6Yc9kB06L",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#This function takes the value of a grid position and \n",
        "# return an npArray with the proper position in the goal Grid \n",
        "def valToPos(val):\n",
        "    pos = np.zeros((2))\n",
        "    if (val==0):\n",
        "      x = 2\n",
        "      y = 2\n",
        "    else:  \n",
        "      if val <= 3 and val!=0 :\n",
        "        x = 0\n",
        "        y = val -1 \n",
        "      elif val <= 6 :\n",
        "        x = 1\n",
        "        y = val -4\n",
        "      elif val<=8:\n",
        "        x = 2\n",
        "        y = val - 7\n",
        "      \n",
        "    pos[0] = int (x)\n",
        "    pos[1] = int (y)\n",
        "    return pos"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9XlTp-FSbiWa",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def returnEmpty(grid):\n",
        "  empty = np.zeros((2))\n",
        "  for i in range(0,3):\n",
        "    for j in range(0,3):\n",
        "      if (grid[i,j]==0):\n",
        "        empty[0] = i\n",
        "        empty[1] = j\n",
        "        return empty #Esa linea equivale a un break\n",
        "  return empty"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UDSDlx0EZ6vS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#return a list of the neighbors for a grid, creates the necessary grids also\n",
        "def neighbors (grid,gVal,grids,parent):\n",
        "  empty = returnEmpty(grid) #Get the position of the empty spot \n",
        "  x = empty[0]\n",
        "  y = empty[1]\n",
        "  x = int(x)\n",
        "  y = int(y)\n",
        "  neighbors = []\n",
        "  \n",
        "  if (x+1<3):\n",
        "    tempGrid = np.copy(grid) #copy the current grid\n",
        "    tempPos = grid[x+1,y] #Save one of the positions to change\n",
        "    tempGrid[x+1,y] = tempGrid[x,y] #change the value of the position saved before\n",
        "    tempGrid[x,y] = tempPos #Change the value of the other position\n",
        "    neighbors.append(createGrid(tempGrid, gVal+1, heurDist(tempGrid), grids, parent))\n",
        "  if (x-1>=0):\n",
        "    tempGrid = np.copy(grid) #copy the current grid\n",
        "    tempPos = grid[x-1,y] #Save one of the positions to change\n",
        "    tempGrid[x-1,y] = tempGrid[x,y] #change the value of the position saved before\n",
        "    tempGrid[x,y] = tempPos #Change the value of the other position\n",
        "    neighbors.append(createGrid(tempGrid,gVal+1,heurDist(tempGrid), grids, parent))\n",
        "  if (y+1<3):\n",
        "    tempGrid = np.copy(grid) #copy the current grid\n",
        "    tempPos = grid[x,y+1] #Save one of the positions to change\n",
        "    tempGrid[x,y+1] = tempGrid[x,y] #change the value of the position saved before\n",
        "    tempGrid[x,y] = tempPos #Change the value of the other position\n",
        "    neighbors.append(createGrid(tempGrid,gVal+1,heurDist(tempGrid), grids, parent))\n",
        "  if (y-1>=0):\n",
        "    tempGrid = np.copy(grid) #copy the current grid\n",
        "    tempPos = grid[x,y-1] #Save one of the positions to change\n",
        "    tempGrid[x,y-1] = tempGrid[x,y] #change the value of the position saved before\n",
        "    tempGrid[x,y] = tempPos #Change the value of the other position\n",
        "    neighbors.append(createGrid(tempGrid,gVal+1,heurDist(tempGrid), grids, parent))\n",
        "  return neighbors\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "imN--cVWCGTU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#iterates through the grid and accumulate the distance between\n",
        "#every tile in the current grid to the correct tile position in the final grid\n",
        "def heurDist(grid):\n",
        "  dist = 0\n",
        "  if(grid[0,0]!=1):\n",
        "    dist = 5\n",
        "  val = 1\n",
        "  for i in range(0,3):\n",
        "    for j in range(0,3):\n",
        "      pos = valToPos(grid[i,j])\n",
        "      dist = dist + (abs(pos[0]-i) + abs(pos[1]-j))\n",
        "      val = val + 1\n",
        "  #print(dist)\n",
        "  dist = dist + linearConflict(grid) - 1\n",
        "  if(dist<0):\n",
        "    dist = 0\n",
        "  return dist"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ttdNoyMSiBrI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def linearConflict(grid):\n",
        "  acum = 0\n",
        "  for i in grid:\n",
        "    if(level(i[0])==level(i[1]) and i[1]<i[0]):\n",
        "      acum = acum + 1\n",
        "      if(i[1]==0):\n",
        "        acum = acum - 1\n",
        "    if(level(i[0])==level(i[2]) and i[2]<i[0]):\n",
        "      acum = acum + 1  \n",
        "      if(i[2]==0):\n",
        "        acum = acum - 1\n",
        "    if(level(i[1])==level(i[2]) and i[2]<i[1]):\n",
        "      acum = acum + 1\n",
        "      if(i[2]==0):\n",
        "        acum = acum - 1\n",
        "  return acum\n",
        "\n",
        "     \n",
        "\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-fZrT8yLiTIR",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def level(val):\n",
        "  if val == 0 or val > 6:\n",
        "    return 2\n",
        "  elif val>=1 and val <=3:\n",
        "    return 0\n",
        "  else:\n",
        "    return 1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "X6JobvLF36Ym",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#function to find an npArray element on a list \n",
        "def findQueu(element,listF):\n",
        "  tempList = copy.deepcopy(listF)\n",
        "  while not tempList.empty():\n",
        "    obj = tempList.get()\n",
        "    obj = obj[1]\n",
        "    if ((element.tiles==obj.tiles).all()):\n",
        "      return True\n",
        "  return False"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XVRlbNK9VIvA",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def findList(tiles,listC):\n",
        "  for element in listC:\n",
        "    if ((element==tiles).all()):\n",
        "      return True\n",
        "  return False"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4eJWxIOdsFTE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def delList(tiles,listC):\n",
        "  index = 0\n",
        "  for element in listC:\n",
        "    if ((element==tiles).all()):\n",
        "      return index\n",
        "  index = index + 1  \n",
        "  return False"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Elx1PdGMFPx8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def a_star_search(start, goal, grids):\n",
        "  frontier = PriorityQueue() #PriorityQueue with the unexplored grids\n",
        "  close = []\n",
        "  priority = start.gVal + start.fVal\n",
        "  frontier.put(priority, start) #First value of the frontier is the first grid\n",
        "  cameFrom = [] #The index of a position in cameFrom indicates the referenced grid, the value in that index position is the index to the grid which current came from \n",
        "  currentCost = [] #Index in currentCost refers to a grid Index, the value in that index of the list is the distance from the starter grid.\n",
        "  cameFrom.insert(start.index,start.tiles)\n",
        "  currentCost.insert(start.index,0)\n",
        "  steps = 1\n",
        "  pace = 100\n",
        "  while not frontier.empty() :\n",
        "    current = frontier.get() #get the grid with the lowest fVal \n",
        "    current = current[1]\n",
        "    close.append(current.tiles)\n",
        "    priority = current.gVal + current.fVal\n",
        "    # frontier.put(priority, current)\n",
        "    if (current.tiles==goal).all() :\n",
        "      return current\n",
        "    #create the list of neighbors\n",
        "    neighborList = neighbors(current.tiles, current.gVal, grids,current)\n",
        "    #iterate through neighbors to find the best path\n",
        "    for neighbor in neighborList:\n",
        "      #If it is already in the closed set, skip it\n",
        "      if(not findList(neighbor.tiles,close)):\n",
        "        #if neighbor on frontier\n",
        "        if(findQueu(neighbor,frontier)):\n",
        "          \n",
        "          tempgVal = current.gVal + 1\n",
        "          if(tempgVal<neighbor.gVal):\n",
        "            neighbor.setgVal(tempgVal)\n",
        "            neighbor.setParent(current)\n",
        "        else:\n",
        "          priority = neighbor.gVal + neighbor.fVal\n",
        "          frontier.put(priority, neighbor)\n",
        "          \n",
        "    steps = steps + 1\n",
        "  print('Sin solucion')  \n",
        "  return []\n",
        "        \n",
        "      \n",
        "    \n",
        "    "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "reHrwxrjeB6J",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def path(finalGrid):\n",
        "  pathFinal = []\n",
        "  if(finalGrid != []):\n",
        "    if(finalGrid != None):\n",
        "      pathFinal.append(finalGrid)\n",
        "      if(finalGrid.parent != None):\n",
        "        finalGrid = finalGrid.parent \n",
        "  return pathFinal"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6TMU6NzdDTTl",
        "colab_type": "code",
        "outputId": "e1cf7d0b-6d9e-46d2-ebb8-86ce51d647dc",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        }
      },
      "source": [
        "global index \n",
        "index = 0\n",
        "grids = []\n",
        "grid =np.array([[3, 7, 0],[2, 1, 4],[8, 5, 6],])\n",
        "goal =np.array([[1, 2, 3],[4, 5, 6],[7, 8, 0],])\n",
        "createGrid(grid, 0, valF, grids, None)\n",
        "final = a_star_search(grids[0], goal,grids)\n",
        "path = []\n",
        "path.append(final.tiles)\n",
        "while(final.parent != None):\n",
        "  path.append(final.parent.tiles)\n",
        "  final = final.parent\n",
        "path.reverse()\n",
        "print('numero de movimientos fue: ' + str(len(path) - 1))\n",
        "print('')\n",
        "print('camino')\n",
        "print('')\n",
        "for i in path:\n",
        "  print(i)\n",
        "  print('')"
      ],
      "execution_count": 176,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "numero de movimientos fue: 23\n",
            "\n",
            "camino\n",
            "\n",
            "[[3 7 0]\n",
            " [2 1 4]\n",
            " [8 5 6]]\n",
            "\n",
            "[[3 0 7]\n",
            " [2 1 4]\n",
            " [8 5 6]]\n",
            "\n",
            "[[0 3 7]\n",
            " [2 1 4]\n",
            " [8 5 6]]\n",
            "\n",
            "[[2 3 7]\n",
            " [0 1 4]\n",
            " [8 5 6]]\n",
            "\n",
            "[[2 3 7]\n",
            " [1 0 4]\n",
            " [8 5 6]]\n",
            "\n",
            "[[2 3 7]\n",
            " [1 4 0]\n",
            " [8 5 6]]\n",
            "\n",
            "[[2 3 0]\n",
            " [1 4 7]\n",
            " [8 5 6]]\n",
            "\n",
            "[[2 0 3]\n",
            " [1 4 7]\n",
            " [8 5 6]]\n",
            "\n",
            "[[0 2 3]\n",
            " [1 4 7]\n",
            " [8 5 6]]\n",
            "\n",
            "[[1 2 3]\n",
            " [0 4 7]\n",
            " [8 5 6]]\n",
            "\n",
            "[[1 2 3]\n",
            " [4 0 7]\n",
            " [8 5 6]]\n",
            "\n",
            "[[1 2 3]\n",
            " [4 5 7]\n",
            " [8 0 6]]\n",
            "\n",
            "[[1 2 3]\n",
            " [4 5 7]\n",
            " [0 8 6]]\n",
            "\n",
            "[[1 2 3]\n",
            " [0 5 7]\n",
            " [4 8 6]]\n",
            "\n",
            "[[1 2 3]\n",
            " [5 0 7]\n",
            " [4 8 6]]\n",
            "\n",
            "[[1 2 3]\n",
            " [5 7 0]\n",
            " [4 8 6]]\n",
            "\n",
            "[[1 2 3]\n",
            " [5 7 6]\n",
            " [4 8 0]]\n",
            "\n",
            "[[1 2 3]\n",
            " [5 7 6]\n",
            " [4 0 8]]\n",
            "\n",
            "[[1 2 3]\n",
            " [5 0 6]\n",
            " [4 7 8]]\n",
            "\n",
            "[[1 2 3]\n",
            " [0 5 6]\n",
            " [4 7 8]]\n",
            "\n",
            "[[1 2 3]\n",
            " [4 5 6]\n",
            " [0 7 8]]\n",
            "\n",
            "[[1 2 3]\n",
            " [4 5 6]\n",
            " [7 0 8]]\n",
            "\n",
            "[[1 2 3]\n",
            " [4 5 6]\n",
            " [7 8 0]]\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}