AdventOfCode/Advent_Day_3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 3](http://adventofcode.com/2017/day/3): Spiral Memory\n",
    "\n",
    "Numbers are arranged in a spiral\n",
    "\n",
    "    17  16  15  14  13\n",
    "    18   5   4   3  12\n",
    "    19   6   1   2  11\n",
    "    20   7   8   9  10\n",
    "    21  22  23---> ...\n",
    "    \n",
    "Given an integer n, what is its Manhattan Distance from the center (1) of the spiral? For instance, the distance of 3 is $2 = 1 + 1$, since it's one space to the right and one space up from the center.\n",
    "\n",
    "Here's my idea. The bottom right corner of the $k$th layer is the integer $(2k+1)^2$, since that's how many integers are contained within that square. The other three corners in that layer are $(2k+1)^2 - 2k, (2k+1)^2 - 4k$, and $(2k+1)^2 - 6k$. Finally, the closest spot on the $k$th layer to the origin is at distance $k$: these are the four \"axis locations\" halfway between the corners, at $(2k+1)^2 - k, (2k+1)^2 - 3k, (2k+1)^2 - 5k$, and $(2k+1)^2 - 7k$.\n",
    "\n",
    "For instance when $k = 1$, the bottom right is $(2 + 1)^2 = 9$, and the four \"axis locations\" are $9 - 1, 9 - 3, 9-5$, and $9-7$. The \"axis locations\" are $k$ away, and the corners are $2k$ away.\n",
    "\n",
    "So I will first find which layer the number is on. Then I'll figure out which side it's on, and then how far away it is from the nearest \"axis location\" or \"corner\".\n",
    "\n",
    "My given number happens to be 289326."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def find_lowest_larger_odd_square(n):\n",
    "    upper = math.ceil(n**.5)\n",
    "    if upper %2 == 0:\n",
    "        upper += 1\n",
    "    return upper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert find_lowest_larger_odd_square(39) == 7\n",
    "assert find_lowest_larger_odd_square(26) == 7\n",
    "assert find_lowest_larger_odd_square(25) == 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "539"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_lowest_larger_odd_square(289326)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1195"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "539**2 - 289326"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It happens to be that our integer is very close to an odd square.\n",
    "The square is $539^2$, and the distance to that square is $538$ from the center.\n",
    "\n",
    "Note that $539 = 2(269) + 1$, so this is the $269$th layer of the square.\n",
    "The previous corner to $539^2$ is $539^2 - 538$, and the previous corner to that is $539^2 - 2\\cdot538 = 539^2 - 1076$.\n",
    "This is the nearest corner.\n",
    "How far away from the square is this corner?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "119"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "539**2 - 2*538 - 289326"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's really close to the corner. The corner is $538$ from the center, and the square is $119$ steps closer to the center. So the distance in this case is $538 - 119$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "419"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "538 - 119"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And so we solved the first part quickly with a mixture of function and handiwork.\n",
    "\n",
    "# Part 2\n",
    "\n",
    "In part two, the spiral has changed significantly. Build the spiral iteratively. Initially, start with 1. Then in the next square of the spiral, put in the integer that is the sum of the adjacent (including diagonal) numbers in the spiral. This spiral is\n",
    "\n",
    "    147  142  133  122   59\n",
    "    304    5    4    2   57\n",
    "    330   10    1    1   54\n",
    "    351   11   23   25   26\n",
    "    362  747  806--->   ...\n",
    "    \n",
    "What is the first value that's larger than 289326?\n",
    "\n",
    "My plan is to construct this spiral. The central 1 will have coordinates (0,0), and the spiral will be stored in a dictionary whose key is the tuple of the location.\n",
    "\n",
    "To construct the spiral, we note that the direction of adding goes in the pattern RULLDDRRRUUULLLLDDDD. The order is right, up, left, down: the number of times each direction is repeated goes in the sequence 1,1,2,2,3,3,4,4,...."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "spiral = {}\n",
    "spiral[(0,0)] = 1\n",
    "\n",
    "NEIGHBORS = [(1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1)]\n",
    "DIRECTION = [(1,0), (0,1), (-1,0), (0,-1)] #Right Up Left Down\n",
    "\n",
    "def spiral_until_at_least(n):\n",
    "    spiral = {}               # Spiral dictionary\n",
    "    spiral[(0,0)] = 1\n",
    "    x,y = 0,0\n",
    "    steps_in_row = 1          # times spiral extends in same direction\n",
    "    second_direction = False  # spiral extends in same direction twice: False if first leg, True if second\n",
    "    nstep = 0                 # number of steps in current direction\n",
    "    step_direction = 0        # index of direction in DIRECTION\n",
    "    \n",
    "    while True:\n",
    "        dx, dy = DIRECTION[step_direction]\n",
    "        x, y = x + dx, y + dy\n",
    "        total = 0\n",
    "        for neighbor in NEIGHBORS:\n",
    "            nx, ny = neighbor\n",
    "            if (x+nx, y+ny) in spiral:\n",
    "                total += spiral[(x+nx, y+ny)]\n",
    "                \n",
    "        print(\"X: {}, Y:{}, Total:{}\".format(x,y,total))\n",
    "        \n",
    "        if total > n:\n",
    "            return total\n",
    "        spiral[(x,y)] = total\n",
    "        nstep += 1\n",
    "        if nstep == steps_in_row:\n",
    "            nstep = 0\n",
    "            step_direction = (step_direction + 1)% 4\n",
    "            if second_direction:\n",
    "                second_direction = False\n",
    "                steps_in_row += 1\n",
    "            else:\n",
    "                second_direction = True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X: 1, Y:0, Total:1\n",
      "X: 1, Y:1, Total:2\n",
      "X: 0, Y:1, Total:4\n",
      "X: -1, Y:1, Total:5\n",
      "X: -1, Y:0, Total:10\n",
      "X: -1, Y:-1, Total:11\n",
      "X: 0, Y:-1, Total:23\n",
      "X: 1, Y:-1, Total:25\n",
      "X: 2, Y:-1, Total:26\n",
      "X: 2, Y:0, Total:54\n",
      "X: 2, Y:1, Total:57\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "57"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spiral_until_at_least(55)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X: 1, Y:0, Total:1\n",
      "X: 1, Y:1, Total:2\n",
      "X: 0, Y:1, Total:4\n",
      "X: -1, Y:1, Total:5\n",
      "X: -1, Y:0, Total:10\n",
      "X: -1, Y:-1, Total:11\n",
      "X: 0, Y:-1, Total:23\n",
      "X: 1, Y:-1, Total:25\n",
      "X: 2, Y:-1, Total:26\n",
      "X: 2, Y:0, Total:54\n",
      "X: 2, Y:1, Total:57\n",
      "X: 2, Y:2, Total:59\n",
      "X: 1, Y:2, Total:122\n",
      "X: 0, Y:2, Total:133\n",
      "X: -1, Y:2, Total:142\n",
      "X: -2, Y:2, Total:147\n",
      "X: -2, Y:1, Total:304\n",
      "X: -2, Y:0, Total:330\n",
      "X: -2, Y:-1, Total:351\n",
      "X: -2, Y:-2, Total:362\n",
      "X: -1, Y:-2, Total:747\n",
      "X: 0, Y:-2, Total:806\n",
      "X: 1, Y:-2, Total:880\n",
      "X: 2, Y:-2, Total:931\n",
      "X: 3, Y:-2, Total:957\n",
      "X: 3, Y:-1, Total:1968\n",
      "X: 3, Y:0, Total:2105\n",
      "X: 3, Y:1, Total:2275\n",
      "X: 3, Y:2, Total:2391\n",
      "X: 3, Y:3, Total:2450\n",
      "X: 2, Y:3, Total:5022\n",
      "X: 1, Y:3, Total:5336\n",
      "X: 0, Y:3, Total:5733\n",
      "X: -1, Y:3, Total:6155\n",
      "X: -2, Y:3, Total:6444\n",
      "X: -3, Y:3, Total:6591\n",
      "X: -3, Y:2, Total:13486\n",
      "X: -3, Y:1, Total:14267\n",
      "X: -3, Y:0, Total:15252\n",
      "X: -3, Y:-1, Total:16295\n",
      "X: -3, Y:-2, Total:17008\n",
      "X: -3, Y:-3, Total:17370\n",
      "X: -2, Y:-3, Total:35487\n",
      "X: -1, Y:-3, Total:37402\n",
      "X: 0, Y:-3, Total:39835\n",
      "X: 1, Y:-3, Total:42452\n",
      "X: 2, Y:-3, Total:45220\n",
      "X: 3, Y:-3, Total:47108\n",
      "X: 4, Y:-3, Total:48065\n",
      "X: 4, Y:-2, Total:98098\n",
      "X: 4, Y:-1, Total:103128\n",
      "X: 4, Y:0, Total:109476\n",
      "X: 4, Y:1, Total:116247\n",
      "X: 4, Y:2, Total:123363\n",
      "X: 4, Y:3, Total:128204\n",
      "X: 4, Y:4, Total:130654\n",
      "X: 3, Y:4, Total:266330\n",
      "X: 2, Y:4, Total:279138\n",
      "X: 1, Y:4, Total:295229\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "295229"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spiral_until_at_least(289326)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mathematical Outerlude\n",
    "\n",
    "The sequence in the part 2 grows really, really quickly. The sequence starts 1,1,2,4,5,10,11,23...\n",
    "Many mathematicians (recreational, amateur, and professional alike) often delight in properties of sequences of integers. And sometimes they put them in Sloane's **Online Encyclopedia of Integer Sequences**, the OEIS. Miraculously, the sequence from part 2 appears in the OEIS.\n",
    "It's [OEIS A141481](https://oeis.org/A141481).\n",
    "\n",
    "But I've never seen this sequence before.\n",
    "I wonder: how quickly does it grow? This is one of the most fundamantal questions one can ask about a sequence.\n",
    "Clearly it grows quickly --- the entries are strictly increasing, and after each corner they roughly double (since the adjacent and diagonal are each there and roughly the same size). \n",
    "But does this capture most of the growth?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "spiral = {}\n",
    "spiral[(0,0)] = 1\n",
    "\n",
    "NEIGHBORS = [(1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1)]\n",
    "DIRECTION = [(1,0), (0,1), (-1,0), (0,-1)] #Right Up Left Down\n",
    "\n",
    "CORNERS = [1]\n",
    "\n",
    "def spiral_until_at_least_print_corners(n):\n",
    "    spiral = {}               # Spiral dictionary\n",
    "    spiral[(0,0)] = 1\n",
    "    x,y = 0,0\n",
    "    steps_in_row = 1          # times spiral extends in same direction\n",
    "    second_direction = False  # spiral extends in same direction twice: False if first leg, True if second\n",
    "    nstep = 0                 # number of steps in current direction\n",
    "    step_direction = 0        # index of direction in DIRECTION\n",
    "    \n",
    "    while True:\n",
    "        dx, dy = DIRECTION[step_direction]\n",
    "        x, y = x + dx, y + dy\n",
    "        total = 0\n",
    "        for neighbor in NEIGHBORS:\n",
    "            nx, ny = neighbor\n",
    "            if (x+nx, y+ny) in spiral:\n",
    "                total += spiral[(x+nx, y+ny)]\n",
    "                \n",
    "        if total > n:\n",
    "            return total\n",
    "        spiral[(x,y)] = total\n",
    "        nstep += 1\n",
    "        if nstep == steps_in_row:\n",
    "            print(\"X: {}, Y:{}, Total:{}\".format(x,y,total))\n",
    "            CORNERS.append(total)\n",
    "            nstep = 0\n",
    "            step_direction = (step_direction + 1)% 4\n",
    "            if second_direction:\n",
    "                second_direction = False\n",
    "                steps_in_row += 1\n",
    "            else:\n",
    "                second_direction = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X: 1, Y:0, Total:1\n",
      "X: 1, Y:1, Total:2\n",
      "X: -1, Y:1, Total:5\n",
      "X: -1, Y:-1, Total:11\n",
      "X: 2, Y:-1, Total:26\n",
      "X: 2, Y:2, Total:59\n",
      "X: -2, Y:2, Total:147\n",
      "X: -2, Y:-2, Total:362\n",
      "X: 3, Y:-2, Total:957\n",
      "X: 3, Y:3, Total:2450\n",
      "X: -3, Y:3, Total:6591\n",
      "X: -3, Y:-3, Total:17370\n",
      "X: 4, Y:-3, Total:48065\n",
      "X: 4, Y:4, Total:130654\n",
      "X: -4, Y:4, Total:369601\n",
      "X: -4, Y:-4, Total:1026827\n",
      "X: 5, Y:-4, Total:2957731\n",
      "X: 5, Y:5, Total:8391037\n",
      "X: -5, Y:5, Total:24612291\n",
      "X: -5, Y:-5, Total:71138314\n",
      "X: 6, Y:-5, Total:211906819\n",
      "X: 6, Y:6, Total:622599690\n",
      "X: -6, Y:6, Total:1881661363\n",
      "X: -6, Y:-6, Total:5614313360\n",
      "X: 7, Y:-6, Total:17197809473\n",
      "X: 7, Y:7, Total:52035339395\n",
      "X: -7, Y:7, Total:161377186945\n",
      "X: -7, Y:-7, Total:494675470203\n",
      "X: 8, Y:-7, Total:1552158495650\n",
      "X: 8, Y:8, Total:4816175781069\n",
      "X: -8, Y:8, Total:15277743850220\n",
      "X: -8, Y:-8, Total:47947180112774\n",
      "X: 9, Y:-8, Total:153672147749041\n",
      "X: 9, Y:9, Total:487485542154934\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1009266205008841"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spiral_until_at_least_print_corners(10**15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this version, I've added in a print statement at each corner, to see the growth. The sequence grows really, really quickly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 1,\n",
       " 2,\n",
       " 5,\n",
       " 11,\n",
       " 26,\n",
       " 59,\n",
       " 147,\n",
       " 362,\n",
       " 957,\n",
       " 2450,\n",
       " 6591,\n",
       " 17370,\n",
       " 48065,\n",
       " 130654,\n",
       " 369601,\n",
       " 1026827,\n",
       " 2957731,\n",
       " 8391037,\n",
       " 24612291,\n",
       " 71138314,\n",
       " 211906819,\n",
       " 622599690,\n",
       " 1881661363,\n",
       " 5614313360,\n",
       " 17197809473,\n",
       " 52035339395,\n",
       " 161377186945,\n",
       " 494675470203,\n",
       " 1552158495650,\n",
       " 4816175781069,\n",
       " 15277743850220,\n",
       " 47947180112774,\n",
       " 153672147749041,\n",
       " 487485542154934]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CORNERS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n",
      "2.0\n",
      "2.5\n",
      "2.2\n",
      "2.3636363636363638\n",
      "2.269230769230769\n",
      "2.4915254237288136\n",
      "2.4625850340136055\n",
      "2.643646408839779\n",
      "2.560083594566353\n",
      "2.690204081632653\n",
      "2.635411925352754\n",
      "2.7671272308578008\n",
      "2.7182773327785292\n",
      "2.8288533072083517\n",
      "2.7782040633006946\n",
      "2.8804569805819287\n",
      "2.8369844992664985\n",
      "2.933164399108239\n",
      "2.890357260931134\n",
      "2.978800130123972\n",
      "2.9380823747819083\n",
      "3.022265178127538\n",
      "2.9837001866525545\n",
      "3.0632079775824983\n",
      "3.025695771120955\n",
      "3.101299786285366\n",
      "3.065337050221315\n",
      "3.137730874371112\n",
      "3.102889166645396\n",
      "3.1721732230522837\n",
      "3.1383678495227265\n",
      "3.2050299389369084\n",
      "3.1722439576431065\n"
     ]
    }
   ],
   "source": [
    "for a, b in zip(CORNERS, CORNERS[1:]):\n",
    "    print(b/a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It appears that the size of the $(n+1)$st corner is roughly $\\lambda$ times the size of the $n$th corner, where $\\lambda \\geq 2.5$. It actually appears like $\\lambda$ grows slowly with $n$ (which makes some sense, as the lengths between each corner is increasing with each layer of the spiral). It would be interesting if one could actually show that this growth rate appears to be consistent, and if one could grasp how $\\lambda$ behaves with $n$. But I'm not sure how to do that."
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}