Exercise Moonlight best algorithm for part e and f.

huikang_ef_code.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%reset -sf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a_example.txt                    f_libraries_of_the_world.txt\r\n",
      "b_read_on.txt                    f_libraries_of_the_world.txt.out\r\n",
      "c_incunabula.txt                 grader.ipynb\r\n",
      "c_incunabula.txt.out             huikang_ef_code.ipynb\r\n",
      "d_tough_choices.txt              order.txt\r\n",
      "e_so_many_books.txt              tyl1.class\r\n",
      "e_so_many_books.txt.out          tyl1.java\r\n"
     ]
    }
   ],
   "source": [
    "!ls\n",
    "# path = \"c_incunabula.txt\"\n",
    "# path = \"e_so_many_books.txt\"\n",
    "path = \"f_libraries_of_the_world.txt\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(path, \"r\") as f:\n",
    "    lines = [w.strip() for w in f.readlines()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_books, num_libraries, num_days = [int(x) for x in lines[0].split()]\n",
    "books = [int(x) for x in lines[1].split()] # scores\n",
    "books2 = [int(x) for x in lines[1].split()]\n",
    "\n",
    "signups = []\n",
    "ships = []\n",
    "books_avail_arr = []\n",
    "\n",
    "for lib_info, x_info in zip(lines[2::2], lines[3::2]):\n",
    "    _, signup, ship = [int(x) for x in lib_info.split()]\n",
    "    books_avail = [int(x) for x in x_info.split()]\n",
    "    signups.append(signup)\n",
    "    ships.append(ship)\n",
    "    books_avail_arr.append(books_avail)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "40111142\n"
     ]
    }
   ],
   "source": [
    "# stats\n",
    "print(sum(books))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# consolidated data\n",
    "\n",
    "# book scores\n",
    "books\n",
    "\n",
    "# for each library\n",
    "signups # duration to signup\n",
    "ships # ship time\n",
    "books_avail_arr # books_id\n",
    "\n",
    "pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def library_scoring(idd, days_left=0):\n",
    "    signup = signups[idd]\n",
    "    ship = ships[idd]\n",
    "    books_avail = books_avail_arr[idd]\n",
    "\n",
    "    book_scores = [books2[bid] for bid in books_avail]\n",
    "    book_scores = sorted(book_scores)[::-1]\n",
    "    \n",
    "    book_scores = book_scores[:min(len(book_scores), max(0, ship*(days_left - signup)))]    \n",
    "\n",
    "    return -18.5*signup + sum(book_scores)/150"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "873"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(books_avail_arr[602])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "31 2024 204 | 66 1795 694 | 107 1758 719 | 137 1662 210 | 182 1622 901 | 227 1605 774 | 275 1576 422 | 326 1521 672 | 375 1464 622 | 426 1379 147 | 466 1341 618 | 503 1263 595 | 543 1174 312 | 585 1128 828 | b 622 1029 369 | b 654 685 454 | b 684 -83 431 | b 715 -573 960 | "
     ]
    }
   ],
   "source": [
    "day = 0\n",
    "libs = []\n",
    "libs_set = {}\n",
    "while day < num_days:\n",
    "    lib_scores = [(library_scoring(idx, num_days-day),idx) for idx in range(num_libraries) if idx not in libs_set]\n",
    "    lib_scores = sorted(lib_scores)[::-1][0]\n",
    "    next_lib = lib_scores[1]\n",
    "    libs_set[next_lib] = \"booked\"\n",
    "    libs.append(next_lib)\n",
    "    \n",
    "    counter = (num_days-day-signups[next_lib])*ships[next_lib]\n",
    "    for bk in books_avail_arr[next_lib]:\n",
    "        books2[bk] = 0\n",
    "        counter -= 1\n",
    "        if counter <= 0:\n",
    "            print(\"b\", end=\" \")\n",
    "            break\n",
    "    \n",
    "    day += signups[next_lib]\n",
    "    print(day, int(lib_scores[0]), lib_scores[1], end=\" | \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18\n"
     ]
    }
   ],
   "source": [
    "order = libs\n",
    "print(len(order))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"order.txt\", \"w\") as f:\n",
    "    f.write(str(len(order)))\n",
    "    f.write(\"\\n\")\n",
    "    f.write(\"\\n\".join([str(s) for s in order]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "scanned = set()\n",
    "\n",
    "strr = []\n",
    "def output(line):\n",
    "    strr.append(str(line))\n",
    "\n",
    "output(len(order))\n",
    "for idd in order:\n",
    "    book_list = []\n",
    "    reorder = [idd for score,idd in sorted([[books[idd], idd] for idd in books_avail_arr[idd]])[::-1]]\n",
    "    for book in reorder:\n",
    "        if book not in scanned:\n",
    "            book_list.append(book)\n",
    "            scanned.add(book)\n",
    "    output(str(idd) + \" \" + str(len(book_list)))\n",
    "    output(\" \".join([str(x) for x in book_list]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(path+\".out\", \"w\") as f:\n",
    "    f.write(\"\\n\".join(strr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !javac tyl1.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !java tyl1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !head output1.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !cat f_libraries_of_the_world.txt.out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !cat f_libraries_of_the_world.txt.out"
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}