day19.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import scipy as sc\n",
    "import re"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [],
   "source": [
    "file19 = open('./input_files/day19_input', 'r') \n",
    "input19_lines = file19.readlines() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_rules(rules):\n",
    "        \n",
    "    if '\"a\"' in rules:\n",
    "        return ['a']\n",
    "    elif '\"b\"' in rules:\n",
    "        return ['b']\n",
    "    else:\n",
    "        rules_idx = re.findall(r'\\d+', rules)\n",
    "        return [int(r) for r in rules_idx]\n",
    "    \n",
    "def subst_list(main, origin, subst):\n",
    "    \"\"\" Subsitutes every occurace of 'origin' in main with subst. \"\"\"\n",
    "    eq_origin = [e == origin for e in main]\n",
    "    \n",
    "    new_main = list(main)\n",
    "    for idx, eq in enumerate(eq_origin):\n",
    "        if eq:\n",
    "            new_main = new_main[:idx] + subst + new_main[idx+1:]\n",
    "    \n",
    "    return new_main"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of path splits in rule book: 115\n",
      "Length of longest messagae: 88\n"
     ]
    }
   ],
   "source": [
    "## Create Rules table\n",
    "rules_nbr = []\n",
    "rules_table = []\n",
    "for line in input19_lines[:131]:\n",
    "    \n",
    "    line = line.replace('\\n', '')\n",
    "    nbr, rules = line.split(':')\n",
    "\n",
    "    rules_nbr += [int(nbr)]\n",
    "    \n",
    "    if '|' in rules:\n",
    "        rules_split = rules.split('|')\n",
    "    else:\n",
    "        rules_split = [rules]\n",
    "    \n",
    "    rl_list = []\n",
    "    for rl in rules_split:\n",
    "        rl_list += [split_rules(rl)]\n",
    "    \n",
    "    rules_table += [rl_list]\n",
    "    \n",
    "rules_nbr  = np.array(rules_nbr)\n",
    "sorted_idx = np.argsort(rules_nbr)\n",
    "\n",
    "rules_table = [rules_table[idx] for idx in sorted_idx]\n",
    "print('Number of path splits in rule book:', sum([len(rule) > 1 for rule in rules_table]))\n",
    "\n",
    "# Read messages\n",
    "messages = []\n",
    "for line in input19_lines[132:]:\n",
    "    \n",
    "    line = line.replace('\\n', '')\n",
    "    messages += [line]\n",
    "    \n",
    "MAX_SEQ_LENGTH = max([len(m) for m in messages])\n",
    "print('Length of longest messagae:',  MAX_SEQ_LENGTH)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8796093022208"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2**43"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[[4, 1, 5]],\n",
       " [[2, 3], [3, 2]],\n",
       " [[4, 4], [5, 5]],\n",
       " [[4, 5], [5, 4]],\n",
       " [['a']],\n",
       " [['b']]]"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rules_table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [],
   "source": [
    "def next_branch(path_id):\n",
    "\n",
    "    bin_path_id = list(bin(path_id)[2:])\n",
    "    bin_path_id = [int(s) for s in bin_path_id]\n",
    "    \n",
    "    for direction in reversed(bin_path_id):\n",
    "        yield direction\n",
    "\n",
    "    while True:\n",
    "        yield 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [],
   "source": [
    "def walk_tree(init_rule_seq, rule_book, path_generator):\n",
    "    \"\"\" Walk the subsitiution rule tree recursively along a trajectory given by path_nbr \"\"\"\n",
    "    \n",
    "    rule_seq = list(init_rule_seq)\n",
    "    while (not all([(e == 'a') | (e == 'b') for e in rule_seq])):\n",
    "    \n",
    "        new_rule_seq = list(rule_seq)\n",
    "        for rule in rule_seq:\n",
    "            if (rule == 'a') | (rule == 'b'):\n",
    "                continue\n",
    "            else:                \n",
    "                subs_rules = rule_book[rule]\n",
    "                if len(subs_rules) == 1:\n",
    "                    new_rule_seq = subst_list(new_rule_seq, rule, subs_rules[0])\n",
    "                elif len(subs_rules) == 2:\n",
    "                    new_rule_seq = subst_list(new_rule_seq, rule, subs_rules[next(path_generator)])\n",
    "                else:\n",
    "                    print('Error: Nbr of subst rules > 2. Len =', len(subs_rule), subs_rule)\n",
    "                    \n",
    "        rule_seq = list(new_rule_seq)\n",
    "        if len(rule_seq) > MAX_SEQ_LENGTH:\n",
    "            return ''\n",
    "        \n",
    "    return ''.join(rule_seq)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 \t \n",
      "1 \t aaaabbabababbabbbababbabaabbabbabababaaaabababbaabab\n",
      "2 \t aaabaaaaaaaaaaaaaaaaaabaabaaaaaabaaabaaabaaaaaabaaabaaaabaaaaaaaabbabbbababbaabab\n",
      "3 \t \n",
      "4 \t \n",
      "5 \t aaaabbabababbabbbababbabaabbabbaabaaaaabbbabbaa\n",
      "6 \t aaabaaaaaaaaaaaaaaaaaabaabaaaaaabaaabaaabaaaaaabaaabaaaabaaaaaaaabbabbbbbabbaa\n",
      "7 \t \n",
      "8 \t bbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbabbbbbbbbbbabbbbabbbbaaabaaaaaabbaabab\n",
      "9 \t bbabababaaabbabbaabaaaaabababbaabab\n"
     ]
    }
   ],
   "source": [
    "init_rule_seq = rules_table[0][0]\n",
    "\n",
    "for path_id in range(10):\n",
    "    code = walk_tree(init_rule_seq, rules_table, next_branch(path_id))\n",
    "    print(path_id, '\\t', code)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'aaaabbabababbabbbababbabaabbabbabababaaaabababbaabab'"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "walk_tree(init_rule_seq, rules_table, next_branch(8796093022209))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'valid_message' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-124-f872e4873f39>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mmessage\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mmessages\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m     \u001b[0;32mwhile\u001b[0m \u001b[0mmessage\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mvalid_message\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      5\u001b[0m         \u001b[0mvalid_message\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mwalk_tree\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minit_rule_seq\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mrules_table\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mnext_branch\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m8796093022208\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m         \u001b[0;31m#print(path_id, '\\t', valid_message)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'valid_message' is not defined"
     ]
    }
   ],
   "source": [
    "# Check which of the messages are valid. That is\n",
    "for message in messages:\n",
    "    \n",
    "    while message != valid_message:\n",
    "        valid_message = walk_tree(init_rule_seq, rules_table, next_branch(path_id))\n",
    "        #print(path_id, '\\t', valid_message)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Old method: attempt to make all possible strings that fullfil the rules."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rule_seq_list = list(rules_table[0])\n",
    "rule_seq_flat = [False]*len(rule_seq_list)\n",
    "total_ab = sum(rule_seq_flat)\n",
    "idx = 0\n",
    "\n",
    "new_rule_seq_list = list([rule_seq_list])\n",
    "while total_ab != len(rule_seq_flat):\n",
    "\n",
    "    print(idx, '  -  ', rule_seq_list)   \n",
    "    \n",
    "    new_rule_seq_list = []\n",
    "    for rule_seq_idx, rule_seq in enumerate(rule_seq_list):\n",
    "        \n",
    "        # Subsitute all rules that do not contain a split.\n",
    "        new_rule_seq = list(rule_seq)\n",
    "        for rule_idx, rule in enumerate(rule_seq):\n",
    "            if (rule == 'a') | (rule == 'b'):\n",
    "                continue\n",
    "            else:                \n",
    "                subs_rules = rules_table[rule]\n",
    "                if len(subs_rules) == 1:\n",
    "                    new_rule_seq = subst_list(new_rule_seq, rule, subs_rules[0])\n",
    "        \n",
    "        # Subsitute all rules that split.\n",
    "        temp_nrs_list = [new_rule_seq]\n",
    "        for rule_idx, rule in enumerate(rule_seq):\n",
    "            if (rule == 'a') | (rule == 'b'):\n",
    "                continue\n",
    "            else:                \n",
    "                subs_rules = rules_table[rule]\n",
    "                if len(subs_rules) == 2:\n",
    "                    temp = []\n",
    "                    for nrs in temp_nrs_list:\n",
    "                        new_rule_seq1 = subst_list(nrs, rule, subs_rules[0])\n",
    "                        new_rule_seq2 = subst_list(nrs, rule, subs_rules[1])\n",
    "                        temp += [new_rule_seq1]\n",
    "                        temp += [new_rule_seq2]\n",
    "                    \n",
    "                    temp_nrs_list = list(temp)\n",
    "                    \n",
    "        new_rule_seq_list += temp_nrs_list\n",
    "                    \n",
    "    #print(new_rule_seq_list)\n",
    "                        \n",
    "    rule_seq_list = list(new_rule_seq_list)\n",
    "    rule_seq_flat = [(l == 'a') | (l == 'b') for ll in rule_seq_list for l in ll]\n",
    "    total_ab = sum(rule_seq_flat)\n",
    "    \n",
    "    idx += 1\n",
    "    \n",
    "new_rule_seq_list"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}