{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Finding highest amount of diamonds\n",
    "## Job interview exercise for Medecide"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The maximum amount of diamonds are determined by a recursive function as depicted in \"maxdiamonds\" function.<br>\n",
    "The function also keeps documentation of the amount of diamonds collected in a numpy array \"path\" for backtracking through the recursive path later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def maxdiamonds(A, m, n):\n",
    "    if n > 2 or m > 2:\n",
    "        return -1\n",
    "    elif (m == 2 and n == 2):\n",
    "        return A[m][n] \n",
    "    else:\n",
    "        temp =   max( maxdiamonds(A, m+1, n),maxdiamonds(A, m, n+1))\n",
    "        path[m,n] = A[m][n] + temp #documentation for backtracking the path\n",
    "        return A[m][n] + temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of Diamonds collected : 30\n"
     ]
    }
   ],
   "source": [
    "A = [[1, 2, 3],[15, 4, 7],[0, 0, 3]]\n",
    "path = np.zeros((3,3))\n",
    "print('Number of Diamonds collected :',maxdiamonds(A, 0, 0))\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A greedy algorithm could be easily used in order to find the path with the highest amount of diamonds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path of collected diamonds:\n",
      "0 0\n",
      "1 0\n",
      "1 1\n",
      "1 2\n",
      "2 2\n"
     ]
    }
   ],
   "source": [
    "i,j=0,0\n",
    "print('Path of collected diamonds:')\n",
    "print(i,j)\n",
    "while (i!=2) or (j!=2):\n",
    "    if i==2:\n",
    "        j+=1\n",
    "        print(i,j)\n",
    "        continue\n",
    "    if j==2:\n",
    "        i+=1\n",
    "        print(i,j)\n",
    "        continue\n",
    "    if (path[i,j]-path[i+1,j])<(path[i,j]-path[i,j+1]):\n",
    "        i+=1\n",
    "        print(i,j)\n",
    "    else:\n",
    "        j+=1\n",
    "        print(i,j)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "どうもありがとうございます！"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python (myenv)",
   "language": "python",
   "name": "myenv"
  },
  "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}