AoC_Day_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advent of Code - Day 1: No time for a taxicab\n",
    "[http://adventofcode.com/2016/day/1]\n",
    "\n",
    "Santa's sleigh uses a very high-precision clock to guide its movements, and the clock's oscillator is regulated by stars. Unfortunately, the stars have been stolen... by the Easter Bunny. To save Christmas, Santa needs you to retrieve all fifty stars by December 25th.\n",
    "\n",
    "Collect stars by solving puzzles. Two puzzles will be made available on each day in the advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!\n",
    "\n",
    "You're airdropped near Easter Bunny Headquarters in a city somewhere. \"Near\", unfortunately, is as close as you can get - the instructions on the Easter Bunny Recruiting Document the Elves intercepted start here, and nobody had time to work them out further.\n",
    "\n",
    "The Document indicates that you should start at the given coordinates (where you just landed) and face North. Then, follow the provided sequence: either turn left (L) or right (R) 90 degrees, then walk forward the given number of blocks, ending at a new intersection.\n",
    "\n",
    "There's no time to follow such ridiculous instructions on foot, though, so you take a moment and work out the destination. Given that you can only walk on the street grid of the city, how far is the shortest path to the destination?\n",
    "\n",
    "For example:\n",
    "\n",
    "* Following R2, L3 leaves you 2 blocks East and 3 blocks North, or 5 blocks away.\n",
    "* R2, R2, R2 leaves you 2 blocks due South of your starting position, which is 2 blocks away.\n",
    "* R5, L5, R5, R3 leaves you 12 blocks away.\n",
    "\n",
    "**How many blocks away is Easter Bunny HQ?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parse the input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "directions = 'L4, L3, R1, L4, R2, R2, L1, L2, R1, R1, L3, R5, L2, R5, L4, L3, R2, R2, L5, L1, R4, L1, R3, L3, R5, R2, L5, R2, R1, R1, L5, R1, L3, L2, L5, R4, R4, L2, L1, L1, R1, R1, L185, R4, L1, L1, R5, R1, L1, L3, L2, L1, R2, R2, R2, L1, L1, R4, R5, R53, L1, R1, R78, R3, R4, L1, R5, L1, L4, R3, R3, L3, L3, R191, R4, R1, L4, L1, R3, L1, L2, R3, R2, R4, R5, R5, L3, L5, R2, R3, L1, L1, L3, R1, R4, R1, R3, R4, R4, R4, R5, R2, L5, R1, R2, R5, L3, L4, R1, L5, R1, L4, L3, R5, R5, L3, L4, L4, R2, R2, L5, R3, R1, R2, R5, L5, L3, R4, L5, R5, L3, R1, L1, R4, R4, L3, R2, R5, R1, R2, L1, R4, R1, L3, L3, L5, R2, R5, L1, L4, R3, R3, L3, R2, L5, R1, R3, L3, R2, L1, R4, R3, L4, R5, L2, L2, R5, R1, R2, L4, L4, L5, R3, L4'\n",
    "instructions = directions.split(', ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "bearings = ['N','E','S','W'] #not used but for reference to determine the indexes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def new_location(instruction, current_bearing, current_loc):\n",
    "    # determine the direction L or R\n",
    "    movement_direction = instruction[0]\n",
    "    \n",
    "    # determine the stepsize\n",
    "    step_size = int(instruction[1:])\n",
    "    \n",
    "    # determine the change in bearing based on L (-1) or R (1)\n",
    "    if movement_direction == 'L':\n",
    "        delta_bearing = -1\n",
    "    elif movement_direction == 'R':\n",
    "        delta_bearing = 1\n",
    "    \n",
    "    # derive the new bearing from the delta bearing by taking the modulus 4\n",
    "    new_bearing = ((current_bearing + delta_bearing) % 4)\n",
    "    \n",
    "    delta_x = 0\n",
    "    delta_y = 0\n",
    "    \n",
    "    # calculate the delta_x or delta_y based on the new bearing and the step size\n",
    "    if new_bearing == 0:\n",
    "        delta_y = step_size\n",
    "    elif new_bearing == 1:\n",
    "        delta_x = step_size\n",
    "    elif new_bearing == 2:\n",
    "        delta_y = -step_size\n",
    "    elif new_bearing == 3:\n",
    "        delta_x = -step_size\n",
    "        \n",
    "    # calculate the new location by combining current location and delta_x and delta_y    \n",
    "    x_new = current_loc[0] + delta_x\n",
    "    y_new = current_loc[1] + delta_y\n",
    "    \n",
    "    new_loc = (x_new, y_new)\n",
    "    \n",
    "    return new_bearing, new_loc, delta_x, delta_y # delta_x, delta_y added for part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# initialize\n",
    "current_bearing = 0 # we start facing north\n",
    "current_loc = (0,0)\n",
    "\n",
    "# iterate over the instructions\n",
    "for instruction in instructions:\n",
    "    current_bearing, current_loc, delta_x, delta_y = new_location(instruction, current_bearing, current_loc)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The distance is: 332\n"
     ]
    }
   ],
   "source": [
    "print \"The distance is:\", abs(current_loc[0]) + abs(current_loc[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two: Some changes are needed to the initial solution\n",
    "\n",
    "Then, you notice the instructions continue on the back of the Recruiting Document. Easter Bunny HQ is actually at the first location you visit twice.\n",
    "\n",
    "For example, if your instructions are R8, R4, R4, R8, the first location you visit twice is 4 blocks away, due East.\n",
    "\n",
    "How many blocks away is the first location you visit twice?\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(-158, 8)] 166\n"
     ]
    }
   ],
   "source": [
    "# initialize\n",
    "current_bearing = 0 # we start facing north\n",
    "current_loc = (0,0)\n",
    "\n",
    "locs_touched = []\n",
    "for instruction in instructions:\n",
    "    new_bearing, new_loc, delta_x, delta_y = new_location(instruction, current_bearing, current_loc)    \n",
    "\n",
    "    # initialize\n",
    "    current_y = current_loc[1]\n",
    "    current_x = current_loc[0]\n",
    "    path = []\n",
    "    x_dir = 0\n",
    "    y_dir = 0\n",
    "    \n",
    "    # determine the direction we are moving in\n",
    "    if delta_x > 0:\n",
    "        x_dir = 1 \n",
    "    elif delta_x < 0:\n",
    "        x_dir = -1\n",
    "    elif delta_y > 0:\n",
    "        y_dir = 1\n",
    "    elif delta_y < 0:\n",
    "        y_dir = -1\n",
    "\n",
    "    # go over each of the locations touched\n",
    "    # we can combine x and y since we know its either x or y\n",
    "    for step_x in range(0,abs(delta_x)+abs(delta_y)):\n",
    "        current_x = current_x + x_dir\n",
    "        current_y = current_y + y_dir\n",
    "        step = (current_x , current_y)\n",
    "        path.append(step)\n",
    "\n",
    "    # check if any locations in the current path are in any of the previous touched locations\n",
    "    double_locs = [i for i in path if i in locs_touched]\n",
    "    if len(double_locs)>0:\n",
    "        print double_locs, abs(double_locs[0][0]) + abs(double_locs[0][1])\n",
    "        break\n",
    "    \n",
    "    # add the current path to the touched locations\n",
    "    locs_touched.extend(path)\n",
    "    \n",
    "    # update the bearing and current location\n",
    "    current_bearing = new_bearing\n",
    "    current_loc = new_loc"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}