The Binary Fences

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!


->\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
   L.fmt('%b','')  # Join binary representations
   ~~              # Regex match
   m:ov/(1+)<{"0+$0"x n-1}>/  # Find overlapping matches

Husk, 33 bytes


Try it online!

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


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

ΛΛ=⁰Fzż+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
  =⁰         are equal to first input.

JavaScript (ES6), 187 184 177 173 bytes

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


Try it online!


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

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


                      (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:


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)