15
\$\begingroup\$

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.
  • 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]
\$\endgroup\$
8
  • \$\begingroup\$ By what metric is the distance between two boxes calculated? (when you say the closest binary box) \$\endgroup\$ – Command Master Feb 2 at 10:03
  • 2
    \$\begingroup\$ @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? \$\endgroup\$ – Kevin Cruijssen Feb 2 at 10:07
  • \$\begingroup\$ 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) \$\endgroup\$ – user202729 Feb 2 at 10:23
  • \$\begingroup\$ @user202729 Yes, that was indeed what I meant. I'll edit it a bit. How it's stored internally doesn't really matter. \$\endgroup\$ – Kevin Cruijssen Feb 2 at 10:25
  • 2
    \$\begingroup\$ @Razetime You can only increase, not decrease. \$\endgroup\$ – user202729 Feb 2 at 10:52
3
\$\begingroup\$

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
\$\endgroup\$
0
5
\$\begingroup\$

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
\$\endgroup\$
0
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 39 37 bytes

≔¹ζ≔⁻¹θηW‹⌊η⁰«≦⊗ζ≔Eθ⁻⎇﹪λ⊖Lθ⊕ζ⊖⊗ζκη»Iη

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.

W‹⌊η⁰«

Repeat until a large enough box is found.

≦⊗ζ

Increase the size of the box.

≔Eθ⁻⎇﹪λ⊖Lθ⊕ζ⊖⊗ζκη

Calculate the box and subtract the original input.

»Iη

Output the final increments.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ @KevinCruijssen Numpy is simply not installed on TIO. Do you know about one? \$\endgroup\$ – user202729 Feb 2 at 10:58
  • \$\begingroup\$ 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? :) \$\endgroup\$ – Kevin Cruijssen Feb 2 at 11:01
  • \$\begingroup\$ You can save a few bytes by starting with n=1 and doubling n on each recursive call. \$\endgroup\$ – ovs Feb 2 at 11:01
  • \$\begingroup\$ @ovs Good idea. \$\endgroup\$ – user202729 Feb 2 at 11:02
  • \$\begingroup\$ You could save 1 by writing out 2*n-1 for t. \$\endgroup\$ – Varun Vejalla Feb 3 at 1:46
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Feb 2 at 11:21
  • \$\begingroup\$ IgÅ1 can be d to get a list of 1s, so then you're back at your 25 byte-count. :) Try it online. \$\endgroup\$ – Kevin Cruijssen Feb 2 at 11:23
1
\$\begingroup\$

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!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Feb 4 at 7:56
  • \$\begingroup\$ @KevinCruijssen wow thank you for everything \$\endgroup\$ – Sheik Yerbouti Feb 4 at 8:09
  • \$\begingroup\$ @ceilingcat as always, thank you! :D \$\endgroup\$ – Sheik Yerbouti Feb 14 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.