12_chaos_orbits.ipynb

{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.7.1"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3
 },
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "import itertools as it\n",
    "\n",
    "with open('inputs/12.txt') as file:\n",
    "    input = file.read()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "[[0, 4, 0], [-10, -6, -14], [9, -16, -3], [6, -1, 2]]"
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coords = list(map((lambda s:list(map(int, re.findall(r'-?\\d+', s)))),input.split('\\n')))\n",
    "coords\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "Wall time: 24.9 ms\n"
    },
    {
     "data": {
      "text/plain": "13500"
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "moons = [[coord,[0]*3] for coord in coords]\n",
    "\n",
    "for step in range(1000):\n",
    "    for a,b in it.permutations(moons,2):\n",
    "        a[1] = [v+(p<s)-(p>s) for v,p,s in zip(a[1],a[0],b[0])]\n",
    "    for m in moons:\n",
    "        m[0] = [p+v for p,v in zip(m[0],m[1])]\n",
    "\n",
    "sum(sum(map(abs,m[0]))*sum(map(abs,m[1])) for m in moons)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "oh f#ck! \"Of course, the universe might last for a very long time before repeating.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "loop [[0, 0], [-10, 0], [9, 0], [6, 0]] 286332\nloop [[4, 0], [-6, 0], [-16, 0], [-1, 0]] 161428\nloop [[0, 0], [-14, 0], [-3, 0], [2, 0]] 96236\nWall time: 3.71 s\n"
    },
    {
     "data": {
      "text/plain": "278013787106916"
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "# the trick is: movements in x, y and z are uncorrelated, so we can find 3 separate loops.\n",
    "\n",
    "planes = [[[coord[i],0] for coord in coords] for i in range(3)]\n",
    "\n",
    "def gcd(a,b):\n",
    "    if a == 0:\n",
    "        return b\n",
    "    return gcd(b%a,a)\n",
    "\n",
    "loop = 1\n",
    "for plane in planes:\n",
    "    state = repr(plane)\n",
    "    step = 0\n",
    "    while 1:\n",
    "        step += 1\n",
    "        for a,b in it.permutations(plane,2):\n",
    "            a[1] += (a[0]<b[0])-(a[0]>b[0])\n",
    "        for m in plane:\n",
    "            m[0] += m[1]\n",
    "        if state == repr(plane):\n",
    "            print('loop',plane,step)\n",
    "            loop = (step*loop//gcd(step,loop))\n",
    "            break\n",
    "\n",
    "loop\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}