Day15.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[![Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/oddrationale/AdventOfCode2020CSharp/main?urlpath=lab%2Ftree%2FDay15.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# --- Day 15: Rambunctious Recitation ---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\r\n",
       "<div>\r\n",
       "    <div id='dotnet-interactive-this-cell-8264.Microsoft.DotNet.Interactive.Http.HttpPort' style='display: none'>\r\n",
       "        The below script needs to be able to find the current output cell; this is an easy method to get it.\r\n",
       "    </div>\r\n",
       "    <script type='text/javascript'>\r\n",
       "async function probeAddresses(probingAddresses) {\r\n",
       "    function timeout(ms, promise) {\r\n",
       "        return new Promise(function (resolve, reject) {\r\n",
       "            setTimeout(function () {\r\n",
       "                reject(new Error('timeout'))\r\n",
       "            }, ms)\r\n",
       "            promise.then(resolve, reject)\r\n",
       "        })\r\n",
       "    }\r\n",
       "\r\n",
       "    if (Array.isArray(probingAddresses)) {\r\n",
       "        for (let i = 0; i < probingAddresses.length; i++) {\r\n",
       "\r\n",
       "            let rootUrl = probingAddresses[i];\r\n",
       "\r\n",
       "            if (!rootUrl.endsWith('/')) {\r\n",
       "                rootUrl = `${rootUrl}/`;\r\n",
       "            }\r\n",
       "\r\n",
       "            try {\r\n",
       "                let response = await timeout(1000, fetch(`${rootUrl}discovery`, {\r\n",
       "                    method: 'POST',\r\n",
       "                    cache: 'no-cache',\r\n",
       "                    mode: 'cors',\r\n",
       "                    timeout: 1000,\r\n",
       "                    headers: {\r\n",
       "                        'Content-Type': 'text/plain'\r\n",
       "                    },\r\n",
       "                    body: probingAddresses[i]\r\n",
       "                }));\r\n",
       "\r\n",
       "                if (response.status == 200) {\r\n",
       "                    return rootUrl;\r\n",
       "                }\r\n",
       "            }\r\n",
       "            catch (e) { }\r\n",
       "        }\r\n",
       "    }\r\n",
       "}\r\n",
       "\r\n",
       "function loadDotnetInteractiveApi() {\r\n",
       "    probeAddresses([\"http://192.168.86.66:1000/\", \"http://127.0.0.1:1000/\"])\r\n",
       "        .then((root) => {\r\n",
       "        // use probing to find host url and api resources\r\n",
       "        // load interactive helpers and language services\r\n",
       "        let dotnetInteractiveRequire = require.config({\r\n",
       "        context: '8264.Microsoft.DotNet.Interactive.Http.HttpPort',\r\n",
       "                paths:\r\n",
       "            {\r\n",
       "                'dotnet-interactive': `${root}resources`\r\n",
       "                }\r\n",
       "        }) || require;\r\n",
       "\r\n",
       "            window.dotnetInteractiveRequire = dotnetInteractiveRequire;\r\n",
       "\r\n",
       "            window.configureRequireFromExtension = function(extensionName, extensionCacheBuster) {\r\n",
       "                let paths = {};\r\n",
       "                paths[extensionName] = `${root}extensions/${extensionName}/resources/`;\r\n",
       "                \r\n",
       "                let internalRequire = require.config({\r\n",
       "                    context: extensionCacheBuster,\r\n",
       "                    paths: paths,\r\n",
       "                    urlArgs: `cacheBuster=${extensionCacheBuster}`\r\n",
       "                    }) || require;\r\n",
       "\r\n",
       "                return internalRequire\r\n",
       "            };\r\n",
       "        \r\n",
       "            dotnetInteractiveRequire([\r\n",
       "                    'dotnet-interactive/dotnet-interactive'\r\n",
       "                ],\r\n",
       "                function (dotnet) {\r\n",
       "                    dotnet.init(window);\r\n",
       "                },\r\n",
       "                function (error) {\r\n",
       "                    console.log(error);\r\n",
       "                }\r\n",
       "            );\r\n",
       "        })\r\n",
       "        .catch(error => {console.log(error);});\r\n",
       "    }\r\n",
       "\r\n",
       "// ensure `require` is available globally\r\n",
       "if ((typeof(require) !==  typeof(Function)) || (typeof(require.config) !== typeof(Function))) {\r\n",
       "    let require_script = document.createElement('script');\r\n",
       "    require_script.setAttribute('src', 'https://cdnjs.cloudflare.com/ajax/libs/require.js/2.3.6/require.min.js');\r\n",
       "    require_script.setAttribute('type', 'text/javascript');\r\n",
       "    \r\n",
       "    \r\n",
       "    require_script.onload = function() {\r\n",
       "        loadDotnetInteractiveApi();\r\n",
       "    };\r\n",
       "\r\n",
       "    document.getElementsByTagName('head')[0].appendChild(require_script);\r\n",
       "}\r\n",
       "else {\r\n",
       "    loadDotnetInteractiveApi();\r\n",
       "}\r\n",
       "\r\n",
       "    </script>\r\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "using System.IO;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "var startingNumbers = File.ReadAllText(@\"input/15.txt\").Split(\",\").Select(int.Parse).ToArray();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Per Numberphile, this is known as the [Van Eck Sequence](https://www.youtube.com/watch?v=etMJxB-igrc)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "IEnumerable<int> SayNumber(int[] startingNumbers)\n",
    "{\n",
    "    // key is the spoken number, value is the turn number\n",
    "    var spokenNumbers = new Dictionary<int, int>();\n",
    "    \n",
    "    // go through the starting numbers first except for the last number\n",
    "    for (var i = 0; i < startingNumbers.Length - 1; i++)\n",
    "    {\n",
    "        yield return startingNumbers[i];\n",
    "        spokenNumbers[startingNumbers[i]] = i + 1;\n",
    "    }\n",
    "    \n",
    "    // return the last number, but don't add it to the spoken numbers yet\n",
    "    yield return startingNumbers[^1];\n",
    "    \n",
    "    // initialize the while loop\n",
    "    var last = startingNumbers[^1];\n",
    "    var turn = startingNumbers.Length;\n",
    "    \n",
    "    while (true)\n",
    "    {\n",
    "        var next = spokenNumbers.ContainsKey(last) ? turn - spokenNumbers[last] : 0;\n",
    "        yield return next;\n",
    "        spokenNumbers[last] = turn++;\n",
    "        last = next;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\">447</div>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "Wall time: 135.8563ms"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#!time\n",
    "SayNumber(startingNumbers).ElementAt(2020 - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# --- Part Two ---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\">11721679</div>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "Wall time: 2700.1639ms"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#!time\n",
    "SayNumber(startingNumbers).ElementAt(30000000 - 1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".NET (C#)",
   "language": "C#",
   "name": ".net-csharp"
  },
  "language_info": {
   "file_extension": ".cs",
   "mimetype": "text/x-csharp",
   "name": "C#",
   "pygments_lexer": "csharp",
   "version": "8.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}