problem-2a-binary-serarch.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "jRvcvxnOfO6w"
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "sx6HLLj2fO61"
   },
   "outputs": [],
   "source": [
    "#test=pd.read_csv('test.csv')\n",
    "#train =pd.read_csv('train.csv')\n",
    "validation =pd.read_csv('validation.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "heal_lDTfO64"
   },
   "outputs": [],
   "source": [
    "#train_X = train[['click','bidprice','payprice','slotprice']]\n",
    "val_X = validation[['click','bidprice','payprice','slotprice']]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "cURi9VbxfO66"
   },
   "outputs": [],
   "source": [
    "def ad1_spend(x,df):\n",
    "    clicks=0\n",
    "    budget=6250000\n",
    "    win=0\n",
    "    for i in range(len(df)):\n",
    "        #print(i)\n",
    "        y = df['payprice'].iloc[i]\n",
    "        if budget <= y:\n",
    "            break\n",
    "        elif (x>=y and x >=df['slotprice'].iloc[i]):\n",
    "            #df['win'].iloc[i] = 1\n",
    "            win+=1\n",
    "            budget -= df['payprice'].iloc[i]\n",
    "            clicks += df['click'].iloc[i]\n",
    "    #df.loc[df[\"win\"]=='','win'] = 0\n",
    "    spend = 6250000-budget\n",
    "    #ctr=clicks/(df['win'].sum())\n",
    "    ctr=clicks/win\n",
    "    return clicks,spend,ctr, win"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "5z_YMfiJfO68"
   },
   "outputs": [],
   "source": [
    "def ran_gen(l,h):\n",
    "    mid = np.ceil((h+l)/2).astype(int)\n",
    "    n = np.ceil(0.2*(mid-l+1)).astype(int)\n",
    "    \n",
    "    bid_ran_list=[]\n",
    "    bid_ran_list2=[]\n",
    "    \n",
    "    bid_ran_list = random.sample(range(l,mid), n)\n",
    "    bid_ran_list2 = random.sample(range(mid,h), n)\n",
    "    \n",
    "    ran = []\n",
    "    ran = bid_ran_list + bid_ran_list2\n",
    "    return ran"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "VATOzcG_gfGn"
   },
   "outputs": [],
   "source": [
    "def run_range(low,high,df):\n",
    "    iteration = 0\n",
    "    bid = (high-low)/2\n",
    "\n",
    "    while (bid-low)>0 or (high-bid)>0: \n",
    "        mid = np.ceil((high+low)/2).astype(int)\n",
    "        sp3_val=[]\n",
    "        c3_val=[]\n",
    "        ctr3_val = []\n",
    "        win3_val = []\n",
    "        bid_range =[]\n",
    "        if high-low >1:\n",
    "            bid_range = ran_gen(low,high)\n",
    "            print (bid_range)\n",
    "            for bid in bid_range:\n",
    "                a, b, c, d = ad1_spend(bid,df)\n",
    "                c3_val.append(a)\n",
    "                sp3_val.append(b)\n",
    "                ctr3_val.append(c)\n",
    "                win3_val.append(d)\n",
    "                print(bid) \n",
    "            z = np.argmax(c3_val)\n",
    "            best_bid = bid_range[z]\n",
    "            print(\"best bid \",best_bid)\n",
    "            if best_bid >= mid:\n",
    "                low = mid\n",
    "            elif best_bid < mid:\n",
    "                high = mid\n",
    "            bid = best_bid \n",
    "            iteration += 1\n",
    "            print (\"done iteration \", iteration)\n",
    "            print (\"new range = \", low, \" to \", high )\n",
    "        else:\n",
    "            id_range = (low,high)\n",
    "            a1, b1, c1, d1 = ad1_spend(low,df)\n",
    "            a2, b2, c2, d2 = ad1_spend(high,df)\n",
    "            print (\"done iteration \", iteration)\n",
    "            if a1>a2:\n",
    "                print(\"optimal best bid:\",low)\n",
    "                print (\"clicks = \", a1 )\n",
    "            else:\n",
    "                print(\"optimal best bid: \",high)\n",
    "                print (\"clicks = \", a2 )\n",
    "            break\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5QH7BYnOgfG_"
   },
   "source": [
    "# Run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {}
     ]
    },
    "colab_type": "code",
    "id": "7keVsVangfHA",
    "outputId": "977dd080-f698-494a-ed0b-7e3cf16b24b8"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[47, 5, 28, 21, 40, 10, 2, 71, 51, 67, 17, 62, 20, 6, 18, 23, 125, 142, 78, 90, 123, 138, 130, 146, 85, 89, 114, 102, 80, 129, 86, 100]\n",
      "47\n",
      "5\n",
      "28\n",
      "21\n",
      "40\n",
      "10\n",
      "2\n",
      "71\n",
      "51\n",
      "67\n",
      "17\n",
      "62\n",
      "20\n",
      "6\n",
      "18\n",
      "23\n",
      "125\n",
      "142\n",
      "78\n",
      "90\n",
      "123\n",
      "138\n",
      "130\n",
      "146\n",
      "85\n",
      "89\n",
      "114\n",
      "102\n",
      "80\n",
      "129\n",
      "86\n",
      "100\n",
      "best bid  78\n",
      "done iteration  1\n",
      "new range =  76  to  150\n",
      "[80, 88, 107, 110, 94, 81, 112, 100, 133, 125, 135, 116, 120, 114, 134, 148]\n",
      "80\n",
      "88\n",
      "107\n",
      "110\n",
      "94\n",
      "81\n",
      "112\n",
      "100\n",
      "133\n",
      "125\n",
      "135\n",
      "116\n",
      "120\n",
      "114\n",
      "134\n",
      "148\n",
      "best bid  81\n",
      "done iteration  2\n",
      "new range =  76  to  113\n",
      "[78, 85, 84, 93, 103, 112, 102, 110]\n",
      "78\n",
      "85\n",
      "84\n",
      "93\n",
      "103\n",
      "112\n",
      "102\n",
      "110\n",
      "best bid  78\n",
      "done iteration  3\n",
      "new range =  76  to  95\n",
      "[84, 81, 76, 89, 86, 93]\n",
      "84\n",
      "81\n",
      "76\n",
      "89\n",
      "86\n",
      "93\n",
      "best bid  81\n",
      "done iteration  4\n",
      "new range =  76  to  86\n",
      "[80, 78, 85, 84]\n",
      "80\n",
      "78\n",
      "85\n",
      "84\n",
      "best bid  78\n",
      "done iteration  5\n",
      "new range =  76  to  81\n",
      "[78, 80]\n",
      "78\n",
      "80\n",
      "best bid  78\n",
      "done iteration  6\n",
      "new range =  76  to  79\n",
      "[76, 78]\n",
      "76\n",
      "78\n",
      "best bid  78\n",
      "done iteration  7\n",
      "new range =  78  to  79\n",
      "done iteration  7\n",
      "optimal best bid:  79\n",
      "clicks =  68\n"
     ]
    }
   ],
   "source": [
    "run_range(1,150,val_X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "rENzZspdgfHa"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "default_view": {},
   "name": "problem-2b-range (1).ipynb",
   "provenance": [],
   "version": "0.3.2",
   "views": {}
  },
  "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}