31
\$\begingroup\$

The Challenge

Given two strings/an array of strings, output the first string slowly shrinking and expanding back into the second string.

You can assume the strings will always start with the same character.

Example

Input:
"Test", "Testing"

Output:
Test
Tes
Te
T
Te
Tes
Test
Testi
Testin
Testing

First you output the first word:

Test

Then you keep removing one letter until the string is one character long:

Tes
Te
T

Then keep adding one letter of the second word until it's done:

Te
Tes
Test
Testi
Testin
Testing

(if both strings are one character long, then just output one of them once.)

Test Cases

"Hello!", "Hi."
Hello!
Hello
Hell
Hel
He
H
Hi
Hi.

"O", "O"

O

"z", "zz"

z
zz

".vimrc", ".minecraft"

.vimrc
.vimr
.vim
.vi
.v
.
.m
.mi
.min
.mine
.minec
.minecr
.minecra
.minecraf
.minecraft

"     ", "   "

SSSSS
SSSS
SSS
SS
S
SS
SSS

"0123456789", "02468"

0123456789
012345678
01234567
0123456
012345
01234
0123
012
01
0
02
024
0246
02468

(note: on the space/fourth test case, replace the S with spaces)

Rules

  • This is , so shortest answer in bytes wins! Tiebreaker is most upvoted post. Winner will be chosen on 09/10/2016.

  • Standard loopholes are forbidden.

\$\endgroup\$
  • \$\begingroup\$ Will 2 trailing newlines (one visible empty line after the sequence) be allowed or not? \$\endgroup\$ – seshoumara Sep 8 '16 at 10:36

43 Answers 43

11
\$\begingroup\$

Pyth, 9 bytes

j+_._Et._

A program that takes the second string, and then the first string, as quoted strings on STDIN and prints the result.

Try it online

How it works

j+_._Et._  Program. Inputs: Q, E
   ._E     Yield prefixes of E as a list
  _        Reverse the above
       ._  Yield prefixes of Q as a list (implicit input fill)
      t    All but the first element of above
 +         Merge the two lists
j          Join on newlines
           Implicitly print
\$\endgroup\$
14
\$\begingroup\$

V, 14 bytes

òYp$xhòjòÄ$xhh

Try it online!

Explanation:

ò     ò     "Recursively:
 Yp         "  Yank the current line and paste it
   $        "  Move to the end of the current line
    x       "  Delete one character
     h      "  Move One character to the right.
            "  Because of the way loops work in V, this will throw an error if there
            "  Is only one character on the current line.

Now, the buffer looks like this:

0123456789
012345678
01234567
0123456
012345
01234
0123
012
01
0

We just need to do the same thing in reverse for the next line:

j           "Move down one line
 ò     ò    "Recursively (The second ò is implicit)
  Ä         "  Duplicate this line up
   $        "  Move to the end of the current line
    x       "  Delete one character
     hh     "  Move two characters to the right.
            "  Because of the way loops work in V, this will throw an error if there
            "  Is only two characters on the current line.

More interesting alternate solution:

òÄ$xhòç^/:m0
ddGp@qd
\$\endgroup\$
  • 3
    \$\begingroup\$ It is like vim is always correct tool for job \$\endgroup\$ – Downgoat Sep 4 '16 at 4:14
  • \$\begingroup\$ @Downgoat Exactly. That's why you need to start golfing in V. :P \$\endgroup\$ – DJMcMayhem Sep 4 '16 at 4:15
9
\$\begingroup\$

Python, 93 bytes

f=lambda a,b,r='',i=2:a and f(a[:-1],b,r+a+'\n')or(len(b)>=i and f(a,b,r+b[:i]+'\n',i+1)or r)

Starts with the empty string r, adds a and a newline and removes the last character from a until a is empty then adds the required portions of b and a newline by keeping a counter, i, which starts at 2 until the length of b is exceeded, then returns r. Has a trailing newline.

All tests are on ideone

\$\endgroup\$
  • \$\begingroup\$ 2 things. 1) I believe that you miscounted characters and it is actually 93 and 2) You don't need to say r="". Simple r would still work. \$\endgroup\$ – user63571 Jan 15 '17 at 23:23
  • \$\begingroup\$ Thanks @JackBates. 1. Correct, and updated - I probably forgot the f=. 2. Without the r='' present f('test','testing') would not work; yes f('test','testing','') would, but we must follow the specifications. \$\endgroup\$ – Jonathan Allan Jan 16 '17 at 18:03
  • \$\begingroup\$ Forgive me. I was just looking at the code and not the examples. \$\endgroup\$ – user63571 Jan 17 '17 at 19:06
7
\$\begingroup\$

05AB1E, 9 bytes

.pRI.p¦«»

Explanation

.pR           # prefixes of first word
     I.p       # prefixes of second word
         ¦       # remove first prefix
          «     # concatenate
           »    # join with newlines

Try it online!

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

Retina, 50 41 26 bytes

Thanks to Martin Ender for saving 15(!) bytes.

M&!r`.+
Om`^.¶[^·]+|.+
A1`

Takes input with the two strings separated by a newline:

Test
Testing

Try it online!

Explanation

M&!r`.+

The first line generates the "steps" of both words:

Testing
Testin
Testi
Test
Tes
Te
T
Test
Tes
Te
T

M is for match mode, & considers overlapping matches, and ! prints the matches instead of the number of them. The reason it's reversed is the right-to-left option: the engine starts looking for matches at the end of the string and continues toward the beginning.

Om`^.¶[^·]+|.+

This gets everything in the right order: it sOrts all matches of the subsequent regex: A character on its own line and every character (including newlines) after it, which matches the whole second half as one chunk, or otherwise a line of characters, which matches each individual line. These matches are then sorted by code point, so the T followed by the newline goes first, followed by the lines, ascending by length.

A1`

Now we just have that first character line on top so we use Antigrep mode to discard the first match of the default regex .+.

Old version

M&!r`.+
O`\G..+¶
s`(.*)¶.¶(.*)
$2¶$1
¶.$

Try this version online!

Explanation

The first line is the same, so see the explanation for that above.

O`\G..+¶

This reverses the lines of the first half (second input word). It actually sOrts the lines, and the regex limits the matches: it must be a line of two or more characters (..+) followed by a newline () that begins where the last one left off (\G). In the above example, the single T in the middle doesn't match, so nothing after it can.

Te
Tes
Test
Testi
Testin
Testing
T
Test
Tes
Te
T

Now we have the right two components, but in the wrong order.

s`(.*)¶.¶(.*)
$2¶$1

¶.¶ matches the lone T in the middle, which we don't need but separates the two parts. The two (.*) capture everything before and after, including newlines thanks to single-line mode. The two captures are substituted in the right order with a newline in between.

Now we're done, unless the input strings are one character long, in which case the input hasn't changed. To get rid of the duplicate, we replace ¶.$ (when the last line of the string a single character) with nothing.

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

Python 2, 88 82 bytes

x,y=input(),input()
for i in x:print x;x=x[:-1]
s=y[0]
for i in y[1:]:s+=i;print s

Takes two inputs, each surrounded by quotes.

Thanks @JonathanAllan for saving some bytes and pointing out a bug.

\$\endgroup\$
  • 1
    \$\begingroup\$ No need for the len(x) in x=x[:len(x)-1] since negative offset slicing works - you can just write x=x[:-1]. Only problem is your code wont handle the " ", " " test case very well. \$\endgroup\$ – Jonathan Allan Sep 4 '16 at 2:02
  • 1
    \$\begingroup\$ You can drop the second input() and use an input format like "<str1>", "<str2>" \$\endgroup\$ – LevitatingLion Sep 4 '16 at 11:41
  • \$\begingroup\$ You could change the second line to for i in range(x):print x[-i:], and the fourth line to for i in range(1,y):print y[:-i]. Not sure it would work, though. \$\endgroup\$ – Qwerp-Derp Sep 4 '16 at 12:25
4
\$\begingroup\$

Perl, 34 28 bytes

Includes +2 for -0n

Run with the strings on separate lines on STDIN:

perl -M5.010 -0n slow.pl
Test
Testing
^D

slow.pl:

/(^..+|
\K.+?)(?{say$&})^/

Let regex backtracking do the work...

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

Cheddar, 76 bytes

(a,b,q=s->(|>s.len).map((_,i)->s.head(i+1)))->(q(a).rev+q(b).slice(1)).vfuse

A bit longer than I'd liked. I'll add an explanation soon

Try it online!

\$\endgroup\$
  • \$\begingroup\$ What does |> do? \$\endgroup\$ – Cyoce Sep 6 '16 at 6:42
  • \$\begingroup\$ @Cyoce unary |> is range [0,n) binary is [a,b] \$\endgroup\$ – Downgoat Sep 16 '16 at 14:10
3
\$\begingroup\$

Brachylog, 32 bytes

:1aLtT,Lhbr:Tc~@nw
:2fb
~c[A:B]h

Try it online!

Explanation

Brachylog has no prefix built-in, therefore we will get the prefixes by using concatenate (See predicate 2): a prefix of S is P if P concatenated to Q (whatever it is) results in S.

  • Main predicate:

    :1aL                  L is all prefixes of both elements of the input (see predicate 1)
       LtT,               T is the second element of L
           Lhbr           Remove the first prefix of the first list of L and reverse it
               :Tc        Concatenate with T
                  ~@n     Join with newlines
                     w    Write to STDOUT
    
  • Predicate 1:

    :2f                   Find all prefixes of the input string (see predicate 2)
       b                  Remove the first one (empty string)
    
  • Predicate 2:

    ~c[A:B]               Input is the result of concatenating A to B
           h              Output is A
    
\$\endgroup\$
3
\$\begingroup\$

Javascript, 103 81 bytes

f=(x,y,n=1)=>x?`
`+x+f(x.slice(0,-1),y):n++<y.length?`
`+y.slice(0,n)+f(x,y,n):''

Example: f("Test", "Testing")

Output:

Test
Tes
Te
T
Te
Tes
Test
Testi
Testin
Testing

Original answer

f=(x,y,n=1)=>x?(console.log(x),f(x.slice(0,-1),y)):n++<y.length?(console.log(y.slice(0,n)),f(x,y,n)):''
\$\endgroup\$
3
\$\begingroup\$

Java, 188 179 bytes

interface E{static void main(String[]a){int i=a[0].length();while(i>1)System.out.println(a[0].substring(0,i--));while(i<=a[1].length())System.out.println(a[1].substring(0,i++));}}

Update

  • Removed s variable, saved 9 bytes

Ungolfed:

interface E {

    static void main(String[] a) {
        int i = a[0].length();
        while (i > 1) {
            System.out.println(a[0].substring(0, i--));
        }
        while (i <= a[1].length()) {
            System.out.println(a[1].substring(0, i++));
        }
    }
}

Usage:

$ java E 'test' 'testing'
test
tes
te
t
te
tes
test
testi
testin
testing
\$\endgroup\$
3
\$\begingroup\$

Haskell, 54 53 47 bytes

t[]=[]
t x=x:t(init x)
(.reverse.t).(++).init.t

Usage example: ((.reverse.t).(++).init.t) "Hello" "Hi!" -> ["Hello","Hell","Hel","He","H","Hi","Hi!"].

Some pointfree magic. It's the same as f x y = (init(t x))++reverse (t y) where t makes a list of all initial substrings e.g. t "HI!" -> ["H","HI","HI!"].

\$\endgroup\$
  • \$\begingroup\$ Hm, t=reverse.tail.inits? \$\endgroup\$ – Bergi Sep 5 '16 at 13:23
  • \$\begingroup\$ @Bergi: sure, but inits needs import Data.List. \$\endgroup\$ – nimi Sep 5 '16 at 15:38
3
\$\begingroup\$

Pyke, 14 bytes

VDO)KKQlFh<)_X

Try it here!

And 17 bytes just because it's an awesome solution:

mVDO)Fto!I_O(RKsX

Try it here!

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

GNU sed, 57 45 + 2(rn flags) = 47 bytes

:;1{/../p};2G;2h;s/.(\n.*)?$//;/./t;g;s/.$//p

Run:

echo -e "Test\nTesting" | sed -rnf morphing_string.sed

The input should be the two strings separated by a newline. The code is run by sed for each line.

The loop : deletes one character from the end of the string iteratively. The output related to the first string is printed directly, except the first character: 1{/../p}. The output for the second string is stored in hold space in reverse order (2G;2h) during deletion and printed at the end.

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

C (gcc), 102 97 95 93 bytes

n;f(char*a,char*b){for(n=strlen(a);n;puts(a))a[n--]=0;for(a=b+1;*a++;*a=n)n=*a,*a=0,puts(b);}

Try it online!

The first loop overwrites the string with 0 bytes starting from the end, and uses puts() to print the string. The second loop can't just overwrite from the beginning, it has to store the old value so it can put it back; the 0 byte is just walking towards the end.

Thanks to @homersimpson and @ceilingcat for each shaving off 2 bytes!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a couple bytes by declaring n as a global int like: n;f(char*a,char*b){n=strlen(a).... And you can probably do n=*a=0 as a chained assignment in the body of your for loop. \$\endgroup\$ – homersimpson Sep 6 '16 at 5:05
  • \$\begingroup\$ Thanks @homersimpson. But n=*a=0 is not the same as n=*a,*a=0. \$\endgroup\$ – G. Sliepen Sep 8 '16 at 10:26
2
\$\begingroup\$

Python 3, 104 bytes

Meh.

n='\n';lambda x,y:x+n+n.join(x[:-i]for i in range(1,len(x)-1))+n+n.join(y[:i]for i in range(1,len(y)+1))

Thanks to @DJMcMayhem for golfing 21 bytes off.

Ideone it!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can take 5 bytes of if you do n='\n' and use n instead of '\n'. You could take another 8 off if you used a lambda instead of printing: n='\n';lambda x,y:n.join(x+n+n.join(x[:-i]for i in range(1,len(x)-1))+n+n.join(y[:i]for i in range(1,len(y)+1))) \$\endgroup\$ – DJMcMayhem Sep 3 '16 at 23:01
2
\$\begingroup\$

REPL/Javascript, 109 Bytes

Uses false string to whittle down the original string

Abuses substring with larger numbers to grow the second one, stops when its about to print the same word as last time.

(a,b)=>{l=console.log;z='substring';for(c=a.length;d=a[z](0,c--);){l(d)}for(c=2;d!=(n=b[z](0,c++));){l(d=n)}}

Demo:

> ((a,b)=>{l=console.log;z='substring';for(c=a.length;d=a[z](0,c--);){l(d)}for(c=2;d!=(n=b[z](0,c++));){l(d=n)}})("asdf","abcd")
[Log] asdf
[Log] asd
[Log] as
[Log] a
[Log] ab
[Log] abc
[Log] abcd
\$\endgroup\$
  • 1
    \$\begingroup\$ it's 1 byte shorter to do a=>b=>... and call the function with (a)(b) \$\endgroup\$ – Zwei Sep 5 '16 at 13:15
2
\$\begingroup\$

Brainfuck, 38 55 bytes

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

Edit: included newlines in output

\$\endgroup\$
  • \$\begingroup\$ I can't get your code to work. Is the input separated by a new line? Which interpreter are you using? \$\endgroup\$ – acrolith Sep 9 '16 at 22:02
2
\$\begingroup\$

Dyalog APL, 20 13 bytes

↑(⌽,\⍞),1↓,\⍞

matrify

(⌽,\⍞) reversed () cumulative concatenation (,\) of character input ()

, prepended to

1↓ one element dropped from

,\⍞ cumulative concatenation of character input

TryAPL online!

\$\endgroup\$
2
\$\begingroup\$

Racket 193 bytes

(define(f l)
(let*((s(list-ref l 0))
(x(string-length s)))
(for((n x))
(println(substring s 0(- x n))))
(set! s(list-ref l 1))
(for((n(range 1(string-length s))))
(println(substring s 0(add1 n))))))

Testing:

(f(list "Test" "Testing"))

"Test"
"Tes"
"Te"
"T"
"Te"
"Tes"
"Test"
"Testi"
"Testin"
"Testing"


(f(list "Hello!" "Hi."))

"Hello!"
"Hello"
"Hell"
"Hel"
"He"
"H"
"Hi"
"Hi."
\$\endgroup\$
  • \$\begingroup\$ It should delete last character from input string, not the first one. \$\endgroup\$ – agilob Sep 5 '16 at 14:40
2
\$\begingroup\$

Floroid, 69 bytes

a,b=L.J
c=1
NZ(a)!=1:z(a);a=a[:-1]
z(a)
NZ(a)!=Z(b):c+=1;a=b[:c];z(a)

It's a start. Takes the input from STDIN.

Testcases

Input: Test Testing
Output:
Test
Tes
Te
T
Te
Tes
Test
Testi
Testin
Testing

Input: O O
Output: O
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 92 bytes

(s,t)=>s.replace(/./g,`
$\`$&`).split`
`.slice(2).reverse().join`
`+t.replace(/./g,`
$\`$&`)

The replace statements build up a triangle of strings, which is exactly what's required for the second half of the output, however the first half needs to be reversed and the duplicate single-character line removed. Note: outputs a leading newline if the first string is a single character. If this is undesirable then for an extra byte this version always outputs a trailing newline:

(s,t)=>s.replace(/./g,`
$\`$&\n`).split(/^/m).slice(1).reverse().join``+t.replace(/./g,`
$\`$&\n`)
\$\endgroup\$
1
\$\begingroup\$

C, 142 bytes

#define _(x,y) while(y)printf("%.*s\n",d,x-c);
f(char*a,char*b){int c=1,d=strlen(a)+1;while(*++a==*++b)c++;_(a,--d>=c)d++;_(b,d++<strlen(b-c))}

Provide f(char* str1, char* str2).

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

TI-Basic, 56 bytes

Prompt Str1,Str2
Str1
While 1<length(Ans
Disp Ans
sub(Ans,1,length(Ans)-1
End
For(I,1,length(Str2
Disp sub(Str2,1,I
End

Example usage

Str1=?Test
Str2=?Testing
Test
Tes
Te
T
Te
Tes
Test
Testi
Testin
Testing

Str1=?O
Str2=?O
O

Str1=?z
Str2=?zz
z
zz
\$\endgroup\$
1
\$\begingroup\$

Java, 168 136 bytes

(s,d)->{int i=s.length()+1;while(i-->1)System.out.println(s.substring(0,i));while(i++<d.length())System.out.println(d.substring(0,i));};

Ungolfed test program

public static void main(String[] args) {

    BiConsumer<String, String> biconsumer = (s, d) -> {
        int i = s.length() + 1;
        while (i-- > 1) {
            System.out.println(s.substring(0, i));
        }
        while (i++ < d.length()) {
            System.out.println(d.substring(0, i));
        }
    };

    biconsumer.accept("Test", "Testing123");

}
\$\endgroup\$
1
\$\begingroup\$

(Lambdabot) Haskell - 41 bytes

f=(.drop 2.inits).(++).reverse.tail.inits

More readable, but two bytes longer:

a!b=(reverse.tail$inits a)++drop 2(inits b)


Output:

f "Hello" "Hi!"
["Hello","Hell","Hel","He","H","Hi","Hi!"]
\$\endgroup\$
1
\$\begingroup\$

J, 18 bytes

]\@],~[:}:[:|.]\@[

Ungolfed:

]\@] ,~ [: }: [: |. ]\@[

This is a 7-train:

]\@] ,~ ([: }: ([: |. ]\@[))

The innermost train [: |. ]\@[ consists of a cap [: on the left, so we apply |. (reverse) to the result of ]\@[, which is ]\ (prefixes) over [ (left argument).

Here's what that looks like on the testing, test input:

   'testing' ([: |. ]\@]) 'test'
test
tes
te
t

This gives us the first portion, almost. The 5-train outside of that is ([: }: ([: |. ]\@[)), which applies }: (betail, remove last element) to the above expression:

   'testing' ([: }: [: |. ]\@]) 'test'
test
tes
te

(This is because we can't have a duplicate midpoint.)

The outer part is finally:

]\@] ,~ ([: }: ([: |. ]\@[))

This is composed of ]\@] (prefixes of left argument) and ,~ (append what's to the left with what's to the right), leaving us with the desired result:

   'testing' (]\@] ,~ ([: }: ([: |. ]\@[))) 'test'
testing
testin
testi
test
tes
te
t
te
tes
test

Test cases

   k =: ]\@] ,~ ([: }: ([: |. ]\@[))
   'o' k 'o'
o
   k~ 'o'
o
   'test' k 'test'
test
tes
te
t
te
tes
test
   k~ 'test'
test
tes
te
t
te
tes
test
   '. . .' k '...'
. . .
. .
. .
.
.
..
...
   'z' k 'zz'
z
zz
\$\endgroup\$
  • \$\begingroup\$ You can rearrange it to 14 bytes using (,~}:@|.)&(]\) \$\endgroup\$ – miles Sep 8 '16 at 21:53
1
\$\begingroup\$

PHP, 117 109 bytes

for($i=strlen($a=$argv[1]);$i>1;)echo" ".substr($a,0,$i--);
for(;$j<strlen($b=$argv[2]);)echo" ".$c.=$b[$j++];

for($i=strlen($a=$argv[1]);$i>1;)echo substr($a,0,$i--)." ";
for(;$i<=strlen($b=$argv[2]);)echo substr($b,0,$i++)." ";

PHP, 107 bytes (not working with strings containing 0)

for($a=$argv[1];$a[$i];)echo substr($a.a,0,-++$i)." ";
for($b=$argv[2];$b[$j];)echo substr($b,0,++$j+1)." ";
\$\endgroup\$
1
\$\begingroup\$

C, 111 bytes

f(char*a, char*b){int l=strlen(a),k=1;while(*a){printf("%s\n",a);a[--l]=0;}while(b[k]) printf("%.*s\n",++k,b);}

Ungolfed test

#include <stdio.h>
#include <string.h>

f(char*a, char*b) {
  int l=strlen(a), k=1;
  while(*a) {
    printf("%s\n",a);
    a[--l]=0;
  }
  while(b[k])
    printf("%.*s\n",++k,b);
}

int main() {
  char a[10] = {0};
  char b[10] = {0};

  for (int i=0; i<5; ++i) {
    a[i] = 'a' + i;
    b[i] = 'a' + i*2;
  }

  f(&(a[0]), &(b[0]));
}
\$\endgroup\$
1
\$\begingroup\$

brainfuck, 162 bytes

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

Try it here

Input takes the two strings separated by a linefeed.

First program with brianfuck and first code golf so I'm sure there is plenty of optimization to be done. Had fun doing it though.

Ungolfed

,[>,] Read all input
++++++++++ Flag for 10
[                   Subtract 10 from each cell to flag space for blank
    [-<]            
    >
        [->]
        <
]
++++++++++ Flag for 10
[                   Add 10 back to each cell with value in it
    <[+<]<[+<]
    >[+>]>[+>]<---
]
<[<]<[<]>               goto first cell in first string string      

[                           Print first word subtracting one each time
    [.>]                    Print first string
    ++++++++++.----------   Print new line
    <[-]                    Kill last letter of first string
    <                       Back one
    [                       Move each first string character up one
          [->+<]
          <
    ]>>
]
>[<+>-]>                    Move to first letter of scond string back one goto second letter
[                               
    [<+>-]                  Move next letter back
    <[<]>                   Move to start of string
    [.>]                    Print string
    ++++++++++.----------   Print new line
    >
]
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Impressive first post! \$\endgroup\$ – Rɪᴋᴇʀ Sep 9 '16 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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