Expand description
§Like a Rogue
We represent a trap with a 1 bit and a safe tile with a 0 bit. Writing out the truth table for the rules:
| Left | Center | Right | Output |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 |
We can see that the value of the center doesn’t matter and that the next tile will be a trap if the left and right values are different. We calculate this for all traps at the same time with a bitwise XOR.
Since even columns depend only on odd columns and vice-versa, we split the input into two,
storing each half using 50 bits of a u64.