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
  • 4
    Could use a couple test cases. – isaacg Nov 11 '15 at 2:10
  • Is the input an ASCII string, or actually 1's and 0's? – Tom Carpenter Nov 11 '15 at 2:15
  • @TomCarpenter 1s and 0s. – The_Basset_Hound Nov 11 '15 at 2:20
  • @isaacg Added ways to get 1-5 as output. – The_Basset_Hound Nov 11 '15 at 2:21
  • Are functions which convert a string to a given base allowed? – isaacg Nov 11 '15 at 2:40

17 Answers 17

up vote 14 down vote accepted

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.

  • 4
    Congratulations, you outgolfed Dennis! For the moment... – Conor O'Brien Nov 11 '15 at 2:51
  • 9
    @CᴏɴᴏʀO'Bʀɪᴇɴ The secret is Pyth. – isaacg Nov 11 '15 at 2:52

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.
  • Do you have to repeat the "10" string length-1 times, or could you skip the decrement? – DLosc Nov 11 '15 at 3:34
  • Subtracting 1 from the length turns "10" into "" if the integer has a single digit. This makes sure the code doesn't get into an infinite loop. – Dennis Nov 11 '15 at 3:35
  • 2
    Fascinating, captain. }:^| – DLosc Nov 11 '15 at 3:37

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)

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.

  • Nice :) The only thing is that the usual problem applies - the pesky L from repr... – Sp3000 Nov 11 '15 at 7:47

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.

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

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())

  • 1
    You could save 19 bytes by using forinstead of while and setting values directly in the statement (this also reduces some {}), discarding some ;, using ES6 function description, increment i inline. It'll look like this: c=x=>{for(r=0;x&&!/[2-9]/.test(x);x=r)for(i=0;x>0;r+=x%10*Math.pow(2,i++),x=parseInt(x/10));alert(x)};c(prompt()). – insertusernamehere Nov 11 '15 at 14:00
  • 1
    114: function c(x){while(x^0&&!/[2-9]/.test(x)){for(i=r=0;x;i++)r+=x%10*Math.pow(2,i),x=0|x/10;x=r}alert(x)}c(prompt()) – Mama Fun Roll Nov 13 '15 at 6:03
  • @insertusernamehere, thanks for the suggestion, but I didn't understand the c=x=> at the start, didn't work on Chrome or Firefox console. :( @ןnɟuɐɯɹɐןoɯ, could not wrap my head around the XOR condition and the x=0|x/10‌ instead of parseInt, I've incorporated the rest of the changes. Thanks.. – LearningDeveloper Nov 16 '15 at 5:36
  • @GauthamPJ I'm sorry, somehow the code got broken while copying and contained unprintable characters. Here's the correct version: c=x=>{for(r=0;x!=0&&!/[2-9]/.test(x);x=r)for(i=r=0;x;)r+=x%10*Math.pow(2,i++),x=parseInt(x/10);alert(x)};c(prompt()). It definitely runs in Firefox 42, try this fiddle. Note that this more golfed version and also your original code don't work for 1 and will run into an endless loop. c=x=> is like function c(x){} see "Arrow functions". – insertusernamehere Nov 16 '15 at 9:44

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>

  • 1
    Really liking n+=+c+n for the binary conversion. So elegant... – nderscore Nov 11 '15 at 15:14

Mathematica, 62 59 55 48 bytes

Saved 7 bytes thanks to Martin Büttner.

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

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>

𝔼𝕊𝕄𝕚𝕟, 37 chars / 54 bytes

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

Try it here (Firefox only).

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

Perl 6, 67 bytes

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

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.

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.

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>

  • If you use eval, you might be able to pull off an implicit return. – Mama Fun Roll Nov 11 '15 at 5:08
  • 5 bytes shorter with eval and anonymous functions – Downgoat Nov 11 '15 at 5:15
  • @ןnɟuɐɯɹɐןoɯ For some reason the eval'd function does not work with 1. because it doesn't enter the loop I assume – rink.attendant.6 Nov 11 '15 at 5:20
  • 1
    @nderscore Thanks, but recursion was 4 bytes shorter :-) – rink.attendant.6 Nov 11 '15 at 5:46

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

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)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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