day13.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 🍭 [Day 13](https://adventofcode.com/2020/day/13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1202161486\n",
      "Bus index 0 runs every 1789 minutes\n",
      "0\n",
      "Bus index 1 runs every 37 minutes\n",
      "0\n",
      "Bus index 2 runs every 47 minutes\n",
      "0\n",
      "Bus index 3 runs every 1889 minutes\n",
      "0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1202161486"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from functools import reduce\n",
    "\n",
    "def waiting_for_the_bus(timestamp, buses):\n",
    "    first_bus = None, float('inf')\n",
    "    for _, b in buses:\n",
    "        ### Find the first n = k . b which is bigger\n",
    "        ### than timestamps\n",
    "        k = timestamp // b\n",
    "        if (k + 1) * b < first_bus[1]:\n",
    "            first_bus =  b, (k + 1) * b\n",
    "    # result\n",
    "    wait_time = first_bus[1] - timestamp\n",
    "    return first_bus[0] * wait_time\n",
    "\n",
    "\n",
    "def contest_winner(buses):\n",
    "    # We're searching for timestamp t\n",
    "    # such that for all i, there exists some ki\n",
    "    # buses[i] * ki = t + i\n",
    "    # => t = - i [bi], for all is\n",
    "    # This is a typical scenario of the Chinese remainder theorem\n",
    "    # Let n = b1 * b2 * ... * bn\n",
    "    # Let ri = n / ni (product ignoring i-th term)\n",
    "    # Let vi such that vi * ri = 1 [ni] (modulo inverse)\n",
    "    # Then x = sum_i(-i * vi * ri) is a solution modulo n\n",
    "    #\n",
    "    # In fact:\n",
    "    # x [nj] = sum_i(-i * vi * ri [nj]) = -j * vj * rj [nj] \n",
    "    #        = -j [ nj] * vj * rj [nj] \n",
    "    #        = - j\n",
    "    n = reduce(lambda a, b: a * b, [x[1] for x in buses])\n",
    "    t = 0\n",
    "    for i, b in buses:\n",
    "        vi = pow(n // b, -1, b)\n",
    "        t += (-i) * vi * n // b\n",
    "    # Our t will be negative, so t % n should be the smallest \n",
    "    # positive integer that verifies the system of equation\n",
    "    t = t % n\n",
    "    ### Optional Sanity check\n",
    "    for i, b in buses:\n",
    "        assert (t + i ) % b\n",
    "    return t\n",
    "    \n",
    "inputs = \"\"\"0\n",
    "1789,37,47,1889\"\"\"\n",
    "timestamp, buses = inputs.splitlines()\n",
    "timestamp = int(timestamp)\n",
    "buses = [(i, int(b)) for i, b in enumerate(buses.split(',')) if b != 'x']\n",
    "contest_winner(buses)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "836024966345345\n",
      "Bus index 0 runs every 37 minutes\n",
      "0\n",
      "Bus index 27 runs every 41 minutes\n",
      "0\n",
      "Bus index 37 runs every 587 minutes\n",
      "0\n",
      "Bus index 55 runs every 13 minutes\n",
      "0\n",
      "Bus index 56 runs every 19 minutes\n",
      "0\n",
      "Bus index 60 runs every 23 minutes\n",
      "0\n",
      "Bus index 66 runs every 29 minutes\n",
      "0\n",
      "Bus index 68 runs every 733 minutes\n",
      "0\n",
      "Bus index 85 runs every 17 minutes\n",
      "0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "836024966345345"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "with open('inputs/day13.txt', 'r') as f:\n",
    "    inputs = f.read()\n",
    "    timestamp, buses = inputs.splitlines()\n",
    "    timestamp = int(timestamp)\n",
    "    buses = [(i, int(b)) for i, b in enumerate(buses.split(',')) if b != 'x']\n",
    "    \n",
    "waiting_for_the_bus(timestamp, buses)\n",
    "contest_winner(buses)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}