18.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from scipy.signal import convolve\n",
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = open(\"inputs/18.input\").read().strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = \"\"\"\n",
    ".#.#...|#.\n",
    ".....#|##|\n",
    ".|..|...#.\n",
    "..|#.....#\n",
    "#.#|||#|#|\n",
    "...#.||...\n",
    ".|....|...\n",
    "||...#|.#|\n",
    "|.||||..|.\n",
    "...#.|..|.\n",
    "\"\"\".strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "field = np.asarray([[c for c in line] for line in data.split(\"\\n\")])\n",
    "orig_field = field"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "def show(field):\n",
    "    return \"\\n\".join([\"\".join([str(c) for c in r]) for r in field])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tick(field):\n",
    "    ground, trees, lumber = [(field == ch).astype(np.int) for ch in [\".\", \"|\", \"#\"]]\n",
    "    adjacent = np.array([[1, 1, 1], \n",
    "                         [1, 0, 1], \n",
    "                         [1, 1, 1]])\n",
    "\n",
    "    adj_ground, adj_trees, adj_lumber = [convolve(f, adjacent, \"same\") for f in [ground, trees, lumber]]\n",
    "\n",
    "    new_field = field.copy()\n",
    "    # the rules:\n",
    "    new_field[(field == \".\") & (adj_trees >= 3)] = \"|\"\n",
    "    new_field[(field == \"|\") & (adj_lumber >= 3)] = \"#\"\n",
    "    new_field[(field == \"#\") & ((adj_lumber == 0) | (adj_trees == 0))] = \".\"\n",
    "    return new_field"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "def resource_val(field):\n",
    "    return (field==\"|\").sum() * (field==\"#\").sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "539682\n"
     ]
    }
   ],
   "source": [
    "field = orig_field.copy()\n",
    "\n",
    "for t in range(10):\n",
    "    field = tick(field)\n",
    "\n",
    "print(resource_val(field))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [],
   "source": [
    "it = 1000000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loop detected: every 28 min\n"
     ]
    }
   ],
   "source": [
    "field = orig_field.copy()\n",
    "\n",
    "# do 1000 iterations\n",
    "i = 1000\n",
    "for _ in range(i):\n",
    "    field = tick(field)\n",
    "\n",
    "before_val = resource_val(field)\n",
    "while before_val != resource_val(field) or i == 1000:\n",
    "    field = tick(field)\n",
    "    i = i+1\n",
    "\n",
    "loop = i - 1000\n",
    "print(f\"Loop detected: every {loop} min\")\n",
    "\n",
    "# assert the loop is indeed correct\n",
    "for _ in range(loop):\n",
    "    field = tick(field)\n",
    "\n",
    "assert resource_val(field) == before_val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now calculate an earlier moment which has the same state as the one after 1000000000 min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "metadata": {},
   "outputs": [],
   "source": [
    "diff = (it - 1000)%loop\n",
    "assert (it - 1000 - diff)%loop == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This means that after 1000000000 minutes the value will be exactly the same as after (1000 + diff) minutes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "226450\n"
     ]
    }
   ],
   "source": [
    "field = orig_field.copy()\n",
    "for _ in range(1000 + diff):\n",
    "    field = tick(field)\n",
    "print(resource_val(field))"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}