# Close(st) Binary Boxes

## 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 , 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.

## 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]

• By what metric is the distance between two boxes calculated? (when you say the closest binary box) – Command Master Feb 2 at 10:03
• @CommandMaster Not sure if it's relevant? I guess you mean to ask whether it's by base-10 integers or the binary-bits? The idea is by base-10 integers, but since we're only allowing increasing the numbers (or keeping them the same by increasing with 0) and never decreasing, it wouldn't matter whether the metric is by base-10 integers or the binary itself, unless I'm missing something? Could you give an example where your question would give different results based on the metric used? Or am I misunderstanding your question completely? – Kevin Cruijssen Feb 2 at 10:07
• By "You are not allowed to take the input-integers as binary", did you mean "binary string representation of the number"? (normally numbers are stored internally in binary format anyway) – user202729 Feb 2 at 10:23
• @user202729 Yes, that was indeed what I meant. I'll edit it a bit. How it's stored internally doesn't really matter. – Kevin Cruijssen Feb 2 at 10:25
• @Razetime You can only increase, not decrease. – user202729 Feb 2 at 10:52

# 05AB1E, 2521 18 bytes

-4 bytes thanks to Kevin Cruijssen!

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


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


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


# 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


# 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


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

≔¹ζ


≔⁻¹θη


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.

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

• @KevinCruijssen Numpy is simply not installed on TIO. Do you know about one? – user202729 Feb 2 at 10:58
• Ah ok. And no, I don't know too many online compilers. Only TIO and ideone for languages in general. In that case, could you perhaps add a screenshot as verification? :) – Kevin Cruijssen Feb 2 at 11:01
• You can save a few bytes by starting with n=1 and doubling n on each recursive call. – ovs Feb 2 at 11:01
• @ovs Good idea. – user202729 Feb 2 at 11:02
• You could save 1 by writing out 2*n-1 for t. – Varun Vejalla Feb 3 at 1:46

# 05AB1E, 253125 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}α

• There is a surround builtin, so the ©ª®š can be .ø for -2. Also, the I- can be α for an additional -1. And in your new 31-byte version you can remove the leading I. – Kevin Cruijssen Feb 2 at 11:21
• IgÅ1 can be d to get a list of 1s, so then you're back at your 25 byte-count. :) Try it online. – Kevin Cruijssen Feb 2 at 11:23

# C (gcc), 181175 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!

• Nice answer! And taking the length as argument is allowed by default I think, so that's no problem. As for some golfs: <=(m=n[i])-1; can be <(m=n[i]); for -3; both || can be | for -2; and j*2-1-n[i] can be j*2+~n[i] for -1. – Kevin Cruijssen Feb 4 at 7:56
• @KevinCruijssen wow thank you for everything – Sheik Yerbouti Feb 4 at 8:09
• @ceilingcat as always, thank you! :D – Sheik Yerbouti Feb 14 at 12:08