# Decompose binary into alternating subsequences

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
``````

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.

-
@DigitalTrauma: Hmmm......no, I don't think that's within the spirit of the challenge. – El'endia Starman Mar 12 at 4:32
Ok. `|tac` will remain in my answer then :) – Digital Trauma Mar 13 at 22:43

# 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.
``````
-
If you replace `tJ` by `+dJ` you can remove `hM`. – Jakube Mar 11 at 8:16
@Jakube Nice one! – isaacg Mar 11 at 8:17

# 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.

-

# 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.

-

# 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>``

-
Could you save two bytes with the regex `/(01)*0?|(10)*1?/g`, or would that mess something up?? – ETHproductions Mar 11 at 14:59
Also, I think you could do `x=>'0b'+x-0+' '` to save a byte. – ETHproductions Mar 11 at 15:00
@ETHproductions I tried the shorter regexp, no good :(. Thx for the other hint – edc65 Mar 11 at 15:34
The Leadboard says you have a 1 byte answer. I assume it's because you have the corrected number (62) before the old number (63) instead of after. – Kyle Kanos Mar 12 at 17:33
I think the regex `/((.)(?!\2))*./g` saves you a cool 4 bytes. – Neil Mar 12 at 18:56

# 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`.
-

# 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.

-

# 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
``````
-

# Jelly, 12 bytes

``````BI¬-ẋż@BFṣ-Ḅ
``````

### 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.
``````
-
Surely 12 characters but 20 bytes. Or are you using a system with CHAR_BIT >> 8? – James Youngman Mar 12 at 14:17
@JamesYoungman Jelly doesn't use UTF-8 by default. In fact, it has its own code page that encodes each of the 256 characters it understands as a single byte each. – Dennis Mar 12 at 14:22

# 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.

-

# 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
``````
-

## zsh, 6763 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!

-
It's the `for` syntax. ...Wait, no `for`s? – CalculatorFeline Mar 11 at 14:40
Bash's arithmetic expansion doesn't let you specify an output base. To get rid of the xargs, you could use `for i in `grep -oP '1?(01)*0?'<<<\$[[##2]\$1]`;<<<\$[2#\$i]`. – Dennis Mar 11 at 17:33

## PHP, 171168162160158121120131124118116113 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 `echo`ed string of `int`s 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`.

-
I think you can save 2 bytes: `function d(\$i){for(;\$d<\$l=strlen(\$b=decbin(\$i));print\$u==\$b[++\$d]||\$d==\$l?bindec(\$c).\$c=" ":"")\$c.=\$u=\$b[\$d];}`. – Blackhole Mar 13 at 17:11

## 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
``````
-

# 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

-

# Dyalog APL, 21 bytes

``````2⊥¨{⍵⊂⍨1,2=/⍵}2⊥⍣¯1⊢⎕
``````
-
`⊂` is really useful here. I should add that to Jelly. – Dennis Mar 11 at 18:36
@Dennis Be aware of the two versions of `R←X⊂Y`: With `⎕ML<3` (i.e. Dyalog style), a new partition is started in the result corresponding to each 1 in X up to the position before the next 1 in X (or the last element of X) become the successive items of R. With `⎕ML=3` (i.e. IBM style), a new partition is started in the result whenever the corresponding element in X is greater than the previous one. Items in Y corresponding to 0s in X are not included in the result. So `⎕ML←1 ⋄ 1 0 0 1 0 1 1 ⊂ ⍳7` is equivalent to `⎕ML←3` ⋄ 4 3 2 4 4 5 7 ⊂ ⍳7` – Adám Mar 14 at 12:03

## 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')]
``````
-

``````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
``````
-

# 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
``````
-

## 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]`, `convert`s it to binary, feeds it into `Matches`, takes the resultant `.Value`s, pipes them through a loop `|%{...}` and `convert`s 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 `-join`ed 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.

-

# 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
``````
-
Welcome to Programming Puzzles & Code Golf! Since this is a code-golf competition, you should make your code as short as possible. Here are some tips for golfing in Java. You can start by defining your function without the boilerplate `package` and `class`, and removing unnecessary whitespace. Let me know if you have any questions! – Alex A. Mar 11 at 20:41

# 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!

-

# 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.

-
I don't think you need the `puts`, even though it would be unpleasant to use, the spec doesn't require a trailing newline. – FryAmTheEggman Mar 15 at 17:13
@FryAmTheEggman I'd rather not generate an incomplete last line. But for the cost of one byte (still a net reduction) I can change the separator from space to newline. – Fox Mar 15 at 19:19

# 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).' ';
}
``````
-

# Retina, 60

``````+`(1+)\1
\$1a
a1
1
(?<=(.))(?=\1)
¶
+`1(a*)\b
a\$.1\$*1;
a

;
1
``````

Try it online! Or try a slightly modified version for all test cases (with decimal I/O).

Unfortunately, zero length matches seem to have two "sides", causing duplication when used with the regex from the third stage. Only costs one byte though.

Takes input as unary, outputs as unary. Not really sure about using different in/out unary values, but that would save 4 bytes.

-