Test if a Gray code is Beckett

Question

Background

An \$n\$-bit Gray code is an ordering of \$2^n\$ binary sequences so that adjacent sequences always differ by exactly one bit.

A Beckett-Gray code is a special kind of Gray code. In addition to being a Gray code, it has the following characteristics:

• It is cyclic: the last bit pattern has one bit difference with the first pattern. (Your input is guaranteed to be cyclic)
• The first pattern is all zeros. (Your input is guaranteed to start with 0)
• Whenever a bit turns from 1 to 0, that bit is the one which has been 1 for the longest time (consecutively). (You need to verify this)

It is known that a Beckett-Gray code exists for \$n=2, 5, 6, 7, 8\$, but does not exist for \$n=3\$ and \$4\$. It is not known if any such code exists for \$n \ge 9\$, and no constructive methods to build such a code are known.

One example for \$n=5\$ is as follows (copied from this paper, 1-0 transition marked):

00000, 00001, 00011, 00010, 00110, 00111, 00101, 01101,
                         ^                   ^
01001, 01000, 01010, 01011, 11011, 10011, 10111, 10101,
  ^        ^                        ^               ^
10100, 00100, 01100, 11100, 11000, 11010, 10010, 10110,
    ^  ^                      ^            ^
11110, 01110, 01111, 11111, 11101, 11001, 10001, 10000
       ^                       ^     ^     ^         ^

Task

Given a cyclic Gray code starting with an all-zero pattern, determine if it is a Beckett-Gray code.

You may take input as a sequence of boolean arrays (possibly transposed), a sequence of strings, or a sequence of equivalent integers. Also, you may optionally take the value of \$n\$ as the second input.

For output, you can choose to

1. output truthy/falsy using your language's convention (swapping is allowed), or
2. use two distinct values to represent true (affirmative) or false (negative) respectively.

Standard code-golf rules apply. Shortest code in bytes wins.

Test cases

Each test case is separated with an empty line.

Truthy (Beckett)

0, 1

00, 01, 11, 10

00, 10, 11, 01

00000, 00001, 00011, 00010, 00110, 00111, 00101, 01101,
01001, 01000, 01010, 01011, 11011, 10011, 10111, 10101,
10100, 00100, 01100, 11100, 11000, 11010, 10010, 10110,
11110, 01110, 01111, 11111, 11101, 11001, 10001, 10000

00000, 01000, 01001, 00001, 00011, 01011, 01010, 11010,
11000, 10000, 10001, 11001, 11101, 01101, 01111, 01110,
00110, 00010, 10010, 10110, 10100, 10101, 00101, 00111,
10111, 10011, 11011, 11111, 11110, 11100, 01100, 00100

Falsy (Not Beckett)

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

0000, 1000, 1100, 1110, 1111, 1101, 0101, 0001,
1001, 1011, 1010, 0010, 0011, 0111, 0110, 0100

00000, 00001, 00011, 00010, 00110, 00111, 00101, 00100,
01100, 01101, 01111, 01110, 01010, 01011, 01001, 01000,
11000, 11001, 11011, 11010, 11110, 11111, 11101, 11100,
10100, 10101, 10111, 10110, 10010, 10011, 10001, 10000

Answer 1

Husk, 9 bytes

Λ≡½hÖ▼Ẋz-

Try it online! (Version with formatting header to allow pasting testcases: Try it online!)

Explanation

If we compute differences from each binary sequence to the next with an element-by-element subtraction, we will get a series of results each containing a single -1/+1 on the flipped bit and a 0 on all other bits. In order for this Gray code to be Beckett, the subsequence of -1 lists must be identical to the subsequence of +1 lists (except for the sign).

As noted by Unrelated String we don't need to check the last element against the first, since it will always consist of a single 1 turning into a 0.

 Λ≡½hÖ▼Ẋz-    Input: list of binary sequences
       Ẋ      For each pair of adjacent sequences:
        z-       subtract the first from the second element by element
     Ö▼       Sort by the minimum (in place): all the -1 sequences move to the beginning
    h         Discard the last (would match the final sequence turning into the first)
   ½          Group the sequences into two lists of equal length 
                (the first will contain the -1s, the second the +1s)
 Λ            Check that the two elements
  ≡           Have the same distribution of zeros/nonzeros

Answer 2

APL (Dyalog Classic), 35 bytes

{(∊⍸¨↓b)≡(∨/b←2>⌿⍵)/¯1↓⊣/⍒⍤1⊥⍨¨,⍀⍵}

-27 from Bubbler, -13 for pointing out the input is a Gray code, -3 for removing an excess variable, and another -11 for just being an all round golfing god.

{(∊⍸¨↓b)≡(∨/b←2>⌿⍵)/¯1↓⊣/⍒⍤1⊥⍨¨,⍀⍵}
                            ⊥⍨¨,⍀⍵ ⍝ cumulative sums (time a 1 has been there)
                    ¯1↓⊣/⍋⍤1       ⍝ index of maxima (without last element)
         (∨⌿b←2>/⍵)/               ⍝ filter where 1s change to 0s
 (∊⍸¨↓b)≡                          ⍝ does that equal the locations of 1s?

Try it online!

Answer 3

J, ³² 25 bytes

[:-:/[:(|/.~/:~"1)2-/\,&0

Try it online!

Based on Leo's excellent idea

• 2-/\,&0 Adjacent elementwise row deltas, with an extra row of zeros appended first.
• (|/.~/:~"1) Group by sorted rows and take absolute value. This puts all rows with a single 1 into one bucket, and all rows with a single -1 into another.
• [:-:/ Are those buckets equal?

Answer 4

Python 2, 62 bytes

Output is via exit code: 0 if it is a Beckett-Gray Codex and 1 otherwise.

a=p,=[1]
for x in input():0<p-x!=a.pop(0)<_;a+=[x-p]*(x>p);p=x

Try it online!

Answer 5

JavaScript (Node.js), 55 bytes

a=>a.every(n=>(n-=a[++i]|0)>0?m<(m=a[-n]):a[n]=i,i=m=0)

Try it online!

Input an array of equivalent integers, output true / false.

a=>a.every(n=>
  (
    n-=a[++i]|0 // compare current one with next one
                // if current one is the last one, we compare with 0
  )>0?
    // > 0 means some digit changed 1->0
    m<(m=a[-n]) // We use a[-n] to remember when 0->1 happened
                // We use m to remember where the related 0->1
                //    happened for last 1->0 change
                // If we find out related 1->0 changing earlier
                //    than m, it is not Beckett
                //    and we return false
                // Remember the where the related 0->1 mutation for current
                //    1->0 happened by assigning m
    // < 0 means some digit changed 0->1
    a[n]=i // Remember where 0->1 mutation happened for digit -n
           // This is always truthy too
 ,i=m=0)

Answer 6

Jelly, 10 bytes

_ƝµṂƇNṖ⁼ṬƇ

Try it online!

Semi-translation of Leo's excellent Husk answer.

_Ɲ            Take the vectorized differences between adjacent elements.
              (The deltas builtin, I, vectorizes itself instead.)
   ṂƇ         Filter by minimum, keeping elements containing -1.
     N        Negate.
      Ṗ       Remove the last element.
       ⁼      Is this list equal to
  µ           the differences
        ṬƇ    filtered to only elements containing 1?

Ṭ was originally Ṁ (maximum), but this produced a false negative on the first test case, as the largest element of [-1] is -1 rather than 0. Ṭ produces an array with ones at the provided indices and zeros elsewhere, but ignores non-positive indices, producing an empty array (which is falsy) if there are no positive indices.

Jelly, 15 13 bytes

ṛa+ɗ\>TẇM{ʋƝP

Try it online!

-2 removing ṙ1 because the all-zeros pattern can essentially be ignored--if you flip the last bit off, you already know it's the one that's been on the longest

Takes input as an array of Boolean arrays, and outputs 0 or 1.

   ɗ\            Cumulatively reduce the input by:
ṛ                right argument
 a               vectorizing-logical-AND
  +              the vectorized sum of the arguments.
ṛa+ɗ\            This turns each 1 into how "long" it's been a 1, consecutively.
          ʋƝ     For each pair of adjacent elements from that result:
      T          are the indices at which
     >           the right is less than the left
       ẇ         a sublist of
        M{       the maximal indices of the left?
            P    Take the product of the results.

Answer 7

Python 3, ^{138 \$\cdots\$ 102} 95 bytes

Saved 13 bytes thanks to rak1507!!!
Saved 7 bytes thanks to dingledooper!!!

def f(b):
 r,*u=1,
 for x,y in zip(b,b[1:]):
  if x<y:u+=x^y,
  else:r&=u.pop(0)==x^y
 return r

Try it online!

Inputs a Gray-cyclic code starting with \$0\$ as list of integers and returns 1 is it's a Beckett-Gray code or 0 otherwise.

Answer 8

JavaScript (V8), 106 bytes

a=>!a.some((c,i)=>c.map((x,j)=>n+=x<(y=(a[i+1]||a[0])[j])?!!o.push(j):x>y?1<<o.shift()-j:0,n=0)&&n-1,o=[])

Try it online!

Accepts input as a 2-dimensional array of booleans.

Answer 9

Charcoal, 34 bytes

¹≔⁰ζＦＩ⮌Ａ«¿›ζιＦ¬⁼⁻ζι⊟υ⎚≔⁺⟦⁻ιζ⟧υυ≔ιζ

Try it online! Link is to verbose version of code. Takes input as strings and outputs a Charcoal boolean, i.e. - for a Beckett-Gray code, nothing if not. Explanation:

¹

Start by assuming that the input is a Beckett-Gray code.

≔⁰ζ

Initialise the previous value to 0.

ＦＩ⮌Ａ«

Convert the input to decimal (leading zeros aren't allowed as numeric input, but the cast operator is fine with them) and loop through it in reverse order. (I hope this works, as it saves a byte over skipping the leading string of all zeros.)

¿›ζι

If the previous value is greater than this value, ...

Ｆ¬⁼⁻ζι⊟υ⎚

... then if the oldest saved value is not the same as a difference then clear the canvas, as this is not a Beckett-Gray code.

≔⁺⟦⁻ιζ⟧υυ

Otherwise prepend the difference to the queue.

≔ιζ

Save the current value.

Answer 10

C (gcc), 95 bytes

t;r;b;e;f(a,n)int*a;{int l[n];for(b=e=r=1;--n;)t=*a^a[1],r&=*a++<*a?l[e++]=t,1:l[b++]==t;r=r;};

Try it online!

Port of my Python answer.

Inputs an array of integers and its length (since length of arrays passed into functions as pointers are undefined in C) and returns 1 is it's a Beckett-Gray code or 0 otherwise.

Answer 11

R, 73 64 bytes

function(m,d=diff(rbind(m,0)),`-`=rowSums)any(d[-d>0,]+d[-d<0,])

Try it online!

Based on the idea in Leo's Husk answer.

Takes input as a matrix m of 1s and 0s with each pattern corresponding to a row. Outputs a swapped T/F value (in the footer, the results are swapped back).