27
\$\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

To be clear, the spaces above are just for demonstration, your program does not need to do that, it just has to divide the string into the appropriate lengths. The format of the output is not specific.

The input will not be the empty string.

This is ; shortest solution per language wins.

Improve this question
\$\endgroup\$
1

43 Answers 43

Reset to default
1
2
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)
Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The parens around takeWhile are not necessary. \$\endgroup\$ Commented Jul 5, 2024 at 23:21
3
\$\begingroup\$

JavaScript (Node.js), 44 bytes

x=>[...x].reduce((a,c,i)=>i&++i?a+c:a+' '+c)

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Nice solution! In case you didn't see, @l4m2 posted a JavaScript solution earlier in the thread at 38 bytes: l4m2's solution \$\endgroup\$ Commented Jul 14, 2024 at 23:37
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°⊏

Try it!

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

MathGolf, 12 11 bytes

hâΣÆïó‼<≥;]

Try it online.

Explanation:

Step 1: Calculate the amount of parts we need to output, basically \$\log_2(length+1)\$ manually:

 # (e.g. input = "abcdefghijklmno") h # Push the length of the (implicit) input-string # → 15 â # Convert it to a binary list # → [1,1,1,1] Σ # Sum this list of 1-bits # → 4

Step 2: Actually split the input into the power of 2 parts:

Æ # Loop in the range [0,value], # using 5 characters as inner code-block: ï # Push the current 0-based loop-index ó # Pop and convert it to 2 to the power this index ‼ # Apply the next two operators separately on the current stack: < # Slice to substring [0,val) ≥ # Slice to substring [val,length) ; # After the loop: discard the trailing no-op part ] # Wrap all correct parts on the stack into a list # (after which the entire stack is output implicitly as result)
Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'm surprised that a language with "Math" in the name doesn't have logarithm built-in and chose instead to have "5-character block" built-in, lol. (h╥(âΣ would just be ceiling of log_2) \$\endgroup\$ Commented Jul 3, 2024 at 13:12
  • \$\begingroup\$ @noodleperson ikr.. I've been missing a lot of Math-related builtins besides logarithm in the past in this language, like sine/cosine/tangent; rounding; base conversion besides binary/hexadecimal; bitwise operations like AND/OR/XOR; etc. \$\endgroup\$ Commented Jul 3, 2024 at 13:17
  • \$\begingroup\$ Wow, why on earth is it called MathGolf?! Is it just the fact that it uses Σ to mean sum? :P \$\endgroup\$ Commented Jul 3, 2024 at 13:18
  • \$\begingroup\$ @noodleperson I think the idea was to eventually add all the other stuff, but it was mostly abandoned. It does have 59 different 1-byte numeral constants, though (but no way to actually push other numbers consistently). xD \$\endgroup\$ Commented Jul 3, 2024 at 13:21
2
\$\begingroup\$

Julia 1.0, 54 bytes

~s=[s[2^i:2*2^i-1] for i=0:floor(Int,log2(length(s)))]

Try it online!

Uses array comprehension to generate pairs of indices. The related solution with map takes the same number of bytes:

Julia 1.0, 54 bytes

~s=map(i->s[2^i:2*2^i-1],0:floor(Int,log2(length(s))))

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

J, 16 12 bytes

</.~2<.@^.#\

Attempt This Online!

This is my first time trying to golf in J! I got a lot of help golfing the forks and whatnot. I tried a different method from Bubbler's way and it ended 4 bytes shorter :)

Thanks to ovs for telling me about #\ which is a much shorter way of getting the length-one-range.

Explanation:

</.~2<.@^.#\ </.~ NB. Group the items of the input by 2<.@^. NB. floors of the base-2 logarithms of #\ NB. the range of 1 to the input's length. NB. (Literally: length of prefixes)
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ This can actually be 12 bytes borrowing #\ -: 1+i.@# from Bubbler's solution. \$\endgroup\$ Commented Jul 3, 2024 at 23:38
  • \$\begingroup\$ Thanks @ovs, I didn't know about #\ to get the indices :) \$\endgroup\$ Commented Jul 4, 2024 at 0:51
2
\$\begingroup\$

GolfScript, 20 19 bytes

1/.,,{).)&!n*}%]zip

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ -1 byte: dammit. \$\endgroup\$ Commented Jul 4, 2024 at 13:27
2
\$\begingroup\$

Julia 1.0, 36 bytes

!s=keys(s).|>k->show(s[2^~-k:~-2^k])

Try it online!

Ends with an error. Substrings are printed in quotes. Cleaner output with println instead of show (+3 bytes)

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Very nice! Good use of letting it just error out so you don't have to worry about just taking log2 of the length or some shenanigans \$\endgroup\$ Commented Jul 6, 2024 at 13:16
2
\$\begingroup\$

AWK, 64 52 41 bytes

{for(i=1;i<NF;i=2*i)print substr($0,i,i)}

Use [ -F '' ] flag upon calling awk to separate fields and give us the right number for NF.

{for(i=1;i<length($0);i=2*i)printf substr($0,i,i)FS}

Try it online!

{for(i=1;i<length($0);i=2*i)printf substr($0,i,i)"\n"(y=y y" ")} {for(i=1;i<length($0);i=2*i) # twice as many letters per printf substr($0,i,i) # just the letters we need "\n"(y=y y" ")} # whitespace for next line
Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Pyth, 9 bytes

fTcQtM^2U

Try it online!

Takes a string as an input and outputs a list of strings.

 U # create a range 0..length of the string ^2 # make them powers of 2 tM # decrease by 1 cQ # chop the input string Q fT # remove empty strings
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Raku (Perl 6) (rakudo), 90 bytes

sub MAIN($i){my $s=$i;for (1,2,4...^*>$s.chars) ->$x {say $s.substr(0,$x);$s.=substr($x)}}

Attempt This Online!

ungolfed:

sub MAIN($i){ my $s=$i; for (1,2,4...^*>$s.chars) ->$x { say $s.substr(0,$x); $s.=substr($x) } }

straightfowards and uninventive and probably not very golfed but this is my first time doing raku or perl and i wanted to try it out.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ You linked the ungolfed program in the ATO link \$\endgroup\$ Commented Aug 20, 2024 at 15:20
  • \$\begingroup\$ @noodleperson I sure did. The ungolfed version is exactly the same with additional whitespace, I don't think it really matters (I've tested that it sill functions with it removed, hence why there are still mandatory spaces in the golfed version) \$\endgroup\$ Commented Aug 20, 2024 at 20:42
  • \$\begingroup\$ -33 by abusing regexes and containers \$\endgroup\$ Commented Oct 30, 2024 at 9:22
  • \$\begingroup\$ Otherwise, -24 making an explicit container anyway \$\endgroup\$ Commented Oct 30, 2024 at 9:23
1
\$\begingroup\$

Haskell, 47 bytes

g n""=[] g n s|(h,t)<-splitAt n s=h:g(n*2)t g 1

Try it online!

It returns the answer as a list of strings. This is basically the simplest possible answer. More readably, it might be written like this:

go n "" = [] go n string = chunk : go (n*2) string' where (chunk, string') = splitAt n string
Improve this answer
\$\endgroup\$
1
2

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.