Najkrótszy unikalny podciąg

14

Biorąc pod uwagę (na STDIN, jako argumenty wiersza poleceń lub jako argumenty funkcji) dwa różne niepuste ciągi, znajdź i zwróć najkrótszy ciąg pierwszego ciągu, który nie jest ciągiem drugiego. Jeśli taki podciąg nie istnieje, możesz zwrócić pusty ciąg, zwrócić dowolny ciąg, który nie jest podciągiem oryginalnego ciągu, lub zgłosić wyjątek. Jeśli wracasz z funkcji, możesz również zwrócić null (lub niezdefiniowany, None, itp.) W tym przypadku. Jeśli kilka takich podciągów jest powiązanych w najkrótszym czasie, możesz zwrócić jeden z nich.

Ciągi znaków mogą zawierać dowolne znaki ascii do wydrukowania.

Dane wejściowe podane na STDIN będą podawane z jednym ciągiem w każdej linii. Na żądanie można dodać jedną pustą linię na końcu danych wejściowych.

To jest golf golfowy, więc wygrywa najkrótszy prawidłowy program.

NIEKTÓRE PRZYPADKI TESTOWE

WEJŚCIE:

STRING ONE
STRING TWO

WYNIK:

E

WEJŚCIE:

A&&C
A&$C

WAŻNE PRODUKTY:

&&
&C

WEJŚCIE:

(Dwa losowo generowane ciągi 80-literowe)

QIJYXPYWIWESWBRFWUHEERVQFJROYIXNKPKVDDFFZBUNBRZVUEYKLURBJCZJYMINCZNQEYKRADRYSWMH
HAXUDFLYFSLABUCXUWNHPSGQUXMQUIQYRWVIXGNKJGYUTWMLLPRIZDRLFXWKXOBOOEFESKNCUIFHNLFE

WSZYSTKIE WAŻNE PRODUKTY:

AD
BJ
BR
CZ
DD
EE
ER
EY
EY
FF
FJ
FW
FZ
HE
IJ
IN
IW
JC
JR
JY
KL
KP
KR
KV
LU
MH
MI
NB
NQ
OY
PK
PY
QE
QF
QI
RA
RB
RF
RO
RV
RY
RZ
SW
UE
UH
UN
UR
VD
VQ
VU
WB
WE
WI
WU
XN
XP
YI
YK
YK
YM
YS
YW
YX
ZB
ZJ
ZN
ZV
SuperJedi224
źródło
1
najkrótszy czy najdłuższy?
Leaky Nun
@FryAmTheEggman W takim razie powinienem jeszcze opublikować swoje rozwiązanie ...
Leaky Nun
„Jeden ciąg w każdej linii” z cudzysłowami lub bez?
Leaky Nun
1
Czy możemy wziąć tablicę ciągów?
Dennis
czy „B” jest podciągiem „aBc”?
downrep_nation

Odpowiedzi:

4

Brachylog , 23 bajty

:1foh.,{,.[A:B]hs?'~sB}

Działa na starym transpilerze Java. Oczekuje, że dwa ciągi na liście jako dane wejściowe, ujednolica dane wyjściowe z podłańcuchem. Jeśli nie znaleziono żadnego podłańcucha, zwraca false.

Niestety nie zakodowałem jeszcze podzbioru wbudowanego w nowy transpiler Prolog.

Wyjaśnienie

:1f               Find all bindings which satisfy predicate 1 with that binding as input and
                  with the Input of the main predicate as output.
   oh.,           Order that list of bindings, and unify the output with the first one.

{
 ,.[A:B]          Unify the output with the list [A,B]
        hs?       Unify the input with a subset of A
           '~sB   Check that no subset of B can be unified with the input
               }
Fatalizować
źródło
4

Python, 119 115 91

lambda a,b:[a[m:m+n]for n in range(1,len(a)+1)for m in range(len(a))if a[m:m+n]not in b][0]

Przypadki testowe:

| Input 1  | Input 2     | Output        |
|----------+-------------+---------------|
| 'abcd'   | 'abc'       |  'd'          |
| 'abcd'   | 'dabc'      |  'cd'         |
| 'abcd'   | 'dcbabbccd' |  'abc'        |
| 'abcdf'  | 'abcdebcdf' |  'abcdf'      |
| 'abc'    | 'abc'       |  (IndexError) |

Pracuję nad tym, aby był krótszy, ale to mój instynkt mózgu. Jeszcze nie bardzo golfista.

Dzięki @ user81655 i @NonlinearFruit za dodatkowe bajty.

Edytuj :

Dang. Próbowałem tego kodu:

def z(a,b):
 for s in [a[m:m+n]for n in range(1,len(a)+1)for m in range(len(a)-n+1)]:
  if s not in b:return s
 return''

Pomyślałem, że jest o kilka bajtów krótszy. Okazuje się, że był o 1 bajt dłuższy niż to, co miałem przed edycją.

Taylor Lopez
źródło
Nie wiem, dużo Python, ale być może nie można (r=range)(1,len(a)+1)wtedy używać r?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Nie mogę tego zrobić w ten sposób. Jeśli przypiszę rangedo rw powyższej linii, faktycznie dodaje bajt. Dobry pomysł. Prawdopodobnie istnieje krótszy sposób na iterację przez podciągi.
Taylor Lopez
range(1,len(a))i range(len(a)-1)powinno działać, prawda? Myślę też, że użycie znaku tabulacji dla wcięcia dwóch spacji uratuje bajt.
user81655,
Nie, z range(1,len(a))czwartym rzutem testowym kończy się niepowodzeniem, ponieważ nie wypróbuje pełnego ciągu; przejdzie tylko do długości łańcucha - 1. I z range(len(a)-1), pierwszy przypadek testowy nie powraca 'cd'zamiast po prostu 'd'. Coś jednak może tam być.
Taylor Lopez
Przepraszamy, nie znam Pythona i założyłem, że zakresy są włącznie. W takim przypadku spróbuj range(1,len(a)+1)i range(len(a)).
user81655,
3

Python, 87 86 bajtów

lambda s,t,e=enumerate:[s[i:i-~j]for j,_ in e(s)for i,_ in e(s)if(s[i:i-~j]in t)<1][0]

Jeśli istnieje, zwróci skrajnie lewy ze wszystkich najkrótszych unikalnych podciągów.

Jeśli nie ma unikalnego podłańcucha, zgłaszany jest błąd IndexError .

Przetestuj na Ideone .

Dennis
źródło
Tu jest. Czekałem, aż ktoś zabije moją implementację inną niż lambda. nice lol
Taylor Lopez
Myślę, że można zrobić to krócej, dostarczając opcjonalny drugi argument do enumeraterozpoczęcia jw i+1.
user2357112 obsługuje Monikę
@ user2357112 To niestety wywołuje błąd NameError . Kod jnajpierw definiuje i.
Dennis
@Dennis: Tak, ale nie musi. Możesz zmienić kolejność pętli.
użytkownik2357112 obsługuje Monikę
1
@ user2357112 Jeśli zmienię kolejność pętli, pierwszy znaleziony podciąg może nie być najkrótszy. Po prostu zamiana zamówień zwraca 'ab'dane wejściowe 'abc','aaa'.
Dennis
2

Python, 82 bajty

g=lambda u:{u}|g(u[1:])|g(u[:-1])if u else{''}
f=lambda s,t:min(g(s)-g(t),key=len)

Zastosowanie: f('A&&C', 'A&$C')-> zwraca'&&'

Podnosi ValueError, jeśli nie ma odpowiedniego podciągu.

Wyjaśnienie:

g=lambda u:{u}|g(u[1:])|g(u[:-1])if u else{''}rekurencyjnie tworzy zestaw podciągów z u f=lambda s,t:min(g(s)-g(t),key=len)najkrótszych podciągów z różnicy w zestawie

RootTwo
źródło
2

JavaScript (ES6), 79 bajtów

f=
(a,b)=>[...a].some((_,i,c)=>c.some((_,j)=>b.indexOf(s=a.substr(j,i+1))<0))?s:''
<div oninput=o.textContent=f(a.value,b.value)><input id="a"/><input id="b"/><pre id=o>

Jeśli zwracanie falsejest dopuszczalne, zapisz 2 bajty, używając &&szamiast ?s:''.

Neil
źródło
1

JavaScript (Firefox), 80 bajtów

solution=

a=>b=>[for(_ of(i=0,a))for(_ of(j=!++i,a))if(b.includes(s=a.substr(j++,i)))s][0]

document.write("<pre>"+
[ [ "test", "best" ], [ "wes", "west" ], [ "red", "dress" ] ]
.map(c=>c+": "+solution(c[0])(c[1])).join`\n`)

Test działa tylko w przeglądarce Firefox. Zwraca, undefinedjeśli nie ma podciągu.

użytkownik 81655
źródło
Ciągi mogą zawierać drukowalne znaki ASCII, takie jak \ lub inne metaznaki RegExp, ale jeśli ograniczasz się do Firefoksa, dlaczego nie użyć b.includeszamiast tego?
Neil
@Neil Pytanie nie mówiło, że ciągi mogą być dowolnymi postaciami wcześniej, ale dzięki za poinformowanie mnie! Zaktualizowano do użycia includes.
user81655
1
Fragment testowy wyrzucaSyntaxError: unexpected token 'for'
NoOneIsHere
@NoOneIsHere Oto błąd, który wystąpi, jeśli nie korzystasz z przeglądarki Firefox ...
user81655,
1

Siatkówka , 37 bajtów

M!&`\G(.+?)(?!.*¶.*\1)
O$#`.+
$.&
G1`

Dane wyjściowe są puste, jeśli nie znaleziono poprawnego podłańcucha w A.

Wypróbuj online! (Nieznacznie zmodyfikowano, aby uruchamiało kilka przypadków testowych jednocześnie. Format wejściowy jest faktycznie oddzielony od linii, ale zestawy testów najłatwiej jest napisać z jednym przypadkiem w linii. Środowisko testowe przekształca przestrzeń w kanał przed rozpoczęciem właściwego kodu.)

Wyjaśnienie

M!&`\G(.+?)(?!.*¶.*\1)

Dla każdej możliwej pozycji początkowej w Adopasuj najkrótszy podciąg, który nie pojawia się w B. &Jest dla nakładających się mecze, takie, które rzeczywiście staramy każdą pozycję wyjściową, nawet jeśli jest to mecz dłużej niż jeden znak. W \Ggwarantuje, że nie pominąć żadnej pozycji - w szczególności w ten sposób mamy do przystanku przy wysuw, tak że nie mamy dodatkowe mecze od Bsiebie. Powód, dla którego to nie psuje, jest w rzeczywistości dość subtelny: ponieważ jeśli jest pozycja początkowaA której nie możemy znaleźć żadnego prawidłowego podłańcucha, oznacza to również awarię, która spowoduje, że \Gprzestaniesz sprawdzać dalsze pozycje. Jeśli jednak (z bieżącej pozycji początkowej) wszystkie podciągi pojawią się wB, podobnie jak wszystkie podciągi, które zaczynają się bardziej na prawo od bieżącej pozycji, więc ich odrzucenie nie stanowi problemu (i faktycznie poprawia wydajność).

Ze względu na M!konfigurację wszystkie te mecze zostaną zwrócone ze sceny, połączone z liniami.

O$#`.+
$.&

To sortuje linie poprzedniego wyniku według długości. Odbywa się to poprzez dopasowanie linii do .+. Następnie $aktywuje formę „sortowania według”, dzięki czemu dopasowanie jest zastępowane $.&określaniem kolejności sortowania. $.&Sama zastępuje mecz z jego długości. Na koniec #opcja mówi Retinie, aby sortowała numerycznie (w przeciwnym razie traktowałaby powstałe liczby jako łańcuchy i sortowała je leksykograficznie).

G1`

Wreszcie, po prostu zachowujemy tylko pierwszą linię, używając etapu grep z pustym wyrażeniem regularnym (który zawsze pasuje) i limitem 1.

Martin Ender
źródło
1

Perl, 87 85

sub{(grep{$_[1]!~/\Q$_/}map{$}=$_;map{substr($_[0],$_,$})}@}}(@}=0..length$_[0]))[0]}

Jest to anonimowa funkcja, która zwraca pierwsze (według pozycji) najkrótszych podciągów $_[0], które nie występują w $_[1]lub undefjeśli takie podciąg nie istnieje.

Program testowy z ciągami zaczerpniętymi z odpowiedzi @ iAmMortos, przetestowany w Perlu 5.22.1:

#!/usr/bin/perl -l
use strict;
use warnings;

my $f = <see above>;
print $f->('abcd', 'abc');
print $f->('abcd', 'dabc');
print $f->('abcd', 'dcbabbccd');
print $f->('abcdf', 'abcdebcdf');
print $f->('abc', 'abc');
hvd
źródło
1

Haskell, 72 bajty

import Data.Lists
a#b=argmin length[x|x<-powerslice a,not$isInfixOf x b]

Przykład użycia: "abcd" # "dabc"-> "cd".

Prosta implementacja: zbuduj wszystkie podciągi ai zachowaj te, które się nie pojawiają b. argminzwraca element listy, który minimalizuje funkcję otrzymują 2nd argument tutaj: length.

nimi
źródło
Nie wiedziałem o argmin! Wydaje się to niezwykle przydatne.
Zgarb
0

Pyth - 9 6 bajtów

h-Fm.:

Wypróbuj online tutaj .

Maltysen
źródło
Przekreślony 9 to wciąż 9
kot
Chciałbym wiedzieć, jak to działa.
mroman
@mroman the.: z jednym argumentem wszystkie substraty. Więc odwzorowuję to na obu ciągach, a następnie składam diff zgodnie z ustawieniami, więc mam wszystkie podłańcuchy pierwszego z tych drugich, a następnie wybieram pierwszy, który jest najmniejszy, ponieważ: jest posortowany.
Maltysen
0

C #, 152 bajty

string f(string a,string b){int x=a.Length;for(int i=1;i<=x;i++)for(int j=0;j<=x-i;j++){var y=a.Substring(j,i);if(!b.Contains(y))return y;}return null;}
downrep_nation
źródło
0

Rubinowy, 70 bajtów

Zbiera wszystkie podciągi o określonej długości z pierwszego ciągu, a jeśli istnieje taki, którego nie ma w drugim ciągu, zwróć go.

->a,b{r=p;(1..l=a.size).map{|i|(0...l).map{|j|b[s=a[j,i]]?0:r||=s}};r}
Wartość tuszu
źródło
0

Burleska - 26 bajtów

W tej chwili najkrótszą drogą, jaką mogę wymyślić, jest:

lnp^sujbcjz[{^p~[n!}f[-][~
mroman
źródło
0

Japt , 14 bajtów

Êõ!ãU c k!èV g

Wypróbuj online!

Zwraca, undefinedjeśli nie ma prawidłowego podłańcucha . Różni się to od zwracania ciągu „niezdefiniowany” , chociaż różnica jest widoczna tylko z powodu flagi -Q.

Wyjaśnienie:

Ê                 :Length of the first input
 õ                :For each number in the range [1...length]:
  !ãU             : Get the substrings of the first input with that length
      c           :Flatten to a single array with shorter substrings first
        k         :Remove ones which return non-zero to:
         !èV      : Number of times that substring appears in second input
             g    :Return the shortest remaining substring
Kamil Drakari
źródło
0

Japt -h, 11 bajtów

à f@øX «VøX

Spróbuj

                :Implicit input of strings U & V
à               :All combinations of U
  f@            :Filter each as X
    øX          :  Does U contain X?
       «        :  Logical AND with the negation of
        VøX     :  Does V contain X?
                :Implicit output of last element
Kudłaty
źródło