15
\$\begingroup\$

We all know how binary conversion works: the sequence of bits

$$ b_1, b_2, ..., b_{n-1}, b_n $$

encodes the number

$$ b_1 \times 2^{n-1} + b_2 \times 2^{n-2} + ... + b_{n-1} \times 2^1 + b_n \times 2^0 $$

This gives an unambiguous representation when we limit all bits \$ b_i \$ to be only 0 or 1.

...but what if we allow digits outside that range? How about also allowing the "bits" 2 and 3?

The normal representation of 18 in binary would be 10010, but since 10 is \$ 1 \times 2^1 + 0 \times 2^0 = 1 \times 2 + 0 = 2 \$, we could also write it as 02 (\$ 0 \times 2^1 + 2 \times 2^0 = 2 \$), we could also write \$ 18 \$, in an "overflowed" binary, as 10002.

But we can also see that 10000 (\$ 16 \$) could be 02000, so \$ 18 \$ could be 02002. We can repeat this process and get a whole list of possible "overflowed binary" encodings for our number \$ 18 \$ (which includes \$ 18 \$'s normal binary encoding):

10010
10002
02010
02002
01210
01202
01130
01122
00330
00322

Task

Given a number \$ n \$ and a maximum digit value \$ c \$, output all possible lists of digits between \$ 0 \$ and \$ c \$ (inclusive) which encode \$ n \$ in overflowed binary.

Rules

  • You may assume \$ n \$ and \$ c \$ will both be integers with \$ n \ge 0 \$ and \$ c \ge 1 \$
  • You may output lists with any (finite) number of leading zeroes, but you not output duplicate lists that differ only by leading zeroes; for example, you may not output both [0, 1, 3] and [1, 3]
  • You must output in a way that clearly separates digits, even when they are greater than \$ 9 \$. For example, [13, 2] must be distinguishable from [1, 3, 2]
  • You may use any reasonable I/O method
  • Standard loopholes are forbidden
  • This is , so the shortest code in bytes wins

Test cases

These test outputs are padded with leading zeroes such that all output lists are the same length.

n   c   output
--------------
0   1   [[0]]
0   5   [[0]]
1   1   [[1]]
4   7   [[0,0,4],[0,1,2],[0,2,0],[1,0,0]]
18  3   [[0,0,3,2,2],[0,0,3,3,0],[0,1,1,2,2],[0,1,1,3,0],[0,1,2,0,2],[0,1,2,1,0],[0,2,0,0,2],[0,2,0,1,0],[1,0,0,0,2],[1,0,0,1,0]]
12  12  [[0,0,0,12],[0,0,1,10],[0,0,2,8],[0,0,3,6],[0,0,4,4],[0,0,5,2],[0,0,6,0],[0,1,0,8],[0,1,1,6],[0,1,2,4],[0,1,3,2],[0,1,4,0],[0,2,0,4],[0,2,1,2],[0,2,2,0],[0,3,0,0],[1,0,0,4],[1,0,1,2],[1,0,2,0],[1,1,0,0]]
14  10  [[0,0,2,10],[0,0,3,8],[0,0,4,6],[0,0,5,4],[0,0,6,2],[0,0,7,0],[0,1,0,10],[0,1,1,8],[0,1,2,6],[0,1,3,4],[0,1,4,2],[0,1,5,0],[0,2,0,6],[0,2,1,4],[0,2,2,2],[0,2,3,0],[0,3,0,2],[0,3,1,0],[1,0,0,6],[1,0,1,4],[1,0,2,2],[1,0,3,0],[1,1,0,2],[1,1,1,0]]
429 3   [[0,1,2,3,2,3,3,3,3],[0,1,2,3,3,1,3,3,3],[0,1,2,3,3,2,1,3,3],[0,1,2,3,3,2,2,1,3],[0,1,2,3,3,2,2,2,1],[0,1,2,3,3,2,3,0,1],[0,1,2,3,3,3,0,1,3],[0,1,2,3,3,3,0,2,1],[0,1,2,3,3,3,1,0,1],[0,1,3,1,2,3,3,3,3],[0,1,3,1,3,1,3,3,3],[0,1,3,1,3,2,1,3,3],[0,1,3,1,3,2,2,1,3],[0,1,3,1,3,2,2,2,1],[0,1,3,1,3,2,3,0,1],[0,1,3,1,3,3,0,1,3],[0,1,3,1,3,3,0,2,1],[0,1,3,1,3,3,1,0,1],[0,1,3,2,0,3,3,3,3],[0,1,3,2,1,1,3,3,3],[0,1,3,2,1,2,1,3,3],[0,1,3,2,1,2,2,1,3],[0,1,3,2,1,2,2,2,1],[0,1,3,2,1,2,3,0,1],[0,1,3,2,1,3,0,1,3],[0,1,3,2,1,3,0,2,1],[0,1,3,2,1,3,1,0,1],[0,1,3,2,2,0,1,3,3],[0,1,3,2,2,0,2,1,3],[0,1,3,2,2,0,2,2,1],[0,1,3,2,2,0,3,0,1],[0,1,3,2,2,1,0,1,3],[0,1,3,2,2,1,0,2,1],[0,1,3,2,2,1,1,0,1],[0,1,3,3,0,0,1,3,3],[0,1,3,3,0,0,2,1,3],[0,1,3,3,0,0,2,2,1],[0,1,3,3,0,0,3,0,1],[0,1,3,3,0,1,0,1,3],[0,1,3,3,0,1,0,2,1],[0,1,3,3,0,1,1,0,1],[0,2,0,3,2,3,3,3,3],[0,2,0,3,3,1,3,3,3],[0,2,0,3,3,2,1,3,3],[0,2,0,3,3,2,2,1,3],[0,2,0,3,3,2,2,2,1],[0,2,0,3,3,2,3,0,1],[0,2,0,3,3,3,0,1,3],[0,2,0,3,3,3,0,2,1],[0,2,0,3,3,3,1,0,1],[0,2,1,1,2,3,3,3,3],[0,2,1,1,3,1,3,3,3],[0,2,1,1,3,2,1,3,3],[0,2,1,1,3,2,2,1,3],[0,2,1,1,3,2,2,2,1],[0,2,1,1,3,2,3,0,1],[0,2,1,1,3,3,0,1,3],[0,2,1,1,3,3,0,2,1],[0,2,1,1,3,3,1,0,1],[0,2,1,2,0,3,3,3,3],[0,2,1,2,1,1,3,3,3],[0,2,1,2,1,2,1,3,3],[0,2,1,2,1,2,2,1,3],[0,2,1,2,1,2,2,2,1],[0,2,1,2,1,2,3,0,1],[0,2,1,2,1,3,0,1,3],[0,2,1,2,1,3,0,2,1],[0,2,1,2,1,3,1,0,1],[0,2,1,2,2,0,1,3,3],[0,2,1,2,2,0,2,1,3],[0,2,1,2,2,0,2,2,1],[0,2,1,2,2,0,3,0,1],[0,2,1,2,2,1,0,1,3],[0,2,1,2,2,1,0,2,1],[0,2,1,2,2,1,1,0,1],[0,2,1,3,0,0,1,3,3],[0,2,1,3,0,0,2,1,3],[0,2,1,3,0,0,2,2,1],[0,2,1,3,0,0,3,0,1],[0,2,1,3,0,1,0,1,3],[0,2,1,3,0,1,0,2,1],[0,2,1,3,0,1,1,0,1],[0,2,2,0,0,3,3,3,3],[0,2,2,0,1,1,3,3,3],[0,2,2,0,1,2,1,3,3],[0,2,2,0,1,2,2,1,3],[0,2,2,0,1,2,2,2,1],[0,2,2,0,1,2,3,0,1],[0,2,2,0,1,3,0,1,3],[0,2,2,0,1,3,0,2,1],[0,2,2,0,1,3,1,0,1],[0,2,2,0,2,0,1,3,3],[0,2,2,0,2,0,2,1,3],[0,2,2,0,2,0,2,2,1],[0,2,2,0,2,0,3,0,1],[0,2,2,0,2,1,0,1,3],[0,2,2,0,2,1,0,2,1],[0,2,2,0,2,1,1,0,1],[0,2,2,1,0,0,1,3,3],[0,2,2,1,0,0,2,1,3],[0,2,2,1,0,0,2,2,1],[0,2,2,1,0,0,3,0,1],[0,2,2,1,0,1,0,1,3],[0,2,2,1,0,1,0,2,1],[0,2,2,1,0,1,1,0,1],[0,3,0,0,0,3,3,3,3],[0,3,0,0,1,1,3,3,3],[0,3,0,0,1,2,1,3,3],[0,3,0,0,1,2,2,1,3],[0,3,0,0,1,2,2,2,1],[0,3,0,0,1,2,3,0,1],[0,3,0,0,1,3,0,1,3],[0,3,0,0,1,3,0,2,1],[0,3,0,0,1,3,1,0,1],[0,3,0,0,2,0,1,3,3],[0,3,0,0,2,0,2,1,3],[0,3,0,0,2,0,2,2,1],[0,3,0,0,2,0,3,0,1],[0,3,0,0,2,1,0,1,3],[0,3,0,0,2,1,0,2,1],[0,3,0,0,2,1,1,0,1],[0,3,0,1,0,0,1,3,3],[0,3,0,1,0,0,2,1,3],[0,3,0,1,0,0,2,2,1],[0,3,0,1,0,0,3,0,1],[0,3,0,1,0,1,0,1,3],[0,3,0,1,0,1,0,2,1],[0,3,0,1,0,1,1,0,1],[1,0,0,3,2,3,3,3,3],[1,0,0,3,3,1,3,3,3],[1,0,0,3,3,2,1,3,3],[1,0,0,3,3,2,2,1,3],[1,0,0,3,3,2,2,2,1],[1,0,0,3,3,2,3,0,1],[1,0,0,3,3,3,0,1,3],[1,0,0,3,3,3,0,2,1],[1,0,0,3,3,3,1,0,1],[1,0,1,1,2,3,3,3,3],[1,0,1,1,3,1,3,3,3],[1,0,1,1,3,2,1,3,3],[1,0,1,1,3,2,2,1,3],[1,0,1,1,3,2,2,2,1],[1,0,1,1,3,2,3,0,1],[1,0,1,1,3,3,0,1,3],[1,0,1,1,3,3,0,2,1],[1,0,1,1,3,3,1,0,1],[1,0,1,2,0,3,3,3,3],[1,0,1,2,1,1,3,3,3],[1,0,1,2,1,2,1,3,3],[1,0,1,2,1,2,2,1,3],[1,0,1,2,1,2,2,2,1],[1,0,1,2,1,2,3,0,1],[1,0,1,2,1,3,0,1,3],[1,0,1,2,1,3,0,2,1],[1,0,1,2,1,3,1,0,1],[1,0,1,2,2,0,1,3,3],[1,0,1,2,2,0,2,1,3],[1,0,1,2,2,0,2,2,1],[1,0,1,2,2,0,3,0,1],[1,0,1,2,2,1,0,1,3],[1,0,1,2,2,1,0,2,1],[1,0,1,2,2,1,1,0,1],[1,0,1,3,0,0,1,3,3],[1,0,1,3,0,0,2,1,3],[1,0,1,3,0,0,2,2,1],[1,0,1,3,0,0,3,0,1],[1,0,1,3,0,1,0,1,3],[1,0,1,3,0,1,0,2,1],[1,0,1,3,0,1,1,0,1],[1,0,2,0,0,3,3,3,3],[1,0,2,0,1,1,3,3,3],[1,0,2,0,1,2,1,3,3],[1,0,2,0,1,2,2,1,3],[1,0,2,0,1,2,2,2,1],[1,0,2,0,1,2,3,0,1],[1,0,2,0,1,3,0,1,3],[1,0,2,0,1,3,0,2,1],[1,0,2,0,1,3,1,0,1],[1,0,2,0,2,0,1,3,3],[1,0,2,0,2,0,2,1,3],[1,0,2,0,2,0,2,2,1],[1,0,2,0,2,0,3,0,1],[1,0,2,0,2,1,0,1,3],[1,0,2,0,2,1,0,2,1],[1,0,2,0,2,1,1,0,1],[1,0,2,1,0,0,1,3,3],[1,0,2,1,0,0,2,1,3],[1,0,2,1,0,0,2,2,1],[1,0,2,1,0,0,3,0,1],[1,0,2,1,0,1,0,1,3],[1,0,2,1,0,1,0,2,1],[1,0,2,1,0,1,1,0,1],[1,1,0,0,0,3,3,3,3],[1,1,0,0,1,1,3,3,3],[1,1,0,0,1,2,1,3,3],[1,1,0,0,1,2,2,1,3],[1,1,0,0,1,2,2,2,1],[1,1,0,0,1,2,3,0,1],[1,1,0,0,1,3,0,1,3],[1,1,0,0,1,3,0,2,1],[1,1,0,0,1,3,1,0,1],[1,1,0,0,2,0,1,3,3],[1,1,0,0,2,0,2,1,3],[1,1,0,0,2,0,2,2,1],[1,1,0,0,2,0,3,0,1],[1,1,0,0,2,1,0,1,3],[1,1,0,0,2,1,0,2,1],[1,1,0,0,2,1,1,0,1],[1,1,0,1,0,0,1,3,3],[1,1,0,1,0,0,2,1,3],[1,1,0,1,0,0,2,2,1],[1,1,0,1,0,0,3,0,1],[1,1,0,1,0,1,0,1,3],[1,1,0,1,0,1,0,2,1],[1,1,0,1,0,1,1,0,1]]
\$\endgroup\$
3
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – pxeger
    Dec 5 '21 at 19:32
  • 4
    \$\begingroup\$ May I output [[]] for 0? \$\endgroup\$
    – tsh
    Dec 6 '21 at 5:58
  • \$\begingroup\$ @tsh hmm, I was gonna say no but I see that it's logical since it's arguably a leading zero... I guess you can. \$\endgroup\$
    – pxeger
    Dec 6 '21 at 7:54

11 Answers 11

7
\$\begingroup\$

R, 97 81 78 73 68 bytes

Or R>=4.1, 61 bytes by replacing the word function with \.

-11 bytes and another -3 thanks to @Giuseppe.
-5 bytes thanks to @Dominic van Essen.

function(n,c,g=t(expand.grid(rep(list(0:c),n+1))))g[,2^(n:0)%*%g==n]

Try it online!

Brute-force solution.
Multiple vectors are output column-wise. Outputs additional leading zeros.
Deals with the 0 case in a rather ugly manner. No if thanks to @Dominic van Essen.

Explanation

function(n,c,   # a function taking n and c as arguments
 g=             # we use another argument to compute g 
                # - all combinations of digits 0..c of length n+1
  t(            # transpose (converts from data frame to matrix)
   expand.grid( # all combinations of
   rep(         # repeat...
    list(0:c),  # ...a list of digits 0..c 
                # (list to repeat whole object not just append to vector) ...
    n+1         # n+1 times (to handle 0 edge case)
))))            ​
g[,             # get all rows of g
                # and columns where ...
 2^(n:0)        # ...powers of 2: 2^n to 2^0...
  %*%g          # ...matrix-multplied by g 
                # (the vector of powers is promoted to a column matrix)
                # - this resuts in a row matrix of corresponding overflowed binary numbers - ...
 ​==n]           # ... equal input n

Longer but faster and without additional leading zeros:

R, 93 bytes

Or R>=4.1, 86 bytes by replacing the word function with \.

function(n,c,g=t(expand.grid(rep(list(0:c),b<-log2(n)%/%1+1))))"if"(n,g[,2^(b:1-1)%*%g==n],0)

Try it online!

\$\endgroup\$
10
  • 1
    \$\begingroup\$ 86 bytes though it runs out of memory. \$\endgroup\$
    – Giuseppe
    Dec 5 '21 at 21:39
  • \$\begingroup\$ Something might be able to be done with combn but the uniqueness might cost some additional bytes. \$\endgroup\$
    – Giuseppe
    Dec 5 '21 at 21:40
  • 1
    \$\begingroup\$ @pajonk - (although, based on the OP's answer to tsh, you could probably just output an empty matrix for the zero case, but I think your solution is much nicer) \$\endgroup\$ Dec 6 '21 at 12:40
  • 1
    \$\begingroup\$ @thejonymyster done. \$\endgroup\$
    – pajonk
    Dec 6 '21 at 20:55
  • 1
    \$\begingroup\$ alternate 68 bytes \$\endgroup\$
    – Giuseppe
    Dec 7 '21 at 0:35
6
\$\begingroup\$

Jelly, 10 8 bytes

Żṗ‘}Ḅ=¥Ƈ

Try it online!

Takes c on the left, n on the right

Brute-force approach. Generates all lists of length \$n+1\$ containing the numbers \$0\$ to \$c\$, meaning that it times out for \$n > 7\$ on TIO. For a much faster version, see the revision history.

-2 bytes thanks partially to a suggestion by hyper-neutrino

How it works

Żṗ‘}Ḅ=¥Ƈ - Main link. Takes c on the left, n on the right
Ż        - Generate the range [0, ..., c]
   }     - To n:
  ‘      -   Yield n+1, to account for n = 0
 ṗ       - Cartesian power. Yield all lists of length n+1 of the elements of [0, ..., c]
      ¥Ƈ - Keep those for which the following is true:
    Ḅ    -   When converting from binary,
     =   -   they equal n
\$\endgroup\$
0
6
\$\begingroup\$

J, 26 24 bytes

]((=#.)#])((##:i.@^~)>:)

Try it online!

Brute force. In this case, the idea is simple -- just try all possible combos and filter the ones which match n -- but the J mechanics are kind of fun: The whole thing is fork, made up of nested forks and dyadic hooks:

enter image description here

\$\endgroup\$
1
  • 2
    \$\begingroup\$ +1 for the renaissance picture :D \$\endgroup\$ Dec 7 '21 at 8:48
5
\$\begingroup\$

Wolfram Language (Mathematica), 52 bytes

Cases[FrobeniusSolve[2^Range[#,0,-1],#],s_/;s#2]&

Try it online!

-3 bytes thanks to @att.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 52 bytes \$\endgroup\$
    – att
    Dec 6 '21 at 23:07
  • \$\begingroup\$ What is supposed to be? It's displayed as an empty rectangle for me, and copy-pasting the code into Mathematica 11.2 doesn't work correctly. \$\endgroup\$
    – Ruslan
    Dec 7 '21 at 22:49
  • 1
    \$\begingroup\$ @Ruslan \[VectorLessEqual], here xy means x[[i]]<=y for every i. This symbol is introduced in Mathematica 12.0. See @att's Mathematica golfing tip: codegolf.stackexchange.com/a/236601/9288 \$\endgroup\$
    – alephalpha
    Dec 7 '21 at 23:48
3
\$\begingroup\$

Charcoal, 20 bytes

IΦE↨↨⊕θ²⊕η↨ι⊕η⁼Iθ↨ι²

Try it online! Link is to verbose version of code. Output removes all leading zeros even for an output of zero (which is simply empty). Uses brute force but easily manages the last test case on TIO. Explanation:

      θ                 First input `n`
     ⊕                  Incremented
    ↨                   Converted to base
       ²                Literal `2`
   ↨                    Interpreted as base
         η              Second input `c`
        ⊕               Incremented
  E                     Map over implicit range
           ι            Current value
          ↨             Converted to base
             η          Second input `c`
            ⊕           Incremented
 Φ                      Filtered where
                  ι     Current base `c+1` value
                 ↨      Interpreted as base
                   ²    Literal `2`
              ⁼         Equals
                θ       First input `n`
               I        Cast to integer
I                       Cast to string
                        Implicitly print

Technically it would be more efficient to convert n into base 2 and from base c+1 first before incrementing but this is code golf.

\$\endgroup\$
3
\$\begingroup\$

Python 3.8 (pre-release), 92 bytes

f=lambda n,a,*i:n and f(n//2,a,n%2,*i)+(()<i<(a-1,)and f(n-1,a,i[0]+2,*i[1:])or[])or[[0,*i]]

Try it online!

Straight-forward recursion.

\$\endgroup\$
3
\$\begingroup\$

Vyxal RM, 7 bytes

›ÞẊ'B¹=

Try it Online!

The R flag automatically converts ranges to digits. The M flag changes the default range from 1...n to 0...n.

›ÞẊ     # Cartesian power - 0...c combinations to length n
   '    # Filtered by...
    B   # Binary
      = # Equal to 
     ¹  # n?

Luckily, Vyxal has the same bug feature as Jelly of automatically converting overflowed binary.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (SpiderMonkey), 80 bytes

c=>g=(n,t,i=c-(c+n&1))=>n?n*i<0?[]:g(n-i>>1,t?i+[,t]:[i])+g(n,t,i-2):print(t||0)

Try it online!


JavaScript (Node.js), 79 bytes

c=>g=(n,t=[],i=c-(c+n&1))=>n?n*i<0?[]:[...g(n-i>>1,[i,...t]),...g(n,t,i-2)]:[t]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 7 bytes

Ýsãʒ2βQ

Try it online!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (V8), 84 bytes

Expects (c)(n) and prints all solutions as space-separated strings.

c=>g=(n,j,o,h=i=>~i&&g(n-(i<<j),-~j,i+' '+[o])|h(i-1))=>(n>>j)>0?h(c):n||print(o||0)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 3, 81 79 bytes

f=lambda a,b:[[]][a:]or[d+[i]for i in range(a,-1,-2)for d in(i<=b)*f(a-i>>1,b)]

Try it online!

Outputs without leading zeroes.

\$\endgroup\$

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.