Na ile kawałków można wyciąć ten sznurek?

45

Rozważ kawałek sznurka (jak w „sznurku”, a nie w „wiązce znaków”), który jest składany w tę iz powrotem na linii rzeczywistej. Możemy opisać kształt łańcucha za pomocą listy punktów, przez które przechodzi (w kolejności). Dla uproszczenia założymy, że wszystkie te punkty są liczbami całkowitymi.

Weź jako przykład [-1, 3, 1, -2, 5, 2, 3, 4](pamiętaj, że nie każdy wpis oznacza zakładanie):

wprowadź opis zdjęcia tutaj

Ciąg rozciągający się wzdłuż kierunku pionowego służy wyłącznie do celów wizualizacji. Wyobraź sobie, że sznurek jest spłaszczony na prawdziwej linii.

Teraz pojawia się pytanie: jaka jest największa liczba kawałków, na które ten sznurek można pokroić jednym cięciem (które na powyższym zdjęciu musiałyby być pionowe). W tym przypadku odpowiedź brzmi 6 z cięciem pomiędzy 2i 3:

wprowadź opis zdjęcia tutaj

Aby uniknąć dwuznaczności, cięcie musi być wykonywane w pozycji innej niż całkowita.

Wyzwanie

Biorąc pod uwagę listę pozycji całkowitych, przez które składa się sznurek, musisz określić największą liczbę kawałków, na które można cięć za pomocą pojedynczego cięcia w pozycji innej niż całkowita.

Możesz napisać pełny program lub funkcję. Możesz przyjmować dane wejściowe za pomocą STDIN, argumentu wiersza poleceń, pytania lub parametru funkcji. Możesz zapisać dane wyjściowe do STDOUT, wyświetlić je w oknie dialogowym lub zwrócić z funkcji.

Możesz założyć, że lista ma dowolny dogodny format listy lub łańcucha.

Lista będzie zawierać co najmniej 2 i nie więcej niż 100 wpisów. Wpisy będą liczbami całkowitymi, każdy w zakresie -2 31 ≤ p i <2 31 . Możesz założyć, że żadne dwa kolejne wpisy nie są identyczne.

Twój kod musi przetwarzać takie dane wejściowe (w tym poniższe przypadki testowe) w czasie krótszym niż 10 sekund na rozsądnym komputerze stacjonarnym.

Przypadki testowe

Wszystkie przypadki testowe są po prostu wprowadzane, a następnie generowane.

[0, 1]
2

[2147483647, -2147483648]
2

[0, 1, -1]
3

[1, 0, -1]
2

[-1, 3, 1, -2, 5, 2, 3, 4]
6

[-1122432493, -1297520062, 1893305528, 1165360246, -1888929223, 385040723, -80352673, 1372936505, 2115121074, -1856246962, 1501350808, -183583125, 2134014610, 720827868,  -1915801069, -829434432, 444418495, -207928085, -764106377, -180766255, 429579526,  -1887092002, -1139248992, -1967220622, -541417291, -1617463896, 517511661, -1781260846,  -804604982, 834431625, 1800360467, 603678316, 557395424, -763031007, -1336769888,  -1871888929, 1594598244, 1789292665, 962604079, -1185224024, 199953143, -1078097556, 1286821852, -1441858782, -1050367058, 956106641, -1792710927, -417329507, 1298074488,  -2081642949, -1142130252, 2069006433, -889029611, 2083629927, 1621142867, -1340561463,  676558478, 78265900, -1317128172, 1763225513, 1783160195, 483383997, -1548533202,  2122113423, -1197641704, 319428736, -116274800, -888049925, -798148170, 1768740405,  473572890, -1931167061, -298056529, 1602950715, -412370479, -2044658831, -1165885212,  -865307089, -969908936, 203868919, 278855174, -729662598, -1950547957, 679003141,  1423171080, 1870799802, 1978532600, 107162612, -1482878754, -1512232885, 1595639326,  1848766908, -321446009, -1491438272, 1619109855, 351277170, 1034981600, 421097157,  1072577364, -538901064]
53

[-2142140080, -2066313811, -2015945568, -2013211927, -1988504811, -1884073403, -1860777718,  -1852780618, -1829202121, -1754543670, -1589422902, -1557970039, -1507704627, -1410033893,  -1313864752, -1191655050, -1183729403, -1155076106, -1150685547, -1148162179, -1143013543,  -1012615847, -914543424, -898063429, -831941836, -808337369, -807593292, -775755312, -682786953, -679343381, -657346098, -616936747, -545017823, -522339238, -501194053,  -473081322, -376141541, -350526016, -344380659, -341195356, -303406389, -285611307, -282860017, -156809093, -127312384, -24161190, -420036, 50190256, 74000721, 84358785,  102958758, 124538981, 131053395, 280688418, 281444103, 303002802, 309255004, 360083648,  400920491, 429956579, 478710051, 500159683, 518335017, 559645553, 560041153, 638459051,  640161676, 643850364, 671996492, 733068514, 743285502, 1027514169, 1142193844, 1145750868,  1187862077, 1219366484, 1347996225, 1357239296, 1384342636, 1387532909, 1408330157,  1490584236, 1496234950, 1515355210, 1567464831, 1790076258, 1829519996, 1889752281,  1903484827, 1904323014, 1912488777, 1939200260, 2061174784, 2074677533, 2080731335, 2111876929, 2115658011, 2118089950, 2127342676, 2145430585]
2
Martin Ender
źródło
Czy możemy założyć, że chcesz, aby cięcie było w miejscu gwarantującym maksymalną liczbę sztuk?
DavidC
2
Prawdopodobnie powiedziałbym: „określ największą liczbę sztuk” zamiast „określ, ile sztuk”.
DavidC
1
Czy to nie a reasonable desktop PCjest niejednoznaczne?
globby
3
@globby Jest to dość powszechne wyrażenie, którego używamy, gdy środowisko wykonawcze nie jest częścią zwycięskiego kryterium (ale służy jedynie do upewnienia się, że rozwiązania nie wykorzystują brutalnej siły). Oznacza to przede wszystkim, że limit nie jest w 100% ścisły. Jeśli zajmuje to 15 sekund na twoim komputerze (a nie używasz superkomputera), istnieje prawdopodobieństwo, że ktoś w okolicy ma komputer stacjonarny, na którym kończy się w 10 sekund. Ale jeśli zajmie to chwilę na twoim komputerze, jest to mniej prawdopodobne, więc musisz pomyśleć o innym podejściu. Limit jest również wybrany w taki sposób, że skuteczny algorytm z łatwością ukończy się w czasie krótszym niż 10 sekund.
Martin Ender
2
@ZainR nope.
Martin Ender

Odpowiedzi:

16

APL, 16 14 bajtów

1+⌈/+/2≠/∘.≤⍨⎕

Dzięki @ngn za zapisanie 2 bajtów.

W rzeczywistości jest to znak ramki, a nie błąd braku czcionki. Możesz wypróbować program na tryapl.org , ale ponieważ nie jest tam w pełni obsługiwany, musisz go zastąpić wartością wejściową:

    1+⌈/+/2≠/∘.≤⍨ ¯1 3 1 ¯2 5 2 3 4
6

Wyjaśnienie

Program najlepiej objaśnia przykładowe dane wejściowe s = ¯1 3 1 ¯2 5 2 3 4pobrane ze STDIN przez . Najpierw obliczamy produkt routera za spomocą samego siebie ∘.≤⍨. Wynikiem tego jest macierz boolowska, której irząd informuje, które elementy ssą mniejsze lub równe s[i]:

1 1 1 0 1 1 1 1
0 1 0 0 1 0 1 1
0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0
0 1 0 0 1 1 1 1
0 1 0 0 1 0 1 1
0 0 0 0 1 0 0 1

Występowanie w wierszu 0 1i 1 0na nim ioznacza miejsca, w których ciąg przechodzi przez punkt s[i] + 0.5. Dopasowujemy je w każdym wierszu, używając opcji 2≠/„zmniejsz 2 listy podrzędne o ”:

0 0 1 1 0 0 0
1 1 0 1 1 1 0
1 0 1 1 0 0 0
0 0 0 0 0 0 0
0 0 0 1 1 0 0
1 1 0 1 0 0 0
1 1 0 1 1 1 0
0 0 0 1 1 0 1

Pozostaje wziąć sumy wierszy +/

2 5 3 0 2 3 5 3

i jeden plus ich maksimum z 1+⌈/:

6

Wynik jest automatycznie drukowany do STDOUT w większości implementacji APL.

Zgarb
źródło
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳ Mój zły - oczekiwany wynik to liczba sztuk, a nie lokalizacja, w której można go wyprodukować.
J ...
Technicznie jest to 16 znaków, 28 bajtów. Unicode ci to zrobi = P
KChaloux 15.01.2015
1
@KChaloux tylko, jeśli policzysz w bajtach utf8, czego nie zrobiłbyś dla APL. Istnieje jednobajtowa strona kodowa, która zawiera cały zestaw znaków używany przez APL, więc można go używać tylko do zliczania.
Martin Ender
@ MartinBüttner Niezawodny link źródłowy byłby świetny. W przeciwnym razie ktoś mógłby stworzyć dowolną własną stronę internetową zawierającą tylko zestaw znaków używanych w dowolnym języku w celu zmniejszenia liczby bajtów.
agweber,
1
@GuillaumeLethuillier APL jest naprawdę bardzo łatwy do nauczenia, przynajmniej do tego stopnia, że ​​możesz pisać proste odpowiedzi na golfa w ten sposób. Istnieje kilkadziesiąt funkcji o łatwych do zapamiętania nazwach, takich jak ×mnożenie i bardzo proste reguły składniowe. Google „mastering Dyalog APL” dla dobrego przewodnika.
Zgarb
16

Python, 88 75 73 bajtów

lambda x:max(sum((a+.5-m)*(a+.5-n)<0for m,n in zip(x,x[1:]))for a in x)+1

Po prostu prosta lambda


Aby pokazać inne podejście:

Pyth, 28 27 bajtów

heSmsmq@S+k(d)1dC,QtQm+b.5Q

Ten jest mniej więcej równoważny

lambda x:max(sum(a+.5==sorted(n+(a+.5,))[1]for n in zip(x,x[1:]))for a in x)+1

stosowane do listy danych wejściowych z STDIN. Wypróbuj go w tłumaczu online .

Sp3000
źródło
Możesz nawet przechowywać tę funkcję w tej samej ilości znaków:def f(x):max(sum((a+.5-m)*(a+.5-n)<0for m,n in zip(x,x[1:]))for a in x)+1
Christian Sonne
4
@ChristianSonne Twoja funkcja nic nie zwraca.
Jakube
Strzelaj, masz rację @Jakube
Christian Sonne
Nie jestem do końca pewien, jak to działa, ale myślę, że możesz usunąć +.5s, aby uratować niektóre postacie. Uświadomiłem sobie, że w moim przypadku są bezcelowe.
KSFT
@KSFT Dzieli ciąg na przedziały, iteruje każdy a = point + .5i zlicza ściśle określone przedziały a. Bez tego .5będziesz mieć problemy z przypadkami takimi jak [1, 0, -1]przykład.
Sp3000,
16

Pyth : 31 30 29 28 24 23 znaków (znaki Python 68)

heSmsm&<hSkdgeSkdC,tQQQ

Wypróbuj tutaj: Pyth Compiler / Executor

Oczekuje listy liczb całkowitych jako danych wejściowych [-1, 3, 1, -2, 5, 2, 3, 4]

To proste tłumaczenie mojego programu w języku Python:

lambda s:1+max(sum(min(a)<i<=max(a)for a in zip(s,s[1:]))for i in s)

Stare rozwiązanie: Pyth 28 char

Tylko z powodów archiwizacji.

heSmsm<*-dhk-dek0C,tQQm+b.5Q

Odpowiedni kod Pythona to:

f=lambda x:1+max(sum((i-a)*(i-b)<0for a,b in zip(x,x[1:]))for i in [j+.5 for j in x])
Jakube
źródło
,QtQ[QtQ)
Jestem
inie jest linią przecięcia, i - 0.5jest. I dlatego 1 (właściwie 1 - 0.5 = 0.5) jest w środku (-1, 1). min(a)<i<=max(a)jest równoważne min(a) < i - 0.5 < max(a)rozwiązaniu w Pyth z min(a) < i < max(a)+1(zauważ hin heSk).
Jakube,
Myślę, że tu jesteś. A przynajmniej nie mogę znaleźć żadnego przypadku, w którym ta logika zawodzi ...
Optymalizator
Można zapisać znak za pomocą g, która jest >=, jeśli zastąpi <dheSksię geSkd.
isaacg
2
Dzięki @isaacg. Ale dlaczego zawsze przychodzisz i niszczysz moje rozwiązanie, skoro jestem naprawdę szczęśliwy i pewny tego? ;-)
Jakube,
10

CJam, 36 34 33 30 bajtów

q~[__(+]zW<f{f{1$+$#1=}1b}$W=)

Uważam, że istnieje lepszy algorytm na wolności. Mimo to działa to poniżej limitu wymaganego dla wszystkich przypadków testowych (nawet w kompilatorze online)

Dane wejściowe są jak

[-2142140080 -2066313811 -2015945568 -2013211927 -1988504811 -1884073403 -1860777718  -1852780618 -1829202121 -1754543670 -1589422902 -1557970039 -1507704627 -1410033893  -1313864752 -1191655050 -1183729403 -1155076106 -1150685547 -1148162179 -1143013543  -1012615847 -914543424 -898063429 -831941836 -808337369 -807593292 -775755312 -682786953 -679343381 -657346098 -616936747 -545017823 -522339238 -501194053  -473081322 -376141541 -350526016 -344380659 -341195356 -303406389 -285611307 -282860017 -156809093 -127312384 -24161190 -420036 50190256 74000721 84358785  102958758 124538981 131053395 280688418 281444103 303002802 309255004 360083648  400920491 429956579 478710051 500159683 518335017 559645553 560041153 638459051  640161676 643850364 671996492 733068514 743285502 1027514169 1142193844 1145750868  1187862077 1219366484 1347996225 1357239296 1384342636 1387532909 1408330157  1490584236 1496234950 1515355210 1567464831 1790076258 1829519996 1889752281  1903484827 1904323014 1912488777 1939200260 2061174784 2074677533 2080731335 2111876929 2115658011 2118089950 2127342676 2145430585]

Dane wyjściowe (w powyższym przypadku) to

2

Jak to działa

q~[__(+]zW<f{f{1$+$#1=}1b}$W=)
q~                                "Evaluate input string as array";
  [__                             "Put two copies of it in an array";
     (+]                          "Shift first element of second copy to its end";
        z                         "Zip together the two arrays. This creates";
                                  "pair of adjacent elements of the input.";
         W<                       "Remove the last pair";
           f{            }        "For each element of input array, take the zipped";
                                  "array and run the code block";
             f{       }           "For each element of the zipped array along with";
                                  "the current element from input array, run this block";
               1$+                "Copy the current number and add it to the pair";
                  $#              "Sort the pair and find index of current number";;
                    1=            "check if index == 1 for a < I <= b check";
                       1b         "Get how many pairs have this number inside of them";
                          $W=)    "Get the maximum parts the rope can be cut into";

Załóżmy teraz, że tablica wejściowa [-1 3 1 -2 5 2 3 4]wygląda następująco:

[-1 3 1 -2 5 2 3 4] [[-1 3 1 -2 5 2 3 4] [-1 3 1 -2 5 2 3 4]
[-1 3 1 -2 5 2 3 4] [[-1 3 1 -2 5 2 3 4] [3 1 -2 5 2 3 4 -1]
[-1 3 1 -2 5 2 3 4] [[-1 3] [3 1] [1 -2] [-2 5] [5 2] [2 3] [3 4]]]

Druga tablica w ostatnim wierszu to fałdy łańcucha.

Teraz iterujemy [-1 3 1 -2 5 2 3 4]i obliczamy liczbę zestawów, w których każdy z nich leży. Uzyskaj maksimum z tej liczby, zwiększ ją i otrzymamy odpowiedź.

Wypróbuj online tutaj

Optymalizator
źródło
10

Matlab (123) (97) (85)

Tak, w końcu zastosowanie XNOR =) Jestem pewien, że można go bardziej zagrać w golfa.

Ale szczerze mówiąc jestem trochę zawstydzony tym, że MatLab staje się językiem, który znam najlepiej = /

Przybliżony czas działania to O(n^2).

EDYCJA 2:

a=input();v=2:nnz(a);disp(max(arrayfun(@(e)sum(~xor(a(v-1)<e,e<a(v))),sort(a)-.5))+1)

EDYCJA: Nowa wersja bardziej golfowa (w tym wskazówki od @DennisJaheruddin, dzięki!)

a=input();c=sort(a)-.5;n=0;v=2:nnz(c);for e=c;n=[n,sum(~xor(a(v-1)<e,e<a(v)))];end;disp(max(n)+1)

Stara wersja:

a=input();
c=conv(sort(a),[.5,.5],'valid');' %find all cutting positions by taking the mean of two successive points
k=numel(c);
for e=1:k %iterate over all 'cuts'
    n(e)=sum(~xor(a(1:k)<c(e),c(e)<a(2:k+1)));%find the number of threads the cut cuts
end
disp(max(n)+1) %output the max

@ MartinBüttner: Naprawdę podobają mi się twoje małe, miłe wyzwania tuż przed pójściem do łóżka!

wada
źródło
10
Moja żona nie znosi XNORingu
gnibbler
9
Czas, aby @xnor zanotował =)
błąd
Myślę, że możesz zaoszczędzić trochę na znajdowaniu punktów cięcia, ponieważ fałdy są zawsze liczbami całkowitymi: c=sort(a)-.5Oczywiście pierwszy punkt jest poza zakresem, ale z pewnością łatwiej sobie z tym poradzić. W najgorszym przypadku możesz to zrobić c(1)=[];. - Możesz także usunąć polecenie disp, tylko obliczenie czegoś zapisze to na standardowe wyjście. - Wreszcie w tym przypadku numelmożna go zastąpićnnz
Dennis Jaheruddin
Ale byłem bardzo dumny z mojego convpodejścia ... = D. Zawsze zapominam o nnz, bardzo dziękuję!
flawr
Mogłem znaleźć kilka sposobów, aby uczynić to jeszcze krótszym w ten sposób! Używam, dispponieważ ktoś kiedyś skrytykował to, że za pomocą zaproponowanej przez ciebie metody otrzymujesz także inne znaki (nazwa var lub ans) napisane na standardowe wyjście ...
flawr
9

Mathematica 134 133 104

Fajne do rozwiązania, pomimo wielkości kodu. Dalsze golfa nadal można osiągnąć poprzez wymianę idei IntervalMemberQ[Interval[a,b],n]z a<n<b.

n_~f~i_:=Count[IntervalMemberQ[#,n]&/@i,1>0];
g@l_:=Max[f[#,Interval/@Partition[l,2,1]]&/@(Union@l+.5)]+1

g[{-1, 3, 1, -2, 5, 2, 3, 4}]

6


Wyjaśnienie

list1czy podana lista punktów list2jest skróconą listą, która usuwa liczby, które nie były złożone ; są nieistotne. Nie jest to konieczne, ale prowadzi do bardziej przejrzystego i wydajnego rozwiązania.

list1 = {-1, 3, 1, -2, 5, 2, 3, 4};
list2 = {-1, 3, 1, -2, 5,2, 3, 4} //. {beg___, a_, b_, c_, end___} /; (a <= b <= c) 
 \[Or] (a >= b >= c) :> {beg, a, c, end}

Przedziały w list1i list2są przedstawione na wykresach poniżej:

NumberLinePlot[Interval /@ Partition[list1, 2, 1]]
NumberLinePlot[intervalsArrangedVertically = Interval /@ Partition[list2, 2, 1]]

interwały


Musimy przetestować tylko jedną linię w każdym interwale określonym przez punkty zagięcia. Linie testowe to przerywane pionowe linie na wykresie.

delimitersLeftToRight = Union[list2]
testLines = delimitersLeftToRight + .5
NumberLinePlot[
 intervalsArrangedVertically = Interval /@ Partition[list2, 2, 1], 
 GridLines -> {testLines, {}}, 
 GridLinesStyle -> Directive[Gray, Dashed]]

linie testowe


fznajduje liczbę cięć lub skrzyżowań każdej linii testowej. Linia przy x = 2,5 wykonuje 5 skrzyżowań. To pozostawia 5 + 1 kawałków sznurka.

f[num_, ints_] := Count[IntervalMemberQ[#, num] & /@ ints, True]
f[#, intervalsArrangedVertically] & /@ testLines
Max[%] + 1

{2, 3, 5, 3, 2, 0}
6

DavidC
źródło
8

Pyth, 21 bajtów

heSmsmq1xS+dSkdC,tQQQ

Wypróbuj tutaj.

Podaj dane jako listę w stylu Python, np [-1, 3, 1, -2, 5, 2, 3, 4]

Ściśle oparty na programie @ jakube, ale z ulepszonym centralnym algorytmem. Zamiast >sprawdzać i >=sprawdzać, robię a .index()na trzech liczbach łącznie i upewniam się, że indeks wynosi 1, co oznacza, że ​​jest większy niż minimum i mniejszy lub równy maksimum.

isaacg
źródło
7

R, 86 83

Pracowałem nad tym, a potem zdałem sobie sprawę, że w zasadzie znalazłem to samo rozwiązanie, co Optimizer i inne, które podejrzewam.

W każdym razie jest to funkcja pobierająca wektor

f=function(l)max(colSums(mapply(function(n)c(l[-1],NA,l)<=n&c(l,l[-1],NA)>=n,l),T))
MickyT
źródło
OK, więc jestem stronniczy i po prostu lubię R. FWIW możesz zapisać 3 znaki, używając T„PRAWDA”
Carl Witthoft 15.01.2015
@CarlWitthoft Dzięki za wskazówkę
MickyT
4

GolfScript (43 bajty)

~[.(;]zip);{$}%:x{0=:y;x{{y>}%2,=},,}%$-1=)

Pod względem wydajności jest to O (n ^ 2) przy założeniu, że porównania zajmują czas O (1). Dzieli dane wejściowe na segmenty linii i dla każdego punktu początkowego liczy półotwarte segmenty linii, które je przekraczają.

Demo online

Peter Taylor
źródło
4

Python - 161

To może być bardziej golfa. gnibbler bardzo pomógł w grze w golfa.

l=input()
d={}
for i in zip(l,l[1:]):d[sum(i)/2.]=0
for i,k in zip(l,l[1:]):
 for j in[m for m in d.keys()if min(i,k)<m<max(i,k)]:d[j]+=1
print max(d.values())+1
KSFT
źródło
1
@ MartinBüttner / Jakube Naprawiłem to. Działa teraz dla wszystkich przypadków testowych w mniej niż dziesięć sekund.
KSFT
Dlaczego są na to dwa zdania negatywne?
KSFT
3

Ruby, 63

Podobne do koncepcji rozwiązań w języku Python.

->a{a.map{|x|a.each_cons(2).count{|v|v.min<x&&x<=v.max}}.max+1}

Dodaj 2 znaki przed kodem, np. f=Jeśli potrzebujesz nazwanej funkcji. Thx do MarkReed .

Vectorized
źródło
Nagie proc wydaje się być akceptowalną odpowiedzią bez przypisywania jej do zmiennej. Zapisuje dwie postacie.
Mark Reed,
3

C #, 73 65 bajtów

N=>1+N.Max(i=>N.Zip(N.Skip(1),(f,s)=>f<i+.5==i+.5<s).Count(b=>b))

Czytając zasady, pomyślałem, że C # lambda powinna zrobić całkiem nieźle.

Edycja: właśnie znaleziona Countma przydatne przeciążenie do filtrowania!

Możesz to przetestować, definiując odpowiedni delegatetyp:

delegate int solver(int[] l);

I wtedy

var l = new int[] { -1, 3, 1, -2, 5, 2, 3, 4 };
solver s = N=>1+N.Max(i=>N.Zip(N.Skip(1),(f,s)=>f<i+.5==i+.5<s).Count(b=>b));

Console.WriteLine(s(l));
Carl Walsh
źródło
3

Matlab ( 63 43)

Dane wejściowe podano jako wektor wiersza przekazany do funkcji f. Na przykład f([-1, 3, 1, -2, 5, 2, 3, 4])powraca 6.

f=@(x)max(sum(diff(bsxfun(@le,2*x',x(1:end-1)+x(2:end)))~=0))+1

Krótsza wersja:

f=@(x)max(sum(diff(bsxfun(@lt,x',x))~=0))+1

Oktawa (31)

W Octave bsxfunmożna usunąć dzięki automatycznemu nadawaniu:

f=@(x)max(sum(diff(x'<x)~=0))+1
Luis Mendo
źródło
2

JavaScript (ES6) 80 82

Zobacz komentarze - liczba bajtów nie obejmuje przypisania do F (to wciąż potrzebne do przetestowania)

F=l=>Math.max(...l.map(v=>l.map(t=>(n+=t>u?v<t&v>=u:v>=t&v<u,u=t),n=1,u=l[0])&&n))

Testuj w konsoli FireFox / FireBug

;[
 F([0, 1])
,F([2147483647, -2147483648])
,F([0, 1, -1])
,F([1, 0, -1])
,F([-1, 3, 1, -2, 5, 2, 3, 4])  
,F([-1122432493, -1297520062, 1893305528, 1165360246, -1888929223, 385040723, -80352673, 1372936505, 2115121074, -1856246962, 1501350808, -183583125, 2134014610, 720827868, -1915801069, -829434432, 444418495, -207928085, -764106377, -180766255, 429579526, -1887092002, -1139248992, -1967220622, -541417291, -1617463896, 517511661, -1781260846, -804604982, 834431625, 1800360467, 603678316, 557395424, -763031007, -1336769888, -1871888929, 1594598244, 1789292665, 962604079, -1185224024, 199953143, -1078097556, 1286821852, -1441858782, -1050367058, 956106641, -1792710927, -417329507, 1298074488, -2081642949, -1142130252, 2069006433, -889029611, 2083629927, 1621142867, -1340561463, 676558478, 78265900, -1317128172, 1763225513, 1783160195, 483383997, -1548533202, 2122113423, -1197641704, 319428736, -116274800, -888049925, -798148170, 1768740405,  473572890, -1931167061, -298056529, 1602950715, -412370479, -2044658831, -1165885212, -865307089, -969908936, 203868919, 278855174, -729662598, -1950547957, 679003141,  1423171080, 1870799802, 1978532600, 107162612, -1482878754, -1512232885, 1595639326, 1848766908, -321446009, -1491438272, 1619109855, 351277170, 1034981600, 421097157, 1072577364, -538901064])
,F([-2142140080, -2066313811, -2015945568, -2013211927, -1988504811, -1884073403, -1860777718, -1852780618, -1829202121, -1754543670, -1589422902, -1557970039, -1507704627, -1410033893,  -1313864752, -1191655050, -1183729403, -1155076106, -1150685547, -1148162179, -1143013543,  -1012615847, -914543424, -898063429, -831941836, -808337369, -807593292, -775755312, -682786953, -679343381, -657346098, -616936747, -545017823, -522339238, -501194053,  -473081322, -376141541, -350526016, -344380659, -341195356, -303406389, -285611307, -282860017, -156809093, -127312384, -24161190, -420036, 50190256, 74000721, 84358785,  102958758, 124538981, 131053395, 280688418, 281444103, 303002802, 309255004, 360083648,  400920491, 429956579, 478710051, 500159683, 518335017, 559645553, 560041153, 638459051,  640161676, 643850364, 671996492, 733068514, 743285502, 1027514169, 1142193844, 1145750868,  1187862077, 1219366484, 1347996225, 1357239296, 1384342636, 1387532909, 1408330157,  1490584236, 1496234950, 1515355210, 1567464831, 1790076258, 1829519996, 1889752281,  1903484827, 1904323014, 1912488777, 1939200260, 2061174784, 2074677533, 2080731335, 2111876929, 2115658011, 2118089950, 2127342676, 2145430585])
]

Wynik

[2, 2, 3, 2, 6, 53, 2]

edc65
źródło
2
W oparciu o lambdarozwiązania Python nie musisz przypisywać wartości funkcji do rzeczywistej zmiennej, więc możesz znokautować dwa znaki.
Mark Reed,
1
Tak. O ile nie wskazano inaczej w wyzwaniu, funkcje bez nazw są w porządku.
Martin Ender,
1

Galaretka , 10 bajtów

>þ`^ƝS$€Ṁ‘

Wypróbuj online!

Jak to działa

>þ`^ƝS$€Ṁ‘ - Main link. 1 argument        e.g.   [1, 0, -1]
>þ`        - Greater than outer product          [[0, 0, 0], [1, 0, 0], [1, 1, 0]]
      $€   - Over each sublist:           e.g.   [1, 1, 0]
    Ɲ      -   Over each overlapping pair e.g.   [1, 0]
   ^       -     Perform XOR                     1
     S     -   Take the sums                     [0, 1, 1]
        Ṁ  - Take the maximum                    1
         ‘ - Increment                           2
Cairney Coheringaahing
źródło
1

05AB1E , 6 bajtów

ε@Ôg}à

Wypróbuj online!

Wyjaśnienie:

ε   }    # for each element of the input
 @       # is each element >= this one? (returns list of booleans)
  Ô      # connected uniquified
   g     # length
     à   # maximum
Ponury
źródło
0

Dodaj ++ , 27 bajtów

D,w,@@,VbUG€<ÑBxs
L~,A€wM1+

Wypróbuj online!

Podejdź do Zgarba za odpowiedź APL

Kluczową częścią tego wyzwania jest wdrożenie zewnętrznego polecenia produktu. Niestety, Add ++ nie ma wbudowanego do tego celu, nie ma też żadnego sposobu definiowania funkcji, które przyjmują inne funkcje jako argumenty. Niemniej jednak nadal możemy wprowadzić uogólnioną funkcję produktu zewnętrznego. Ponieważ jedynym sposobem na dostęp do funkcji w innej funkcji jest odwołanie się do istniejącej funkcji zdefiniowanej przez użytkownika lub wbudowanej, musimy stworzyć „wbudowaną”, która odwołuje się do takiej funkcji.

Uogólniona funkcja „tabeli” wyglądałaby mniej więcej tak:

D,func,@@,+

D,iter,@@*, VbUG €{func}
D,table,@@, $ bRbU @ €{iter} B]

Wypróbuj online!

gdzie funcjest funkcja dyadyczna, która zawiera nasz operand. Widać nikłe podobieństwo tej struktury w oryginalnym złożenia, na początku wag funkcji, ale tutaj chcemy przede wszystkim, a jednowartościowy funkcji produktu zewnętrzna - zewnętrzną funkcję produktu, które ma ten sam argument po obu stronach.

Ogólna funkcja tabeli wykorzystuje to, jak ach szybko zbliża się do funkcji dyadycznych. Jeśli wygląda stos

 [a b c d e]

gdy €{func}zostanie napotkany, wyskakuje e, wiąże to jako lewy argument z diadem i odwzorowuje tę częściową funkcję a, b, c, d. Jednak szybkie mapy na całym stosie, a nie na listach. Musimy więc spłaszczyć tablice przekazane jako argumenty jako pierwsze.

Funkcja tabeli działa ogólnie w ten sposób

D,func,@@,+

D,iter,		; Define our helper function iter
		;   This takes an array as its left argument
		;   And a single integer as its right argument
	@@	; Dyadic arguments - take two arguments and push to the stack
	*,	; After execution, return the entire stack, rather then just the top element
		;
		; Example arguments:	[5 6 7 8] 1
		; 
	VbUG	; Unpack the array;	[5 6 7 8 1]
		;
	€{func}	; Map func over the stack
		; As func is dyadic, this pops the right argument
		;   and binds that to a monadic func
		; This then maps the remaining elements, [5 6 7 8]
		;   over the monadic call of func, yielding [6 7 8 9]
		; Now, as the * flag was defined, we return the entire array
		;   rather than just the last element.
		; We'd achieve the same behaviour by removing the flag and appending B]

D,table,	; Define the main table function
		;   This takes two arrays as arguments
		;   Returns a single 2D array representing their outer product with func
	@@,	; Take the two arrays and push to the stack
		; 
		; Example arguments:	[[1 2 3 4] [5 6 7 8]]
		;
	$	; Swap;		STACK = [[5 6 7 8] [1 2 3 4]]
	bR	; Reverse last;	STACK = [[5 6 7 8] [4 3 2 1]]
	bU	; Unpack;	STACK = [[5 6 7 8] 4 3 2 1]
	@	; Reverse;	STACK = [1 2 3 4 [5 6 7 8]]
		; 
		; This allows us to place the stack so that each element of
		;   the first array is iterated over with the second array
		;
	€{iter}	; Map iter;	STACK = [[6 7 8 9] [7 8 9 10] [8 9 10 11] [9 10 11 12]]
		;
	B]	; Return the whole stack;

$table>?>?
O

Możemy to jednak znacznie skrócić, ponieważ potrzebujemy, aby nasz zewnętrzny stół był monadyczny i wystarczy zastosować się do przekazanego argumentu. AKomenda popycha każdy argument do stosu pojedynczo, więc nie trzeba poeksperymentować z dowolnej manipulacji stosu. Krótko mówiąc, jeśli naszym argumentem jest tablica [a b c d], musimy zrobić stos

[a b c d [a b c d]]

Najwyższą wartością jest oczywiście argument. Być może zauważyłeś z ogólnego przykładu, jakim bUjest polecenie rozpakuj, tzn. Dzieli on górną tablicę na stos. Aby wykonać powyższą konfigurację, możemy użyć kodu

L,bUA

Wypróbuj online!

Można to jednak skrócić bajtem. Jako alias L,bUmożemy użyć ~flagi, aby wcześniej przelać argumenty na stos, czyniąc nasz przykład konfiguracji w

L~,A

Wypróbuj online!

który jest początkiem drugiej linii w programie. Teraz wdrożyliśmy monadyczny produkt zewnętrzny, wystarczy zaimplementować resztę algorytmu. Po pobraniu wyniku tabeli za pomocą <(mniej niż) i policz liczbę [0 1]i [1 0]pary w każdym rzędzie. Wreszcie bierzemy maksimum tych liczb i zwiększamy je.

Kompletny krok do przejścia krok po kroku to

D,w,		; Define a function w
		;   This takes an array and an integer as arguments
		;   First, it produces the outer product with less than
		;   Then reduce overlapping pairs by XOR
		;   Finally, sum the rows
	@@,	; Take two arguments
		;
		; Example arguments:		[[0 1 2 3] 0]
		;
	VbUG€<	; Map < over the array;	STACK = [0 1 1 1]
	ÑBx	; Equals [1 0];		STACK = [1 0 0]
	s	; Sum;			STACK = [1]

L		; Define a lambda function
		;   This takes one argument, an array
	~,	;   Splat the array to the stack before doing anything
		;
		; Example argument:		[0 1 2 3]
		;
	A€w	; Map with w;		STACK = [1 1 1 0]
	M	; Maximum;		STACK = [1]
	1+	; Increment;		STACK = [2]
Społeczność
źródło