diff options
Diffstat (limited to '_posts/2015-11-21-happy-trees.md')
| -rw-r--r-- | _posts/2015-11-21-happy-trees.md | 237 |
1 files changed, 237 insertions, 0 deletions
diff --git a/_posts/2015-11-21-happy-trees.md b/_posts/2015-11-21-happy-trees.md new file mode 100644 index 0000000..2ac2850 --- /dev/null +++ b/_posts/2015-11-21-happy-trees.md @@ -0,0 +1,237 @@ +--- +layout: post +title: Happy Trees +--- + +Source code related to this post is available [here](https://github.com/mediocregopher/happy-tree). + +This project was inspired by [this video](https://www.youtube.com/watch?v=_DpzAvb3Vk4), +which you should watch first in order to really understand what's going on. + +My inspiration came from his noting that happification could be done on numbers +in bases other than 10. I immediately thought of hexadecimal, base-16, since I'm +a programmer and that's what I think of. I also was trying to think of how one +would graphically represent a large happification tree, when I realized that +hexadecimal numbers are colors, and colors graphically represent things nicely! + +## Colors + +Colors to computers are represented using 3-bytes, encompassing red, green, and +blue. Each byte is represented by two hexadecimal digits, and they are appended +together. For example `FF0000` represents maximum red (`FF`) added to no green +and no blue. `FF5500` represents maximum red (`FF`), some green (`55`) and no +blue (`00`), which when added together results in kind of an orange color. + +## Happifying colors + +In base 10, happifying a number is done by splitting its digits, squaring each +one individually, and adding the resulting numbers. The principal works the same +for hexadecimal numbers: + +``` +A4F +A*A + 4*4 + F*F +64 + 10 + E1 +155 // 341 in decimal +``` + +So if all colors are 6-digit hexadecimal numbers, they can be happified easily! + +``` +FF5500 +F*F + F*F + 5*5 + 5*5 + 0*0 + 0*0 +E1 + E1 + 19 + 19 + 0 + 0 +0001F4 +``` + +So `FF5500` (an orangish color) happifies to `0001F4` (a darker blue). Since +order of digits doesn't matter, `5F50F0` also happifies to `0001F4`. From this +fact, we can make a tree (hence the happification tree). I can do this process +on every color from `000000` (black) to `FFFFFF` (white), so I will! + +## Representing the tree + +So I know I can represent the tree using color, but there's more to decide on +than that. The easy way to represent a tree would be to simply draw a literal +tree graph, with a circle for each color and lines pointing to its parent and +children. But this is boring, and also if I want to represent *all* colors the +resulting image would be enormous and/or unreadable. + +I decided on using a hollow, multi-level pie-chart. Using the example +of `000002`, it would look something like this: + + + +The inner arc represents the color `000002`. The second arc represents the 15 +different colors which happify into `000002`, each of them may also have their +own outer arc of numbers which happify to them, and so on. + +This representation is nice because a) It looks cool and b) it allows the +melancoils of the hexadecimals to be placed around the happification tree +(numbers which happify into `000001`), which is convenient. It's also somewhat +easier to code than a circle/branch based tree diagram. + +An important feature I had to implement was proportional slice sizes. If I were +to give each child of a color an equal size on that arc's edge the image would +simply not work. Some branches of the tree are extremely deep, while others are +very shallow. If all were given the same space, those deep branches wouldn't +even be representable by a single pixel's width, and would simply fail to show +up. So I implemented proportional slice sizes, where the size of every slice is +determined to be proportional to how many total (recursively) children it has. +You can see this in the above example, where the second level arc is largely +comprised of one giant slice, with many smaller slices taking up the end. + +## First attempt + +My first attempt resulted in this image (click for 5000x5000 version): + +[](/img/happy-tree/happy-tree-atmp1.png) + +The first thing you'll notice is that it looks pretty neat. + +The second thing you'll notice is that there's actually only one melancoil in +the 6-digit hexadecimal number set. The innermost black circle is `000000` which +only happifies to itself, and nothing else will happify to it (sad `000000`). +The second circle represents `000001`, and all of its runty children. And +finally the melancoil, comprised of: + +``` +00000D -> 0000A9 -> 0000B5 -> 000092 -> 000055 -> 00003 -> ... +``` + +The final thing you'll notice (or maybe it was the first, since it's really +obvious) is that it's very blue. Non-blue colors are really only represented as +leaves on their trees and don't ever really have any children of their own, so +the blue and black sections take up vastly more space. + +This makes sense. The number which should generate the largest happification +result, `FFFFFF`, only results in `000546`, which is primarily blue. So in effect +all colors happify to some shade of blue. + +This might have been it, technically this is the happification tree and the +melancoil of 6 digit hexadecimal numbers represented as colors. But it's also +boring, and I wanted to do better. + +## Second attempt + +The root of the problem is that the definition of "happification" I used +resulted in not diverse enough results. I wanted something which would give me +numbers where any of the digits could be anything. Something more random. + +I considered using a hash instead, like md5, but that has its own problems. +There's no gaurantee that any number would actually reach `000001`, which isn't +required but it's a nice feature that I wanted. It also would be unlikely that +there would be any melancoils that weren't absolutely gigantic. + +I ended up redefining what it meant to happify a hexadecimal number. Instead of +adding all the digits up, I first split up the red, green, and blue digits into +their own numbers, happified those numbers, and finally reassembled the results +back into a single number. For example: + +``` +FF5500 +FF, 55, 00 +F*F + F*F, 5*5 + 5*5, 0*0 + 0*0 +1C2, 32, 00 +C23200 +``` + +I drop that 1 on the `1C2`, because it has no place in this system. Sorry 1. + +Simply replacing that function resulted in this image (click for 5000x5000) version: + +[](/img/happy-tree/happy-tree-atmp2.png) + +The first thing you notice is that it's so colorful! So that goal was achieved. + +The second thing you notice is that there's *significantly* more melancoils. +Hundreds, even. Here's a couple of the melancoils (each on its own line): + +``` +00000D -> 0000A9 -> 0000B5 -> 000092 -> 000055 -> 000032 -> ... +000D0D -> 00A9A9 -> 00B5B5 -> 009292 -> 005555 -> 003232 -> ... +0D0D0D -> A9A9A9 -> B5B5B5 -> 929292 -> 555555 -> 323232 -> ... +0D0D32 -> A9A90D -> B5B5A9 -> 9292B5 -> 555592 -> 323255 -> ... +... +``` + +And so on. You'll notice the first melancoil listed is the same as the one from +the first attempt. You'll also notice that the same numbers from the that +melancoil are "re-used" in the rest of them as well. The second coil listed is +the same as the first, just with the numbers repeated in the 3rd and 4th digits. +The third coil has those numbers repeated once more in the 1st and 2nd digits. +The final coil is the same numbers, but with the 5th and 6th digits offset one +place in the rotation. + +The rest of the melancoils in this attempt work out to just be every conceivable +iteration of the above. This is simply a property of the algorithm chosen, and +there's not a whole lot we can do about it. + +## Third attempt + +After talking with [Mr. Marco](/members/#marcopolo) about the previous attempts +I got an idea that would lead me towards more attempts. The main issue I was +having in coming up with new happification algorithms was figuring out what to +do about getting a number greater than `FFFFFF`. Dropping the leading digits +just seemed.... lame. + +One solution I came up with was to simply happify again. And again, and again. +Until I got a number less than or equal to `FFFFFF`. + +With this new plan, I could increase the power by which I'm raising each +individual digit, and drop the strategy from the second attempt of splitting the +number into three parts. In the first attempt I was doing happification to the +power of 2, but what if I wanted to happify to the power of 6? It would look +something like this (starting with the number `34BEEF`): + +``` +34BEEF +3^6 + 4^6 + B^6 + E^6 + E^6 + E^6 + F^6 +2D9 + 1000 + 1B0829 + 72E440 + 72E440 + ADCEA1 +1AEB223 + +1AEB223 is greater than FFFFFF, so we happify again + +1^6 + A^6 + E^6 + B^6 + 2^6 + 2^6 + 3^6 +1 + F4240 + 72E440 + 1B0829 + 40 + 40 + 2D9 +9D3203 +``` + +So `34BEEF` happifies to `9D3203`, when happifying to the power of 6. + +As mentioned before the first attempt in this blog was the 2nd power tree, +here's the trees for the 3rd, 4th, 5th, and 6th powers (each image is a link to +a larger version): + +3rd power: +[](/img/happy-tree/happy-tree-atmp3-pow3.png) + +4th power: +[](/img/happy-tree/happy-tree-atmp3-pow4.png) + +5th power: +[](/img/happy-tree/happy-tree-atmp3-pow5.png) + +6th power: +[](/img/happy-tree/happy-tree-atmp3-pow6.png) + +A couple things to note: + +* 3-5 are still very blue. It's not till the 6th power that the distribution + becomes random enough to become very colorful. + +* Some powers have more coils than others. Power of 3 has a lot, and actually a + lot of them aren't coils, but single narcissistic numbers. Narcissistic + numbers are those which happify to themselves. `000000` and `000001` are + narcissistic numbers in all powers, power of 3 has quite a few more. + +* 4 looks super cool. + +Using unsigned 64-bit integers I could theoretically go up to the power of 15. +But I hit a roadblock at power of 7, in that there's actually a melancoil which +occurs whose members are all greater than `FFFFFF`. This means that my strategy +of repeating happifying until I get under `FFFFFF` doesn't work for any numbers +which lead into that coil. + + All images linked to in this post are licensed under the [Do what the fuck you + want to public license](http://www.wtfpl.net/txt/copying/). |