{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 7: Lies, more lies and statistics\n",
    "\n",
    "- <https://adventofcode.com/2021/day/7>\n",
    "\n",
    "To get the optimal position for the crabs, we just need to move them all to the [median](https://en.wikipedia.org/wiki/Median) of their starting positions. Python makes this super-simple, just use [`staticstics.median()`](https://docs.python.org/3/library/statistics.html#statistics.median).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from statistics import median\n",
    "\n",
    "\n",
    "def optimal_fuel_cost(positions: list[int]) -> int:\n",
    "    target = int(median(positions))\n",
    "    return sum(abs(pos - target) for pos in positions)\n",
    "\n",
    "\n",
    "test_positions = [16, 1, 2, 0, 4, 2, 7, 1, 2, 14]\n",
    "assert optimal_fuel_cost(test_positions) == 37"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 339321\n"
     ]
    }
   ],
   "source": [
    "import aocd\n",
    "\n",
    "positions = [int(pos) for pos in aocd.get_data(day=7, year=2021).split(\",\")]\n",
    "print(\"Part 1:\", optimal_fuel_cost(positions))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2, more statistics\n",
    "\n",
    "The new best position is the (rounded) [mean](https://en.wikipedia.org/wiki/Mean) of their starting positions, and the fuel cost for a given crab to move to the new position can be calculated using the [triangle number formula](https://en.wikipedia.org/wiki/Triangular_number).\n",
    "\n",
    "That's because we are trying to minimize the sum over the triangle distances from crab positions $c$ to target position $t$ (you can ignore the division by two, it doesn't matter to the outcome):\n",
    "\n",
    "$$min_t \\sum_{i=1}^n \\frac {(|c_i - t|) (|c_i - t| + 1)} {2}$$\n",
    "\n",
    "and $(|c_i - t|) (|c_i - t| + 1)$ is _very_ close to $(c_i - t) ^ 2$. When solve for $t$ we get:\n",
    "\n",
    "$$t = \\frac {\\sum_{i=1}^n c_i} {n} + \\frac {\\sum_{i=1}^n sgn(c_i - t)} {2n}$$\n",
    "\n",
    "Here, the $sgn()$ function gives -1, 0 or 1 for negative, zero or positive outcomes of $c_i - t$. The first term in the sum is just the mean of the positions (the sum of all distances divided by $n$, the number of values). The other part is always going to be somewhere between -0.5 and +0.5 (the value will always lie between $\\frac {-n} {2n}$ and $\\frac {n} {2n}$)!\n",
    "\n",
    "So the trick lies in where to round off to; I simply round up and down (add `-0.5`, `0` or `0.5` and use `int()` to floor the value), and see which one is cheaper.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from statistics import mean\n",
    "\n",
    "\n",
    "def optimal_fuel_cost_triangle(positions: list[int]) -> int:\n",
    "    target = mean(positions)\n",
    "\n",
    "    def triangle(n: int) -> int:\n",
    "        return n * (n + 1) // 2\n",
    "\n",
    "    def summed_cost(t: int) -> int:\n",
    "        return sum(triangle(abs(pos - t)) for pos in positions)\n",
    "\n",
    "    return min(summed_cost(int(target + bias)) for bias in (-0.5, 0, 0.5))\n",
    "\n",
    "\n",
    "assert optimal_fuel_cost_triangle(test_positions) == 168"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 95476244\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", optimal_fuel_cost_triangle(positions))"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "b1b6870d1e0a983b1943c858d70ac8a7c80477f9f3ca364eb8daa198319a8a87"
  },
  "kernelspec": {
   "display_name": "Python 3.10.0 64-bit ('adventofcode-mOkh6lsX': pipenv)",
   "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.12.0"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}