Cofnij i ponownie wpisz listę słów

38

Oto sposób cofania i ponownego wpisywania jednego łańcucha na drugi:

  1. Zacznij od pierwszego ciągu.
  2. Usuń znaki na końcu, aż wynik będzie prefiksem drugiego ciągu. (Może to zająć 0 kroków.)
  3. Dodaj znaki na końcu, aż wynik będzie równy drugiemu ciągowi. (Może to również wymagać 0 kroków.)

Na przykład ścieżka od fooabcdo fooxyzwygląda następująco:

fooabc
fooab
fooa
foo
foox
fooxy
fooxyz

Zadanie

Biorąc pod uwagę listę słów, napisz program, który cofa się i ponownie typuje swoją drogę od pustego łańcucha, do wszystkich kolejnych słów z listy, z powrotem do pustego łańcucha. Wyprowadza wszystkie łańcuchy pośrednie.

Na przykład, biorąc pod uwagę listę danych wejściowych ["abc", "abd", "aefg", "h"], dane wyjściowe powinny być:

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

h

Zasady

Możesz zwrócić lub wydrukować listę ciągów znaków lub pojedynczy ciąg znaków z wybranym ogranicznikiem. Opcjonalnie możesz dołączyć początkowe i końcowe puste ciągi. Dane wejściowe z pewnością zawierają co najmniej jedno słowo, a każde słowo może zawierać tylko małe litery ASCII ( a- z). Edycja: gwarantuje, że kolejne ciągi wejściowe nie będą sobie równe.

To jest ; najkrótszy kod w bajtach wygrywa.

Referencyjna implementacja w Pythonie 3: Wypróbuj online!

Lynn
źródło
4
@ rahnema1> napisz program, który backspace-i-typuje drogę z pustego łańcucha
Kritixi Lithos
3
Jaka byłaby wydajność ["abc","abc"]?
Kritixi Lithos
1
@Emigna Ups, to jest dokładnie to, ale w pętli! Więc zamierzam powiedzieć, że to duplikat tego.
Lynn,
4
@ Lynn To nie jest dokładnie to samo. Że nie obejmuje rozpoznawania typowych prefiksów, zawsze sprowadza się do jednej postaci.
Martin Ender
6
Przypadek testowy:a,abc,abcde,abc,a,abc,abcde
Zgarb

Odpowiedzi:

9

Perl, 43 bajty

42 bajty kodu + -nflagi.

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

Aby uruchomić:

perl -nE 'chop$@,say$@while!s/^$@//;s/./say$@.=$&/ge' <<< "abc
abd
aefg
h"
Dada
źródło
drukuje abc 3 razy
izabera
@izabera Po abcspowodowaniu 3-krotnego wydrukowania spacji pojawiła się spacja (ale tak naprawdę za pierwszym i trzecim razem bez spacji). Usunąłem to.
Dada
5

Java 8, 144 bajty

Ta jest podobna do implementacji referencyjnej, ale łączy dwie whilepętle. Jest to wyrażenie lambda akceptujące String[]parametr.

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++));}

Bez golfa

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++));
}

Podziękowanie

  • -38 bajtów dzięki sugestii lambda CAD97
Jakob
źródło
Czy nie jest tańszy w użyciu class Bzamiast interface B? Możesz uruchomić z klasy prywatnej pakietu. Rozważ także użycie lambda, ponieważ już określiłeś Java8.
97 CAD
@ CAD97 interface B{static void mainjest krótszy niż class B{public static void main.
Kevin Cruijssen
@ CAD97 Nie mogłem wymyślić sposobu, aby wprowadzić w to lambdy, ale dopiero wczoraj się o nich dowiedziałem. Jakieś pomysły?
Jakob
1
Ach, jestem zardzewiały. Powinieneś być w stanie to zrobić a->{/*your code*/}, który przypisze zmienną typu java.util.function.Consumer<String[]>. Jednak w tej chwili nie mogę przetestować.
97 CAD
1
@JakobCornell Domyślnie PPCG zezwala na pełne przesyłanie programu lub funkcji. W przypadku języków z funkcjami anonimowymi (lambda) sama anonimowa funkcja jest akceptowalną odpowiedzią (dlatego nie trzeba dołączać zmiennej, aby ją przechowywać). (Chociaż w pismach Java jest uprzejmy, aby zapewnić typ lambda.)
CAD97
4

Mathematica, 149 bajtów

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]]&
JungHwan Min
źródło
3

Siatkówka , 39 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.

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

Wypróbuj online!

Wejścia i wyjścia są listami oddzielonymi od linii. Dane wyjściowe obejmują początkowy i końcowy pusty ciąg.

Martin Ender
źródło
3

Galaretka , 31 29 26 bajtów

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

Wypróbuj online!

Jak to działa

⁷;ç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.
Dennis
źródło
2

Haskell , 102 93 91 90 bajtów

(?)=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
(""!).(++[""])

Ostatni wiersz to anonimowa funkcja, która pobiera i zwraca listę ciągów znaków. Wypróbuj online!

Wyjaśnienie

Moje rozwiązanie jest rekurencyjne. Po pierwsze, ?jest to funkcja pomocnicza: a?bdaje pierwsze length aznaki blub całość bjeśli ajest dłuższa. Następnie definiuję funkcję infix !. Chodzi o to, że a!xgdzie ajest ciąg znaków i xlista ciągów, tworzy ścieżkę od apierwszego ciągu xi wraca do końca x. W ostatnim wierszu definiuję anonimową funkcję, która dołącza pusty ciąg, a następnie stosuje !się do pustego ciągu i danych wejściowych.

Wyjaśnienie !:

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.
Zgarb
źródło
2

Python 2, 118 107 103 97 93 92 bajty

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

Dane wejściowe są podawane jako ['abc', 'abcdef', 'abcfed']lub jako [ "abc", "abcdef", "abcfed"].

Wersja 1: -11 bajtów. Podziękowania należą się @xnor za jego post na temat wskazówek golfowych w Pythonie, a @Lynn za znalezienie wskazówki dla mnie i dla mnie za bycie inteligentnym. Wprowadzono dwie zmiany: zamiast not s.startswith(i), użyłem s.find(i)i zamiast i!=sużyłem i>s.

Wersja 2: -4 bajty. Uznanie, że popełniłem naprawdę głupi błąd. Zamiast wcięcia pojedynczej tabulacji i podwójnej tabulacji użyłem wcięcia pojedynczej spacji i pojedynczej tabulacji.

Wersja 3: -6 bajtów. Podziękowania należą się @ @ mbomb007 za sugerowanie umieszczenia whiles w jednej linii. Naprawiłem również błąd, zmieniając s.find(i)na i.find(s).

Wersja 4: -4 bajty. Podziękowania dla @xnor za to, że nie musiałem przechowywać danych wejściowych w zmiennej.

Wersja 5: -1 bajt. Uznanie zasługuje na zrozumienie, że ['']jest to to samo, co [s]podczas dodawania go do danych wejściowych.

HyperNeutrino
źródło
Umieść whilekażdy z nich w jednej linii. Możesz także użyć <1zamiast not.
mbomb007
Niezła odpowiedź! Xnor ma dobrą wskazówkę, jak tego uniknąćstartswith .
Lynn
@ Lynn Och, dzięki za link! Znalazłem to naprawdę pomocne!
HyperNeutrino,
@ mbomb007 Przykro mi, ale nie rozumiem, co masz na myśli, umieszczając whiles w jednym wierszu. Masz na myśli while s.find(i):s=s[:-1];print s? Dziękuję również za sugestię <1, ale zmieniłem się na coś jeszcze krótszego dzięki jednej z porad xnor w wątku wskazówek Python.
HyperNeutrino,
@AlexL. Tak, włóż trochę czasu.
mbomb007
1

GNU M4, 228 lub 232 bajty¹

(¹ w zależności od tego, czy zakończyć plik, dnl\nczy nie - wciąż jestem nowy zarówno w golfie, jak i 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),$@)')

Dodatkowo można by zapisać 3 bajty, zastępując drugi argument „ substrod 0” pustym ciągiem, ale spowodowałoby to wiele ostrzeżeń na stderr.

Nie golfowany:

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

Stosowanie:

$ m4 <<<"include(\`backspace-golfed.m4')M(abc, abd, aefg, abcdefg, h)"
Kryminał
źródło
1

PHP, 116 111 101 83 bajtów

Uwaga: używa kodowania Windows-1252.

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

Uruchom tak:

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

Wyjaśnienie

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.

Poprawki

  • Zaoszczędzono 5 bajtów, używając trim($c^$w,"\0")zamiast sprawdzać dopasowanie podłańcucha $c&&strpos($w,$c)!==0.
  • Zaoszczędzono 2 bajty, używając ~ÿdo uzyskania łańcucha z bajtem NUL zamiast"\0"
  • Zaoszczędzono 8 bajtów, używając $c=$c.ÿ&$wsufiksu $cz następnym znakiem$w
  • Zaoszczędzono ogromne 18 bajtów, łącząc logikę 2 wewnętrznych pętli w jednej pętli
  • Naprawiono błąd związany z testem z komentarzy, bez zmiany liczby bajtów
aross
źródło
1

Partia, 296 291 bajtów

@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

Obliczenie wspólnego przedrostka było uciążliwe.

Neil
źródło
0

PHP, 153 bajty

okropnie długie :(

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
";}

Uruchom z php -nr '<ode>' <text1> <text2> ....

Tytus
źródło
0

JavaScript (ES6), 135 bajtów

Ciekawe wyzwanie! Zastosowanie: g(["abc", "abd", "aefg", "h"]). Nie mogłem zaoszczędzić żadnych bajtów, pisząc to jako jedną funkcję, więc są dwie. Nowe linie nie są uwzględnione w liczbie bajtów.

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])

Jestem pewien, że można to znacznie zmniejszyć. Dodanie wersji bez golfa później.

Chris M.
źródło
0

JavaScript, 98 bajtów

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++])}

Odpowiedź Javy Port of Jakob

SuperStormer
źródło