1306. A Single-Bit-Change Tour Starting Anywhere
Print an ordering of all 2^n values of n bits in which consecutive values
differ in exactly one bit, the LAST value differs from the first in exactly one
bit too, and the ordering STARTS at a given value s.
n=2 s=0 -> 0 1 3 2
n=2 s=1 -> 1 0 2 3
n=3 s=5 -> 5 4 6 7 3 2 0 1
Problem 1298 is this with s = 0.
## What most people try first
Generating #1298's sequence and then rotating it so that s comes first. That
fails, and seeing why is the point. #1298's order is 0 1 3 2 6 7 5 4 for
n = 3; rotating it to start at 5 gives 5 4 0 1 3 2 6 7, and the step from 4
to 0 changes one bit while the step from 4 to 0... in fact 4 and 0 differ in one
bit, so that join is fine. The join that breaks is the new wrap: the last value
7 and the first value 5 differ in TWO bits. Rotation preserves every internal
step and breaks the wrap, so it produces a single-bit PATH but not a cycle.
The other instinct is to search: build the tour by backtracking over which bit to flip next. That is exponential and unnecessary.
## XOR the whole sequence by s
answer[i] = s XOR gray(i) for i = 0 .. 2^n - 1
Three things have to be checked, and all three follow from one property of XOR:
XORing by a fixed constant is a bijection on n-bit values, and it preserves
differences, since (s^a) XOR (s^b) = a XOR b.
It starts at s, because gray(0) = 0 and s XOR 0 = s.
It visits everything exactly once, because gray is a bijection by #1299 and
XOR by s is a bijection, so the composition is one too.
Consecutive values differ in exactly one bit, because the difference
(s ^ gray(i)) XOR (s ^ gray(i+1)) equals gray(i) XOR gray(i+1), and s
cancels out entirely. So every step inherits #1298's single-bit property,
including the wrap from the last entry back to the first, which in #1298 is
gray(2^n - 1) XOR gray(0): a single bit, since gray(2^n - 1) = 2^(n-1).
That is the whole argument, and it is why no rotation and no search is needed.
## What the construction says more generally
The Gray cycle is VERTEX-TRANSITIVE: the hypercube looks the same from every
corner, so a Hamiltonian cycle through it can be slid to start anywhere without
changing its shape. XOR by s is the map that does the sliding, and it is a
symmetry of the hypercube rather than a renumbering of the tour.
This is the useful generalisation: when a structure has a symmetry group, a solution starting at one point extends to all of them for free, and finding the symmetry is cheaper than redoing the construction.
## Width
n is at most 16, so values are below 65536 and s is below 2^n.
Everything fits in a signed 32-bit integer, limit 2147483647, with fifteen
bits to spare, and the sequence has at most 65536 entries.
JavaScript is safe with plain Numbers, because ^ and >> coerce to signed
32 bits and every value already fits. Nothing here needs 64 bits or BigInt.
Constraints - `0 ≤ n ≤ 16` - `0 ≤ s < 2^n`, and `s` is 0 when `n` is 0
Input
A single line containing two integers n and s, separated by a space.
Output
Print the 2^n values on one line, separated by single spaces, beginning with s, such that consecutive values and also the last and first differ in exactly one bit.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.