Close(st) Binary Boxes

Question

Challenge:

Given a list of non-negative integers, determine by how much you should increase each item to create the closest binary box with the resulting integer-list.

What is a binary box?

A binary box is where the first and last rows consists of 1-bits; the first and last columns consist of 1-bits; and everything else (if applicable) consists of 0-bits. Some examples of binary boxes, with their corresponding integer-list below it:

                                             111
              1111                           101                           1111111
      111     1001        11      11111      101                           1000001
11    101     1001        11      10001      101         1111111           1000001
11    111     1111        11      11111      111         1111111   1   11  1111111

[3,3] [7,5,7] [15,9,9,15] [3,3,3] [31,17,31] [7,5,5,5,7] [255,255] [1] [3] [127,65,65,127]

Example I/O:

• If the input is [0,2], the output would be [3,1], because [3,3] is the closest binary box to reach by increasing numbers: [0+3,2+1].
• If the input is [3,4,1], the output would be [4,1,6], because [7,5,7] is the closest binary box to reach by increasing numbers: [3+4,4+1,1+6].
• If the input is [2], the output would be [1], because [3] is the closest binary box to reach by increasing numbers: [2+1].

Challenge rules:

• The goal is to find the closest binary box. If the input is [1,2,3] the output should be [2,1,0]; so [62,31,60] wouldn't be allowed as output, even though it does form a binary box as well.
• I/O can be taken in any reasonable format. Can be a list/array/stream of integers; read one by one from STDIN; etc. You are not allowed to take the input-integers as binary-strings.
• The input-integers are guaranteed to be non-negative; and the output-integers may not be negative.
• If the input is already a binary-box of itself, you can choose to output a corresponding list of 0s, or the result for the next binary-box in line. I.e. input [3,3,3] may result in both [0,0,0] or [4,2,4].

The first/last rows of the binary-boxes with binary 111...111 form the OEIS sequences A000042 (literal) and A000225: \$a(n)=2^n-1\$ (as base-10 integers).
The middle rows of the binary-boxes with binary 100...001 form the OEIS sequences A000533 (literal) and A083318: \$a(n)=2^n+1\$ (as base-10 integers).

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 with default I/O rules, 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:  [0,2]
Output: [3,1]

Input:  [3,4,1]
Output: [4,1,6]

Input:  [2]
Output: [1]

Input:  [3,3,3]
Output: [0,0,0] OR [4,2,4]

Input:  [1,27,40]
Output: [62,6,23]

Input:  [7,20,6,44,14]
Output: [120,45,59,21,113]

Input:  [7,20,6,33,14]
Output: [56,13,27,0,49]

Input:  [7,2,6,3,14]
Output: [8,7,3,6,1]

Input:  [1,0,1]
Output: [0,1,0]

Input:  [1,2,3]
Output: [2,1,0]

Input:  [0]
Output: [1]

Input:  [6,6,6]
Output: [9,3,9]

Answer 1

APL (Dyalog Extended), ^{47 46} 48 bytes

{x←0⋄⍵{x≡|x⊢←⍺-⍨⊥(1@1)∘⌽∘⍉⍣4⊢0×⍵:x⋄⍺∇⍵⍪0}⊤⍵+~×⍵}

Try it online!

A dfn which takes a vector as its right argument.

Outputs a list of 0's if the input is already a binary-box.

+2 bytes after a fix.(Thanks, Arnauld)

Explanation

{x←0⋄⍵{x≡|x⊢←⍺-⍨⊥(1@1)∘⌽∘⍉⍣4⊢0×⍵:x⋄⍺∇⍵⍪0}⊤⍵+~×⍵}
 x←0                                             set var x to 0(required for extended)
      {x≡|x⊢←⍺-⍨⊥(1@1)∘⌽∘⍉⍣4⊢0×⍵:x⋄⍺∇⍵⍪0}        call the following recursive function with
                                          ⍵+~×⍵  add !(signum(input)) to itself
                                                 (special casing for [0])
                                         ⊤       converted to binary matrix
     ⍵                                           and the input list as right arg
                                :                If:
                             0×⍵                 the matrix converted to zeroes
                 (1@1)∘⌽∘⍉⍣4⊢                    with 1s added on each side
                ⊥                                convert from binary
             ⍺-⍨                                 subtract from the input
          x⊢←                                    assign to x
       x≡|                                       if x matches its absolute value
                                 x               then return x
                                  ⋄⍺∇⍵⍪0         otherwise add a row of zeroes, and try again

Answer 2

05AB1E, 25 21 18 bytes

-4 bytes thanks to Kevin Cruijssen!

[NoD<Id¦¦s.ø~I-Wd#

Try it online! or Try all cases!

Commented:

[                    # infinite loop, for N=0,1, ...
 No                  # push 2**N
   D                 # duplicate this value
    <                # decrement
     Id              # push a list of 1's in the same length as the input
       ¦¦            # remove the first 2 elements
         s           # swap to 2**N-1
          .ø         # surround the list of 1's to get a new list of the same length as the input
                     #  => [2**N-1, 1, ..., 1, 2**N-1]
            ~        # bitwise OR with 2**N, this is now the binary grid of width N+1
                     #  => [2**n|2**N-1, 2**N|1, ..., 2**N|1, 2**N|2**N-1]
             I-      # subtract the input list element-wise from the binary grid
               W     # take the minimum without popping the list
                d    # if this is non-negative
                 #   # break the infinite loop and implicitly print the list

Answer 3

Python 3.8, 95 bytes

f=lambda s,n=1:(b:=[x-y for x,y in zip(([n|n-1]+[n|1]*(len(s)-2))*2,s)])*(min(b)>=0)or f(s,n*2)

Try it online!

Commented:

f=lambda s,n=1:           # f is a recursive function taking two arguments:
                          # a list of integers: s, and the current power of 2: n
                          # it tries all binary boxes with the correct number of rows
                          # until it finds one where all row numbers are >= the values in s

     (b:= ... )           # construct a list of differences between row numbers and s
   * (min(b)>=0)          # if there is no negative value in this list, return it
  or f(s,n*2)             # otherwise try the next power of 2
                 
[x-y for x,y in zip(...,s)])] # take the differences of each pair of row numbers and integers in s

 [n|n-1]                  # the first and last row are equal to n|n-1;
                          # example: n=8, n|n-1 = 8|7 = 0b1000|0b0111 = 0b1111 = 15
+[n|1]*(len(s)-2)         # the middle rows are n|1
                          # example: n=8, n|1 = 8|1 = 0b1000|0b0001 = 0b1001 = 9
 (...)*2                  # repeat this list twice to get the first row twice,
                          # zip will ignore all extra elements

Answer 4

JavaScript (ES6),  72  71 bytes

Outputs a list of 0's if the input is already a binary-box.

a=>(g=k=>/-/.test(b=a.map((v,i)=>(i/a[i+1]?k^k/2|1:k)-v))?g(k-~k):b)(1)

Try it online!

Commented

a =>                   // a[] = input array
(g = k =>              // g is a recursive function taking a bit mask k
                       // of the form (2 ** n) - 1
  /-/.test(            // test whether there is a minus side in the ...
    b = a.map(         //   ... array b[] defined as the result of this map()
      (v, i) =>        //   for each value v at position i in a[]:
      ( i / a[i + 1] ? //     if this is neither the first nor the last item
                       //     (i.e. i is not equal to 0 and a[i + 1] is defined):
          k ^ k / 2    //       use the vertical borders
          | 1          //       e.g. (0b111111 XOR (0b111111 >> 1)) OR 1 = 0b100001
        :              //     else:
          k            //       use the horizontal border (i.e. the full bit mask k)
      ) - v            //     subtract v
    )                  //   end of map()
  )                    // end of test()
  ?                    // if there's a minus sign:
    g(k - ~k)          //   try again with 2 * k + 1
  :                    // else:
    b                  //   success: return b[]
)(1)                   // initial call to g with k = 1

Answer 5

Charcoal, 39 37 bytes

≔¹ζ≔⁻¹θηＷ‹⌊η⁰«≦⊗ζ≔Ｅθ⁻⎇﹪λ⊖Ｌθ⊕ζ⊖⊗ζκη»Ｉη

Try it online! Link is to verbose version of code. Explanation: I tried directly calculating the correct box size, but there were too many edge cases.

≔¹ζ

Start with a box of width 1.

≔⁻¹θη

See whether this box can hold the input.

Ｗ‹⌊η⁰«

Repeat until a large enough box is found.

≦⊗ζ

Increase the size of the box.

≔Ｅθ⁻⎇﹪λ⊖Ｌθ⊕ζ⊖⊗ζκη

Calculate the box and subtract the original input.

»Ｉη

Output the final increments.

Answer 6

Python 3.8+, 91 bytes

f=lambda b,n=1:f(b,n*2)if min(u:=r_[(t:=2*n-1),b[2:]*0+n|1,t]-b)<0else u
from numpy import*

The parameter b must be a numpy array of integers.

Therefore, no try it online.

Recurse with n take values 1, 2, 4, 8,..., and construct the array

r_[
(t:=2*n-1),  #first line
b[2:]*0+n|1, #middle lines, all values are n|1, length=len(b[2:])
t            #last line, same as first line
]

being the binary boxes, then return the first one that is no smaller than b.

Answer 7

05AB1E, 25 31 25 26 bytes

+6 for bug fix for input [1,0,1]

-6 thanks to Kevin Cruijssen

+1 for bug fix for single-element lists

d¸∞εoIg<и¨>y>o<.ø}«.ΔI@P}α

Try it online! or Try all cases

Answer 8

C (gcc), 181 175 166 bytes

-6 bytes thanks to Kevin Cruijssen
-9 bytes thanks to ceilingcat

i,j,m;f(n,l)int*n;{for(i=m=0;i<l;i++)if(m<n[i])for(j=1;(j*=2)<(m=n[i]););for(i=0,m-2&&(j/=2);++i<l-1;)n[i]>j+1?j*=2:0;for(i=l;i--;)n[i]=j-n[i]+(!i|i==l-1|m<4?j-1:1);}

Try it online!