16
\$\begingroup\$

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.
\$\endgroup\$
5
  • 1
    \$\begingroup\$ @Satan'sSon If you pad in front, that's equivalent to the description. \$\endgroup\$
    – isaacg
    May 19, 2017 at 6:13
  • 1
    \$\begingroup\$ Is the specified output order required or just the values? \$\endgroup\$ May 19, 2017 at 6:17
  • \$\begingroup\$ @Satan'sSon No padding with 0s. \$\endgroup\$ May 19, 2017 at 6:28
  • 1
    \$\begingroup\$ @JonathanAllan The specified output order is required. \$\endgroup\$ May 19, 2017 at 6:28
  • \$\begingroup\$ Suggesting different title of "Split this in Half". \$\endgroup\$ May 19, 2017 at 17:02

11 Answers 11

14
\$\begingroup\$

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.

\$\endgroup\$
0
6
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ @JonathanAllan Yep fixed it now. Seems to be a problem the examples do not cover, thanks :) \$\endgroup\$
    – kalsowerus
    May 19, 2017 at 7:59
  • \$\begingroup\$ ʒ - This new codepage... Since when is 05AB1E Jelly? Me likey. \$\endgroup\$ May 19, 2017 at 17:14
5
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ How does this work? \$\endgroup\$ May 19, 2017 at 6:31
  • \$\begingroup\$ @Satan'sSon I added an explanation just now \$\endgroup\$ May 19, 2017 at 6:31
  • \$\begingroup\$ You added it at the same time I commented :D \$\endgroup\$ May 19, 2017 at 6:32
  • \$\begingroup\$ @ØrjanJohansen both ways have the same byte cost \$\endgroup\$ May 19, 2017 at 6:47
  • \$\begingroup\$ Oh, didn't see the Pyth answer first, which already used that trick. \$\endgroup\$ May 19, 2017 at 6:51
4
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
6
  • \$\begingroup\$ This does not work, according to the Try it online system in this page, \$\endgroup\$ May 22, 2017 at 10:59
  • \$\begingroup\$ @MartinBarker what do you mean? \$\endgroup\$ May 22, 2017 at 11:20
  • \$\begingroup\$ tio.run/nexus/… => Array( [0] => 225 [1] => 14 [2] => 1 [3] => 3 [4] => 2 [5] => 1 [6] => 1 [7] => 1 [8] => 0 ) when it does not = 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1 \$\endgroup\$ May 22, 2017 at 12:53
  • \$\begingroup\$ @MartinBarker You must change the input in the header Version. Change the variable $argn This variable is available if you running PHP from the command line with the -R option. Here is an example for input 255 Try it online! \$\endgroup\$ May 22, 2017 at 13:14
  • \$\begingroup\$ That's what i was trying to say it did not work according to the try it online system. (linked in the post) \$\endgroup\$ May 22, 2017 at 16:21
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Java 10, 541 521 245 243 bytes

n->{var L=new java.util.Stack<Integer>();L.add(n);for(int i=9,o=0,t;o<i;)for(i=o;i<L.size();o++)if((t=L.get(i++))>1){var b=n.toString(t,2);L.add(n.parseInt(0+b.substring(0,t=b.length()/2),2));L.add(n.parseInt(b.substring(t),2));o++;}return L;}

Try it online.

-22 bytes thanks to @ceilingcat.

Explanation:

n->{                      // Method with Integer parameter & Integer-List return-type
  var L=new java.util.Stack<Integer>();
                          //  Create the result-List
  L.add(n);               //  Add the input-Integer to it
  for(int i=9,            //  Index integer `i`, set to a non-0 digit
      o=0,                //  Off-set integer `o`, starting at 0
      t;                  //  Temp integer `t`, uninitialized
      o<i;)               //  Loop as long as `o` isn't `i` yet:
    for(i=o;i<L.size()    //   Inner loop `i` in the range [`o`,list-size):
        ;o++)             //     After every iteration: Increase `o` by 1
      if((t=L.get(i++))   //    Set `t` to the `i`'th item
                          //    (and increase `i` by 1 afterwards with `i++`)
         >1){             //    If `t` is larger than 1 (thus can be further split):
        var b=n.toString(t,2);
                          //     Convert `t` to a binary-String
        L.add(            //     Add to the List:
          n.parseInt(     //      A String converted to Integer:
            0             //       A "0",
            +b.substring( //       Appended with a substring of `b`
               0,t=b.length()/2)
                          //       in the char-range [0,length/2)
          ,2));           //      Converted as a base-2 String to base-10 Integer
        L.add(            //     Also add to the List:
          n.parseInt(     //      A String converted to Integer:
            b.substring(  //       A substring of `b`
              t)          //       in the char-range [length/2,length)
          ,2));           //      Also converted from a base-2 String to base-10 Integer
        o++;}             //     And increase `o` by 1
  return L;}              //  Return the result-List
\$\endgroup\$
0
0
\$\begingroup\$

MathGolf, 18 bytes

{gÉo1>môàh½‼<≥å}∟;

Takes the input wrapped inside a list. If this is not allowed, a leading a can be added.
Print each of the resulting items on a separated line to STDOUT.

Try it online.

Explanation:

{              }∟  # Do-while true without popping:
 g                 #  Filter the current list of integers by
                   #  (or the implicit input-list in the first iteration),
  É                #  using the following 3 characters as inner code-block:
   o               #   Print the integer with trailing newline (without popping)
    1>             #   Check that it's larger than 1 (thus can be further split)
      m            #  Map over the remaining integers,
       ô           #  using the following 6 characters as inner code-block:
        à          #   Convert the integer to a binary-string
                   #   Split it into the correct halves by:
         h         #    Pushing its length (without popping)
          ½        #    Integer-dividing this length by 2
           ‼       #    And apply the following commands separated on the stack:
            <      #     Slice to get the first length//2 bits
             ≥     #     Slice to get the remaining bits
              å    #  After the map: convert all binary-parts back to integers
                 ; # After the do-while: remove the empty list from the stack
                   # (the empty stack is then output implicitly with newline)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.