{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Morse Trie\n\nA prefix tree (aka a \"trie\") representing the Morse encoding of the alphabet.\nA letter can be encoded by tracing the path from the corresponding node in the\ntree to the root node, reversing the order of the symbols encountered along\nthe path.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import networkx as nx\n\n# Unicode characters to represent the dots/dashes (or dits/dahs) of Morse code\ndot = \"\u2022\"\ndash = \"\u2014\"\n\n# Start with the direct mapping of letter -> code\nmorse_direct_mapping = {\n    \"a\": dot + dash,\n    \"b\": dash + dot * 3,\n    \"c\": dash + dot + dash + dot,\n    \"d\": dash + dot * 2,\n    \"e\": dot,\n    \"f\": dot * 2 + dash + dot,\n    \"g\": dash * 2 + dot,\n    \"h\": dot * 4,\n    \"i\": dot * 2,\n    \"j\": dot + dash * 3,\n    \"k\": dash + dot + dash,\n    \"l\": dot + dash + dot * 2,\n    \"m\": dash * 2,\n    \"n\": dash + dot,\n    \"o\": dash * 3,\n    \"p\": dot + dash * 2 + dot,\n    \"q\": dash * 2 + dot + dash,\n    \"r\": dot + dash + dot,\n    \"s\": dot * 3,\n    \"t\": dash,\n    \"u\": dot * 2 + dash,\n    \"v\": dot * 3 + dash,\n    \"w\": dot + dash * 2,\n    \"x\": dash + dot * 2 + dash,\n    \"y\": dash + dot + dash * 2,\n    \"z\": dash * 2 + dot * 2,\n}\n\n### Manually construct the prefix tree from this mapping\n\n# Some preprocessing: sort the original mapping by code length and character\n# value\nmorse_mapping_sorted = dict(\n    sorted(morse_direct_mapping.items(), key=lambda item: (len(item[1]), item[1]))\n)\n\n# More preprocessing: create the reverse mapping to simplify lookup\nreverse_mapping = {v: k for k, v in morse_direct_mapping.items()}\nreverse_mapping[\"\"] = \"\"  # Represent the \"root\" node with an empty string\n\n# Construct the prefix tree from the sorted mapping\nG = nx.DiGraph()\nfor node, char in morse_mapping_sorted.items():\n    pred = char[:-1]\n    # Store the dot/dash relating the two letters as an edge attribute \"char\"\n    G.add_edge(reverse_mapping[pred], node, char=char[-1])\n\n# For visualization purposes, layout the nodes in topological order\nfor i, layer in enumerate(nx.topological_generations(G)):\n    for n in layer:\n        G.nodes[n][\"layer\"] = i\npos = nx.multipartite_layout(G, subset_key=\"layer\", align=\"horizontal\")\n# Flip the layout so the root node is on top\nfor k in pos:\n    pos[k][-1] *= -1\n\n# Visualize the trie\nnx.draw(G, pos=pos, with_labels=True)\nelabels = {(u, v): l for u, v, l in G.edges(data=\"char\")}\nnx.draw_networkx_edge_labels(G, pos, edge_labels=elabels)\n\n\n# A letter can be encoded by following the path from the given letter (node) to\n# the root node\ndef morse_encode(letter):\n    pred = next(G.predecessors(letter))  # Each letter has only 1 predecessor\n    symbol = G[pred][letter][\"char\"]\n    if pred != \"\":\n        return morse_encode(pred) + symbol  # Traversing the trie in reverse\n    return symbol\n\n\n# Verify that the trie encoding is correct\nimport string\n\nfor letter in string.ascii_lowercase:\n    assert morse_encode(letter) == morse_direct_mapping[letter]\n\nprint(\" \".join([morse_encode(ltr) for ltr in \"ilovenetworkx\"]))"
      ]
    }
  ],
  "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.12.7"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}