16/20/s20.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advent of Code 2016 Day 20\n",
    "http://adventofcode.com/2016/day/20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "MAXINT = 4294967295"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1 in `numpy` plus a Python function\n",
    "First we load the data into a numpy array and sort it by row so that our blacklist ranges are in increasing order of start address"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fwRules = np.loadtxt('input.txt', delimiter='-', dtype=np.uint32)\n",
    "fwRules.sort(axis=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`first_gap` looks through the array for the first allowed IP.  I know that there is at least one such in the data, so I'm not testing for running off the end of the array.  Below,  I'll use pure pandas to get the first IP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17348574"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def first_gap(r):\n",
    "    i = 1\n",
    "    ls, le = r[0]\n",
    "    while r[i][0] <= le + 1:\n",
    "        if r[i][1] > le:\n",
    "            le = r[i][1]\n",
    "        i += 1\n",
    "    return le + 1\n",
    "\n",
    "first_gap(fwRules)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Working in pure `pandas` \n",
    "\n",
    "## Part 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fwRulesDF = pd.DataFrame(fwRules, columns=['start', 'end'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To allow for the fact that the ends of ranges in the input might not be in monotonic order (we sorted first on the starts of the ranges), we add a column to keep track of the highest endpoint so far:-"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fwRulesDF['maxEnd'] = fwRulesDF.cummax()['end']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we have the `maxEnd` column, the number of allowed IPs before each range in the table can be determined from the difference of the `start` on this row and the `maxEnd` on the previous row.  If this is greater than zero, it is the count of the allowed IPs. (if it's negative, it represents the size of overlap of this range with the ones prior to it)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fwRulesDF['ipcount'] = fwRulesDF['start'] - fwRulesDF['maxEnd'].shift(1) - 1\n",
    "fwRulesDF.loc[fwRulesDF['ipcount'] < 0, 'ipcount'] = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, the first IP address in each block of allowed IPs can be calculated.  We select on column `ipcount` greater than 0 and subtract the number of allowed IPs from the start of the blacklist range to determine the first allowed IP in each window."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fwRulesDF['firstip'] = fwRulesDF[fwRulesDF['ipcount'] > 0]['start'] - fwRulesDF['ipcount']\n",
    "\n",
    "fwRulesDF = fwRulesDF.fillna(0).astype(np.uint32)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The very first allowed IP is then the first non-zero entry in our `firstip` column:-"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17348574"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fwRulesDF[fwRulesDF['firstip'] > 0]['firstip'].iloc[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2\n",
    "Part 2, the number of allowed IP addresses, comes easily.  We need to sum the `ipcount` column, then allow for the fact that the end of the last blacklist range might not be the upper limit of IP addresses (MAXINT)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "104"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.sum(fwRulesDF['ipcount']) + (MAXINT - fwRulesDF['maxEnd'].iloc[-1])"
   ]
  }
 ],
 "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
}