day13.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "day13.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "X9WQ0lmfsw_t"
      },
      "source": [
        "https://adventofcode.com/2020/day/13"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SKMKHgXI7Ive"
      },
      "source": [
        "input = r'''1000052\r\n",
        "23,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,863,x,x,x,x,x,x,x,x,x,x,x,19,13,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,29,x,571,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,41'''"
      ],
      "execution_count": 137,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ssq2I6LV7QsQ"
      },
      "source": [
        "from itertools import *\n",
        "from more_itertools import *\n",
        "import numpy as np\n",
        "import networkx as nx\n",
        "import re\n",
        "from sympy.ntheory import factorint\n",
        "from collections import defaultdict"
      ],
      "execution_count": 138,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ixJTWQht7fVV"
      },
      "source": [
        "def main(input):\n",
        "  time, busses = input.split('\\n')\n",
        "  time = int(time)\n",
        "  busses = list(map(int, filter(lambda x: x != 'x', busses.split(','))))\n",
        "\n",
        "  min_val = np.inf\n",
        "  best_bus = None\n",
        "  for bus in busses:\n",
        "    val = bus - (time % bus)\n",
        "    if val == bus:\n",
        "      val = 0\n",
        "    if val < min_val:\n",
        "      min_val = val\n",
        "      best_bus = bus\n",
        "  \n",
        "  return best_bus * min_val"
      ],
      "execution_count": 139,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HPjAV-9CIRzR",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fc855c79-b05d-4c12-b1e6-f93ac49d277f"
      },
      "source": [
        "main(input)"
      ],
      "execution_count": 140,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "119"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 140
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SSavSblQ8z96"
      },
      "source": [
        "test_input = r'''939\r\n",
        "7,13,x,x,59,x,31,19'''"
      ],
      "execution_count": 141,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vAcv4QRsgBKl",
        "outputId": "6cc3cdec-6ab1-47d5-d8b7-5f074ef38644"
      },
      "source": [
        "main(test_input)"
      ],
      "execution_count": 142,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "295"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 142
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nEIDkFAps3YG"
      },
      "source": [
        "https://adventofcode.com/2020/day/13#part2"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "77lFS9zpgCGq"
      },
      "source": [
        "def is_true(time, busses, debug=False):\r\n",
        "  flag = True\r\n",
        "  for offset, bus in busses:\r\n",
        "    val = bus - (time % bus)\r\n",
        "    if val == bus:\r\n",
        "      val = 0\r\n",
        "    if debug:\r\n",
        "      print(offset, bus)\r\n",
        "    if not (val == offset):\r\n",
        "      return False\r\n",
        "  return True\r\n",
        "\r\n",
        "def main2(input):\r\n",
        "  time, busses = input.split('\\n')\r\n",
        "  time = int(time)\r\n",
        "  busses = list(map(lambda x: (x[0], int(x[1])), filter(lambda x: x[1] != 'x', enumerate(busses.split(',')))))\r\n",
        "  \r\n",
        "  for test_time in range(10000000000):\r\n",
        "    if is_true(test_time, busses):\r\n",
        "      return test_time\r\n",
        "\r\n",
        "  return 0"
      ],
      "execution_count": 143,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fMLY01ObipgY"
      },
      "source": [
        "test_input2 = r'''939\r\n",
        "17,x,13,19'''"
      ],
      "execution_count": 144,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "epDKAVUflxzv",
        "outputId": "3270dd95-eb1c-4a35-9ef9-6ff37991155d"
      },
      "source": [
        "main2(test_input2)"
      ],
      "execution_count": 145,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3417"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 145
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 306
        },
        "id": "HYNGTMbkhOWy",
        "outputId": "674b9e9e-0b32-45c1-ed0e-bd3e4aa6f5db"
      },
      "source": [
        "main2(input) # too long"
      ],
      "execution_count": 123,
      "outputs": [
        {
          "output_type": "error",
          "ename": "KeyboardInterrupt",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-123-42c62e2d11ab>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mmain2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minput\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# too long\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;32m<ipython-input-121-7486fc19d00c>\u001b[0m in \u001b[0;36mmain2\u001b[0;34m(input)\u001b[0m\n\u001b[1;32m     17\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     18\u001b[0m   \u001b[0;32mfor\u001b[0m \u001b[0mtest_time\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m10000000000\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 19\u001b[0;31m     \u001b[0;32mif\u001b[0m \u001b[0mis_true\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtest_time\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbusses\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     20\u001b[0m       \u001b[0;32mreturn\u001b[0m \u001b[0mtest_time\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     21\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-121-7486fc19d00c>\u001b[0m in \u001b[0;36mis_true\u001b[0;34m(time, busses, debug)\u001b[0m\n\u001b[1;32m      7\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mdebug\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      8\u001b[0m       \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0moffset\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbus\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 9\u001b[0;31m     \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mval\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0moffset\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     10\u001b[0m       \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;32mreturn\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5SrXe8HFmR0K"
      },
      "source": [
        "# This link describes an approach similar to ours.\r\n",
        "# (We didn't reference this during the competition though.)\r\n",
        "# https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Search_by_sieving\r\n",
        "\r\n",
        "def remap(offset, bus):\r\n",
        "  offset = offset % bus\r\n",
        "  val = bus - offset\r\n",
        "  if val == bus:\r\n",
        "    val = 0\r\n",
        "  return val\r\n",
        "\r\n",
        "def combine_constraints(bus1_val, bus1_num, bus2_val, bus2_num):\r\n",
        "  lcm = np.lcm(bus1_num, bus2_num)\r\n",
        "  faux_bus_num = lcm\r\n",
        "\r\n",
        "  # larger_bus = max(bus1_num, bus2_num)\r\n",
        "\r\n",
        "  for k in range(lcm // bus1_num):\r\n",
        "    if (bus1_num * k + bus1_val) % bus2_num == bus2_val:\r\n",
        "      faux_bus_val = bus1_num * k + bus1_val\r\n",
        "\r\n",
        "  return faux_bus_val, faux_bus_num\r\n",
        "\r\n",
        "def main4(input, debug=False):\r\n",
        "  time, busses = input.split('\\n')\r\n",
        "  time = int(time)\r\n",
        "  busses = list(map(lambda x: (x[0], int(x[1])), filter(lambda x: x[1] != 'x', enumerate(busses.split(',')))))\r\n",
        "  if debug:\r\n",
        "      print(busses)\r\n",
        "  busses = list(map(lambda x: (remap(x[0], x[1]), x[1]), busses))\r\n",
        "  if debug:\r\n",
        "      print(busses)\r\n",
        "\r\n",
        "  while len(busses) > 1:\r\n",
        "    if debug:\r\n",
        "      print(busses)\r\n",
        "    fbv, fbn = combine_constraints(busses[0][0], busses[0][1], busses[1][0], busses[1][1])\r\n",
        "    busses = [(fbv, fbn)] + busses[2:]\r\n",
        "  \r\n",
        "  return busses[0]"
      ],
      "execution_count": 146,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9CsKO0HArav-",
        "outputId": "1d689577-bcb3-418f-d7a3-b101e14e4ffd"
      },
      "source": [
        "main4(input, debug=True)"
      ],
      "execution_count": 147,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[(0, 23), (17, 37), (23, 863), (35, 19), (36, 13), (40, 17), (52, 29), (54, 571), (95, 41)]\n",
            "[(0, 23), (20, 37), (840, 863), (3, 19), (3, 13), (11, 17), (6, 29), (517, 571), (28, 41)]\n",
            "[(0, 23), (20, 37), (840, 863), (3, 19), (3, 13), (11, 17), (6, 29), (517, 571), (28, 41)]\n",
            "[(575, 851), (840, 863), (3, 19), (3, 13), (11, 17), (6, 29), (517, 571), (28, 41)]\n",
            "[(654994, 734413), (3, 19), (3, 13), (11, 17), (6, 29), (517, 571), (28, 41)]\n",
            "[(9467950, 13953847), (3, 13), (11, 17), (6, 29), (517, 571), (28, 41)]\n",
            "[(65283338, 181400011), (11, 17), (6, 29), (517, 571), (28, 41)]\n",
            "[(1153683404, 3083800187), (6, 29), (517, 571), (28, 41)]\n",
            "[(25824084900, 89430205423), (517, 571), (28, 41)]\n",
            "[(34367022967332, 51064647296533), (28, 41)]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(1106724616194525, 2093650539157853)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 147
        }
      ]
    }
  ]
}