notebook/Solve.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2586b112",
   "metadata": {},
   "source": [
    "# 2022 hash code practice problem - One Pizza"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7ef5a96a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import os"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "bfe13cd4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# scoring function\n",
    "# param: a list of ingredients\n",
    "# return: score\n",
    "def score(ingredients, likes, dislikes):\n",
    "    ret = 0\n",
    "    for like, dislike in zip(likes, dislikes):\n",
    "        like = like.split()[1:]\n",
    "        \n",
    "        fail = False\n",
    "        for ing in like:\n",
    "            if ing not in ingredients:\n",
    "                fail = True\n",
    "                break\n",
    "        \n",
    "        if not fail:\n",
    "            dislike = dislike.split()[1:]\n",
    "            for ing in dislike:\n",
    "                if ing in ingredients:\n",
    "                    fail = True\n",
    "                    break\n",
    "        if not fail:\n",
    "            ret += 1\n",
    "\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0a88d63",
   "metadata": {},
   "source": [
    "## 1) Read input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6736cc13",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "../inputs/a_an_example.in.txt\n",
      "total people:  3\n"
     ]
    }
   ],
   "source": [
    "iroot = '../inputs'\n",
    "oroot = '../outputs'\n",
    "inputs = sorted(os.listdir('../inputs'))\n",
    "inputN = 0\n",
    "\n",
    "print(os.path.join(iroot, inputs[inputN]))\n",
    "with open(os.path.join(iroot, inputs[inputN])) as f:\n",
    "    in_lines = f.read().splitlines()\n",
    "\n",
    "print('total people: ', in_lines[0])\n",
    "#for K in range(0,100):\n",
    "C = int(in_lines[0])\n",
    "\n",
    "likes = in_lines[1:][::2]\n",
    "dislikes = in_lines[1:][1::2]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b8a2c96",
   "metadata": {},
   "source": [
    "## 2) Processing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "04be84c3",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "like_dic = dict()\n",
    "dislike_dic = dict()\n",
    "\n",
    "for like in likes:\n",
    "    like = like.split()\n",
    "    for i in like[1:]:\n",
    "        if i in like_dic:\n",
    "            like_dic[i] += 1\n",
    "        else:\n",
    "            like_dic[i] = 1\n",
    "\n",
    "for dislike in dislikes:\n",
    "    dislike = dislike.split()\n",
    "    for i in dislike[1:]:\n",
    "        if i in dislike_dic:\n",
    "            dislike_dic[i] += 1\n",
    "        else:\n",
    "            dislike_dic[i] = 1\n",
    "            \n",
    "diff_dic = dict()\n",
    "for key, val in dislike_dic.items():\n",
    "    if key in like_dic:\n",
    "        diff_dic[key] = like_dic[key] - val\n",
    "    else:\n",
    "        diff_dic[key] = 0 - val\n",
    "            \n",
    "sorted_likes = sorted(like_dic.items(), key=lambda item: item[1], reverse=True)\n",
    "sorted_dislikes = sorted(dislike_dic.items(), key=lambda item: item[1], reverse=True)\n",
    "sorted_diff = sorted(diff_dic.items(), key=lambda item: item[1])\n",
    "\n",
    "selected_ingredients = [ i[0] for i in sorted_likes]\n",
    "all_ing = [ i[0] for i in sorted_likes]\n",
    "\n",
    "for name, count in sorted_diff:\n",
    "    if count < 0:\n",
    "        if name in selected_ingredients:\n",
    "            selected_ingredients.remove(name)\n",
    "    else:\n",
    "        break\n",
    "\n",
    "\"\"\"\n",
    "for name, count in sorted_dislikes:\n",
    "    if count > K:\n",
    "        if name in selected_ingredients:\n",
    "            selected_ingredients.remove(name)\n",
    "    else:\n",
    "        break\n",
    "\"\"\"\n",
    "print(score(selected_ingredients, likes, dislikes))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8fecffe",
   "metadata": {},
   "source": [
    "## 3) first optimisation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "534641e8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# fine-tune\n",
    "for k in range(1):\n",
    "    max_score = 0\n",
    "    for i in all_ing:\n",
    "        tmp = selected_ingredients.copy()\n",
    "        if i in tmp:\n",
    "            tmp.remove(i)\n",
    "        else:\n",
    "            tmp.append(i)\n",
    "\n",
    "        tmp_score = score(tmp, likes, dislikes)\n",
    "        print(tmp_score)\n",
    "        if tmp_score > max_score:\n",
    "            max_score = tmp_score\n",
    "            selected_ingredients = tmp.copy()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb76250f",
   "metadata": {},
   "source": [
    "## 4) write output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "3803533f",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(os.path.join(oroot, inputs[inputN]), 'w') as f:\n",
    "    f.write(f'{len(selected_ingredients)}')\n",
    "    for ing in selected_ingredients:\n",
    "        f.write(f' {ing}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d28afdf8",
   "metadata": {},
   "source": [
    "## 5) Scoring"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "756eae2c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a_an_example.in.txt 3 1\n",
      "b_basic.in.txt 5 5\n",
      "c_coarse.in.txt 10 5\n",
      "d_difficult.in.txt 9368 1788\n",
      "e_elaborate.in.txt 4986 1004\n"
     ]
    }
   ],
   "source": [
    "# scoring\n",
    "for fname in inputs:\n",
    "    with open(os.path.join(iroot, fname)) as f:\n",
    "        in_lines = f.read().splitlines()\n",
    "    likes = in_lines[1:][::2]\n",
    "    dislikes = in_lines[1:][1::2]\n",
    "    \n",
    "    with open(os.path.join(oroot, fname)) as f:\n",
    "        ings = f.read().split()[1:]\n",
    "\n",
    "    print(fname, in_lines[0], score(ings, likes, dislikes))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}