Skip to main content
6 of 6
Commonmark migration

Longest hypercube path

Challenge

You are given two distinct bit strings of the same length. (For example, 000 and 111.) Your goal is to find a path from one to the other such that:

  • At each step, you change only one bit (you can go from 000 to any of 001, 010, 100).
  • You cannot visit the same bit string twice.
  • The path is as long as possible, under these constraints.

For example, going from 000 to 111, we can take the path

000, 001, 011, 010, 110, 100, 101, 111

which visits all 8 bit strings of length 3, so it has to be the longest possible.

Rules

  • Standard loopholes apply.
  • You may take the input as two strings of zeroes and ones, or as two arrays of zeroes and ones, or as two arrays of boolean values.
  • You may not take the input as two integers with the right binary representation (writing 000 and 111 as 0 and 7 is not valid).
  • If you want, you may take the length of the bit strings as input.
  • Your program is allowed to output the path by printing the bit strings visited one at a time, or by returning an array of the bit strings visited (each in the same format as the input).
  • Your output should include the start and end of the path (which are your inputs).
  • This is , the shortest code in bytes wins.

Examples

0 1 -> 0, 1
10 01 -> 10, 00, 01 or 10, 11, 01
000 111 -> any of the following:

   000, 100, 110, 010, 011, 001, 101, 111

   000, 100, 101, 001, 011, 010, 110, 111

   000, 010, 110, 100, 101, 001, 011, 111

   000, 010, 011, 001, 101, 100, 110, 111

   000, 001, 101, 100, 110, 010, 011, 111

   000, 001, 011, 010, 110, 100, 101, 111

1001 1100 -> 1001, 0001, 0000, 0010, 0011, 0111, 0101, 0100, 0110, 1110, 1010, 1011, 1111, 1101, 1100 (other paths exist)
Misha Lavrov
  • 5.3k
  • 13
  • 27