26
\$\begingroup\$

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 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
\$\endgroup\$
5
  • \$\begingroup\$ Should 000, 010, 110, 100 be added as a falsy test case? \$\endgroup\$
    – rewritten
    Mar 11 at 10:36
  • 3
    \$\begingroup\$ @rewritten It is not a Gray code, since it does not have \$2^n\$ terms. \$\endgroup\$
    – Bubbler
    Mar 11 at 10:53
  • \$\begingroup\$ Would it be legal in a language like C or assembly to take an array where the end is marked by a 0 element? i.e. implicit length instead of a separate explicit length arg. This may be a stretch too far because it opens up the convenience of using the same compare a[i] and a[i+1] as for earlier elements, not just using it as a sentinel. (And because we also expect the first element to be 0, so the end is marked by the 2nd 0). Still, I have a couple x86 asm versions I'm working on (scalar and AVX512); wanted to ask before fully finishing or testing them. godbolt.org/z/59o5eM \$\endgroup\$ Mar 14 at 5:20
  • \$\begingroup\$ @PeterCordes Interesting idea. I'm afraid it does feel stretchy to me though, since any valid input would contain a zero entry, which breaks the 0-terminated input format. You could use -1 (or maybe INT_MIN) for the sentinel value instead. \$\endgroup\$
    – Bubbler
    Mar 14 at 6:42
  • \$\begingroup\$ Just realized that cyclic is guaranteed, so the last bit-pattern has only 1 bit set and thus there's nothing to verify there. A counted loop should work for my ideas, maybe returning the elements-left counter as a 0 / non-0 status. (I made an edit to make it very clear which Beckett properties are already guaranteed and don't need to be tested; many other readers apparently missed that, too. Hopefully it's not too intrusive / noisy.) \$\endgroup\$ Mar 14 at 7:04

11 Answers 11

13
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

J, 32 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?
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
3
  • \$\begingroup\$ Fails for [[0,0,0],[0,0,1],[0,1,1],[0,1,0],[1,1,0],[1,0,0],[1,0,1],[1,1,1]] (should be false) \$\endgroup\$
    – rak1507
    Mar 10 at 1:59
  • 1
    \$\begingroup\$ @rak1507 That isn't a cyclic Gray code, so it isn't a valid input to begin with. \$\endgroup\$ Mar 10 at 2:06
  • 3
    \$\begingroup\$ Sorry, I completely missed that the input is always cyclic, my bad! (this is why you don't code golf at 2am) \$\endgroup\$
    – rak1507
    Mar 10 at 2:07
3
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ bin(z).count('1')==1 can be 1>z&~-z \$\endgroup\$
    – rak1507
    Mar 10 at 1:34
  • \$\begingroup\$ @rak1507 That's very nice, was just looking at that thinking there must be a better way - thanks! :D \$\endgroup\$
    – Noodle9
    Mar 10 at 1:37
  • \$\begingroup\$ Thanks, no problem \$\endgroup\$
    – rak1507
    Mar 10 at 1:41
  • 1
    \$\begingroup\$ I don't think the empty check in u and u.pop... is necessary. Also u+=[x^y] can be replaced with u+=x^y, (all this saves 7 bytes, I think). \$\endgroup\$ Mar 10 at 2:53
  • \$\begingroup\$ @dingledooper Yes, I was thinking that test isn't necessary since we have preconditions starting from \$0\$ and only changing one bit at a time. Really like that list append golf - thanks! :D \$\endgroup\$
    – Noodle9
    Mar 10 at 10:31
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 34 bytes

¹≔⁰ζFI⮌A«¿›ζιF¬⁼⁻ζι⊟υ⎚≔⁺⟦⁻ιζ⟧υυ≔ιζ

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.

FI⮌A«

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, ...

F¬⁼⁻ζι⊟υ⎚

... 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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.