Convert numbers to binary... but you're allowed to use twos as well

Question

Based on the "binary, but with twos" notation mentioned in this numberphile video, write a function that takes a single number as input and outputs all variations of that number in a "binary" system where twos are allowed.

Rules

• Code must only be a function/method, not a full program
• Input is an integer passed as the sole parameter to the function
• Output is all valid variations of the input number converted to "binary, but with twos" notation
• Output is the return value of the function, but can be in whatever format is convenient as long as it's obvious (eg, 3 ints, 3 strings, comma/space delimited string, array of ints, etc), order is unimportant
• In the unlikely event that a language happens to contain a built-in function to achieve the result, it's disallowed
• Shortest code in bytes is the winner

Explanation of the output

By example, if you're passed the number 9, you can convert it to binary as 1001, but if you allowed 2s in each position, you could also write it as 201 (i.e. 2*4 + 0*2 + 1*1), or 121 (i.e. 1*4 + 2*2 + 1*1), as shown in this table:

+----+----+----+----+
| 8s | 4s | 2s | 1s |
+----+----+----+----+
|  1 |  0 |  0 |  1 |
|  0 |  2 |  0 |  1 |
|  0 |  1 |  2 |  1 |
+----+----+----+----+

So, if passed 9, your function would need to return the three numbers, 1001, 201 and 121.

Format and order are irrelevant, so long as it's obvious (i.e. [121,201,1001], "0201 0121 1001", ("1001","121","201") are valid results when given an input of 9).

Examples

• 2 => 10, 2
• 9 => 1001, 201, 121
• 10 => 1010, 210, 202, 1002, 122
• 23 => 2111, 10111
• 37 => 100101, 20101, 100021, 20021, 12101, 12021, 11221

Answer 1

GolfScript (25 bytes) / CJam (19 17 bytes)

GolfScript:

{:^.*,{3base}%{2base^=},}

This creates an anonymous function (see meta discussion about permissibility of anonymous functions).

Online demo

A straight translation into CJam is (with thanks to Martin Büttner for shaving a couple of characters)

{:X_*,3fb{2bX=},}

Dissection

{             # Function boilerplate
  :^          # Store parameter as variable ^
  .*          # Square parameter - see detailed explanation below
  ,{3base}%   # Produce an array of 0 to ^*^-1 in ternary
  {2base^=},  # Filter to those which evaluate to ^ in binary
}

The reason for the squaring operation is that we need to iterate up to the largest possible value whose ternary representation, interpreted in binary, is equal to ^. Since 2 = 10, the "normal" binary representation of ^ is the one which matters. If we convert that to ternary, we find that the "worst" cases are powers of 2. An optimal approach would be to take the argument to the power of ln 3/ln 2 ~= 1.585, but squaring is much shorter.

Answer 2

Python 2 (59 bytes)

S=lambda n,B="":[B][n:]or~n%2*S(n/2-1,"2"+B)+S(n/2,`n&1`+B)

(Much thanks to @grc, @xnor and @PeterTaylor for helping out in chat)

Simple recursion, call with S(23) or similar.

Explanation

The general idea is that if n's binary expansion ends in a 1, then any pseudo-binary ("binary, but with twos") expansion must also end with a 1. Otherwise it could end with 0 or 2.

Hence we look at the last bit of n, divide out and branch accordingly.

Dissection

S=lambda n,B="":           # Lambda expression
[B][n:]or                  # Short circuit, return [B] if n==0 else what follows
~n%2*                      # Keep next list result if n is even else turn into []
S(n/2-1,"2"+B)             # Add a "2" to B, recurse
+
S(n/2,`n&1`+B)             # Add "0" or "1" to B depending on n's last bit, recurse

Variables:

• n: The number we want to find pseudo-binary expansions of
• B: A pseudo-binary string being built right-to-left

Answer 3

Bash+coreutils, 77

f()(seq `dc -e2o$1p`|sed '/[3-9]/d;s/.*/&n9P2i&pAi/'|dc|grep -Po ".*(?= $1)")

(That is a TAB character in the grep expression.)

This is bending this rule a bit:

"In the unlikely event that a language happens to contain a built-in function to achieve the result, it's disallowed"

It turns out that dc has the reverse of what we need built in. For instance if we set the input base to 2 and input a binary number with twos, it will correctly parse it. (Similarly if the input mode is base 10, then A-F are parsed as decimal "digits" 10-15).

seq creates a list of all decimal numbers up to the standard binary representation of n, parsed as a decimal. Then all numbers that contain anything other than {0,1,2} are filtered out. Then dc parses the remaining numbers as binary to see which evaluate back to n.

Bash functions can only "return" scalar integers 0-255. So I'm taking the liberty of printing the list to STDOUT as my way of "returning". This is idiomatic for shell scripts.

Output:

$ f 2
2   
10  
$ f 9
121 
201 
1001    
$

Answer 4

Haskell, 82

t n=[dropWhile(==0)s|s<-mapM(\_->[0..2])[0..n],n==sum[2^(n-i)*v|(i,v)<-zip[0..]s]]

this is just a brute-force solution. it is very inefficient, because it is expected to crunch through 3^n possibilities.

Answer 5

Jelly, 10 bytes, language postdates challenge

ṗ@3Ḷ¤Ḅ=¥Ðf

Try it online!

A bruteforce solution up to a number of hyperbits equal to the input (this format is known as "hyperbinary"). As such, it's incredibly inefficient, running in O(3ⁿ).

Explanation

ṗ@3Ḷ¤Ḅ=¥Ðf
ṗ@            Construct all lists with the given length, and elements taken from
  3Ḷ¤         the list [0,1,2]
        Ðf    then take only those elements which
     Ḅ=¥      when interpreted as binary, equal {the original number}

Answer 6

PHP, 138 Bytes

function p($v,$i=0,$r=""){global$a;if($v==0)$a[]=$r?:0;elseif($v>0)for(;$l<3;)p($v-2**$i*$l,$i+1,+$l++.$r);}p($argv[1]);echo join(",",$a);

Breakdown

function p($v,$i=0,$r=""){
    global$a;
    if($v==0)$a[]=$r?:0;  # fill result array
    elseif($v>0) # make permutations
        for(;$l<3;)
            p($v-2**$i*$l,$i+1,+$l++.$r); #recursive
}
p($argv[1]);
echo join(",",$a); # Output

Answer 7

C++, 159 bytes

void c(int x,string r){int i,t=0,s=r.size();if(s<8){if(r[0]>48){for(i=0;i<s;i++)t+=(r[s-i-1]-48)*1<<i;if(t==x)cout<<r<<" ";}for(char n=48;n<51;n++)c(x,r+n);}}

Test it here

Answer 8

k, 21 bytes

Uses the same method as Peter Taylor's Golfscript answer

{X@&x=2/:'X:3\:'!x*x}

Examples:

k) {X@&x=2/:'X:3\:'!x*x}9
(1 2 1;2 0 1;1 0 0 1)
k) {X@&x=2/:'X:3\:'!x*x}10
(1 2 2;2 0 2;2 1 0;1 0 0 2;1 0 1 0)

Answer 9

Haskell, 80 bytes

f 0=[[]]
f n=((++[n-2*d])<$>f d)++[x|n==2*d,x<-(++[2])<$>(f$d-1)]where d=n`div`2

Try it online!

Recursive solution, and my first Haskell golf.

-- recursive definition
-- base case: a sum of 0 is possible as simply a 0-length "binary-with-two" string
f 0=[[]]
-- f n=all possibilities to form n
f n =
-- like normal binary, can have a last digit of 0 or 1 if even or odd, respectively
-- consider n`mod'`2 = n-2*d
  (
    (++[n-2*d])<$> -- add that last digit to each
    f d -- possibility from n/2
  )
-- additional possibility of last digit 2, only if n is even
     n==2*d -- if n is even:
  [x|      ,x<-(++[2])<$>(f$d-1)] -- add that last digit 2 to each possibility from (n-2)/2
  where d=n`div`2