API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jul 23rd, 2019
158
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 15.78 KB | None | 0 0
raw download clone embed print report
  1. {
  2. "cells": [
  3. {
  4. "cell_type": "code",
  5. "execution_count": 1,
  6. "metadata": {},
  7. "outputs": [],
  8. "source": [
  9. "class Kid:\n",
  10. " def __init__(self, name, sport, camp=None):\n",
  11. " self.name = name\n",
  12. " self.sport = sport\n",
  13. " self.camp = camp\n",
  14. "\n",
  15. "class Camp:\n",
  16. " def __init__(self, name, sports):\n",
  17. " self.name = name\n",
  18. " self.sports = sports\n",
  19. " self.open_spots = 3\n",
  20. "\n",
  21. "kids = [\n",
  22. " Kid('Ben', 'Baseball'),\n",
  23. " Kid('John', 'Baseball'),\n",
  24. " Kid('Tom', 'Baseball'),\n",
  25. " Kid('Chris', 'Soccer'),\n",
  26. " Kid('Josh', 'Soccer'),\n",
  27. " Kid('Alan', 'Basketball'),\n",
  28. " Kid('Timmy', 'Basketball'),\n",
  29. " Kid('Greg', 'Tennis'),\n",
  30. "]\n",
  31. "\n",
  32. "camps = [\n",
  33. " Camp('Cool Camp', ['Baseball', 'Soccer']),\n",
  34. " Camp('Fun Camp', ['Baseball']),\n",
  35. " Camp('Super Camp', ['Basketball']),\n",
  36. " Camp('Sporty Camp', ['Basketball']),\n",
  37. "]\n",
  38. "\n",
  39. "expected_answer = {\n",
  40. " 'Ben': 'Cool Camp',\n",
  41. " 'John': 'Fun Camp',\n",
  42. " 'Tom': 'Fun Camp',\n",
  43. " 'Chris': 'Cool Camp',\n",
  44. " 'Josh': 'Cool Camp',\n",
  45. " 'Alan': 'Super Camp',\n",
  46. " 'Timmy': 'Sporty Camp',\n",
  47. " 'Greg': None,\n",
  48. "}\n"
  49. ]
  50. },
  51. {
  52. "cell_type": "code",
  53. "execution_count": 2,
  54. "metadata": {},
  55. "outputs": [],
  56. "source": [
  57. "import pandas as pd\n",
  58. "import pulp"
  59. ]
  60. },
  61. {
  62. "cell_type": "code",
  63. "execution_count": 3,
  64. "metadata": {},
  65. "outputs": [],
  66. "source": [
  67. "kids_by_name = {\n",
  68. " kid.name: kid for kid in kids\n",
  69. "}\n",
  70. "camps_by_name = {\n",
  71. " camp.name: camp for camp in camps\n",
  72. "}"
  73. ]
  74. },
  75. {
  76. "cell_type": "code",
  77. "execution_count": 4,
  78. "metadata": {},
  79. "outputs": [],
  80. "source": [
  81. "kids_names = list(kids_by_name)\n",
  82. "camps_names = list(camps_by_name)"
  83. ]
  84. },
  85. {
  86. "cell_type": "code",
  87. "execution_count": 5,
  88. "metadata": {},
  89. "outputs": [
  90. {
  91. "data": {
  92. "text/html": [
  93. "<div>\n",
  94. "<style scoped>\n",
  95. " .dataframe tbody tr th:only-of-type {\n",
  96. " vertical-align: middle;\n",
  97. " }\n",
  98. "\n",
  99. " .dataframe tbody tr th {\n",
  100. " vertical-align: top;\n",
  101. " }\n",
  102. "\n",
  103. " .dataframe thead th {\n",
  104. " text-align: right;\n",
  105. " }\n",
  106. "</style>\n",
  107. "<table border=\"1\" class=\"dataframe\">\n",
  108. " <thead>\n",
  109. " <tr style=\"text-align: right;\">\n",
  110. " <th></th>\n",
  111. " <th>Cool Camp</th>\n",
  112. " <th>Fun Camp</th>\n",
  113. " <th>Super Camp</th>\n",
  114. " <th>Sporty Camp</th>\n",
  115. " </tr>\n",
  116. " </thead>\n",
  117. " <tbody>\n",
  118. " <tr>\n",
  119. " <th>Ben</th>\n",
  120. " <td>Ben|Cool_Camp</td>\n",
  121. " <td>Ben|Fun_Camp</td>\n",
  122. " <td>Ben|Super_Camp</td>\n",
  123. " <td>Ben|Sporty_Camp</td>\n",
  124. " </tr>\n",
  125. " <tr>\n",
  126. " <th>John</th>\n",
  127. " <td>John|Cool_Camp</td>\n",
  128. " <td>John|Fun_Camp</td>\n",
  129. " <td>John|Super_Camp</td>\n",
  130. " <td>John|Sporty_Camp</td>\n",
  131. " </tr>\n",
  132. " <tr>\n",
  133. " <th>Tom</th>\n",
  134. " <td>Tom|Cool_Camp</td>\n",
  135. " <td>Tom|Fun_Camp</td>\n",
  136. " <td>Tom|Super_Camp</td>\n",
  137. " <td>Tom|Sporty_Camp</td>\n",
  138. " </tr>\n",
  139. " <tr>\n",
  140. " <th>Chris</th>\n",
  141. " <td>Chris|Cool_Camp</td>\n",
  142. " <td>Chris|Fun_Camp</td>\n",
  143. " <td>Chris|Super_Camp</td>\n",
  144. " <td>Chris|Sporty_Camp</td>\n",
  145. " </tr>\n",
  146. " <tr>\n",
  147. " <th>Josh</th>\n",
  148. " <td>Josh|Cool_Camp</td>\n",
  149. " <td>Josh|Fun_Camp</td>\n",
  150. " <td>Josh|Super_Camp</td>\n",
  151. " <td>Josh|Sporty_Camp</td>\n",
  152. " </tr>\n",
  153. " <tr>\n",
  154. " <th>Alan</th>\n",
  155. " <td>Alan|Cool_Camp</td>\n",
  156. " <td>Alan|Fun_Camp</td>\n",
  157. " <td>Alan|Super_Camp</td>\n",
  158. " <td>Alan|Sporty_Camp</td>\n",
  159. " </tr>\n",
  160. " <tr>\n",
  161. " <th>Timmy</th>\n",
  162. " <td>Timmy|Cool_Camp</td>\n",
  163. " <td>Timmy|Fun_Camp</td>\n",
  164. " <td>Timmy|Super_Camp</td>\n",
  165. " <td>Timmy|Sporty_Camp</td>\n",
  166. " </tr>\n",
  167. " <tr>\n",
  168. " <th>Greg</th>\n",
  169. " <td>Greg|Cool_Camp</td>\n",
  170. " <td>Greg|Fun_Camp</td>\n",
  171. " <td>Greg|Super_Camp</td>\n",
  172. " <td>Greg|Sporty_Camp</td>\n",
  173. " </tr>\n",
  174. " </tbody>\n",
  175. "</table>\n",
  176. "</div>"
  177. ],
  178. "text/plain": [
  179. " Cool Camp Fun Camp Super Camp Sporty Camp\n",
  180. "Ben Ben|Cool_Camp Ben|Fun_Camp Ben|Super_Camp Ben|Sporty_Camp\n",
  181. "John John|Cool_Camp John|Fun_Camp John|Super_Camp John|Sporty_Camp\n",
  182. "Tom Tom|Cool_Camp Tom|Fun_Camp Tom|Super_Camp Tom|Sporty_Camp\n",
  183. "Chris Chris|Cool_Camp Chris|Fun_Camp Chris|Super_Camp Chris|Sporty_Camp\n",
  184. "Josh Josh|Cool_Camp Josh|Fun_Camp Josh|Super_Camp Josh|Sporty_Camp\n",
  185. "Alan Alan|Cool_Camp Alan|Fun_Camp Alan|Super_Camp Alan|Sporty_Camp\n",
  186. "Timmy Timmy|Cool_Camp Timmy|Fun_Camp Timmy|Super_Camp Timmy|Sporty_Camp\n",
  187. "Greg Greg|Cool_Camp Greg|Fun_Camp Greg|Super_Camp Greg|Sporty_Camp"
  188. ]
  189. },
  190. "execution_count": 5,
  191. "metadata": {},
  192. "output_type": "execute_result"
  193. }
  194. ],
  195. "source": [
  196. "variables = pd.DataFrame(\n",
  197. " [\n",
  198. " [pulp.LpVariable(f'{kid}|{camp}', 0, 1) for camp in camps_names]\n",
  199. " for kid in kids_names\n",
  200. " ],\n",
  201. " index=kids_names, columns=camps_names,\n",
  202. ")\n",
  203. "variables"
  204. ]
  205. },
  206. {
  207. "cell_type": "code",
  208. "execution_count": 6,
  209. "metadata": {},
  210. "outputs": [
  211. {
  212. "data": {
  213. "text/html": [
  214. "<div>\n",
  215. "<style scoped>\n",
  216. " .dataframe tbody tr th:only-of-type {\n",
  217. " vertical-align: middle;\n",
  218. " }\n",
  219. "\n",
  220. " .dataframe tbody tr th {\n",
  221. " vertical-align: top;\n",
  222. " }\n",
  223. "\n",
  224. " .dataframe thead th {\n",
  225. " text-align: right;\n",
  226. " }\n",
  227. "</style>\n",
  228. "<table border=\"1\" class=\"dataframe\">\n",
  229. " <thead>\n",
  230. " <tr style=\"text-align: right;\">\n",
  231. " <th></th>\n",
  232. " <th>Cool Camp</th>\n",
  233. " <th>Fun Camp</th>\n",
  234. " <th>Super Camp</th>\n",
  235. " <th>Sporty Camp</th>\n",
  236. " </tr>\n",
  237. " </thead>\n",
  238. " <tbody>\n",
  239. " <tr>\n",
  240. " <th>Ben</th>\n",
  241. " <td>1</td>\n",
  242. " <td>1</td>\n",
  243. " <td>0</td>\n",
  244. " <td>0</td>\n",
  245. " </tr>\n",
  246. " <tr>\n",
  247. " <th>John</th>\n",
  248. " <td>1</td>\n",
  249. " <td>1</td>\n",
  250. " <td>0</td>\n",
  251. " <td>0</td>\n",
  252. " </tr>\n",
  253. " <tr>\n",
  254. " <th>Tom</th>\n",
  255. " <td>1</td>\n",
  256. " <td>1</td>\n",
  257. " <td>0</td>\n",
  258. " <td>0</td>\n",
  259. " </tr>\n",
  260. " <tr>\n",
  261. " <th>Chris</th>\n",
  262. " <td>1</td>\n",
  263. " <td>0</td>\n",
  264. " <td>0</td>\n",
  265. " <td>0</td>\n",
  266. " </tr>\n",
  267. " <tr>\n",
  268. " <th>Josh</th>\n",
  269. " <td>1</td>\n",
  270. " <td>0</td>\n",
  271. " <td>0</td>\n",
  272. " <td>0</td>\n",
  273. " </tr>\n",
  274. " <tr>\n",
  275. " <th>Alan</th>\n",
  276. " <td>0</td>\n",
  277. " <td>0</td>\n",
  278. " <td>1</td>\n",
  279. " <td>1</td>\n",
  280. " </tr>\n",
  281. " <tr>\n",
  282. " <th>Timmy</th>\n",
  283. " <td>0</td>\n",
  284. " <td>0</td>\n",
  285. " <td>1</td>\n",
  286. " <td>1</td>\n",
  287. " </tr>\n",
  288. " <tr>\n",
  289. " <th>Greg</th>\n",
  290. " <td>0</td>\n",
  291. " <td>0</td>\n",
  292. " <td>0</td>\n",
  293. " <td>0</td>\n",
  294. " </tr>\n",
  295. " </tbody>\n",
  296. "</table>\n",
  297. "</div>"
  298. ],
  299. "text/plain": [
  300. " Cool Camp Fun Camp Super Camp Sporty Camp\n",
  301. "Ben 1 1 0 0\n",
  302. "John 1 1 0 0\n",
  303. "Tom 1 1 0 0\n",
  304. "Chris 1 0 0 0\n",
  305. "Josh 1 0 0 0\n",
  306. "Alan 0 0 1 1\n",
  307. "Timmy 0 0 1 1\n",
  308. "Greg 0 0 0 0"
  309. ]
  310. },
  311. "execution_count": 6,
  312. "metadata": {},
  313. "output_type": "execute_result"
  314. }
  315. ],
  316. "source": [
  317. "possible_assignments = pd.DataFrame(\n",
  318. " [\n",
  319. " [1 if kids_by_name[kid].sport in camps_by_name[camp].sports else 0\n",
  320. " for camp in camps_names]\n",
  321. " for kid in kids_names\n",
  322. " ],\n",
  323. " index=kids_names, columns=camps_names,\n",
  324. ")\n",
  325. "possible_assignments"
  326. ]
  327. },
  328. {
  329. "cell_type": "code",
  330. "execution_count": 7,
  331. "metadata": {},
  332. "outputs": [],
  333. "source": [
  334. "problem = pulp.LpProblem('Camp Assignment', sense=pulp.LpMaximize)"
  335. ]
  336. },
  337. {
  338. "cell_type": "code",
  339. "execution_count": 8,
  340. "metadata": {},
  341. "outputs": [],
  342. "source": [
  343. "# Objective\n",
  344. "problem += variables.sum().sum(), 'Maximize number of kids going to camp'"
  345. ]
  346. },
  347. {
  348. "cell_type": "code",
  349. "execution_count": 9,
  350. "metadata": {},
  351. "outputs": [],
  352. "source": [
  353. "# Only one camp per kid\n",
  354. "for kid in kids_names:\n",
  355. " problem += variables.loc[kid, :].sum() <= 1, f'Only 1 camp per kid ({kid})'\n",
  356. " \n",
  357. "# Limited number of spots per camp\n",
  358. "for camp in camps_names:\n",
  359. " spots = camps_by_name[camp].open_spots\n",
  360. " problem += variables.loc[:, camp].sum() <= spots, f'Only {spots} spots in {camp}'\n",
  361. " \n",
  362. "# Only go if favorite sport is available\n",
  363. "problem += possible_assignments.eq(0).multiply(variables).sum().sum() == 0, 'Only go if favorite sport is available'"
  364. ]
  365. },
  366. {
  367. "cell_type": "code",
  368. "execution_count": 10,
  369. "metadata": {},
  370. "outputs": [
  371. {
  372. "data": {
  373. "text/plain": [
  374. "1"
  375. ]
  376. },
  377. "execution_count": 10,
  378. "metadata": {},
  379. "output_type": "execute_result"
  380. }
  381. ],
  382. "source": [
  383. "# Solve the problem\n",
  384. "problem.solve()"
  385. ]
  386. },
  387. {
  388. "cell_type": "code",
  389. "execution_count": 11,
  390. "metadata": {},
  391. "outputs": [
  392. {
  393. "data": {
  394. "text/html": [
  395. "<div>\n",
  396. "<style scoped>\n",
  397. " .dataframe tbody tr th:only-of-type {\n",
  398. " vertical-align: middle;\n",
  399. " }\n",
  400. "\n",
  401. " .dataframe tbody tr th {\n",
  402. " vertical-align: top;\n",
  403. " }\n",
  404. "\n",
  405. " .dataframe thead th {\n",
  406. " text-align: right;\n",
  407. " }\n",
  408. "</style>\n",
  409. "<table border=\"1\" class=\"dataframe\">\n",
  410. " <thead>\n",
  411. " <tr style=\"text-align: right;\">\n",
  412. " <th></th>\n",
  413. " <th>Cool Camp</th>\n",
  414. " <th>Fun Camp</th>\n",
  415. " <th>Super Camp</th>\n",
  416. " <th>Sporty Camp</th>\n",
  417. " </tr>\n",
  418. " </thead>\n",
  419. " <tbody>\n",
  420. " <tr>\n",
  421. " <th>Ben</th>\n",
  422. " <td>True</td>\n",
  423. " <td>False</td>\n",
  424. " <td>False</td>\n",
  425. " <td>False</td>\n",
  426. " </tr>\n",
  427. " <tr>\n",
  428. " <th>John</th>\n",
  429. " <td>False</td>\n",
  430. " <td>True</td>\n",
  431. " <td>False</td>\n",
  432. " <td>False</td>\n",
  433. " </tr>\n",
  434. " <tr>\n",
  435. " <th>Tom</th>\n",
  436. " <td>False</td>\n",
  437. " <td>True</td>\n",
  438. " <td>False</td>\n",
  439. " <td>False</td>\n",
  440. " </tr>\n",
  441. " <tr>\n",
  442. " <th>Chris</th>\n",
  443. " <td>True</td>\n",
  444. " <td>False</td>\n",
  445. " <td>False</td>\n",
  446. " <td>False</td>\n",
  447. " </tr>\n",
  448. " <tr>\n",
  449. " <th>Josh</th>\n",
  450. " <td>True</td>\n",
  451. " <td>False</td>\n",
  452. " <td>False</td>\n",
  453. " <td>False</td>\n",
  454. " </tr>\n",
  455. " <tr>\n",
  456. " <th>Alan</th>\n",
  457. " <td>False</td>\n",
  458. " <td>False</td>\n",
  459. " <td>True</td>\n",
  460. " <td>False</td>\n",
  461. " </tr>\n",
  462. " <tr>\n",
  463. " <th>Timmy</th>\n",
  464. " <td>False</td>\n",
  465. " <td>False</td>\n",
  466. " <td>False</td>\n",
  467. " <td>True</td>\n",
  468. " </tr>\n",
  469. " <tr>\n",
  470. " <th>Greg</th>\n",
  471. " <td>False</td>\n",
  472. " <td>False</td>\n",
  473. " <td>False</td>\n",
  474. " <td>False</td>\n",
  475. " </tr>\n",
  476. " </tbody>\n",
  477. "</table>\n",
  478. "</div>"
  479. ],
  480. "text/plain": [
  481. " Cool Camp Fun Camp Super Camp Sporty Camp\n",
  482. "Ben True False False False\n",
  483. "John False True False False\n",
  484. "Tom False True False False\n",
  485. "Chris True False False False\n",
  486. "Josh True False False False\n",
  487. "Alan False False True False\n",
  488. "Timmy False False False True\n",
  489. "Greg False False False False"
  490. ]
  491. },
  492. "execution_count": 11,
  493. "metadata": {},
  494. "output_type": "execute_result"
  495. }
  496. ],
  497. "source": [
  498. "# Extract solution\n",
  499. "assignments = variables.applymap(lambda x: x.value()).astype(bool)\n",
  500. "assignments"
  501. ]
  502. },
  503. {
  504. "cell_type": "code",
  505. "execution_count": 12,
  506. "metadata": {},
  507. "outputs": [
  508. {
  509. "data": {
  510. "text/plain": [
  511. "{'Ben': 'Cool Camp',\n",
  512. " 'John': 'Fun Camp',\n",
  513. " 'Tom': 'Fun Camp',\n",
  514. " 'Chris': 'Cool Camp',\n",
  515. " 'Josh': 'Cool Camp',\n",
  516. " 'Alan': 'Super Camp',\n",
  517. " 'Timmy': 'Sporty Camp',\n",
  518. " 'Greg': None}"
  519. ]
  520. },
  521. "execution_count": 12,
  522. "metadata": {},
  523. "output_type": "execute_result"
  524. }
  525. ],
  526. "source": [
  527. "# Get solution to preferred format\n",
  528. "answer = {\n",
  529. " kid: next((camp for camp, is_assigned in row.items() if is_assigned), None)\n",
  530. " for kid, row in assignments.iterrows() \n",
  531. "}\n",
  532. "answer"
  533. ]
  534. },
  535. {
  536. "cell_type": "code",
  537. "execution_count": 13,
  538. "metadata": {},
  539. "outputs": [
  540. {
  541. "data": {
  542. "text/plain": [
  543. "True"
  544. ]
  545. },
  546. "execution_count": 13,
  547. "metadata": {},
  548. "output_type": "execute_result"
  549. }
  550. ],
  551. "source": [
  552. "answer == expected_answer"
  553. ]
  554. }
  555. ],
  556. "metadata": {
  557. "kernelspec": {
  558. "display_name": "Python 3",
  559. "language": "python",
  560. "name": "python3"
  561. },
  562. "language_info": {
  563. "codemirror_mode": {
  564. "name": "ipython",
  565. "version": 3
  566. },
  567. "file_extension": ".py",
  568. "mimetype": "text/x-python",
  569. "name": "python",
  570. "nbconvert_exporter": "python",
  571. "pygments_lexer": "ipython3",
  572. "version": "3.7.3"
  573. }
  574. },
  575. "nbformat": 4,
  576. "nbformat_minor": 2
  577. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!