question1.ipynb

{
 "metadata": {
  "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.3-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "How long is the width of your array?\n",
      "How long is the height of your array?\n",
      "\n",
      "\u001b[91m1\u001b[0m 5 4 1 6 8 3 9 4 9 7 4 1 7 6 3 5 3 7 1 1 3 5 9 5 6 8 6 8 6 5 9 6 1 3 2 4 9 8 2 9 7 5 4 2 5 3 7 6 9 \n",
      "3 2 6 6 1 2 3 4 2 7 1 8 8 3 7 4 2 4 2 7 2 5 8 5 1 4 2 4 1 3 6 8 7 5 6 9 8 7 8 6 3 3 6 3 5 8 3 5 9 2 \n",
      "1 7 6 6 7 5 8 2 5 6 7 5 7 1 8 2 5 3 6 9 6 2 6 7 3 7 8 3 1 6 2 5 2 8 4 9 4 5 8 6 6 1 2 5 7 6 8 3 6 8 \n",
      "3 5 8 8 8 3 3 5 9 8 9 9 3 5 5 8 4 6 4 4 1 7 1 6 1 3 5 8 7 8 4 8 5 4 2 6 8 8 2 5 3 5 7 8 9 8 3 3 2 5 \n",
      "4 8 3 1 2 6 2 1 9 5 4 6 9 2 9 4 6 3 1 7 4 5 9 2 3 7 4 4 8 3 6 9 4 9 1 8 3 3 1 3 7 4 4 5 4 8 2 8 6 5 \n",
      "2 4 5 7 6 6 2 9 5 4 7 3 7 8 5 8 6 7 3 9 9 1 6 9 1 5 3 2 6 6 1 6 5 6 8 6 2 5 1 6 2 3 8 4 7 7 2 9 2 6 \n",
      "1 4 4 1 3 1 7 8 2 4 4 6 3 3 6 1 4 7 5 8 1 7 5 4 8 9 1 6 9 9 3 8 4 9 6 5 9 3 5 1 5 3 7 3 5 5 2 7 5 7 \n",
      "2 8 9 7 4 5 5 2 1 9 3 6 4 4 6 4 9 2 7 6 3 2 9 9 5 4 4 4 2 8 1 8 6 9 8 9 1 7 8 4 9 7 4 4 4 9 3 3 8 3 \n",
      "9 5 1 6 8 8 3 8 1 9 3 5 8 6 2 6 7 8 1 2 8 8 7 9 1 5 5 8 3 7 4 5 6 2 5 2 8 8 8 7 9 3 6 5 3 8 5 5 8 2 \n",
      "5 7 6 5 3 8 2 7 5 4 4 3 7 1 4 8 4 8 9 7 1 5 3 1 1 3 2 5 6 5 5 6 3 9 3 9 3 3 8 9 5 5 1 6 8 7 5 7 2 4 \n",
      "9 5 2 4 4 5 2 9 7 4 1 2 3 5 6 7 3 8 2 1 9 5 9 9 2 6 2 6 1 1 7 3 2 1 3 8 7 4 3 4 6 8 3 2 8 8 4 4 8 1 \n",
      "9 3 2 1 2 3 1 1 3 3 5 9 3 1 4 4 7 6 7 4 1 9 4 8 5 4 2 2 2 5 9 6 5 9 7 8 5 6 6 9 5 7 2 4 8 1 2 1 3 9 \n",
      "9 6 8 2 2 3 7 5 7 8 2 6 7 3 5 6 2 8 2 7 4 3 3 4 8 9 6 4 7 6 2 7 6 4 2 3 5 9 1 8 7 3 7 8 8 5 7 7 7 6 \n",
      "6 3 6 5 3 6 3 8 8 7 4 5 8 7 8 3 2 2 1 6 4 3 4 7 4 1 9 4 6 1 5 2 1 6 5 3 9 7 3 8 1 8 7 9 4 6 6 2 5 2 \n",
      "5 2 6 2 5 8 7 4 7 8 3 7 9 3 3 1 7 8 4 6 6 8 9 9 6 7 6 6 7 9 3 3 1 6 8 2 6 9 9 5 2 4 2 6 1 3 8 6 5 4 \n",
      "1 9 6 2 5 7 7 8 4 6 3 4 1 8 6 5 6 3 8 8 4 7 1 4 7 9 5 3 2 3 7 5 7 7 6 6 3 9 1 1 6 8 7 4 2 3 6 9 4 8 \n",
      "6 4 7 3 2 2 1 7 8 6 8 7 9 9 9 5 5 8 2 3 8 6 2 2 4 2 2 8 3 3 6 1 2 6 8 3 9 1 3 9 2 9 7 5 5 1 4 7 8 5 \n",
      "1 7 4 6 1 2 7 9 7 1 4 8 2 4 5 5 2 6 8 2 7 2 4 2 6 5 3 1 9 6 5 4 2 2 2 5 1 7 5 8 7 9 8 8 8 2 8 3 9 7 \n",
      "2 6 1 1 1 8 6 8 1 7 2 1 6 1 3 8 6 2 5 1 4 6 8 9 6 6 3 6 1 8 5 9 1 9 1 1 3 4 6 4 3 1 4 4 3 2 4 6 8 6 \n",
      "5 2 1 9 2 2 8 9 8 4 7 8 9 1 6 3 5 6 3 6 3 2 8 5 7 7 1 3 7 5 7 8 4 7 6 6 4 9 3 7 1 9 1 2 5 4 6 1 4 3 \n",
      "3 3 2 3 2 4 6 5 8 9 1 2 3 8 3 4 9 8 8 4 1 8 8 2 6 6 2 9 5 1 8 2 3 1 6 9 8 3 1 4 3 3 3 8 7 2 7 3 5 9 \n",
      "2 1 4 4 7 9 9 9 9 9 3 1 8 9 6 4 2 9 2 3 5 5 9 5 2 8 5 5 2 8 3 8 1 7 2 2 1 4 5 7 4 3 8 8 8 5 2 2 8 9 \n",
      "5 9 9 7 8 5 9 6 5 6 5 5 4 8 9 5 3 1 4 3 7 5 7 4 5 3 5 9 3 9 5 6 6 9 1 6 2 9 2 7 7 3 1 6 8 8 3 1 9 9 \n",
      "5 2 6 5 4 9 1 4 5 9 2 3 5 8 5 8 8 6 4 2 1 4 9 1 1 8 1 2 8 3 4 5 5 6 7 5 8 8 7 3 3 1 9 2 8 8 7 2 3 7 \n",
      "9 3 3 8 9 3 2 9 8 4 2 4 5 6 2 4 4 4 9 9 5 8 1 5 8 6 8 8 2 3 6 5 5 2 9 1 5 1 3 4 4 1 4 4 5 3 3 8 5 7 \n",
      "3 3 2 1 6 2 3 1 1 7 5 2 5 9 5 2 9 1 7 3 2 1 9 5 9 6 1 2 1 5 6 6 3 8 1 6 4 1 9 2 3 2 2 8 7 3 9 2 6 7 \n",
      "2 8 4 4 7 3 5 8 5 8 6 3 7 1 2 9 3 9 3 4 4 6 5 1 6 8 6 8 8 9 9 7 9 3 3 6 3 2 5 6 7 3 3 4 1 4 9 8 3 9 \n",
      "3 5 4 6 5 9 9 7 2 1 8 7 4 3 4 1 9 3 9 6 3 3 7 1 3 9 4 6 6 8 3 9 3 4 4 6 7 8 3 1 8 3 2 4 8 2 8 9 8 5 \n",
      "2 9 4 2 4 4 4 8 8 7 1 7 5 4 3 5 2 5 1 2 1 7 8 9 7 1 6 3 5 8 2 4 5 2 8 2 9 9 3 2 5 1 5 3 4 4 5 3 9 7 \n",
      "3 3 9 7 1 7 2 8 8 8 2 2 4 3 6 2 4 2 8 3 2 5 2 7 5 7 3 3 9 6 6 5 3 1 4 9 6 7 2 7 3 4 5 4 9 8 6 4 5 9 \n",
      "8 4 4 2 6 2 9 4 3 5 2 5 4 9 4 2 5 6 7 1 5 5 2 8 4 9 3 4 3 3 9 2 2 6 3 6 7 1 4 7 6 5 5 2 9 4 4 8 6 3 \n",
      "8 5 1 5 3 8 5 4 8 9 6 5 2 9 5 1 5 4 5 5 1 3 4 9 9 2 6 7 8 8 5 7 7 1 9 4 5 5 5 3 9 5 7 6 2 3 7 8 8 7 \n",
      "1 6 2 2 7 6 4 3 3 9 4 5 2 4 4 9 5 5 8 4 5 4 8 8 3 4 5 2 5 3 8 6 1 9 2 8 7 1 7 9 6 1 9 1 7 7 8 9 6 7 \n",
      "7 2 5 6 9 2 4 1 6 2 9 8 8 6 6 1 3 4 5 4 5 9 1 5 7 6 7 9 2 5 5 7 7 3 2 1 8 5 6 1 9 8 1 5 4 5 6 8 7 3 \n",
      "2 4 9 4 9 1 9 8 1 7 5 5 2 8 4 8 4 4 2 2 6 8 2 2 5 2 1 6 6 9 1 2 9 9 4 7 5 5 2 3 8 4 6 8 2 5 6 8 6 9 \n",
      "1 9 2 4 2 1 8 8 7 7 2 8 2 9 8 7 6 6 9 7 8 4 6 4 9 3 8 1 1 2 3 1 5 9 4 1 6 8 2 9 6 8 3 1 7 7 5 8 3 8 \n",
      "8 6 8 6 2 8 6 2 2 7 4 6 6 6 3 3 5 1 9 5 4 3 1 1 2 6 7 5 3 1 6 4 3 2 3 5 8 8 5 3 3 6 5 9 3 3 7 7 6 8 \n",
      "5 9 2 5 7 2 1 8 8 6 1 5 1 9 5 3 7 7 5 4 1 9 5 8 4 3 5 1 1 6 9 8 4 4 5 4 9 8 5 5 7 7 9 2 8 5 4 3 1 5 \n",
      "8 1 9 1 1 2 1 7 9 2 4 2 3 9 3 8 4 8 3 4 1 1 4 4 1 1 3 5 5 5 6 5 1 3 3 3 9 7 7 9 9 2 1 6 2 2 7 9 5 1 \n",
      "3 8 8 6 2 8 6 1 1 6 7 2 8 1 6 2 8 2 4 2 2 2 7 3 3 7 9 7 2 9 9 4 6 4 7 5 9 7 2 9 6 9 5 3 7 6 8 9 1 4 \n",
      "3 2 5 9 8 4 4 2 6 1 9 9 3 4 9 7 3 4 7 7 7 7 2 8 7 9 4 8 4 8 3 3 9 6 8 2 8 6 3 8 1 4 3 8 6 2 5 4 1 3 \n",
      "3 9 2 9 7 7 8 9 9 4 9 9 5 2 3 2 7 3 2 5 2 5 9 9 2 7 5 7 2 2 1 8 6 6 4 4 9 5 6 6 2 6 4 6 1 6 7 1 6 3 \n",
      "5 2 4 7 1 2 9 7 3 6 3 1 4 5 1 6 1 5 7 4 9 8 4 4 3 3 7 6 1 9 2 1 9 8 6 9 7 8 8 1 9 3 3 6 5 1 2 9 9 2 \n",
      "6 5 7 1 2 9 6 2 4 2 9 7 3 2 5 6 1 5 2 9 2 1 3 3 9 8 4 5 7 2 1 4 8 9 5 9 7 9 3 6 6 1 1 1 9 1 8 1 1 5 \n",
      "2 7 5 9 5 6 9 8 4 1 5 3 9 4 8 1 1 2 7 7 1 4 1 5 2 1 8 2 4 6 8 8 2 8 7 9 9 6 2 9 7 6 9 3 5 6 1 9 8 9 \n",
      "1 9 8 5 3 5 8 5 1 4 6 4 3 8 7 8 4 6 3 7 5 5 2 6 2 9 3 5 3 5 3 1 1 3 2 2 7 4 8 1 2 3 7 8 1 9 8 2 7 1 \n",
      "9 4 5 5 4 3 3 9 6 9 3 8 9 6 3 8 8 7 2 3 8 9 7 1 5 5 6 9 9 1 7 7 2 8 2 6 5 4 4 9 1 7 3 7 5 9 2 4 5 3 \n",
      "6 1 9 4 7 1 5 4 8 7 6 9 8 3 7 4 6 9 7 3 2 5 8 4 2 6 7 3 2 1 1 9 1 1 4 4 3 8 3 5 6 9 5 1 4 5 8 6 5 6 \n",
      "5 9 6 9 8 9 7 6 2 3 3 2 5 6 2 3 4 3 2 6 5 2 7 9 4 2 1 5 1 5 3 9 9 4 6 7 5 3 7 8 9 1 8 6 3 1 6 1 8 8 \n",
      "3 3 5 4 9 6 5 3 2 3 2 4 1 1 4 6 2 4 2 6 6 2 8 1 2 1 8 1 2 6 2 3 4 6 4 6 4 8 9 6 3 7 6 3 4 1 3 5 8 3 "
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from numpy.random import default_rng\n",
    "\n",
    "#This class is used for colors in the command prompt\n",
    "\n",
    "class bcolors:\n",
    "    HEADER = '\\033[95m'\n",
    "    OKBLUE = '\\033[94m'\n",
    "    OKCYAN = '\\033[36m'\n",
    "    OKGREEN = '\\033[92m'\n",
    "    WARNING = '\\033[93m'\n",
    "    FAIL = '\\033[91m'\n",
    "    ENDC = '\\033[0m'\n",
    "    BOLD = '\\033[1m'\n",
    "    UNDERLINE = '\\033[4m'\n",
    "\n",
    "arraySizeX = 0\n",
    "arraySizeY = 0\n",
    "\n",
    "#Asking user the size of maze they want (Along then down)\n",
    "\n",
    "print(\"How long is the width of your array?\")\n",
    "arraySizeX = int(input())\n",
    "\n",
    "\n",
    "print(\"How long is the height of your array?\")\n",
    "arraySizeY = int(input())\n",
    "\n",
    "#Creating a array of random numbers.\n",
    "\n",
    "randomArray = np.random.randint(1,10,size=(arraySizeY,arraySizeX))\n",
    "currentElement = 0\n",
    "\n",
    "#Defining a function which prints out the array with a chosen element to be highlighted\n",
    "\n",
    "def printArray(arrayx,arrayy,array,currentElement):\n",
    "    for x1 in range(arrayx):\n",
    "        print(\"\")\n",
    "        for y1 in range(arrayy):\n",
    "            if(currentElement == y1+(x1*arraySizeX)):\n",
    "                print(\"\\033[91m\" + str(array[x1][y1])  + \"\\033[0m\" , end = ' ')\n",
    "            else:\n",
    "                print(array[x1][y1], end = ' ')\n",
    "\n",
    "#Printing array\n",
    "\n",
    "printArray(arraySizeY,arraySizeX,randomArray,currentElement)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "source": [
    "# Nearest neighbour (only in the direction of right and down)"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "def neighbor():\n",
    "\n",
    "    #Creating variables for the nearest neighbor.\n",
    "    tic = timeit.default_timer()\n",
    "    path = []\n",
    "    currentNode = 0\n",
    "    length = 0\n",
    "\n",
    "    #While loop stops when the function has reached the destination (the bottom right node).\n",
    "\n",
    "    while (currentNode != (arraySizeX*arraySizeY - 1)):\n",
    "        #Calculating the absolute difference between the node we are current on and the adjacent bottom and right node.\n",
    "        #The position of the current node can be represent as a number,\n",
    "        #Where the number represents the position of the node as if the array was single vector.\n",
    "        #The value can be converted to the position in the 2d array by using div and mod respectively.\n",
    "        #We will be using this throughout all 3 solutions.\n",
    "\n",
    "\n",
    "        #The adjacent bottom node is the size of the \"x axis\" away from the current node if represented as a single vector.\n",
    "        #Therefore we can represent the node below as currentNode+arraySizeX\n",
    "        #And the node to the right is currentNode+1\n",
    "\n",
    "        #s and d represent the direction (wasd)\n",
    "\n",
    "        s = abs((randomArray[currentNode//arraySizeX][currentNode % arraySizeX]) - (randomArray[(currentNode+arraySizeX)//arraySizeX][(currentNode+arraySizeX) % arraySizeX]))\n",
    "        d = abs((randomArray[currentNode//arraySizeX][currentNode % arraySizeX]) - (randomArray[(currentNode + 1)//arraySizeX][(currentNode + 1) % arraySizeX]))\n",
    "\n",
    "        #If statement is used to see if the node is on the 'edge' of the array.\n",
    "\n",
    "        if (currentNode%arraySizeX < (arraySizeX - 1) and currentNode//arraySizeX < (arraySizeY - 1)):\n",
    "            if (s < d):\n",
    "                currentNode += arraySizeX\n",
    "                length += s\n",
    "            else:\n",
    "                currentNode += 1\n",
    "                length += d\n",
    "\n",
    "        #A problem with this solution is that it priorities going right than down if the two nodes are the same number.\n",
    "        #This could potentially affect the outcome of the final length.\n",
    "\n",
    "        #These next two else if statements are used if the current node are on the 'edge' of the array.\n",
    "\n",
    "        elif(currentNode%arraySizeX < (arraySizeX - 1)):\n",
    "            currentNode += 1\n",
    "            length += d\n",
    "\n",
    "        else:\n",
    "            currentNode += arraySizeX\n",
    "            length += s\n",
    "\n",
    "        #Record the nodes we have passed through.\n",
    "\n",
    "        path.append(currentNode)\n",
    "    \n",
    "\n",
    "    path.append(currentNode)\n",
    "    print(path)\n",
    "\n",
    "\n",
    "    #This is used to print out the solution of the problem and is not part of the algorithm.\n",
    "    #Mainly used to show a clearer solution by adding colour.\n",
    "\n",
    "    for y1 in range(arraySizeY):\n",
    "            print(\"\")\n",
    "            for x1 in range(arraySizeX):\n",
    "                check = 0\n",
    "                for scan in range(len(path)-1):\n",
    "                    if(path[scan] == x1+(y1*arraySizeX)):\n",
    "                        print(\"\\033[91m\" + str(randomArray[y1][x1])  + \"\\033[0m\" , end = ' ')\n",
    "                        check = 1\n",
    "                if(check == 0):\n",
    "                    print(str(randomArray[y1][x1]) , end = ' ')\n",
    "    \n",
    "    # Print out the final length of the solution\n",
    "    print(\"\\nThe length: \", length)\n",
    "    toc = timeit.default_timer()\n",
    "    print(\"\\nThe time to compute: \", toc - tic)\n",
    "    "
   ]
  },
  {
   "source": [
    "# Dijkstra"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "#Dijkstra's algorithm\n",
    "def dijkstra():\n",
    "    tic = timeit.default_timer()\n",
    "    currentNode = 0\n",
    "\n",
    "    #Creating a mapping system for each node in the matrix.\n",
    "    #First value represents the shortest length currently to that node from the start.\n",
    "    #Second value tells us if we have found the shorest length where 1 represents true.\n",
    "\n",
    "    map = np.zeros((arraySizeX*arraySizeY,2,1))\n",
    "\n",
    "    #The starting node is already at the shortest length (0) so mark it 1 (true).\n",
    "\n",
    "    map[0][1] = 1\n",
    "\n",
    "    #Before we start the algorithm, we are making the current shortest length in the map equal to a really high number which will be eventually overwritten.\n",
    "\n",
    "    for change in range(1,arraySizeX*arraySizeY):\n",
    "        map[change][0] = 999\n",
    "\n",
    "    #This function checks if we have found the shortest route for all the nodes in the matrix.\n",
    "    #returns false if no.\n",
    "\n",
    "    def checkState(map):\n",
    "        for x1 in range(0,arraySizeX*arraySizeY):\n",
    "                if (map[x1][1] == 0):\n",
    "                    return False    \n",
    "        return True\n",
    "\n",
    "    #After finding the shortest route for one node, we need to find the next node to work on.\n",
    "\n",
    "    def findNextNode(map):\n",
    "        min = 10000000000\n",
    "        findingNode = 0\n",
    "        currentNode = 0\n",
    "        #For loop to check every node.\n",
    "\n",
    "        for x in range(arraySizeX*arraySizeY):\n",
    "            \n",
    "            #If statements to find the next node that has the current shortest route marked and with no true marked as well.\n",
    "            #The try and catch statements are used if the node we are looking for is out of bounds, so we ignore it.\n",
    "\n",
    "            if (map[x][1] == 1):\n",
    "\n",
    "                try:\n",
    "                    if (map[x+1][1] == 0 and map[x+1][0] <= min):\n",
    "                        min = map[x+1][0]\n",
    "                        findingNode = x+1\n",
    "                except:\n",
    "                    pass\n",
    "\n",
    "                try:\n",
    "                    if (map[x-1][1] == 0 and map[x-1][0] <= min):\n",
    "                        min = map[x-1][0]\n",
    "                        findingNode = x-1\n",
    "                except:\n",
    "                    pass\n",
    "\n",
    "                try:\n",
    "                    if (map[x + arraySizeX][1] == 0 and map[x+ arraySizeX][0] <= min):\n",
    "                        min = map[x + arraySizeX][0]\n",
    "                        findingNode = x + arraySizeX\n",
    "                except:\n",
    "                    pass\n",
    "\n",
    "                try:\n",
    "                    if (map[x - arraySizeX][1] == 0 and map[x - arraySizeX][0] <= min):\n",
    "                        min = map[x - arraySizeX][0]\n",
    "                        findingNode = x - arraySizeX\n",
    "                except:\n",
    "                    pass\n",
    "        \n",
    "        #return the node we have found.\n",
    "        return findingNode\n",
    "\n",
    "    #This function is used to calculate the difference between the current node and the adjacent nodes.\n",
    "    #Directions are represented by \"wasd\" which are top, left, down, right respectively.\n",
    "    #Using something similar to the nearest neighbor algorithm, we are converting a value that represents a value in a vector to a value in an array.\n",
    "    #Using div and mod.\n",
    "    #Overall used to reduce repeated code as we use these many times.\n",
    "\n",
    "    def calculateD(direction,currentNode):\n",
    "\n",
    "        if(direction == \"w\"):\n",
    "            return abs((randomArray[currentNode//arraySizeX][currentNode % arraySizeX]) - (randomArray[(currentNode-arraySizeX)//arraySizeX][(currentNode-arraySizeX) % arraySizeX]))\n",
    "        elif(direction == \"s\"):\n",
    "            return abs((randomArray[currentNode//arraySizeX][currentNode % arraySizeX]) - (randomArray[(currentNode+arraySizeX)//arraySizeX][(currentNode+arraySizeX) % arraySizeX]))\n",
    "        elif(direction == \"a\"):\n",
    "            return abs((randomArray[currentNode//arraySizeX][currentNode % arraySizeX]) - (randomArray[(currentNode - 1)//arraySizeX][(currentNode - 1) % arraySizeX]))\n",
    "        elif(direction == \"d\"):\n",
    "            return abs((randomArray[currentNode//arraySizeX][currentNode % arraySizeX]) - (randomArray[(currentNode + 1)//arraySizeX][(currentNode + 1) % arraySizeX]))\n",
    "\n",
    "    #While loop to check if we have found the shortest route for all the nodes in the matrix.\n",
    "\n",
    "    while (checkState(map) != True):\n",
    "\n",
    "        #Current node is marked 1 as we have found the shortest path to it.\n",
    "\n",
    "        map[currentNode][1] = 1\n",
    "\n",
    "        #Updating any adjacent nodes if we have found a shorter route to it than the current one.\n",
    "\n",
    "        if (currentNode >=arraySizeX):\n",
    "            if (map[currentNode - arraySizeX][1] != 1 and (map[currentNode][0] + calculateD(\"w\",currentNode) < map[currentNode - arraySizeX][0])):\n",
    "                map[currentNode - arraySizeX][0] = map[currentNode][0] + calculateD(\"w\",currentNode)\n",
    "        if (currentNode//arraySizeX < (arraySizeY - 1)):\n",
    "            if (map[currentNode + arraySizeX][1] != 1 and (map[currentNode][0] + calculateD(\"s\",currentNode) < map[currentNode + arraySizeX][0])):\n",
    "                map[currentNode + arraySizeX][0] = map[currentNode][0] + calculateD(\"s\",currentNode)\n",
    "\n",
    "        if (currentNode%arraySizeX > 0):\n",
    "            if (map[currentNode - 1][1] != 1 and (map[currentNode][0] + calculateD(\"a\",currentNode) < map[currentNode - 1][0])):\n",
    "                map[currentNode - 1][0] = map[currentNode][0] + calculateD(\"a\",currentNode)\n",
    "        \n",
    "        if (currentNode%arraySizeX < (arraySizeX - 1)):\n",
    "            if (map[currentNode + 1][1] != 1 and (map[currentNode][0] + calculateD(\"d\",currentNode) < map[currentNode + 1][0])):\n",
    "                map[currentNode + 1][0] = map[currentNode][0] + calculateD(\"d\",currentNode)\n",
    "\n",
    "        #Find the next shortest node marked that hasn't been marked.\n",
    "\n",
    "        currentNode = findNextNode(map)\n",
    "\n",
    "    #Everything below is used to find the path to take when going from the start to finish.\n",
    "\n",
    "    #Sometimes when finding the path, we go the wrong way because two adjacent values could be the same so we need to go backwards.\n",
    "    #Therefore we need to pop values and record that we have visited that value.\n",
    "    #The recording makes sure we never go there again.\n",
    "\n",
    "    def checkPop(number, poparray):\n",
    "        for x in poparray:\n",
    "            if(x == number):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    #This functions find the path from the end to the beginning of the matrix as dijksras works backwards after finding the shortest distance from start to finish.  \n",
    "\n",
    "    def printSolution(arrayx,arrayy,map):\n",
    "\n",
    "        #Here for fun we print out the shortest distance possible from each node to the beginning\n",
    "        #This isn't part of the algorithm.\n",
    "\n",
    "        print(\"Shortest distance from beginning to each node.\")\n",
    "\n",
    "        for x1 in range(0,arrayy):\n",
    "            print(\"\")\n",
    "            for y1 in range(0,arrayx):\n",
    "                print(str(map[y1+(x1*arrayx)][0]) , end = ' ')\n",
    "\n",
    "        #Here we mark the currentNode we are on as 'traversal' as we are going backwards to the beginning.\n",
    "        #nodesThatWeHave passed records the nodes that we have passed.\n",
    "\n",
    "        traversal = arrayx*arrayy - 1\n",
    "        nodesThatWePassed = [arrayx*arrayy - 1]\n",
    "        popList = []\n",
    "        lastDirection1 = \"\"\n",
    "\n",
    "        #While that is stopped when we have reached the beginning of the matrix.\n",
    "\n",
    "        while (traversal != 0):\n",
    "            try:\n",
    "\n",
    "                #Here we are using a lot of conditions to make sure we reach the end with the most optimal route.\n",
    "\n",
    "                #First of all, we are making sure that the different between the adjacent nodes are the same as the difference between the adjacent nodes in the 'map'\n",
    "                #This assures us that we are going the right way.\n",
    "\n",
    "                #Secondly, we making sure the condition above is true when the current node we are on is bigger than the adjacent node on the 'map'.\n",
    "\n",
    "                #Thirdly, we need to make sure that we are not going of the edge of the matrix.\n",
    "\n",
    "                #Then we check if we have went to a node that we have already visited.\n",
    "                #The visited node happens because the if statements below priorities going left,up,down then right.\n",
    "                #There are cases when the adjacent nodes are the same values, so we need to go backwards just in case we are going the wrong way.\n",
    "\n",
    "                #Lastly, we cant go back to a node that we just departed from.\n",
    "\n",
    "                #With all these conditions, we are able to find the most optimal route from the beginning to end.\n",
    "\n",
    "                if (abs(map[traversal][0] - map[traversal - 1][0]) == calculateD(\"a\",traversal) and map[traversal][0] >= map[traversal - 1][0] \\\n",
    "                    and traversal %arrayx > 0 and checkPop(traversal-1,popList) == False and lastDirection1 != \"d\"):\n",
    "                    \n",
    "                    #below every if statement we are adding the node to the list and updating the current node.\n",
    "\n",
    "                    traversal = traversal - 1\n",
    "                    nodesThatWePassed.append(traversal)\n",
    "                    lastDirection1 = \"a\"\n",
    "\n",
    "                elif (abs(map[traversal][0] - map[traversal - arrayx][0]) == calculateD(\"w\",traversal) and map[traversal][0] >= map[traversal - arrayx][0] \\\n",
    "                    and traversal >=arrayx and checkPop(traversal- arrayx,popList) == False and lastDirection1 != \"s\"):\n",
    "\n",
    "                    traversal -= arrayx\n",
    "                    nodesThatWePassed.append(traversal)\n",
    "                    lastDirection1 = \"w\"\n",
    "\n",
    "                elif (abs(map[traversal][0] - map[traversal + 1][0]) == calculateD(\"d\",traversal) and map[traversal][0] >= map[traversal + 1][0] \\\n",
    "                    and (traversal % arrayx) < arrayx - 1 and checkPop(traversal + 1,popList) == False and lastDirection1 != \"a\"):\n",
    "\n",
    "                    traversal = traversal + 1\n",
    "                    nodesThatWePassed.append(traversal)\n",
    "                    lastDirection1 = \"d\"\n",
    "\n",
    "                elif (abs(map[traversal][0] - map[traversal + arrayx][0]) == calculateD(\"s\",traversal) and map[traversal][0] >= map[traversal + arrayx][0] \\\n",
    "                    and (traversal // arrayx) < arrayy -1 and checkPop(traversal + arrayx,popList) == False and lastDirection1 != \"w\"):\n",
    "\n",
    "                    traversal = traversal + arrayx\n",
    "                    nodesThatWePassed.append(traversal)\n",
    "                    lastDirection1 = \"s\"\n",
    "\n",
    "                else:\n",
    "                    \n",
    "                    #This else statement is used if the first condition is not met.\n",
    "                    #We go back in time to try again on a different node.\n",
    "\n",
    "                    popList.append(nodesThatWePassed.pop(len(nodesThatWePassed) - 1))             \n",
    "                    traversal = nodesThatWePassed[len(nodesThatWePassed) - 1]\n",
    "            except:\n",
    "                    break\n",
    "\n",
    "\n",
    "        print(\"\\n\")\n",
    "\n",
    "        #The list we have created was from end to beginning so we reverse the list to get beginning to end.\n",
    "\n",
    "        print(list(reversed(nodesThatWePassed)))\n",
    "\n",
    "        #This is not part of the algorithm, just to print out the solution with colours.\n",
    "\n",
    "        for y1 in range(arrayy):\n",
    "            print(\"\")\n",
    "            for x1 in range(arrayx):\n",
    "                check = 0\n",
    "                for scan in range(len(nodesThatWePassed)-1):\n",
    "                    if(nodesThatWePassed[scan] == x1+(y1*arrayx)):\n",
    "                        print(\"\\033[91m\" + str(randomArray[y1][x1])  + \"\\033[0m\" , end = ' ')\n",
    "                        check = 1\n",
    "                if(check == 0):\n",
    "                    print(str(randomArray[y1][x1]) , end = ' ')\n",
    "        \n",
    "    #Call the functions within the function\n",
    "    #Tic tok used to time how long the processing time was.\n",
    "\n",
    "    print(\"\\n\")\n",
    "    printSolution(arraySizeX,arraySizeY,map)\n",
    "    toc = timeit.default_timer()\n",
    "    print(toc - tic)"
   ]
  },
  {
   "source": [
    "# Ant Colony Optimization"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "from random import random\n",
    "from random import randint\n",
    "\n",
    "#For ant colony optimization, we are expanding the matrix to allow space for the pheromones which will be place inbetween the nodes.\n",
    "#For example, a 3x3 matrix will turn into a 5x5 matrix\n",
    "\n",
    "#1 - 2 - 3\n",
    "#| x | x |\n",
    "#4 - 5 - 6\n",
    "#| x | x |\n",
    "#7 - 8 - 9\n",
    "\n",
    "#The numbers are the nodes, the lines are the pheromones and the x is blank spaces.\n",
    "\n",
    "#Class used to make ants.\n",
    "#The ants will move a random direction base on probability until they reach the end.\n",
    "\n",
    "class Ants:\n",
    "\n",
    "    #Each ant starts at the beginning of the matrix.\n",
    "    #Similar with the other two algorithms, we will be converting an integer value into a space in the 2d array.\n",
    "\n",
    "    def __init__(self):\n",
    "        self.currentNode = 0\n",
    "        self.lastDirection = \"Null\"\n",
    "\n",
    "    #This function returns a number which will be added to the current node of the ant depending on the direction it want to go to.\n",
    "\n",
    "    def updateCurrentNode(self,character,arraySizeX):\n",
    "        if character == \"w\":\n",
    "            return (-2*(arraySizeX*2-1))\n",
    "        elif character == \"a\":\n",
    "            return -2\n",
    "        elif character == \"s\":\n",
    "            return (2*(arraySizeX*2-1))\n",
    "        elif character == \"d\":\n",
    "            return +2\n",
    "        return 0\n",
    "\n",
    "    #Similar to dijkstras, we are calculating the difference between the current node and adjacent node next to it.\n",
    "    #It is very similar except for the fact that we have expanded our matrix to an even bigger one, so we multiply somethings by 2 when calculating.\n",
    "    #This gets it own function as we use it multiple times.\n",
    "\n",
    "    def calculateDifference(self, character,trail):\n",
    "\n",
    "        if character ==  \"w\":\n",
    "            return (trail[self.ModandDiv(\"//\")][self.ModandDiv(\"%\")]) - (trail[(self.currentNode-2*(arraySizeX*2-1))//(arraySizeX*2-1)][(self.currentNode-2*(arraySizeX*2-1)) % (arraySizeX*2-1)])\n",
    "        elif character == \"a\":\n",
    "            return (trail[self.ModandDiv(\"//\")][self.ModandDiv(\"%\")]) - (trail[(self.currentNode - 2)//(arraySizeX*2-1)][(self.currentNode - 2) % (arraySizeX*2-1)])\n",
    "        elif character == \"s\":\n",
    "            return (trail[self.ModandDiv(\"//\")][self.ModandDiv(\"%\")]) - (trail[(self.currentNode + (2 * (arraySizeX*2-1)))//(arraySizeX*2-1)][(self.currentNode+(2*(arraySizeX*2-1))) % (arraySizeX*2-1)])\n",
    "        elif character == \"d\":\n",
    "            return (trail[self.ModandDiv(\"//\")][self.ModandDiv(\"%\")]) - (trail[(self.currentNode + 2)//(arraySizeX*2-1)][(self.currentNode + 2) % (arraySizeX*2-1)])\n",
    "\n",
    "\n",
    "    #This function returns the adjacent pheromone depending on the direction given.\n",
    "\n",
    "    def returnPheromone(self, character,trail):\n",
    "        if character == \"s\":\n",
    "            return trail[(self.currentNode+(arraySizeX*2-1))//(arraySizeX*2-1)][(self.currentNode+(arraySizeX*2-1))% (arraySizeX*2-1)]\n",
    "        elif character == \"d\":\n",
    "            return trail[(self.currentNode+1)//(arraySizeX*2-1)][(self.currentNode+1)% (arraySizeX*2-1)]\n",
    "        elif character == \"w\":\n",
    "            return trail[(self.currentNode-(arraySizeX*2-1))//(arraySizeX*2-1)][((self.currentNode)-(arraySizeX*2-1))% (arraySizeX*2-1)]\n",
    "        elif character == \"a\":\n",
    "            return trail[(self.currentNode-1)//(arraySizeX*2-1)][(self.currentNode-1)% (arraySizeX*2-1)]\n",
    "        return 0\n",
    "\n",
    "    #This used to reduce line space.\n",
    "\n",
    "    def ModandDiv(self, symbol):\n",
    "        if symbol == \"//\":\n",
    "            return self.currentNode//(arraySizeX*2-1)\n",
    "        elif symbol == \"%\":\n",
    "            return self.currentNode % (arraySizeX*2-1)\n",
    "\n",
    "    #This function is used to record the pheromones that ant has passed.\n",
    "    #Only recording the pheromone between the nodes once.\n",
    "    #Else we ignore it.\n",
    "\n",
    "    #We also update the last direction and current node that the ant was on.\n",
    "\n",
    "    def moveAnt(self,i,arraySizeX,trail):\n",
    "        self.lastDirection = i\n",
    "        if i == \"w\":\n",
    "            adjNode = self.currentNode - arraySizeX*2-1\n",
    "        elif i == \"a\":\n",
    "            adjNode = self.currentNode - 1\n",
    "        elif i == \"s\":\n",
    "            adjNode = self.currentNode + arraySizeX*2-1\n",
    "        elif i == \"d\":\n",
    "            adjNode = self.currentNode + 1\n",
    "        if adjNode not in self.uniqueNodes:\n",
    "            self.totalLength += abs(self.calculateDifference(i,trail))\n",
    "            self.uniqueNodes.append(adjNode)\n",
    "        self.currentNode += self.updateCurrentNode(i,arraySizeX)\n",
    "\n",
    "\n",
    "    #This function moves the ant base on probability.\n",
    "    #First we calculate the denominator by using the sum of the pheromone multiplied by 1/distance between the nodes.\n",
    "    #Then roll a random number between 0 to 1 which will land between the probablities of going to a node to decide which direction to go to.\n",
    "\n",
    "    def findRandomPath(self,arraySizeX,arraySizeY,trail):\n",
    "\n",
    "        self.currentNode = 0\n",
    "        self.lastDirection = \"Null\"\n",
    "        self.totalLength = 0\n",
    "        self.uniqueNodes = []\n",
    "        self.path = []\n",
    "        #This while loop stops when the ant reaches the end of the matrix.\n",
    "\n",
    "        while (self.currentNode != (arraySizeX*2-1)*(arraySizeY*2-1)-1):\n",
    "            self.case = []\n",
    "            specialCase = []\n",
    "            self.trailSum = 0\n",
    "            self.path.append(self.currentNode)\n",
    "            #These 4 if statements are used to calculate the total difference for the current node to the adjacent nodes.\n",
    "            #One if statement for a direction.\n",
    "            #Only condition is that it cant go of the edge (out of bounds) of the matrix.\n",
    "            #And cant go back to a node that the ant was previously on.\n",
    "\n",
    "            #Since we are doing difference of node, there is a special case if the current node and the adjacent node is the same number.\n",
    "            #This because 0/total will always give 0\n",
    "            #Therefore we need to account for an option to go that node.\n",
    "\n",
    "            if ((self.currentNode //((arraySizeX*2)-1)) < (arraySizeY*2 - 2) and self.lastDirection != \"w\") :\n",
    "                if (self.calculateDifference(\"s\",trail) != 0):\n",
    "                    self.trailSum += self.returnPheromone(\"s\",trail) * (1/abs(self.calculateDifference(\"s\",trail)))\n",
    "                    self.case.append(\"s\")\n",
    "                else:\n",
    "                    specialCase.append(\"s\")\n",
    "\n",
    "\n",
    "            if (self.currentNode %(arraySizeX*2-1) < (arraySizeX*2-1) - 1 and self.lastDirection != \"a\") :\n",
    "                if (self.calculateDifference(\"d\",trail) != 0):\n",
    "                    self.trailSum += self.returnPheromone(\"d\",trail) * (1/abs(self.calculateDifference(\"d\",trail)))\n",
    "                    self.case.append(\"d\")\n",
    "                else:\n",
    "                    specialCase.append(\"d\")\n",
    "\n",
    "            #For direction w (up) and a (left), when working with a small matrix, it is very unlikely that up and left are the right way to go.\n",
    "            #Therefore there is a 50% the ant goes to that direction.\n",
    "            #There is also an infinite loop that could occur if we did not have this.\n",
    "\n",
    "            if (self.currentNode >=(arraySizeX*2-1) and self.lastDirection != \"s\") :\n",
    "                if (self.calculateDifference(\"w\",trail) != 0):\n",
    "                    self.trailSum += self.returnPheromone(\"w\",trail) * (1/abs(self.calculateDifference(\"w\",trail)))\n",
    "                    self.case.append(\"w\")\n",
    "                else:\n",
    "                    rn = randint(0, 1)\n",
    "                    if (rn == 1):\n",
    "                        specialCase.append(\"w\")\n",
    "\n",
    "\n",
    "            if (self.currentNode % (arraySizeX*2-1) > 0 and self.lastDirection != \"d\") :\n",
    "                if (self.calculateDifference(\"a\",trail) != 0):\n",
    "                    self.trailSum += self.returnPheromone(\"a\",trail) * (1/abs(self.calculateDifference(\"a\",trail)))\n",
    "                    self.case.append(\"a\")\n",
    "                else:\n",
    "                    rn = randint(0, 1)\n",
    "                    if (rn == 1):\n",
    "                        specialCase.append(\"a\")\n",
    "            \n",
    "\n",
    "\n",
    "            #Here we are calculating the probablity of the ant going to an adjacent node using a number between 0 and 1\n",
    "            #If there was no special case for the previous section, then the ant will go to nodes possible.\n",
    "            #If there is a special node then, the ant will always go there.\n",
    "\n",
    "            if len(specialCase) == 0:\n",
    "\n",
    "                #These set of if statements are used if the ant has 1,2 or 3 nodes that it can go to respectively.\n",
    "                #The probabilties for 3 paths are calculated by:\n",
    "                #The number can either land between these.\n",
    "                # 1/node1 -> 1/node2 + 1/node2 -> else\n",
    "\n",
    "                if len(self.case) == 1:\n",
    "                    self.moveAnt(self.case[0],arraySizeX,trail)\n",
    "\n",
    "                elif len(self.case) == 2:\n",
    "                    rn = random()\n",
    "                    if (rn < (self.returnPheromone(self.case[0],trail) *(1/abs(self.calculateDifference(self.case[0],trail))/self.trailSum))):\n",
    "                        self.moveAnt(self.case[0],arraySizeX,trail)\n",
    "                    else:\n",
    "                        self.moveAnt(self.case[1],arraySizeX,trail)\n",
    "\n",
    "                elif len(self.case) == 3:\n",
    "                    rn = random()\n",
    "                    if (rn < self.returnPheromone(self.case[0],trail) *(1/abs(self.calculateDifference(self.case[0],trail))/self.trailSum)):\n",
    "                        self.moveAnt(self.case[0],arraySizeX,trail)\n",
    "                    elif (rn < ((self.returnPheromone(self.case[0],trail)*1/abs(self.calculateDifference(self.case[0],trail))+ \\\n",
    "                        (self.returnPheromone(self.case[0],trail)*1/abs(self.calculateDifference(self.case[1],trail))))/self.trailSum)):\n",
    "                        \n",
    "                        self.moveAnt(self.case[1],arraySizeX,trail)\n",
    "                    else:\n",
    "                        self.moveAnt(self.case[2],arraySizeX,trail)\n",
    "\n",
    "\n",
    "            #For special cases, if there is only one, then we go to that.\n",
    "            #Else we roll a number between the amount of special cases there are and chose the one we land on.\n",
    "\n",
    "            elif len(specialCase) == 1:\n",
    "                self.moveAnt(specialCase[0],arraySizeX,trail)\n",
    "            elif len(specialCase) == 2:\n",
    "                if (randint(0, 1) == 0):\n",
    "                    self.moveAnt(specialCase[0],arraySizeX,trail)\n",
    "                else:\n",
    "                    self.moveAnt(specialCase[1],arraySizeX,trail)  \n",
    "            else:\n",
    "                randomnumber = randint(0, 2)\n",
    "                if (randomnumber == 0):\n",
    "                    self.moveAnt(specialCase[0],arraySizeX,trail)\n",
    "                elif (randomnumber == 1):\n",
    "                    self.moveAnt(specialCase[1],arraySizeX,trail)\n",
    "                else:\n",
    "                    self.moveAnt(specialCase[2],arraySizeX,trail)    \n",
    "        self.path.append(self.currentNode)\n",
    "        self.path.append((arraySizeX*2-1)*(arraySizeY*2-1)-1)\n",
    "def runAntColony(numberOfAnts, numberOfCycles):\n",
    "    \n",
    "\n",
    "    trail = np.zeros((arraySizeY*2-1,arraySizeX*2-1))\n",
    "\n",
    "    #Add one to every pheromone as a starter\n",
    "\n",
    "    trail = trail + 1\n",
    "\n",
    "    #Add nodes to our new matrix.\n",
    "\n",
    "    for x in range(arraySizeX):\n",
    "        for y in range(arraySizeY):\n",
    "            trail[y*2][x*2] = randomArray[y][x]\n",
    "    print(trail)\n",
    "\n",
    "    #Here we are creating the ants and cycles.\n",
    "\n",
    "    listOfAnts = []\n",
    "\n",
    "    tic = timeit.default_timer()\n",
    "    for i in range(numberOfAnts):\n",
    "        listOfAnts.append(Ants())\n",
    "\n",
    "    #This function adds decay to the problem\n",
    "\n",
    "    def decayPhermone():\n",
    "        for y in range(arraySizeY):\n",
    "            for x in range(arraySizeX):\n",
    "                if (x < arraySizeX-1) :\n",
    "                    trail[y*2][(2*x)+1] *= 0.5\n",
    "                if (y < arraySizeY-1) :\n",
    "                    trail[y*2+1][2*x] *=0.5\n",
    "\n",
    "    #This function runs all the ants.\n",
    "\n",
    "    def cycle(number,trail):\n",
    "        for cycle in range(number):\n",
    "            decayPhermone()\n",
    "            for ants in listOfAnts:\n",
    "                ants.findRandomPath(arraySizeX,arraySizeY,trail)\n",
    "            for ants in listOfAnts:\n",
    "                for phermone in ants.uniqueNodes:\n",
    "                    trail[phermone//(arraySizeX*2-1)][phermone % (arraySizeX*2-1)] += (1/ants.totalLength)\n",
    "\n",
    "    cycle(numberOfCycles,trail)\n",
    "\n",
    "    #This for loop finds the ant that travelled the shortest distance. \n",
    "\n",
    "    smallestLength = 99999\n",
    "    for ants in listOfAnts:\n",
    "        ants.findRandomPath(arraySizeX,arraySizeY,trail)\n",
    "        if (ants.totalLength < smallestLength):\n",
    "            smallestLength = ants.totalLength\n",
    "            path = np.unique(ants.path)\n",
    "    print(trail)\n",
    "\n",
    "    #Prints out smallest length and computation time.\n",
    "\n",
    "    print(smallestLength)\n",
    "    toc = timeit.default_timer()\n",
    "    print(toc - tic) \n",
    "    print(path)\n",
    "\n",
    "    #This is not part of the algorithm, it is just to showcase the ant's path.\n",
    "\n",
    "    for y1 in range(arraySizeY):\n",
    "        print(\"\")\n",
    "        for x1 in range(arraySizeX):\n",
    "            check = 0\n",
    "            for scan in range(len(path)):\n",
    "                if(path[scan] == x1*2+(y1*2*(arraySizeX*2-1))):\n",
    "                    print(\"\\033[91m\" + str(trail[y1*2][x1*2].astype(int))  + \"\\033[0m\" , end = ' ')\n",
    "                    check = 1\n",
    "            if(check == 0):\n",
    "                print(str(trail[y1*2][x1*2].astype(int)) , end = ' ')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "\n",
      "Select an option:\n",
      "1) Play the board.\n",
      "2) Nearest neighbor solution.\n",
      "3) Dijkstra solution.\n",
      "4) Ant Colony Optimization solution\n",
      "5) Stop\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 32, 33, 53, 73, 74, 75, 76, 77, 78, 79, 99, 119, 139, 159, 179, 199, 219, 239, 259, 279, 299, 319, 339, 359, 379, 399, 419, 439, 459, 479, 499, 519, 539, 559, 579, 599, 619, 639, 659, 679, 699, 719, 739, 759, 779, 799, 799]\n",
      "\n",
      "3 \u001b[91m3\u001b[0m \u001b[91m8\u001b[0m \u001b[91m7\u001b[0m \u001b[91m5\u001b[0m \u001b[91m3\u001b[0m \u001b[91m3\u001b[0m \u001b[91m4\u001b[0m \u001b[91m2\u001b[0m \u001b[91m3\u001b[0m \u001b[91m3\u001b[0m \u001b[91m2\u001b[0m \u001b[91m4\u001b[0m 8 5 4 7 1 8 7 \n",
      "4 8 7 4 9 1 6 6 3 7 7 9 \u001b[91m3\u001b[0m \u001b[91m7\u001b[0m 3 9 8 7 8 7 \n",
      "1 3 5 5 9 2 5 4 7 8 8 1 7 \u001b[91m7\u001b[0m 1 2 6 3 6 2 \n",
      "3 1 4 3 4 6 8 8 1 3 5 4 2 \u001b[91m9\u001b[0m \u001b[91m8\u001b[0m \u001b[91m3\u001b[0m \u001b[91m5\u001b[0m \u001b[91m4\u001b[0m \u001b[91m3\u001b[0m \u001b[91m3\u001b[0m \n",
      "1 6 3 9 2 4 8 7 6 5 7 6 7 3 1 5 4 3 9 \u001b[91m1\u001b[0m \n",
      "5 4 8 7 1 2 9 1 6 2 7 9 9 5 7 7 2 7 4 \u001b[91m7\u001b[0m \n",
      "4 9 9 7 8 3 6 6 8 3 3 9 5 1 8 3 3 6 3 \u001b[91m3\u001b[0m \n",
      "4 8 3 9 5 3 8 7 8 3 4 3 7 4 2 6 4 5 3 \u001b[91m6\u001b[0m \n",
      "3 3 3 2 2 4 5 7 5 8 5 5 2 4 9 2 2 6 5 \u001b[91m2\u001b[0m \n",
      "7 6 5 3 3 7 3 2 4 6 9 9 8 9 9 3 7 6 2 \u001b[91m1\u001b[0m \n",
      "3 1 3 4 9 5 6 9 8 6 4 1 8 7 4 5 9 9 2 \u001b[91m4\u001b[0m \n",
      "1 8 2 4 7 4 3 6 7 1 8 7 6 6 6 9 2 7 4 \u001b[91m8\u001b[0m \n",
      "1 4 1 3 1 1 8 5 3 9 4 1 2 3 8 4 5 5 5 \u001b[91m7\u001b[0m \n",
      "4 2 1 3 3 1 8 6 5 1 3 3 6 5 1 2 4 1 8 \u001b[91m3\u001b[0m \n",
      "5 1 5 9 4 5 3 8 2 8 9 6 4 1 4 5 7 6 6 \u001b[91m3\u001b[0m \n",
      "6 4 2 5 9 1 2 1 9 3 4 6 8 6 8 8 3 9 9 \u001b[91m4\u001b[0m \n",
      "1 7 4 8 9 2 3 1 6 7 7 7 2 4 9 4 5 5 1 \u001b[91m8\u001b[0m \n",
      "4 4 8 7 2 9 4 3 8 1 8 3 1 4 4 4 3 3 2 \u001b[91m5\u001b[0m \n",
      "5 9 4 3 4 5 9 9 2 3 9 7 3 3 4 5 6 9 9 \u001b[91m1\u001b[0m \n",
      "1 7 8 9 4 4 7 7 1 1 6 8 4 1 4 8 7 8 2 \u001b[91m7\u001b[0m \n",
      "3 3 2 2 8 6 5 9 2 9 6 8 4 5 1 9 7 6 5 \u001b[91m1\u001b[0m \n",
      "9 8 4 7 1 3 4 2 9 7 3 3 2 1 6 9 5 7 7 \u001b[91m2\u001b[0m \n",
      "5 4 2 8 8 5 3 2 6 4 1 4 7 6 1 2 2 5 2 \u001b[91m8\u001b[0m \n",
      "4 3 2 7 9 3 2 2 4 9 8 1 7 6 2 2 1 3 9 \u001b[91m8\u001b[0m \n",
      "9 2 4 6 7 4 8 8 6 1 9 2 8 9 2 4 3 2 8 \u001b[91m7\u001b[0m \n",
      "7 8 4 2 5 6 7 6 3 2 9 1 3 4 1 2 4 6 8 \u001b[91m2\u001b[0m \n",
      "5 6 8 7 9 5 4 5 9 7 2 3 9 4 9 5 9 9 8 \u001b[91m9\u001b[0m \n",
      "4 3 8 9 4 4 3 7 6 5 7 8 4 6 8 3 3 1 5 \u001b[91m1\u001b[0m \n",
      "6 6 9 7 1 1 6 5 5 9 8 5 5 1 5 1 6 7 8 \u001b[91m3\u001b[0m \n",
      "5 6 1 5 8 9 5 6 8 9 4 5 4 1 1 8 4 1 3 \u001b[91m2\u001b[0m \n",
      "2 4 7 3 3 5 8 6 5 3 5 8 4 2 8 6 3 7 7 \u001b[91m5\u001b[0m \n",
      "9 1 3 9 1 9 6 5 3 3 1 1 8 5 2 2 7 8 4 \u001b[91m6\u001b[0m \n",
      "1 4 2 1 8 8 8 2 1 1 7 8 3 1 6 7 8 2 1 \u001b[91m1\u001b[0m \n",
      "9 8 6 4 9 3 6 4 3 4 9 6 5 7 3 4 5 2 4 \u001b[91m2\u001b[0m \n",
      "5 5 6 7 7 3 6 4 4 7 6 6 9 6 9 6 3 9 7 \u001b[91m3\u001b[0m \n",
      "4 8 9 5 2 8 9 2 9 8 7 5 1 9 8 3 5 4 6 \u001b[91m8\u001b[0m \n",
      "7 7 7 4 6 5 3 2 7 7 8 4 3 7 5 6 8 2 3 \u001b[91m5\u001b[0m \n",
      "8 3 4 2 1 3 4 9 2 7 2 2 7 8 7 7 2 4 4 \u001b[91m1\u001b[0m \n",
      "7 8 9 3 2 8 7 1 3 2 6 3 2 7 2 5 5 8 4 \u001b[91m8\u001b[0m \n",
      "9 4 4 9 9 6 6 7 9 9 2 2 7 5 7 8 3 8 2 \u001b[91m6\u001b[0m \n",
      "The length:  153\n",
      "\n",
      "The time to compute:  0.02813349999996717\n",
      "\n",
      "Would you like to try another action?\n",
      "\n",
      "\n",
      "Shortest distance from beginning to each node.\n",
      "\n",
      "[0.] [0.] [5.] [6.] [8.] [10.] [10.] [11.] [13.] [14.] [14.] [15.] [17.] [21.] [24.] [25.] [28.] [34.] [31.] [32.] \n",
      "[1.] [5.] [6.] [9.] [12.] [12.] [13.] [13.] [14.] [18.] [18.] [20.] [18.] [22.] [26.] [30.] [29.] [30.] [31.] [32.] \n",
      "[4.] [6.] [8.] [8.] [12.] [13.] [14.] [15.] [18.] [19.] [19.] [26.] [22.] [22.] [28.] [29.] [31.] [34.] [33.] [35.] \n",
      "[6.] [8.] [9.] [10.] [11.] [13.] [15.] [15.] [22.] [20.] [22.] [23.] [25.] [24.] [25.] [30.] [32.] [33.] [34.] [34.] \n",
      "[8.] [13.] [10.] [16.] [13.] [15.] [15.] [16.] [17.] [18.] [20.] [21.] [22.] [26.] [28.] [30.] [31.] [32.] [38.] [36.] \n",
      "[12.] [13.] [15.] [16.] [14.] [15.] [16.] [22.] [17.] [21.] [20.] [22.] [22.] [26.] [28.] [28.] [33.] [36.] [37.] [40.] \n",
      "[13.] [16.] [16.] [16.] [17.] [16.] [19.] [19.] [19.] [22.] [22.] [22.] [26.] [30.] [29.] [32.] [32.] [35.] [36.] [36.] \n",
      "[13.] [17.] [14.] [18.] [18.] [16.] [21.] [20.] [19.] [22.] [23.] [24.] [28.] [29.] [31.] [35.] [33.] [34.] [36.] [39.] \n",
      "[14.] [14.] [14.] [15.] [15.] [17.] [18.] [20.] [22.] [25.] [24.] [24.] [27.] [29.] [30.] [35.] [35.] [35.] [36.] [39.] \n",
      "[18.] [17.] [16.] [16.] [16.] [20.] [20.] [21.] [23.] [25.] [28.] [28.] [29.] [30.] [30.] [36.] [36.] [35.] [39.] [40.] \n",
      "[22.] [20.] [18.] [17.] [22.] [22.] [23.] [26.] [27.] [25.] [27.] [30.] [29.] [30.] [33.] [34.] [38.] [38.] [39.] [41.] \n",
      "[24.] [25.] [19.] [17.] [20.] [23.] [24.] [27.] [28.] [30.] [31.] [32.] [31.] [31.] [31.] [34.] [41.] [40.] [39.] [41.] \n",
      "[24.] [23.] [20.] [18.] [20.] [20.] [27.] [28.] [30.] [36.] [35.] [36.] [35.] [34.] [33.] [37.] [38.] [38.] [38.] [40.] \n",
      "[23.] [21.] [20.] [18.] [18.] [20.] [27.] [29.] [30.] [34.] [34.] [34.] [35.] [36.] [40.] [39.] [39.] [42.] [41.] [44.] \n",
      "[24.] [22.] [24.] [24.] [19.] [20.] [22.] [27.] [33.] [35.] [34.] [31.] [33.] [36.] [39.] [40.] [42.] [43.] [43.] [44.] \n",
      "[25.] [25.] [27.] [28.] [24.] [24.] [23.] [24.] [32.] [34.] [33.] [31.] [33.] [35.] [37.] [37.] [40.] [42.] [42.] [45.] \n",
      "[30.] [28.] [29.] [25.] [24.] [25.] [24.] [24.] [29.] [30.] [30.] [30.] [35.] [37.] [38.] [37.] [38.] [38.] [40.] [45.] \n",
      "[31.] [31.] [27.] [26.] [31.] [30.] [25.] [26.] [31.] [36.] [31.] [34.] [36.] [37.] [37.] [37.] [38.] [38.] [39.] [42.] \n",
      "[32.] [36.] [31.] [30.] [31.] [32.] [30.] [30.] [37.] [38.] [32.] [34.] [38.] [38.] [37.] [38.] [39.] [42.] [42.] [46.] \n",
      "[36.] [36.] [35.] [36.] [31.] [31.] [32.] [32.] [38.] [38.] [35.] [35.] [39.] [40.] [37.] [41.] [40.] [41.] [45.] [50.] \n",
      "[38.] [38.] [39.] [39.] [35.] [33.] [34.] [34.] [39.] [38.] [35.] [35.] [39.] [40.] [40.] [42.] [40.] [41.] [42.] [46.] \n",
      "[44.] [43.] [41.] [42.] [38.] [36.] [35.] [37.] [42.] [40.] [38.] [38.] [39.] [40.] [45.] [42.] [42.] [42.] [42.] [47.] \n",
      "[46.] [45.] [43.] [41.] [41.] [38.] [36.] [37.] [41.] [43.] [40.] [39.] [42.] [43.] [46.] [45.] [45.] [44.] [47.] [53.] \n",
      "[45.] [44.] [43.] [42.] [42.] [38.] [37.] [37.] [39.] [44.] [45.] [42.] [42.] [43.] [45.] [45.] [46.] [46.] [52.] [53.] \n",
      "[50.] [45.] [45.] [43.] [42.] [39.] [43.] [43.] [41.] [46.] [46.] [43.] [43.] [44.] [45.] [47.] [48.] [47.] [53.] [54.] \n",
      "[50.] [49.] [45.] [45.] [42.] [41.] [42.] [43.] [44.] [45.] [46.] [44.] [46.] [47.] [46.] [47.] [49.] [51.] [53.] [59.] \n",
      "[52.] [51.] [49.] [48.] [46.] [42.] [43.] [44.] [48.] [50.] [47.] [46.] [52.] [47.] [52.] [50.] [54.] [54.] [53.] [54.] \n",
      "[53.] [54.] [49.] [48.] [43.] [43.] [44.] [46.] [47.] [48.] [50.] [51.] [51.] [49.] [51.] [52.] [52.] [54.] [56.] [60.] \n",
      "[53.] [53.] [50.] [50.] [46.] [46.] [47.] [48.] [48.] [52.] [51.] [52.] [52.] [54.] [54.] [54.] [55.] [56.] [57.] [62.] \n",
      "[54.] [53.] [56.] [52.] [53.] [52.] [48.] [49.] [51.] [52.] [53.] [52.] [53.] [54.] [54.] [61.] [57.] [60.] [62.] [63.] \n",
      "[57.] [55.] [58.] [54.] [54.] [54.] [51.] [49.] [50.] [52.] [54.] [55.] [53.] [55.] [61.] [61.] [58.] [62.] [62.] [64.] \n",
      "[64.] [58.] [60.] [60.] [56.] [54.] [51.] [50.] [52.] [52.] [54.] [54.] [57.] [58.] [61.] [61.] [62.] [63.] [65.] [65.] \n",
      "[64.] [61.] [61.] [60.] [53.] [53.] [53.] [53.] [54.] [54.] [60.] [61.] [62.] [62.] [65.] [64.] [63.] [69.] [68.] [68.] \n",
      "[60.] [59.] [57.] [59.] [54.] [58.] [55.] [55.] [56.] [57.] [62.] [59.] [60.] [62.] [66.] [67.] [66.] [69.] [71.] [69.] \n",
      "[58.] [58.] [57.] [56.] [56.] [58.] [55.] [55.] [55.] [58.] [59.] [59.] [62.] [63.] [66.] [69.] [68.] [74.] [74.] [70.] \n",
      "[59.] [61.] [60.] [58.] [61.] [59.] [58.] [57.] [60.] [59.] [60.] [60.] [64.] [66.] [67.] [72.] [70.] [71.] [73.] [75.] \n",
      "[62.] [62.] [62.] [59.] [61.] [60.] [58.] [57.] [60.] [60.] [61.] [61.] [62.] [66.] [68.] [69.] [71.] [73.] [74.] [76.] \n",
      "[63.] [64.] [63.] [61.] [62.] [60.] [59.] [64.] [65.] [60.] [63.] [63.] [66.] [67.] [68.] [68.] [73.] [75.] [75.] [78.] \n",
      "[64.] [65.] [66.] [62.] [63.] [63.] [62.] [68.] [66.] [65.] [67.] [64.] [65.] [68.] [73.] [70.] [70.] [73.] [75.] [79.] \n",
      "[66.] [69.] [69.] [66.] [66.] [63.] [63.] [64.] [66.] [66.] [65.] [65.] [70.] [70.] [72.] [73.] [72.] [73.] [77.] [81.] \n",
      "\n",
      "[0, 20, 40, 60, 80, 100, 120, 140, 160, 161, 162, 163, 183, 203, 223, 243, 263, 264, 284, 304, 324, 323, 343, 363, 364, 384, 385, 405, 406, 426, 446, 466, 465, 485, 505, 525, 545, 546, 566, 586, 587, 607, 627, 647, 667, 687, 688, 689, 690, 691, 711, 731, 732, 752, 753, 754, 755, 756, 757, 758, 778, 798, 799]\n",
      "\n",
      "3 3 8 7 5 3 3 4 2 3 3 2 4 8 5 4 7 1 8 7 \n",
      "\u001b[91m4\u001b[0m 8 7 4 9 1 6 6 3 7 7 9 3 7 3 9 8 7 8 7 \n",
      "\u001b[91m1\u001b[0m 3 5 5 9 2 5 4 7 8 8 1 7 7 1 2 6 3 6 2 \n",
      "\u001b[91m3\u001b[0m 1 4 3 4 6 8 8 1 3 5 4 2 9 8 3 5 4 3 3 \n",
      "\u001b[91m1\u001b[0m 6 3 9 2 4 8 7 6 5 7 6 7 3 1 5 4 3 9 1 \n",
      "\u001b[91m5\u001b[0m 4 8 7 1 2 9 1 6 2 7 9 9 5 7 7 2 7 4 7 \n",
      "\u001b[91m4\u001b[0m 9 9 7 8 3 6 6 8 3 3 9 5 1 8 3 3 6 3 3 \n",
      "\u001b[91m4\u001b[0m 8 3 9 5 3 8 7 8 3 4 3 7 4 2 6 4 5 3 6 \n",
      "\u001b[91m3\u001b[0m \u001b[91m3\u001b[0m \u001b[91m3\u001b[0m \u001b[91m2\u001b[0m 2 4 5 7 5 8 5 5 2 4 9 2 2 6 5 2 \n",
      "7 6 5 \u001b[91m3\u001b[0m 3 7 3 2 4 6 9 9 8 9 9 3 7 6 2 1 \n",
      "3 1 3 \u001b[91m4\u001b[0m 9 5 6 9 8 6 4 1 8 7 4 5 9 9 2 4 \n",
      "1 8 2 \u001b[91m4\u001b[0m 7 4 3 6 7 1 8 7 6 6 6 9 2 7 4 8 \n",
      "1 4 1 \u001b[91m3\u001b[0m 1 1 8 5 3 9 4 1 2 3 8 4 5 5 5 7 \n",
      "4 2 1 \u001b[91m3\u001b[0m \u001b[91m3\u001b[0m 1 8 6 5 1 3 3 6 5 1 2 4 1 8 3 \n",
      "5 1 5 9 \u001b[91m4\u001b[0m 5 3 8 2 8 9 6 4 1 4 5 7 6 6 3 \n",
      "6 4 2 5 \u001b[91m9\u001b[0m 1 2 1 9 3 4 6 8 6 8 8 3 9 9 4 \n",
      "1 7 4 \u001b[91m8\u001b[0m \u001b[91m9\u001b[0m 2 3 1 6 7 7 7 2 4 9 4 5 5 1 8 \n",
      "4 4 8 \u001b[91m7\u001b[0m 2 9 4 3 8 1 8 3 1 4 4 4 3 3 2 5 \n",
      "5 9 4 \u001b[91m3\u001b[0m \u001b[91m4\u001b[0m 5 9 9 2 3 9 7 3 3 4 5 6 9 9 1 \n",
      "1 7 8 9 \u001b[91m4\u001b[0m \u001b[91m4\u001b[0m 7 7 1 1 6 8 4 1 4 8 7 8 2 7 \n",
      "3 3 2 2 8 \u001b[91m6\u001b[0m \u001b[91m5\u001b[0m 9 2 9 6 8 4 5 1 9 7 6 5 1 \n",
      "9 8 4 7 1 3 \u001b[91m4\u001b[0m 2 9 7 3 3 2 1 6 9 5 7 7 2 \n",
      "5 4 2 8 8 5 \u001b[91m3\u001b[0m 2 6 4 1 4 7 6 1 2 2 5 2 8 \n",
      "4 3 2 7 9 \u001b[91m3\u001b[0m \u001b[91m2\u001b[0m 2 4 9 8 1 7 6 2 2 1 3 9 8 \n",
      "9 2 4 6 7 \u001b[91m4\u001b[0m 8 8 6 1 9 2 8 9 2 4 3 2 8 7 \n",
      "7 8 4 2 5 \u001b[91m6\u001b[0m 7 6 3 2 9 1 3 4 1 2 4 6 8 2 \n",
      "5 6 8 7 9 \u001b[91m5\u001b[0m 4 5 9 7 2 3 9 4 9 5 9 9 8 9 \n",
      "4 3 8 9 4 \u001b[91m4\u001b[0m \u001b[91m3\u001b[0m 7 6 5 7 8 4 6 8 3 3 1 5 1 \n",
      "6 6 9 7 1 1 \u001b[91m6\u001b[0m 5 5 9 8 5 5 1 5 1 6 7 8 3 \n",
      "5 6 1 5 8 9 \u001b[91m5\u001b[0m \u001b[91m6\u001b[0m 8 9 4 5 4 1 1 8 4 1 3 2 \n",
      "2 4 7 3 3 5 8 \u001b[91m6\u001b[0m 5 3 5 8 4 2 8 6 3 7 7 5 \n",
      "9 1 3 9 1 9 6 \u001b[91m5\u001b[0m 3 3 1 1 8 5 2 2 7 8 4 6 \n",
      "1 4 2 1 8 8 8 \u001b[91m2\u001b[0m 1 1 7 8 3 1 6 7 8 2 1 1 \n",
      "9 8 6 4 9 3 6 \u001b[91m4\u001b[0m 3 4 9 6 5 7 3 4 5 2 4 2 \n",
      "5 5 6 7 7 3 6 \u001b[91m4\u001b[0m \u001b[91m4\u001b[0m \u001b[91m7\u001b[0m \u001b[91m6\u001b[0m \u001b[91m6\u001b[0m 9 6 9 6 3 9 7 3 \n",
      "4 8 9 5 2 8 9 2 9 8 7 \u001b[91m5\u001b[0m 1 9 8 3 5 4 6 8 \n",
      "7 7 7 4 6 5 3 2 7 7 8 \u001b[91m4\u001b[0m \u001b[91m3\u001b[0m 7 5 6 8 2 3 5 \n",
      "8 3 4 2 1 3 4 9 2 7 2 2 \u001b[91m7\u001b[0m \u001b[91m8\u001b[0m \u001b[91m7\u001b[0m \u001b[91m7\u001b[0m \u001b[91m2\u001b[0m \u001b[91m4\u001b[0m \u001b[91m4\u001b[0m 1 \n",
      "7 8 9 3 2 8 7 1 3 2 6 3 2 7 2 5 5 8 \u001b[91m4\u001b[0m 8 \n",
      "9 4 4 9 9 6 6 7 9 9 2 2 7 5 7 8 3 8 \u001b[91m2\u001b[0m \u001b[91m6\u001b[0m 2.6285930999997618\n",
      "\n",
      "Would you like to try another action?\n",
      "How many ants do you want?\n",
      "How many cycles do you want?\n",
      "[[3. 1. 3. ... 8. 1. 7.]\n",
      " [1. 1. 1. ... 1. 1. 1.]\n",
      " [4. 1. 8. ... 8. 1. 7.]\n",
      " ...\n",
      " [7. 1. 8. ... 4. 1. 8.]\n",
      " [1. 1. 1. ... 1. 1. 1.]\n",
      " [9. 1. 4. ... 2. 1. 6.]]\n",
      "[[3.         0.26185003 3.         ... 8.         0.12505231 7.        ]\n",
      " [0.04675951 1.         0.16485216 ... 0.01533077 1.         0.01490647]\n",
      " [4.         0.15166146 8.         ... 8.         0.05222762 7.        ]\n",
      " ...\n",
      " [7.         0.05443422 8.         ... 4.         0.08757534 8.        ]\n",
      " [0.03502403 1.         0.02497644 ... 0.10236054 1.         0.08578969]\n",
      " [9.         0.03798258 4.         ... 2.         0.17703691 6.        ]]\n",
      "363.0\n",
      "21.96450640000012\n",
      "[   0    2    4    6    8   86  164  234  236  242  244  246  312  314\n",
      "  316  324  390  392  394  396  398  400  402  468  470  472  474  476\n",
      "  478  480  482  546  548  550  552  554  556  560  624  626  628  630\n",
      "  632  634  636  638  702  704  706  708  710  780  782  784  786  788\n",
      "  862  864  866  940  942  944  946 1014 1016 1018 1020 1022 1024 1026\n",
      " 1092 1094 1096 1098 1100 1102 1104 1182 1184 1192 1194 1196 1262 1264\n",
      " 1266 1268 1270 1274 1352 1354 1432 1502 1504 1506 1508 1510 1580 1582\n",
      " 1584 1586 1658 1660 1662 1664 1742 1820 1894 1896 1898 1972 1974 1976\n",
      " 1978 1980 1982 1984 1986 2054 2056 2058 2060 2062 2064 2132 2136 2138\n",
      " 2142 2144 2210 2220 2222 2288 2290 2292 2294 2296 2298 2300 2368 2370\n",
      " 2372 2374 2376 2378 2454 2456 2532 2534 2612 2688 2690 2766 2768 2844\n",
      " 2846 2922 2998 3000 3076 3078 3080]\n",
      "\n",
      "\u001b[91m3\u001b[0m \u001b[91m3\u001b[0m \u001b[91m8\u001b[0m \u001b[91m7\u001b[0m \u001b[91m5\u001b[0m 3 3 4 2 3 3 2 4 8 5 4 7 1 8 7 \n",
      "4 8 7 4 \u001b[91m9\u001b[0m 1 6 6 3 7 7 9 3 7 3 9 8 7 8 7 \n",
      "1 3 5 5 \u001b[91m9\u001b[0m 2 5 4 7 8 8 1 7 7 1 2 6 3 6 2 \n",
      "\u001b[91m3\u001b[0m \u001b[91m1\u001b[0m 4 3 \u001b[91m4\u001b[0m \u001b[91m6\u001b[0m \u001b[91m8\u001b[0m 8 1 3 5 4 2 9 8 3 5 4 3 3 \n",
      "\u001b[91m1\u001b[0m \u001b[91m6\u001b[0m \u001b[91m3\u001b[0m 9 2 4 \u001b[91m8\u001b[0m 7 6 5 7 6 7 3 1 5 4 3 9 1 \n",
      "\u001b[91m5\u001b[0m \u001b[91m4\u001b[0m \u001b[91m8\u001b[0m \u001b[91m7\u001b[0m \u001b[91m1\u001b[0m \u001b[91m2\u001b[0m \u001b[91m9\u001b[0m 1 6 2 7 9 9 5 7 7 2 7 4 7 \n",
      "\u001b[91m4\u001b[0m \u001b[91m9\u001b[0m \u001b[91m9\u001b[0m \u001b[91m7\u001b[0m \u001b[91m8\u001b[0m \u001b[91m3\u001b[0m \u001b[91m6\u001b[0m \u001b[91m6\u001b[0m 8 3 3 9 5 1 8 3 3 6 3 3 \n",
      "\u001b[91m4\u001b[0m \u001b[91m8\u001b[0m \u001b[91m3\u001b[0m \u001b[91m9\u001b[0m \u001b[91m5\u001b[0m \u001b[91m3\u001b[0m 8 \u001b[91m7\u001b[0m 8 3 4 3 7 4 2 6 4 5 3 6 \n",
      "\u001b[91m3\u001b[0m \u001b[91m3\u001b[0m \u001b[91m3\u001b[0m \u001b[91m2\u001b[0m \u001b[91m2\u001b[0m \u001b[91m4\u001b[0m \u001b[91m5\u001b[0m \u001b[91m7\u001b[0m 5 8 5 5 2 4 9 2 2 6 5 2 \n",
      "\u001b[91m7\u001b[0m \u001b[91m6\u001b[0m \u001b[91m5\u001b[0m \u001b[91m3\u001b[0m \u001b[91m3\u001b[0m 7 3 2 4 6 9 9 8 9 9 3 7 6 2 1 \n",
      "\u001b[91m3\u001b[0m \u001b[91m1\u001b[0m \u001b[91m3\u001b[0m \u001b[91m4\u001b[0m \u001b[91m9\u001b[0m 5 6 9 8 6 4 1 8 7 4 5 9 9 2 4 \n",
      "1 8 \u001b[91m2\u001b[0m \u001b[91m4\u001b[0m \u001b[91m7\u001b[0m 4 3 6 7 1 8 7 6 6 6 9 2 7 4 8 \n",
      "1 4 \u001b[91m1\u001b[0m \u001b[91m3\u001b[0m \u001b[91m1\u001b[0m \u001b[91m1\u001b[0m 8 5 3 9 4 1 2 3 8 4 5 5 5 7 \n",
      "\u001b[91m4\u001b[0m \u001b[91m2\u001b[0m \u001b[91m1\u001b[0m \u001b[91m3\u001b[0m \u001b[91m3\u001b[0m \u001b[91m1\u001b[0m \u001b[91m8\u001b[0m 6 5 1 3 3 6 5 1 2 4 1 8 3 \n",
      "\u001b[91m5\u001b[0m \u001b[91m1\u001b[0m \u001b[91m5\u001b[0m \u001b[91m9\u001b[0m \u001b[91m4\u001b[0m \u001b[91m5\u001b[0m \u001b[91m3\u001b[0m 8 2 8 9 6 4 1 4 5 7 6 6 3 \n",
      "6 4 2 5 9 1 \u001b[91m2\u001b[0m \u001b[91m1\u001b[0m 9 3 4 \u001b[91m6\u001b[0m \u001b[91m8\u001b[0m \u001b[91m6\u001b[0m 8 8 3 9 9 4 \n",
      "1 7 4 8 9 2 3 \u001b[91m1\u001b[0m \u001b[91m6\u001b[0m \u001b[91m7\u001b[0m \u001b[91m7\u001b[0m \u001b[91m7\u001b[0m 2 \u001b[91m4\u001b[0m 9 4 5 5 1 8 \n",
      "4 4 8 7 2 9 4 3 8 1 8 3 1 \u001b[91m4\u001b[0m \u001b[91m4\u001b[0m 4 3 3 2 5 \n",
      "5 9 4 3 4 5 9 9 2 3 9 7 3 3 \u001b[91m4\u001b[0m 5 6 9 9 1 \n",
      "1 7 8 9 4 4 7 7 1 1 \u001b[91m6\u001b[0m \u001b[91m8\u001b[0m \u001b[91m4\u001b[0m \u001b[91m1\u001b[0m \u001b[91m4\u001b[0m 8 7 8 2 7 \n",
      "3 3 2 2 8 6 5 9 2 9 \u001b[91m6\u001b[0m \u001b[91m8\u001b[0m \u001b[91m4\u001b[0m \u001b[91m5\u001b[0m 1 9 7 6 5 1 \n",
      "9 8 4 7 1 3 4 2 9 7 \u001b[91m3\u001b[0m \u001b[91m3\u001b[0m \u001b[91m2\u001b[0m \u001b[91m1\u001b[0m 6 9 5 7 7 2 \n",
      "5 4 2 8 8 5 3 2 6 4 1 4 7 \u001b[91m6\u001b[0m 1 2 2 5 2 8 \n",
      "4 3 2 7 9 3 2 2 4 9 8 1 7 \u001b[91m6\u001b[0m 2 2 1 3 9 8 \n",
      "9 2 4 6 7 4 8 8 6 1 9 \u001b[91m2\u001b[0m \u001b[91m8\u001b[0m \u001b[91m9\u001b[0m 2 4 3 2 8 7 \n",
      "7 8 4 2 5 6 7 6 3 2 9 \u001b[91m1\u001b[0m \u001b[91m3\u001b[0m \u001b[91m4\u001b[0m \u001b[91m1\u001b[0m \u001b[91m2\u001b[0m \u001b[91m4\u001b[0m \u001b[91m6\u001b[0m \u001b[91m8\u001b[0m 2 \n",
      "5 6 8 7 9 5 4 5 9 7 2 3 9 \u001b[91m4\u001b[0m \u001b[91m9\u001b[0m \u001b[91m5\u001b[0m \u001b[91m9\u001b[0m \u001b[91m9\u001b[0m \u001b[91m8\u001b[0m 9 \n",
      "4 3 8 9 4 4 3 7 6 5 7 8 4 \u001b[91m6\u001b[0m 8 \u001b[91m3\u001b[0m \u001b[91m3\u001b[0m 1 \u001b[91m5\u001b[0m \u001b[91m1\u001b[0m \n",
      "6 6 9 7 1 1 6 5 5 9 8 5 5 \u001b[91m1\u001b[0m 5 1 6 7 \u001b[91m8\u001b[0m \u001b[91m3\u001b[0m \n",
      "5 6 1 5 8 9 5 6 8 9 4 5 4 \u001b[91m1\u001b[0m \u001b[91m1\u001b[0m \u001b[91m8\u001b[0m \u001b[91m4\u001b[0m \u001b[91m1\u001b[0m \u001b[91m3\u001b[0m \u001b[91m2\u001b[0m \n",
      "2 4 7 3 3 5 8 6 5 3 5 8 4 2 \u001b[91m8\u001b[0m \u001b[91m6\u001b[0m \u001b[91m3\u001b[0m \u001b[91m7\u001b[0m \u001b[91m7\u001b[0m \u001b[91m5\u001b[0m \n",
      "9 1 3 9 1 9 6 5 3 3 1 1 8 5 2 2 7 8 \u001b[91m4\u001b[0m \u001b[91m6\u001b[0m \n",
      "1 4 2 1 8 8 8 2 1 1 7 8 3 1 6 7 8 2 \u001b[91m1\u001b[0m \u001b[91m1\u001b[0m \n",
      "9 8 6 4 9 3 6 4 3 4 9 6 5 7 3 4 5 2 4 \u001b[91m2\u001b[0m \n",
      "5 5 6 7 7 3 6 4 4 7 6 6 9 6 9 6 3 9 \u001b[91m7\u001b[0m \u001b[91m3\u001b[0m \n",
      "4 8 9 5 2 8 9 2 9 8 7 5 1 9 8 3 5 4 \u001b[91m6\u001b[0m \u001b[91m8\u001b[0m \n",
      "7 7 7 4 6 5 3 2 7 7 8 4 3 7 5 6 8 2 \u001b[91m3\u001b[0m \u001b[91m5\u001b[0m \n",
      "8 3 4 2 1 3 4 9 2 7 2 2 7 8 7 7 2 4 \u001b[91m4\u001b[0m 1 \n",
      "7 8 9 3 2 8 7 1 3 2 6 3 2 7 2 5 5 \u001b[91m8\u001b[0m \u001b[91m4\u001b[0m 8 \n",
      "9 4 4 9 9 6 6 7 9 9 2 2 7 5 7 8 3 \u001b[91m8\u001b[0m \u001b[91m2\u001b[0m \u001b[91m6\u001b[0m \n",
      "Would you like to try another action?\n",
      "\n",
      "\u001b[91m3\u001b[0m 3 8 7 5 3 3 4 2 3 3 2 4 8 5 4 7 1 8 7 \n",
      "4 8 7 4 9 1 6 6 3 7 7 9 3 7 3 9 8 7 8 7 \n",
      "1 3 5 5 9 2 5 4 7 8 8 1 7 7 1 2 6 3 6 2 \n",
      "3 1 4 3 4 6 8 8 1 3 5 4 2 9 8 3 5 4 3 3 \n",
      "1 6 3 9 2 4 8 7 6 5 7 6 7 3 1 5 4 3 9 1 \n",
      "5 4 8 7 1 2 9 1 6 2 7 9 9 5 7 7 2 7 4 7 \n",
      "4 9 9 7 8 3 6 6 8 3 3 9 5 1 8 3 3 6 3 3 \n",
      "4 8 3 9 5 3 8 7 8 3 4 3 7 4 2 6 4 5 3 6 \n",
      "3 3 3 2 2 4 5 7 5 8 5 5 2 4 9 2 2 6 5 2 \n",
      "7 6 5 3 3 7 3 2 4 6 9 9 8 9 9 3 7 6 2 1 \n",
      "3 1 3 4 9 5 6 9 8 6 4 1 8 7 4 5 9 9 2 4 \n",
      "1 8 2 4 7 4 3 6 7 1 8 7 6 6 6 9 2 7 4 8 \n",
      "1 4 1 3 1 1 8 5 3 9 4 1 2 3 8 4 5 5 5 7 \n",
      "4 2 1 3 3 1 8 6 5 1 3 3 6 5 1 2 4 1 8 3 \n",
      "5 1 5 9 4 5 3 8 2 8 9 6 4 1 4 5 7 6 6 3 \n",
      "6 4 2 5 9 1 2 1 9 3 4 6 8 6 8 8 3 9 9 4 \n",
      "1 7 4 8 9 2 3 1 6 7 7 7 2 4 9 4 5 5 1 8 \n",
      "4 4 8 7 2 9 4 3 8 1 8 3 1 4 4 4 3 3 2 5 \n",
      "5 9 4 3 4 5 9 9 2 3 9 7 3 3 4 5 6 9 9 1 \n",
      "1 7 8 9 4 4 7 7 1 1 6 8 4 1 4 8 7 8 2 7 \n",
      "3 3 2 2 8 6 5 9 2 9 6 8 4 5 1 9 7 6 5 1 \n",
      "9 8 4 7 1 3 4 2 9 7 3 3 2 1 6 9 5 7 7 2 \n",
      "5 4 2 8 8 5 3 2 6 4 1 4 7 6 1 2 2 5 2 8 \n",
      "4 3 2 7 9 3 2 2 4 9 8 1 7 6 2 2 1 3 9 8 \n",
      "9 2 4 6 7 4 8 8 6 1 9 2 8 9 2 4 3 2 8 7 \n",
      "7 8 4 2 5 6 7 6 3 2 9 1 3 4 1 2 4 6 8 2 \n",
      "5 6 8 7 9 5 4 5 9 7 2 3 9 4 9 5 9 9 8 9 \n",
      "4 3 8 9 4 4 3 7 6 5 7 8 4 6 8 3 3 1 5 1 \n",
      "6 6 9 7 1 1 6 5 5 9 8 5 5 1 5 1 6 7 8 3 \n",
      "5 6 1 5 8 9 5 6 8 9 4 5 4 1 1 8 4 1 3 2 \n",
      "2 4 7 3 3 5 8 6 5 3 5 8 4 2 8 6 3 7 7 5 \n",
      "9 1 3 9 1 9 6 5 3 3 1 1 8 5 2 2 7 8 4 6 \n",
      "1 4 2 1 8 8 8 2 1 1 7 8 3 1 6 7 8 2 1 1 \n",
      "9 8 6 4 9 3 6 4 3 4 9 6 5 7 3 4 5 2 4 2 \n",
      "5 5 6 7 7 3 6 4 4 7 6 6 9 6 9 6 3 9 7 3 \n",
      "4 8 9 5 2 8 9 2 9 8 7 5 1 9 8 3 5 4 6 8 \n",
      "7 7 7 4 6 5 3 2 7 7 8 4 3 7 5 6 8 2 3 5 \n",
      "8 3 4 2 1 3 4 9 2 7 2 2 7 8 7 7 2 4 4 1 \n",
      "7 8 9 3 2 8 7 1 3 2 6 3 2 7 2 5 5 8 4 8 \n",
      "9 4 4 9 9 6 6 7 9 9 2 2 7 5 7 8 3 8 2 6 \n",
      "What direction do you want to go?\n",
      "\n",
      "3 \u001b[91m3\u001b[0m 8 7 5 3 3 4 2 3 3 2 4 8 5 4 7 1 8 7 \n",
      "4 8 7 4 9 1 6 6 3 7 7 9 3 7 3 9 8 7 8 7 \n",
      "1 3 5 5 9 2 5 4 7 8 8 1 7 7 1 2 6 3 6 2 \n",
      "3 1 4 3 4 6 8 8 1 3 5 4 2 9 8 3 5 4 3 3 \n",
      "1 6 3 9 2 4 8 7 6 5 7 6 7 3 1 5 4 3 9 1 \n",
      "5 4 8 7 1 2 9 1 6 2 7 9 9 5 7 7 2 7 4 7 \n",
      "4 9 9 7 8 3 6 6 8 3 3 9 5 1 8 3 3 6 3 3 \n",
      "4 8 3 9 5 3 8 7 8 3 4 3 7 4 2 6 4 5 3 6 \n",
      "3 3 3 2 2 4 5 7 5 8 5 5 2 4 9 2 2 6 5 2 \n",
      "7 6 5 3 3 7 3 2 4 6 9 9 8 9 9 3 7 6 2 1 \n",
      "3 1 3 4 9 5 6 9 8 6 4 1 8 7 4 5 9 9 2 4 \n",
      "1 8 2 4 7 4 3 6 7 1 8 7 6 6 6 9 2 7 4 8 \n",
      "1 4 1 3 1 1 8 5 3 9 4 1 2 3 8 4 5 5 5 7 \n",
      "4 2 1 3 3 1 8 6 5 1 3 3 6 5 1 2 4 1 8 3 \n",
      "5 1 5 9 4 5 3 8 2 8 9 6 4 1 4 5 7 6 6 3 \n",
      "6 4 2 5 9 1 2 1 9 3 4 6 8 6 8 8 3 9 9 4 \n",
      "1 7 4 8 9 2 3 1 6 7 7 7 2 4 9 4 5 5 1 8 \n",
      "4 4 8 7 2 9 4 3 8 1 8 3 1 4 4 4 3 3 2 5 \n",
      "5 9 4 3 4 5 9 9 2 3 9 7 3 3 4 5 6 9 9 1 \n",
      "1 7 8 9 4 4 7 7 1 1 6 8 4 1 4 8 7 8 2 7 \n",
      "3 3 2 2 8 6 5 9 2 9 6 8 4 5 1 9 7 6 5 1 \n",
      "9 8 4 7 1 3 4 2 9 7 3 3 2 1 6 9 5 7 7 2 \n",
      "5 4 2 8 8 5 3 2 6 4 1 4 7 6 1 2 2 5 2 8 \n",
      "4 3 2 7 9 3 2 2 4 9 8 1 7 6 2 2 1 3 9 8 \n",
      "9 2 4 6 7 4 8 8 6 1 9 2 8 9 2 4 3 2 8 7 \n",
      "7 8 4 2 5 6 7 6 3 2 9 1 3 4 1 2 4 6 8 2 \n",
      "5 6 8 7 9 5 4 5 9 7 2 3 9 4 9 5 9 9 8 9 \n",
      "4 3 8 9 4 4 3 7 6 5 7 8 4 6 8 3 3 1 5 1 \n",
      "6 6 9 7 1 1 6 5 5 9 8 5 5 1 5 1 6 7 8 3 \n",
      "5 6 1 5 8 9 5 6 8 9 4 5 4 1 1 8 4 1 3 2 \n",
      "2 4 7 3 3 5 8 6 5 3 5 8 4 2 8 6 3 7 7 5 \n",
      "9 1 3 9 1 9 6 5 3 3 1 1 8 5 2 2 7 8 4 6 \n",
      "1 4 2 1 8 8 8 2 1 1 7 8 3 1 6 7 8 2 1 1 \n",
      "9 8 6 4 9 3 6 4 3 4 9 6 5 7 3 4 5 2 4 2 \n",
      "5 5 6 7 7 3 6 4 4 7 6 6 9 6 9 6 3 9 7 3 \n",
      "4 8 9 5 2 8 9 2 9 8 7 5 1 9 8 3 5 4 6 8 \n",
      "7 7 7 4 6 5 3 2 7 7 8 4 3 7 5 6 8 2 3 5 \n",
      "8 3 4 2 1 3 4 9 2 7 2 2 7 8 7 7 2 4 4 1 \n",
      "7 8 9 3 2 8 7 1 3 2 6 3 2 7 2 5 5 8 4 8 \n",
      "9 4 4 9 9 6 6 7 9 9 2 2 7 5 7 8 3 8 2 6 \n",
      "What direction do you want to go?\n"
     ]
    },
    {
     "output_type": "error",
     "ename": "KeyboardInterrupt",
     "evalue": "Interrupted by user",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-13-fb00ae420030>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m     14\u001b[0m         \u001b[1;32mwhile\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mcurrentElement\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[0marraySizeX\u001b[0m\u001b[1;33m*\u001b[0m\u001b[0marraySizeY\u001b[0m \u001b[1;33m-\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     15\u001b[0m             \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"\\nWhat direction do you want to go?\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 16\u001b[1;33m             \u001b[0musersinput\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0minput\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     17\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mcurrentElement\u001b[0m \u001b[1;33m>=\u001b[0m\u001b[0marraySizeX\u001b[0m \u001b[1;32mand\u001b[0m \u001b[0musersinput\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;34m\"w\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     18\u001b[0m                 total += abs((randomArray[currentElement//arraySizeX][currentElement % arraySizeX]) - \\\n",
      "\u001b[1;32m~\\AppData\\Roaming\\Python\\Python38\\site-packages\\ipykernel\\kernelbase.py\u001b[0m in \u001b[0;36mraw_input\u001b[1;34m(self, prompt)\u001b[0m\n\u001b[0;32m    858\u001b[0m                 \u001b[1;34m\"raw_input was called, but this frontend does not support input requests.\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    859\u001b[0m             )\n\u001b[1;32m--> 860\u001b[1;33m         return self._input_request(str(prompt),\n\u001b[0m\u001b[0;32m    861\u001b[0m             \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_parent_ident\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    862\u001b[0m             \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_parent_header\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Roaming\\Python\\Python38\\site-packages\\ipykernel\\kernelbase.py\u001b[0m in \u001b[0;36m_input_request\u001b[1;34m(self, prompt, ident, parent, password)\u001b[0m\n\u001b[0;32m    902\u001b[0m             \u001b[1;32mexcept\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    903\u001b[0m                 \u001b[1;31m# re-raise KeyboardInterrupt, to truncate traceback\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 904\u001b[1;33m                 \u001b[1;32mraise\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"Interrupted by user\"\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mfrom\u001b[0m \u001b[1;32mNone\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    905\u001b[0m             \u001b[1;32mexcept\u001b[0m \u001b[0mException\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0me\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    906\u001b[0m                 \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mlog\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mwarning\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"Invalid Message:\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mexc_info\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mTrue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m: Interrupted by user"
     ]
    }
   ],
   "source": [
    "print(\"\\nSelect an option:\")\n",
    "print(\"1) Play the board.\")\n",
    "print(\"2) Nearest neighbor solution.\")\n",
    "print(\"3) Dijkstra solution.\")\n",
    "print(\"4) Ant Colony Optimization solution\")\n",
    "print(\"5) Stop\")\n",
    "userOption = input()\n",
    "while(userOption != \"5\"):\n",
    "        \n",
    "    #I allow the user to play the board themselves.\n",
    "\n",
    "    if (userOption == \"1\"):\n",
    "        currentElement = 0\n",
    "        total = 0\n",
    "        printArray(arraySizeY,arraySizeX,randomArray,currentElement)\n",
    "        while(currentElement != arraySizeX*arraySizeY - 1):\n",
    "            print(\"\\nWhat direction do you want to go?\")\n",
    "            usersinput = input()\n",
    "            if (currentElement >=arraySizeX and usersinput == \"w\"):\n",
    "                total += abs((randomArray[currentElement//arraySizeX][currentElement % arraySizeX]) - \\\n",
    "                    (randomArray[(currentElement-arraySizeX)//arraySizeX][(currentElement-arraySizeX) % arraySizeX]))\n",
    "                currentElement = currentElement - arraySizeX\n",
    "                printArray(arraySizeY,arraySizeX,randomArray,currentElement)\n",
    "            if (currentElement //arraySizeX < arraySizeY -1 and usersinput == \"s\"):\n",
    "                total += abs((randomArray[currentElement//arraySizeX][currentElement % arraySizeX]) - \\\n",
    "                    (randomArray[(currentElement+arraySizeX)//arraySizeX][(currentElement+arraySizeX) % arraySizeX]))\n",
    "                currentElement = currentElement + arraySizeX\n",
    "                printArray(arraySizeY,arraySizeX,randomArray,currentElement)\n",
    "            if (currentElement %arraySizeX > 0) and usersinput == \"a\":\n",
    "                total += abs((randomArray[currentElement//arraySizeX][currentElement % arraySizeX]) - \\\n",
    "                    (randomArray[(currentElement - 1)//arraySizeX][(currentElement - 1) % arraySizeX]))\n",
    "                currentElement = currentElement - 1\n",
    "                printArray(arraySizeY,arraySizeX,randomArray,currentElement)\n",
    "            if (currentElement %arraySizeX < arraySizeX - 1 and usersinput == \"d\"):\n",
    "                total += abs((randomArray[currentElement//arraySizeX][currentElement % arraySizeX]) - \\\n",
    "                    (randomArray[(currentElement + 1)//arraySizeX][(currentElement + 1) % arraySizeX]))\n",
    "                currentElement = currentElement + 1\n",
    "                printArray(arraySizeY,arraySizeX,randomArray,currentElement)\n",
    "        print(\"Total length: \" , total)\n",
    "        \n",
    "    elif (userOption == \"2\"):\n",
    "        neighbor()\n",
    "\n",
    "    elif (userOption == \"3\"):\n",
    "        dijkstra()\n",
    "\n",
    "    elif (userOption == \"4\"):\n",
    "\n",
    "        #Input variables for the user.\n",
    "\n",
    "        print(\"How many ants do you want?\")\n",
    "        numberOfAnts = numberOfCycles = int(input())\n",
    "        print(\"How many cycles do you want?\")\n",
    "        numberOfCycles = int(input())\n",
    "        runAntColony(numberOfAnts,numberOfCycles)\n",
    "\n",
    "    print(\"\\nWould you like to try another action?\")\n",
    "    userOption = input()\n",
    "print(\"Stop\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}