Dojo 1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>Given a matrix of dimension r*c where each cell in the matrix can have values 0, 1 or 2 which has the following meaning:<br>\n",
    "0 : Empty cell<br>\n",
    "1 : Cells have fresh oranges<br>\n",
    "2 : Cells have rotten oranges</p>\n",
    "<p>So, we have to determine what is the minimum time required to rot all oranges. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in unit time. If it is impossible to rot every orange then simply return -1.</p>\n",
    "<p>Input:<br>\n",
    "The first line of input contains an integer T denoting the number of test cases. Each test case contains two integers r and c, where r is the number of rows and c is the number of columns in the array a[]. Next line contains space separated r*c elements each in the array a[].</p>\n",
    "<p>Output:<br>\n",
    "Print an integer which denotes the minimum time taken to rot all the oranges (-1 if it is impossible).</p>\n",
    "<p>Constraints:<br>\n",
    "1 &lt;= T &lt;= 100<br>\n",
    "1 &lt;= r &lt;= 100<br>\n",
    "1 &lt;= c &lt;= 100<br>\n",
    "0 &lt;= a[i] &lt;= 2</p>\n",
    "<p>Example:<br>\n",
    "Input:<br>\n",
    "2<br>\n",
    "3 5<br>\n",
    "2 1 0 2 1 1 0 1 2 1 1 0 0 2 1<br>\n",
    "3 5<br>\n",
    "2 1 0 2 1 0 0 1 2 1 1 0 0 2 1</p>\n",
    "<p>Output:<br>\n",
    "2<br>\n",
    "-1</p>\n",
    "<p>Explanation:<br>\n",
    "Testcase 1:<br>\n",
    "2 | 1 | 0 | 2 | 1<br>\n",
    "1 | 0 | 1 | 2 | 1<br>\n",
    "1 | 0 | 0 | 2 | 1</p>\n",
    "<p>Oranges at positions {0,0}, {0, 3}, {1, 3} and {2, 3} will rot oranges at {0, 1}, {1, 0}, {0, 4}, {1, 2}, {1, 4}, {2, 4} during 1st unit time. And, during 2nd unit time, orange at {1, 0} got rotten and will rot orange at {2, 0}. Hence, total 2 unit of time is required to rot all oranges.</p>\n",
    "<p>Testcase 2:<br>\n",
    "2 | 1 | 0 | 2 | 1<br>\n",
    "0 | 0 | 1 | 2 | 1<br>\n",
    "1 | 0 | 0 | 2 | 1</p>\n",
    "<p>Orange at position {2,0} will not rot as there is no path to it.</p>\n",
    "<hr>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-23T16:03:39.236501Z",
     "start_time": "2019-07-23T16:03:39.083810Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-23T16:03:39.244103Z",
     "start_time": "2019-07-23T16:03:39.240583Z"
    }
   },
   "outputs": [],
   "source": [
    "def get_fresh_oranges():\n",
    "    global matrix_\n",
    "    return list(zip(*np.where(matrix_==1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-23T16:03:39.367298Z",
     "start_time": "2019-07-23T16:03:39.246207Z"
    }
   },
   "outputs": [],
   "source": [
    "def make_orange_rotten(x):\n",
    "    global matrix_\n",
    "    if (x[0]-1)>= 0 and x[1]>= 0 and matrix_[x[0]-1][x[1]]==2:\n",
    "        return True\n",
    "    elif (x[0]+1)<matrix_.shape[0] and x[1]>=0 and matrix_[x[0]+1][x[1]]==2:\n",
    "        return True\n",
    "    elif x[0]>=0 and x[1]-1>= 0 and matrix_[x[0]][x[1]-1]==2:\n",
    "        return True\n",
    "    elif x[0]>=0 and (x[1]+1)<matrix_.shape[1] and matrix_[x[0]][x[1]+1] == 2:\n",
    "        return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-23T16:03:39.474410Z",
     "start_time": "2019-07-23T16:03:39.372301Z"
    }
   },
   "outputs": [],
   "source": [
    "def run():\n",
    "    global matrix_\n",
    "    fresh_oranges = get_fresh_oranges()\n",
    "    time_taken = 0\n",
    "    while fresh_oranges:\n",
    "        updated_indices = []\n",
    "        for tuple_index in fresh_oranges:\n",
    "            if make_orange_rotten(tuple_index):\n",
    "                updated_indices.append(tuple_index)\n",
    "        for x in updated_indices:\n",
    "            matrix_[x[0]][x[1]] = 2\n",
    "        prev_fresh_oranges = fresh_oranges.copy()\n",
    "        fresh_oranges = get_fresh_oranges()\n",
    "        if prev_fresh_oranges == fresh_oranges:\n",
    "            time_taken = -1\n",
    "            break\n",
    "        time_taken += 1\n",
    "    return matrix_, time_taken"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-23T16:03:58.079210Z",
     "start_time": "2019-07-23T16:03:39.477048Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3 5\n",
      "2 1 0 2 1 1 0 1 2 1 1 0 0 2 1\n",
      "Input:\n",
      "[[2 1 0 2 1]\n",
      " [1 0 1 2 1]\n",
      " [1 0 0 2 1]]\n",
      "Output:\n",
      "[[2 2 0 2 2]\n",
      " [2 0 2 2 2]\n",
      " [2 0 0 2 2]]\n",
      "Minimum Time taken:  2\n",
      "\n",
      "3 5\n",
      "2 1 0 2 1 0 0 1 2 1 1 0 0 2 1\n",
      "Input:\n",
      "[[2 1 0 2 1]\n",
      " [0 0 1 2 1]\n",
      " [1 0 0 2 1]]\n",
      "Output:\n",
      "[[2 2 0 2 2]\n",
      " [0 0 2 2 2]\n",
      " [1 0 0 2 2]]\n",
      "Minimum Time taken:  -1\n",
      "\n"
     ]
    }
   ],
   "source": [
    "T = int(input())\n",
    "if 0<T<=100:\n",
    "    for i in range(T):\n",
    "        row, col = (int(x) for x in input().split())\n",
    "        if 0<row<=100 and 0<col<=100:\n",
    "            matrix_ = [int(x) for x in input().split()]\n",
    "            if len([x for x in matrix_ if 0<=x<=2]) == len(matrix_):\n",
    "                print('Input:')\n",
    "                matrix_ = np.reshape(matrix_, (row,col))\n",
    "                print(np.matrix(matrix_))\n",
    "                matrix_, time_taken = run()\n",
    "                print('Output:')\n",
    "                print(np.matrix(matrix_))\n",
    "                print('Minimum Time taken: ', time_taken)\n",
    "                print()\n",
    "            else:\n",
    "                print('Error: matrix_ values must be between 0 and 2')\n",
    "                break\n",
    "        else:\n",
    "            print('Error: Number of Rows and Columns must be between 0 and 100')\n",
    "            break\n",
    "else:\n",
    "    print('Error: Number of test cases must be between 0 and 100')\n",
    "    "
   ]
  }
 ],
 "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.5.2"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}