day13.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "TZ5O20obUjg0"
   },
   "source": [
    "##  🍭 [Day 13](https://adventofcode.com/2018/day/13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Mk1gkvnlUhYu"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def parse_char(c):\n",
    "  \"\"\"Parse a character and return the direction and orientation \n",
    "    when encountering this track. \n",
    "    Direction is + 1 for ^ and v, -1 for < and >\n",
    "    Orientation is + 1 for ^ and >, -1 for v and <\"\"\"\n",
    "  if c == '|':\n",
    "    return (1, 1, ord('|'))\n",
    "  elif c == '-':\n",
    "    return (1, 1, ord('-'))\n",
    "  elif c == '/':\n",
    "    return (-1, 1, ord('/'))\n",
    "  elif c == '\\\\':\n",
    "    return (-1, -1, ord('\\\\'))\n",
    "  elif c in ['>', '<', '^', 'v']:\n",
    "    return (1 if c in ['v', '^'] else -1, 1 if c in ['^', '>'] else -1,  -1)\n",
    "  elif c == '+':\n",
    "    return (-2, 0, ord('+'))\n",
    "  else:\n",
    "    return (0, 0, ord(' '))\n",
    "  \n",
    "def parse_inputs(inputs):\n",
    "  \"\"\"Parse inputs into a grid and initial cars positions\"\"\"\n",
    "  grid = np.array([[parse_char(c) for c in line] for line in inputs])\n",
    "  cars = []\n",
    "  for x, y in zip(*np.where(grid[:, :, -1] < 0)):\n",
    "    pos = np.array([x, y])\n",
    "    direction = grid[x, y, 0]\n",
    "    orientation = grid[x, y, 1]\n",
    "    grid[x, y] = parse_char('|') if inputs[x][y] in ['^', 'v'] else parse_char('-')\n",
    "    cars.append((pos, direction, orientation, 0, True)) # (position, direction, orientation, next_turn, alive or crashed)\n",
    "  return cars, grid\n",
    "  \n",
    "def get_character(direction, orientation):\n",
    "  \"\"\"Display a car given its current direction and orientation\"\"\"\n",
    "  if direction == 1:\n",
    "    return ord('^' if orientation == +1 else 'v')\n",
    "  else:\n",
    "    return ord('>' if orientation == +1 else '<')\n",
    "  \n",
    "def print_grid(grid, cars):\n",
    "  \"\"\"Display a grid with cars\"\"\"\n",
    "  g  = np.array(grid)[:, :, -1]\n",
    "  for pos, direction, orientation, _, alive in cars:\n",
    "    if alive:\n",
    "      g[pos[0], pos[1]] = get_character(direction, orientation)\n",
    "    else:\n",
    "      g[pos[0], pos[1]] = ord('X')\n",
    "  for line in g:\n",
    "    print('\\r' * g.shape[0], ''.join(list(map(chr, line))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "axCn6FNaUql6"
   },
   "outputs": [],
   "source": [
    "def drive(inputs, num_steps=15, part1=True, verbose=False):\n",
    "  \"\"\"Let the carts drive for the given number of steps and stop using \n",
    "     the rule for the Part 1 problem or Part 2 problem\"\"\"\n",
    "  cars, grid = parse_inputs(inputs)  \n",
    "  for s in range(num_steps):\n",
    "    # Sort and filter current cars\n",
    "    if verbose:\n",
    "      print_grid(grid, cars)\n",
    "    cars = sorted(cars, key=lambda x: tuple(x[0]))\n",
    "    cars = [c for c in cars if c[-1]]\n",
    "    if not part1:\n",
    "      print('\\rCurrent number of cars: %d' % len(cars), end='')\n",
    "      \n",
    "    # Advance each car\n",
    "    for i, car in enumerate(cars):\n",
    "      pos, direction, orientation, next_turn, alive = car      \n",
    "      if not alive: continue\n",
    "      \n",
    "      # Crash detection\n",
    "      dead = []\n",
    "      for j,  (p, _, _, _, j_alive) in enumerate(cars):\n",
    "        if i == j or not j_alive:\n",
    "          continue\n",
    "        if np.all(pos == p):\n",
    "          dead.append(j)\n",
    "          # Part1: First crash detection\n",
    "          if part1:\n",
    "            if verbose:\n",
    "              cars[i] = cars[i][:-1] + [False]\n",
    "              cars[j] = cars[j][:-1] + [False]\n",
    "              print_grid(grid, cars)\n",
    "            return (s, (pos[1], pos[0]))\n",
    "      # Part2: mark cars as crashed to be removed in the next iteration\n",
    "      # Stop if there's only one car remaining\n",
    "      if len(dead):\n",
    "        for j in (dead + [i]):\n",
    "          cars[j] = cars[j][:-1] + [False]\n",
    "        if len(cars) - len(dead) - 1 == 1:\n",
    "          cars = [c for c in cars if c[-1]]\n",
    "          if verbose:  print_grid(grid, cars)\n",
    "          return (s, (cars[0][0][1], cars[0][0][0]))\n",
    "      else:\n",
    "        # If the car is still alive, move it\n",
    "        # Change orientation and direction (if needed) and then go straight\n",
    "        if grid[pos[0], pos[1], -1] != ord('+'): # normal tracks:\n",
    "          direction *= grid[pos[0], pos[1], 0]\n",
    "          orientation *= grid[pos[0], pos[1], 1]\n",
    "        else:                            # + tracks\n",
    "          if next_turn == 0:       \n",
    "            if direction == 1:\n",
    "              orientation *= -1\n",
    "            direction *= -1\n",
    "          elif next_turn == 2:       \n",
    "            if direction ==  -1:\n",
    "              orientation *= -1\n",
    "            direction *= -1\n",
    "          next_turn = (next_turn + 1) % 3          \n",
    "\n",
    "        # Update the position\n",
    "        pos += np.array([(direction > 0) * (- orientation), (direction < 0) * orientation])\n",
    "        cars[i] = [pos, direction, orientation, next_turn, alive]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 119
    },
    "colab_type": "code",
    "id": "EKzVobQ5zf9J",
    "outputId": "b56d66f2-02dd-4e04-c0a3-8b4102094140"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Time step and position of the first car crash: (123, (143, 43))\n",
      "\n",
      "Current number of cars: 3\n",
      "Time step of the last crach and position of the survivor: (22879, (116, 125))\n",
      "CPU times: user 7.79 s, sys: 1.76 s, total: 9.55 s\n",
      "Wall time: 10.4 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "with open(\"day13.txt\", 'r') as f:  \n",
    "  inputs = f.read().splitlines()\n",
    "  \n",
    "print('Time step and position of the first car crash:', drive(inputs, num_steps=200, part1=True, verbose=False))\n",
    "print()\n",
    "print('\\nTime step of the last crach and position of the survivor:', drive(inputs, num_steps=200000, part1=False, verbose=False))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1666
    },
    "colab_type": "code",
    "id": "Oib2eEDMzhW9",
    "outputId": "a622946a-f53b-4487-e9ff-fb5a65e4a798"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /->-\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | v  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /-->\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-v--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /--->        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+>-/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   v  /----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+->/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-v--+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+-->\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+>-+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  ^\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+->+-\\  ^\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /----^\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+-->-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /---<\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+>\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /--<-\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+->  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /-<--\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | v  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /<---\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-v--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  <----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\<+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--v-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  | |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  <-+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  ^ |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " /---\\        \n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " |   |  /----\\\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | /-+--+-\\  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " | | |  X |  |\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      " \\-+-/  \\-+--/\n",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "\r",
      "   \\------/   \n",
      "Time step and position of the first car crash: (14, (7, 3))\n"
     ]
    }
   ],
   "source": [
    "#@title Visualization on a toy example\n",
    "test_inputs = \"\"\"/->-\\\\        \n",
    "|   |  /----\\\\\n",
    "| /-+--+-\\  |\n",
    "| | |  | v  |\n",
    "\\\\-+-/  \\\\-+--/\n",
    "  \\\\------/   \"\"\"\n",
    "test_inputs = test_inputs.splitlines()\n",
    "print('Time step and position of the first car crash:', drive(test_inputs, num_steps=15, part1=True, verbose=True))"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "day1.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}