Dovetail two blocks of bits

Question

Check if two blocks of bits dovetail perfectly.

Specifications

• A block of bits is a fixed sequence of 8 bits just like this for example : 11110101.

• For simplicity we refer to truthy/falsey values as 1/0 bits but they can be everything capable of representing those two states in a clear, well defined and consistent way, for example :0/1 x/y False/True "false"/"true" 'a'/'b' []/[...] odd/even >0 / <0 0 / !0

What does it mean dovetail perfectly?

• 1's bits of one block can fit only into 0's of the other block or outside it.

• You can shift an entire block left or right but you cannot modify a block nor reverse it.

• The resulting block must contain all 1's of both inputted blocks and only those.
  

• There must not be any 0's between 1's while there can be any trailing and leading 0's.

• The resulting block can be more than 8 bits long.

• Example

 Input : [ 10010111, 01011010 ]
 
             10010111 
             ↓  ↓ ↓↓↓
           01011010   <- shif by 2
  result   0111111111  => dovetails perfectly 
 

Input: two blocks of bits.

• You don't need to handle empty blocks (all 0's).

Output: your solution have to clearly state if input blocks can dovetail perfectly as described above or not.

• the resulting block won't be a valid answer.

Test cases.

00000000, 00000000 | you don't  
00000000, ...      | need to
...     , 00000000 | handle these

11111111, 11111111 -> True
11111111, 10000000 -> True
11110000, 00101000 -> False 
00101000, 10100000 -> True
10000000, 00111000 -> True
00110011, 11001100 -> True
00010000, 11101010 -> False
10000100, 10111101 -> True 
01111010, 01011111 -> True 
10010101, 00001101 -> False 
01010011, 10110000 -> True
00000111, 00010011 -> False
00000011, 00000101 -> False

Rules

• Input/output can be given by any convenient method.
• You can print it to STDOUT, return it as a function result or error message/s.
• Either a full program or a function are acceptable.
• Standard loopholes are forbidden.
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

---

Sandbox

Answer 1

JavaScript (ES6),  63 54 52  50 bytes

^{Saved 2 bytes by applying an optimization similar to the one suggested by @AZTECCO on my C answer}

Expects (a)(b), where a and b are bytes. Returns 0 if the blocks can dovetail perfectly or 1 otherwise.

a=>g=b=>b?a<<8&b|(c=a<<8|b,c+=c&-c)&c-1&&g(b<<1):1

Try it online!

How?

The recursive function g attempts to shift b to the left, 1 position at a time, until the following conditions are both met:

• (a << 8) & b is equal to 0, i.e. a << 8 and b have no set bits in common
• c = (a << 8) | b is a sequence of consecutive 1's, possibly followed by trailing 0's

For the second test, we add to c the rightmost set bit in c and see if this results in a single 1, by carry propagation along the sequence of consecutive 1's.

We use the following bitwise tricks:

c & -c      // returns the rightmost set bit in c

c & (c - 1) // returns c without the rightmost set bit in c
            // (0 if c is an exact power of 2)

Example:

0111111000 + (0111111000 & -0111111000) = 0111111000 + 0000001000 = 1000000000
1000000000 & (1000000000 - 1) = 1000000000 & 0111111111 = 0

We stop the recursion when b = 0, which means that all bits have been thrown away. (This is why we do b << 1 instead of b * 2, so that b is forced to a 32-bit integer rather than an IEEE 754 floating-point number.)

Answer 2

Python 3, 68 bytes

lambda a,b:any(a<<8&b<<x==('01'in bin(a<<8^b<<x))for x in range(17))

Try it online!

The function tries all overlap configurations of the two binary sequences. It performs a bitwise xor for each configuration and checks if all the resulting 1s are consecutive. This gives a false positive for some cases where the xor operation results in a leading 0, so additionally it checks if the bitwise and operation yields 0.

-4 bytes thanks to xnor

Answer 3

Python 2, 78 59 57 bytes

Output is via exit code. The program fails (1) for truthy inputs and completes (0) for falsely ones. Input are two non-negative integers.

This is now quite similar to Arnauld's answers, but I found the d&-d trick on this website.

a,b=input()
b<<=8
exec"d=a|b;a&b<1>d&(d&-d)+d>q;a*=2;"*17

Try it online!

Answer 4

C (gcc),  61 58 57  53 bytes

Saved 4 bytes thanks to @AZTECCO

A port of my JS answer.

Returns 0 if the blocks can dovetail perfectly or a non-zero integer otherwise.

c;f(a,b){for(a<<=8;b&&a&b|(c=a|b,c+=c&-c)&c-1;b*=2);}

Try it online!

Answer 5

Jelly,  18  17 bytes

T_8+Ɱ17;ṢIPʋ€T}1e

A dyadic Link accepting two lists of eight ones/zeros which yields 1 if they may dovetail, or 0 if not.

Try it online! Or see the test-suite (I reordered them to have the eight truthy cases followed by the five falsey cases).

There is probably a terser way...

How?

T_8+Ɱ17;ṢIPʋ€T}1e - Link: block A; block B
T                 - truthy indices of A
 _8               - subtract eight from each
     17           - seventeen
   +Ɱ             - map with addition -> a list of the 17 shifted versions of T
            €     - for each:
             T}   -   using the truthy indices of B as the right argument
           ʋ      -   last four links as a dyad:
       ;          -     concatenate
        Ṣ         -     sort
         I        -     incremental differences
          P       -     product (0 if two 1-bits collide; >1 if zero-gaps would result)
               1e - does 1 exist in that result?

Answer 6

05AB1E, 18 bytes

¬0*æδì`âε0ζO0ÚPΘ}à

Input as a pair of lists of bit-integers, outputs 1/0 for truthy/falsey respectively.

Try it online or verify all test cases. (The test suite contains an additional Ù after the æ, otherwise it'll time out. The single TIO takes roughly 35-40 seconds without this uniquify.)

Explanation:

¬                # Push the first list of the (implicit) input-pair (without popping)
 0*              # Multiply each value by 0 to create a list of 0s of that same length
   æ             # Get the powerset of this list of 0s (including empty list)
                 # (prefixes builtin would be preferably here, but unfortunately it lacks
                 #  an empty list; obviously this powerset contains a lot of duplicated
                 #  lists, which is why the uniquify `Ù` in the test suite is used to
                 #  make the program faster)
    δ            # Apply double-vectorized (using the powerset of 0s and implicit input)
     ì           #  Prepend the list of 0s to the inner input-list
      `          # Pop and push both list of lists separated to the stack
       â         # Use the cartesian product to get every possible pair of inner lists
        ε        # Map each pair of lists to:
          ζ      #  Zip/transpose; swapping rows/columns,
         0       #  using a 0 as trailing filler-item if the lists are unequal in length
           O     #  Sum each inner pair
            0Ú   #  Remove all leading and trailing 0s from this list
              P  #  Take the product of the remaining values
               Θ #  And check that this is equal to 1
        }à       # After the map: check if any are truthy by taking the maximum
                 # (after which this is output implicitly as result)

Try it online for a step-by-step from input to output (with the uniquify to speed it up).

Answer 7

Husk, 15 bytes

VΠ¤×ż≠ö→kΣQṠ+mṗ

Try it online! or verify test cases. Output is a positive integer for truthy cases and 0 for falsy.

Explanation

Parentheses added for clarity.

VΠ¤(׿≠)(→kΣQ(Ṡ+mṗ))   Implicit inputs: two lists of integers.
  ¤( A )(     B    )   Apply B to both and combine with A.
         →kΣQ(Ṡ+mṗ)    Argument is a list x.
                m      Map
                 ṗ     primality test
              Ṡ+       and concatenate before x.
                       Since 0 and 1 aren't primes, this effectively prepends 8 zeros.
            Q          All contiguous slices.
          k            Classify (into separate lists)
           Σ           by sum.
         →             Get the last class, i.e. the slices with maximal sum.
                       They are those that contain all the 1s of x.
    ׿≠                Combining function:
    ×                  Cartesian product by
     ż                 zip (preserving overflowing elements) by
      ≠                absolute difference.
                       Now we have a list of all combinations of slices from both extended lists,
                       with 1 and 1 producing 0.
V                      Does any of them have
 Π                     nonzero product (all 1s)?

Answer 8

x86 32-bit machine code, 27 bytes

An x86-64 version would be callable from C as int dovetail(dummy, unsigned x, unsigned y); Returns EAX=0 for dovetail, non-zero for not; all paths of execution for non-zero inputs that don't dovetail lead to EAX=(x<<n)|y as the last thing calculated in EAX before returning. Also more simply and obviously, returns ZF=1 for dovetail, ZF=0 for not.

Try it online!. NASM listing: offset, machine code, source

 1                         dovetail:                   ; bool dovetail (ESI, EDX)
 2 00000000 86F2               xchg  dh, dl             ; shl edx,8 ; upper bytes are zero
 3                         .loop:
 4 00000002 85F2               test  edx, esi
 5 00000004 7510               jnz   .overlap           ; skip any bit conflicts
 6                         
 7 00000006 8D0432             lea   eax, [edx+esi]     ; equivalent to | or ^ for non-overlapping bits
 8 00000009 0FBCC8             bsf   ecx, eax           ; count trailing zeros
 9 0000000C D3E8               shr   eax, cl            ; shift out low zeros
10 0000000E 40                 inc   eax                ; turn contiguous low bits into 1 set bit
11                         
12 0000000F 8D48FF             lea  ecx, [eax-1]        ; clear lowest set bit
13 00000012 21C8               and  eax, ecx            ; like blsr  eax, eax
14 00000014 7404               jz   .dovetail_found     ; there was only 1 set bit, now 0
15                         .overlap:
16 00000016 01F6               add  esi, esi
17 00000018 79E8               jns  .loop             ; keep looping until ESI hits the top
18                         
19                         .dovetail_found:
20                             ;; return value in ZF:
21                                   ; 1 for dovetail detection by BLSR
22                                   ; 0 for exiting loop via ESI setting SF: implies non-zero
23 0000001A C3                 ret

See https://catonmat.net/low-level-bit-hacks for an overview of bithack tricks including isolating or clearing the lowest set bit.

---

Alternate versions:

BMI1 blsr eax, eax is 5 bytes, same as lea edx, [rax-1] / and eax, edx. That would require BMI1 (Haswell+, Piledriver+). I used and instead of test so an integer result in EAX would be available.

BMI1 blsi ecx, eax (5B) / add eax, ecx (2B) (eax += lowest_set_bit(eax)) turned out not to be the shortest way to turn a contiguous bit-range into a single set bit. Instead, shifting to the bottom with bsf / shr / inc saved 1 byte in 32-bit code, for a total of 6 bytes to turn a contiguous bit-range into a single set bit. An x86-64 version (no single-byte inc encoding) could save instructions at equal code-size by doing that, though, if BMI1 was available.

---

I was hoping to avoid doing the x & y == 0 test separately from combining the bits. e.g. by XORing them together and checking that a contiguous bit-range started at the bottom of one of the inputs:

    mov  eax, edx
    xor  eax, esi
    jz  .all_cancelled      ; exclude all-zeros from the 1-set-bit test

    blsi  ecx, esi          ; isolate lowest set of the shifting input
    add   eax, ecx          ; carry turns contiguous set bits into 1
                    ; BROKEN, need blsi(esi|edx)

But we can't just use the lowest set bit of the XOR result; some conflicting bits might have cancelled each other. e.g. x=0b110010 y=1 would give a false-positive when with x ^ (y<<1) = 0b110000 having all its set bits contiguous.

And it doesn't work to isolate the lowest set bit of the input you're shifting; once you shift it left past the lowest set bit of the other input, you need to be adding that isolated bit instead. e.g. the following input was mis-handled by my first version using xor and blsi ecx, esi, because it only dovetails with ESI's lowest bit shifted left past EDX's lowest set bit.

mov edx, 0b0110010
mov esi, 0b1001100

This way could still work with some kind of min(blsi(x), blsi(y)), or blsi(x|y), but doing that separately is not a win.

Answer 9

C (gcc), ^{105 \$\cdots\$ 63} 62 bytes

Saved a whopping 13 bytes thanks to the man himself Arnauld!!!
Saved a byte thanks to AZTECCO!!!

t;f(a,b){for(a<<=t=8;b&&t;b*=2)t=a|b,t/=t&-t,t=a&b|t&-~t;t=b;}

Try it online!

Returns \$!0\$ for true and \$0\$ otherwise.

Explanation

Shifts the first parameter, \$a\$, over \$8\$-bits so we can try all different shift positions by just shifting the second parameter, \$b\$. Loops over all shifts of \$b\$ checking to see if all bits are ever different from \$a\$ and \$b\$ forms one continuous block of \$1\$s when combined with \$a\$.

Answer 10

Retina 0.8.2, 82 81 bytes

$'¶$`;
(.+),(.*;.*)
$2,$1
+`;(.)(.*),(.)
-$1$3;$2,
-(0|(1))+
$#2
;|,

m`^0*1+0*$

Try it online! Link includes test cases. Explanation:

$'¶$`;

Create duplicates of the input with ;s inserted at every position.

(.+),(.*;.*)
$2,$1

Swap the two inputs if the ; lies within the second.

+`;(.)(.*),(.)
-$1$3;$2,

Try to dovetail the part between the ; and the , with the other input.

-(0|(1))+
$#2

Count the number of bits in each overlap.

;|,

Delete the separators.

m`^0*1+0*$

Check whether a dovetail produced a valid result. Edit: Saved 1 byte by returning any non-zero value for a valid result (value is number of possible dovetailings plus one if concatenating the inputs is a valid dovetailing).

Answer 11

Perl 5 -p, 68 bytes

s/\b0+|0+\b//g;s/(1*)(.*?)(1*) //;y/01/10/;$_=/^(0*$1)?$2(${3}0*)?$/

Try it online!

• s/\b0+|0+\b//g trims 0 from two blocks

• s/(1*)(.*?)(1*) // substitution to remove the first argument, and capture 3 groups :

  • $1: the left ones
  • $2: shortest sequence between
  • $3: the right ones (eventually)

• y/01/10/ transliteration of second argument remaining (bitwise not)

• /^(0*$1)?$2(${3}0*)?$/ the pattern second argument (inverted) must match

Answer 12

Factor, 149 139 bytes

: d ( a b -- ? ) [ 8 [ 0 suffix ] times 15 rotate ] bi@
all-rotations [ dupd [ + ] 2map [ 0 = ] trim all-equal? ] map
f [ or ] reduce nip ;

Try it online!

Gets the input as arrays of integers.

A naive solution - pads both arrays with 8 additional 0s, then adds each of the rotations of the second array to the first one, trims the leading/trailing zeros and check if the resulting arrays consist only of one number (1).

Answer 13

C (gcc), 94 82 71 70 bytes

Edit: -12 bytes by poring over Noodle9's similar C answer and rather shamelessly stealing all of the golfing tricks that I could use here... so please upvote that one, too!

More edits: ...thanks to various stolen tips & tricks from Arnauld, also -12 more bytes...

c;i;f(a,b){for(b<<=9,i=18;i-->1;i*=a&b||c&c++)a*=2,c/=(c=b|a)&-c;i=i;}

Try it online!

My first ever answer in 'C' (which embarassingly didn't work the first time: thanks to Arnauld for spotting the bug...).

Input is two 8-bit integers, outputs '-1' (truthy) if bits of input dovetail together perfectly, '0' (falsy) otherwise.

Works by first bit-shifting b by 9 bits, and then testing for successful dovetailing with a shifted by 1..18 bits (so, all-the-way to the right up to all-the-way to the left).
Tests dovetailing at each position by checking that a AND b is zero (so there are no 'clashing' bits), then taking A XOR B, chopping-off any trailing zeros, and testing whether x AND (x+1) is equal to zero (which is only true for 2^n-1 = strings of 1-bits).

Answer 14

Charcoal, 29 bytes

¬⬤α№⭆↨⁺×Ｘ³χ⍘η³×Ｘ³κ⍘賦³⮌⍘λ²01

Try it online! Works by dovetailing in base 3, which avoids issues other answers have when trying to XOR or add the values together. Explanation:

  α                             (Uppercase alphabet)
¬⬤                              No indices match
   №                            (Non-zero) Count of
                           01   Literal string `01` in
                   θ            First input
                  ⍘ ³           Converted as if base 3
              ×                 Multiplied by
                ³               Literal 3
               Ｘ                Raised to power
                 κ              Current index
      ⁺                         Plus
            η                   Second input
           ⍘ ³                  Converted as if base 3
       ×                        Multiplied by
         ³                      Literal `3`
        Ｘ                       Raised to power
          χ                     Predefined constant 10
     ↨                ³         Converted to base 3 as a list
    ⭆                           Map over digits
                         λ      Current digit
                        ⍘ ²     Converted to base 2 as a string
                       ⮌        Reversed
                                Implicitly print

Answer 15

Java 8, 86 83 82 bytes

(a,b)->{int i=18,t;for(a<<=8;--i>0;i=(a&b)>-(t&(t&-t)+t)?i:0,b*=2)t=a|b;return i;}

Inspired by halve the other answers. -3 bytes thanks to @AZTECCO.
-1 byte thanks to @ceilingcat.

Inputs as (32-bit) integers. Output as -1 for truthy and 0 for falsey.

Try it online.

Explanation:

(a,b)->{               // Method with two integer parameters and boolean return-type
  int i=18,            //  Index-integer, starting at 18
      t;               //  Temp-integer, uninitialized
  for(a<<=8;           //  Bit-shift the first input-integer `a` 8 bits to the left
      --i>0            //  Loop `i` in the range (18, 0):
      ;                //    After every iteration:
       i=(a&b)         //     Get `a` bitwise-AND `b`
         <             //     And check that it's smaller than:
          -(           //      The negative of:
            t          //      `t`
             &         //      Bitwise-AND with:
              (t&-t)   //       `t` bitwise-AND `-t`
                    +t)//       and add `t`
         ?             //     If this is truthy:
          0            //      Change `i` to 0 (which will also stop the loop)
         :             //     Else:
          i,           //      Keep `i` the same
       b*=2)           //     And multiply `b` by 2
    t=a|b;             //   Set `t` to `a` bitwise-OR `b`
  return i;}           //  Return `i` as result (where -1 means we've changed `i` to 0
                       //  manually as truthy output and 0 means the loop has fully
                       //  looped as falsey output)