Practice_Question_Code.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Google Hashcode 2021, Practice Problem\n",
    "###       Even More Pizza\n",
    "\n",
    "#### By <a href=\"https://chaudharyhamdan.me/\">Chaudhary Hamdan </a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import of libraries\n",
    "import os\n",
    "import random\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Reading file names in the Input directory \n",
    "files = os.listdir('Input_Files/')\n",
    "l = len(files)\n",
    "\n",
    "# Cleaning file names\n",
    "for i in range(l):\n",
    "    files[i] = files[i][:-3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function to compute and return Answers.\n",
    "def solve(m,t2,t3,t4,ing,shuff):\n",
    "    i,score = 0, 0\n",
    "    \n",
    "    # Shuffling Data to get optimized result\n",
    "    random.shuffle(shuff)\n",
    "    \n",
    "    tt,ttt,tttt = [],[],[]\n",
    "    \n",
    "    # While we have some pizzas left\n",
    "    while i < m:\n",
    "        \n",
    "        # If 2 member team is still left and we have pizza to deliver them\n",
    "        if i+2 <= m and t2 > 0:\n",
    "            t2 -= 2 # Updating after delivering it to a team\n",
    "            tt.append([shuff[i],shuff[i+1]]) # Appending to the answer\n",
    "            ss = len(set(ing[shuff[i]]+ing[shuff[i+1]])) # Unique Ingredients delivered\n",
    "            i += 2 # 2 pizzas Delivered.\n",
    "        \n",
    "        elif i+3 <= m and t3 > 0:\n",
    "            t3 -= 3\n",
    "            ttt.append([shuff[i],shuff[i+1],shuff[i+2]])\n",
    "            ss = len(set(ing[shuff[i]]+ing[shuff[i+1]]+ing[shuff[i+2]]))\n",
    "            i += 3\n",
    "        \n",
    "        elif i+4 <= m and t4 > 0:\n",
    "            t4 -= 4\n",
    "            tttt.append([shuff[i],shuff[i+1],shuff[i+2],shuff[i+3]])\n",
    "            ss = len(set(ing[shuff[i]]+ing[shuff[i+1]]+ing[shuff[i+2]]+ing[shuff[i+3]]))\n",
    "            i += 4\n",
    "        \n",
    "        # If no team is left or we don't have sufficient pizzas, Break loop\n",
    "        else:\n",
    "            break\n",
    "        \n",
    "        # Score Calculation\n",
    "        score += ss**2\n",
    "        \n",
    "    # Returning the vals computed\n",
    "    return len(tt),len(ttt),len(tttt),tt,ttt,tttt,score \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Done  a_example \n",
      "Score : 74\n",
      "Done  b_little_bit_of_everything \n",
      "Score : 8082\n",
      "Done  c_many_ingredients \n",
      "Score : 227495849\n",
      "Done  d_many_pizzas \n",
      "Score : 1529471\n",
      "Done  e_many_teams \n",
      "Score : 4475329\n",
      "All Done\n"
     ]
    }
   ],
   "source": [
    "\n",
    "# Loop to iterate through all input files\n",
    "for i in range(l):\n",
    "    \n",
    "    # Opening files\n",
    "    with open('Input_Files/'+files[i]+'.in', 'r') as f:\n",
    "        \n",
    "        # Reading contents\n",
    "        content = f.readlines()\n",
    "        ingredients = []\n",
    "        m, t2, t3, t4 = [int(x) for x in content[0].split()]\n",
    "        for j in range(1,m+1):\n",
    "            \n",
    "            # Ingredients in the pizza\n",
    "            ingredient = content[j].split()[1:]\n",
    "            ingredients.append((ingredient))\n",
    "    \n",
    "    bestscore = 0\n",
    "    besttwo,bestthree,bestfour = [],[],[]\n",
    "    vals = list(range(m))\n",
    "    \n",
    "    # Get best score out of 1000 (increase for better answers) iterations.\n",
    "    for _ in range(10000):\n",
    "        l2,l3,l4,two,three,four,score = solve(m,2*t2,3*t3,4*t4,ingredients,vals)\n",
    "        \n",
    "        # Comparing with the best score till now.\n",
    "        if score > bestscore:\n",
    "            bestscore,besttwo,bestthree,bestfour = score,two,three,four\n",
    "\n",
    "    # Writing the best results to output files in Output Directory.\n",
    "    with open('Output_Files/'+files[i]+'.out', 'w') as f:\n",
    "        f.write(str(l2+l3+l4)+'\\n')\n",
    "        \n",
    "        # Writing in proper format as mentioned in the question\n",
    "        for ii in range(l2):\n",
    "            f.write('2 ')\n",
    "            for j in range(2):\n",
    "                f.write(str(besttwo[ii][j])+' ')\n",
    "            f.write('\\n')\n",
    "        for ii in range(l3):\n",
    "            f.write('3 ')\n",
    "            for j in range(3):\n",
    "                f.write(str(bestthree[ii][j])+' ')\n",
    "            f.write('\\n')\n",
    "        for ii in range(l4):\n",
    "            f.write('4 ')\n",
    "            for j in range(4):\n",
    "                f.write(str(bestfour[ii][j])+' ')\n",
    "            f.write('\\n')\n",
    "    \n",
    "    # Printing to Terminal to get the progress.\n",
    "    print(\"Done \",files[i],\"\\nScore :\",bestscore)\n",
    "    \n",
    "# Printing for 'THE END'.\n",
    "print(\"All Done\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Thank You"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}