30:Tab5,## How to approach decoding the badges I initially struggled to identify the encoding rules, so thought I'd note down my thoughts here. ### Some facts - Dots come in two sizes, small and large. - There are 6 dots in the top red row and 5x5 blue dots - The blue dots have 3 possible backgrounds (approximate square shapes): white, light blue and dark blue - The combinations of counts of blue dots over each background colour (e.g. 3 white, 3 dark blue, 5 light blue in the top-left badge) are unique within the set of 9 badges provided. - All the squares have the same 'C' arrangement in all 9 sample badges - Squares are only approximate, with minor irregularities to the vertex positions - We don't know from the puzzle description whether or not there is any redundancy in the encoding (i.e. whether more than one visual arrangement can encode the same Fibonacci number). - The first 12 [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_sequence) are `0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89`, which may be useful when exploring possible coding schemes. ### Some inferences and assumptions - The two sizes of dots suggest some form of binary encoding. This is supported by the regular positioning of dots in rows (or columns) - Considering dot size alone there are 31 (6 + 5x5) bits of information encoded in their size and position. Perhaps this is not a coincidence that this is the same as the positive number encoding of a typical 32 bit integer (the remaining bit being used for negative number encoding). - Because there are 6 red dots but only 5 blue dots in each row, the red and blue dots should probably be considered separately (as opposed to using the red dots as some kind of column heading for the blue dots). - It may not be coincidental that background squares have 3 states (dark blue, light blue and white) and a Fibonacci expression involves 3 numbers (${tex`F_n = F_{n-2} + F_{n-1}`}) - Binet's formula can determine if a number is in the Fibonacci sequence if either of ${tex`5x^2 \pm 4`} is a perfect square. Perhaps it is not a coincidence that we have a 5x5 square of symbols in each badge. - The 9 example patterns all have the same concentric 'C' arrangement of squares. It seems reasonable to assume this will be the case for all 25 badges. Perhaps this places the dots into three separate sets. Could also be used as a form of orientation check, in much the same way as the [3 larger squares in a QR code](https://en.wikipedia.org/wiki/QR_code). It could also be as simple as 'C' for 'City'. - The irregularities in the squares appear random and with a degree of irregularity that seems pretty consistent across squares. I assume these are for aesthetic purposes only and not forms of encoding. 31:T474,function drawBadge(n) { const fibData = toFibBin(n); const indexData = posIndex(fibData.redRow); const scale = 3; return Plot.plot({ width: 110 * scale, height: 150 * scale, margin: 12 * scale, x: { axis: null, domain: [0, 4], type: "linear" }, y: { axis: null, domain: d3.range(0, 6), reverse: true }, r: { domain: [0, 1], range: [scale, 8 * scale] }, color: { domain: [0, 1, 2], range: ["white", "rgb(182,210,242)", "rgb(106,160,207)"] }, marks: [ Plot.dot(squares, { x: "x", y: "y", fill: "z", symbol: "square", r: 10 * scale }), Plot.dot(fibData.dots, { x: "x", y: "y", fill: "rgb(0,84,146)", r: (d) => (d.z === "1" ? 1 : 0) }), Plot.dot(indexData, { x: "x", y: 5, fill: "rgb(224,64,64)", r: (d) => (d.z === "1" ? 1 : 0) }), Plot.text([`F(${fibIndex}) = ${seq[fibIndex].F}`], { x: 0, y: 0, dx: -7 * scale, dy: 15 * scale, fontSize: 8 * scale, textAnchor: "start" }) ] }); }32:[{"id":"187cfc14f638b5aa71398339acb3cc23a19c6e8f0c3d395a8e76ba1e4970f2d9bff64a108c807719821d3416950459c9d4970360746904ad349d403e471ef782","href":"https://static.observableusercontent.com/files/187cfc14f638b5aa71398339acb3cc23a19c6e8f0c3d395a8e76ba1e4970f2d9bff64a108c807719821d3416950459c9d4970360746904ad349d403e471ef782","name":"fibFriend.grid.9up.png","type":"image/png","lastModified":1728113963344.609,"size":208109},{"id":"4dd22cd8ae6ddea9be7fe81a3d21ec15db5f4aff644911d548ef7c810cdee842302e847da5981be9968a8eb7227936372374aa351113cbfaddab8c5c2b7ec2c6","href":"https://static.observableusercontent.com/files/4dd22cd8ae6ddea9be7fe81a3d21ec15db5f4aff644911d548ef7c810cdee842302e847da5981be9968a8eb7227936372374aa351113cbfaddab8c5c2b7ec2c6","name":"badge.jpg","type":"image/jpeg","lastModified":1728287687611.653,"size":554347}] 2e:{"title":"Fib Friends","cells":[{"id":0,"value":"# Fib Friends","pinned":false,"hidden":false,"mode":"md"},{"id":55,"value":"[@jsndyks](https://observablehq.com/@jsndyks) designed some badges to give to students as part of an induction to his creative coding class. Each student was given a badge with some coloured symbols on it. ","pinned":false,"hidden":false,"mode":"md"},{"id":410,"value":"badge = FileAttachment(\"badge.jpg\").image({ width: 240 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":416,"value":"Students were told there were 25 different versions in all, and were encouraged to find others that shared the same badge.\n\nA challenge was to work out what was encoded on each badge, and what the encoding rules were. Some clues were given:\n\n- Each badge represents a number from the Fibonacci sequence\n- 9 of the 25 badges look like this:","pinned":false,"hidden":false,"mode":"md"},{"id":3,"value":"FileAttachment(\"fibFriend.grid.9up.png\").image({ width: 640 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":58,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":91,"value":"### Binary coding rows and columns\n\nMy first attempt was to convert each row of the badge from its binary (large dot = 1; small dot =0) to decimal, to see if that yielded some Fibonacci-friendly numbers.","pinned":false,"hidden":false,"mode":"md"},{"id":184,"value":"

\n${binRows(badges[0])}\n ${binRows(badges[1])}\n ${binRows(badges[2])}\n ${binRows(badges[3])}\n ${binRows(badges[4])}\n ${binRows(badges[5])}\n ${binRows(badges[6])}\n ${binRows(badges[7])}\n ${binRows(badges[8])}\n

","pinned":false,"hidden":false,"mode":"md"},{"id":249,"value":"No obvious Fibonacci numbers there. I tried reversing the order of bits in each row before performing the binary to decimal conversion, but again, nothing Fibonacci-like in the numbers. I also tried transposing the 5x5 grid to see if the bits were arranged in columns. Again, no Fibs.","pinned":false,"hidden":false,"mode":"md"},{"id":252,"value":"### Binary coding the groups of rows\n\nGiven the fact that the 31 dots in each badge could be used to represent any positive 32 bit signed integer, my next approach was to encode the full string of bits into a single decimal number:","pinned":false,"hidden":false,"mode":"md"},{"id":258,"value":"

\n${binAll(badges[0])}\n ${binAll(badges[1])}\n ${binAll(badges[2])}\n ${binAll(badges[3])}\n ${binAll(badges[4])}\n ${binAll(badges[5])}\n ${binAll(badges[6])}\n ${binAll(badges[7])}\n ${binAll(badges[8])}\n

","pinned":false,"hidden":false,"mode":"html"},{"id":283,"value":"I am not capable of recognising whether or not any of those large numbers are part of the Fibonacci sequence, so I took advantage of Binet's formula above (${tex`5x^2 \\pm 4`} is a perfect square) to test if each was part of the sequence:","pinned":false,"hidden":false,"mode":"md"},{"id":286,"value":"

\n${testAll(badges[0])}\n ${testAll(badges[1])}\n ${testAll(badges[2])}\n ${testAll(badges[3])}\n ${testAll(badges[4])}\n ${testAll(badges[5])}\n ${testAll(badges[6])}\n ${testAll(badges[7])}\n ${testAll(badges[8])}\n

","pinned":false,"hidden":false,"mode":"html"},{"id":311,"value":"Given that the first red row contains 6 digits and the square rows contain 5, I then tried encoding them separately: one for the top row, the other the sequence of 25 values in the square row-wise from top-left:","pinned":false,"hidden":false,"mode":"md"},{"id":264,"value":"

\n${binGrid(badges[0])}\n ${binGrid(badges[1])}\n ${binGrid(badges[2])}\n ${binGrid(badges[3])}\n ${binGrid(badges[4])}\n ${binGrid(badges[5])}\n ${binGrid(badges[6])}\n ${binGrid(badges[7])}\n ${binGrid(badges[8])}\n

","pinned":false,"hidden":false,"mode":"html"},{"id":314,"value":"Are any of these blue numbers in the Fibonacci sequence?","pinned":false,"hidden":false,"mode":"md"},{"id":316,"value":"

\n${testGrid(badges[0])}\n ${testGrid(badges[1])}\n ${testGrid(badges[2])}\n ${testGrid(badges[3])}\n ${testGrid(badges[4])}\n ${testGrid(badges[5])}\n ${testGrid(badges[6])}\n ${testGrid(badges[7])}\n ${testGrid(badges[8])}\n

","pinned":false,"hidden":false,"mode":"html"},{"id":50,"value":"Bingo! The 5x5 grid of blue dots in all 9 badges encode a Fibonacci number! But what about the top red row? Looking at the pattern it is clear that smaller red numbers are associated with smaller Fibonacci numbers. A fairly obvious possibility is revealed: that the red number represents the _index_ of the Fibonacci number, i.e. its position in the Fibonacci sequence. Displaying the first 38 Fib numbers in sequence confirms this:","pinned":false,"hidden":false,"mode":"md"},{"id":165,"value":"tex`${fibSequence(37).map((d) => `F_{${d.n}}=${d.F}\\\\newline`)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":400,"value":"## Some more badges\n\nNow we have the ability to encode any Fibonacci number that does not exceed ${tex`2^{25}-1`} (${Math.pow(2,25)-1}), we can generate our own badges. That gives us 37 different Fib numbers to choose from (the next in the sequence would exceed ${Math.pow(2,25)-1}). You can cycle through them below:","pinned":false,"hidden":false,"mode":"md"},{"id":549,"value":"drawBadge(fibIndex)","pinned":false,"hidden":false,"mode":"ojs"},{"id":693,"value":"viewof fibIndex = Scrubber(d3.range(0, 38), {\n autoplay: false,\n loop: false,\n delay: 500\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":402,"value":"## What about those blue squares?\n\nSo do the blue squares have any special meaning? Do the bits in each of the three levels have particular qualities? While they may not be necessary to decode the badges, it is left as an exercise for the reader to determine if they have any special significance. How might you investigate this systematically?","pinned":false,"hidden":false,"mode":"md"},{"id":763,"value":"## Advanced Challenge\n\nLooking at the transitions of large dots when running the animation above, it occurred to me that there might be a cellular automaton that could transition from one Fib arrangement to the next. Does such an automaton exist? What would be its transition rules?\n\n(I'm no expert on these matters, so perhaps the answer is obvious to you)","pinned":false,"hidden":false,"mode":"md"},{"id":94,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md"},{"id":697,"value":"import { Scrubber } from \"@mbostock/scrubber\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":96,"value":"_Binary representation of the circle sizes:_","pinned":false,"hidden":false,"mode":"md"},{"id":11,"value":"badges = [\n { redRow: \"100011\", dots: [\"01000\", \"11001\", \"10011\", \"00110\", \"01001\"] },\n { redRow: \"010011\", dots: [\"00000\", \"00000\", \"00100\", \"00010\", \"10101\"] },\n { redRow: \"100000\", dots: [\"00010\", \"00010\", \"01111\", \"01000\", \"00101\"] },\n { redRow: \"011000\", dots: [\"00000\", \"00001\", \"01101\", \"01001\", \"00000\"] },\n { redRow: \"011011\", dots: [\"00000\", \"00101\", \"11111\", \"11010\", \"00010\"] },\n { redRow: \"010110\", dots: [\"00000\", \"00000\", \"10001\", \"01001\", \"01111\"] },\n { redRow: \"011010\", dots: [\"00000\", \"00011\", \"10110\", \"10001\", \"10001\"] },\n { redRow: \"011110\", dots: [\"00000\", \"11001\", \"01100\", \"10001\", \"01000\"] },\n { redRow: \"010101\", dots: [\"00000\", \"00000\", \"01010\", \"10110\", \"00010\"] }\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":115,"value":"_Is a given number in the Fibonacci sequence?_","pinned":false,"hidden":false,"mode":"md"},{"id":45,"value":"function isFibonacci(n) {\n const perfectSq = (x) => {\n const s = Math.floor(Math.sqrt(x));\n return s * s === x;\n };\n const fiveNSq = 5 * n * n;\n return perfectSq(fiveNSq + 4) || perfectSq(fiveNSq - 4);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":752,"value":"_Provide the first n Fibonacci numbers:_","pinned":false,"hidden":false,"mode":"md"},{"id":159,"value":"function fibSequence(n) {\n let [prev, current] = [0, 1];\n const seq = [\n { n: 0, F: prev },\n { n: 1, F: prev + current }\n ];\n\n for (let i = 2; i <= n; i++) {\n const next = prev + current;\n seq.push({ n: i, F: next });\n prev = current;\n current = next;\n }\n return seq;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":447,"value":"seq = fibSequence(37)","pinned":false,"hidden":false,"mode":"ojs"},{"id":749,"value":"_To display numeric grids:_","pinned":false,"hidden":false,"mode":"md"},{"id":181,"value":"function binRows(badge) {\n return md`\n ${parseInt(badge.redRow, 2) + \": \"}\n ${badge.dots\n .map((d) => parseInt(d, 2))\n .join(\", \")}`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":275,"value":"function binAll(badge) {\n return md`${parseInt(badge.redRow + badge.dots.join(\"\"), 2)}`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":289,"value":"function testAll(badge) {\n return md`${\n parseInt(badge.redRow + badge.dots.join(\"\"), 2) +\n \": \" +\n (isFibonacci(parseInt(badge.redRow + badge.dots.join(\"\"), 2))\n ? \"**Yes**\"\n : \"**No**\")\n }`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":255,"value":"function binGrid(badge) {\n return md`${parseInt(badge.redRow, 2) + \": \"}\n ${parseInt(badge.dots.join(\"\"), 2)}`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":322,"value":"function testGrid(badge) {\n return md`${parseInt(badge.redRow, 2) + \": \"}\n ${\n parseInt(badge.dots.join(\"\"), 2) +\n \": \" +\n (isFibonacci(parseInt(badge.dots.join(\"\"), 2)) ? \"**Yes**\" : \"**No**\")\n }`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":758,"value":"_Decimal to binary string conversion:_","pinned":false,"hidden":false,"mode":"md"},{"id":457,"value":"function decToBinary(dec, digits = 0) {\n const padDigit = dec < 0 ? \"1\" : \"0\";\n // Unsigned right-shift by 0 positions coerces the number into an unsigned integer.\n return (dec >>> 0).toString(2).padStart(digits, padDigit);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":754,"value":"_For drawing assistance:_","pinned":false,"hidden":false,"mode":"md"},{"id":441,"value":"squares = [\n { x: 0, y: 0, z: 1 },\n { x: 1, y: 0, z: 1 },\n { x: 2, y: 0, z: 1 },\n { x: 3, y: 0, z: 1 },\n { x: 4, y: 0, z: 1 },\n { x: 0, y: 1, z: 1 },\n { x: 1, y: 1, z: 2 },\n { x: 2, y: 1, z: 2 },\n { x: 3, y: 1, z: 2 },\n { x: 0, y: 2, z: 1 },\n { x: 1, y: 2, z: 2 },\n { x: 0, y: 3, z: 1 },\n { x: 1, y: 3, z: 2 },\n { x: 2, y: 3, z: 2 },\n { x: 3, y: 3, z: 2 },\n { x: 0, y: 4, z: 1 },\n { x: 1, y: 4, z: 1 },\n { x: 2, y: 4, z: 1 },\n { x: 3, y: 4, z: 1 },\n { x: 4, y: 4, z: 1 }\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":451,"value":"function toFibBin(n) {\n return {\n redRow: decToBinary(n, 6),\n dots: posGrid(decToBinary(seq[n].F, 25))\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":463,"value":"function posGrid(str) {\n const result = [];\n\n for (let y = 0; y < 5; y++) {\n for (let x = 0; x < 5; x++) {\n result.push({\n x: x,\n y: 4 - y,\n z: str[x + 5 * y]\n });\n }\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":539,"value":"function posIndex(str) {\n const result = [];\n for (let x = 0; x < 6; x++) {\n result.push({\n x: (5 * x) / 6,\n z: str[x]\n });\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":419,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}