Day19.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%2FDay19.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# --- Day 19: Monster Messages ---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\r\n",
       "<div>\r\n",
       "    <div id='dotnet-interactive-this-cell-6832.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: '6832.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;\n",
    "using System.Text.RegularExpressions;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "var input = File.ReadAllText(@\"input/19.txt\").Split(\"\\n\\n\");\n",
    "var rules = input.First().Split(\"\\n\")\n",
    "    .Select(line => line.Split(\": \"))\n",
    "    .ToDictionary(s => Convert.ToInt32(s.First()), s => s.Last());\n",
    "var messages = input.Last().Split(\"\\n\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "Dictionary<int, string> ConvertRules2Regex(Dictionary<int, string> rules)\n",
    "{\n",
    "    // Make a copy of the rules so we don't override the original\n",
    "    var tempRules = new Dictionary<int, string>(rules);\n",
    "    var regexRules = new Dictionary<int, string>();\n",
    "    \n",
    "    // Rules that contain digits or contain the rule number itself\n",
    "    var finalRules = tempRules\n",
    "        .Where(kv => !Regex.IsMatch(kv.Value, @\"\\d\"))\n",
    "        .Where(kv => !Regex.IsMatch(kv.Value, $@\"\\b{kv.Key}\\b\"));\n",
    "    \n",
    "    while (finalRules.Any())\n",
    "    {\n",
    "        foreach (var kv in finalRules)\n",
    "        {\n",
    "            var regex = kv.Value.Replace(\"\\\"\", \"\").Replace(\" \", \"\");\n",
    "            regex = regex.Contains(\"|\") ? $\"({regex})\" : regex;\n",
    "\n",
    "            foreach (var key in tempRules.Keys)\n",
    "            {\n",
    "                tempRules[key] = Regex.Replace(tempRules[key], $@\"\\b{kv.Key}\\b\", regex);\n",
    "            }\n",
    "\n",
    "            regexRules.Add(kv.Key, regex);\n",
    "            tempRules.Remove(kv.Key);\n",
    "        }\n",
    "        finalRules = tempRules.Where(kv => !Regex.IsMatch(kv.Value, @\"\\d\")).ToArray();\n",
    "    }\n",
    "        \n",
    "    return regexRules;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "var regexRules = ConvertRules2Regex(rules);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(((((b(a(((bb|aa)b|bba)a|bbbb)|b(((ab|b(a|b))(a|b))b|(a(ab|b(a|b))|b(ba|aa))a))|a(a(a(((a|b)(a|b))b|(ab|aa)a)|b(b((a|b)b|aa)|a(ab|aa)))|b(a(((a|b)b|aa)a|(bb|aa)b)|b(b(ba|aa)|abb))))a|(a((b(b((a|b)(a|b))|aab)|a(bbb|a((a|b)(a|b))))b|(baaa|(bab|a(bb|ba))b)a)|b(a(((a|b)(ba|aa))b|(bba|(ab|b(a|b))b)a)|b((((a|b)b|aa)a|(ab|b(a|b))b)b|abba)))b)a|((a(b((a(ab|aa)|b(ab|bb))a|(b((a|b)b|aa)|aab)b)|a(a(b(ba|aa)|abb)|b((ba|aa)b|((a|b)b|aa)a)))|b(((b((a|b)b|aa)|aab)a|((ab|bb)b|((a|b)b|aa)a)b)a|(a(abb|bba)|b(aba|(ba|aa)b))b))a|(a(((b(ba|aa)|a(bb|aa))b|(b(ba|aa)|abb)a)a|(a(bba|bab)|b(aaa|b(ba|aa)))b)|b((b(((a|b)a|ab)a|((a|b)(a|b))b)|a(b((a|b)a|ab)|a(ab|b(a|b))))b|(((ab|bb)b|((a|b)b|aa)a)a|(a(bb|aa)|b(aa|b(a|b)))b)a))b)b))((((b(a(((bb|aa)b|bba)a|bbbb)|b(((ab|b(a|b))(a|b))b|(a(ab|b(a|b))|b(ba|aa))a))|a(a(a(((a|b)(a|b))b|(ab|aa)a)|b(b((a|b)b|aa)|a(ab|aa)))|b(a(((a|b)b|aa)a|(bb|aa)b)|b(b(ba|aa)|abb))))a|(a((b(b((a|b)(a|b))|aab)|a(bbb|a((a|b)(a|b))))b|(baaa|(bab|a(bb|ba))b)a)|b(a(((a|b)(ba|aa))b|(bba|(ab|b(a|b))b)a)|b((((a|b)b|aa)a|(ab|b(a|b))b)b|abba)))b)a|((a(b((a(ab|aa)|b(ab|bb))a|(b((a|b)b|aa)|aab)b)|a(a(b(ba|aa)|abb)|b((ba|aa)b|((a|b)b|aa)a)))|b(((b((a|b)b|aa)|aab)a|((ab|bb)b|((a|b)b|aa)a)b)a|(a(abb|bba)|b(aba|(ba|aa)b))b))a|(a(((b(ba|aa)|a(bb|aa))b|(b(ba|aa)|abb)a)a|(a(bba|bab)|b(aaa|b(ba|aa)))b)|b((b(((a|b)a|ab)a|((a|b)(a|b))b)|a(b((a|b)a|ab)|a(ab|b(a|b))))b|(((ab|bb)b|((a|b)b|aa)a)a|(a(bb|aa)|b(aa|b(a|b)))b)a))b)b)((b((((bbb|aaa)a|abbb)b|((aba|(ba|aa)b)b|(aab|b(ab|aa))a)a)b|((b(a(ab|bb)|baa)|a(b(ba|aa)|a(bb|aa)))a|((((a|b)(a|b))a|(bb|aa)b)a|((ab|b(a|b))b|(ab|aa)a)b)b)a)|a(a((b(a((a|b)a|ab)|bbb)|a(a((a|b)b|aa)|b((a|b)(a|b))))b|(a((ab|aa)a|(aa|b(a|b))b)|b(b(bb|aa)|abb))a)|b((a((ab|b(a|b))b|(bb|ba)a)|b((ab|bb)b|(bb|ba)a))b|(a(b((a|b)(a|b))|aab)|b(aaa|b(ab|aa)))a)))b|(a(b(a(b(bbb|a((a|b)(a|b)))|a((ba|ab)b|bba))|b(((a|b)(ba|aa))b|((ab|aa)a|(aa|b(a|b))b)a))|a(((b(ab|bb)|a(bb|ba))a|babb)a|(a((a|b)(ba|aa))|b((ba|aa)a|((a|b)a|ab)b))b))|b(a(b(a(((a|b)(a|b))a|(bb|aa)b)|b(aba|bbb))|a(a((aa|b(a|b))b|((a|b)b|aa)a)|b(((a|b)(a|b))a|(bb|aa)b)))|b(a(a((aa|b(a|b))b|((a|b)b|aa)a)|baab)|b(b(aab|b(ab|aa))|a(baa|((a|b)a|ab)b)))))a)))"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "regexRules[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\">299</div>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "messages.Where(m => Regex.IsMatch(m, $@\"^{regexRules[0]}$\")).Count()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# --- Part Two ---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For rule 11, use [balancing group definitions](https://docs.microsoft.com/en-us/dotnet/standard/base-types/grouping-constructs-in-regular-expressions#balancing-group-definitions)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(((b(a(((bb|aa)b|bba)a|bbbb)|b(((ab|b(a|b))(a|b))b|(a(ab|b(a|b))|b(ba|aa))a))|a(a(a(((a|b)(a|b))b|(ab|aa)a)|b(b((a|b)b|aa)|a(ab|aa)))|b(a(((a|b)b|aa)a|(bb|aa)b)|b(b(ba|aa)|abb))))a|(a((b(b((a|b)(a|b))|aab)|a(bbb|a((a|b)(a|b))))b|(baaa|(bab|a(bb|ba))b)a)|b(a(((a|b)(ba|aa))b|(bba|(ab|b(a|b))b)a)|b((((a|b)b|aa)a|(ab|b(a|b))b)b|abba)))b)a|((a(b((a(ab|aa)|b(ab|bb))a|(b((a|b)b|aa)|aab)b)|a(a(b(ba|aa)|abb)|b((ba|aa)b|((a|b)b|aa)a)))|b(((b((a|b)b|aa)|aab)a|((ab|bb)b|((a|b)b|aa)a)b)a|(a(abb|bba)|b(aba|(ba|aa)b))b))a|(a(((b(ba|aa)|a(bb|aa))b|(b(ba|aa)|abb)a)a|(a(bba|bab)|b(aaa|b(ba|aa)))b)|b((b(((a|b)a|ab)a|((a|b)(a|b))b)|a(b((a|b)a|ab)|a(ab|b(a|b))))b|(((ab|bb)b|((a|b)b|aa)a)a|(a(bb|aa)|b(aa|b(a|b)))b)a))b)b)+(?<open>(((b(a(((bb|aa)b|bba)a|bbbb)|b(((ab|b(a|b))(a|b))b|(a(ab|b(a|b))|b(ba|aa))a))|a(a(a(((a|b)(a|b))b|(ab|aa)a)|b(b((a|b)b|aa)|a(ab|aa)))|b(a(((a|b)b|aa)a|(bb|aa)b)|b(b(ba|aa)|abb))))a|(a((b(b((a|b)(a|b))|aab)|a(bbb|a((a|b)(a|b))))b|(baaa|(bab|a(bb|ba))b)a)|b(a(((a|b)(ba|aa))b|(bba|(ab|b(a|b))b)a)|b((((a|b)b|aa)a|(ab|b(a|b))b)b|abba)))b)a|((a(b((a(ab|aa)|b(ab|bb))a|(b((a|b)b|aa)|aab)b)|a(a(b(ba|aa)|abb)|b((ba|aa)b|((a|b)b|aa)a)))|b(((b((a|b)b|aa)|aab)a|((ab|bb)b|((a|b)b|aa)a)b)a|(a(abb|bba)|b(aba|(ba|aa)b))b))a|(a(((b(ba|aa)|a(bb|aa))b|(b(ba|aa)|abb)a)a|(a(bba|bab)|b(aaa|b(ba|aa)))b)|b((b(((a|b)a|ab)a|((a|b)(a|b))b)|a(b((a|b)a|ab)|a(ab|b(a|b))))b|(((ab|bb)b|((a|b)b|aa)a)a|(a(bb|aa)|b(aa|b(a|b)))b)a))b)b))+(?<close-open>((b((((bbb|aaa)a|abbb)b|((aba|(ba|aa)b)b|(aab|b(ab|aa))a)a)b|((b(a(ab|bb)|baa)|a(b(ba|aa)|a(bb|aa)))a|((((a|b)(a|b))a|(bb|aa)b)a|((ab|b(a|b))b|(ab|aa)a)b)b)a)|a(a((b(a((a|b)a|ab)|bbb)|a(a((a|b)b|aa)|b((a|b)(a|b))))b|(a((ab|aa)a|(aa|b(a|b))b)|b(b(bb|aa)|abb))a)|b((a((ab|b(a|b))b|(bb|ba)a)|b((ab|bb)b|(bb|ba)a))b|(a(b((a|b)(a|b))|aab)|b(aaa|b(ab|aa)))a)))b|(a(b(a(b(bbb|a((a|b)(a|b)))|a((ba|ab)b|bba))|b(((a|b)(ba|aa))b|((ab|aa)a|(aa|b(a|b))b)a))|a(((b(ab|bb)|a(bb|ba))a|babb)a|(a((a|b)(ba|aa))|b((ba|aa)a|((a|b)a|ab)b))b))|b(a(b(a(((a|b)(a|b))a|(bb|aa)b)|b(aba|bbb))|a(a((aa|b(a|b))b|((a|b)b|aa)a)|b(((a|b)(a|b))a|(bb|aa)b)))|b(a(a((aa|b(a|b))b|((a|b)b|aa)a)|baab)|b(b(aab|b(ab|aa))|a(baa|((a|b)a|ab)b)))))a))+(?(open)(?!))"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "var regexRules2 = ConvertRules2Regex(rules);\n",
    "regexRules2[8] = $\"{regexRules2[42]}+\";\n",
    "regexRules2[11] = $\"(?<open>{regexRules2[42]})+(?<close-open>{regexRules2[31]})+(?(open)(?!))\";\n",
    "regexRules2[0] = regexRules2[8] + regexRules2[11];\n",
    "regexRules2[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\">414</div>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "messages.Where(m => Regex.IsMatch(m, $@\"^{regexRules2[0]}$\")).Count()"
   ]
  }
 ],
 "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
}