Rozważ tablicę liczb całkowitych:
[1, 0, 9, 1, 3, 8]
Istnieje wiele sposobów podziału tej listy na kolejne listy podrzędne. Oto trzy:
A: [[1, 0, 9], [1, 3, 8]]
B: [[1], [0, 9], [1, 3], [8]]
C: [[1, 0], [9, 1], [3, 8]]
Nazwiemy partycję Y i udoskonalenie innej partycji X, jeśli X można uzyskać z Y , łącząc ponownie niektóre jego listy podrzędne.
Podobnie B
jest z udoskonaleniem A
: jeśli połączymy dwie pierwsze i dwie ostatnie podlisty razem, otrzymamy A
. Ale nieC
jest to wyrafinowanie : musielibyśmy rozdzielić i , aby wyjść z tego. Ponadto każda partycja jest trywialnie udoskonaleniem samego siebie.A
9
1
A
Pamiętaj, że w żadnym momencie nie możemy zmieniać kolejności podlist lub elementów.
Wyzwanie
Biorąc pod uwagę dwie partycje (listy list liczb całkowitych) X
i Y
ustal, czy Y
jest to udoskonalenie X
.
Możesz założyć, że partycje będą zawierać tylko liczby całkowite od 0
do 9
włącznie. Nie należy zakładać, że X
i Y
są partycje z tej samej listy (jeśli nie są one również nie są udoskonalenia siebie). X
i / lub Y
mogą być puste, ale nigdy nie będą zawierać pustych list podrzędnych.
Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).
Dane wejściowe mogą być pobierane w dowolnym dogodnym formacie ciągu lub listy. Ponieważ elementami będą tylko jednocyfrowe liczby całkowite, możesz pominąć ogranicznik w podlistach, ale upewnij się, że wiodące 0
s są możliwe. Można wybrać się X
i Y
w odwrotnej kolejności.
Wynik powinien być prawdziwy, jeśli Y
jest udoskonaleniem, X
a fałszem w przeciwnym razie.
Twój kod musi być w stanie rozwiązać każdy z poniższych przypadków testowych w ciągu 1 sekundy na rozsądnej maszynie stacjonarnej. (Jest to jedynie kontrola rozsądku w celu uniknięcia prostych rozwiązań z użyciem siły brutalnej).
To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).
Przypadki testowe
Każdy przypadek testowy ma swoją własną linię, zapisaną jako X Y
. Używam notacji tablicowej w stylu GolfScript / CJam, aby zaoszczędzić trochę miejsca w poziomie:
Prawda:
[] []
[[0]] [[0]]
[[1 0 9 1 3 8]] [[1 0 9] [1 3 8]]
[[1 0 9 1 3 8]] [[1 0 9 1 3] [8]]
[[1 0 9 1 3 8]] [[1] [0] [9] [1] [3] [8]]
[[1 0 9] [1 3 8]] [[1 0 9] [1 3 8]]
[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]
[[9 8 8 5 8 2 7] [5] [1 4] [2 0 0 6 0 8 4 2 6 4 2 3 7 8 7 3 9 5 7 9 8 2 9 5] [3 9 8] [7 1 4 9 7 4 5 9] [3 3 3] [9 0 7 8] [3 9 4 7 2 7 8 0 3 0] [8 2 2 7 3 9 3 2] [2 9 0 8 5 4 1 8 5 5 6 2 0 9 2 7 7 9 2 7] [3 6] [1 2 7 7 4 4 2 9]] [[9 8] [8] [5 8 2] [7] [5] [1 4] [2] [0 0 6] [0] [8 4 2] [6 4] [2] [3] [7 8] [7 3] [9] [5 7 9] [8 2] [9 5] [3] [9 8] [7 1 4] [9 7] [4 5 9] [3 3] [3] [9 0] [7 8] [3] [9] [4] [7 2] [7 8] [0] [3 0] [8 2] [2] [7 3] [9 3] [2] [2] [9] [0] [8 5 4] [1 8] [5 5] [6] [2 0] [9] [2] [7 7 9] [2 7] [3 6] [1 2] [7 7] [4 4 2] [9]]
Falsy:
[[0]] []
[[0]] [[1]]
[[1 0 9]] [[1 0 9] [1 3 8]]
[[1 0 9] [1 3 8]] [[1 0 9 1 3 8]]
[[1 0 9] [1 3 8]] [[1 0 9]]
[[1 0 9] [1 3 8]] [[1 0] [9]]
[[1 0 9] [1 3 8]] [[1 0] [9 1] [3 8]]
[[1] [0 9] [1 3] [8]] [[1 0 9] [1 3 8]]
[[9 8 8 5 8 2 7] [5] [1 4] [2 0 0 6 0 8 4 2 6 4 2 3 7 8 7 3 9 5 7 9 8 2 9 5] [3 9 8] [7 1 4 9 7 4 5 9] [3 3 3] [9 0 7 8] [3 9 4 7 2 7 8 0 3 0] [8 2 2 7 3 9 3 2] [2 9 0 8 5 4 1 8 5 5 6 2 0 9 2 7 7 9 2 7] [3 6] [1 2 7 7 4 4 2 9]] [[9 8] [8] [5 8 2] [7] [5 1] [4] [2] [0 0 6] [0] [8 4 2] [6 4] [2] [3] [7 8] [7 3] [9] [5 7 9] [8 2] [9 5] [3] [9 8] [7 1 4] [9 7] [4 5 9] [3 3] [3] [9 0] [7 8] [3] [9] [4] [7 2] [7 8] [0] [3 0] [8 2] [2] [7 3] [9 3] [2] [2] [9] [0] [8 5 4] [1 8] [5 5] [6] [2 0] [9] [2] [7 7 9] [2 7] [3 6] [1 2] [7 7] [4 4 2] [9]]
Liderów
Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka.
Aby upewnić się, że Twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:
# Language Name, N bytes
gdzie N
jest rozmiar twojego zgłoszenia. Jeśli poprawisz swój wynik, możesz zachować stare wyniki w nagłówku, przekreślając je. Na przykład:
# Ruby, <s>104</s> <s>101</s> 96 bytes
<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51719</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
Powiązane wyzwania
źródło
[[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]]
lub[["109" "138"] ["1" "09" "13" "8"]]
być akceptowalny formatu wejściowego?Odpowiedzi:
CJam,
13109 bajtówWypróbuj online w interpretatorze CJam .
Dzięki @ MartinBüttner za zasugerowanie genialnego formatu wejściowego @ edc65 .
Dzięki @ jimmy23013 za ulepszenie formatu wejściowego i odgranie 3 dodatkowych bajtów.
I / O
Wejście
Podlisty są oddzielone
;
od siebie przez,
:Wynik
Jak to działa
W przypadku łańcuchów o różnej długości
.-
pozostawi znaki w tablicy, które nie mogą być równe liczbom całkowitym 0 lub 15.źródło
;
jako separator ...ll.m27m0-!
.,
i;
oba są typową składnią tablicową (i żadna z nich nie jest używana przez CJam). Dzięki!Pyth, 19 bajtów
Wypróbuj online: Demonstracja lub Uprząż testowa
Używam formatu krotki / listy Pytha jako danych wejściowych. Po prostu zastąp spacje skrzynek testowych przecinkami.
Wyjaśnienie:
Ponieważ pseudo-kod jest nadal nieco mylący, przedstawię algorytm na przykładowym wejściu.
.u+NYdY
Część oblicza ciągłych listy zagnieżdżone, które zawierają pierwszy element.B
jest udoskonaleniemA
, jeśli każda ciągła podlistaA
jest również ciągłą podlistąB
(istnieje tylko jeden wyjątek).Więc po prostu sprawdzam, czy zbiór ciągłych list
A
podrzędnych jest podzbiorem zbioru ciągłych list podrzędnychB
(gF_m.u+NYdYQ
).Jedynym wyjątkiem jest sytuacja, gdy pierwsza lista wejściowa zawiera mniej elementów niż druga lista wejściowa. Na przykład
<Fm.u+YdYQ
wróciłbyTrue
po dane wejściowe[[1]],[[1],[2]]
.Dlatego sprawdzam również, czy połączone listy są równe
&...qFsMQ
.źródło
JavaScript ( ES6 ), 67
70Edytuj 3 bajty zapisane thx @apsillers
Uruchom poniższy fragment w przeglądarce Firefox, aby przetestować
źródło
OK
iKO
.C, 69
75Funkcja z 2 parametrami łańcuchowymi, zwracająca 0 lub 1.
Format parametru: lista podrzędna oddzielona spacjami (''), elementy listy oddzielone przecinkami.
Przykład:
"1,0,9 1,3,8"
"1,0 9,1,3,8"
Mniej golfa
Test Ideone (nieaktualny)
źródło
Haskell, 76 bajtów
Zwraca
True
lubFalse
. Przykładowe użycie:[[1,0,9],[1,3,8]] # [[1,0],[9]]
->False
.Proste rekurencyjne podejście: jeśli pierwsze elementy pasują, kontynuuj ogonami, w przeciwnym razie zacznij od nowa, ale połącz dwa elementy na początku drugiej listy. Podstawowymi przypadkami są: obie listy puste ->
True
; obie listy z jednym elementem -> porównaj je; tylko jedna lista pusta ->False
.źródło
CJam, 19 bajtów
Wypróbuj online.
I / O
Wejście
Wynik
Pomysł
Każdą partycję można jednoznacznie zidentyfikować, obserwując następujące dwie właściwości:
Lista utworzona przez połączenie wszystkich podlist.
„Punkty odcięcia”, w tym skrajności listy.
Możemy połączyć oba kryteria w jedno, zastępując każdy punkt cięcia podlistą elementów od punktu cięcia do końca listy.
Aby zweryfikować, że dana partycja jest drobniejsza niż inna, musimy tylko sprawdzić, czy grubsza partycja, reprezentowana jak powyżej, jest podzbiorem drobniejszej i czy największe listy obu partycji pasują.
Kod
Dla danych wejściowych z przykładu We / Wy stos jest przechowywany
przed wykonaniem
-!
.Zauważ, że pierwszy element każdej tablicy ma spację końcową. Dzięki temu porównamy pełną listę pierwszego wejścia z pełną listą drugiego.
źródło
CJam, 24 bajty
Algorytm
Tutaj po prostu używamy chciwego algorytmu, aby sprawdzić, czy pierwsze
N
podlisty drugiej listy można połączyć ze sobą, tworząc pierwszą podlistę pierwszej listy. Gdy takieN
zostanie znalezione, usuwamy pierwszeN
podlisty z drugiej listy i pierwszą podlistę z pierwszej listy i powtarzamy proces.Idealnie byłoby, gdyby druga lista była udoskonaleniem pierwszej, powinniśmy pozostawić 2 puste listy na stosie. Sprawdzamy to i drukujemy,
1
jeśli tak jest. W żadnej innej kombinacji, po pełnym przejściu przez podlisty drugiej listy, nie otrzymamy 2 pustych list. Tak więc0
dla takich przypadków zostanie wydrukowany.Rozszerzenie kodu
Wypróbuj online tutaj lub uruchom pełny pakiet testowy tutaj
źródło
C,
120114 bajtówOstatnio nie grałem dużo w golfa, więc pomyślałem, że spróbuję tego.
Definiujemy funkcję,
R(char* s, char* t)
która zwraca,1
jeślit
jest wyrafinowaną partycjąs
i0
inaczej.s
it
powinny mieć format, w[DDDD...][DDDD...]...
którym każdyD
jest kolejnym jednocyfrowym elementem.Kod testowy:
Powyżej drukuje następujące:
Przynajmniej wydaje się, że działa.
źródło
Haskell,
525053 bajtówCałkowicie różni się od mojego innego rozwiązania . Używa tego samego sprytnego formatu wejściowego, co odpowiedź @ edc65 , tzn. Elementy są oddzielone za pomocą,
,
a lista z.
Przykład użycia:
"1,0,9,1,3,8" # "1,0,9 1,3,8"
->True
.Drugi parametr jest udoskonaleniem pierwszego, jeśli mają albo jednakowe elementy na każdej pozycji, albo pierwszy jest
,
. Muszę dołączyć unikalny token końcowy (->..
) do obu parametrów, ponieważzipWith
obcina dłuższy parametr i na przykład"1,2,3" # "1,2"
teżTrue
.źródło
(\a b->a==b||a>b)
jest po prostu(>=)
."."
zamiast".."
pracy?"2"#"1"
ponieważ funkcje sprawdzają tylko, czy wartości są większe, a nie równe"."
nie zadziała, ponieważ dałaby fałszywy wynik dodatni, dla"2,1" # "2"
którego najpierw rozwinąłaby się,"2,1." # "2."
a następnie zostałaby obciętazipWith
do"2," # "2."
. Przecinek w pierwszym ciągu pasuje do wszystkiego.Mathematica, 65 bajtów
źródło
Matematyka z wyrażeniami regularnymi jest fajna!
ES6 JavaScript, 53 znaki
Vintage Javascript, 70 znaków
Używa tego samego formatu wejściowego co odpowiedź edc65 .
Pełna wersja demo zawierająca wszystkie przypadki testowe tutaj.
źródło
Mathematica, 55 bajtów
Definiuje to nienazwaną funkcję, przyjmującą dwie partycje na jednej liście , w odwrotnej kolejności (tj.
Y
Pierwsza,X
druga).Wyjaśnienie
To sprawdza, czy obie partycje są w rzeczywistości partycjami tej samej listy.
To jest golfowa forma mojego podejścia do tego pytania na Mathematica.SE , które zainspirowało to wyzwanie. Zasadniczo partycja jest zdefiniowana jako liczba wskaźników, w których wstawiane są podziały, i to sprawdza, czy wszystkie pozycje podziału
X
również pojawiają sięY
poprzez zsumowanie długości list podrzędnych.źródło
Python 2,
6851 bajtówDzięki xnor za znaczne oszczędności bajtów!
Anonimowa funkcja, która pobiera dwa ciągi formularza
"1,0,9 1,3,8"
(wzięte z odpowiedzi C edc65 ) i zwracaTrue
lubFalse
. Nowa wersjamap(None)
nie działa już w Pythonie 3.Zestaw testowy:
Poprzednie 92-bajtowe rozwiązanie, które przyjmuje dane wejściowe jako
"109 138"
:źródło
None
ale drugi indeks ma numer, ponieważi==j or"0">i>j
nie może zostać zatrzymany.i==','
. Pozwala to łączyć testy jakoi in[',',j]
(nie możemy tego zrobići in ','+j
), ponieważj
mogą byćNone
.b
w tym miejscu jest liczba?” ... zapominając, że przy tym formacie wejściowym nie jest to możliwe.