Visualizing a forest of happy trees.
Source code related to this post is available here.
This project was inspired by this video, 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 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.
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!
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.
My first attempt resulted in this image (click for 5000x5000 version):
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.
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:
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.
After talking with Mr. Marco 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:
4th power:
5th power:
6th power:
A couple things to note:
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.
-----
Published 2015-11-21
