_notebooks/2021-10-23-SR-codes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Better QR codes\n",
    "> Snake Race codes to replace QR codes. With NumPy, rotation matrix and animated images!\n",
    "- image: images/copied_from_nb/animation.gif\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "QR codes are quite interesting, but boring to look at. For this reason I introduce SR codes, which stands for Snake Race codes. It improves QR codes on several fronts:\n",
    "\n",
    "* Animation!\n",
    "* Color!\n",
    "* Hardcore. QR codes have error correction. SR codes don't. If you make an error it's game over.\n",
    "* Not quick. Savour the wait before you can scan the code.\n",
    "\n",
    "Developing a scanner app is left as an exercise for the reader :)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](animation.gif) ![](qrcode.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "QR codes are really interesting. Error correction and packing as much information as you can in a small amount of pixels while keeping it robust is a nice challenge.\n",
    "\n",
    "Nice explanation in Dutch [https://michielp1807.github.io/qr-codes/](https://michielp1807.github.io/qr-codes/) or check out the [Wikipedia page](https://en.wikipedia.org/wiki/QR_code)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#hide\n",
    "import numpy as np\n",
    "from typing import NamedTuple, Tuple\n",
    "from numpy.random import default_rng\n",
    "from matplotlib import cm\n",
    "from PIL import Image, ImageDraw\n",
    "import numpy as np\n",
    "from typing import NamedTuple, Tuple\n",
    "from numpy.random import default_rng\n",
    "from matplotlib import cm\n",
    "from PIL import Image, ImageDraw"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Representing position and orientation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We represent the position of the snake as a point $(x, y)$ with an orientation $(h, v)$. Taking turns is done with a _rotation matrix_ that defines 90 degree turns and going straight (=not changing direction)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "actions = [\n",
    "    # Left\n",
    "    np.array([\n",
    "        [0, 1],\n",
    "        [-1, 0]\n",
    "    ]),\n",
    "    # Straight\n",
    "    np.array([\n",
    "        [1, 0],\n",
    "        [0, 1]\n",
    "    ]),  \n",
    "    # Right\n",
    "    np.array([\n",
    "        [0, -1],\n",
    "        [1, 0]\n",
    "    ])\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, if the snake is going to the right it has orientation $(1,0)$. If it makes a 90 degree turn to the left it goes up and has orientation $(0, -1)$. The first coordinate is horizontal and the second is vertical."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0, -1])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "actions[0] @ np.array([1, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Going left four times we should end up in the same direction:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 0])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "orientation = np.array([1, 0])\n",
    "for i in range(4):\n",
    "    orientation = actions[0] @ orientation\n",
    "orientation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Going places\n",
    "We want to see where the snakes have been as well as their current position. Below we define:\n",
    "\n",
    "- The different snakes in `snakes`, including start position, color and trail\n",
    "- For each snake we also keep track if they are active. The snake stops if there is no valid move to make.\n",
    "- To make our lives easy we have per position the information if some snake has been there to limit possible moves `matrix`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define a method to generat the _trails_ of the snakes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_trails(size: int, bits):\n",
    "    # Define quarter distance\n",
    "    q = size // 4\n",
    "    \n",
    "    # Define the start positions of all snakes\n",
    "    snakes = [\n",
    "        {\n",
    "            'c': 'Greens', \n",
    "            'position': np.array([q+1, q+1]), \n",
    "            'orientation':  np.array([1, 0]), \n",
    "            'trail': np.full((2*(size+2), 2*(size+2)), 0),\n",
    "            'active': True\n",
    "        },\n",
    "        {\n",
    "            'c': 'Reds', \n",
    "            'position': np.array([3*q+1, 1+1]), \n",
    "            'orientation': np.array([0, 1]), \n",
    "            'trail': np.full((2*(size+2), 2*(size+2)), 0),\n",
    "            'active': True\n",
    "        },\n",
    "        {\n",
    "            'c': 'Blues', \n",
    "            'position': np.array([3*q+1, 3*q+1]), \n",
    "            'orientation': np.array([-1, 0]), \n",
    "            'trail': np.full((2*(size+2), 2*(size+2)), 0),\n",
    "            'active': True\n",
    "        },\n",
    "        {\n",
    "            'c': 'Purples', \n",
    "            'position': np.array([q+1, 3*q+1]), \n",
    "            'orientation': np.array([0, -1]), \n",
    "            'trail': np.full((2*(size+2), 2*(size+2)), 0),\n",
    "            'active': True\n",
    "        }\n",
    "    ]\n",
    "    \n",
    "\n",
    "    # Keep track of where the snakes have passed\n",
    "    matrix = np.full((size+2, size+2), False)\n",
    "    \n",
    "    # Set the borders\n",
    "    matrix[0, :] = True\n",
    "    matrix[:, 0] = True\n",
    "    matrix[-1, :] = True\n",
    "    matrix[:, -1] = True\n",
    "    \n",
    "    # Go over the bits\n",
    "    current_bit = 0\n",
    "    iteration = 0\n",
    "    \n",
    "    # While there are active snakes try it out\n",
    "    while any([snake['active'] for snake in snakes]):\n",
    "\n",
    "        # For each active snake\n",
    "        active_snakes = [snake for snake in snakes if snake['active']]\n",
    "        for i, snake in enumerate(active_snakes) :\n",
    "           \n",
    "            # Get the bit or exit\n",
    "            if current_bit >= len(bits):\n",
    "                return snakes\n",
    "            \n",
    "            bit = bits[current_bit]\n",
    "            \n",
    "            # Get the possible actions\n",
    "            possible_actions = [ \n",
    "                action for action in actions \n",
    "                if not matrix[ tuple(snake['position'] + action @ snake['orientation']) ] \n",
    "            ]\n",
    "\n",
    "            # Execute an action\n",
    "            if len(possible_actions) == 0:\n",
    "                snake['active'] = False\n",
    "                continue  # See if other snakes can still play\n",
    "                \n",
    "            elif len(possible_actions) == 1:\n",
    "                action = possible_actions[0]\n",
    "                \n",
    "            elif len(possible_actions) == 2:\n",
    "                action = possible_actions[int(bit)]\n",
    "                \n",
    "            elif len(possible_actions) == 3:\n",
    "                offset = iteration % 2\n",
    "                action = possible_actions[(int(bit) + offset)]\n",
    "\n",
    "            # Update\n",
    "            current_bit += 1\n",
    "            snake['orientation'] = action @ snake['orientation']\n",
    "            prev_position = snake['position']\n",
    "            snake['position'] = snake['position'] + snake['orientation']\n",
    "\n",
    "            # Update boundaries where snakes have been\n",
    "            matrix[ tuple(snake['position']) ] = True\n",
    "\n",
    "            # Update the twice larger pretty image (so that there is space and it looks pretty)\n",
    "            snake['trail'][ tuple(prev_position + snake['position']) ] = 2 * iteration\n",
    "            snake['trail'][tuple(2 * snake['position']) ] = 2 * iteration + 1\n",
    "        \n",
    "        # Update iteration\n",
    "        iteration += 1\n",
    "\n",
    "    return snakes, current_bit, iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Showing it on screen\n",
    "Some code that generates the image at a certain frame/point in time:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_image(snakes, frame=np.inf, canvas_size = 44):\n",
    "\n",
    "    \n",
    "    # Define a transparant layer\n",
    "    transparent = np.uint8(np.broadcast_to(\n",
    "        np.array([255, 255, 255, 0]), \n",
    "        (canvas_size, canvas_size, 4)\n",
    "    ))\n",
    "    \n",
    "    # Define the bottom layer (transparent white)\n",
    "    composite = Image.new(\n",
    "        'RGBA', \n",
    "        (canvas_size, canvas_size), \n",
    "        (255, 255, 255, 255)\n",
    "    )\n",
    "\n",
    "    # Draw each trail\n",
    "    for snake in snakes:\n",
    "        # Get the trail until this frame\n",
    "        trail = snake['trail'] * (snake['trail'] <= frame)\n",
    "        \n",
    "        # Get the color\n",
    "        color = cm.get_cmap(snake['c'])\n",
    "        \n",
    "        # Set the trail and rest transparent\n",
    "        df = np.where(\n",
    "            trail[:, :, np.newaxis] > 0, \n",
    "            np.uint8(color(trail / trail.max())  *255), \n",
    "            transparent\n",
    "        )\n",
    "        \n",
    "        # Create an image and add the layer\n",
    "        im = Image.fromarray(df)\n",
    "        composite = Image.alpha_composite(composite, im)\n",
    "\n",
    "    d = ImageDraw.Draw(composite)\n",
    "    d.rectangle(\n",
    "        [(0, 0), (canvas_size-1, canvas_size-1)], \n",
    "        fill=None, \n",
    "        outline=(0,0,0,255), \n",
    "        width=1)\n",
    "    \n",
    "    return composite.resize((5 * canvas_size, 5 * canvas_size), Image.NEAREST)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this piece of code we'll generate 500 bits on a canvas of 22x22. The bits are not generated efficiently."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPAAAADwCAYAAAA+VemSAAALTUlEQVR4nO3dfcyVdR3H8euc65wbCAihDDYQH3KNcg0d2mTNCnpg5VN/mNOi4cZyFJUpGiMtsmgZlFQKOTfLHNiy6RJbZaXI/AO0B3woSmcpQqiNEDGE7vs89EerP/p+sB/nXPd9nc+5368/f/td1/W775vPfuO77/W7KlmWtTMAlqplLwBA5wgwYIwAA8YIMGCspgbbbepaQK+pVCphjB0YMEaAAWMEGDBGgAFjsoilTPn83DA2UIuX12p5GNt99QNHt6oecPmDV4WxMXn8ecfkA3GsFscGqvUwduVpn+1wdcC/sQMDxggwYIwAA8YIMGAsuYg1NNQIY/u+vDWMnbT6Pd2tqEccbsSfd+1Zazq+3w2Pr+1mOYDEDgwYI8CAMQIMGCPAgLHkItagKGIp9Xq85Sk3niPmxY4tdW0uOrvUPDU2VnSKpY6NyeNzlR889f0wNtgcFPeL3VlAt9iBAWMEGDBGgAFjBBgwlt6JJTqTlCcu/3nHi3E0UI3FqYtPXlTCSjAasQMDxggwYIwAA8YIMGAsuYjVHmyGscriWXHiYEuMxWuzf4oxde1QHGv/cncYe2zfr8NYoxULb0OtoaQx1U012Ipj9WryrxAoHDswYIwAA8YIMGCMAAPGKlmWhU8ROn6dcMeLj4Sxt0w+dcTXAQwXvk4I9BkCDBgjwIAxAgwY6/k2ot0Hnw5jDdE5VRdf/wP6HTswYIwAA8YIMGCMAAPGer6IVavEJc6YeGIJKwF6DzswYIwAA8YIMGCMAAPGer6IVa2kfSUQGI3YgQFjBBgwRoABYwQYMNbzRaycIhZwROzAgDECDBgjwIAxAgwYsyxiHRjanzRvfG3icCypLx1+JX55sVKNB4lXMjEmtgF1CHmtTkGyaOzAgDECDBgjwIAxAgwY65uvE6I7hw7GIta48QMlrARHwtcJgT5DgAFjBBgwRoABYz3fiYWRMdoKl/dv/nMYa7Xi76DZbCXNazfj2AfOntXh6tKxAwPGCDBgjAADxggwYIwiFrIsy7JRVsPK8jzuXfPndf7Vy3s27ehmOR1jBwaMEWDAGAEGjBFgwBhFLGRZVl4n1qOPPhfGZPeTWF9TdD/JLikxVhXnfXVDPXcksAMDxggwYIwAA8YIMGCMIhayLCuviKWKSbNnTy9hJd1RhbeRwA4MGCPAgDECDBgjwIAxilh9bv++V8KYOB9cHho+ElI7om5ev1Vcm3Y/9eqgnFeL89QXGvX9ytkL2YEBYwQYMEaAAWMEGDBGEavPqQ6rY6aML2ElWjVPK2I1W7HT6dJPvL3o5dhhBwaMEWDAGAEGjBFgwBhFrD5X1llNqaqJHWDqXKuRsPLqe8NYqxELaurrhGpeS7x2eN0N53W4OnZgwBoBBowRYMAYAQaMUcTqcz1ew8ry1E4sUSQaCVXx6uC1X1nQ8f2WL727m+UE7MCAMQIMGCPAgDECDBgrrYh14H1z4qAoVLRF50q70QxjquOooTphxDxVIGmKefLaRtq16uDvNz/1lzBWNLXm5587EMbUa4fyS3+ilqTmqa8JqmtTz+JSz1i7ZksYS/67qX9rYl5qke2KS34UxqrqjC1RFOsGOzBgjAADxggwYIwAA8ZKK2JV6nkYm/iLh0tYycj4w0knlvLcqdMmlvLcol227B1lL+FVqdcEr7/1Q8P+XHZgwBgBBowRYMAYAQaMJRexDi+cH8ZUR5TsnBJjRXekpBo3b1UcbMWfQ441h5LmHdq2WkyLXT7bZxwf54luoDl7no3PHWUWTIp/N3UofEV8JfCne1eEsQvetDZeK+6nuql++Pinw5g6E+tTF94exlSxa92dC8NYKnZgwBgBBowRYMAYAQaMJRex1H/wx26Ir3P1vLwehg5tvqbj240744qkeW/d+UzSvIemHdfxWhy9q/KFMPZA+0thTBUB730p/t3OmXZd0nNVMemuJ5eFsYtPvSHpft+6/aKkeR8//7akeanYgQFjBBgwRoABYwQYMJZexBKv/1mqFvxzqI6tbm4nzo16cOoMMS9OfOff/lroWkZCpRqLo/PrXwxj1Vra2VTqfufPXBPvJ+YpqhNr4dvWx3mis/C2rUvCWNFfWWQHBowRYMAYAQaMEWDA2FF0YvVJ1vOCjwEruIg194VdSfM2Hzu90OeWZXPz2kLvd8+e5YXeb+NvlibNu+Ssm5PmtcTHBrrRJ6kERicCDBgjwIAxAgwYS6/o9EsRq+BOrEPbbyz0fqkaWbEdPWU5cFh8QbKbLyWqa1Pnya8sxmuPmzImjKkOsMXvviXOS/zaYao+SSUwOhFgwBgBBowRYMBYeidWrbQPGRar2h8/R8FvpZVGvdX32rG98+rqs38/nDTve1s+Nswr0diBAWMEGDBGgAFjBBgwll7REV99a1x5QdK82uo7jmpRw6pPinEN1YZkqFpJ60z67TMHxLVp95s9c+JRr+s/xHnyPYUdGDBGgAFjBBgwRoABY8kVndo3f5w0r/G5D3e6lpEhimyOWn3yOuFrBtKKWG1RtDvthElh7LFdL3e9pv/33F7SH/+agVGKAAPGCDBgjAADxopvS8rTXgVr/+NFMSgOvRYHp1cmveFoV/VfeeL6ep3qELpz8tQ4T14bL1Zjg+IZqgPs0pf3yjUWqZn4/mQu2rN27DkYxlK7uBIbxUrDDgwYI8CAMQIMGCPAgLHii1iJnU6VCZOT5rX3P9/NauJzVfXC0Af3Fft7SbV+wutLeW5qQ9Qp0ycM70J6DDswYIwAA8YIMGCMAAPGii9iFX3mlOjEau/dFeeJLq7KsceHMdWJNfmjG8NYVRTjquILjd3MUwU1tb6d3z43jClLKvHspzyLz1jXjudLpRos6UR51SkGdmDAGgEGjBFgwBgBBoyV1omVqjJletK89gtPJ83bv3FhN8sZdid85icdX3tTO54HdVk1nhvVjbIOlKeIpbEDA8YIMGCMAAPGCDBgbEQ6sRpf/2Scp4pd4tqK6EzKl66J14pOrPaeJ+O8ljh3K/Esrra6tjkUhqonnx7nJcpFF1c3BsTtVtSPifPE4U818eZlraRDotSZWL/6YzyLqyWKXQ1xrT4XLP591dlj+hlp1zbFvEVnzIwTE7EDA8YIMGCMAAPGCDBgrPAiVm35dwq9X/OmFUnzKtPeWOhz5TPEWOuJhwp9RrXgM7vWNF4q9H5lmTfrdWUvoRDffXhnofdjBwaMEWDAGAEGjBFgwFjxnVhF6/WvCYpOrG4U3YnVL5Zt+lMYq+fiTDFRBKyrs8fkWHyufIboRktdS9F/Xv61AMYIMGCMAAPGCDBgrPeLWLV62St4deK1w24U3YnVL9Trf984e1YJK+kt7MCAMQIMGCPAgDECDBjr/SJWNXZiNTd8Nc4T52nlF101HCv6n8UMfxFr9sr7kuZtXzm/4+cuWLct6Rmqu6imvsYoupXuWjynw9Vl2ZA6YArswIAzAgwYI8CAMQIMGOv5Ila+6Jqkec07rh/mlWjtZqPQ+/1+1XuT5p2+anOhz1WHn9+39MyO73fhrb/rZjmBOtgd7MCANQIMGCPAgDECDBjr+SJWMtGJ1bx7XZwnOrvyc5d0/tyCO7FSqS6puV/bEsbUGVuyw6rgw5pUx9ZHNjwSxmriK5W624vXLBV2YMAYAQaMEWDAGAEGjFWyLAstLm1x/lC/aP7sljCWv39x5/fbtine78zzOr4fcCQV8YomOzBgjAADxggwYIwAA8b6pxMrlfjaYfP+DXGe6NjKcnHIfK9/PRF9jR0YMEaAAWMEGDBGgAFjo64TC3BFJxbQZwgwYIwAA8YIMGCMAAPGCDBgjAADxggwYIwAA8ZkJxYAD+zAgDECDBgjwIAxAgwY+xdp8YgA4XxetQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<PIL.Image.Image image mode=RGBA size=240x240 at 0x7F1EB0C85D90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Some settings\n",
    "seed = 0\n",
    "nr_bits = 500\n",
    "size = 22\n",
    "\n",
    "# Sizes of the canvas\n",
    "canvas_size=2*(2+size)\n",
    "canvas_size_xl = canvas_size * 5\n",
    "\n",
    "# Generate some random bits\n",
    "rng = default_rng(seed)\n",
    "bits = rng.random(nr_bits) < 0.5\n",
    "\n",
    "# Get the trails\n",
    "snakes, nr_generated, max_iteration = generate_trails(\n",
    "    size,\n",
    "    bits\n",
    ")\n",
    "\n",
    "# Display\n",
    "image = generate_image(snakes, frame=max_iteration, canvas_size=canvas_size)\n",
    "display(image)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Animation\n",
    "Finally we create a GIF image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a gif\n",
    "gif = Image.new('RGBA', (canvas_size_xl, canvas_size_xl))\n",
    "\n",
    "gif.save('animation.gif', \n",
    "         save_all=True, \n",
    "         append_images=[generate_image(snakes, frame=frame, canvas_size=canvas_size) \n",
    "                        for frame in range(2, max_iteration)],\n",
    "         duration=100, \n",
    "         loop=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](animation.gif)"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}