In wie viele Stücke kannst du diese Saite schneiden?

45

Betrachten Sie ein Stück Schnur (wie in "Seil", nicht wie in "eine Reihe von Zeichen"), das auf der realen Linie hin und her gefaltet wird. Wir können die Form der Zeichenkette mit einer Liste von Punkten beschreiben, die sie durchläuft (in der Reihenfolge). Der Einfachheit halber nehmen wir an, dass alle diese Punkte ganze Zahlen sind.

Nehmen Sie als Beispiel [-1, 3, 1, -2, 5, 2, 3, 4](beachten Sie, dass nicht jeder Eintrag eine Falte impliziert):

Bildbeschreibung hier eingeben

Die Zeichenfolge, die sich in vertikaler Richtung erstreckt, dient nur zu Visualisierungszwecken. Stellen Sie sich vor, die Zeichenfolge ist auf die reale Linie abgeflacht.

Hier ist die Frage: In wie viele Stücke kann diese Saite mit einem einzigen Schnitt geschnitten werden (was im obigen Bild vertikal sein müsste)? In diesem Fall lautet die Antwort 6 mit einem Schnitt zwischen 2und 3:

Bildbeschreibung hier eingeben

Mehrdeutigkeiten zu vermeiden, der Schnitt muss bei einer nicht ganzzahligen Position durchgeführt werden.

Die Herausforderung

Wenn eine Liste von Ganzzahlpositionen angegeben wird, durch die eine Zeichenfolge gefaltet wird, müssen Sie die größte Anzahl von Teilen bestimmen, in die die Zeichenfolge mit einem einzelnen Schnitt an einer nicht ganzzahligen Position geschnitten werden kann.

Sie können ein vollständiges Programm oder eine Funktion schreiben. Sie können Eingaben über STDIN, Befehlszeilenargument, Eingabeaufforderung oder Funktionsparameter vornehmen. Sie können die Ausgabe in STDOUT schreiben, in einem Dialogfeld anzeigen oder von der Funktion zurückgeben.

Sie können davon ausgehen, dass die Liste in einem beliebigen geeigneten Listen- oder Zeichenfolgenformat vorliegt.

Die Liste enthält mindestens 2 und höchstens 100 Einträge. Die Einträge sind ganze Zahlen, jeweils im Bereich -2 31 ≤ p i <2 31 . Sie können davon ausgehen, dass keine zwei aufeinander folgenden Einträge identisch sind.

Ihr Code muss solche Eingaben (einschließlich der folgenden Testfälle) in weniger als 10 Sekunden auf einem vernünftigen Desktop-PC verarbeiten.

Testfälle

Alle Testfälle werden einfach eingegeben, gefolgt von der Ausgabe.

[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
quelle
Dürfen wir annehmen, dass der Schnitt an einer Stelle erfolgen soll, die die maximale Stückzahl garantiert?
DavidC
2
Ich würde wahrscheinlich sagen, "Bestimmen Sie die größte Anzahl von Stücken" statt "Bestimmen Sie, wie viele Stücke".
DavidC
1
Ist das nicht a reasonable desktop PCmehrdeutig?
Ruhmreiche
3
@globby Es ist eine ziemlich verbreitete Redewendung, die wir verwenden, wenn die Laufzeit nicht Teil des Gewinnkriteriums ist (sondern nur verwendet wird, um sicherzustellen, dass Lösungen keine rohe Gewalt anwenden). Dies bedeutet meistens, dass das Limit nicht 100% streng ist. Wenn es auf Ihrem Computer 15 Sekunden dauert (und Sie keinen Supercomputer verwenden), hat wahrscheinlich jemand in der Nähe einen Desktop-PC, der in 10 Sekunden fertiggestellt ist. Wenn es auf Ihrem Computer jedoch eine Minute dauert, ist dies weniger wahrscheinlich, sodass Sie über einen anderen Ansatz nachdenken müssen. Die Grenze wird auch so gewählt, dass ein effizienter Algorithmus in weniger als 10 Sekunden problemlos abgeschlossen werden kann.
Martin Ender
2
@ZainR Nein.
Martin Ender

Antworten:

16

APL, 16 bis 14 Bytes

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

Vielen Dank an @ngn für das Speichern von 2 Bytes.

Das ist eigentlich ein Kästchen, kein Fehler mit fehlender Schriftart. Sie können das Programm unter tryapl.org testen , da es dort jedoch nicht vollständig unterstützt wird, müssen Sie es durch den Eingabewert ersetzen:

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

Erläuterung

Das Programm wird am besten mit der Beispieleingabe erklärt s = ¯1 3 1 ¯2 5 2 3 4, die von STDIN übernommen wird . Zunächst berechnen wir das -outer-Produkt von smit sich selbst ∘.≤⍨. Dies ergibt eine boolesche Matrix, deren idritte Zeile angibt, welche Elemente skleiner oder gleich sind 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

Die Vorkommen von 0 1und 1 0in der Zeile imarkieren Stellen, an denen die Zeichenfolge über den Punkt verläuft s[i] + 0.5. Wir vergleichen diese in jeder Zeile mit 2≠/"Reduziere 2-Unterlisten um ":

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

Was bleibt, ist, die Summen der Reihen mitzunehmen +/

2 5 3 0 2 3 5 3

und eins plus das Maximum davon mit 1+⌈/:

6

Das Ergebnis wird in den meisten APL-Implementierungen automatisch auf STDOUT gedruckt.

Zgarb
quelle
@ n̴̖̋h̴̖̋ã̷͉h̷̭̿d̷̰̀ĥ̷̳ Mein schlecht erwartetes Ergebnis ist die Stückzahl, nicht die Produktionsstätte.
J ...
Technisch sind das 16 Zeichen, 28 Bytes. Unicode wird Ihnen das antun = P
KChaloux
1
@KChaloux nur, wenn Sie in utf8 Bytes zählen, was Sie für APL nicht tun würden. Es gibt eine Single-Byte-Codepage, die den gesamten von APL verwendeten Zeichensatz enthält. Es ist also nur fair, diesen zum Zählen zu verwenden.
Martin Ender
@ MartinBüttner Ein zuverlässiger Quelllink wäre super. Andernfalls könnte jemand eine beliebige eigene Webseite mit nur dem Zeichensatz erstellen, der für eine Sprache verwendet wird, um die Anzahl der Bytes zu verringern.
15.
1
@GuillaumeLethuillier APL ist eigentlich sehr einfach zu erlernen, zumindest bis zu dem Punkt, an dem Sie einfache Golfantworten wie diese schreiben können. Es gibt ein paar Dutzend Funktionen mit leicht zu merkenden Namen wie ×für die Multiplikation und sehr einfachen Syntaxregeln. Google "Dyalog APL beherrschen" für eine gute Anleitung.
Zgarb
16

Python, 88 75 73 Bytes

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

Nur ein einfaches Lambda


Nur um einen anderen Ansatz zu zeigen:

Pyth, 28 27 Bytes

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

Das ist ungefähr gleichbedeutend mit

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

wird von STDIN auf die Eingabeliste angewendet. Probieren Sie es mit dem Online-Dolmetscher aus .

Sp3000
quelle
Sie können die Funktion sogar in der gleichen Anzahl Zeichen speichern: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 Ihre Funktion gibt nichts zurück.
Jakube
Shoot, du hast recht @Jakube
Christian Sonne
Ich bin nicht ganz sicher, wie das funktioniert, aber ich denke, Sie können das +.5s entfernen , um einige Zeichen zu speichern. Mir wurde klar, dass sie für mich sinnlos waren.
KSFT
@KSFT Zerlegt die Zeichenfolge in Intervalle, durchläuft alle a = point + .5und zählt die Anzahl der Intervalle, die genau enthalten sind a. Ohne die haben .5Sie Probleme mit Fällen wie dem [1, 0, -1]Beispiel.
Sp3000,
16

Python : 31 30 29 28 24 23 Zeichen (Python 68 Zeichen)

heSmsm&<hSkdgeSkdC,tQQQ

Probieren Sie es hier aus: Pyth Compiler / Executor

Es erwartet eine Liste von Ganzzahlen als Eingabe [-1, 3, 1, -2, 5, 2, 3, 4]

Es ist eine einfache Übersetzung meines Python-Programms:

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

Alte Lösung: Pyth 28 char

Nur aus Archivierungsgründen.

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

Ein entsprechender Python-Code wäre:

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
quelle
Ziemlich sicher, dass Sie ,QtQanstelle von verwenden könnten[QtQ)
FryAmTheEggman
iist nicht die Schnittlinie, i - 0.5ist. Und deshalb ist 1 (eigentlich 1 - 0.5 = 0.5) drinnen (-1, 1). min(a)<i<=max(a)ist äquivalent zu min(a) < i - 0.5 < max(a), was in Pyth mit min(a) < i < max(a)+1(beachte das hin heSk) gelöst wird .
Jakube
Ich denke, Sie sind hier richtig. Oder zumindest kann ich keinen Fall finden, in dem diese Logik versagt ...
Optimierer
Sie können durch die Verwendung eines Zeichens speichern g, das ist >=, wenn Sie ersetzen <dheSkmit geSkd.
isaacg
2
Danke @isaacg. Aber warum kommst du immer mit und zerstörst meine Lösung, wenn ich wirklich glücklich und zuversichtlich bin? ;-)
Jakube
10

CJam, 36 34 33 30 Bytes

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

Ich glaube, dass es einen besseren Algorithmus in freier Wildbahn gibt. Dies funktioniert jedoch unter der für alle Testfälle erforderlichen Grenze (auch auf dem Online-Compiler).

Eingabe ist wie

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

Ausgabe (für obigen Fall) ist

2

Wie es funktioniert

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

Angenommen [-1 3 1 -2 5 2 3 4], das Eingabearray sieht folgendermaßen aus:

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

Das zweite Array in der letzten Zeile sind die Falten der Zeichenfolge.

Jetzt iterieren wir [-1 3 1 -2 5 2 3 4]und berechnen die Anzahl der Sätze, in denen jeder von ihnen liegt. Holen Sie das Maximum aus dieser Anzahl heraus, erhöhen Sie sie und wir haben unsere Antwort.

Probieren Sie es hier online aus

Optimierer
quelle
10

Matlab (123) (97) (85)

Yay, endlich eine Verwendung für XNOR =) Ich bin mir sicher, dass es viel mehr Golf spielen kann.

Aber ehrlich gesagt ist es mir ein wenig peinlich, dass MatLab die Sprache wird, die ich am besten kenne = /

Ungefähre Laufzeit ist O(n^2).

EDIT2:

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

BEARBEITEN : Neue mehr Golf-Version (einschließlich Tipps von @ TennisJaheruddin, danke!)

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)

Alte Version:

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: Ich genieße deine netten kleinen Herausforderungen, kurz bevor ich ins Bett gehe!

fehlerhaft
quelle
10
Meine Frau kann XNORing nicht ausstehen
Knabberzeug
9
Zeit für @xnor, sich Notizen zu machen =)
Fehler
Ich denke, Sie können beim Finden der Schnittpunkte einiges sparen, da die Falten immer ganzzahlig sind: c=sort(a)-.5Natürlich ist der erste Punkt dann außerhalb des Bereichs, aber es ist sicherlich einfacher, damit umzugehen. Im schlimmsten Fall können Sie tun c(1)=[];. - Sie können auch den disp Befehl abzustreifen, nur etwas Berechnung wird es schreiben in diesem Fall an stdout .-- Schließlich numelkann ersetzt werdennnz
Dennis Jaheruddin
Aber ich war so stolz auf meine convHerangehensweise ... = D. Ich vergesse immer das nnz, vielen Dank!
Fehler
Ich konnte einige Möglichkeiten finden, es auf diese Weise noch kürzer zu machen! Ich benutze dispseitdem jemand kritisiert hat, dass mit der von Ihnen vorgeschlagenen Methode auch andere Zeichen (Name des var oder ans) nach stdout geschrieben werden ...
flawr
9

Mathematica 134 133 104

Spaß zu lösen, trotz der Größe des Codes. Weiteres Golfen kann noch durch Ersetzen des Gedankens von erreicht werdenIntervalMemberQ[Interval[a,b],n] durch ersetzt wird 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


Erläuterung

list1ist die gegebene Liste von Punkten list2eine verkürzte Liste, die Zahlen entfernt, die sich nicht in Falten befanden; sie sind irrelevant. Dies ist nicht erforderlich, führt jedoch zu einer klareren und effizienteren Lösung.

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}

Die Intervalle in list1und list2sind in den folgenden Diagrammen dargestellt:

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

Intervalle


Wir müssen nur eine einzelne Linie in jedem Intervall testen, das durch die Faltpunkte bestimmt wird. Die Testlinien sind die gestrichelten vertikalen Linien im Diagramm.

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

Testlinien


fFindet die Anzahl der Schnitte oder Kreuzungen jeder Testlinie. Die Linie bei x = 2,5 ergibt 5 Überfahrten. So bleiben 5 + 1 Schnurstücke übrig.

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

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

DavidC
quelle
8

Pyth, 21 Bytes

heSmsmq1xS+dSkdC,tQQQ

Probieren Sie es hier aus.

Geben Sie die Eingabe als Python-Liste ein, z [-1, 3, 1, -2, 5, 2, 3, 4]

Basierend auf @ jakubes Programm, aber mit einem verbesserten zentralen Algorithmus. Anstatt einen >Check und einen >=Check durchzuführen, mache ich einen Check .index()für die drei kombinierten Zahlen und stelle sicher, dass der Index 1 ist, was bedeutet, dass er größer als das Minimum und kleiner oder gleich dem Maximum ist.

isaacg
quelle
7

R 86, 83

Ich habe das durchgearbeitet und dann festgestellt, dass ich im Wesentlichen die gleiche Lösung gefunden habe wie Optimizer und andere, die ich vermute.

Jedenfalls ist es eine Funktion, die einen Vektor nimmt

f=function(l)max(colSums(mapply(function(n)c(l[-1],NA,l)<=n&c(l,l[-1],NA)>=n,l),T))
MickyT
quelle
OK, also bin ich voreingenommen und mag es einfach R. FWIW können Sie 3 Zeichen sparen, indem Sie Tfür "WAHR"
Carl Witthoft
@CarlWitthoft Danke für den Tipp
MickyT
4

GolfScript (43 Bytes)

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

In Bezug auf die Effizienz ist dies O (n ^ 2), vorausgesetzt, dass Vergleiche O (1) Zeit benötigen. Es unterteilt die Eingabe in Liniensegmente und zählt für jeden Startpunkt die halboffenen Liniensegmente, die es kreuzen.

Online-Demo

Peter Taylor
quelle
4

Python - 161

Damit kann wohl mehr golfen werden. gnibbler hat beim golf viel mitgeholfen.

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
quelle
1
@ MartinBüttner / Jakube Ich habe es behoben. Es funktioniert jetzt für alle Testfälle in weniger als zehn Sekunden.
KSFT
Warum gibt es zwei Ablehnungen?
KSFT
3

Rubin, 63

Ähnlich wie die Python-Lösungen im Konzept.

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

Fügen Sie vor dem Code 2 Zeichen ein, z. B. f=wenn Sie eine benannte Funktion wünschen. Vielen Dank an MarkReed .

Vektorisiert
quelle
Der nackte Prozess scheint eine akzeptable Antwort zu sein, ohne ihn einer Variablen zuzuweisen. Speichert zwei Zeichen.
Mark Reed
3

C # 73 65 Bytes

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

Als ich die Regeln las, dachte ich, ein C # -Lambda sollte ziemlich gut funktionieren.

Bearbeiten: gerade gefunden Count hat eine nützliche Überladung zum Filtern!

Sie können dies testen, indem Sie den entsprechenden delegateTyp definieren:

delegate int solver(int[] l);

Und dann

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
quelle
3

Matlab ( 63 43)

Die Eingabe erfolgt als Zeilenvektor, der an die Funktion übergeben wird f. So f([-1, 3, 1, -2, 5, 2, 3, 4])kehrt zum Beispiel zurück 6.

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

Kürzere Version:

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

Oktave (31)

In Octave bsxfunkann dank automatischem Broadcasting entfernt werden:

f=@(x)max(sum(diff(x'<x)~=0))+1
Luis Mendo
quelle
2

JavaScript (ES6) 80 82

Siehe Kommentare - Die Byteanzahl beinhaltet nicht die Zuweisung zu F

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

Test In FireFox / Firebug - Konsole

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

Ausgabe

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

edc65
quelle
2
Basierend auf den Python- lambdaLösungen müssen Sie den Funktionswert keiner tatsächlichen Variablen zuweisen, sodass Sie zwei Zeichen ablehnen können.
Mark Reed
1
Ja. Sofern in der Challenge nicht anders angegeben, sind unbenannte Funktionen vollkommen in Ordnung.
Martin Ender
1

Gelee , 10 Bytes

>þ`^ƝS$€Ṁ‘

Probieren Sie es online!

Wie es funktioniert

>þ`^Ɲ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
Caird Coinheringaahing
quelle
1

05AB1E , 6 Bytes

ε@Ôg}à

Probieren Sie es online!

Erläuterung:

ε   }    # for each element of the input
 @       # is each element >= this one? (returns list of booleans)
  Ô      # connected uniquified
   g     # length
     à   # maximum
Grimmig
quelle
0

Add ++ , 27 Bytes

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

Probieren Sie es online!

Vielen Dank an Zgarb für die APL-Antwort

Der Schlüssel zu dieser Herausforderung liegt in der Implementierung eines äußeren Produktbefehls. Leider hat Add ++ keine eingebaute Funktion, und es gibt auch keine Möglichkeit, Funktionen zu definieren, die andere Funktionen als Argumente verwenden. Wir können jedoch trotzdem eine verallgemeinerte äußere Produktfunktion erzeugen. Da der Zugriff auf eine Funktion in einer anderen Funktion nur über die Referenzierung einer vorhandenen benutzerdefinierten oder integrierten Funktion möglich ist, müssen wir eine integrierte Funktion erstellen, die auf eine solche Funktion verweist.

Eine verallgemeinerte "Tabellen" -Funktion würde ungefähr so ​​aussehen:

D,func,@@,+

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

Probieren Sie es online!

wo funcist eine dyadische Funktion, die unseren Operanden enthält. Sie können schwache Ähnlichkeiten dieser Struktur in der ursprünglichen Einreichung zu Beginn der w- Funktion sehen, aber hier wollen wir in erster Linie eine Monade äußere Produktfunktion - eine äußere Produktfunktion, die auf beiden Seiten dasselbe Argument verwendet.

Die allgemeine Tabellenfunktion macht sich zunutze, wie sich die ach quick dyadischen Funktionen nähert. Wenn der Stapel so aussieht

 [a b c d e]

Wenn er €{func}angetroffen wird , bindet der Pop edas als linkes Argument an die Dyade und ordnet diese Teilfunktion zu a, b, c, d. Die Schnellzuordnungen beziehen sich jedoch auf den gesamten Stapel und nicht auf Listen. Wir müssen also zuerst die als Argumente übergebenen Arrays reduzieren.

Die Tabellenfunktion funktioniert insgesamt so

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

Wir können dies jedoch um einiges verkürzen, da unsere äußere Tabelle monadisch sein muss und nur auf das übergebene Argument angewendet werden muss. Der ABefehl überträgt jedes Argument einzeln auf den Stapel, sodass wir nicht mit Stapelmanipulationen herumspielen müssen. Kurz gesagt, wenn unser Argument das Array ist [a b c d], müssen wir den Stapel in machen

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

Der obere Wert wird, natürlich hat die argument.You kann von dem allgemeinen Beispiel bemerkt , dass bUdas ist auspacken Befehl dh die obere Anordnung auf den Stapel splats. Um die obige Konfiguration vorzunehmen, können wir den Code verwenden

L,bUA

Probieren Sie es online!

Dies kann jedoch durch ein Byte verkürzt werden. Als Alias ​​für L,bUkönnen wir das ~Flag verwenden, um die Argumente vorher auf den Stack aufzuteilen und unser Konfigurationsbeispiel zu erstellen

L~,A

Probieren Sie es online!

Das ist der Anfang der zweiten Zeile im Programm. Jetzt haben wir ein monadisches äußeres Produkt implementiert, wir müssen nur den Rest des Algorithmus implementieren. Sobald Sie das Ergebnis der Tabelle mit <(kleiner als) erhalten haben, zählen Sie die Anzahl [0 1]und die [1 0]Paare in jeder Zeile. Schließlich nehmen wir das Maximum dieser Zählungen und erhöhen es.

Der komplette Schritt für Schritt durch ist

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]
Gemeinschaft
quelle