26
\$\begingroup\$

Simple task today. Given a string whose length is one less than a whole power of 2, divide it into segments with doubling length.

For example for the string abcdefghijklmno, the result should be a, bc, defg, hijklmno:

abcdefghijklmno  (length 15)

a                 length 1
 bc               length 2
   defg           length 4
       hijklmno   length 8

The input will not be the empty string.

This is ; shortest solution per language wins.

\$\endgroup\$
1

39 Answers 39

10
\$\begingroup\$

brainfuck, 26 bytes

+[[->,.>++<<]+++++++++.>>]

Attempt This Online!

Output separated by tabs with some extra tabs at the end.

This is pretty short so I may as well add an explanation:

+        1 is the first segment length
[  
  [-     Repeat that many times:
    >,.    Go right: read and output one character
    >++    Go right: Add two to this cell
             (This is what doubles the length)
    <<]    Go back to the loop counter cell
  +++++  The cell is now zero so we can freely
  ++++.    change it; output a tab (ASCII 9)
  >>]    Go to our new loop counter cell and start
           again
\$\endgroup\$
8
\$\begingroup\$

R, 46 bytes

\(x)substring(x,a<-2^(0:log2(nchar(x))),2*a-1)

Attempt This Online!

Takes input as a string and outputs a vector of strings.


R, 44 bytes

\(x)split(x,rep(i<-2^(0:log2(length(x))),i))

Attempt This Online!

Takes input as a vector of characters and outputs a list of vectors of characters.

\$\endgroup\$
7
\$\begingroup\$

C (gcc), 58

f(s,i)char*s;{while(putchar(*s++))if(!(++i&i-1))puts("");}

Try it online!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ I like the idea to conditionally print newlines instead of changing the number of characters printed. \$\endgroup\$ Commented Jul 3 at 10:57
  • \$\begingroup\$ 51 bytes \$\endgroup\$
    – Arnauld
    Commented Jul 3 at 15:54
  • \$\begingroup\$ That said, I don't think you're allowed to force the initialization of i by the caller. So it's probably more like 54 bytes. \$\endgroup\$
    – Arnauld
    Commented Jul 3 at 16:02
6
\$\begingroup\$

K (ngn/k), 16 bytes

{(&*/'2\'!#x)_x}

Try it online!

A near-backport from my own J solution. Instead of checking each 1-based index has exactly one 1 bit, this checks if each 0-based index is all ones in binary. This works in K (2\0 is an empty array and its product is 1) but not in J (#:0 is 0 instead of an empty array).

K (ngn/k), 17 bytes

{(|1_(-2!)\#x)_x}

Try it online!

Similar to Jelly (x_y cuts y at the indices specified in x), but had to be careful to avoid generating large indices or indices in non-increasing order (which give domain error).

My initial approach used 2\ (integer into binary vector) and 2/ (binary vector into integer), but I realized that simply repeatedly dividing the length by 2 gives the correct cut indices.

{(|1_(-2!)\#x)_x}    Input: a string of length 2^n-1 (example: "abcdefg")
 (         #x)       length of x = 7
     (-2!)\          repeatedly floor-divide by 2 until convergence and collect:
                     (7 3 1 0)
   1_                remove head which is too large (3 1 0)
  |                  reverse (0 1 3)
              _x     cut x with those indices ("a"; "bc"; "defg")
\$\endgroup\$
6
\$\begingroup\$

Nekomata, 5 bytes

JxËᶻL

Attempt This Online!

JxËᶻL
J       Split the input into a list of substrings
 x      Push [0, ..., length of the list - 1]
  Ë     Power of 2
   ᶻL   Check that each substring has the corresponding length
\$\endgroup\$
6
\$\begingroup\$

APL (Dyalog Extended), 16 12 bytes

Anonymous tacit prefix function, port of Bubbler's J.

⊢⊂⍨1=1⊥2⊤⍳∘≢

 the argument…

⊂⍨ partitioned by…

1= where one equals…

1⊥  the vertical sum (lit. base-1 evaluation) of…

2⊤ the binary representation (one number per column) of

⍳∘  the indices from 1 to the…

 length of the argument

Try it online!

Alternative APL (Dyalog Unicode), 12 bytes

Anonymous tacit prefix function, port of noodle person's J.

⊢⊆⍨1+∘⌊2⍟⍳∘≢

 the argument…

⊂⍨ grouped by…

1+∘ incremented…

 floored…

2⍟ log₂ of…

⍳∘ the indices of…

 the argument length Try it online!

Old APL (Dyalog Unicode), 16 bytes

Anonymous tacit prefix function. Requires 0-based indexing (⎕IO←0) which is default on many systems.

⊢⊂⍨≢↑∘∊1↑¨⍨2*⍳∘≢

Try it online!

 the argument…

⊂⍨ partitioned by…

 the length of the argument…

↑∘∊ -sized prefix of the the flattened…

1↑¨⍨ prefixes of 1 (padding with trailing 0s) of lengths…

2* two to the power of…

⍳∘≢ the indices (0…n−1) of the length of the argument

\$\endgroup\$
2
  • \$\begingroup\$ If porting Bubbler's 16 byte J gives you 12 bytes, how does porting my 12 byte J give you? \$\endgroup\$ Commented Jul 4 at 11:55
  • \$\begingroup\$ @noodleperson Also 12; added. \$\endgroup\$
    – Adám
    Commented Jul 4 at 16:29
6
\$\begingroup\$

Ruby, 55 53 47 45 37 bytes

  • -2 bytes thanks to Dingus
  • -8 bytes thanks to G B
f=->s,a=1{s&&[s[0,a],*f[s[a..],a+a]]}

Attempt This Online!

@OP just to let you know, the easy tasks are welcome! :)

A recursive function with 2 variables: the original string and the counter. The function chops a string piece, adds it to the unnamed output vector and updates the counter until the string is empty.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I like the recursive way, intuitive but still short. As for easy challenges, I try to intermix them among more medium-difficulty challenges because those tend to be more interesting. but I always have a few of these laying around if I run out of ideas :P \$\endgroup\$ Commented Jul 3 at 11:14
  • \$\begingroup\$ @Dingus thanks for your suggestion! Considering the output, I would rather stick to the output type I have already chosen, as a list. \$\endgroup\$ Commented Jul 4 at 7:29
  • 2
    \$\begingroup\$ 37 bytes \$\endgroup\$
    – G B
    Commented Jul 4 at 7:30
  • \$\begingroup\$ @GB fantastic! the asterisk is not necessary, or have I missed something? \$\endgroup\$ Commented Jul 4 at 7:41
  • 2
    \$\begingroup\$ You get a nested list if you don't "splat". You are not seeing it because puts flattens the result. \$\endgroup\$
    – G B
    Commented Jul 4 at 11:11
5
\$\begingroup\$

K (ngn/k), 15 bytes

{x@.=+|\2\!-#x}

Try it online!

x:"abcdefg"
!-#x          / integers from -length to -1
  -7 -6 -5 -4 -3 -2 -1
2\!-#x        / convert to base 2
  -1 -1 -1 -1 -1 -1 -1
   0  0  0  1  1  1  1
   0  1  1  0  0  1  1
   1  0  1  0  1  0  1
|\2\!-#x      / maximum scan
  -1 -1 -1 -1 -1 -1 -1
   0  0  0  1  1  1  1
   0  1  1  1  1  1  1
   1  1  1  1  1  1  1
.=+|\2\!-#x   / group identical columns
   (,0; 1 2; 3 4 5 6)
x@.=+|\2\!-#x / index back into the input string
   (,"a"; "bc"; "defg")
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Ooh love it! |\2\!-#x is quite clever \$\endgroup\$ Commented Jul 3 at 11:33
5
\$\begingroup\$

Python 3.8 (pre-release),  66   65   50   49   46   42  41 bytes

-1 byte by doing away with int.bit_length().
-15 bytes: recursion for the win!
-1 byte by using list unpacking instead of list().
-3 bytes by moving some stuff around.
-4 bytes by using and instead of the ternary ... if ... else ....
-1 byte by Jakque.

f=lambda x,n=1:x and[x[:n],*f(x[n:],2*n)]

Try it online!

\$\endgroup\$
1
4
\$\begingroup\$

Vyxal, 3 bytes

ẏEẇ

Try it Online!

Golf pilled sbcs maxxer.

Explained

ẏEẇ­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌­
ẏ    # ‎⁡Range [0, len input)
 E   # ‎⁢Each to the power of 2
  ẇ  # ‎⁣Partition the string into groups corresponding to each length
💎

Created with the help of Luminespire.

\$\endgroup\$
4
\$\begingroup\$

Jelly, 5 bytes

J2*œṖ

A monadic Link that accepts a list and yields a list of lists.

Try it online!

How?

J2*œṖ - Link: List of characters, S
J     - indices -> [1..len(S)]
 2*   - two exponentiate {that}
   œṖ - partition {S} at {those} indices
\$\endgroup\$
4
\$\begingroup\$

Retina 0.8.2, 21 bytes

!`(?<=(.)*).(?<-1>.)*

Try it online! Explanation: The last stage is by default a Match stage if there is no replacement pattern for it to be a Replace stage. The ! changes the output from the number of matches (in decimal) to the matches themselves (on separate lines). The pattern then uses a .NET balancing group to count its match index (which will be one less than a power of 2) and allow one character more than that to be matched.

\$\endgroup\$
4
\$\begingroup\$

J, 16 bytes

<;.1~1=1#.[:#:#\

Attempt This Online!

<;.1~1=1#.[:#:#\     Input: string of length 2^n-1 (example: 'abcdefg')
              #\     1-based indices (1 2 3 4 5 6 7)
          [:#:       each number to binary (0 0 1; 0 1 0; 0 1 1; 1 0 0; ...; 1 1 1)
       1#.           sum the bits of each number (1 1 2 1 2 2 3)
     1=              is it 1? (1 1 0 1 0 0 0)
<;.1~                cut at 1s and box each word ('a'; 'bc'; 'defg')
\$\endgroup\$
4
\$\begingroup\$

JavaScript (V8), 38 bytes

x=>x.replace(/|/g,_=>i&++i?'':' ',i=0)

Try it online!

Separate by space

\$\endgroup\$
1
  • \$\begingroup\$ 37 bytes by taking an array of characters as input. \$\endgroup\$
    – Arnauld
    Commented Jul 3 at 6:45
4
\$\begingroup\$

Charcoal, 13 bytes

E↨Lθ²×ψX²κ↑¤θ

Try it online! Link is to verbose version of code. Explanation:

E↨Lθ²×ψX²κ

Reserve a number of lines corresponding to the 1s in the base-2 representation of the input length, with each line's length being each power of 2 in turn, according to its index.

↑¤θ

Fill that reserved area using the original input string, thereby partitioning it as required.

\$\endgroup\$
4
\$\begingroup\$

APL+WIN, 20 bytes

Prompts for string. Outputs a nested vector of segments. Index origin = 0

(∊n⍴¨n←2*⍳⌈2⍟⍴s)⊂s←⎕

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
3
  • \$\begingroup\$ Using ⎕IO←1: (r↑i/i←⍳r←⍴s)⊂s←⎕ (or s⊂⍨r↑i/i←⍳r←⍴s←⎕ if you upgrade.) \$\endgroup\$
    – Adám
    Commented Jul 4 at 9:02
  • \$\begingroup\$ @Adám. Thanks but your first suggestion results in segments of linear increasing length: a bc def ghij klmno in APL+WIN \$\endgroup\$
    – Graham
    Commented Jul 4 at 12:25
  • \$\begingroup\$ Silly me. (r↑i/i←2*⍳r←⍴s)⊆s←⎕ or s⊂⍨r↑i/i←×⍨⍳r←⍴s←⎕ with ⎕IO←0 \$\endgroup\$
    – Adám
    Commented Jul 4 at 17:07
4
\$\begingroup\$

Arturo, 34 32 bytes

$=>[i:1chunk&=>[2i'i+1ceil log]]

Try it!

Explanation

$=>[]        ; a function where input is assigned to &
i:1          ; assign 1 to i
chunk&=>[]   ; split input by...
2i ceil log  ; bit length of i
'i+1         ; increment i
\$\endgroup\$
2
  • \$\begingroup\$ I really gotta learn Arturo. It's so pretty! \$\endgroup\$ Commented Jul 3 at 11:03
  • \$\begingroup\$ @noodleperson I love it for golfing because you can do things in a surprising number of orders as well as prefix, infix, and postifx, all of which are shorter in different circumstances. \$\endgroup\$
    – chunes
    Commented Jul 3 at 11:06
4
\$\begingroup\$

Japt -m, 9 7 5 bytes

Input as a character array, output as a 2D character array

Wv2pV

Try it

\$\endgroup\$
1
  • \$\begingroup\$ Very nice. TIL -m gives U,V,W the standard .map arguments, I guess it makes sense though. BTW, I'm working on a spiritual-successor to Japt called Vascri which in theory is about as short as Jelly while maintaining Japt/JS familiarity. It's almost ready for a 0.1 release, so you should see some solutions in Vascri popping up pretty soon :) \$\endgroup\$ Commented Jul 3 at 11:12
4
\$\begingroup\$

Google Sheets, 41 bytes

=index(let(i,2^(row(A:A)-1),mid(A1,i,i)))

screenshot

\$\endgroup\$
2
  • 1
    \$\begingroup\$ you can save 10 bytes by using 2^(row(1:99)-1) instead of 2^sequence(99,1,) and 2^(1+sequence(99,1,-1)). \$\endgroup\$
    – z..
    Commented Jul 3 at 4:16
  • 1
    \$\begingroup\$ @z.. right. I was brainless to use two different sequences in the first place. let() saves another 6. \$\endgroup\$ Commented Jul 3 at 9:58
4
\$\begingroup\$

05AB1E, 6 bytes

gÝo£õÜ

Try it online.

Or minor alternative:

ā<o£ʒĀ

Try it online.

Explanation:

g       #  Push the length of the (implicit) input-list
 Ý      #  Pop and push a list in the range [0,length]
        # OR:
ā       #  Push a list in the range [1, (implicit) input-length]
 <      #  Decrease each by 1 to the range [0,length)
  o     # Map each value to 2 to the power this value
   £    # Split the (implicit) input-string into parts of those sizes
    õÜ  #  Trim all trailing ""
        # OR:
    ʒ   #  Filter these string-parts:
     Ā  #   Check if truthy (where "" is falsey)
        # (after which the result is output implicitly)
\$\endgroup\$
4
\$\begingroup\$

Husk, 5 bytes

C:1İ2

Try it online!

C       # cut input into chunks with lengths:
 :1     # prepend 1 to
   İ2   # infinite sequence of powers of 2
        # (starting at 2)
\$\endgroup\$
4
\$\begingroup\$

Perl 5 -n, 28 bytes

($.*=2)&say$&while s/.{$.}//

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Very nice, I came up with a similar (but longer!) approach, using $. is really nice! You can save three bytes using the return of say in the calculation for the increment, and using ; as the delimited for s/// though: Try it online! \$\endgroup\$ Commented Jul 4 at 14:25
4
\$\begingroup\$

Pip -p, 10 bytes

a^@--E\,#a

I feel there could be 1 or 2 bytes improvement but I don't see it at the moment.

Attempt This Online!

\$\endgroup\$
2
  • \$\begingroup\$ Ah, nice! My initial solution was 12 bytes, very similar except I didn't think of the fact that too-big values in the argument of ^@ wouldn't make a difference. \$\endgroup\$
    – DLosc
    Commented Jul 8 at 22:09
  • \$\begingroup\$ A scan-based solution is also 10 bytes. \$\endgroup\$
    – DLosc
    Commented Jul 8 at 22:13
3
\$\begingroup\$

Uiua, 11 bytes

⊕□⊚⍜ₙ⇡2+1⧻.

Try it online!

Nice and short! (group) and (where) are a great combo for this.

⊕□⊚⍜ₙ⇡2+1⧻.  # input string on the right.   "abcdefghijklmno"
       +1⧻.  # length + 1                   16
   ⍜ₙ⇡2      # 2^( range( log_2( that )))   [1 2 4 8]
⊕□⊚          # group into pieces that size  {"a" "bc" "defg" "hijklmno"}

⍜ₙ⇡2 means range () "under" () logarithm base 2. applies a function, then a second function, and then the inverse of that first function. Here, we apply log_2(x), then range, and then the inverse of log_2(x) which is 2^x.

Literally, ⊕□⊚ does:

     #                              [1 2 4 8]
⊚    # these repeat the naturals:   [0 1 1 2 2 2 2 3 3 3 3 3 3 3 3]
⊕□   # group by boxing the chars     a b c d e f g h i j k l m n o
     # corresponding with indices   {"a" "bc" "defg" "hijklmno"}
\$\endgroup\$
3
\$\begingroup\$

Uiua, 9 bytes

This solution was written by Kai Schmidt, the creator of Uiua, not by me, so I'm making this a community wiki.

⊕□⌊ₙ2+1°⊏

This is a very simple solution, and very short: Take the range of 0 to the length of the input, add one to each, take the base-2 logarithm, and floor it. This list has natural numbers repeated doubling in length, so we use this as a group to take each part of the input into a list of boxes.

\$\endgroup\$
3
\$\begingroup\$

Excel, 35 34 bytes

-1 byte thanks to @doubleunary

=LET(i,2^(ROW(A:A)-1),MID(A1,i,i))

enter image description here

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Replace 1:99 with A:A to save a byte? \$\endgroup\$ Commented Jul 3 at 11:30
3
\$\begingroup\$

C (gcc), 54 50 bytes

-4 bytes thanks to Mukundan314

i;f(s,l){for(i=1;i<l;i*=2)puts(strndup(s+i-1,i));}

Try it online!

May have a memory leak or two.

\$\endgroup\$
3
  • \$\begingroup\$ 51 bytes \$\endgroup\$ Commented Jul 4 at 11:30
  • \$\begingroup\$ 50 bytes \$\endgroup\$ Commented Jul 4 at 14:16
  • \$\begingroup\$ Thank you, edited. \$\endgroup\$
    – corvus_192
    Commented Jul 4 at 15:15
3
\$\begingroup\$

Nibbles, 17 nibbles (8.5 bytes)

| . `,,$ <;^2$ >-$~ _

Attempt This Online!

  .                     # map over
    `,                  # range from zero to
      ,$                # length of input:
         <              #   take the first
           ^2$          #   2^n characters
          ;             #   (and save that number)
                        #   from
               >        #   drop the first
                -$~     #   saved number minus 1
                        #   characters
                        #   from
                    _   #   the input
|                       # and finally filter-out 
                        # any empty strings

Nibbles, 17 nibbles (8.5 bytes)

\ ! ;`. $ </,$~$ >>@ ~ -

Attempt This Online!

A completely different approach for same bytes: successively halve the string and take pairwise differences.

\ ! ;`. $ </,$~$ >>@ ~ -
     `'                     # iterate while unique
        $                   # starting with the input:
          <                 #   select the first
           /,$~             #   half its length
               $            #   characters
    ;                       # and save this list;
  !                         # now, zip this list with
                 >>@        # itself without the first element:
                     ~ -    #   get differences;
\                           # finally, reverse it

This would be 1 nibble shorter if we're allowed to output the divided segments in reverse order.

\$\endgroup\$
3
\$\begingroup\$

Haskell + hgl, 22 bytes

This answer was written jointly with 0 '

cr<<<gB(l<bi<st)<zp nN

Attempt This Online!

Explanation

  • zp nN zip with the natural numbers to pair each element with its 1-index.
  • gB(l<ni<st) group the list by the length of the index as a binary number.
  • cr remove the indices

23 bytes

he<pST(fo<pa(eq<db.*l))

Attempt This Online!

Explanation

This implements an exponential time algorithm. Unlike the previous solution this errors when the input is not one less than a power of two in length.

  • he get the first ..
  • pST partition of the input such that ...
  • fo for all ...
  • pa pairs of consecutive elements ...
  • eq<db.*l the length of the second is double the length of the first.

Reflection

There are quite a few things I see here to improve.

  • There should be a version of eu which starts indexing from 1 instead of 0. zp nN is the way we are doing that now.
  • There should be some log functions for calculating the digit lengths in various bases. Currently this is l<bi.
  • There should be a function to determine if every pair of consecutive elements in a list satisfies a predicate. This is currently fo<<pa.
  • There are currently functions for breaking lists into fixed-size chunks. There should be a function which takes a list and spits it into chunks of the sizes given in the list. This would vastly trivialize this challenge.

As of 79db5b20 these reflections are implemented and this answer can be

10 bytes

xuc$pw2<nn

18 bytes

cr<<<gB(lB2<st)<eU

19 bytes

he<pST(apa$eq<db.*l)
\$\endgroup\$
3
\$\begingroup\$

Haskell, 61 58 56 55 bytes

takeWhile(>"").evalState(mapM(state.splitAt.(2^))[0..])

Try it online!

It maps (with state) over the infinite sequence of powers of two. Each map step returns the first n characters of the string in the state and puts the remaining in the state. So giving as initial state the string and stop iterating when the result is the empty string, we obtain the result.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The parens around takeWhile are not necessary. \$\endgroup\$
    – Wheat Wizard
    Commented Jul 5 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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