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
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\$
{(&*/'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")
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
-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~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
2 days ago
=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
2 days ago
{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
2 days ago
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
yesterday
!`(?<=(.)*).(?<-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.
⊕□⊚⍜ₙ⇡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
2 days ago
%{for($i=1;$_[$i];$i*=2){$_|% S*g($i-1)$i}}
Straightforward: extract substrings of doubling length at doubling start indexes.
Relevant golfing:
$_[$i] tests just whether there is still a character at the current index; way shorter than $i-lt$_.Length$_|% S*g($i-1)$i takes the input string in $_, pipes it to % (an alias for ForEach-Object), calls the string object's member 'Substring' (the only member matching S*g), passing the start index and the length of the substring to retrieve. Shorter than $_.Substring($i-1,$i)
hâΣÆïó‼<≥;]
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)
h╥(âΣ would just be ceiling of log_2)
\$\endgroup\$
Commented
2 days ago
Σ to mean sum? :P
\$\endgroup\$
Commented
2 days ago
{Ẹg|ḍgᵗ↰ʰc}b
We rely on ḍ - dichotomize to split the string in 2. When the length is odd, the first string is shorter which is what we want. We then recurse dichotomization on the first string. The tricky part is then to flatten the list recursively up in the same predicate. We use the same idea as @Dlosc answer here, integrated directly in the predicate thas splits the string instead of applied after (which is longer).
{ } Apply the following predicate on the input string:
Ẹ If the input is the empty string ""…
g …output [""]
| Else
ḍ Dichotomize the string [<first half>, <second half>]
gᵗ Wrap the second half in a list
↰ʰ Recursive call on the first half
c Concatenate to flatten the current level
b Remove the first element which is the empty string at the end
-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.
