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 code-golf; shortest solution per language wins.
+[[->,.>++<<]+++++++++.>>]
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
{(&*/'2\'!#x)_x}
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).
{(|1_(-2!)\#x)_x}
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")
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
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!
Anonymous tacit prefix function. Requires 0-based indexing (⎕IO←0) which is default on many systems.
⊢⊂⍨≢↑∘∊1↑¨⍨2*⍳∘≢
⊢ 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
f=->s,a=1{s&&[s[0,a],*f[s[a..],a+a]]}
@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.
puts flattens the result.
\$\endgroup\$
JxËᶻL
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
{x@.=+|\2\!-#x}
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")
|\2\!-#x is quite clever
\$\endgroup\$
Commented
Jul 3 at 11:33
-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)]
ẏEẇ
Golf pilled sbcs maxxer.
ẏ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.
!`(?<=(.)*).(?<-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.
<;.1~1=1#.[:#:#\
<;.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')
Ｅ↨Ｌθ²×ψＸ²κ↑¤θ
Try it online! Link is to verbose version of code. Explanation:
Ｅ↨Ｌθ²×ψＸ²κ
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.
Prompts for string. Outputs a nested vector of segments. Index origin = 0
(∊n⍴¨n←2*⍳⌈2⍟⍴s)⊂s←⎕
⎕IO←1: (r↑i/i←⍳r←⍴s)⊂s←⎕ (or s⊂⍨r↑i/i←⍳r←⍴s←⎕ if you upgrade.)
\$\endgroup\$
(r↑i/i←2*⍳r←⍴s)⊆s←⎕ or s⊂⍨r↑i/i←×⍨⍳r←⍴s←⎕ with ⎕IO←0
\$\endgroup\$
$=>[i:1chunk&=>[2i'i+1ceil log]]
$=>[] ; 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
-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
=index(let(i,2^(row(A:A)-1),mid(A1,i,i)))
2^(row(1:99)-1) instead of 2^sequence(99,1,) and 2^(1+sequence(99,1,-1)).
\$\endgroup\$
let() saves another 6.
\$\endgroup\$
Commented
Jul 3 at 9:58
gÝo£õÜ
Or minor alternative:
ā<o£ʒĀ
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)
C:1İ2
C # cut input into chunks with lengths:
:1 # prepend 1 to
İ2 # infinite sequence of powers of 2
# (starting at 2)
$. 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
-p, 10 bytesa^@--E\,#a
I feel there could be 1 or 2 bytes improvement but I don't see it at the moment.
⊕□⊚⍜ₙ⇡2+1⧻.
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"}
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.
1:99 with A:A to save a byte?
\$\endgroup\$
Commented
Jul 3 at 11:30
-4 bytes thanks to Mukundan314
i;f(s,l){for(i=1;i<l;i*=2)puts(strndup(s+i-1,i));}
May have a memory leak or two.
| . `,,$ <;^2$ >-$~ _
. # 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
\ ! ;`. $ </,$~$ >>@ ~ -
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.
takeWhile(/="").evalState(mapM(state.splitAt.(2^))[0..])
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.
takeWhile are not necessary.
\$\endgroup\$
This answer was written jointly with 0 '
cr<<<gB(l<bi<st)<zp nN
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 indiceshe<pST(fo<pa(eq<db.*l))
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.There are quite a few things I see here to improve.
eu which starts indexing from 1 instead of 0. zp nN is the way we are doing that now.l<bi.fo<<pa.As of 79db5b20 these reflections are implemented and this answer can be
xuc$pw2<nn
cr<<<gB(lB2<st)<eU
he<pST(apa$eq<db.*l)
