Skip to content

Instantly share code, notes, and snippets.

@Z30G0D
Created May 23, 2018 10:03
Show Gist options
  • Save Z30G0D/fbc593f0a616bfba43b90a1f6baa3e86 to your computer and use it in GitHub Desktop.
Save Z30G0D/fbc593f0a616bfba43b90a1f6baa3e86 to your computer and use it in GitHub Desktop.
for medecide
{
"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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment