Dovetail two blocks of bits

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 so all usual golfing rules apply, and the shortest code (in bytes) wins.

Sandbox

• Can we take the inputs as 8-bit numbers from 0 to 255?
– xnor
Sep 16 '20 at 9:48
• @Arnauld The test cases seem to say we don't have to handle any all-zero inputs.
– xnor
Sep 16 '20 at 11:00
• @xnor Ah ... the famous 'put some part of the spec in the test cases' joke. :-) Thank you, I totally missed that. Sep 16 '20 at 11:03
• @Arnauld true ahahah! Actually it was specified initially, but I missed it during the many reviews on sandbox Sep 16 '20 at 11:59
• That's what I thought, and agreed it's reasonable, but I wondered if you might have just switched conventions because everything else was listed with that order, too, like "false"/"true" which would be surprising because it's strings as well as inverted from our normal conventions of what those words mean. Sep 16 '20 at 21:06

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

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

• Did you mean ...<1>...?
– xnor
Sep 17 '20 at 0:47
• @xnor I did not. In many cases, there are trailing zeroes in the binary representation. The 2>... part captures both with and without trailing zeroes. For the ...<2 part, it does not matter. Any overlapping bits happen at the 8th bit or further left. Sep 17 '20 at 6:58
• Oh, I see, that's neat. Would it also work to count '01' and check that this is 0 using 1>, for the same byte count? If so, there's probably something shorter with '01'in.
– xnor
Sep 17 '20 at 7:27
• @xnor Good point! That saves some bytes right away. Sep 17 '20 at 8:46

Python 2, 7859 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!

• Out of curiosity: where does the q come from in your code? Sep 17 '20 at 9:33
• @KevinCruijssen Because chained comparisons are lazily evaluated, q throws a NameError if all comparisons before are True.
– ovs
Sep 17 '20 at 9:37
• Ah, I hadn't noticed you throw an error as truthy inputs and not as falsey. That makes sense. And I didn't knew Python comparisons are lazy evaluated like that. If I'd try to use a non-existing variable in Java I would already get an error during compilation way before the program is actually executed. TIL. :) Oh, and nice approach! Sep 17 '20 at 9:41
• catonmat.net/low-level-bit-hacks is a nice explanation of multiple bithacks like d & -d to isolate the lowest set bit, with 8-bit examples. (Like the x86 BMI2 instruction blsi.) Sep 18 '20 at 19:07

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!

• Bah! I don't believe it! After all your help, you had this up your sleeve all along...! Sep 16 '20 at 15:03
• @Dominic Best man wins - and he always has a whopper up his sleeve! :D Sep 16 '20 at 15:11
• I'll do. Btw glad to see a C answer of you Sir! Sep 16 '20 at 21:24

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
;          -     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?

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

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

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)?
• Nice! I think C answers and some others can benefit how you used output rules Sep 16 '20 at 21:01

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

• ...I've been frantically fixing my buggy first 'C' attempt, and when I finally post the fix, I see that you've got almost exactly the same strategy... Now I need to learn how you saved those 3 bytes... Sep 16 '20 at 14:14
• @DominicvanEssen Yeah, basically shifting and making sure the bits are all different but form a block of 1s when combined. Started dead simple to make sure it worked and then started doing tricks - best way with C. One nice trick is n & (n - 1) is zero iff $n$ is a power of $2$. Sep 16 '20 at 14:19
• t/=t&-t can be used instead of t>>=__builtin_ctz(t) Sep 16 '20 at 14:32
• @Arnauld Now that's a nice trick - thanks! :D Sep 16 '20 at 14:36
• @AZTECCO Thanks for reminding me, noticed that but go so into into it forgot. Great challenge - thanks muchly! :D Sep 16 '20 at 21:13

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

• Yes you can drop it! Sep 16 '20 at 21:10

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

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

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.

C (gcc), 948271 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).

• I also have an 81 byte answer, but it leaves-behind disrupted global variables & so cannot be run multiple times sequentially. I assume that this is frowned-upon (or outright banned): perhaps someone can confirm/refute this...? Sep 16 '20 at 12:16
• Regarding your question: this is indeed banned Sep 16 '20 at 12:37
• Rats! How did I miss that... Sep 16 '20 at 13:13
• ...fixed at last Sep 16 '20 at 14:53
• The c/=c&-c trick works fine with Noodle9's answer, but in your case it may result in a division by zero and a floating point exception. (Example: a=9 / b=9.) Sep 16 '20 at 15:10

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
• What's the difference between true and false outputs? They both appear to be - when I run the linked program
– Jo King
Sep 16 '20 at 12:44
• @JoKing There's a byte missing. I'll add it shortly.
– Neil
Sep 16 '20 at 15:28
• @JoKing Or better still, I can golf it away again...
– Neil
Sep 16 '20 at 15:29

Java 8, 8683 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)
• Why don't you use --i>0; and return i? Sep 17 '20 at 15:18
• @AZTECCO The TIO you've linked all returned 0, but you're indeed correct I can save 3 bytes with -->0. Thanks! Sep 17 '20 at 16:44
• Previous link was wrong sorry, this may work.. Not sure though. Sep 17 '20 at 16:57