Day16.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "571255d2-7bab-457f-ae95-82559d01d0b0",
   "metadata": {},
   "source": [
    "<h2>--- Day 16: Packet Decoder ---</h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7a3f76c-cab3-4f6f-a28b-13b69ccc798a",
   "metadata": {},
   "source": [
    "[![Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/oddrationale/AdventOfCode2021FSharp/main?urlpath=lab%2Ftree%2FDay16.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73bcba6b",
   "metadata": {},
   "source": [
    "<p>As you leave the cave and reach open waters, you receive a transmission from the Elves back on the ship.</p>\n",
    "<p>The transmission was sent using the Buoyancy Interchange Transmission System (<span title=\"Just be glad it wasn't sent using the BuoyancY Transmission Encoding System.\">BITS</span>), a method of packing numeric expressions into a binary sequence. Your submarine's computer has saved the transmission in <a href=\"https://en.wikipedia.org/wiki/Hexadecimal\" target=\"_blank\">hexadecimal</a> (your puzzle input).</p>\n",
    "<p>The first step of decoding the message is to convert the hexadecimal representation into binary. Each character of hexadecimal corresponds to four bits of binary data:</p>\n",
    "<pre><code>0 = 0000\n",
    "1 = 0001\n",
    "2 = 0010\n",
    "3 = 0011\n",
    "4 = 0100\n",
    "5 = 0101\n",
    "6 = 0110\n",
    "7 = 0111\n",
    "8 = 1000\n",
    "9 = 1001\n",
    "A = 1010\n",
    "B = 1011\n",
    "C = 1100\n",
    "D = 1101\n",
    "E = 1110\n",
    "F = 1111\n",
    "</code></pre>\n",
    "<p>The BITS transmission contains a single <em>packet</em> at its outermost layer which itself contains many other packets. The hexadecimal representation of this packet might encode a few extra <code>0</code> bits at the end; these are not part of the transmission and should be ignored.</p>\n",
    "<p>Every packet begins with a standard header: the first three bits encode the packet <em>version</em>, and the next three bits encode the packet <em>type ID</em>. These two values are numbers; all numbers encoded in any packet are represented as binary with the most significant bit first. For example, a version encoded as the binary sequence <code>100</code> represents the number <code>4</code>.</p>\n",
    "<p>Packets with type ID <code>4</code> represent a <em>literal value</em>. Literal value packets encode a single binary number. To do this, the binary number is padded with leading zeroes until its length is a multiple of four bits, and then it is broken into groups of four bits. Each group is prefixed by a <code>1</code> bit except the last group, which is prefixed by a <code>0</code> bit. These groups of five bits immediately follow the packet header. For example, the hexadecimal string <code>D2FE28</code> becomes:</p>\n",
    "<pre><code>110100101111111000101000\n",
    "VVVTTTAAAAABBBBBCCCCC\n",
    "</code></pre>\n",
    "<p>Below each bit is a label indicating its purpose:</p>\n",
    "<ul>\n",
    "<li>The three bits labeled <code>V</code> (<code>110</code>) are the packet version, <code>6</code>.</li>\n",
    "<li>The three bits labeled <code>T</code> (<code>100</code>) are the packet type ID, <code>4</code>, which means the packet is a literal value.</li>\n",
    "<li>The five bits labeled <code>A</code> (<code>10111</code>) start with a <code>1</code> (not the last group, keep reading) and contain the first four bits of the number, <code>0111</code>.</li>\n",
    "<li>The five bits labeled <code>B</code> (<code>11110</code>) start with a <code>1</code> (not the last group, keep reading) and contain four more bits of the number, <code>1110</code>.</li>\n",
    "<li>The five bits labeled <code>C</code> (<code>00101</code>) start with a <code>0</code> (last group, end of packet) and contain the last four bits of the number, <code>0101</code>.</li>\n",
    "<li>The three unlabeled <code>0</code> bits at the end are extra due to the hexadecimal representation and should be ignored.</li>\n",
    "</ul>\n",
    "<p>So, this packet represents a literal value with binary representation <code>011111100101</code>, which is <code>2021</code> in decimal.</p>\n",
    "<p>Every other type of packet (any packet with a type ID other than <code>4</code>) represent an <em>operator</em> that performs some calculation on one or more sub-packets contained within. Right now, the specific operations aren't important; focus on parsing the hierarchy of sub-packets.</p>\n",
    "<p>An operator packet contains one or more packets. To indicate which subsequent binary data represents its sub-packets, an operator packet can use one of two modes indicated by the bit immediately after the packet header; this is called the <em>length type ID</em>:</p>\n",
    "<ul>\n",
    "<li>If the length type ID is <code>0</code>, then the next <em>15</em> bits are a number that represents the <em>total length in bits</em> of the sub-packets contained by this packet.</li>\n",
    "<li>If the length type ID is <code>1</code>, then the next <em>11</em> bits are a number that represents the <em>number of sub-packets immediately contained</em> by this packet.</li>\n",
    "</ul>\n",
    "<p>Finally, after the length type ID bit and the 15-bit or 11-bit field, the sub-packets appear.</p>\n",
    "<p>For example, here is an operator packet (hexadecimal string <code>38006F45291200</code>) with length type ID <code>0</code> that contains two sub-packets:</p>\n",
    "<pre><code>00111000000000000110111101000101001010010001001000000000\n",
    "VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB\n",
    "</code></pre>\n",
    "<ul>\n",
    "<li>The three bits labeled <code>V</code> (<code>001</code>) are the packet version, <code>1</code>.</li>\n",
    "<li>The three bits labeled <code>T</code> (<code>110</code>) are the packet type ID, <code>6</code>, which means the packet is an operator.</li>\n",
    "<li>The bit labeled <code>I</code> (<code>0</code>) is the length type ID, which indicates that the length is a 15-bit number representing the number of bits in the sub-packets.</li>\n",
    "<li>The 15 bits labeled <code>L</code> (<code>000000000011011</code>) contain the length of the sub-packets in bits, <code>27</code>.</li>\n",
    "<li>The 11 bits labeled <code>A</code> contain the first sub-packet, a literal value representing the number <code>10</code>.</li>\n",
    "<li>The 16 bits labeled <code>B</code> contain the second sub-packet, a literal value representing the number <code>20</code>.</li>\n",
    "</ul>\n",
    "<p>After reading 11 and 16 bits of sub-packet data, the total length indicated in <code>L</code> (27) is reached, and so parsing of this packet stops.</p>\n",
    "<p>As another example, here is an operator packet (hexadecimal string <code>EE00D40C823060</code>) with length type ID <code>1</code> that contains three sub-packets:</p>\n",
    "<pre><code>11101110000000001101010000001100100000100011000001100000\n",
    "VVVTTTILLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCC\n",
    "</code></pre>\n",
    "<ul>\n",
    "<li>The three bits labeled <code>V</code> (<code>111</code>) are the packet version, <code>7</code>.</li>\n",
    "<li>The three bits labeled <code>T</code> (<code>011</code>) are the packet type ID, <code>3</code>, which means the packet is an operator.</li>\n",
    "<li>The bit labeled <code>I</code> (<code>1</code>) is the length type ID, which indicates that the length is a 11-bit number representing the number of sub-packets.</li>\n",
    "<li>The 11 bits labeled <code>L</code> (<code>00000000011</code>) contain the number of sub-packets, <code>3</code>.</li>\n",
    "<li>The 11 bits labeled <code>A</code> contain the first sub-packet, a literal value representing the number <code>1</code>.</li>\n",
    "<li>The 11 bits labeled <code>B</code> contain the second sub-packet, a literal value representing the number <code>2</code>.</li>\n",
    "<li>The 11 bits labeled <code>C</code> contain the third sub-packet, a literal value representing the number <code>3</code>.</li>\n",
    "</ul>\n",
    "<p>After reading 3 complete sub-packets, the number of sub-packets indicated in <code>L</code> (3) is reached, and so parsing of this packet stops.</p>\n",
    "<p>For now, parse the hierarchy of the packets throughout the transmission and <em>add up all of the version numbers</em>.</p>\n",
    "<p>Here are a few more examples of hexadecimal-encoded transmissions:</p>\n",
    "<ul>\n",
    "<li><code>8A004A801A8002F478</code> represents an operator packet (version 4) which contains an operator packet (version 1) which contains an operator packet (version 5) which contains a literal value (version 6); this packet has a version sum of <code><em>16</em></code>.</li>\n",
    "<li><code>620080001611562C8802118E34</code> represents an operator packet (version 3) which contains two sub-packets; each sub-packet is an operator packet that contains two literal values. This packet has a version sum of <code><em>12</em></code>.</li>\n",
    "<li><code>C0015000016115A2E0802F182340</code> has the same structure as the previous example, but the outermost packet uses a different length type ID. This packet has a version sum of <code><em>23</em></code>.</li>\n",
    "<li><code>A0016C880162017C3686B18A3D4780</code> is an operator packet that contains an operator packet that contains an operator packet that contains five literal values; it has a version sum of <code><em>31</em></code>.</li>\n",
    "</ul>\n",
    "<p>Decode the structure of your hexadecimal-encoded BITS transmission; <em>what do you get if you add up the version numbers in all packets?</em></p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3d2fe85",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let input = File.ReadAllText @\"input/16.txt\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d347b76e",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "type Packet = \n",
    "    | LiteralValue of LiteralValue\n",
    "    | Operation of Operation\n",
    "\n",
    "and LiteralValue = {\n",
    "    Version: int\n",
    "    TypeID: int\n",
    "    Value: int64\n",
    "}\n",
    "\n",
    "and Operation = {\n",
    "    Version: int\n",
    "    TypeID: int\n",
    "    LengthTypeID: int\n",
    "    Length: int\n",
    "    Packets: Packet list\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e75dafc9",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let toBStr xStr =\n",
    "    xStr\n",
    "    |> Seq.map string\n",
    "    |> Seq.map (fun xStr -> Int32.Parse(xStr, System.Globalization.NumberStyles.HexNumber))\n",
    "    |> Seq.map (fun num -> Convert.ToString(num, 2))\n",
    "    |> Seq.map (fun bStr -> bStr.PadLeft(4, '0'))\n",
    "    |> String.Concat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75319160",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let rec getPacketStrings (bStr: string) = \n",
    "\n",
    "    let literalValueSubString (bStr: string) = \n",
    "        let last = \n",
    "            bStr.[6..]\n",
    "            |> Seq.chunkBySize 5\n",
    "            |> Seq.takeWhile (fun chunk -> chunk.[0] = '1')\n",
    "            |> Seq.length\n",
    "            |> fun count -> 6 + ((count + 1) * 5) - 1\n",
    "        bStr.[..last], bStr.[last + 1..]\n",
    "\n",
    "    let operationSubString (bStr: string) = \n",
    "        let lengthTypeID = Convert.ToInt32(bStr.[6] |> string)\n",
    "        let length = \n",
    "            match lengthTypeID with\n",
    "            | 0 -> Convert.ToInt32(bStr.[7..21], 2)\n",
    "            | 1 -> Convert.ToInt32(bStr.[7..17], 2)\n",
    "            | _ -> failwith \"Invalid Length Type ID.\"\n",
    "        let last = \n",
    "            match lengthTypeID with\n",
    "            | 0 -> 21 + length\n",
    "            | 1 -> 17 + (bStr.[18..] |> getPacketStrings |> Seq.truncate length |> Seq.concat |> Seq.length)\n",
    "            | _ -> failwith \"Invalid Length Type ID.\"\n",
    "        bStr.[..last], bStr.[last + 1..]\n",
    "\n",
    "    let rec split (bStr: string) = \n",
    "        seq {\n",
    "            if bStr.Length < 11 then\n",
    "                yield None\n",
    "            else \n",
    "                let typeID = Convert.ToInt32(bStr.[3..5], 2)\n",
    "                let (subString, rest) = \n",
    "                    match typeID with\n",
    "                    | 4 -> literalValueSubString bStr\n",
    "                    | _ -> operationSubString bStr\n",
    "                yield Some subString\n",
    "                yield! split rest\n",
    "        }\n",
    "\n",
    "    bStr\n",
    "    |> split\n",
    "    |> Seq.choose id"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72adb728",
   "metadata": {},
   "outputs": [],
   "source": [
    "let rec parse (bStr: string) : seq<Packet> = \n",
    "\n",
    "    let parseLiteralValue (bStr: string) =\n",
    "        {\n",
    "            Version = Convert.ToInt32(bStr.[..2], 2)\n",
    "            TypeID = Convert.ToInt32(bStr.[3..5], 2)\n",
    "            Value = \n",
    "                bStr.[6..]\n",
    "                |> Seq.chunkBySize 5\n",
    "                |> Seq.filter (fun chunk -> chunk.Length = 5)\n",
    "                |> Seq.map (fun chunk -> chunk.[1..])\n",
    "                |> Seq.concat\n",
    "                |> fun chars -> chars |> Seq.toArray |> String\n",
    "                |> fun bstr -> Convert.ToInt64(bstr, 2)\n",
    "        }\n",
    "\n",
    "    let parseOperation (bStr: string) =\n",
    "        let lengthTypeID = Convert.ToInt32(bStr.[6] |> string)\n",
    "        {\n",
    "            Version = Convert.ToInt32(bStr.[..2], 2)\n",
    "            TypeID = Convert.ToInt32(bStr.[3..5], 2)\n",
    "            LengthTypeID = lengthTypeID\n",
    "            Length = \n",
    "                match lengthTypeID with\n",
    "                | 0 -> Convert.ToInt32(bStr.[7..21], 2)\n",
    "                | 1 -> Convert.ToInt32(bStr.[7..17], 2)\n",
    "                | _ -> failwith \"Invalid Length Type ID.\"\n",
    "            Packets = \n",
    "                match lengthTypeID with\n",
    "                | 0 -> bStr.[22..] |> parse |> Seq.toList\n",
    "                | 1 -> bStr.[18..] |> parse |> Seq.toList\n",
    "                | _ -> failwith \"Invalid Length Type ID.\"\n",
    "        }\n",
    "\n",
    "    bStr\n",
    "    |> getPacketStrings\n",
    "    |> Seq.map (fun packetString -> \n",
    "        let typeID = Convert.ToInt32(packetString.[3..5], 2)\n",
    "        match typeID with\n",
    "        | 4 -> packetString |> parseLiteralValue |> LiteralValue\n",
    "        | _ -> packetString |> parseOperation |> Operation)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca7c6c5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "let rec versionNumbers (packet: Packet) = \n",
    "    seq {\n",
    "        match packet with\n",
    "        | LiteralValue p -> yield p.Version\n",
    "        | Operation p -> \n",
    "            yield p.Version\n",
    "            yield! p.Packets |> Seq.map versionNumbers |> Seq.concat\n",
    "    }\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\">974</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Wall time: 8.8598ms"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#!time\n",
    "input\n",
    "|> toBStr\n",
    "|> parse\n",
    "|> Seq.exactlyOne\n",
    "|> versionNumbers\n",
    "|> Seq.sum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "845efdd9-7742-41e1-889d-dc706863d93d",
   "metadata": {},
   "source": [
    "<h2 id=\"part2\">--- Part Two ---</h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6207d17",
   "metadata": {},
   "source": [
    "<p>Now that you have the structure of your transmission decoded, you can calculate the value of the expression it represents.</p>\n",
    "<p>Literal values (type ID <code>4</code>) represent a single number as described above. The remaining type IDs are more interesting:</p>\n",
    "<ul>\n",
    "<li>Packets with type ID <code>0</code> are <em>sum</em> packets - their value is the sum of the values of their sub-packets. If they only have a single sub-packet, their value is the value of the sub-packet.</li>\n",
    "<li>Packets with type ID <code>1</code> are <em>product</em> packets - their value is the result of multiplying together the values of their sub-packets. If they only have a single sub-packet, their value is the value of the sub-packet.</li>\n",
    "<li>Packets with type ID <code>2</code> are <em>minimum</em> packets - their value is the minimum of the values of their sub-packets.</li>\n",
    "<li>Packets with type ID <code>3</code> are <em>maximum</em> packets - their value is the maximum of the values of their sub-packets.</li>\n",
    "<li>Packets with type ID <code>5</code> are <em>greater than</em> packets - their value is <em>1</em> if the value of the first sub-packet is greater than the value of the second sub-packet; otherwise, their value is <em>0</em>. These packets always have exactly two sub-packets.</li>\n",
    "<li>Packets with type ID <code>6</code> are <em>less than</em> packets - their value is <em>1</em> if the value of the first sub-packet is less than the value of the second sub-packet; otherwise, their value is <em>0</em>. These packets always have exactly two sub-packets.</li>\n",
    "<li>Packets with type ID <code>7</code> are <em>equal to</em> packets - their value is <em>1</em> if the value of the first sub-packet is equal to the value of the second sub-packet; otherwise, their value is <em>0</em>. These packets always have exactly two sub-packets.</li>\n",
    "</ul>\n",
    "<p>Using these rules, you can now work out the value of the outermost packet in your BITS transmission.</p>\n",
    "<p>For example:</p>\n",
    "<ul>\n",
    "<li><code>C200B40A82</code> finds the sum of <code>1</code> and <code>2</code>, resulting in the value <code><em>3</em></code>.</li>\n",
    "<li><code>04005AC33890</code> finds the product of <code>6</code> and <code>9</code>, resulting in the value <code><em>54</em></code>.</li>\n",
    "<li><code>880086C3E88112</code> finds the minimum of <code>7</code>, <code>8</code>, and <code>9</code>, resulting in the value <code><em>7</em></code>.</li>\n",
    "<li><code>CE00C43D881120</code> finds the maximum of <code>7</code>, <code>8</code>, and <code>9</code>, resulting in the value <code><em>9</em></code>.</li>\n",
    "<li><code>D8005AC2A8F0</code> produces <code>1</code>, because <code>5</code> is less than <code>15</code>.</li>\n",
    "<li><code>F600BC2D8F</code> produces <code>0</code>, because <code>5</code> is not greater than <code>15</code>.</li>\n",
    "<li><code>9C005AC2F8F0</code> produces <code>0</code>, because <code>5</code> is not equal to <code>15</code>.</li>\n",
    "<li><code>9C0141080250320F1802104A08</code> produces <code>1</code>, because <code>1</code> + <code>3</code> = <code>2</code> * <code>2</code>.</li>\n",
    "</ul>\n",
    "<p><em>What do you get if you evaluate the expression represented by your hexadecimal-encoded BITS transmission?</em></p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c61ddf21",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let rec evaluate (packet: Packet) =\n",
    "    match packet with\n",
    "    | LiteralValue p -> p.Value\n",
    "    | Operation p ->\n",
    "        match p.TypeID with\n",
    "        | 0 -> p.Packets |> Seq.map evaluate |> Seq.sum\n",
    "        | 1 -> p.Packets |> Seq.map evaluate |> Seq.fold (fun acc value -> acc * value) 1\n",
    "        | 2 -> p.Packets |> Seq.map evaluate |> Seq.min\n",
    "        | 3 -> p.Packets |> Seq.map evaluate |> Seq.max\n",
    "        | 5 -> p.Packets |> Seq.map evaluate |> Seq.toList |> fun pair -> if pair.[0] > pair.[1] then 1 else 0\n",
    "        | 6 -> p.Packets |> Seq.map evaluate |> Seq.toList |> fun pair -> if pair.[0] < pair.[1] then 1 else 0\n",
    "        | 7 -> p.Packets |> Seq.map evaluate |> Seq.toList |> fun pair -> if pair.[0] = pair.[1] then 1 else 0\n",
    "        | _ -> failwith \"Invalid operation.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9220663a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\">180616437720</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Wall time: 11.1037ms"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#!time\n",
    "input\n",
    "|> toBStr\n",
    "|> parse\n",
    "|> Seq.exactlyOne\n",
    "|> evaluate"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cf45427-c80e-4427-963f-cef8340e03e7",
   "metadata": {},
   "source": [
    "[Prev](Day15.ipynb) | [Next](Day17.ipynb)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".NET (F#)",
   "language": "F#",
   "name": ".net-fsharp"
  },
  "language_info": {
   "file_extension": ".fs",
   "mimetype": "text/x-fsharp",
   "name": "C#",
   "pygments_lexer": "fsharp",
   "version": "4.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}