31:[] 2f:{"title":"Gray Codes Visualization","cells":[{"id":0,"value":"md`# Gray Codes Visualization`","pinned":false,"hidden":false,"mode":"ojs"},{"id":367,"value":"md`In this notebook we will explore what gray codes are and how they are generated.\n\nA gray code is a sequence of some combinatorial object with minimal changes between successive elements. For example, a binary string with one bit flip in between each successive element. Let's look at an example.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":442,"value":"html`00\n01\n11\n10`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":412,"value":"md`This is a \"binary reflected gray code (BRGC) of length 2\". Each line is a binary string with 2 bits. The underlined bit was the one flipped from the previous string. BRGCs also have a neat property in that they are cyclic. 10 is one bit flip off from 00. As a matter of fact, as we will soon see, the last string in a BRGC is 10 ... 0.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":580,"value":"md`## Recursive Generation`","pinned":false,"hidden":false,"mode":"ojs"},{"id":420,"value":"md`Now, what if we want to figure out what the BRGC of length 3 should be? We can actually be a little clever and use this BRGC of length (n) 2 to generate it. We know that BRGC(n=2) satisfies the \"gray\" condition by definition, so we can just add a 0 to the front and it will continue to satisfy that condition.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":423,"value":"html`000\n001\n011\n010`","pinned":false,"hidden":false,"mode":"ojs"},{"id":515,"value":"present(\n drawPalette(\n [3,Math.pow(2,2),2,l1]\n ),\n \"Augmented BRGC(n=2)\"\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":474,"value":"md`Now we are one step closer closer to BRGC(n=3). But we know that we are missing half of the code as we only have 4 out of the 2³ total codes. We can add a 1 in front of the BRGC(n=2), but as we can see, this makes the code non-gray.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":543,"value":"present(\n drawPalette(\n [3,Math.pow(2,2)*2,2,l2]\n ),\n \"Augmented BRGC(n=2)\"\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":429,"value":"md`The final step is to reflect the BRGC(n=2) for the second half, in order to preserve the gray-ness of the code. This works because as we transition from having 0 in the first position to having 1 in the first position, the rest of the code cannot change. So we copy the rest of the bits from BRGC(n=2) and work backwards.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":565,"value":"present(\n drawPalette(\n [3,Math.pow(2,3),2,BRGC(2,3)]\n ),\n \"BRGC(n=3)\"\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":569,"value":"md`This is how we can generate any binarly reflected gray code of length n, recursively. We see that again the last element is 100, so the gray code is cyclic. This particular gray code is often used to introduce the concept due to its simple construction and nice properties. However, this generation can be inefficient as you need to generate every gray code of length 1 through n-1 in order to generate gray code of length n. There is a faster way: using successor rules!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":582,"value":"md`## Successor Rules`","pinned":false,"hidden":false,"mode":"ojs"},{"id":572,"value":"md`By using greedy algorithms, we do not need to consider any smaller gray code, and we can build something called a \"successor rule\". This way, given any element in a complete code, we can generate the successive element, maintaining grayness.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":615,"value":"md`How do we find such a successor rule? We can see in the above BRGCs that the last bit seems to alternate, but only every other element. That is, it goes 0,0,1,1,0,0,1,1. This gives us half of the bit flips we are looking for. If we define the \"weight\" of a binary string as the number of 1s in it, or the sum of our elements (100101 has weight 3), we can use the parity of the weight in order to tell if we should flip the last bit. When the weight is even, such as with 000, we flip the last bit. Else, flip some other bit.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":627,"value":"present(\n drawPalette(\n [1,8,2,[[0],[1],[1],[0],[0],[1],[1],[0]]]\n ),\n \"Last bits of BRGC(n=3)\"\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":622,"value":"md`Next, we can see for the odd weight cases that the bit left of the rightmost 1 is flipped. So given 010, we will get 110, flipping the first bit. I encourage you to work through this successor algorithm, starting from 000, to see if you are able to generate the gray code!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":693,"value":"md`## Visualizing the Algorithms`","pinned":false,"hidden":false,"mode":"ojs"},{"id":695,"value":"md`While the two algorithms generate the same gray code, they do so in different ways. We can visualize the different steps for each technique.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":697,"value":"md` ### Recursive`","pinned":false,"hidden":false,"mode":"ojs"},{"id":710,"value":"present(\n drawPalette(\n recursiveAnimation[parseInt((animationLoop + 1) / 2) - 1]\n ),\n `Recursive Step ${parseInt((animationLoop + 1) / 2)}`\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":740,"value":"md` ### Sucessor Rule`","pinned":false,"hidden":false,"mode":"ojs"},{"id":729,"value":"present(\n drawPalette(\n successorAnimation[animationLoop-1]\n ),\n `Successor Rule Step ${animationLoop}`\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":584,"value":"md`## To Infinity and Beyond!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":587,"value":"md`We have seen a couple ways to generate *binary* reflected gray codes. However, this is only one type of combinatorial object. In fact, there is even a generalization of the BRGC to a gray code of k-ary strings for arbitrarily large k! However, we lose the nice cyclical property of BRGCs. Let's look at an example of a 3-ary string of length 2.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":600,"value":"html`00\n01\n02\n12\n11\n10\n20\n21\n22`","pinned":false,"hidden":false,"mode":"ojs"},{"id":592,"value":"md`We can use various shades of blue to denote the various possible channels. Below is an interactive visualization with which you can explore various gray codes of strings with k bits and length n.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":241,"value":"viewof k = slider({\n min: 1,\n max: 7,\n step: 1,\n value: 3,\n description:\n \"k, the number of possible characters\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":256,"value":"viewof n = slider({\n min: 1,\n max: 5,\n step: 1,\n value: 2,\n description:\n \"n, the length of the string\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":131,"value":"present(\n drawPalette(\n [n,Math.pow(k,n),k,BRGC(k,n)]\n ),\n `${k}-ary string of length ${n}`\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":682,"value":"animationLoop = {\n let i = 0;\n while (i < 8) {\n yield Promises.delay(1000, ++i);\n if (i == 8) i = 0;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":790,"value":"recursiveAnimation = [[2,Math.pow(2,3),2,BRGC(2,2)],\n [3,Math.pow(2,3),2,l1],\n [3,Math.pow(2,3),2,l2],\n [3,Math.pow(2,3),2,BRGC(2,3)]]","pinned":false,"hidden":false,"mode":"ojs"},{"id":793,"value":"successorAnimation = [[3,Math.pow(2,3),2,BRGC(2,3).slice(0,1)],\n [3,Math.pow(2,3),2,BRGC(2,3).slice(0,2)],\n [3,Math.pow(2,3),2,BRGC(2,3).slice(0,3)],\n [3,Math.pow(2,3),2,BRGC(2,3).slice(0,4)],\n [3,Math.pow(2,3),2,BRGC(2,3).slice(0,5)],\n [3,Math.pow(2,3),2,BRGC(2,3).slice(0,6)],\n [3,Math.pow(2,3),2,BRGC(2,3).slice(0,7)],\n [3,Math.pow(2,3),2,BRGC(2,3).slice(0,8)]]","pinned":false,"hidden":false,"mode":"ojs"},{"id":555,"value":"l1={\n let r = [];\n let t = BRGC(2,2);\n for (let i = 0; i < t.length; i++) {\n r.push([0].concat(t[i]))\n }\n return r;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":558,"value":"l2={\n let r = [];\n let t = BRGC(2,2);\n for (let i = 0; i < t.length; i++) {\n r.push([0].concat(t[i]))\n }\n for (let i = 0; i < t.length; i++) {\n r.push([1].concat(t[i]))\n }\n return r;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":128,"value":"drawPalette = params => {\n\n let w = params[0];\n let h = params[1];\n let channels = params[2];\n let intList = params[3];\n \n let c = DOM.context2d(w, h, 1);\n let data = c.getImageData(0, 0, w, h); // maybe just intialize as 0's = new Uint8ClampedArray([1, 2, 3]);\n let i = 0;\n for (let code of intList) {\n for (let num of code) {\n data.data[i] = (channels - num - 1) * 255 / channels;\n data.data[i + 1] = (channels - num - 1) * 255 / channels;\n data.data[i + 2] = 180;\n data.data[i + 3] = 255;\n i += 4; \n }\n }\n console.log(data);\n c.putImageData(data, 0, 0);\n c.canvas.style = `width: ${w * 40}px; height: ${h *\n 100 / (k * n)}px;image-rendering: pixelated`;\n return c.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":134,"value":"present = (\n thing,\n name\n) => html`

\n${thing}\n

${name}

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":44,"value":"// Generates binary reflected gray code recursively\nfunction BRGC(n,k) {\n if (k == 1) return [...Array(n).keys()].map(x => [x]);\n let ret = [];\n for (let i = 0; i < n; i++) {\n let suffixes = BRGC(n, k - 1);\n if (i % 2 == 1) suffixes.reverse();\n for (let j = 0; j < suffixes.length; j++) {\n ret.push([i].concat(suffixes[j]));\n }\n }\n return ret;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":244,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}