Decompose binary into alternating subsequences

Question

This was inspired by Problem 13 - Non-Repeating Binary of HP CodeWars' recent competition.

Let's take a random decimal number, say

727429805944311

and look at its binary representation:

10100101011001011111110011001011101010110111110111

Now split that binary representation into subsequences where the digits 0 and 1 alternate.

1010 010101 10 0101 1 1 1 1 1 10 01 10 0101 1 1010101 101 1 1 1 101 1 1

And convert each subsequence back into decimal.

10 21 2 5 1 1 1 1 1 2 1 2 5 1 85 5 1 1 1 5 1 1

The Task

Take a single, positive integer as input and output the sequence of positive integers obtained by the above process.

Details

• Input and output must be in decimal or unary.
• Numbers in the output must be separated in a sensible, human-readable fashion, and they must be in decimal or unary. No restriction on white space. Valid output styles: [1,2,3], 1 2 3, 1\n2\n3 where \n are literal newlines, etc.

Test cases

 Input | Output
     0 | 0
     1 | 1
     2 | 2
     3 | 1 1
     4 | 2 0
     5 | 5
     6 | 1 2
     7 | 1 1 1
     8 | 2 0 0
     9 | 2 1
    10 | 10
    50 | 1 2 2
   100 | 1 2 2 0
  1000 | 1 1 1 1 10 0 0
 10000 | 2 1 1 2 0 2 0 0 0
 12914 | 1 2 2 1 1 2 2
371017 | 5 42 10 2 1

Additional note: all numbers in the output should be of the form (2^k-1)/3 or 2*(2^k-1)/3. That is, 0 1 2 5 10 21, 42, 85, 170, ..., which is A000975 in the OEIS.

Answer 1

Pyth, 17 16 bytes

1 byte thanks to Jakube

iR2cJ.BQx1qVJ+dJ

Demonstration

A nice, clever solution. Uses some lesser known features of Pyth, like x<int><list> and c<str><list>.

iR2cJ.BQx1qVJ+dJ
                    Q = eval(input())
    J.BQ            Store in J the input in binary.
          qV        Vectorize equality function over
            J+dJ    J and J with a leading dummy char, to get the offset right.
                    This calculates whether each element matches its successor.
        x1          Find all of the indexes of 1 (True) in this list.
   cJ                Chop J at those locations.
iR2                  Convert from binary back to base ten and output.

Answer 2

Mathematica, 47 bytes

#+##&~Fold~#&/@#~IntegerDigits~2~Split~Unequal&

Ungolfed:

FromDigits[#,2]&/@Split[IntegerDigits[#,2],Unequal]&

Split[list,f] splits a list into multiple lists, breaking at the position between a and b iff f[a,b] does not return True.

FromDigits[n,2] => Fold[#+##&,n] is a neat tip from alephalpha.

Answer 3

Python, 86 bytes

Since I got horribly outgolfed in Pyth, lets just do it in Python again.

import re
lambda n:[int(s,2)for s in re.sub("(?<=(.))(?=\\1)"," ",bin(n)[2:]).split()]

Try it here!

Explanation

We start with converting the input number n into a binary string. bin(n)[2:] takes care of that. We need to discard the first 2 chars of this string since bin() returns the string in the format 0b10101.
Next we need to identify the borders of the subsequences. This can be done with the regex (?<=(.))(?=\1) which matches the zero-length positions in the string which have the same number to the left and right.
The obvious way to get a list of all subsequences would be to use re.split() which splits a string on a certain regex. Unfortunately this function does not work for zero-length matches. But luckily re.sub() does, so we just replace those zero-length matches with spaces and split the string on those after that.
Then we just have to parse each of those subsequences back into a decimal number with int(s,2) and are done.

Answer 4

Jelly, 12 bytes

BI¬-ẋż@BFṣ-Ḅ

Try it online! or verify all test cases.

How it works

BI¬-ẋż@BFṣ-Ḅ  Main link. Argument: n

B             Convert n to base 2.
 I            Compute the increments, i.e., the differences of consecutive digits.
  ¬           Apply logical NOT.
   -ẋ         Repeat -1 that many times, for the logical NOT of each difference.
              [0, 0] / [1, 1] ->   0    -> 1 -> [-1]
              [0, 1] / [1, 0] -> 1 / -1 -> 0 -> []
       B      Yield n in base 2.
     ż@       Zip the result to the right with the result to the left.
        F     Flatten the resulting list of pairs.
         ṣ-   Split at occurrences of -1.
           Ḅ  Convert each chunk from base 2 to integer.

Answer 5

Bash + GNU utilities, 51

dc -e2o?p|sed -r ':;s/(.)\1/\1 \1/;t'|dc -e2i?f|tac

Input taken from STDIN.

• dc -e2o?p reads input integer from STDIN and outputs a base 2 string
• sed -r ':;s/(.)\1/\1 \1/;t' splits the base 2 string with a space everywhere there are same consecutive digits
• dc -e2i?f reads the split binary in one go, putting the each part on the stack, then f dumps the whole dc stack (output numbers in reverse order) ...
• ... which is corrected by tac.

Answer 6

JavaScript (ES6) 58 62 63

Edit 1 byte saved thx @ETHproductions

Edit 4 bytes saved thx @Neil

x=>x.toString(2).replace(/((.)(?!\2))*./g,x=>'0b'+x-0+' ')

f=x=>x.toString(2).replace(/((.)(?!\2))*./g,x=>'0b'+x-0+' ')

 
console.log=x=>O.textContent+=x+'\n'

;[
[     0,'0'],
[     1,'1'],
[     2,'2'],
[     3,'1 1'],
[     4,'2 0'],
[     5,'5'],
[     6,'1 2'],
[     7,'1 1 1'],
[     8,'2 0 0'],
[     9,'2 1'],
[    10,'10'],
[    50,'1 2 2'],
[   100,'1 2 2 0'],
[  1000,'1 1 1 1 10 0 0'],
[ 10000,'2 1 1 2 0 2 0 0 0'],
[ 12914,'1 2 2 1 1 2 2'],
[371017,'5 42 10 2 1']
].forEach(t=>{
  var i=t[0],k=t[1],r=f(i)
  console.log(i+' -> '+r+(r.trim()==k.trim() ? ' ok':'ko (should be '+k+')'))
})

<pre id=O></pre>

Answer 7

Pyth, 26 bytes

iR2c:.BQ"(?<=(.))(?=\\1)"d

Try it here!

Explanation

iR2c:.BQ"(?<=(.))(?=\\1)"d   # Q = input number

     .BQ                     # Convert input to binary
    :   "(?<=(.))(?=\\1)"d   # insert a whitespace between the subsequences
   c                         # split string on whitespaces
iR2                          # convert each subsequence into decimal

Since Python's split() function doesn't split on zero-length matches, I have to replace those matches with a space and split the result on that.

Answer 8

Pyth, 22 21 bytes

&Qu?q%G2H&
GH+yGHjQ2Z

Try it online: Demonstration

Really a tedious task in Pyth.

Explanation:

&Qu?q%G2H&\nGH+yGHjQ2Z   implicit: Q = input number
                  jQ2    convert Q to base 2
  u               jQ2Z   reduce ^: for each digit H update the variable G=0:
   ?q%G2H                   if G%2 == H:
          \nG                  print G
         &   H                 then update G with H
              +yGH           else: update G with 2*G+H
  u                      print the last G also
&Q                       handle Q=0 special: only print 0 once

Answer 9

05AB1E, 18 bytes

Code:

b2FNð«N«Dð-s:}ð¡)C

Explanation:

b                   # Convert input to binary
 2F          }      # Do the following twice ( with N as range variable)
   Nð«N«            #    N + space + N
        D           #    Duplicate this
         ð-         #    Delete spaces from the duplicate string
           s        #    Swap the top two elements
            :       #    Replace the first string with the second
              ð¡    # Split on spaces
                )   # Wrap into an array
                 C  # Convert all element back to decimal
        

Try it online!

Uses CP-1252 encoding.

Answer 10

MATL, 18 17 bytes

YBTyd~Thhfd1wY{ZB

Try it online!

YB      % input number. Convert to binary string
T       % push true value
y       % duplicate binary string and push it at the top of the stack
d~      % true for each value that equals the previous one
T       % push true value
hh      % concatenate: true, indices, true
f       % find indices of true values
d       % consecutive differences: lenghts of alternating sequences
1wY{    % split binary string according to those lengths
ZB      % convert each substring into decimal number

Answer 11

zsh, 67 63 55 bytes

for i in `grep -oP '1?(01)*0?'<<<$[[##2]$1]`;<<<$[2#$i]

I don't know why, but this doesn't work in Bash.

Thanks to Dennis for 8 bytes!

Answer 12

PHP, 171 168 162 160 158 121 120 131 124 118 116 113 112 bytes

function d($i){for(;$d<$l=strlen($b=decbin($i));){$c.=$u=$b[$d];echo$u==$b[++$d]||$d==$l?bindec($c).$c=" ":"";}}

Exploded view

function d($i) {
  for ( ; $d < $l = strlen($b = decbin($i)); ) {
    $c .= $u = $b[$d];
    echo $u == $b[++$d] || $d == $l ? bindec($c) . $c = " "
                                    : "";
  }
}

Use d(int) and you're off, output is an echoed string of ints separated by a space.

Edits:
-3: Moved $b definition into strlen() call.
-6: Removed $c instantiation.
-2: Finally fixed the concatenation issue.
-2: No brackets for single-line for().
-37: Total overhaul. Going with Array chunklets instead of repeated Array->String->Array calls.
-1: Sneaky $c reset.
+11: Bugfix. Was missing final chunk. No more.
-7: Don't need to instantiate $d at all? Nice.
-6: return->echo.
-2: Crunching $c.
-3: Ternary, my first love.
-1: Sneaky sneaky $u.

Answer 13

Convex 0.2+, 25 bytes

Convex is a new language that I am developing that is heavily based on CJam and Golfscript. The interpreter and IDE can be found here. Input is an integer into the command line arguments. This uses the CP-1252 encoding.

2bs®(?<=(.))(?=\\1)"ö2fbp

Explanation:

2bs                         Convert to binary string
   ®(?<=(.))(?=\\1)"        Regex literal
                    ö       Split string on regex
                     2fb    Convert each split string into decimal integer
                        p   Print resulting array

Answer 14

Java 8, 127 119 bytes

l->new java.util.ArrayList<Long>(){{for(String s:l.toBinaryString(l).split("(?<=(.))(?=\\1)"))add(l.parseLong(s,2));}};

There's probably a better regular expression out there to split the string on. I'm not proficient at regex, but I'll keep experimenting.

-8 bytes thanks to @FryAmTheEggman

Answer 15

APL (APL), 21 25 bytes

Now handles 0 as well.

{0::0⋄2⊥¨⍵⊂⍨1,2=/⍵}2⊥⍣¯1⊢

Try it online!

2⊥⍣¯1⊢ convert to base-2, using as many bits as needed (lit. inverse from-base-2 conversion)

{…} apply the following anonymous function

0:: if any error happens:

  0 return 0

 ⋄ now try:

  2=/⍵ pairwise equality of the argument (will fail one 0's length-0 binary representation)

  1, prepend 1

  ⍵⊂⍨ use that to partition the argument (begins new section on each 1)

  2⊥¨ convert each from base-2

Answer 16

Japt, 7 bytes

¤ò¥ mn2

Test it

---

Explanation

¤ò¥ mn2
           :Implicit input of integer U.
¤          :Convert to binary string.
 ò¥        :Split to an array by checking for equality.
    m      :Map over array.
     n2    :Convert to base-10 integer.

Answer 17

Python 3, 115 bytes

def f(s):
 s=bin(s);r=[s[2]]
 for i in s[3:]:
  if i==r[-1][-1]:r+=[i]
  else:r[-1]+=i
 return[int(x,2)for x in r]

Explanation

def f(s):
 s=bin(s)                   # convert input in binary
 r=[s[2]]                   # initialize the result with the first char after the 'b' in binary string
 for i in s[3:]:            # loop on other element
  if i==r[-1][-1]:          # if the last element of the last string equal the current element 
   r+=[i]                   # we add the current element in a new string
  else:
   r[-1]+=i                 # we add the current element to the last sting
 return[int(x,2)for x in r] # convert binary string in integer 

Results

>>> [print(i,f(i)) for i in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 50, 100, 1000, 10000, 12914, 371017]]
0 [0]
1 [1]
2 [2]
3 [1, 1]
4 [2, 0]
5 [5]
6 [1, 2]
7 [1, 1, 1]
8 [2, 0, 0]
9 [2, 1]
10 [10]
50 [1, 2, 2]
100 [1, 2, 2, 0]
1000 [1, 1, 1, 1, 10, 0, 0]
10000 [2, 1, 1, 2, 0, 2, 0, 0, 0]
12914 [1, 2, 2, 1, 1, 2, 2]
371017 [5, 42, 10, 2, 1]

previous solution (118 bytes)

def f(s):
 s=bin(s);r=s[2]
 for i in s[3:]:
  if i==r[-1]:r+='a'+i
  else:r+=i
 return[int(x,2)for x in r.split('a')]

Answer 18

Haskell, 147, 145 bytes

x%[]=[x]
x%(y:z)|or.(zipWith(==)<*>tail)$y:x=x:[]%(y:z)|1<2=(y:x)%z
b x|x<2=[x]|1<2=b(div x 2)++[mod x 2]
map(sum.zipWith((*).(2^))[0..]).([]%).b

map(sum.zipWith((*).(2^))[0..]).([]%).b is an unnamed function that computes the list.

Less golfed:

alternating :: Eq a => [a] -> Bool
alternating = or . (zipWith (==) <*> tail)

-- (%) is the partitioning function
(%) :: Eq a => [a] -> [a] -> [[a]]
x % [] = [x]

x % (y:z) | alternating (y : x) = x : [] % (y:z)
          | otherwise = (y : x) % z

bits :: Integral t => t -> [t]
bits x | x < 2     = [x] 
       | otherwise = bits (div x 2) ++ [mod x 2]

unBits :: Num c => [c] -> c
unBits = sum . zipWith ((*) . (2^)) [0..]

f :: Integer -> [Integer]
f = map unBits . ([]%) . bits

Answer 19

Perl, 53 bytes

Includes +1 for -p

Run with the number on STDIN

perl -p alterbits.pl <<< 371017

alterbits.pl:

$_=sprintf"0b%b",$_;s/(.)\K(?=\1)/ 0b/g;s/\S+/$&/eeg

Answer 20

PowerShell, 103 bytes

[regex]::Matches([convert]::ToString($args[0],2),"(01)+0?|(10)+1?|.").Value|%{[convert]::toint32($_,2)}

Since I'm horrible at regex, I'm using the same expression as edc65's answer.

Absolutely destroyed by the lengthy .NET calls to do conversion to/from binary, and the .NET call to get the regex matches. Otherwise pretty straightforward. Takes the input $args[0], converts it to binary, feeds it into Matches, takes the resultant .Values, pipes them through a loop |%{...} and converts those values back to int. Output is left on the pipeline and implicitly printed with newlines.

---

For extra credit - a (mostly) non-regex version at 126 bytes

$l,$r=[char[]][convert]::ToString($args[0],2);$l+-join($r|%{(" $_",$_)[$l-bxor$_];$l=$_})-split' '|%{[convert]::toint32($_,2)}

We again take input $args[0] and convert it to binary. We re-cast as a char-array, storing the first character in $l and the remaining characters in $r. We then send $r through a loop |%{...} where every iteration we select from either the character prepended with a space or just the character, depending upon the result of a binary xor with $l, and then set $l equal to the character. This effectively ensures that if we have the same character twice in a row, we prepend a space between them.

The output of the loop is -joined together and appended to the first character $l, then -split on spaces (which is technically a regex, but I'm not going to count it). We then do the same loop as the regex answer to convert and output integers.

Answer 21

Java 345 bytes

package com.ji.golf;
import java.util.regex.*;
public class Decompose {
  public static String decompose(long l) {
    String o="";
    String s=Long.toBinaryString(l);
    Matcher m=Pattern.compile("(01)+(0)?|(10)+(1)?|(1)|(0)").matcher(s);
    while(m.find()){String c=s.substring(m.start(),m.end());o+=Integer.parseInt(c, 2)+" ";}
    return o;
  }
}

Test

package com.ji.golf;
public class DecompseTest {
  public static void main(String[] args) {
    String[] inOut = new String[]{
        "0,0",
        "1,1",
        "2,2",
        "3,1 1",
        "4,2 0",
        "5,5",
        "6,1 2",
        "7,1 1 1",
        "8,2 0 0",
        "9,2 1",
        "10,10",
        "50,1 2 2",
        "100,1 2 2 0",
        "1000,1 1 1 1 10 0 0",
        "10000,2 1 1 2 0 2 0 0 0",
        "12914,1 2 2 1 1 2 2",
        "371017,5 42 10 2 1"
    };
    for (String s : inOut) {
      String[] io = s.split(",");
      String result = Decompose.decompose(Long.parseLong(io[0]));
      System.out.println("in: " + io[0] + ", reusult: [" +  result.trim() + "], validates? " + result.trim().equals(io[1].trim()));
    }
  }
}

Output

in: 0, reusult: [0], validates? true
in: 1, reusult: [1], validates? true
in: 2, reusult: [2], validates? true
in: 3, reusult: [1 1], validates? true
in: 4, reusult: [2 0], validates? true
in: 5, reusult: [5], validates? true
in: 6, reusult: [1 2], validates? true
in: 7, reusult: [1 1 1], validates? true
in: 8, reusult: [2 0 0], validates? true
in: 9, reusult: [2 1], validates? true
in: 10, reusult: [10], validates? true
in: 50, reusult: [1 2 2], validates? true
in: 100, reusult: [1 2 2 0], validates? true
in: 1000, reusult: [1 1 1 1 10 0 0], validates? true
in: 10000, reusult: [2 1 1 2 0 2 0 0 0], validates? true
in: 12914, reusult: [1 2 2 1 1 2 2], validates? true
in: 371017, reusult: [5 42 10 2 1], validates? true

Answer 22

Julia, 70 57 bytes

n->map(i->parse(Int,i,2),split(bin(n),r"(?<=(.))(?=\1)"))

This is an anonymous function that accepts an integer and returns an integer array. To call it, assign it to a variable.

The approach here is similar to DenkerAffe's nice Python answer. We get the binary representation of n using bin(n), and split the resulting string at all matches of the regular expression (?<=(.))(?=\1). It's actually a zero-length match; (?<=(.)) is a positive lookbehind that finds any single character, and (?=\1) is a positive lookahead that finds the matched character in the lookbehind. This locates the places where a number is followed by itself in the binary representation. Just parse each as an integer in base 2 using map and voila!

Answer 23

C, 137 129 bytes

main(){unsigned long a,b=scanf("%lu",&a),c=!!a;while(a>=b*2)b*=2;while(b)b/=2,c=c*(~(a^a/2)&b|!b?!printf("%lu\n",c):2)+!!(a&b);}

Input and output are on the standard streams.

Answer 24

J, 16 bytes

#:#.;.1~1,2=/\#:

Try it online!

Explanation

#:#.;.1~1,2=/\#:  Input: integer n
              #:  Convert from decimal to list of binary digits
          2  \    For each overlapping sublist of size 2
           =/       Reduce using equals
        1,        Prepend 1
#:                Binary digits
    ;.1~          Partition those binary digits at the 1s in the previous list
  #.                Convert each partition from a list of binary digits to decimal

Answer 25

q/kdb+, 52 bytes

Solution:

{2 sv'cut[0,(&)(~)differ a]a:(63^(*)(&)a)_a:0b vs x}

Examples:

q){2 sv'cut[0,(&)(~)differ a]a:(63^(*)(&)a)_a:0b vs x}0
,0
q){2 sv'cut[0,(&)(~)differ a]a:(63^(*)(&)a)_a:0b vs x}1
,1
q){2 sv'cut[0,(&)(~)differ a]a:(63^(*)(&)a)_a:0b vs x}3
1 1
q){2 sv'cut[0,(&)(~)differ a]a:(63^(*)(&)a)_a:0b vs x}8
2 0 0
q){2 sv'cut[0,(&)(~)differ a]a:(63^(*)(&)a)_a:0b vs x}10000
2 1 1 2 0 2 0 0 0
q){2 sv'cut[0,(&)(~)differ a]a:(63^(*)(&)a)_a:0b vs x}12914
1 2 2 1 1 2 2
q){2 sv'cut[0,(&)(~)differ a]a:(63^(*)(&)a)_a:0b vs x}371017
5 42 10 2 1
q){2 sv'cut[0,(&)(~)differ a]a:(63^(*)(&)a)_a:0b vs x}727429805944311
10 21 2 5 1 1 1 1 1 2 1 2 5 1 85 5 1 1 1 5 1 1

Explanation:

q is interpreted right-to-left.

Cast input to binary, trim off leading zeros, find indices where different, invert to get indices where the same, split list on these indices, convert back to base-10. Looks a little heavy compared to the APL solution though...

{2 sv'cut[0,where not differ a]a:(63^first where a)_a:0b vs x} / ungolfed solution
{                                                            } / lambda function
      cut[                    ]                                / cut a list at indices, cut[indices]list
                                                      0b vs x  / converts to 64bit binary representation
                                                    a:         / save as a
                                                   _           / drop 'n' elements from a
                                 (                )            / evaluate this
                                     first where a             / returns first occurance of true in list a
                                  63^                          / fill result with 63 if null (to handle input of 0)
                               a:                              / save as a, we've stripped off all the left-most 0s
                      differ a                                 / whether or not item in list a is different to previous
                  not                                          / the inversion of this result
            where                                              / these are the points where we have 00 or 11
          0,                                                   / add the first index too!
  2 sv'                                                        / 2 sv converts binary back to base-10, ' for each list

Answer 26

PHP, 98 bytes

function($x){foreach(str_split(decbin($x))as$c)$o[$p+=$c==$d].=$d=$c;return array_map(bindec,$o);}

Try it online!

Answer 27

Husk, 5 bytes

mḋġ≠ḋ

Try it online!

Answer 28

Jelly, 9 bytes

BI¬0;œṗBḄ

Try it online!

Answer 29

Ruby, 49 48 bytes

-1 byte thanks to Sʨɠɠan

Uses the regexp from edc65’s JavaScript answer.

->n{("%b"%n).scan(/((.)(?!\2))*./){p $&.to_i 2}}

Attempt This Online!

Answer 30

PHP, 147

$b=decbin($argv[1]);$a=[$t=$b[0]];$k=0;for($i=1;$i<strlen($b);$i++){$v=$b[$i];if($v==$t)$k++;$t=$v;$a[$k].=$v;}foreach($a as$c)echo bindec($c).' ';

Need to put extra space at last of output as their are no restriction. Notices are displayed for short coding.

Ungolfed version

$n=$argv[1];
$b=decbin($n);
$l=strlen($b);
$t=$b[0];
$a=[0=>$t];$k=0;
for($i=1;$i<$l;$i++){
    $v=$b[$i];
    if($v==$t){
        $k++;
    }
    $t=$v;$a[$k].=$v;    
}
foreach($a as $c){
    echo bindec($c).' ';
}