day23.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "day1.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "metadata": {
        "id": "TZ5O20obUjg0",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## 💤 [Day 23](https://adventofcode.com/2018/day/23)"
      ]
    },
    {
      "metadata": {
        "id": "axCn6FNaUql6",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "import re\n",
        "import numpy as np\n",
        "\n",
        "def l1dist(A, B):\n",
        "  \"\"\"Manhattan distance\"\"\"\n",
        "  return np.sum(np.abs(A - B), axis=-1)\n",
        "\n",
        "\n",
        "def get_strongest_range(inputs):\n",
        "  \"\"\"Find number of nanobots in range of the bot with strongest range\"\"\"\n",
        "  strongest = np.argmax(inputs[:, -1])\n",
        "  strongest = inputs[strongest][None, :]\n",
        "  distances = l1dist(strongest[:, :-1], inputs[:, :-1])\n",
        "  return np.sum(distances <= strongest[0, -1])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "LqXBEfRttpFF",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "8ad62c58-b06f-4774-e926-768ff54b7d98"
      },
      "cell_type": "code",
      "source": [
        "with open('day23.txt', 'r') as f:\n",
        "  inputs = np.array([[- int(sub[1:]) if sub[0] == '-' else int(sub) \n",
        "                      for sub in re.split('<|,|>|=', line) if (sub.isdigit() or sub[1:].isdigit())]\n",
        "                     for line in f.read().splitlines() if line.strip()])\n",
        "  \n",
        "print('Nanobots in range of the strongest:', get_strongest_range(inputs))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Nanobots in range of the strongest: 248\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "gObkXQaS2a1E",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "For Part 2, we have to solve an optimization problem with a very large search space.\n",
        "The objective function is non-convex (L1 norm) so using techniques such as Gradient Descent does not give guarantees. However the problem can be phrases as a **Mixed Integer Linear Programming obejctive**:\n",
        "\n",
        "\\begin{align}\n",
        "\\arg\\max_{x, y, z} \\sum_{i = 1}^n [\\!| \\  |x - x_i| + |y - y_i| + |z - z_i| \\leq r_i \\ |\\!]\n",
        "\\end{align}\n",
        "\n",
        "Expressed as a constraint problem, this becomes:\n",
        "\n",
        "\\begin{align}\n",
        "\\arg\\max_{x, y, z}\\sum_{i = 1}^n c_i  \\mbox{        with }  c_i = 1 \\mbox{ if }  |x - x_i| + |y - y_i| + |z - z_i| \\leq r_i  \\mbox{ else } 0\n",
        "\\end{align}\n",
        "\n",
        "The constraint can be expressed using only linear terms using the facts that (i) [the conditional on $c_i$ can be expressed with a \"dummy\" large constant $K$](https://blog.adamfurmanek.pl/blog/2015/09/12/ilp-part-4/) and (ii) absolute values can be turned in 2 constraints (resulting in $8 = 2^3$ constraints for the sum of three absolute values):\n",
        "\n",
        "\\begin{align}\n",
        "0 \\leq c_i \\leq 1\\\\\n",
        "(x - x_i) + (y - y_i) + (z - z_i) \\leq r_i + K (1 - c)\\\\\n",
        "(x - x_i) + (y - y_i) - (z - z_i) \\leq r_i + K (1 - c)\\\\\n",
        "(x - x_i) - (y - y_i) + (z - z_i) \\leq r_i + K (1 - c)\\\\\n",
        "(x - x_i) - (y - y_i) - (z - z_i) \\leq r_i + K (1 - c)\\\\\n",
        "- (x - x_i) + (y - y_i) + (z - z_i) \\leq r_i + K (1 - c)\\\\\n",
        "- (x - x_i) + (y - y_i) - (z - z_i) \\leq r_i + K (1 - c)\\\\\n",
        "- (x - x_i) - (y - y_i) + (z - z_i) \\leq r_i + K (1 - c)\\\\\n",
        "- (x - x_i) - (y - y_i) - (z - z_i) \\leq r_i + K (1 - c)\\\\\n",
        "\\end{align}\n",
        "\n",
        "We can use the [```PulP```](https://pythonhosted.org/PuLP/main/installing_pulp_at_home.html)  library to solve this problem"
      ]
    },
    {
      "metadata": {
        "id": "YkgOLi3_sAhz",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        },
        "outputId": "a3339897-2b6f-4094-bb3d-0af3ee589867"
      },
      "cell_type": "code",
      "source": [
        "import pulp\n",
        "\n",
        "def get_widest_in_range(inputs, K=10000000000):\n",
        "  \"\"\"Integer optimization problem using PuLP.\n",
        "    Using simpler techniques (e.g. gradient descent) does not have strong guarantees since the loss \n",
        "    function is non-convex (L1) and risk of falling in local maxima\"\"\"\n",
        "  \n",
        "  # Variables\n",
        "  mins = np.amin(inputs[:, :-1], axis=0)\n",
        "  maxs = np.amax(inputs[:, :-1], axis=0)\n",
        "  lp_problem = pulp.LpProblem(\"Nanobots Problem\", pulp.LpMaximize)\n",
        "  x = pulp.LpVariable('x', cat='Integer')\n",
        "  y = pulp.LpVariable('y', cat='Integer')\n",
        "  z = pulp.LpVariable('z', cat='Integer')\n",
        "  counts = [pulp.LpVariable('c_%d' % i, lowBound=0, upBound=1, cat='Integer') for i in range(len(inputs))]\n",
        "  \n",
        "  # Main objective\n",
        "  lp_problem += sum(counts), \"Z\"\n",
        "  \n",
        "  # Add constraints (note that 0 <= c <= 1 constraints are already included)\n",
        "  for i, (xi, yi, zi, ri) in enumerate(inputs):\n",
        "    lp_problem += (x - xi) + (y - yi) + (z - zi) <= ri + K * (1 - counts[i])\n",
        "    lp_problem += (x - xi) + (y - yi) - (z - zi) <= ri + K * (1 - counts[i])\n",
        "    lp_problem += (x - xi) - (y - yi) + (z - zi) <= ri + K * (1 - counts[i])\n",
        "    lp_problem += (x - xi) - (y - yi) - (z - zi) <= ri + K * (1 - counts[i])\n",
        "    lp_problem += - (x - xi) + (y - yi) + (z - zi) <= ri + K * (1 - counts[i])\n",
        "    lp_problem += - (x - xi) + (y - yi) - (z - zi) <= ri + K * (1 - counts[i])\n",
        "    lp_problem += - (x - xi) - (y - yi) + (z - zi) <= ri + K * (1 - counts[i])\n",
        "    lp_problem += - (x - xi) - (y - yi) - (z - zi) <= ri + K * (1 - counts[i])\n",
        "    \n",
        "  # Solve\n",
        "  lp_problem.solve()\n",
        "  print('Solved status:', pulp.LpStatus[lp_problem.status])\n",
        "  print('Optimal point: (%d, %d, %d)' % (x.varValue, y.varValue, z.varValue))\n",
        "  print('Distance to origin: %d' % \n",
        "        (np.abs(x.varValue) + np.abs(y.varValue) + np.abs(z.varValue)))\n",
        "  return lp_problem\n",
        "  \n",
        "_ = get_widest_in_range(inputs, K=1000000000)"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Solved status: Optimal\n",
            "Optimal point: (23700389, 42553861, 58368752)\n",
            "Distance to origin: 124623002\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}