Split me in half

Question

You will be given a number x, where 0 <= x <= 2^32 - 1.

You should output a list of numbers in decimal, after recursive splitting in binary format.

Examples:

Example 1:

255 -> 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1

The current list is just 255.

The binary representation of 255 is 1111 1111. Splitting it, we get 1111 and 1111, which in decimal are 15 and 15.

We add those to the list, so we will have 255 15 15.

Now the numbers 15 and 15 will serve as inputs and these numbers are to be split.

Doing it again, we get (3 3 from both 15s): 255 15 15 3 3 3 3.

Continuing the logic, final list will be 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1. And since 1 can no longer be split, the output stops.

Example 2:

225 -> 225 14 1 3 2 1 1 1 0

The starting list is 225.

The binary representation of 225 is 1110 0001. Splitting it, we get 1110 and 0001, which in decimal are 14 and 1.

Adding those to the list, we get 225 14 1.

Now the numbers 14 and 1 will serve as inputs and these numbers are to be split.

Since 1 is no splittable, the output will be 225 14 1 3 2.

Example 3:

32 -> 32 4 0 1 0

Conditions:

1. If the number of binary digits are odd, the first number will have one fewer binary digit than the next one. Example, 20 (10100) will be split as 10 and 100, with decimal output being 2 and 4.
2. Standard loophole rules apply.
3. 0s and 1s do not propagate further.
4. Program crashing for trying to display too many numbers is a valid exit condition.

Answer 1

Pyth, 18 bytes

u+QiR2smc2+0dt#.BM

Test suite

This code does something very tricky and clever with u, Pyth's fixed point operator.

The body of the function, which is everything other than the u, is fairly straightforward:

+QiR2smc2+0dt#.BM
+QiR2smc2+0dt#.BMG    Implicit variable
                      G will store the list of numbers from the previous iteration.
              .BMG    Map each number to its binary representation
            t#        Filter out the ones of length 1 (0 and 1)
      m               Map the remaining binary
         +0d          Prefix with a 0
       c2             Chop in half.
                      Since c puts the larger half first, prefixing with a 0
                      makes the chop work out right, and doesn't change the value.
     s                Concatenate
  iR2                 Map back to binary
+Q                    Add the input to the front of the list

This code removes 0s and 1s, splits every number, and adds the input in front.

u will run this function on the prior result of the function until the result stops changing.

What initial value does u use? That's the clever part: the code doesn't specify what value to use, so it defaults to the input. But the input isn't a list of numbers - it's a number. Pyth implicitly coerces the number on the fist time through the loop to the range of the number - [0, 1, ..., Q-1]. That doesn't look anything like the output we want to get. Fortunately, u will find the correct result regardless of what the initial input is - the desired output is the only fixed point of the function, and repeated application will always reach it.

Let's look at the intermediate values of the program with the input 7. I've highlighted the prefix of the result which is guaranteed to be correct, regardless of initial input:

1. 7 (Implicitly [0, 1, 2, 3, 4, 5, 6])

2. [7,1, 0, 1, 1, 1, 0, 1, 1, 1, 2]

3. [7, 1, 3,1, 0]

4. [7, 1, 3, 1, 1]

Which is the output.

---

Packed Pyth, 16 bytes

Note that since Pyth uses only the 0-127 range of ASCII, it can be compressed by using a 7-bit encoding rather than an 8 bit encoding. Thus, the above program can be packed into 16 bytes. The resulting program is:

ꮎ�L����[
    ���4

hexdump:

0000000: eaae 8e9a 4cb9 edc6 c95b 0c9d 11ae 8534  ....L....[.....4

The interpreter is found here. Provide the input as a command line argument.

The code page of this language (Packed Pyth) is the 0-127 range of ASCII, and every character is represented with 7 bits, padded at the end. Thus, the above unreadable hexdump represents:

u+QiR2smc2+0dt#.BM

But in 16 bytes.

Answer 2

05AB1E, 21 20 18 17 bytes

,¸[Žrbvy0ì2äCʒ=1›

Try it online!

Explanation

,¸[Žrbvy0ì2äCʒ=1›   Argument n
,¸                  Print n and push n as array
  [Ž                Loop until stack is empty
    r               Reverse stack
     b              Convert elements in array to binary
      v             For each y in array
       y0ì2ä        Prepend '0' to y and split it into 2 elements
                    (the first element will take the additional character)
            C       Convert elements to decimal
             ʒ=1›   Keep only elements greater than 1, while printing each element

Answer 3

Jelly, 21 20 bytes

-1 byte by removing a monadic chain and then dealing with the consequence of an empty list being converted from binary yielding 0 later.

ỊÐḟBUœs€2UḄF
WÇÐĿṖUF

A monadic link taking a number and returning the list specified.

Try it online!

How?

ỊÐḟBUœs€2UḄF - Link 1, perform an iteration: list of numbers
 Ðḟ          - filter out if:
Ị            -   insignificant (absolute value <= 1 - hence any 0s or 1s)
   B         - convert to a binary list (vectorises)
    U        - upend (reverse each)
     œs€2    - split €ach into 2 equal chunks (the first half is longer if odd ...hence
         U   - upend (reverse each)         ...this upend and the previous one)
          Ḅ  - convert from binary list to number (vectorises, although when the filter
             -                                     removes everything a zero is yielded)
           F - flatten the resulting list of lists to a single list

WÇÐĿṖUF - Main link: number
W       - wrap in a list
  ÐĿ    - loop and collect results until no change occurs:
 Ç      -   call last link (1) as a monad
    Ṗ   - pop (remove the last element - a list containing a single zero which results
        -     from the effect of Ḅ when link 1's input only contained ones and zeros)
     U  - upend (put the iterations into the required order)
      F - flatten to yield a single list

Answer 4

JavaScript (ES6), 99 bytes

This looks a bit too long. There might be a better way to get the correct order.

f=(n,p=(a=[],1),i=33-Math.clz32(n)>>1)=>(a[p]=n)>1?f(n>>i,p*=2)&&f(n&(1<<i)-1,p+1):a.filter(n=>1/n)

Demo

f=(n,p=(a=[],1),i=33-Math.clz32(n)>>1)=>(a[p]=n)>1?f(n>>i,p*=2)&&f(n&(1<<i)-1,p+1):a.filter(n=>1/n)

console.log(JSON.stringify(f(255)))
console.log(JSON.stringify(f(225)))
console.log(JSON.stringify(f(32)))

Answer 5

Java 7, 541 bytes

import java.util.*;List l=new ArrayList(),L=new ArrayList();String c(int n){l.add(x(n));return a(n+" ",l,n);}String a(String r,List q,Integer n){boolean e=q.equals(l),E=q.equals(L);if(e)L.clear();else l.clear();for(String i:new ArrayList<String>(q)){int s=i.length()/2,a=n.parseInt(i.substring(0,s),2),z=n.parseInt(i.substring(s),2);r+=a+" "+z+" ";if(e&a>1)L.add(x(a));if(e&z>1)L.add(x(z));if(E&a>1)l.add(x(a));if(E&z>1)l.add(x(z));}if(e&L.size()>0)r=a(r,L,n);if(E&l.size()>0)r=a(r,l,n);return r;}String x(Integer n){return n.toString(n,2);}

Keeping the original order screwed me over big-time, otherwise it would just be an easy loop and recursive-call principle. Still, fun challenge to figure out while retaining the order.

Explanation:

import java.util.*;                    // Required import for List and Array List

List l=new ArrayList(),L=new ArrayList(); 
                                       // Two Lists on class-level

String c(int n){                       // Method (1) with integer parameter and String return-type
  l.add(x(n));                         //  Start by adding the binary-String of the input integer to list `l`
  return a(n+" ",l,n);                 //  And let the magic begin in method `a` (2)
}                                      // End of method (1)

String a(String r,List q,Integer n){   // Method (2) with a bunch of parameters and String return-type
  boolean e=q.equals(l),E=q.equals(L); //  Determine which of the two class-level Lists the parameter-List is
  if(e)                                //  If it's `l`:
    L.clear();                         //   Empty `L`
  else                                 //  If it's `L` instead:
    l.clear();                         //   Empty `l`
  for(String i:new ArrayList<String>(q)){
                                       //  Loop over the input list (as new ArrayList to remove the reference)
    int s=i.length()/2,                //   Get the length of the current item in the list divided by 2
                                       //   NOTE: Java automatically floors on integer division,
                                       //   which is exactly what we want for the splitting of odd-length binary-Strings
    a=n.parseInt(i.substring(0,s),2),  //   Split the current binary-String item in halve, and convert the first halve to an integer
    z=n.parseInt(i.substring(s),2);    //   And do the same for the second halve
    r+=a+" "+z+" ";                    //   Append the result-String with these two integers
    if(e&a>1)                          //   If the parameter List is `l` and the first halve integer is not 0:
      L.add(x(a));                     //    Add this integer as binary-String to list `L`
    if(e&z>1)                          //   If the parameter List is `l` and the second halve integer is not 0:
      L.add(x(z));                     //    Add this integer as binary-String to List `L`
    if(E&a>1)                          //   If the parameter List is `L` and the first halve integer is not 0:
      l.add(x(a));                     //    Add this integer as binary-String to List `l`
    if(E&z>1)                          //   If the parameter List is `L` and the second halve integer is not 0:
      l.add(x(z));                     //    Add this integer as binary-String to List `l`
  }                                    //  End of loop
  if(e&L.size()>0)                     //  If the parameter List is `l` and List `L` now contains any items:
    r=a(r,L,n);                        //   Recursive call with List `L` as parameter
  if(E&l.size()>0)                     //  If the parameter List is `L` and List `l` now contains any items:
    r=a(r,l,n);                        //   Recursive call with List `l` as parameter
  return r;                            //  Return the result-String with the now appended numbers
}                                      // End of method (2)

String x(Integer n){                   // Method (3) with Integer parameter and String return-type
  return n.toString(n,2);              //  Convert the integer to its Binary-String
}                                      // End of method (3)

Test code:

Try it here.

import java.util.*;
class M{
  List l=new ArrayList(),L=new ArrayList();String c(int n){l.add(x(n));return a(n+" ",l,n);}String a(String r,List q,Integer n){boolean e=q.equals(l),E=q.equals(L);if(e)L.clear();else l.clear();for(String i:new ArrayList<String>(q)){int s=i.length()/2,a=n.parseInt(i.substring(0,s),2),z=n.parseInt(i.substring(s),2);r+=a+" "+z+" ";if(e&a>1)L.add(x(a));if(e&z>1)L.add(x(z));if(E&a>1)l.add(x(a));if(E&z>1)l.add(x(z));}if(e&L.size()>0)r=a(r,L,n);if(E&l.size()>0)r=a(r,l,n);return r;}String x(Integer n){return n.toString(n,2);}

  public static void main(String[] a){
    M m=new M();
    System.out.println(m.c(255));
    m.l.clear();
    m.L.clear();
    System.out.println(m.c(225));
    m.l.clear();
    m.L.clear();
    System.out.println(m.c(32));
  }
}

Output:

255 15 15 3 3 3 3 1 1 1 1 1 1 1 1 
225 14 1 3 2 1 1 1 0 
32 4 0 1 0 

Answer 6

Python 2, 110 bytes

l=[input()];i=1
while i:
 z=0
 for k in l[-i:]:
	if k>1:b=~-len(bin(k))/2;l+=[k>>b,k&2**b-1];z+=2
 i=z
print l

Try it online!

Answer 7

Retina, 142 bytes

.+
$*
+`(1+)\1
${1}0
01
1
{`.+$
$&¶<$&>
+`;(\d*)>
>;<$1>
<.>

{`(\d)>
>$1
}`<(\d)
$1<
<>
;
\b0+\B

}`^;|;\B

¶
;
;;

1
01
+`10
011
0\B

1+
$.&

Try it online!

Answer 8

PHP, 132 Bytes

for($r=[$argn];""<$n=$r[+$i++];)$n<2?:[$r[]=bindec(substr($d=decbin($n),0,$p=strlen($d)/2)),$r[]=bindec(substr($d,$p))];print_r($r);

Try it online!

Answer 9

Ruby, 102 bytes

f=->*a{a==[]?[]:a+=f[*a.map{|i|s='%b'%i;i>1?[s[0...h=s.size/2].to_i(2),s[h..-1].to_i(2)]:[]}.flatten]}

Try it online!

Answer 10

Ruby, 98 bytes

f=->*a{a==[]?a:a+=f[*a.flat_map{|i|s='%b'%i;i>1?[s[0...h=s.size/2].to_i(2),s[h..-1].to_i(2)]:[]}]}

Try it online!

Simply a basic optimization of Value Ink's answer : use flat_map instead of map...flatten, and use

a==[]?a instead of a==[]?[]