# Elias omega coding: decoding

Related: Elias omega coding: encoding

## Background

Elias omega coding is a universal code which can encode positive integers of any size into a stream of bits.

Given a stream of bits $$\S\$$, the decoding algorithm is as follows:

1. If $$\S\$$ is empty, stop. Otherwise, let $$\N=1\$$.
2. Read the next bit $$\b\$$ of $$\S\$$.
3. If $$\b=0\$$, output $$\N\$$ and return to step 1.
4. Otherwise, $$\b=1\$$. Read $$\N\$$ more bits from $$\S\$$, append to $$\b\$$, and convert it from binary to integer. This is the new value of $$\N\$$. Go back to step 2.

In Python-like pseudocode:

s = input()
while s.has_next():
n = 1
while (b = s.next()) == 1:
loop n times:
b = b * 2 + s.next()
n = b
output(n)


## Illustration

If the given bit stream is 101001010100:

1. Initially $$\N = 1\$$.
2. Since the first bit is 1, we read 1 more bit (2 bits in total) to get the new value of $$\N = 10_2 = 2\$$. Now the stream is 1001010100.
3. Proceed as the same. Read a bit (1) and $$\N = 2\$$ more bits to get $$\N = 100_2 = 4\$$. Stream: 1010100
4. Read a bit (1) and $$\N = 4\$$ more bits to get $$\N = 10101_2 = 21\$$. Stream: 00
5. Read a bit (0). Since it is 0, output the current $$\N = 21\$$. The stream has more bits to be consumed, so we reset to $$\N=1\$$ and continue. Stream: 0
6. Read a bit (0). Output the current $$\N = 1\$$. The stream is empty, and decoding is complete.

The output for the input stream 101001010100 is [21, 1].

## Task

Given a stream of bits which consists of zero or more Elias omega coded integers, decode into the original list of integers. You can assume the input is valid (the input stream won't be exhausted in the middle of decoding a number).

Shortest code in bytes wins.

## Test cases

Input => Output
(empty) => []
0       => 
00      => [1,1]
00100   => [1,1,2]
101001010100 => [21,1]
1110000111100001110000 => [8,12,1,8]
1111000111000101011001011110011010100001010 => [12,345,6789]


# convey, 66 bytes

1<<<<,<<
/>>>v$1^ ,<"<##<^ :#?@#^^ {1$v>"}%2
~,>/+?<
3 0$,>*2  Try it online! Explanation will follow after I tried some other orientations … # Charcoal, 32 bytes ≔⪪⮌Ｓ¹θ⊞υ¹Ｗθ⊞υ∨⁼0⊟θ⍘⁺1⭆⊟υ⊟θ²Ｉ∧⊟υυ  Try it online! Link is to verbose version of code. Explanation: ≔⪪⮌Ｓ¹θ  Input the bits and split them into single characters. ⊞υ¹  Start with N=1. Ｗθ  Repeat until the bits are exhausted. ⊞υ∨⁼0⊟θ⍘⁺1⭆⊟υ⊟θ²  If the next bit is a 0 then push a 1 otherwise pop the current value to see how many more bits to extract and convert to base 2 and push that instead. Ｉ∧⊟υυ  Print all of the numbers except the last one (which should be a 1 we pushed when we hit the last 0). # R, 10898 95 bytes function(x)while(length(x)){n=1 while({b=x[0:n+1];x=x[0:(-n*b)-1];b})n=sum(b*2^(n:0)) print(n)}  Try it online! This could still be shortened by 3 more bytes (like this) by modifying sum(b*2^(n:0)) to instead use the inner product operator b%*%2^(n:0), but this gives rather unsatisfying output that mixes 1-element vectors with 1x1 matrices... # JavaScript (ES6), 57 bytes 4 bytes saved by @tsh Expects a list of 0's and 1's. a=>a.map(b=>r=a--?r*2+b:(a=b?r:!o.push(r),1),r=1,o=[])&&o  Try it online! # JavaScript (ES6), 61 bytes Expects a list of 0's and 1's. a=>a.map(b=>r=n--?r|b<<n:1<<(n=b?r:!o.push(r)),r=1,n=o=[])&&o  Try it online! ### Commented a => // a[] = array of bits a.map(b => // for each bit b in a[]: r = // update r: n-- ? // if n is not equal to 0 (decrement it afterwards): r | b << n // set the n-th bit of r to b : // else: 1 << ( // this expression evaluates to either 1 << r or 1 n = // update n: b ? // if b is set: r // set n to r and set r to 1 << r : // else: !o.push(r) // push r into o[], set n to 0 and set r to 1 ), // // start with: r = 1, // r = 1, n = // n zero'ish o = [] // o[] = empty array ) // end of map() && o // return o[]  • 59 bytes without n: a=>a.map(b=>r=a--?r|b<<a:1<<(a=b?r:!o.push(r)),r=1,o=[])&&o And it could be 49 bytes in browser a=>a.map(b=>r=a--?r|b<<a:1<<(a=b?r:alert(r)),r=1) – tsh Feb 22 at 2:29 • 57 bytes without bitwise operator a=>a.map(b=>r=a--?r*2+b:(a=b?r:!o.push(r),1),r=1,o=[])&&o – tsh Feb 22 at 2:35 • @tsh Very nice! – Arnauld Feb 22 at 2:51 # Stax, 17 bytes àkÑ╣±╫¬ò^Ü▌}├n╒/ñ  Run and debug it Input as an array of bits. An almost direct translation of the reference implementation. ## Explanation W|cO{B|csa%aa+:bsWsP W|c while S is truthy: O push a 1 under it (N) { W loop forever stack: [N,S] B pop first bit from S and push it stack: [N,S,b] |c break if it's falsy s swap a% split the list at index N aa+ prepend b to the first part :b convert from binary s swap for the next iteration sP print N after the loop ends  # PowerShell, 78 bytes for($s=$args;""+$s[+$x]){for($n=1;$b=$s[$x++]){1..$n|%{$n=$b+=$b+$s[$x++]}}$n}


Try it online!

# Retina 0.8.2, 82 bytes

^
_¶
{¶0(.*)$¶_¶$1
(_)+¶(1(?<-1>.)+)(.*)2¶$3 1(?=.*¶) 0_ }+_0 0__ %M_ 1¶0$



Try it online! Link includes test cases. Explanation:

^
_¶


Set N=1 (in unary).

{
}


Repeat until the bits are exhausted.

¶0(.*)$¶_¶$1


If the next bit is a 0 then start a new output value of 1.

(_)+¶(1(?<-1>.)+)(.*)2¶$3  But if the next bit is a 1 then extract the next N bits. 1(?=.*¶) 0_ _0 0__  Convert them from binary to unary. (There are 0s left over, but we don't care about them.) %M_  Convert all of the output values from unary to decimal. 1¶0$



Remove the last two values; the 1 is from the 1 that begins the new output value, while the 0 is from the (now empty) input. (This has to be done here so that the case of an empty input works.)

# Racket, 146 bytes

(define(f s[n 1][a'()])(if(null? s)(reverse a)(if(=(car s)0)(f(cdr s)1(cons
n a))(f(drop s(+ n 1))(foldl(λ(a b)(+(* 2 b)a))0(take s(+ n 1)))a))))


Try it online!

1while s/^0//?$\=say$\:s/^1.{$\}//?$\=oct"0b$&":0  Try it online! # PowerShell, 7573 70 bytes Finite-state machine, where $b is a current state {0, 1, other}.

Inspired by Zaelin Goodman

$args|%{if(!($b=2*$b+"$_")){$n+1;$n=1}if($b-1-and!$n--){$n=$b-1;\$b=0}}


Try it online!

# Wolfram Language (Mathematica), 62 bytes

Last@Reap@Fold[If[--n<1,n=1+If[#2<1,0Sow@#,#];1,##+#]&,n=1,#]&
`

Try it online!