{ "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": [ "" ] }, "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 }