38
\$\begingroup\$

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 (az). Edit: consecutive strings in the input are guaranteed not to equal each other.

This is ; shortest code in bytes wins.

A reference implementation in Python 3: Try it online!

\$\endgroup\$
  • 4
    \$\begingroup\$ @rahnema1 > write a program that backspace-and-retypes its way from the empty string \$\endgroup\$ – Kritixi Lithos Jan 15 '17 at 19:11
  • 3
    \$\begingroup\$ How would the output be for ["abc","abc"]? \$\endgroup\$ – Kritixi Lithos Jan 15 '17 at 19:13
  • 1
    \$\begingroup\$ @Emigna Oops, this is exactly that but in a loop! So I’m gonna go ahead and say this is a duplicate of that. \$\endgroup\$ – Lynn Jan 15 '17 at 19:55
  • 4
    \$\begingroup\$ @Lynn It's not exactly the same thing. That one doesn't include recognising the common prefixes, it always goes down to one character. \$\endgroup\$ – Martin Ender Jan 15 '17 at 20:33
  • 6
    \$\begingroup\$ Test case: a,abc,abcde,abc,a,abc,abcde \$\endgroup\$ – Zgarb Jan 15 '17 at 21:09

14 Answers 14

5
\$\begingroup\$

Pyth, 25 23 bytes

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

Try it online.

\$\endgroup\$
9
\$\begingroup\$

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"
\$\endgroup\$
  • \$\begingroup\$ this prints abc 3 times \$\endgroup\$ – izabera Jan 16 '17 at 12:55
  • \$\begingroup\$ @izabera There was a space after abc causing it to be printed 3 times (but actually, the first and third time it was without the space). I removed it. \$\endgroup\$ – Dada Jan 16 '17 at 13:15
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Isn't it cheaper to use class B instead of interface B? You can run from a package-private class. Also, consider using a lambda as you've already specified Java8. \$\endgroup\$ – CAD97 Jan 16 '17 at 7:00
  • \$\begingroup\$ @CAD97 interface B{static void main is shorter than class B{public static void main. \$\endgroup\$ – Kevin Cruijssen Jan 16 '17 at 7:52
  • \$\begingroup\$ @CAD97 I couldn't think of a way to bring lambdas into this, but I only just learned about them yesterday. Any ideas? \$\endgroup\$ – Jakob Jan 16 '17 at 17:03
  • 1
    \$\begingroup\$ Ah, I'm rusty. You should be able to do a->{/*your code*/}, which will assign to a variable of type java.util.function.Consumer<String[]>. I can't test at the moment, however. \$\endgroup\$ – CAD97 Jan 16 '17 at 17:30
  • 1
    \$\begingroup\$ @JakobCornell By default PPCG allows full program or function submissions. For languages with anonymous functions (lambda), the anonymous function on its own is an acceptable answer (thus you don't have to include the variable to store it to). (Though in Java submissions it's courteous to provide the type of the lambda.) \$\endgroup\$ – CAD97 Jan 16 '17 at 18:24
4
\$\begingroup\$

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]]&
\$\endgroup\$
3
\$\begingroup\$

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.

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

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.
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Put the whiles each on a single line. Also, you can use <1 instead of not. \$\endgroup\$ – mbomb007 Jan 17 '17 at 20:23
  • \$\begingroup\$ Nice answer! There’s a nice tip by xnor on how to avoid startswith. \$\endgroup\$ – Lynn Jan 17 '17 at 21:08
  • \$\begingroup\$ @Lynn Oh, thanks for the link! I found it really helpful! \$\endgroup\$ – HyperNeutrino Jan 18 '17 at 1:24
  • \$\begingroup\$ @mbomb007 I'm sorry, I don't quite get what you mean by putting the whiles on a single line. Do you mean like while s.find(i):s=s[:-1];print s? Also, thanks for the suggestion about <1, but I've changed to something even shorter thanks to one of xnor's tips on the Python tips thread. \$\endgroup\$ – HyperNeutrino Jan 18 '17 at 1:30
  • \$\begingroup\$ @AlexL. Yes, put the while's like that. \$\endgroup\$ – mbomb007 Jan 18 '17 at 3:29
1
\$\begingroup\$

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)"
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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> ....

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

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.