Simplify binary

Question

Challenge

Given a binary number as input through any means, "simplify" the number using a full program or a function.

Input

[binary]

• binary is a number in binary that is over 0.

Output

Take the input, convert it to base 10 without using a builtin, then if that number contains only 1s and 0s, convert it into a base 10 number as if it were another binary number. Repeat the process until the number cannot be read in binary and output that number.

Other information

• If the input is 1, simply output 1. Your program should not go on infinitely simplifying 1.

• This is code golf, so shortest answer in bytes by Tuesday (November 17th) wins.

• If anything is confusing, leave a comment specifying what I need to clear up and I will edit it accordingly.

• Builtins for base conversion are not allowed.

Examples

     Input | Output

         1 | 1
      1010 | 2
      1011 | 3
   1100100 | 4
   1100101 | 5
1111110011 | 3

Answer 1

Pyth, 20 16 bytes

u?-GTG`u+yNsTG0z

4 bytes thanks to Jakube

Half of the code (u+yNsTG0) is simply the base conversion code.

Test Suite

u?-GTG`u+yNsTG0z
                    z = input() (The string of 1s and 0s)
                    T = 10
u              z    Apply until the value stops changing, starting with z
                    G is the current value, a string of 0s and 1s.
 ?-GT               If G - T, e.g., G with the digits 1 and 0 removed is not empty,
     G              Return G, to end the iteration.
       u     G0     Else, reduce over G with initial value 0.
         yN         Double the running total
        +  sT       and add the next digit, cast to an int.
      `             Convert to string.

The input 1 is handled by the fact that u notices the value has stopped changing.

Answer 2

CJam, 24 23 bytes

q{:~{1$++}*s__,(As*-!}g

Try it online in the CJam interpreter.

How it works

q                        Read all input.
 {                   }g  Do:
  :~                       Evaluate each character. Maps '0' -> 0 and '1' -> 1.
    {    }*                Fold; for each integer but the first:
     1$                      Copy the second-topmost integer.
       ++                    Add all three integers on the stack.
           s__             Cast to string and push two copies.
              ,(           Calculate string length and subtract 1.
                As         Push the string "10".
                  *        Repeat the string length-1 times.
                   -       Remove its elements from the string representation
                           of the integer.
                    !      Apply logical NOT.
                         If `!' pushed 1, repeat the loop.

Answer 3

Pip, 28 27 bytes

Ta=1|aRMta:$+(^a)*2**RV,#aa

Takes input as a command-line argument. We want to loop until a=1 or a contains some character(s) besides 0's and 1's. This latter condition is tested by RM'ing all characters in t = 10 from a. If there's anything left, the condition is truthy.

Inside the loop, the conversion works as follows:

a:$+(^a)*2**RV,#a

              ,#a  range(len(a))
            RV     reversed
         2**       2 to the power of each element
    (^a)*          multiplied item-wise with each digit in split(a)
  $+               Sum
a:                 and assign back to a

Putting a at the end auto-prints it.

A recursive solution in 28 bytes:

a<2|aRMt?a(f$+(^a)*2**RV,#a)

Answer 4

Python 2, 52

f=lambda n:n>1<'2'>max(`n`)and f(n%10+2*f(n/10))or n

It's easier to think of this as two recursive functions:

g=lambda n:n and n%10+2*g(n/10)
f=lambda n:n>1<'2'>max(`n`)and f(g(n))or n

The function g converts a decimal value to binary, and the function f applies g repeatedly is long as its argument is made of digits 0 and 1 ('2'>max(`n`)) and is not 1. The golfed code collapses them into a single function by inserting the definition of g(n) for f(n), replacing the recursive call to g with f. The base case of n=0 of g is automatically handled by the check n>1.

Answer 5

Prolog, 220 212 bytes

:-use_module(library(clpfd)).
x(B,N):-reverse(B,C),foldl(y,C,0-0,_-N).
y(B,J-M,I-N):-B in 0..1,N#=M+B*2^J,I#=J+1.
b(N,I):-N>47,N<50,I is(N-48).
p(N):-N>1,number_codes(N,L),maplist(b,L,Y),x(Y,B),p(B);write(N).

Explanation
p is the main function and performs the following steps (with help from b,x,y):

• checks if current number is bigger than 1
• converts integer to list of ascii representations of digits
• checks that all numbers are 0 or 1
• converts ascii list to binary integer list
• converts binary integer list to decimal number
• recurses
• prints when a predicate fails.

Edit: Saved 8 bytes by unifying the p-clauses with OR.

Answer 6

Mathematica 107 106

With a byte saved by DLosc.

j@d_:=(p=0;v=IntegerDigits@d;
Which[d<2,1,Complement[v,{0,1}]=={},j@Fold[#+#2 2^p++&,0,Reverse@v],1<2,d])

Break the input into its digits. If the input is 1, output 1.

If the input is a number consisting of 0's and 1's, convert that to decimal and run it through again.

Otherwise, return the input.

---

j[1]

1

---

j[11010001]

209

---

j[1111110001]

1009

---

j[1111110011]

3

The first step yields 1011 which in turn yields 3.

---

Here we test starting with 1011.

j[1011]

3

Answer 7

JavaScript ES6, 52

As a function. The function argument must be either a string of binary digits or a number whose decimal representation contains only 1 and 0.

Test running the snippet below in an EcmaScript 6 compliant browser - implementing arrow functions, template strings and spread operator (I use Firefox)

f=s=>s<2|[...s+''].some(c=>(n+=+c+n,c>1),n=0)?s:f(n)

// To test
console.log=(...x)=>O.innerHTML+=x+'\n';

// Basic test cases
;[[1,1],[1010,2],[1011,3],[1100100,4],[1100101,5],[1111110011,3]]
.forEach(t=>console.log(t[0]+' -> '+f(t[0])+' expected '+t[1]))

function longtest() {
  var o=[],i;
  for (i=1;i<1e6;i++)
    b=i.toString(2),v=f(b),v!=i?o.push(b+' '+v):0;
  O.innerHTML=o.join`\n`
}

Click to run the long test <button onclick="longtest()">go</button>
<pre id=O></pre>

Answer 8

Javascript, 132, 123 bytes

Well, it's not the best answer, but..

FYI, if an invalid input is given, it displays the same to the user.

function c(x){while(x!=0&&!/[2-9]/.test(x)){for(i=r=0;x;i++)r+=x%10*Math.pow(2,i),x=parseInt(x/10);x=r}alert(x)}c(prompt())

Answer 9

Mathematica, 62 59 55 48 bytes

Saved 7 bytes thanks to Martin Büttner.

#//.a_/;Max[b=IntegerDigits@a]<2:>Fold[#+##&,b]&

Answer 10

R, 75 68 bytes

• -7 bytes by rewriting if and digit extraction (pajonk)

f=\(b)`if`(b>1&all((K=b%/%10^(X=0:nchar(b))%%10)<2),f(sum(2^X*K)),b)

Attempt This Online!

A recursive function: the first if-condition is checking whether the input is not 1 or 0; the second condition checks whether there are only the digits 0 or 1 in the generated on the fly K vector. Then the function is called again, with the b converted to its decimal form as the input. Outside of if In the else-clause b is output (outputted ?).

Answer 11

Javascript (ES7) 87 80 78 77 74 bytes

Snippet demo for supporting browsers (currently only Firefox nightly supports the exponential operator)

f=x=>[...x].reverse(i=y=j=0).map(z=>(j|=z,y+=z*2**i++))&&j<2&y>1?f(y+[]):x

<input type="text" id="x" value="1111110011"><button onclick="o.innerHTML=f(x.value)">Run</button><div id="o"></div>

f=x=>
[...x].reverse(i=y=j=0) // reverse string as array, initialize vars
.map(z=>( // iterate over the all chatacters
    j|=z, // keep track of whether a digit higher than 1 is encountered
    y+=z*2**i++ // build decimal result from binary
))&&
j<2&y>1? // if we encountered only 1's and 0's and result > 1
    f(y+[]) // then call recursively and cast to a string
    :x // else return x

Javascript (ES6) 81 bytes

Snippet demo for supporting browsers

f=x=>[...x].reverse(i=y=j=0).map(z=>y+=z*Math.pow(2,i++,j|=z))&&j<2&y>1?f(y+[]):x

<input type="text" id="x" value="1111110011"><button onclick="o.innerHTML=f(x.value)">Run</button><div id="o"></div>

Answer 12

𝔼𝕊𝕄𝕚𝕟, 37 chars / 54 bytes

↺;ï>1⅋(⬯+ï)ĉ/^[01]+$⌿);)ï=+('ᶀ'+ï);ôï

Try it here (Firefox only).

Not sure if the + operator counts as a built-in for binary conversion...

Answer 13

Perl 6, 67 bytes

get,{$_=0;for $^a.comb {$_+<=1;$_+=$^b};$_}...1|/<-[01]>/;say $_//1

Answer 14

PHP, 210 204 bytes

It's my first time posting here, so hope you guys will like it ! Even if it's obviously not the best way to write it, I'm still glad to show it off here !

The Code

<?function j($a){$c=0;if($a==1){return 1;}else{if(preg_match("#^[01]+$#",$a)){$b=strlen($a);$a=str_split($a);foreach($a as$d){$c+=($d==0?0:2**($b-1));$b--;}return j($c);}else{return$a;}}}echo j($_GET[0]);

I've made a recursive function "j" that will first check if the input is equal to 1. If so, the function returns 1 as expected, else it'll split the number in an array to calculate the decimal value, but only if the number is a binary one. If it's not, it'll return the number as is.

Ungolfed code

<?
function j($a) {
  $c = 0;
  if ($a == 1) {
    return 1;
  }
  else {
    if (preg_match("#^[01]+$#", $a) {
      $b = strlen($a);
      $a = str_split($a);
      foreach ($a as $d) {
        $c += ($d == 0 ? 0 : 2 ** ($b - 1));
        $b--;
      }
      return j($c);
    }
    else {
      return $a;
    }
  }
}
echo j($_GET[0]);

I've used a "foreach" statement instead of my initial "for" one, allowing me a gain of 6 bytes but I'm pretty sure there's a lot more to do.

Answer 15

PHP, 114 112 bytes

also works for 0. Run with -r.

for($n=$argv[1];count_chars($s="$n",3)<2&$s>1;)for($i=$n=0;""<$c=$s[$i++];)$n+=$n+$c;echo$s;

count_chars($s,3) returns a string containing all characters from the string (like array_unique does for arrays). For binary numbers, this will be 0, 1 or 01. For other numbers, this will contain a digit larger than 1, so <2will return true only for binary numbers.

&$s>1 is needed for the special case 1.

The rest is straight forward: Loop through the bits with shifting the value and adding the current bit, finally copy the number (cast to string) to $s for the outer loop test.

Answer 16

Go, 123 bytes

func f(n int)(o int){if n<2{return n}
for i:=0;n>0;i++{o+=n%10<<i
n/=10}
for k:=o;k>0;k/=10{if k%10>1{return}}
return f(o)}

Attempt This Online!

A recursive function that takes in an int containing only 0s and 1s, and outputs an `int.

Ungolfed Explanation

// input is a decimal number with only 0s and 1s
func f(n int)(o int){
// return immediately if n=1
if n<2{return n}
// bin-to-dec conversion
for i:=0;n>0;i++{
    o+=n%10<<i
    n/=10
}
// checking for non-0-or-1 digits
for k:=o;k>0;k/=10{
   // if there is one, immediately return
   if k%10>1{return}
}
// otherwise repeat the process
return f(o)}

Answer 17

Vyxal 3, 14 bytes

ᶪλf₀fṡ[|fṚÞỊE∑

Try it Online!

Answer 18

Scala 3, 104 bytes

A port of @xor's Python 2 answer in Scala.

---

Golfed version. Attempt This Online!

def g(n:Int):Int=if(n<1)0 else n%10+2*g(n/10)
def f(n:Int):Int=if(n>1&&'2'>n.toString.max)f(g(n)) else n

Ungolfed version. Attempt This Online!

object Main {
  def main(args: Array[String]): Unit = {
    def g(n: Int): Int = if (n == 0) 0 else n % 10 + 2 * g(n / 10)

    def f(n: Int): Int = if (n > 1 && '2' > maxDigit(n.toString)) f(g(n)) else n

    def maxDigit(s: String): Char = s.max

    println(f(1))
    println(f(1010))
    println(f(1011))
    println(f(1100100))
    println(f(1100101))
    println(f(1111110011))
  }
}

Answer 19

Jelly, 5 chars (8 bytes)

DḄ$ÐL
  $      # 2 previous functions
D        # Split number into digits
 Ḅ       # Convert to binary
   ÐL    # Repeat until output matches input

I mean, obviously this still counts as a win for Dennis.

Answer 20

Perl 5 -p, 48 + 1 = 49 bytes

$b=0;s/./$b=2*$b+$&/ge;$_=$b;y/01//c||$_<2||redo

Try it online!

Answer 21

CoffeeScript, 92 89 bytes

f=(x)->x>1&/^[01]+$/.test(x)&&f(''+x.split('').reverse().reduce ((p,v,i)->p+v*2**i),0)||x

JavaScript (ES6), 105 101 90 bytes

f=y=>y>1&/^[01]+$/.test(y)?f(''+[...y].reverse().reduce(((p,v,i)=>p+v*Math.pow(2,i)),0)):y

Demo

Only works in ES6-compliant browsers such as Firefox and Microsoft Edge

f=y=>y>1&/^[01]+$/.test(y)?f(''+[...y].reverse().reduce(((p,v,i)=>p+v*Math.pow(2,i)),0)):y

// Snippet stuff
$(`form`).submit((e) => {
  document.getElementById(`y`).textContent = f(document.getElementById(`x`).value);
  e.preventDefault()
})

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<form>
  <label>Input:
    <input pattern=^[01]+$ required id=x>
  </label>
  <button type=submit>Go</button>
  <p>Output:
    <output id=y></output>
  </p>
</form>

Answer 22

Scala, 128 bytes

def b(s:String):String=if(s.matches("[10]{2,}"))b(""+s.reverse.zipWithIndex.collect{case('1',i)=>Math.pow(2,i)}.sum.toInt)else s

Answer 23

Matlab (115)

@(a)num2str(sum((fliplr(a)-48).*arrayfun(@(x)2^x,0:nnz(a)-1)));a=ans(input('','s'));while(find(a<50))a=ans(a);end,a

---

• The anonymous function is number type conversion (bin2dec)