This is fundamental in FPGAs. The mode where the bit is not stable is called metastability. Most FPGA tools can automatically create gray code for state machine states. Also, pretty much all cross clock domain FIFOs will use grey code to indicate read and write pointers’ location.

It sounds to me like this might have been useful for day 10 – the asteroid problem where the monitoring station rotates around detecting and/or destroying asteroids.

More interesting than the AoC puzzle connection is the connection between gray codes and the ancient Chinese rings puzzle, as well as the mathematically equivalent Baguenaudier.

If you like that kind of thing tavern puzzles makes a nice one.

This article motivated me to look into Gray codes. Gray encoding can be done efficiently:

encoded = plain ^ (plain >> 1)

Decoding has a higher runtime. If you decode bit by bit, the decoded value depends on the number of decoded ‘1’ bits on the left of the bit that is being decoded. If it’s odd, we need to toggle the bit to decode, if it’s even, we keep the bit as it is. A naive implementation takes time linear in the number of bits, and a more efficient implementation using some kind of parallel prefix evaluation has a runtime on the order of the logarithm of the number of bits.

It’s a bit similar to multiplication and division, where you the same amount of work, but the latter is inherently slower. The reason for this is that the work can’t be parallelized; you need the intermediate results before you can proceed with each step of the computations.

A way to see the gray code is to think about doing a non self intersecting walk on the hypercube that visits all nodes (that is, find a Hamiltonian cycle on the hyper cube).

This is fundamental in FPGAs. The mode where the bit is not stable is called metastability. Most FPGA tools can automatically create gray code for state machine states. Also, pretty much all cross clock domain FIFOs will use grey code to indicate read and write pointers’ location.

Nice explanation.

I was wondering what puzzle you used gray code for, and how you did use it?

It sounds to me like this might have been useful for day 10 – the asteroid problem where the monitoring station rotates around detecting and/or destroying asteroids.

Interesting. I thought of using Gray Code for handling directions in day 11, but opted for simple bit shifting instead: https://github.com/timvisee/advent-of-code-2019/blob/master/day11a/src/main.rs#L4-L20

More interesting than the AoC puzzle connection is the connection between gray codes and the ancient Chinese rings puzzle, as well as the mathematically equivalent Baguenaudier.

If you like that kind of thing tavern puzzles makes a nice one.

This article motivated me to look into Gray codes. Gray encoding can be done efficiently:

Decoding has a higher runtime. If you decode bit by bit, the decoded value depends on the number of decoded ‘1’ bits on the left of the bit that is being decoded. If it’s odd, we need to toggle the bit to decode, if it’s even, we keep the bit as it is. A naive implementation takes time linear in the number of bits, and a more efficient implementation using some kind of parallel prefix evaluation has a runtime on the order of the logarithm of the number of bits.

It’s a bit similar to multiplication and division, where you the same amount of work, but the latter is inherently slower. The reason for this is that the work can’t be parallelized; you need the intermediate results before you can proceed with each step of the computations.

A way to see the gray code is to think about doing a non self intersecting walk on the hypercube that visits all nodes (that is, find a Hamiltonian cycle on the hyper cube).

I think of that every morning right before my quantum müesli and after my hyperjuice.