2022 hashcode practice round one pizza, simply random, 2 5 5 1803 2049

2022-hashcode-one-pizza.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9e9d2218",
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "import itertools\n",
    "import copy\n",
    "import random\n",
    "\n",
    "#ip = \"hashcode2022/a_an_example.in.txt\"\n",
    "#ip = \"hashcode2022/b_basic.in.txt\"\n",
    "#ip = \"hashcode2022/c_coarse.in.txt\"\n",
    "ip = \"hashcode2022/d_difficult.in.txt\"\n",
    "#ip = \"hashcode2022/e_elaborate.in.txt\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "64cd6b1e",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(ip) as f:\n",
    "    c = f.readlines()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e62d60b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 0\n",
    "def parse_taste(line):\n",
    "    global idx, ing_i_dict, i_ing_dict\n",
    "    sp = line.split(\" \")\n",
    "    if len(sp) == 0:\n",
    "        return []\n",
    "    \n",
    "    result = []\n",
    "    for ing in sp[1:]: # ignore count number\n",
    "        if ing in ing_i_dict:\n",
    "            result.append(ing_i_dict[ing])\n",
    "        else:\n",
    "            ing_i_dict[ing] = idx\n",
    "            i_ing_dict[idx] = ing\n",
    "            result.append(idx)\n",
    "            idx += 1\n",
    "    return result\n",
    "\n",
    "\n",
    "def count_customers(choice, cuss):\n",
    "    result = 0\n",
    "    for cu in cuss:\n",
    "        like, dislike = cu\n",
    "        # all like should be included\n",
    "        flag = True\n",
    "        for i in like:\n",
    "            if not choice[i]:\n",
    "                flag = False\n",
    "                break # break inner most\n",
    "        \n",
    "        if flag is False:\n",
    "            continue\n",
    "        \n",
    "        # non dislike should be true\n",
    "        for j in dislike:\n",
    "            if choice[j]:\n",
    "                flag = False\n",
    "                break\n",
    "        \n",
    "        if flag is True:\n",
    "            result += 1\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ddc0001a",
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 0\n",
    "ing_i_dict = dict()\n",
    "i_ing_dict = dict()\n",
    "\n",
    "# each customer contains their like&dislike index as a pair\n",
    "customers = []\n",
    "customer_count = int(c[0])\n",
    "for i in range(0, customer_count):\n",
    "    like = c[2*i+1].strip()\n",
    "    dislike = c[2*i+2].strip()\n",
    "    cus = [parse_taste(like), parse_taste(dislike)]\n",
    "    customers.append(cus)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "125ea740",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9368"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "299aec7c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# now we have all ingredients, [0, idx)\n",
    "# not including idx because it's the next index\n",
    "\n",
    "# let initial input be an array of 0 and 1, of length idx, \n",
    "# we match all customers with the input, calculate customer count\n",
    "ings = [1 for _ in range(idx)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b8cf4c2d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# from combination of dislikes, remove the ingredients, then match with customer\n",
    "alldislikes = dict()\n",
    "for cu in customers:\n",
    "    for d in cu[1]:\n",
    "        c = alldislikes.get(d, 0)\n",
    "        alldislikes[d] = c + 1\n",
    "# k is ingredient index, v is count\n",
    "topdislike = [[k, v] for k, v in sorted(alldislikes.items(), key=lambda item: item[1], reverse=True)]\n",
    "diss = [x[0] for x in topdislike]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d8e0f996",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b54c5b0b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# data, also initial best choices\n",
    "data = []\n",
    "m = 0\n",
    "\n",
    "# chosen indexes\n",
    "ci = [1 for _ in range(idx)]\n",
    "mci = ci\n",
    "\n",
    "m = count_customers(ci, customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "1d1c5717",
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "Input \u001b[0;32mIn [10]\u001b[0m, in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      6\u001b[0m orig \u001b[38;5;241m=\u001b[39m ci[i]\n\u001b[1;32m      7\u001b[0m ci[i] \u001b[38;5;241m=\u001b[39m \u001b[38;5;241m0\u001b[39m \u001b[38;5;28;01mif\u001b[39;00m orig \u001b[38;5;28;01melse\u001b[39;00m \u001b[38;5;241m1\u001b[39m \u001b[38;5;66;03m# flip value\u001b[39;00m\n\u001b[0;32m----> 8\u001b[0m nm \u001b[38;5;241m=\u001b[39m \u001b[43mcount_customers\u001b[49m\u001b[43m(\u001b[49m\u001b[43mci\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mcustomers\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m      9\u001b[0m ic \u001b[38;5;241m+\u001b[39m\u001b[38;5;241m=\u001b[39m \u001b[38;5;241m1\u001b[39m\n\u001b[1;32m     10\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m nm \u001b[38;5;241m>\u001b[39m\u001b[38;5;241m=\u001b[39m m: \u001b[38;5;66;03m# bias against change\u001b[39;00m\n",
      "Input \u001b[0;32mIn [3]\u001b[0m, in \u001b[0;36mcount_customers\u001b[0;34m(choice, cuss)\u001b[0m\n\u001b[1;32m     24\u001b[0m \u001b[38;5;66;03m# all like should be included\u001b[39;00m\n\u001b[1;32m     25\u001b[0m flag \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;01mTrue\u001b[39;00m\n\u001b[0;32m---> 26\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m i \u001b[38;5;129;01min\u001b[39;00m like:\n\u001b[1;32m     27\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;129;01mnot\u001b[39;00m choice[i]:\n\u001b[1;32m     28\u001b[0m         flag \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;01mFalse\u001b[39;00m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "# might mutate into deadend, reset ci to 1 when not seeing progress.... in some time\n",
    "ic = 0\n",
    "while True:\n",
    "    # mutate?\n",
    "    i = random.choice(diss)\n",
    "    orig = ci[i]\n",
    "    ci[i] = 0 if orig else 1 # flip value\n",
    "    nm = count_customers(ci, customers)\n",
    "    ic += 1\n",
    "    if nm >= m: # bias against change\n",
    "        m = nm\n",
    "        mci = ci\n",
    "        #if nm > m and nm % 2 == 0: # but less print..\n",
    "        if nm > m:\n",
    "            print(\"new max \", nm) \n",
    "    else:\n",
    "        ci[i] = orig\n",
    "    \n",
    "    if ic == 1000000:\n",
    "        print(\"reset ci for another run\")\n",
    "        ci = [1 for _ in range(idx)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "078a8506",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1803"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "c82db44d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_ingredients(ccis):\n",
    "    result = [0]\n",
    "    r = 0\n",
    "    for i,v in enumerate(ccis):\n",
    "        if v==1:\n",
    "            r += 1\n",
    "            result.append(i_ing_dict[i])\n",
    "    result[0] = str(r)\n",
    "    return ' '.join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "ce2fdcd9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'358 ingredient319 ingredient79 ingredient123 ingredient550 ingredient478 ingredient552 ingredient266 ingredient359 ingredient312 ingredient68 ingredient124 ingredient200 ingredient452 ingredient494 ingredient396 ingredient349 ingredient518 ingredient339 ingredient598 ingredient250 ingredient450 ingredient584 ingredient333 ingredient157 ingredient146 ingredient12 ingredient547 ingredient160 ingredient8 ingredient174 ingredient426 ingredient152 ingredient360 ingredient2 ingredient30 ingredient212 ingredient288 ingredient326 ingredient98 ingredient318 ingredient302 ingredient166 ingredient388 ingredient74 ingredient92 ingredient489 ingredient272 ingredient370 ingredient303 ingredient327 ingredient41 ingredient237 ingredient195 ingredient377 ingredient331 ingredient13 ingredient199 ingredient101 ingredient363 ingredient459 ingredient419 ingredient254 ingredient320 ingredient409 ingredient298 ingredient267 ingredient11 ingredient497 ingredient94 ingredient471 ingredient44 ingredient16 ingredient374 ingredient380 ingredient144 ingredient227 ingredient321 ingredient270 ingredient451 ingredient490 ingredient464 ingredient128 ingredient460 ingredient481 ingredient504 ingredient299 ingredient373 ingredient291 ingredient405 ingredient534 ingredient549 ingredient345 ingredient502 ingredient130 ingredient214 ingredient351 ingredient332 ingredient561 ingredient436 ingredient253 ingredient338 ingredient290 ingredient217 ingredient495 ingredient208 ingredient454 ingredient503 ingredient585 ingredient355 ingredient35 ingredient223 ingredient82 ingredient506 ingredient145 ingredient10 ingredient131 ingredient112 ingredient511 ingredient205 ingredient155 ingredient244 ingredient538 ingredient19 ingredient412 ingredient265 ingredient477 ingredient150 ingredient72 ingredient536 ingredient284 ingredient252 ingredient22 ingredient114 ingredient143 ingredient328 ingredient206 ingredient515 ingredient301 ingredient416 ingredient55 ingredient529 ingredient440 ingredient437 ingredient346 ingredient274 ingredient106 ingredient371 ingredient76 ingredient40 ingredient259 ingredient180 ingredient203 ingredient156 ingredient486 ingredient89 ingredient501 ingredient479 ingredient134 ingredient470 ingredient566 ingredient179 ingredient138 ingredient15 ingredient311 ingredient275 ingredient189 ingredient583 ingredient258 ingredient66 ingredient554 ingredient1 ingredient499 ingredient97 ingredient107 ingredient361 ingredient334 ingredient524 ingredient249 ingredient366 ingredient378 ingredient228 ingredient5 ingredient255 ingredient340 ingredient95 ingredient322 ingredient463 ingredient385 ingredient590 ingredient125 ingredient93 ingredient161 ingredient383 ingredient6 ingredient281 ingredient201 ingredient120 ingredient557 ingredient198 ingredient472 ingredient403 ingredient330 ingredient257 ingredient329 ingredient600 ingredient514 ingredient395 ingredient127 ingredient191 ingredient425 ingredient582 ingredient308 ingredient177 ingredient213 ingredient77 ingredient33 ingredient491 ingredient386 ingredient193 ingredient553 ingredient453 ingredient316 ingredient430 ingredient384 ingredient188 ingredient73 ingredient570 ingredient210 ingredient69 ingredient173 ingredient43 ingredient29 ingredient83 ingredient402 ingredient32 ingredient165 ingredient577 ingredient473 ingredient467 ingredient508 ingredient24 ingredient418 ingredient49 ingredient587 ingredient18 ingredient535 ingredient369 ingredient513 ingredient563 ingredient314 ingredient376 ingredient413 ingredient262 ingredient465 ingredient428 ingredient569 ingredient519 ingredient204 ingredient487 ingredient522 ingredient525 ingredient565 ingredient222 ingredient391 ingredient593 ingredient71 ingredient202 ingredient516 ingredient207 ingredient545 ingredient289 ingredient389 ingredient521 ingredient480 ingredient172 ingredient354 ingredient287 ingredient530 ingredient286 ingredient78 ingredient571 ingredient447 ingredient375 ingredient523 ingredient572 ingredient85 ingredient520 ingredient537 ingredient90 ingredient542 ingredient261 ingredient498 ingredient84 ingredient568 ingredient546 ingredient578 ingredient190 ingredient401 ingredient410 ingredient466 ingredient576 ingredient248 ingredient539 ingredient224 ingredient271 ingredient505 ingredient512 ingredient399 ingredient444 ingredient597 ingredient162 ingredient558 ingredient548 ingredient591 ingredient532 ingredient461 ingredient586 ingredient541 ingredient599 ingredient372 ingredient170 ingredient247 ingredient517 ingredient556 ingredient438 ingredient560 ingredient531 ingredient510 ingredient580 ingredient592 ingredient543 ingredient408 ingredient579 ingredient147 ingredient559 ingredient594 ingredient581 ingredient564 ingredient575 ingredient533 ingredient574 ingredient540 ingredient187 ingredient595 ingredient573 ingredient507 ingredient589 ingredient567 ingredient555 ingredient509 ingredient562 ingredient551 ingredient596 ingredient528 ingredient544 ingredient588 ingredient527 ingredient526'"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_ingredients(ci)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 534,
   "id": "b39144d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"/mnt/c/Users/ho/Desktop/hashc/\"+ip, \"w\") as f:\n",
    "    f.write(to_ingredients(ci))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 535,
   "id": "eb7e5093",
   "metadata": {},
   "outputs": [],
   "source": [
    "eci = ci"
   ]
  }
 ],
 "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.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}