Biorąc pod uwagę ciąg znaków s
i tablicę / listę l
, określ, czy s
można wykonać z części l
.
Na przykład, jeśli ciąg jest, "Hello, world!"
a lista jest [' world!', 'Hello,']
, to program / funkcja powinna zwrócić prawdziwą wartość, ponieważ można ustawić listę w celu utworzenia ciągu. Poniższa lista będzie również zwrócić wartość truthy: ['l', 'He', 'o, wor', 'd!']
. Wyobraź sobie 'l'
wypełnienie tam, gdzie jest potrzebne. Tak, możesz powtórzyć elementy listy, aby utworzyć ciąg. Jeśli nie może utworzyć ciągu, powinien zwrócić wartość fałszowania. Obowiązują standardowe metody IO, standardowe luki.
Przypadki testowe:
Input (In the form of s, l)
Output (1 if possible, 0 if impossible)
"Hello, world!", ["l", "He", "o, wor", "d!"]
1
"la lal al ", ["la", " l", "al "]
1
"this is a string", ["this should return falsy"]
0
"thi is a string", ["this", "i i", " a", " string"]
0
"aaaaa", ["aa"]
0
"foo bar foobar", ["foo", "bar", " ", "spam"]
1
"ababab", ["a","ba","ab"]
1
"", ["The string can be constructed with nothing!"]
1
code-golf
string
decision-problem
subsequence
Towarzyszu SparklePony
źródło
źródło
"ababab", ["a","ba","ab"]
Odpowiedzi:
Brachylog , 8 bajtów
Wypróbuj online!
To jest naprawdę powolne. Zajęło około 37 sekund na „Witaj, świecie!” test skrzynki na moim komputerze i przekroczony limit czasu w TIO.
Spowoduje to przejście ciągu przez zmienną wejściową i listę przez zmienną wyjściową
Wyjaśnienie
źródło
["la", " l", "al "]
jako lista zakończyła się na moim komputerze i poprawnie odpowiedziałafalse.
po 6800 sekundach, i „tylko” 113 miliardów wniosków.Mathematica, 29 bajtów
Wyjaśnienie:
Graniczne rozwiązanie oszukiwania, 21 bajtów
Ponieważ Mathematica jest symbolicznym językiem programowania, nie ma * różnicy między wyrażeniami
List[a,b,...]
iAlternatives[a,b,...]
innymi, niż sposób, w jaki oddziałują one z innymi symbolami i sposób ich wyświetlania ({a,b,...}
ia|b|...
odpowiednio). Przy stosowaniu w drugim argumencieStringMatchQ
, AnAlternatives
wyrażenie jest traktowany jako wzorzec strun, a zatem możemy zapisać8
bajtów ponad mojego powyższego roztworu poprzez drugi argument jakoAlternatives
wyrazu.* Technicznie
List
jest równieżLocked
, co uniemożliwia użytkownikom wprowadzanieUnprotect
go i zmianę jego zachowania.źródło
{x,y,z}
jest traktowany tak samo, jak wx|y|z
przypadku dopasowania wzorca ciągu. Myślę, że możesz zastąpić""|##&@@#2..
tylko#2..
.Pyth, 23 bajty
Przyjmuje dane wejściowe jak
[['string'],['list', 'of', 'parts']]
. Dane wyjściowe to pusta lista lub lista z wartościami w środku. W Pyth lista zawierająca cokolwiek, nawet łańcuch zerowy (['']
), ma wartość true.Wypróbuj online!
Wyjaśnienie:
To rozwiązanie nieustannie próbuje usunąć każdą możliwą część z początku łańcucha i śledzi, jakie wartości musi jeszcze przejrzeć.
Jeśli spojrzymy na wartość
G
w przypadku testowym[['ababab'],['a','ba','ab']]
po każdej iteracji pętli while, otrzymamy:A w przypadku testowym
[['aaaaa'],['aa']]
otrzymujemy:Utworzyłem inny przypadek testowy,
[['aaaaaa'],['a','aa','aaa']]
a wynik był następujący:Lista wyjściowa zawiera garść śmieci, ale wciąż jest to prawdziwa wartość.
źródło
Perl 5 , 39 bajtów
38 bajtów kodu +
-p
flaga.Wypróbuj online!
Dla danych wejściowych
"Hello, world!", ["l", "He", "o, wor", "d!"]
(faktycznie oddzielonych znakami nowej linii) konstruuje wzórl|He|o, wor|d!|
(dzięki metaznakom, dzięki\Q..\E
), a następnie sprawdza, czy pierwszy ciąg znaków pasuje do tego wzorca/^($v)*$/
.W TryItOnline zauważ, że musi być końcowy nowy wiersz.
źródło
undef
jest wartością fałszowania zwracaną przez większość wbudowanych. A kiedy go drukujesz, w rzeczywistości nic nie drukuje. I właśnie to robię. Drukowanie „1/0” jest naturalne dla języków podobnych do C, ale dla Perla „1 / undef” jest naturalnym sposobem.PHP, 69 bajtów
Przypadki testowe
źródło
["", ["The string can be constructed with nothing!"]]
Python 2, 141 bajtów
Wypróbuj online!
Niezwykle nieefektywny. Limit czasu pierwszego przypadku testowego dla TIO.
źródło
JavaScript (ES6), 59 bajtów
Pobiera tablicę podciągów
a
i ciąg znakóws
w składni curry(a)(s)
. Zwracafalse
/true
.Skomentował
Przypadki testowe
Pokaż fragment kodu
źródło
Haskell , 35 bajtów
#
pobieraString
ai listęString
s, i zwraca aBool
.Wypróbuj online!
Po prostu nie przejmuj się przypadkiem testowym, który pominąłem, ponieważ uderzył mojego skromnego laptopa nawet z -O2. Podejrzewam, że GHC nie usuwa tej pośredniej listy elementów 30517578125, ma zbyt dużo współużytkowania, aby szybko zebrać śmieci, a ponieważ test jest fałszywy, program musi wygenerować wszystko ... możesz spróbować, jeśli możesz załatw to.
mapM("":)(l<$s)
to lista wszystkich sposobów tworzenialength s
listy elementów, które są albo pustymi ciągami, albo ciągami zl
.źródło
Pyth,
17151114 bajtówZmieniono wymaganie dotyczące pustego ciągu, dodając 3 bajty.
Wyjaśnienie
Stare wersje
Krótszy i trwa w całym wszechświecie!
Wyjaśnienie
Jest to przerażająco wolne, ale działa w moich (trywialnie małych) testach.
Wyjaśnienie
źródło
Galaretka ,
14128 bajtówWypróbuj online!
Jak to działa
"", ["The string can be constructed with nothing"]
poprawka błędu w sprawie dzięki @JonathanAllanźródło
"", ["The string can be constructed with nothing!"]
;FŒṖḟ⁹$€Ạ¬
to naprawi.ḟ
, więc nie potrzebne są$
albo⁹
:;FŒṖḟ€Ạ¬
.¬
operacją, która zawsze zwraca true z poprawnym argumentem „”.R, 49 bajtów
Wypróbuj online!
źródło
('x', '.')
, ale nie.Pyth, 10
8bajtówZestaw testowy
To pobiera listę w pierwszym wierszu STDIN, a ciąg znaków (bez cudzysłowów) w drugim.
Aby rozpocząć, lista jest przechowywana w
Q
, a ciąg jest przechowywany wz
. Następnie tworzymy wszystkie możliwe partycjez
. Każda partycja zostanie przefiltrowana (f
), aby sprawdzić, czy używa tylko elementów wQ
. Aby to zrobić, usuwamy wszystkie elementyQ
zT
partycji, na której partycjonujemy, i logicznie negujemy wynik!
, aby tylko partycje, w których znajdował się każdy elementQ
przechowywane są .Aby rozwiązać problem, który
''
nie ma partycji, dodajemy pierwsze słowo słownika do z, aby nie był to pusty ciąg.źródło
""
wygląda na to, że zawiodła."", [""]
and"", []
have not been covered - lets not go there :)PowerShell,
615857 bytesTry it online!
Old solutions:
źródło
Python 2, 64 bytes
Try this online!
źródło
("aaaaaaa",["aa","aaa"])
.('x', '.')
, I guess, but doesn't."Hello", ["\w"]
etc.PowerShell, 78
Pretty straightforward regex-based approach.
źródło
CJam (16 bytes)
This is an anonymous block (function) taking the string and the array of strings on the stack. Online demo.
It uses the obvious algorithm:
The return value is an empty array/string (falsy) if
str
can't be made, or an array containingstr
(truthy, even ifstr
is itself the empty string) if it can be made.źródło
C++(Bcc), 287 bytes
because i do not wrote or used too much the next_permutation() i don't know if is all ok. I don't know 100% if it is a solution too possibly this is out of quality... One list of string is here one array of pointers to char; NULL terminated The algo is easy, there is one algo that linearity try if all string in the list fit with argument "a" string there is one other algo that permute the index of the list of string so it try all possible combination.
ungolf it, test code and results here
this would compile in gcc C++ compiler
źródło
Python, 66 bytes
Ungolfed:
źródło
Microsoft Sql Server, 353 bytes
Test it online.
Readable version:
źródło
C, 140 bytes
I'm sure there is a shorter way to do this in C but I wanted to create a solution that tests all the possible combinations of substrings instead of the usual find/replace method.
Try it online
Ungolfed:
źródło