hexa-tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hexa-Tree\n",
    "\n",
    "This is an interactive canvas for the puzzle described in [Mathologer \"Secret of row 10: a new visual key to ancient Pascalian puzzles\"](https://www.youtube.com/watch?v=9JN5f7_3YmQ).\n",
    "\n",
    "#### Below is some code..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "import math\n",
    "from ipywidgets import AppLayout\n",
    "from ipycanvas import MultiCanvas, hold_canvas\n",
    "\n",
    "s3 = math.sqrt(3)\n",
    "size = 500\n",
    "border = 30\n",
    "csize = size + 2 * border\n",
    "\n",
    "colors = ['red', 'green', 'yellow']\n",
    "\n",
    "canvas = MultiCanvas(3, size=(csize, csize))\n",
    "background_layer = canvas[0]\n",
    "c = canvas[1]\n",
    "interaction_layer = canvas[2]\n",
    "\n",
    "def hexagon(x0, y0, n, color, cv):\n",
    "    \"Draws a hexagon at (x0, y0) position with specified size and color\"\n",
    "    step_x = size / n\n",
    "    side = step_x / s3\n",
    "    step_y = 3 * side / 2\n",
    "    x = step_x * x0 + step_x * y0 / 2\n",
    "    y = step_y * y0\n",
    "    cv.fill_style = colors[color]\n",
    "    cv.begin_path()\n",
    "    cv.move_to(x + border, csize - border - y)\n",
    "    cv.line_to(x + step_x / 2 + border, csize - border - (y - side / 2))\n",
    "    cv.line_to(x + step_x + border, csize - border - y)\n",
    "    cv.line_to(x + step_x + border, csize - border - (y + side))\n",
    "    cv.line_to(x + step_x / 2 + border, csize - border - (y + 3 * side / 2))\n",
    "    cv.line_to(x + border, csize - border - (y + side))\n",
    "    cv.fill()\n",
    "\n",
    "def star(n, cv):\n",
    "    \"Draws the star on the tree's top\"\n",
    "    step_x = size / n\n",
    "    side = step_x / s3\n",
    "    center_x = size / 2\n",
    "    center_y = center_x * s3\n",
    "    cv.fill_style = '#FFC030'\n",
    "    cv.font =  str(4 * side) + 'px serif'\n",
    "    cv.text_align = 'center'\n",
    "    cv.fill_text('★', center_x + border, csize - border - center_y)\n",
    "\n",
    "\n",
    "def make_color(a, b, rule='combine'):\n",
    "    \"\"\"\n",
    "        Computes the color of a neighbor hexagon.\n",
    "        Rule 'combine' means either the same color if 'a'='b' or the third color if 'a' is not 'b'.\n",
    "        Rule 'mod3' is the Pascal's triangle rule\n",
    "    \"\"\"\n",
    "    if rule == 'combine':\n",
    "        if a == b:\n",
    "            return a\n",
    "        else:\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            if a == 0:\n",
    "                if b == 1:\n",
    "                    return 2\n",
    "                else:\n",
    "                    return 1\n",
    "            else:\n",
    "                return 0\n",
    "    else:\n",
    "        return (a + b) % 3\n",
    "    \n",
    "def draw_bottom_up(a, cv):\n",
    "    \"Calculates and draws the trianlge from bottom to up\"\n",
    "    n = len(a)\n",
    "    left = []\n",
    "    right = []\n",
    "    a0 = []\n",
    "    for y in range(n):\n",
    "        a1 = []\n",
    "        for x in range(n - y):\n",
    "            if y == 0:\n",
    "                c = a[x]\n",
    "            else:\n",
    "                c = make_color(a0[x], a0[x + 1])\n",
    "            hexagon(x, y, n, c, cv)\n",
    "            a1.append(c)\n",
    "            if x == 0:\n",
    "                left.append(c)\n",
    "            if x == n - y - 1:\n",
    "                right.append(c)\n",
    "        a0 = a1\n",
    "    return left, right\n",
    "\n",
    "def draw_left_right(a, cv):\n",
    "    \"Calculates and draws the trianlge from left to right and down (it's messy but it works)\"\n",
    "    n = len(a)\n",
    "    right = []\n",
    "    bottom = []\n",
    "    a0 = []\n",
    "    for x in range(n):\n",
    "        a1 = []\n",
    "        for y in range(n - x):\n",
    "            if x == 0:\n",
    "                c = a[y]\n",
    "            else:\n",
    "                c = make_color(a0[y], a0[y + 1])\n",
    "            hexagon(x, y, n, c, cv)\n",
    "            a1.append(c)\n",
    "            if y == 0:\n",
    "                bottom.append(c)\n",
    "            if y == n - x - 1:\n",
    "                right.append(c)\n",
    "        a0 = a1\n",
    "    right.reverse()\n",
    "    return right, bottom\n",
    "\n",
    "def draw_right_left(a, cv):\n",
    "    \"Calculates and draws the trianlge from right to left and down (it's messy but it works)\"\n",
    "    n = len(a)\n",
    "    left = []\n",
    "    bottom = []\n",
    "    a0 = []\n",
    "    for x0 in range(n):\n",
    "        x = n - x0 - 1\n",
    "        a1 = []\n",
    "        for y in range(n - x0):\n",
    "            if x0 == 0:\n",
    "                c = a[y]\n",
    "            else:\n",
    "                c = make_color(a0[y], a0[y + 1])\n",
    "            hexagon(x - y, y, n, c, cv)\n",
    "            a1.append(c)\n",
    "            if y == 0:\n",
    "                bottom.append(c)\n",
    "            if y == n - x0 - 1:\n",
    "                left.append(c)\n",
    "        a0 = a1\n",
    "    left.reverse()\n",
    "    bottom.reverse()\n",
    "    return left, bottom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### More code...\n",
    "\n",
    "The array `A` below defines the colors of the lower row (now it's 28 red and yellow hexagons).\n",
    "If the row's size is \"magic\" then the color of the top hexagon color is determined by lower left and right hexagons ONLY. The \"magic\" sizes are 4, 10, 28, 82, ...\n",
    "<br>See the abovementioned Youtube video for the explanation.\n",
    "\n",
    "**Note:** Unfortunately, with large size jupyter breaks with some cryptic messages (thus, size=82 will not work)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c.clear()\n",
    "\n",
    "# 4, 10, 28, 82 are the \"magic\" sizes\n",
    "A = [0, 2] * 14\n",
    "\n",
    "B, C = draw_bottom_up(A, c)\n",
    "star(len(A), c)\n",
    "\n",
    "# Test updates in other directions:\n",
    "\"\"\"\n",
    "C, A = draw_left_right(B, c)\n",
    "B, A = draw_right_left(C, c)\n",
    "print('A:', A)\n",
    "print('B:', B)\n",
    "print('C:', C)\n",
    "\"\"\"\n",
    "\n",
    "def on_mouse_down(x, y):\n",
    "    \"Changes the color of the clicked hexagon and redraws all the tringle\"\n",
    "    global A\n",
    "    global B\n",
    "    global C\n",
    "    global L\n",
    "    with hold_canvas(canvas):\n",
    "        n = len(A)\n",
    "        step_x = size / n\n",
    "        side = step_x / s3\n",
    "        step_y = 3 * side / 2\n",
    "        x -= border\n",
    "        y = csize - y\n",
    "        y -= border\n",
    "        i = int(x / step_x)\n",
    "        j = int(y / step_y)\n",
    "        if n / 2 - 1 <= i <= n / 2 + 1 and j >= n:\n",
    "            A = [1] * len(A)\n",
    "            B, C = draw_bottom_up(A, c)\n",
    "            interaction_layer.clear()\n",
    "            return\n",
    "        if i < 0 or i > len(A):\n",
    "            return\n",
    "        if j < 1:\n",
    "            v = A[i]\n",
    "            v = (v + 1) % 3\n",
    "            A[i] = v\n",
    "            B, C = draw_bottom_up(A, c)\n",
    "        elif i + 1 > n / 2:\n",
    "            v = C[j]\n",
    "            v = (v + 1) % 3\n",
    "            C[j] = v\n",
    "            B, A = draw_right_left(C, c)\n",
    "        else:\n",
    "            v = B[j]\n",
    "            v = (v + 1) % 3\n",
    "            B[j] = v\n",
    "            C, A = draw_left_right(B, c)\n",
    "            \n",
    "        interaction_layer.clear()\n",
    "\n",
    "interaction_layer.on_mouse_down(None)\n",
    "interaction_layer.on_mouse_down(on_mouse_down)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### And finally, the tree\n",
    "\n",
    "All the sides are clickable!\n",
    "<br>Click on the start to reset the state.\n",
    "\n",
    "**Note**: If the canvas starts blinking or otherwise malfunctioning just rerun it with \">>\" toolbar button or \"Kernel/Restart & Run All\" menu command."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "AppLayout(center=canvas)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Triangle calculation as a reversible tranformation\n",
    "\n",
    "Note that each trianlge side determines the color of all the rest hexagons, including other two sides (if the color combination rule is aplied, not a \"mod3\" rule). Therefore this can be viewed as a reversible transformation of a row consisting of \\[012\\] digits.\n",
    "\n",
    "Indeed, you can easily verify that in many cases one side has simpler pattern that the two others (e.g. in terms of \"Run Length Encoder\", RLE complexity). Hence the idea for a compression algorithm &ndash; get the data, encode it as a 3-base number, run the calculation and then choose which of the resulted \"sides\" can be compressed more.\n",
    "\n",
    "However, unlike [BWT](https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform) this transform must show much less power (plus BWT is much faster and has application for inexact pattern matching)."
   ]
  }
 ],
 "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.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}