Created
May 23, 2018 10:03
-
-
Save Z30G0D/fbc593f0a616bfba43b90a1f6baa3e86 to your computer and use it in GitHub Desktop.
for medecide
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"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