# Identify identicon icons

Stack Exchange users who have not uploaded a personal profile picture will have their generated identicon as their avatar. Inspired by this, I decided to create my own identicon specification.

It takes a string, hashes it into a 64-bit value (exact method not important for this puzzle), then generates the corresponding identicon from the hash. Your task is to reverse-engineer it. An answer will describe the process for generating one of these identicons from a given hash.

Examples (click on image to see original size)

Hash Identicon
ce6bef6e48294cdb
07e89855b946865d
cdec55a0d461aa45
ab00816d87576195
6a6f31112bcc2f52
7b738a271159ddb0
51f4b4567ba20633
1b91e674c1d0a271
bd5587e6f23b3199
c9f4c16885546d6a

To start, I looked at

the elements that make up each identicon.
I will ignore the colors for now, and just call them "black" and "white". The top-left quadrant is a 4x4 grid of 'blocks'; each block is either all-black, all-white, or split in half one of eight ways. (All eight appear, even if you restrict it to the top-left quadrant, but it's still possible there are some positional restrictions that I haven't noticed yet.)

So, the most straightforward way to do this would be to

take groups of 4 bits, turn each group into a shape (with a table of 16 possible shapes), and then put the shapes in the grid one-by-one.

This, of course, doesn't work. But it's possible that a similar procedure is being used. So I'll start by decomposing these into bits, and looking for places where common shapes correspond to common bits.

I'll label these sections:

No better place to start than with the top left corner, block A.

Four of the identicons are all-black in that block: the second, third, seventh, and tenth. Do these bits match in any contiguous sections?

They do! In those four bitstrings, bits 8-11 are all 1. This makes sense - all-1 would be a natural pattern to assign to the "fully black" cell.
Well, if all-1 is all-black, then surely all-0 is all-white? But the first bit there doesn't fit that pattern. And the two ◢ shapes match in their last three bits - this would make me want to discard the first bit... and say bits 9-11 are that upper-left block.
But there's a separate problem: the ◥ shape matches the ◢s in bits 9-11 (and one of them in bits 8-11)! So this probably isn't completely right... nevertheless, I still feel like I'm onto something with "all 1 = black, all 0 = white" Those bits line up too perfectly for me to ignore.

I'll investigate block F next - there are a lot of all-black and all-white cells there.

Once again, there are some perfect matches in bit patterns. This makes me more confident that I have the right idea. But this time, there are only two of them...
Actually, hold on a minute. The two triangles there are all 01 rather than 00 or 11. The same holds for bits 9-10 with block A; those two bits are the same exactly when we have a filled block. Maybe if a certain pair of bits match, the block is filled/empty, and if they don't, it's split in half? To make this actually deterministic, we'd need some way to decide how it's split in half... but this seems like a good start.

I continue this analysis for all the other blocks:

It looks pretty good! And there's now a natural way to decide how to fix the ambiguities I had before:

So, the rule for the shapes is:

The 64 bits are interpreted in the pattern:
aabbeeff AABBEEFF ccddgghh CCDDGGHH iijjmmnn IIJJMMNN kklloopp KKLLOOPP

Each set of bits is taken in the order XXxx, and then looked up in the following table:

These shapes are then placed in the top-left quadrant in standard reading order; finally, the shape is mirrored right and down.

Now for the colors:

Taking the RGB values of the colors, I noticed that each time, exactly one of them was 00, one was FF, and one was in between.

Converting to HSV made things clearer: saturation and value for these colors are all 100.
For the hue, I did a bit of experimentation:
These bytes (almost) match up: it appears that the hue is the second half of the hash, reinterpreted as a fraction of FFFFFFFF. (They're off slightly, but not by much - presumably this is rounding error due to color space conversion, and the discretization of color back into RGB for creating the images.)