Exploded substrings

Introduction

Let's observe the string abc. The substrings that can be made from this are:

a, ab, abc, b, bc, c


We now need to align them under the initial string, like this:

abc
a
b
c
ab
bc
abc


The order of the string doesn't matter, so this is also perfectly valid:

abc
a
ab
abc
b
bc
c


So, the substring is positioned under the location of the substring in the initial string. So for abcdef and the substring cde, it would look like this:

abcdef
cde


The task is to align all substrings with a length greater than 0, like shown above. You can assume that the string itself will only contain alphabetic characters and has at least 1 character. For the padding, you can use a space or some other non-alphabetic printable ASCII character (32 - 127). Maybe not necessary to mention, but the string itself will only contain unique characters, so not like aba, since the a occurs twice.

Test cases

Input: abcde

Possible output:

a
ab
abc
abcd
abcde
b
bc
bcd
bcde
c
cd
cde
d
de
e


Input: abcdefghij

Possible output:

a
ab
abc
abcd
abcde
abcdef
abcdefg
abcdefgh
abcdefghi
abcdefghij
b
bc
bcd
bcde
bcdef
bcdefg
bcdefgh
bcdefghi
bcdefghij
c
cd
cde
cdef
cdefg
cdefgh
cdefghi
cdefghij
d
de
def
defg
defgh
defghi
defghij
e
ef
efg
efgh
efghi
efghij
f
fg
fgh
fghi
fghij
g
gh
ghi
ghij
h
hi
hij
i
ij
j


This is , so the submission with the least amount of bytes wins!

• Where is the empty substring? Apr 27, 2016 at 10:23
• @KennyLau Oh yes, that reminds me to edit some more info into the challenge. Apr 27, 2016 at 10:46
• Is a trailing newline acceptable? Apr 27, 2016 at 11:19
• @user81655 Yes, that's acceptable. Apr 27, 2016 at 11:20
• Is an array of strings acceptable, or does it have to be newline-separated? Apr 27, 2016 at 18:31

Perl, 3228 24 bytes

Includes +1 for -n

Code:

/.+(??{say$"x"@-".$&})/


Run with the string on STDIN:

perl -nE '/.+(??{say$"x"@-".$&})/' <<< abcd


The golfing languages are so close and yet so far away...

Explanation

/.+/ matches a substring. Unfortunately it stops once it matched one. So I use the runtime regex construct (??{}) to extend the regex so it fails and backtracking will try the following substring, in the end trying them all before giving up in disgust.

Inside the (??{}) I print the current substring prefixed by as many spaces as the offset of the substring using $"x"@-" So the output neatly documents how regex backtracking works: abcd abc ab a bcd bc b cd c d  • Good gravy, this is just as esoteric looking as the esolangs. Have a +1. Apr 27, 2016 at 19:06 • @TimmyD: For some strange reason there are people who say golfing gives Perl a bad name... Apr 27, 2016 at 19:22 • The Perl 6 version that was inspired from this is very similar functionally perl6 -ne 'm/^(.*)(.+)<{+put " "x$0.to,$1}>/' Apr 28, 2016 at 2:40 • Doesn't work on input ab1 (I assume because say... evaluates to 1). (Tested in 5.18.2.) Edit: Oh! sorry, the question says "You can assume that the string itself will only contain alphabetic characters". May 19, 2016 at 21:17 MATL, 20 18 bytes Inspired by the pattern of substrings generated by @aditsu's answer tt!+gR*ct3Lt3$)tn


Try it online!

The pattern of substrings is generated by an upper triangular matrix the same size as the input, and all submatrices obtained by successively removing the last row and column.

Explanation

t         % implicit input. Duplicate
t!+g      % square matrix with size as input
R         % keep upper triangular part
*c        % multiply element-wise with broadcast. Convert to char
% do...while
t       %   duplicate
$&¶$1 2  The % means that this entire thing is done to each line individually (considering it a separate string for time being, and joining it all back together with linefeeds at the end). The + tells Retina to run this substitution in a loop until the output stops changing (which in this case means that the regex no longer matches). The regex then tries to match the last line of the input with at least two non-space characters, and appends a new row where the first of those is replaced with a space. • Can we have ! implies M and 1char versions of .+ and .*? Apr 27, 2016 at 23:40 • Also prefixes of prefixes of a string=prefixes of a string. Maybe you meant prefixes of suffixes? (Edited to correct.) Apr 27, 2016 at 23:42 • @CatsAreFluffy No the explanation was correct. When we remove prefixes from prefixes, we get substrings. As for the other suggestions, I don't think I'll make options imply stages. While currently, a lot characters are used only for one stage type, that will probably change in the future. As for .+ and .* I'd have to tokenise the regex, and while I'm planning to do that at some point, I don't think it's gonna happen any time soon (and if I do, I'll probably focus on features that actually add expressiveness). Apr 28, 2016 at 6:55 • 1 byte saved May 7, 2016 at 5:03 Pyth, 1413 10 bytes Thanks to @FryAmTheEggman for saving 3 bytes. jmXQ-Qd;.:  Try it online! • @LuisMendo Done. Apr 27, 2016 at 11:02 • jmXQ-Qd;.: Similar idea, using X. Apr 27, 2016 at 12:59 Oracle SQL 11.2, 146 bytes WITH v AS(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=LENGTH(:1))SELECT LPAD(SUBSTR(:1,s.i,l.i),s.i+l.i-1)FROM v s,v l WHERE s.i+l.i<=LENGTH(:1)+1;  Un-golfed WITH v AS(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=LENGTH(:1)) SELECT LPAD(SUBSTR(:1,s.i,l.i),s.i+l.i-1) FROM v s, v l WHERE s.i+l.i<=LENGTH(:1)+1  CJam, 20 q{__,{\_N+oSt}/;W<}h  Try it online Explanation: q read the input (initial string) {…}h do … while _ copy the current string _, copy and get the length {…}/ for each value (say i) from 0 to length-1 \ bring the string to the top _N+o make a copy, append a newline and print St set the i'th element to S=" " ; pop the last result (array full of spaces) W< remove the last character of the current string if the string is empty, the do-while loop terminates  Python, 57 bytes f=lambda s,p='':set(s)and{p+s}|f(s[1:],' '+p)|f(s[:-1],p)  Outputs a set like {' b', 'a', 'ab'}. The idea is to recurse down two branched that cut off the first or last character. The gives redundant outputs, but the set automatically removes duplicates. For alignment, every time the first character is cut off, a space is added to the prefix p, which is concatenated onto the front. PowerShell v2+, 69 bytes param(a)0..($b=$a.length-1)|%{($i=$_)..$b|%{" "*$i+-join$a[$i..$_]}}  Takes input $a, loops over the length (setting $b in the process for use later). Each outer loop, we loop up to $b again, setting $i for use later. Each inner loop, we output $i number of spaces concatenated with a slice of the input string. Since we're just looping through the string, this will actually handle any arbitrary string (duplicate letters, spaces, whatever).

Example

PS C:\Tools\Scripts\golfing> .\exploded-substrings.ps1 "Golfing"
G
Go
Gol
Golf
Golfi
Golfin
Golfing
o
ol
olf
olfi
olfin
olfing
l
lf
lfi
lfin
lfing
f
fi
fin
fing
i
in
ing
n
ng
g


C#, 136132 131 bytes

Golfed

String m(String s){String o="",e=o;for(int i=0,a,l=s.Length;i<l;i++,e+=" ")for(a=1;a+i<=l;a++)o+=e+s.Substring(i,a)+"\n";return o;}


Ungolfed

String m( String s ) {
String o = "", e = o;

for (int i = 0, a, l = s.Length; i < l; i++, e += " ")
for (a = 1; a + i <= l; a++)
o += e + s.Substring( i, a ) + "\n";

return o;
}


Full code

    using System;
using System.Collections.Generic;

namespace Namespace {
class Program {
static void Main( string[] args ) {
List<String> ls = new List<String>() {
"abcde",
"abcdefghijklmnop",
"0123456789",
};

foreach (String s in ls) {
Console.WriteLine( s );
Console.WriteLine( m( s ) );
Console.WriteLine( "" );
}

}

static String m( String s ) {
String o = "", e = o;

for (int i = 0, a, l = s.Length; i < l; i++, e += " ")
for (a = 1; a + i <= l; a++)
o += e + s.Substring( i, a ) + "\n";

return o;
}
}
}


Releases

• v1.2 - -1 byte - Changed the String o="",e=""; to String o="",e=o; to save 1 byte. The idea was from Gallant ( I forgot to apply this part in the last update, I apologize. ).
• v1.1 -  -4 bytes - Droped the brackets from the for loops and moved the e var space increment to the iterator zone of the outer for loop. The idea was from Gallant.
• v1.0 - 136 bytes - Initial solution.
• You can drop the curly braces on the inner loop and assign e=o to save 3 bytes. Apr 27, 2016 at 18:51
• can also swap String o="",... with var o... for another 3. Apr 27, 2016 at 18:55
• @tycobb it would render useless convert String o = "", e = ""; to var since I would have to separate them into two, resulting in var o = ""; var e = ""; which is the same length compared with the one I have. Would do it, but VS doesn't allow multiple variable declaration when using implicitly-typed variables - a.k.a. var's. But thanks for the help. EDIT: Having VS shouting me that I can't do it, I'm assuming it's incorrect, may be wrong. Apr 27, 2016 at 20:17

Python 2.7, 70 82 bytes

I couldn't figure out how to get it on 1 line. Call with e("abcde",0)

def e(s,p):
f=len(s)
for x in range(f):print(' '*p+s[:x+1])
if f>1:e(s[1:],p+1)


Python 3, 80 78 bytes

Loop through the number of spaces to prefix with and then the number of characters to end with.

lambda x:[print(' '*i+x[i:j+1])for i in range(len(x))for j in range(i,len(x))]


Edit: Removed spaces before the for loops.

MATL, 15 14 bytes

Saved one byte due to @LuisMendo's tip here!

tfWt2/!-RXzB*c


So many ways... had to find a new one. Happy bits! :)

Try it online!

Exploded

t       % duplicate input
f       % get indices of nonzero elements in vector (i.e. 1:n)
W       % 2 raised to array, element-wise: 2^(1:n)
t       % duplicate array
2/      % divide by 2: 2^(0:n-1)
!       % transpose array
-       % element-wise subtraction (w/singleton expansion)
R       % upper triangular part
Xz      % nonzero elements
B       % convert from decimal to binary. Produces a logical array
*       % array product (element-wise, singleton expansion)
c       % convert to character array; 0's automatically converted to spaces


JavaScript (ES6), 89 bytes

document.write("<pre>"+(

s=>(a=[...s]).map((_,i)=>a.map((_,j)=>++j>i?r+=" ".repeat(i)+s.slice(i,j)+
:0),r="")&&r

)("abcde"))

Straight-forward approach. Output has a trailing newline.

• What does => mean in Javascript ? Is it a binary operator Apr 29, 2016 at 12:02
• @EwanDelanoy It declares an ES6 Arrow Function. Apr 29, 2016 at 12:04

JavaScript (ES6), 72

s=>{for(i=j=0;s[j]||s[j=++i];)console.log(' '.repeat(i)+s.slice(i,++j))}


Pyth, 12 11 bytes

jm+*;xQdd.:


Sadly the question allows us to assume unique characters, so I just lookup the first position of the substring, and pad with spaces.

• You can use ; instead of \  when inside the lowest level map. Apr 27, 2016 at 13:03

Mathematica 89 bytes

r@i_:=StringReplace[i,#->" "]&/@(Complement[y,#]&/@Subsequences[y=Characters@i])//Column



Explanation

i refers to the input string

Subsequences[y=Characters@i] returns all subsequences (represented lists of characters) of the input. (Subsequences was introduced in v. 10.4)

For each subsequence, Complement... returns those characters from the input string that are not present. Each of those characters is replaced by an empty space via StringReplace[i,#->" "].

Column displays the results in a single column. Each output string has the same number of characters, resulting in aligned letters.

r@"abcdefgh"


• By 10.0.4 you mean 10.4, right? 10.3 doesn't have it. Apr 27, 2016 at 23:48
• Yes. 10.4 I'll correct it. Apr 28, 2016 at 1:04

J, 32 29 28 bytes

(-@{.@i.|.])"1 a:>@-.~&,<\\.


This evaluates to a monadic verb. Try it here. Usage:

   f =: (-@{.@i.|.])"1 a:>@-.~&,<\\.
f 'abe'
a
ab
abe
b
be
e


Explanation

As some other answers, I compute the index of occurrence of the first character of each substring. The substrings are stored in a matrix with trailing spaces, so I rotate them to the right by their index to get the right amount of padding. That one piece of whitespace between "1 and a: is really annoying...

(-@{.@i.|.])"1 a:>@-.~&,<\\.  Input is y
<\\.  Compute suffixes of prefixes of y, and put them in boxes.
This gives a 2D array of substrings in boxes.
&,      Flatten the array of boxes,
a:  -.~        remove all empty strings, and
>@           open each box. This places the strings in a 2D matrix of
characters, with trailing spaces to make it rectangular.
(          )"1                Do this for each line x in the matrix:
i.                        The index of every character of x in y.
-@{.@                          Take the first one and negate it.
|.]                     Rotate x to the left by that amount.
Since we negated the index, this rotates to the right.

• a e is not a substring as defined by the challenge Apr 27, 2016 at 20:44
• @TonHospel I fixed the program, it now follows the spec. Apr 28, 2016 at 16:33

JavaScript (Firefox 30-57), 65 63 bytes

s=>[for(c of(i=0,s))for(d of(t=r=i?t+' ':'',s.slice(i++)))r+=d]


Returns an array of strings. As ES6 it's 78 bytes:

s=>[...s].map((_,i,a)=>a.slice(i).map(c=>r.push(u+=c),t=u=i?t+' ':''),r=[])&&r


QBasic, 75 bytes

INPUT s$FOR i=1TO LEN(s$)
FOR j=1TO i
LOCATE,j
?MID$(s$,j,i+1-j)
NEXT
NEXT


The basic double-FOR-loop strategy, modified a bit for QBasic's 1-based indexing. The main trick is LOCATE,j, which moves the cursor over to column j of the current line before printing. Since column 1 is the first column, this is equivalent to printing j-1 leading spaces.

Perl 6, 34 bytes

perl6 -ne 'm/^(.*)(.+)<{+put " "x$0.to,$1}>/'

m/       # match the input line
^      # from the start
( .* ) # 0 or more characters ( $0 ) ( .+ ) # 1 or more characters ($1 )

<{ # match against the result of:

+put # print with a trailing newline:
" " x $0.to, # add the leading spaces$1           # the substring
}>
/


The reason for the + before put is so that it returns 1 instead of True, which is guaranteed not to be in the input so it always has to backtrack.

$perl6 -ne 'm/^(.*)(.+)<{+put " "x$0.to,$1}>/' <<< abcd   d cd c bcd bc b abcd abc ab a  ( If you want it in the opposite order use (.*?)(.+?) instead of (.*)(.+) ) This was inspired by the Perl 5 answer. J, 3523 22 bytes [:;#\.<@{."_1|.\."1^:2  It took me a while but I finally optimized it. Usage  f =: [:;#\.<@{."_1|.\."1^:2 f 'abcde' abcde abcd abc ab a bcde bcd bc b cde cd c de d e  Explanation [:;#\.<@{."_1|.\."1^:2 Input: s |.\."1 For each suffix of s, reverse it ^:2 Repeat that twice to create all exploded substrings #\. Get the length of each suffix. This is used to make the range [len(s), len(s)-1, ..., 1] {."_1 For each value in the range, take that many strings from the list of exploded substrings. This avoids blank substrings <@ Box each set of strings [:; Unbox and join the strings together and return  • You can save 2 bytes by removing the right pair of parentheses. Also, doing [:+./"1' '~:] instead of [:-.[:*/"1' '=] saves another 2 bytes. Apr 28, 2016 at 17:48 Java, 138 bytes String e(String s){int l=s.length(),a=0,i,j;for(;++a<l;)for(i=0;i<=l-a;){s+="\n";for(j=0;j++<i;)s+=" ";s+=s.substring(i,i+++a);}return s;}  Formatted: String e(String s) { int l = s.length(), a = 0, i, j; for (; ++a < l;) for (i = 0; i <= l - a;) { s += "\n"; for (j = 0; j++ < i;) s += " "; s += s.substring(i, i++ + a); } return s; }  Pyke, 15 bytes QlFUQRd:DlRF2h<  Try it here! Assumes array of padded strings is acceptable Pads first and then chops. Haskell, 65 bytes (>>=zipWith((++).(replicate' '))[0..].init.tails).reverse.inits  It requires inits and tails from Data.List, though. To output it, add mapM_ putStrLn. to the front. Relatively straightforward; the reverse is to make sure the original string is first. GHCi> mapM_ putStrLn.(>>=zipWith((++).(replicate' '))[0..].init.tails).reverse.inits$"abcde"
abcde
bcde
cde
de
e
abcd
bcd
cd
d
abc
bc
c
ab
b
a
it :: ()
(0.02 secs, 0 bytes)

• (>>=zipWith(++)(initscycle" ").init.tails).inits. And please add the import Data.List; to the byte count. – nimi Apr 28, 2016 at 17:04 Ruby, 75 67 bytes Anonymous function. Uses regex substitution to align the substrings. . is the filler character. ->s{(l=s.size).times{|i|(l-i).times{|j|puts s.tr(?^+s[j,i+1],?.)}}}  bash + GNU coreutils, 109 Bytes l={#1}
for i in seq 0 $l;{ for j in seq$((l-i));{
for k in seq $i;{ printf ' ';} echo${1:i:j}
}; }


Maybe there is a shorter solution, but this is the best that came into my mind. Uniqueness of chracters does not matter here.

PHP, 151 chars

Ungolfed

<?php
$input =$argv[1];
foreach(str_split($input) as$p=>$letter) {$spaces = str_repeat(" ", $p); echo$spaces.$letter."\n";$p++;
for($i=$p;$i<strlen($input);$i++) { echo$spaces.$letter.substr($input, $p,$i)."\n";
}
}
?>


Golfed

<?$c=$argv[1];foreach(str_split($c)as$d=>$b){$a=str_repeat(" ",$d);echo$a.$b."\n";$d++;for($e=$d;$e<strlen($c);$e++){echo$a.$b.substr($c,$d,$e)."\n";}}


Example

php explodesub.php 'abc'
a
ab
abc
b
bc
c


C++, 145 Bytes

the first start parameter is used as input, console as output

#include<iostream>
#define f(y,b,d) for(int y=b;r[0][y];y++){d;}
int main(int,char*r[]){f(x,0,f(y,x+1,std::cout.write(r[0],y)<<'\n')r[0][x]=32)}

• Great answer and welcome to PPCG! I don't use C++ much but can't you do std::cout<<r[0]<<y<<'\n' instead of std::cout.write(r[0],y)<<'\n'? Can you please add a brief explanation? Thanks! May 6, 2016 at 23:05

Python 2 (Ungolfed) 99 Bytes

t=raw_input()
l=len(t)
for j in range(l):
for i in range(l):
if i>=j:print j*' '+t[j:i+1]


Result:

>>python codegolf.py
abc
a
ab
abc
b
bc
c

>>python codegolf.py
abcdef
a
ab
abc
abcd
abcde
abcdef
b
bc
bcd
bcde
bcdef
c
cd
cde
cdef
d
de
def
e
ef
f

>>python codegolf.py
lmnopqrst
l
lm
lmn
lmno
lmnop
lmnopq
lmnopqr
lmnopqrs
lmnopqrst
m
mn
mno
mnop
mnopq
mnopqr
mnopqrs
mnopqrst
n
no
nop
nopq
nopqr
nopqrs
nopqrst
o
op
opq
opqr
opqrs
opqrst
p
pq
pqr
pqrs
pqrst
q
qr
qrs
qrst
r
rs
rst
s
st
t
`