Python notebook containing the solution to a puzzle from 'Saturday Morning Breakfast Cereal' comic 'Spheres Part 5'

SMBC Spheres.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b0c9f9a4-8cbe-4643-ac71-3d6b78893c5e",
   "metadata": {},
   "source": [
    "# SMBC puzzle\n",
    "\n",
    "On April 9, 2026, the comic Saturday Morning Breakfast Cereal published a 5-part comic co-authored by Terence Tau and Zach Weinersmith [Part 1](https://www.smbc-comics.com/comic/spheres-part-1). It addresses applications of math, with one example being error-correcting codes. [Part 5](https://www.smbc-comics.com/comic/spheres-part-5) ends with the following puzzle:\n",
    "\n",
    "![](https://www.smbc-comics.com/comics/1775754447terrytaoafter.png)\n",
    "\n",
    "_Warning: solution below_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a74be841-e751-4af0-a37f-ab1d89543094",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import functools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "feb81b76-e219-4d09-a0a7-6b19be1b366a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Convert puzzle string to binary\n",
    "puzzle_str = \"\"\"\n",
    "011100101 011111111 110100110 101111010 100010011 010101110 000000000\n",
    "010011010 001100001 100110001 101111011 011100001 010110111 001111011\n",
    "111101011 100000000 001100001 011111111 110100110 110101011 000000010\n",
    "001100100 100001101 001001010 001110111 101111010 111100001 110111000\n",
    "101010100 100110101 001111011 001110110 011111111 111100001 011010010\n",
    "001110110 101110011 100001101 001100101 001110110 010101110 111010100\n",
    "010110101 101110011 001100101 111100000 101111011 110101011 111100001\n",
    "000101111 010100110 101111011 111110000 000000000 001100100 100001111\n",
    "011100110 010111000 001101101 101111011 010110101 111100001 111010100\n",
    "101010100 111100001 111010000 010100110 000101110 001110110\n",
    "\"\"\"\n",
    "puzzle = [int(n,2) for n in puzzle_str.split()]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afbbc3df-d134-483d-b7b8-b13f76100ed0",
   "metadata": {},
   "source": [
    "We are given some letters in the comic: ABCDEHNY"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "0f8911c1-7f98-45d2-98e7-c7f8cd00c1c7",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# plaintext message character -> ciphertext block\n",
    "cipher_key = {\n",
    "    #          234        \n",
    "    0b00000: 0b000_000_000, #'A',\n",
    "    0b00001: 0b000_010_011, #'B',\n",
    "    0b00010: 0b001_001_010, #'C',\n",
    "    0b00011: 0b001_011_001, #'D',\n",
    "    0b00100: 0b010_100_110, #'E',\n",
    "    0b00111: 0b011_111_111, #'H',\n",
    "    0b01101: 0b110_111_000, #'N',\n",
    "    0b11000: 0b100_110_001, #'Y',\n",
    "}\n",
    "# ciphertext block ->  plaintext message character\n",
    "decipher_key = {v:k for k,v in cipher_key.items()}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9e06bf06-d239-4c6f-bbbd-3d6a3b2c0fcf",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Some helper functions for working with this format\n",
    "def ltr(num):\n",
    "    \"Convert 5-bit message into a letter\"\n",
    "    if num < 26:\n",
    "        return chr(num+ord('A'))\n",
    "    if num == 26:\n",
    "        return ' '\n",
    "    return '?'\n",
    "def substitute(text, key):\n",
    "    \"Apply a key to a text. Works for both encoding and decoding\"\n",
    "    return [key.get(c, None) for c in text]\n",
    "def decode(text, key):\n",
    "    \"Apply a decryption key to a ciphertext, converting the result back to a string\"\n",
    "    return \"\".join([ltr(c) if c is not None else '?' for c in substitute(text, key)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c43e5d0d-66b2-4d2d-97b5-0cd86d3a1186",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'?H????A??Y???????H?????C???N????H?????????????????E??A????????????E??'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Decode the initial puzzle. Not much to go on.\n",
    "decode(puzzle, decipher_key)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1ccf98f-2eb4-4c85-9576-e686d5d5cbf5",
   "metadata": {},
   "source": [
    "Now I looked up a few common error-correcting codes. None fit the (9-bit block, 5-bit message) format.\n",
    "- Not Hamming, which is either (7,4) or (15,11)\n",
    "- It's not a parity code. The first three cipherbits do correspond to plainbits 2-4, but no column for bit 1 or 5.\n",
    "- Not a Hadamard code, which would be [16, 5, 8] (block length, message length, minimum distance)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43ac7633-ccd9-43e4-948a-e4be8a2b1fb4",
   "metadata": {},
   "source": [
    "Minimum distance is an important property of codes. Let's try to guess that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5ea275a1-0030-45bc-a86e-283ac5f0595b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def hamming(a,b):\n",
    "    \"Hamming distance between two numbers\"\n",
    "    d = 0\n",
    "    x = a ^ b\n",
    "    while(x>0):\n",
    "        if x & 1: d+=1\n",
    "        x >>= 1\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ab6461e0-c603-4f8a-9135-269e129aa407",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hamming(cipher_key[1],cipher_key[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "c274157d-c752-45d1-84b4-ff93b0dffac1",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def dist_matrix(key):\n",
    "    \"Full (hamming) distance matrix between all blocks\"\n",
    "    return [\n",
    "        [\n",
    "            hamming(key[i], key[j])\n",
    "            for i in key.keys()\n",
    "        ]\n",
    "        for j in key.keys()\n",
    "    ]\n",
    "def min_dist(key):\n",
    "    \"Minimum distance to another block\"\n",
    "    return { j:\n",
    "        min([\n",
    "            hamming(key[i], key[j])\n",
    "            for i in key.keys()\n",
    "            if i != j\n",
    "        ])\n",
    "        for j in key.keys()\n",
    "    }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ca50cac9-6285-4320-b106-0ca7f093f395",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 3, 3, 4, 4, 8, 5, 4],\n",
       " [3, 0, 4, 3, 5, 5, 6, 3],\n",
       " [3, 4, 0, 3, 5, 5, 6, 7],\n",
       " [4, 3, 3, 0, 8, 4, 5, 4],\n",
       " [4, 5, 5, 8, 0, 4, 5, 6],\n",
       " [8, 5, 5, 4, 4, 0, 5, 6],\n",
       " [5, 6, 6, 5, 5, 5, 0, 3],\n",
       " [4, 3, 7, 4, 6, 6, 3, 0]]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dist_matrix(cipher_key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "2156e209-5ab2-425f-abc1-d4008ccfd77d",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 3, 1: 3, 2: 3, 3: 3, 4: 4, 7: 4, 13: 3, 24: 3}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Minimum distance seems to be 3\n",
    "min_dist(cipher_key)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c133def-e8f2-4721-a307-8c4de763dc5e",
   "metadata": {},
   "source": [
    "Many codes are linear, meaning `encode(a) ^ encode(b) == encode(a^b)`. Let's check for that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "1f7d8ef6-d110-4d4a-84df-550b52bfbafb",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cipher_key[1] ^ cipher_key[2] == cipher_key[1^2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "21c7b798-988b-49ae-b6df-2a79cab4b269",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cipher_key[1] ^ cipher_key[3] == cipher_key[1^3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "fc5152c1-b447-44f8-bcf2-5dd1d78eba01",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cipher_key[1] ^ cipher_key[2] ^ cipher_key[4] == cipher_key[1^2^4]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac394a32-2cbf-4a13-87a2-9ac2253e8d03",
   "metadata": {},
   "source": [
    "Success! Now we can use linearity to fill the rest of the table based on known keys. Let's start from powers of two, then build the rest from those."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "529b631c-1e4a-4e29-8bf4-7591404ccc79",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b100001101'"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cipher_key[0b01000] = cipher_key[0b01101] ^ cipher_key[0b00100] ^ cipher_key[0b00001]\n",
    "bin(cipher_key[0b01000])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "a48c0dac-e648-49a7-898c-150a06a9443e",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b111100'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cipher_key[0b10000] = cipher_key[0b11000] ^ cipher_key[0b01000]\n",
    "bin(cipher_key[0b10000])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "41bb563b-403f-4458-9317-08592cf6e325",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Fill all other values\n",
    "for i in range(32):\n",
    "    if i not in cipher_key:\n",
    "        cipher_key[i] = functools.reduce(lambda a,b: a^b,\n",
    "                                         [cipher_key[1<<k] for k in range(5+1) if i & (1<<k) > 0],\n",
    "                                         0)\n",
    "decipher_key = {v:k for k,v in cipher_key.items()}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "4094fc56-ed1c-4db4-9dc4-5a5c5df9af52",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A 00000: 000000000\n",
      "B 00001: 000010011\n",
      "C 00010: 001001010\n",
      "D 00011: 001011001\n",
      "E 00100: 010100110\n",
      "F 00101: 010110101\n",
      "G 00110: 011101100\n",
      "H 00111: 011111111\n",
      "I 01000: 100001101\n",
      "J 01001: 100011110\n",
      "K 01010: 101000111\n",
      "L 01011: 101010100\n",
      "M 01100: 110101011\n",
      "N 01101: 110111000\n",
      "O 01110: 111100001\n",
      "P 01111: 111110010\n",
      "Q 10000: 000111100\n",
      "R 10001: 000101111\n",
      "S 10010: 001110110\n",
      "T 10011: 001100101\n",
      "U 10100: 010011010\n",
      "V 10101: 010001001\n",
      "W 10110: 011010000\n",
      "X 10111: 011000011\n",
      "Y 11000: 100110001\n",
      "Z 11001: 100100010\n",
      "  11010: 101111011\n",
      "? 11011: 101101000\n",
      "? 11100: 110010111\n",
      "? 11101: 110000100\n",
      "? 11110: 111011101\n",
      "? 11111: 111001110\n"
     ]
    }
   ],
   "source": [
    "print(\"\\n\".join(f\"{ltr(k)} {k:>05b}: {v:>09b}\" for k,v in sorted(cipher_key.items())))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5988608c-e304-4ab0-bb5e-37e8bdc6a636",
   "metadata": {},
   "source": [
    "Now we have a full key available. Decode the message!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "523602ab-7f16-48cb-bc19-8b72d77df687",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'?H????AU?Y ??????H?M??IC??ONL??SHO?S?ITS??F?T? MORE ?A????? FO?LO?E?S'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decode(puzzle, decipher_key)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2633481a-4e51-49f2-93eb-71723a0d927a",
   "metadata": {},
   "source": [
    "Results are underwhelming. Lots of blocks don't correspond to a valid letter. But we do get some english words, so we're on the right track.\n",
    "\n",
    "Don't forget this is an error correcting code! Distance 3 means that we can unambiguously correct single-bit errors in each block. There's a clever linear algebra way to do this, but it's easier to just write a for loop finding the closest valid message."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "7d34b4a3-08d6-4de8-8143-2ad5d653e427",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def find_closest(blk, decipher_key):\n",
    "    if blk in decipher_key: return decipher_key[blk]\n",
    "\n",
    "    dist = 32\n",
    "    best = None\n",
    "    for k, v in decipher_key.items():\n",
    "        d = hamming(blk, k)\n",
    "        if d < dist:\n",
    "            best = v\n",
    "            dist = d\n",
    "    # print a warning if a block was evenly spaced between multiple messages\n",
    "    if dist > 1: print(f\"Large distance for 0b{blk:>09b}: {dist}\")\n",
    "    return best\n",
    "\n",
    "def decode_noisy(text, key):\n",
    "    \"\"\"Apply a decryption key to a ciphertext\"\"\"\n",
    "    return \"\".join([ltr(find_closest(c, key)) for c in text])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "025fb278-3cb5-4fca-a41c-1f59f38f4d1b",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'THE BEAUTY OF MATHEMATICS ONLY SHOWS ITSELF TO MORE PATIENT FOLLOWERS'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Solved it!\n",
    "decode_noisy(puzzle, decipher_key)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ede0c62e-d258-45a2-970f-fbf62ba20730",
   "metadata": {},
   "source": [
    "This is a quote from Iranian mathemetician Maryam Mirza-Khani."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ce623bb-e211-4e5b-9857-5eaf5f564ed5",
   "metadata": {},
   "source": [
    "Bonus fact: the QR code in panel 9 leads Terence Tao's article [I’m an award-winning mathematician. Trump just cut my funding](https://nesletter.ofthebrave.org/p/im-an-award-winning-mathematician) about the 2025 cuts to US research budgets."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}