17
\$\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]]
Improve this question
\$\endgroup\$
3
  • \$\begingroup\$ Sandbox \$\endgroup\$ Commented Dec 5, 2021 at 19:32
  • 5
    \$\begingroup\$ May I output [[]] for 0? \$\endgroup\$ Commented Dec 6, 2021 at 5:58
  • 2
    \$\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\$ Commented Dec 6, 2021 at 7:54

11 Answers 11

Reset to default
7
\$\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
Improve this answer
\$\endgroup\$
0
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!

Improve this answer
\$\endgroup\$
10
  • 1
    \$\begingroup\$ 86 bytes though it runs out of memory. \$\endgroup\$ Commented Dec 5, 2021 at 21:39
  • \$\begingroup\$ Something might be able to be done with combn but the uniqueness might cost some additional bytes. \$\endgroup\$ Commented Dec 5, 2021 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\$ Commented Dec 6, 2021 at 12:40
  • 1
    \$\begingroup\$ @thejonymyster done. \$\endgroup\$ Commented Dec 6, 2021 at 20:55
  • 1
    \$\begingroup\$ alternate 68 bytes \$\endgroup\$ Commented Dec 7, 2021 at 0:35
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

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ +1 for the renaissance picture :D \$\endgroup\$ Commented Dec 7, 2021 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.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 52 bytes \$\endgroup\$ Commented Dec 6, 2021 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\$ Commented Dec 7, 2021 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\$ Commented Dec 7, 2021 at 23:48
3
\$\begingroup\$

Charcoal, 20 bytes

ＩΦＥ↨↨⊕θ²⊕η↨ι⊕η⁼Ｉθ↨ι²

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
  Ｅ                     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`
               Ｉ        Cast to integer
Ｉ                       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.

Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 7 bytes

Ýsãʒ2βQ

Try it online!

Improve this answer
\$\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!

Improve this answer
\$\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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.