The Binary Fences

Question

Input:

• An integer n in the range 2 <= n <= 10
• A list of positive integers

Output:

Convert the integers to their binary representation (without any leading zeroes), and join them all together.
Then determine all binary substrings that form a 'binary fence' using n amount of fence posts. The spaces (zeros) between each fence post are irrelevant (at least 1), but the fence posts themselves should all be of equal width.
Here the regexes the binary substrings should match for each n:

n Regex to match to be a 'binary fence' Some examples
2 ^(1+)0+1円$ 101; 1100011; 1110111;
3 ^(1+)0+10円+1円$ 10101; 1000101; 110011011;
4 ^(1+)0+10円+10円+1円$ 1010101; 110110011011; 11110111100001111001111;
etc. etc. You get the point

Looking at the n=4 examples:

1010101
^ ^ ^ ^ All fence posts have a width of one 1
 ^ ^ ^ with one or more 0s in between them
110110011011
^^ ^^ ^^ ^^ All fence posts have a width of two 1s
 ^ ^^ ^ with one or more 0s in between them
11110111100001111001111
^^^^ ^^^^ ^^^^ ^^^^ All fence posts have a width of four 1s
 ^ ^^^^ ^^ with one or more 0s in between them

We then output the numbers that use binary digits of the matches 'binary fences'.

Example:

Input: n=4, L=[85,77,71]

The binary representation of these integer joined together is:
1010101 1001101 1000111 (NOTE: The spaces are only added as clarification for the example).

Since n=4, we look for substrings matching the regex (1+)0+10円+10円+1円, in which case we can find two:
1010101 (at position (1010101) 1001101 1000111); and 11001101100011 (at position 101010(1 1001101 100011)1)

The first binary fence only uses binary digits from 85, and the second binary fence uses binary digits from all three integers. So the output in this case would be:
[[85],[85,77,71]]

Challenge rules:

• Although it's also mentioned in the example above, the last sentence is an important one: We output the numbers for which binary digits are used in the 'binary fence' substring.
• I/O is flexible. Input can be a list/array/stream of integers, space/comma/newline delimited string, etc. Output can be a 2D integer-list, a single delimited string, a string-list, new-line printed to STDOUT, etc. All up to you, but please state what you've used in your answer.
• Output order of the list itself is irrelevant, but the output of each inner list is of course in the same order as the input-list. So with the example above, [[85,77,71],[85]] is a valid output as well, but [[85],[77,85,71]] is not.
• As you may have already noticed from the example (the 85), binary-digits can be used multiple times.
• The regexes should match the substring entirely. So 110101 or 010101 aren't ever a valid 'binary fences' (10101 is however, iff n=3).
• Items in the output-list aren't unique, only the binary-positions of the 'binary fences' are unique. If multiple 'binary fences' can be created with the same integer(s), we add them multiple times to the output-list.
  For example: n=2, L=[109, 45] (binary 1101101 101101) can form these 'binary fence' substrings: 11011 (at position (11011)01 101101); 101 (at position 1(101)101 101101); 11011 (at position 110(1101 1)01101); 101 (at position 1101(101) 101101); 11011 (at position 110110(1 1011)01); 101 (at position 1101101 (101)101); 101 (at position 1101101 101(101)), so the output would be [[109],[109],[109,45],[109],[109,45],[45],[45]].
  Another example: n=2, L=[8127] (binary 1111110111111) can form these 'binary fence' substrings: 1111110111111 (at position (1111110111111)); 11111011111 (at position 1(11111011111)1); 111101111 (at position 11(111101111)11); 1110111 (at position 111(1110111)111); 11011 (at position 1111(11011)1111); 101 (at position 11111(101)11111), so the output would be [[8127],[8127],[8127],[8127],[8127],[8127]].
• If no valid output is possible, you can return an empty list or some other kind of falsey output (null, false, throws an error, etc. Again, your call).

General rules:

• This is code-golf, so shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (i.e. TIO).
• Also, adding an explanation for your answer is highly recommended.

Test cases:

Input: Output
 (the binary below the output are added as clarification,
 where the parenthesis indicate the substring matching the regex):
4, [85,77,71] [[85],[85,77,71]]
 (1010101) 1001101 1000111; 101010(1 1001101 100011)1
2, [109,45] [[109],[109],[109,45],[109],[109,45],[45],[45]]
 (11011)01 101101; 1(101)101 101101; 110(1101 1)01101; 1101(101) 101101; 110110(1 1011)01; 1101101 (101)101; 1101101 101(101)
3, [990,1,3,3023,15,21] [[990,1,3,3023],[990,1,3,3023],[1,3,3023],[21]]
 (1111011110 1 11 1)01111001111 1111 10101; 11110(11110 1 11 101111)001111 1111 10101; 1111011110 (1 11 101111001111) 1111 10101; 1111011110 1 11 101111001111 1111 (10101)
2, [1,2,3,4,5,6,7,8,9,10] [[1,2,3],[2,3],[4,5],[5],[5,6,7],[6,7],[6,7],[8,9],[9],[10]]
 (1 10 11) 100 101 110 111 1000 1001 1010; 1 (10 1)1 100 101 110 111 1000 1001 1010; 1 10 11 (100 1)01 110 111 1000 1001 1010; 1 10 11 100 (101) 110 111 1000 1001 1010; 1 10 11 100 10(1 110 111) 1000 1001 1010; 1 10 11 100 101 (110 11)1 1000 1001 1010; 1 10 11 100 101 1(10 1)11 1000 1001 1010; 1 10 11 100 101 110 111 (1000 1)001 1010; 1 10 11 100 101 110 111 1000 (1001) 1010; 1 10 11 100 101 110 111 1000 1001 (101)0
3, [1,2,3,4,5,6,7,8,9,10] [[4,5],[8,9]]
 1 10 11 (100 101 )110 111 1000 1001 1010; 1 10 11 100 101 110 111 (1000 1001) 1010
10, [1,2,3,4,5,6,7,8,9,10] []
 No binary fences are possible for this input
6, [445873,2075] [[445873,2075],[445873,2075],[445873,2075]]
 (1101100110110110001 1)00000011011; 110(1100110110110001 100000011)011; 1101100(110110110001 100000011011)
2, [8127] [[8127],[8127],[8127],[8127],[8127],[8127]]
 (1111110111111); 1(11111011111)1; 11(111101111)11; 111(1110111)111; 1111(11011)1111; 11111(101)11111
2, [10,10] [[10],[10,10],[10]]
 (101)0 1010; 10(10 1)010; 1010 (101)0
4, [10,10,10] [[10,10],[10,10,10],[10,10]]
 (1010 101)0 1010; 10(10 1010 1)010; 1010 (1010 101)0

• Quintec: Ah, shucks, you posted this just as class started!
• TFeld: Isn't [1,2,3] valid for testcase 4? I see the fence (1 10 11)
• Arnauld: Ok, I think I got it right this time. I didn't read the last sentence of the example carefully enough. (Since it is a very important one, maybe it should not be mentioned within the example.)
• Kevin Cruijssen: @Arnauld I've added the last sentence of the example as first rule now. I hope that makes it more apparent.
• nwellnhof: I'd suggest to add a test case where the same integer appears multiple times in the list, for example 2, [10, 10] which should result in [[10],[10,10],[10]] if I understand the challenge correctl.y

Answer 1

Perl 6, (削除) 114 (削除ここまで) (削除) 112 (削除ここまで) (削除) 110 (削除ここまで) (削除) 107 (削除ここまで) (削除) 106 (削除ここまで) 104 bytes

->\n,\L{L[map {[...] flat(^L Zxx(L>>.msb X+1))[.from,.to-1]},L.fmt('%b','')~~m:ov/(1+)<{"0+0ドル"x n-1}>/]}

Try it online!

Explanation

->\n,\L{ # Anonymous block taking arguments n and L
 L[ # Return elements of L
 map { # Map matches to ranges
 [...] # Create range from start/end pair
 # Map indices into binary string to indices into L
 flat( # Flatten
 ^L # indices into L
 Zxx # repeated times
 (L>>.msb X+1) # length of each binary representation
 )
 # Lookup start/end pair in map above
 [.from,.to-1]
 },
 L.fmt('%b','') # Join binary representations
 ~~ # Regex match
 m:ov/(1+)<{"0+0ドル"x n-1}>/ # Find overlapping matches
 ]
}

Answer 2

Husk, 33 bytes

ṠṘmȯF-mȯ#öΛΛ=0Fzż+C2gQṁḋmëhohttIQ

Try it online!

Passes all test cases. This was a difficult challenge and my solution feels somewhat convoluted.

Explanation

The program loops through the slices of the input, and repeats each as many times as it contains a match of the regex. We want to count only those matches that overlap the binary expansion of every number in the slice. This seems difficult, but it's easier to count those matches that do not use the first number: just remove that number and count all matches. To get the good matches, we thus count all matches, then subtract the number of matches that don't use the first number, and those that don't use last number. The matches that use neither are counted twice, so we must add them back to get the correct result.

Counting the number of matches in a slice is a matter of concatenating the binary expansions and looping over the slices of the result. Since Husk has no support for regexes, we use list manipulation to recognize a match. The function g splits a slice to groups of equal adjacent elements. Then we must verify the following:

1. The first group is a 1-group.
2. The number of groups is odd.
3. The number of 1-groups is equal to the first input n.
4. The 1-groups have equal lengths.

First we cut the groups into pairs. If 1 and 2 hold, then the first group of each pair is a 1-group and the last pair is a singleton. Then we reduce this list of pairs by zipping them with componentwise addition. This means that the 1-groups and 0-groups are added separately. The addition preserves overflowing elements, so adding [1,1,1] and [1,1] gives [2,2,1]. Zipping does not, so if the last pair is a singleton, the componentwise sum of the 0-groups vanishes from the result. Finally, we check that all numbers in the result are equal to n.

ṠṘm(...)Q First input is explicit, say 3, second is implicit.
 Q List of slices.
 m(...) Map this function (which counts good matches) over the slices
ṠṘ and replicate each by the corresponding number.
F-m(...)mëhohttI Count good matches. Argument is a slice, say [6,2,5].
 ë Define a list of 4 functions:
 h remove first element,
 oht remove first and last element,
 t remove last element,
 I identity.
 m Apply each: [[2,5],[2],[6,2],[6,2,5]]
 m(...) Map function (which counts all matches): [0,0,1,2]
F- Reduce by subtraction: 1
 In Husk, - has reversed arguments, so this computes
 M(x) - (M(tx) - (M(htx) - M(hx)))
 where M means number of matches.
#(...)Qṁḋ Count all matches. Argument is a slice.
 ṁ Map and concatenate
 ḋ binary expansions.
 Q List of slices.
#(...) Count number of truthy results of function (which recognizes a match).
ΛΛ=0Fzż+C2g Recognize a match. Argument is list of bits, say [1,1,0,1,1,0,0,0,1,1].
 g Group elements: [[1,1],[0],[1,1],[0,0,0],[1,1]]
 C2 Cut into pairs: [[[1,1],[0]],[[1,1],[0,0,0]],[[1,1]]]
 F Reduce by
 z zip (discarding extraneous elements) with
 ż zip (preserving extraneous elements) with
 + addition: [[3,3]]
Λ For all lists
 Λ all elements
 =0 are equal to first input.

Answer 3

JavaScript (ES6), (削除) 187 (削除ここまで) (削除) 184 (削除ここまで) (削除) 177 (削除ここまで) 173 bytes

Takes input as (n)(list). Returns an array of arrays.

n=>a=>(g=p=>(m=s.slice(p).match(`(1+)(0+\1円){${n-1}}`))?[a.filter((_,i)=>-~b[i-1]<p+m[0].length&b[i]>=p,p-=~m.index),...g(p)]:[])(s=[],b=a.map(n=>(s+=n.toString(2)).length))

Try it online!

How?

We first compute the binary string \$s\$ and a list \$b\$ that describes the bounds of each number in \$s\$.

s = [], b = a.map(n => (s += n.toString(2)).length)

Example:

 (0) 7 13
 v v v
a = [109, 45] --> s = "1101101101101" --> b = [7, 13]
 \_____/\____/
 109 45

We use the following template to generate a regular expression matching binary fences:

`(1+)(0+\1円){${n-1}}`

This regular expression is applied to \$s\$, starting from a position \$p\$.

m = s.slice(p).match(`(1+)(0+\1円){${n-1}}`)

We start with \$p=0\$ and update it at each iteration according to the position of the previous match.

Whenever a match \$m\$ is found in \$s\$: for each \$i\$-th number in the input array, we test whether the interval made of its bounds (stored in \$b\$) overlaps the interval made of the starting and ending positions of \$m\$ in \$s\$.

a.filter((_, i) => -~b[i - 1] < p + m[0].length & b[i] >= p, p -= ~m.index)

Answer 4

Python 2, (削除) 271 (削除ここまで) (削除) 246 (削除ここまで) (削除) 223 (削除ここまで) (削除) 214 (削除ここまで) (削除) 208 (削除ここまで) (削除) 202 (削除ここまで) (削除) 200 (削除ここまで) 195 bytes

lambda n,l,R=range,L=len:sum([next(([l[i:j+1]]for j in R(i,L(l))if re.match('(1+)'+r'(0+1円)'*~-n,('{:b}'*(1+j-i)).format(*l[i:])[o:])),[])for i in R(L(l))for o in R(L(bin(l[i]))-2)],[])
import re

Try it online!

Answer 5

Python 2, 182 bytes

lambda n,L,b='{:b}'.format:[zip(*set([t
for t in enumerate(L)for _ in b(t[1])][slice(*m.span(1))]))[1]for
m in re.finditer('(?=((1+)'+r'[0]+2円'*~-n+'))',''.join(map(b,L)))]
import re

Try it online!

• Kevin Cruijssen: This seems to give an error for any n input larger than 2. Also, even with n=2 it gives an incorrect result for the test case n=2, L=[10,10]. The other test cases with n=2 work, though.
• lynn: Oh, I see why it fails for [10,10]; let me see how costly it is to fix that...
• lynn: @KevinCruijssen I fixed both issues (at the cost of 22 bytes, oh well!)

Answer 6

05AB1E, (削除) 38 (削除ここまで) (削除) 36 (削除ここまで) 35 bytes

Œεy ̈D¦y¦)bJεŒεγ0KDËsgIQyнyθP}}OÆFy,

Inspired by @Zgarb's Husk answer.

Output the lists newline-delimited.

Try it online or verify all test cases.

Explanation:

Π# Get the sublists of the (implicit) input-list
 ε # Loop `y` over each sublist:
 # (implicitly push `y`)
 y ̈ # Push `y` with the last item removed
 D¦ # Push `y` with the first and last items removed
 y¦ # Push `y` with the first item removed
 ) # Wrap all four into a list
 b # Get the binary-string of each integer
 J # Join each inner list together
 ε # Map each converted binary-string to:
 Π# Get all substrings of the binary-string
 ε # Map each binary substring to:
 γ # Split it into chunks of equal adjacent digits
 0K # Remove all chunks consisting of 0s
 DË # Check if all chunks consisting of 1s are the same
 sgIQ # Check if the amount of chunks of 1s is equal to the second input-integer
 yн # Check if the substring starts with a 1
 yθ # Check if the substring end with a 1
 P # Check if all four checks above are truthy for this substring
 # (1 if truthy; 0 if falsey)
 }} # Close both maps
 O # Take the sum of each inner list
 Æ # Reduce the list of sums by subtraction
 F # Loop that many times:
 y, # And print the current sublist `y` with a trailing newline