Elias omega coding: decoding

Question

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       => [1]
00      => [1,1]
00100   => [1,1,2]
101001010100 => [21,1]
1110000111100001110000 => [8,12,1,8]
1111000111000101011001011110011010100001010 => [12,345,6789]

Answer 1

convey, 66 bytes

1<<<<,<<
/>>>v$1^
,<"<##<^
:`#?@#^^
{1$v>"}%2
  ~,>/+?<
  3 0$,>*2

Try it online!

Explanation will follow after I tried some other orientations …

Answer 2

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

Answer 3

R, 108 98 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...

Answer 4

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[]

Answer 5

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

Answer 6

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!

Answer 7

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

Answer 8

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!

Answer 9

Perl 5 (-l061n), 49 bytes

1while s/^0//?$\=say$\:s/^1.{$\}//?$\=oct"0b$&":0

Try it online!

Answer 10

PowerShell, 75 73 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!

Answer 11

Wolfram Language (Mathematica), 62 bytes

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

Try it online!