prob_597.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "\n",
    "from time import time\n",
    "from math import exp, log\n",
    "from random import random, seed\n",
    "from collections import defaultdict, OrderedDict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def getOrder(bumptime):\n",
    "    sign = 0\n",
    "    result = [i for i in range(len(bumptime))]\n",
    "    bumptime = sorted(bumptime, key=lambda x: x[2])\n",
    "    for i in range(len(bumptime)):\n",
    "        i_index = result.index(bumptime[i][0])\n",
    "        j_index = result.index(bumptime[i][1])\n",
    "        result[i_index:(j_index+1)] = [result[j_index]] + result[i_index:j_index]\n",
    "        sign = (sign + (j_index-i_index))%2\n",
    "    return(sign, result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# n, L0, Delta = 3, 160, 40\n",
    "n, L0, Delta = 13, 180, 40"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[226.9192457192563, 241.28569511224129, 1268.7887226863045, 78.50106410337018, 29.51653386727437, -37.58867957594577, -35.51899213577752, -149.34085964578853, -302.88499997503607, -775.991772269623, -93.09615840079843, -217.9929630132805, -124.97277627717007]\n",
      "0 1 0.7932337313631624 0.5802250313052119 187.78575705648504\n",
      "0 2 0.7932337313631624 0.07881532851921795 111.97919829827643\n",
      "1 2 0.5802250313052119 0.07881532851921795 79.77508169017692\n"
     ]
    }
   ],
   "source": [
    "seed(11)\n",
    "Vs = [-log(random()) for _ in range(n)]\n",
    "bumptime = list()\n",
    "arrivaltime = [(L0-Delta*i)/Vs[i] for i in range(n)]\n",
    "print(arrivaltime)\n",
    "for i in range(0,n):\n",
    "    minbumptime = arrivaltime[i]\n",
    "    for j in range(i+1,n):\n",
    "        if Vs[i] > Vs[j]:\n",
    "            testtime = (j-i)*Delta/(Vs[i]-Vs[j])\n",
    "            if testtime < arrivaltime[j] and testtime < minbumptime:\n",
    "                minbumptime = testtime\n",
    "                minbumpboat = j                \n",
    "                print(i,j,Vs[i],Vs[j],testtime)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([2.0072009271185753, 0.16554262928899602, 0.2694825346765816],\n",
       " [79.71299626175791, 724.8888127209217, 296.8652498983345])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Vs, arrivaltime, "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bumptime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[79.71299626175791, 724.8888127209217, 296.8652498983345]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arrivaltime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99999 0.44551\n",
      "199999 0.444915\n",
      "299999 0.44526666666666664\n",
      "399999 0.44534\n",
      "499999 0.445488\n",
      "599999 0.4453916666666667\n",
      "699999 0.44505428571428574\n",
      "799999 0.44567375\n",
      "899999 0.44572555555555554\n",
      "999999 0.44543\n",
      "1099999 0.4452481818181818\n",
      "1199999 0.445305\n",
      "1299999 0.44500923076923077\n",
      "1399999 0.44515571428571427\n",
      "1499999 0.4450773333333333\n",
      "1599999 0.444931875\n",
      "1699999 0.44479705882352943\n",
      "1799999 0.44463166666666665\n",
      "1899999 0.44464789473684213\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-12-9a93191d8140>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0mevencount\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mrep\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m     \u001b[0mseed\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrep\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      5\u001b[0m     \u001b[0mVs\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0mlog\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrandom\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0m_\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m     \u001b[0mbumptime\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlist\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/opt/conda/lib/python3.5/random.py\u001b[0m in \u001b[0;36mseed\u001b[0;34m(self, a, version)\u001b[0m\n\u001b[1;32m    120\u001b[0m                 \u001b[0ma\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mfrom_bytes\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'big'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    121\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 122\u001b[0;31m         \u001b[0msuper\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mseed\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    123\u001b[0m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mgauss_next\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    124\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "N = 10000000\n",
    "evencount = 0\n",
    "for rep in range(N):\n",
    "    seed(rep)\n",
    "    Vs = [-log(random()) for _ in range(n)]\n",
    "    bumptime = list()\n",
    "    arrivaltime = [(L+Lint*i)/Vs[i] for i in range(n)]\n",
    "    for i in range(n):\n",
    "        minbumptime = arrivaltime[i]\n",
    "        minbumpboat = i\n",
    "        for j in range(i+1,n):\n",
    "            if Vs[j] > Vs[i]:\n",
    "                testtime = (j-i)*Lint/(Vs[j]-Vs[i])\n",
    "                if testtime < minbumptime:\n",
    "                    minbumptime = testtime\n",
    "                    minbumpboat = j\n",
    "        bumptime.append((i,minbumpboat, minbumptime))\n",
    "    evencount += getOrder(bumptime)[0] ==0\n",
    "    \n",
    "    if (rep+1)%100000 == 0:\n",
    "        print(rep, evencount/(rep+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.4148148148148148"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "56/135"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}