Day 19.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 19\n",
    "\n",
    "https://adventofcode.com/2020/day/19"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1\n",
    "\n",
    "After several attempts, ultimately I reckon I cannot solve it withour using regexp. so I need to learn the basics..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 412,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 412,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Here's how I can use a rule as a regexp, using the OR sign and parentheses...\n",
    "import re\n",
    "bool(re.fullmatch('a(b|a)','aa'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 453,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getRules(p):\n",
    "    \n",
    "    # store rules in dictionary with rule number as key (as a string)\n",
    "    rules = {}\n",
    "    for l in p:\n",
    "        i, r = l.split(\": \")\n",
    "        rules[i] = r.replace('\"','')\n",
    "    \n",
    "    # add parentesys (and space to that later split will work) if there's an OR symbol in rule.\n",
    "    for r in rules.keys():\n",
    "        if \"|\" in rules[r]:\n",
    "            rules[r] = \"( \"+rules[r]+\" )\"\n",
    "\n",
    "    return rules\n",
    "        \n",
    "\n",
    "def solveRules(rules,debug=False):\n",
    "\n",
    "    # dictionay of solved rules\n",
    "    rules_solved = {}\n",
    "\n",
    "    while '0' not in rules_solved.keys():\n",
    "\n",
    "        for k in rules.keys():\n",
    "            if k in rules_solved.keys():\n",
    "                continue\n",
    "\n",
    "            r = rules[k]        \n",
    "            if not re.findall(\"[0-9]\",rules[k]): # rule is solved, store it\n",
    "                rules_solved[k] = r\n",
    "            else: # otherwise see whether I can replace rule number with corresponding rule\n",
    "                l = r.split(\" \")\n",
    "                for i in range(len(l)):\n",
    "                    j = l[i]\n",
    "                    if j in rules_solved.keys():\n",
    "                        l[i] = rules_solved[j] \n",
    "                nr = \"\" # reform rule string after replacements\n",
    "                for j in l:\n",
    "                    nr += j+\" \"\n",
    "                nr = nr[:-1] # remove last white space\n",
    "                rules[k] = nr\n",
    "        if debug:     \n",
    "            print(len(rules),len(rules_solved))\n",
    "            print(rules['0'].replace(\" \",\"\"))\n",
    "\n",
    "    return rules_solved"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 520,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution Part 1 = 126\n"
     ]
    }
   ],
   "source": [
    "#filename = \"data/day19test1.txt\"\n",
    "filename = \"data/input19.txt\"\n",
    "\n",
    "with open(filename) as f:\n",
    "    p = [b.split(\"\\n\") for b in f.read().split(\"\\n\\n\")]\n",
    "\n",
    "messages = p[1][:-1]\n",
    "rules = getRules(p[0])\n",
    "rules_solved = solveRules(rules)\n",
    "\n",
    "rule0 = rules_solved['0'].replace(\" \",\"\") # remove all white spaces from rule 0\n",
    "#print(rule0)\n",
    "\n",
    "import re\n",
    "match = sum( [ bool(re.fullmatch(rule0, m)) for m in messages ] )\n",
    "print('Solution Part 1 =',match)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 521,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution Test 2 = 3\n"
     ]
    }
   ],
   "source": [
    "filename = \"data/day19test2.txt\"\n",
    "\n",
    "with open(filename) as f:\n",
    "    p = [b.split(\"\\n\") for b in f.read().split(\"\\n\\n\")]\n",
    "\n",
    "messages = p[1][:-1]\n",
    "rules = getRules(p[0])\n",
    "rules_solved = solveRules(rules)\n",
    "\n",
    "rule0 = rules_solved['0'].replace(\" \",\"\") # remove all white spaces from rule 0\n",
    "#print(rule0)\n",
    "\n",
    "match = sum( [ bool(re.fullmatch(rule0, m)) for m in messages ] )\n",
    "print('Solution Test 2 =',match)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Notes\n",
    "\n",
    "* There seem to be only rule 0 to depend on rule 8 and rule 11, so loop only happens there\n",
    "* I can begin toremove rules 0, 8 and 11 from `rules`, and attempt to solve all others since they should not be affected by loop. I can probably use the same solving routine than in Part 1, but with a different ending condition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 604,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8 11 (42 | 42 8) (42 31 | 42 11 31)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'42 31'"
      ]
     },
     "execution_count": 604,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "filename = \"data/day19test2.txt\"\n",
    "\n",
    "with open(filename) as f:\n",
    "    p = [b.split(\"\\n\") for b in f.read().split(\"\\n\\n\")]\n",
    "\n",
    "messages = p[1][:-1]\n",
    "rules = getRules(p[0])\n",
    "\n",
    "# New rules\n",
    "r0 = rules['0']\n",
    "r8 = \"(42 | 42 8)\" # 8\n",
    "r11 = \"(42 31 | 42 11 31)\" # 11\n",
    "\n",
    "print(r0,r8,r11)\n",
    "\n",
    "rules.pop('0')\n",
    "rules.pop('8')\n",
    "rules.pop('11')\n",
    "\n",
    "#rules"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 605,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solveRules2(rules,debug=False):\n",
    "\n",
    "    # dictionay of solved rules\n",
    "    rules_solved = {}\n",
    "\n",
    "    while len(rules) !=len(rules_solved): # change condition wrt to Part 1, now looking to solve all rules\n",
    "        \n",
    "        for k in rules.keys():\n",
    "            if k in rules_solved.keys():\n",
    "                continue\n",
    "\n",
    "            r = rules[k]        \n",
    "            if not re.findall(\"[0-9]\",rules[k]): # rule is solved, store it\n",
    "                rules_solved[k] = r\n",
    "            else: # otherwise see whether I can replace rule number with corresponding rule\n",
    "                l = r.split(\" \")\n",
    "                for i in range(len(l)):\n",
    "                    j = l[i]\n",
    "                    if j in rules_solved.keys():\n",
    "                        l[i] = rules_solved[j] \n",
    "                nr = \"\" # reform rule string after replacements\n",
    "                for j in l:\n",
    "                    nr += j+\" \"\n",
    "                nr = nr[:-1] # remove last white space\n",
    "                rules[k] = nr\n",
    "    \n",
    "        #print(len(rules),len(rules_solved))\n",
    "\n",
    "    return rules_solved"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 606,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "42: ( ( b ( a ( b b | a b ) | b ( a | b ) ( a | b ) ) | a ( b b b | a ( b b | a ( a | b ) ) ) ) b | ( ( ( a a | a b ) a | b b b ) b | ( ( a | b ) a | b b ) a a ) a )\n",
      "31: ( b ( b ( a b a | b a a ) | a ( b ( a b | ( a | b ) a ) | a ( b a | a b ) ) ) | a ( b ( ( a b | ( a | b ) a ) b | ( ( a | b ) a | b b ) a ) | a ( b a b | ( b a | b b ) a ) ) )\n"
     ]
    }
   ],
   "source": [
    "rules_solved = solveRules2(rules)\n",
    "print(\"42:\", rules_solved['42'])\n",
    "print(\"31:\", rules_solved['31'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the puzzle test:\n",
    "\n",
    "> it might help to start by looking at which rules always match the same set of values and how those rules (especially rules 42 and 31) are used by the new versions of rules 8 and 11.\n",
    "\n",
    "Now I have solved rules 42 and 31, all the ingredients needed to build rules 8 and 11 and therefore rule 0.\n",
    "\n",
    "`0: 8 11`\n",
    "\n",
    "`8: 42 | 42 8`\n",
    "\n",
    "`42 31 | 42 11 31`\n",
    "\n",
    "Rule 8 is itself or itself repeated...\n",
    "\n",
    "Rule 11 is `42+31` or `42+42+31+31` or `42+42+42+32+31+31` and so on... \n",
    "\n",
    "(after some studyin of regexp...)\n",
    "\n",
    "For Rule 8 can use the RE `+` symbol on Rule 42.\n",
    "\n",
    "For Rule 11 I can use `{m}` to repeate rules 42 and 31 `m` times.\n",
    "\n",
    "Note that for Rule 8 there's nothing more to be done since `+` takes care of everything, while for Rule 11 I need to make a loop over `m` and count how many expressions match as a function of `m`, hoping that at some point the number stabilizes..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 608,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3 9 6\n",
      "3 2 11 9\n",
      "4 1 12 11\n",
      "5 0 12 12\n",
      "Solution Test 2 after replacing = 12\n"
     ]
    }
   ],
   "source": [
    "# Rule 8 with +\n",
    "# ==> + Causes the resulting RE to match 1 or more repetitions of the preceding RE\n",
    "rules_solved['8'] = rules_solved['42']+ '+'\n",
    "    \n",
    "# Rule 11 with variable {n}, to be replaced during counting by numerical values\n",
    "# ==> {m} Specifies that exactly m copies of the previous RE should be matched; \n",
    "#     fewer matches cause the entire RE not to match. \n",
    "rules_solved['11'] = rules_solved['42'] + r'{m}' + rules_solved['31'] + r'{m}'\n",
    "\n",
    "# Rule 0\n",
    "rules_solved['0'] = rules_solved['8']+rules_solved['11']\n",
    "\n",
    "# Being with 1 repetition to initialize counter\n",
    "n = 1\n",
    "rule0 = rules_solved['0'].replace(\" \",\"\").replace('m',str(n)) \n",
    "count_all = sum([bool(re.fullmatch(rule0, m)) for m in messages])\n",
    "count_pre = 0\n",
    "\n",
    "# Increase RE repetitions untile number of matched expression saturates to asymptotic value\n",
    "while count_pre != count_all:\n",
    "    count_pre = count_all\n",
    "    n += 1\n",
    "    rule0 = rules_solved['0'].replace(\" \",\"\").replace('m',str(n)) # increase regex repetition\n",
    "    count_n = sum([bool(re.fullmatch(rule0, m)) for m in messages])\n",
    "    count_all += count_n\n",
    "    print(n,count_n,count_all,count_pre)\n",
    "\n",
    "print('Solution Test 2 after replacing =',count_all)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 609,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution Part 2 after replacing = 282\n"
     ]
    }
   ],
   "source": [
    "filename = \"data/input19.txt\"\n",
    "\n",
    "with open(filename) as f:\n",
    "    p = [b.split(\"\\n\") for b in f.read().split(\"\\n\\n\")]\n",
    "\n",
    "messages = p[1][:-1]\n",
    "rules = getRules(p[0])\n",
    "rules.pop('0')\n",
    "rules.pop('8')\n",
    "rules.pop('11')\n",
    "rules_solved = solveRules2(rules)\n",
    "\n",
    "rules_solved['8'] = rules_solved['42']+ '+'\n",
    "rules_solved['11'] = rules_solved['42'] + r'{m}' + rules_solved['31'] + r'{m}'\n",
    "rules_solved['0'] = rules_solved['8']+rules_solved['11']\n",
    "\n",
    "n = 1\n",
    "rule0 = rules_solved['0'].replace(\" \",\"\").replace('m',str(n)) \n",
    "count_all = sum([bool(re.fullmatch(rule0, m)) for m in messages])\n",
    "count_pre = 0\n",
    "\n",
    "while count_pre != count_all:\n",
    "    count_pre = count_all\n",
    "    n += 1\n",
    "    rule0 = rules_solved['0'].replace(\" \",\"\").replace('m',str(n))\n",
    "    count_n = sum([bool(re.fullmatch(rule0, m)) for m in messages])\n",
    "    count_all += count_n\n",
    "\n",
    "print('Solution Part 2 after replacing =',count_all)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.9.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}