Backspace-and-retype a list of words

Question

Here’s how to backspace-and-retype from one string to another:

1. Start from the first string.
2. Remove characters at the end until the result is a prefix of the second string. (This may take 0 steps.)
3. Add characters at the end until the result equals the second string. (This may take 0 steps, too.)

For example, the path from fooabc to fooxyz looks like:

fooabc
fooab
fooa
foo
foox
fooxy
fooxyz

Task

Given a list of words, write a program that backspace-and-retypes its way from the empty string, to all of the words in the list in succession, back to the empty string. Output all intermediate strings.

For example, given the input list ["abc", "abd", "aefg", "h"], the output should be:

a
ab
abc
ab
abd
ab
a
ae
aef
aefg
aef
ae
a

h

Rules

You may return or print a list of strings, or a single string with some delimiter of choice. You may optionally include the initial and final empty strings. The input is guaranteed to contain at least one word, and each word is guaranteed to contain only lowercase ASCII letters (a–z). Edit: consecutive strings in the input are guaranteed not to equal each other.

This is code-golf; shortest code in bytes wins.

A reference implementation in Python 3: Try it online!

Answer 1

Perl, 43 bytes

42 bytes of code + -n flags.

chop$@,say$@while!s/^$@//;s/./say$@.=$&/ge

To run it:

perl -nE 'chop$@,say$@while!s/^$@//;s/./say$@.=$&/ge' <<< "abc
abd
aefg
h"

Answer 2

Pyth, 25 23 bytes

V+QkWxNk
=Pk)
M>._Nl~kN

Try it online.

Answer 3

Java 8, 144 bytes

This one is similar to the reference implementation but combines the two while loops. It's a lambda expression accepting a String[] parameter.

a->{String c="";int l=0,i;for(String w:a)while((i=w.indexOf(c))!=0||!c.equals(w))System.out.println(c=i!=0?c.substring(0,--l):c+w.charAt(l++));}

Ungolfed

a -> {
    String c = "";
    int l = 0, i;
    for (String w : a)
        while ((i = w.indexOf(c)) != 0 || !c.equals(w))
            System.out.println(c = i != 0 ? c.substring(0, --l) : c + w.charAt(l++));
}

Acknowledgments

• -38 bytes thanks to CAD97's lambda suggestion

Answer 4

Mathematica, 149 bytes

Reap[Fold[n=NestWhile;s=StringMatchQ;r=StringReplace;n[k=#2;Sow@r[k,#~~a_~~___:>#<>a]&,n[Sow@r[#,a___~~_:>a]&,#,!s[k,#~~___]&],k!=#&]&,"",#]][[2,1]]&

Answer 5

Retina, 39 bytes

Byte count assumes ISO 8859-1 encoding.

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

Try it online!

Input and output are linefeed-separated lists. Output does include the leading and trailing empty string.

Answer 6

Jelly, 31 29 26 bytes

⁷œ|;\
ÇṚðfḢṭḟ;ḟ@ḊðÇ}
⁷;ç2\

Try it online!

How it works

⁷;ç2\           Main link. Argument: A (string array)

⁷;              Prepend a linefeed to A. 
                This is cheaper than prepending an empty string.
  ç2\           Reduce all overlapping pairs by the second helper link.


ÇṚðfḢṭḟ;ḟ@ḊðÇ}  Second helper link. Arguments: s, t (strings)

Ç               Call the first helper link with argument s.
 Ṛ              Reverse the results.
            Ç}  Call the first helper link with argument t.
  ð        ð    Combine everything in between into a dyadic chain, and call it
                with the results to both sides as arguments.
                Let's call the arguments S and T.
   f            Filter; get the common strings of S and T.
    Ḣ           Head; select the first one.
      ḟ         Filterfalse; get the strings in S that do not appear in T.
     ṭ          Tack; append the left result to the right one.
        ḟ@      Filterfalse swap; get the strings in T that do not appear in S.
       ;        Concatenate the results to both sides.
          Ḋ     Dequeue; remove the first string.


⁷œ|;\           First helper link. Argument: s (string)

⁷œ|             Linefeed multiset union; prepend a linefeed to s unless it already
                has a linefeed in it (the first string does).
   ;\           Concatenate cumulative reduce; generate all prefixes of the result.

Answer 7

GNU M4, 228 or 232 bytes¹

(¹ depending on whether to end the file with dnl\n or not—I'm still new to both golfing and M4)

define(E,`ifelse(index($2,$1),0,`T($1,$2)',`$1
E(substr($1,0,decr(len($1))),$2)')')define(T,`ifelse($1,$2,,`$1
T(substr($2,0,incr(len($1))),$2)')')define(K,`ifelse($2,,$1,`E($1,$2)K(shift($@))')')define(M,`K(substr($1,0,1),$@)')

Additionally, 3 bytes could be saved by replacing the second argument for substr from 0 to the empty string, but that would produce a lot of warnings on stderr.

Ungolfed:

define(erase_til_prefix, `dnl arguments: src dst; prints src and chops one char off of it until src == dst, at which point it calls type_til_complete instead
ifelse(dnl
index($2, $1), 0, `type_til_complete($1, $2)',dnl
`$1
erase_til_prefix(substr($1, 0, decr(len($1))), $2)dnl
')')dnl
define(type_til_complete, `dnl arguments: src dst; types src, does not type `dst' itself
ifelse(dnl
$1, $2, ,dnl
`$1
type_til_complete(substr($2, 0, incr(len($1))), $2)'dnl
)')dnl
define(main_, `dnl
ifelse(dnl
$2, , $1, dnl no arguments left
`erase_til_prefix($1, $2)main_(shift($@))'dnl
)')dnl
define(main, `main_(substr($1, 0, 1), $@)')dnl

Usage:

$ m4 <<<"include(\`backspace-golfed.m4')M(abc, abd, aefg, abcdefg, h)"

Answer 8

Haskell, 102 93 91 90 bytes

(?)=take.length
a!x@(b:c)|a==b=b!c|a/=a?b=a:init a!x|d<-'?':a=a:d?b!x
_!x=x
(""!).(++[""])

The last line is an anonymous function, which takes and returns a list of strings. Try it online!

Explanation

My solution is recursive. First, ? is a helper infix function: a?b gives the first length a characters of b, or the whole of b if a is longer. Next I define an infix function !. The idea is that a!x, where a is a string and x a list of strings, produces the path from a to the first string in x and recurses to the tail of x. On the final line I define an anonymous function that appends the empty string, then applies ! to the empty string and the input.

Explanation of !:

a!x@(b:c)        -- a!x, where x has head b and tail c:
  |a==b          -- If a equals b,
    =b!c         -- recurse to x.
  |a/=a?b        -- If a is not a prefix of b,
    =a:          -- produce a and
    init a!x     -- continue with one shorter prefix of a.
  |              -- Otherwise a is a proper prefix of b.
   d<-'?':a      -- Let d be a with an extra dummy element,
    =a:          -- produce a and
    d?b!x        -- continue with one longer prefix of b.
_!x=x            -- If x is empty, return x.

Answer 9

Python 2, 118 107 103 97 93 92 bytes

s=''
for i in input()+[s]:
 while i.find(s):s=s[:-1];print s
 while i>s:s+=i[len(s)];print s

Input is given as ['abc', 'abcdef', 'abcfed'], or as ["abc", "abcdef", "abcfed"].

Revision 1: -11 bytes. Credit goes to @xnor for his post on Python golfing tips, and to @Lynn for finding the tip for me, and to me for being smart. Two changes were made: Instead of not s.startswith(i), I used s.find(i), and instead of i!=s I used i>s.

Revision 2: -4 bytes. Credit goes to me realizing I made a really dumb mistake. Instead of using single-tab and double-tab indentation, I used single-space and single-tab indentation.

Revision 3: -6 bytes. Credit goes to @mbomb007 for suggesting to put the whiles on a single line. I also fixed a bug by changing s.find(i) to i.find(s).

Revision 4: -4 bytes. Credit goes to @xnor for realizing that I didn't need to store the input in a variable.

Revision 5: -1 byte. Credit goes to me for realizing that [''] is the same thing as [s] when adding it to the input.

Answer 10

PHP, 116 111 101 83 bytes

Note: uses Windows-1252 encoding.

for(;$w=$argv[++$i];)for(;$c!=$w;)echo$c=($c^$c^$w)==$c?$c.ÿ&$w:substr($c,0,-1),~õ;

Run like this:

php -r 'for(;$w=$argv[++$i];)for(;$c!=$w;)echo$c=($c^$c^$w)==$c?$c.ÿ&$w:substr($c,0,-1),~õ;' -- abc abd aefg h 2>/dev/null
> a
> ab
> abc
> ab
> abd
> ab
> a
> ae
> aef
> aefg
> aef
> ae
> a
>
> h

Explanation

for(                       # Outer loop.
  ;
  $w=$argv[++$i];          # Loops over the input words.
)
  for(                     # Second inner loop.
    ;
    $c!=$w;                # Loop until the word was output.
  )
    echo $c=
      ($c^$c^$w)==$c?      # Check if last output string is a substring
                           # match with the next word to output.
        $c.ÿ&$w:           # ... If yes, suffix the string with the next
                           # char of the word, and output the result.
        substr($c,0,-1),   # ... If not, remove a char and output.
      ~õ;                  # Output newline.

Tweaks

• Saved 5 bytes by using trim($c^$w,"\0") to check for substring match instead of $c&&strpos($w,$c)!==0.
• Saved 2 bytes by using ~ÿ to yield a string with a NUL byte instead of "\0"
• Saved 8 bytes by using $c=$c.ÿ&$w to suffix $c with the next char of $w
• Saved a massive 18 bytes by combining the logic of the 2 inner loops in a single loop
• Fixed a bug with a testcase from the comments, no change in byte count

Answer 11

Batch, 296 291 bytes

@echo off
set f=
set t=%1
:t
set f=%f%%t:~,1%
set t=%t:~1%
echo(%f%
if not "%t%"=="" goto t
shift
set t=%1
set s=%f%
set p=
:h
if %s:~,1%==%t:~,1% set p=%p%%t:~,1%&set s=%s:~1%&set t=%t:~1%&goto h
:b
set f=%f:~,-1%
echo(%f%
if not "%f%"=="%p%" goto b
if not "%1"=="" goto t

Computing the common prefix was cumbersome.

Answer 12

Pip, 33 30 bytes

FsgAExTyQsYPyQs@<#y?y.s@#y;@<y

Try it online!

Explanation

                                g is list of cmdline args; x & y are "" (implicit)
Fs                              For each s in
  gAEx                          g with an empty string appended:
      TyQs                       Do this till y equals s:
              s@<                 Get the prefix of s
                 #y               having the same length as y
            yQ                    and check if it equals y
                   ?              If so (y is a prefix of s), calculate:
                    y.             y, concatenated with
                      s@           the character in s at index
                        #y         len(y)
                          ;       If not, calculate:
                           @<y     y without its last character
          YP                      Print that quantity and yank it back into y

Answer 13

PHP, 153 bytes

awfully long :(

for($s=$argv[$k=1];$t=$argv[++$k];){for(;$s>""&&strstr($t,$s)!=$t;$s=substr($s,0,-1))echo"$s
";for($i=strlen($s);$s<$t;$s.=$t[$i++])echo"$s
";echo"$s
";}

Run with php -nr '<ode>' <text1> <text2> ....

Answer 14

JavaScript (ES6), 135 bytes

Interesting challenge! Usage: g(["abc", "abd", "aefg", "h"]). I couldn't seem to save any bytes by writing this as one function, so it's two. Newlines not included in byte count.

f=a=>console.log(([,...z]=[x,y]=a)[0])||
y?f(a=(x==y.slice(0,-1))?z:([y.match(x)
?x+y[x.length]:x.slice(0,-1),...z])):1;
g=a=>f(['',...a])

I'm sure this can be reduced a lot more. Will add ungolfed version later.

Answer 15

Javascript, 98 bytes

a=>{c="",l=0;for(w of a)while((i=w.indexOf(c))!=0||c!=w)alert(c=i!=0?c.substring(0,--l):c+w[l++])}

Port of Jakob's Java answer