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):
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 2
und 3
:
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
quelle
a reasonable desktop PC
mehrdeutig?Antworten:
APL,
16 bis14 BytesVielen 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: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 vons
mit sich selbst∘.≤⍨
. Dies ergibt eine boolesche Matrix, dereni
dritte Zeile angibt, welche Elementes
kleiner oder gleich sinds[i]
:Die Vorkommen von
0 1
und1 0
in der Zeilei
markieren Stellen, an denen die Zeichenfolge über den Punkt verläufts[i] + 0.5
. Wir vergleichen diese in jeder Zeile mit2≠/
"Reduziere 2-Unterlisten um≠
":Was bleibt, ist, die Summen der Reihen mitzunehmen
+/
und eins plus das Maximum davon mit
1+⌈/
:Das Ergebnis wird in den meisten APL-Implementierungen automatisch auf STDOUT gedruckt.
quelle
×
für die Multiplikation und sehr einfachen Syntaxregeln. Google "Dyalog APL beherrschen" für eine gute Anleitung.Python,
887573 BytesNur ein einfaches Lambda
Nur um einen anderen Ansatz zu zeigen:
Pyth,
2827 BytesDas ist ungefähr gleichbedeutend mit
wird von STDIN auf die Eingabeliste angewendet. Probieren Sie es mit dem Online-Dolmetscher aus .
quelle
def f(x):max(sum((a+.5-m)*(a+.5-n)<0for m,n in zip(x,x[1:]))for a in x)+1
+.5
s entfernen , um einige Zeichen zu speichern. Mir wurde klar, dass sie für mich sinnlos waren.a = point + .5
und zählt die Anzahl der Intervalle, die genau enthalten sinda
. Ohne die haben.5
Sie Probleme mit Fällen wie dem[1, 0, -1]
Beispiel.Python :
313029282423 Zeichen (Python 68 Zeichen)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:
Alte Lösung: Pyth 28 char
Nur aus Archivierungsgründen.
Ein entsprechender Python-Code wäre:
quelle
,QtQ
anstelle von verwenden könnten[QtQ)
i
ist nicht die Schnittlinie,i - 0.5
ist. Und deshalb ist1
(eigentlich1 - 0.5 = 0.5
) drinnen(-1, 1)
.min(a)<i<=max(a)
ist äquivalent zumin(a) < i - 0.5 < max(a)
, was in Pyth mitmin(a) < i < max(a)+1
(beachte dash
inheSk
) gelöst wird .g
, das ist>=
, wenn Sie ersetzen<dheSk
mitgeSkd
.CJam,
36 34 3330 BytesIch 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
Ausgabe (für obigen Fall) ist
Wie es funktioniert
Angenommen
[-1 3 1 -2 5 2 3 4]
, das Eingabearray sieht folgendermaßen aus: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
quelle
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:
BEARBEITEN : Neue mehr Golf-Version (einschließlich Tipps von @ TennisJaheruddin, danke!)
Alte Version:
@ MartinBüttner: Ich genieße deine netten kleinen Herausforderungen, kurz bevor ich ins Bett gehe!
quelle
c=sort(a)-.5
Natürlich ist der erste Punkt dann außerhalb des Bereichs, aber es ist sicherlich einfacher, damit umzugehen. Im schlimmsten Fall können Sie tunc(1)=[];
. - Sie können auch den disp Befehl abzustreifen, nur etwas Berechnung wird es schreiben in diesem Fall an stdout .-- Schließlichnumel
kann ersetzt werdennnz
conv
Herangehensweise ... = D. Ich vergesse immer dasnnz
, vielen Dank!disp
seitdem jemand kritisiert hat, dass mit der von Ihnen vorgeschlagenen Methode auch andere Zeichen (Name des var oderans
) nach stdout geschrieben werden ...Mathematica
134 133104Spaß zu lösen, trotz der Größe des Codes. Weiteres Golfen kann noch durch Ersetzen des Gedankens von erreicht werden
IntervalMemberQ[Interval[a,b],n]
durch ersetzt wirda<n<b
.Erläuterung
list1
ist die gegebene Liste von Punktenlist2
eine 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.Die Intervalle in
list1
undlist2
sind in den folgenden Diagrammen dargestellt: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.
f
Findet die Anzahl der Schnitte oder Kreuzungen jeder Testlinie. Die Linie bei x = 2,5 ergibt 5 Überfahrten. So bleiben 5 + 1 Schnurstücke übrig.quelle
Pyth, 21 Bytes
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.quelle
R
86,83Ich 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
quelle
R
. FWIW können Sie 3 Zeichen sparen, indem SieT
für "WAHR"GolfScript (43 Bytes)
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
quelle
Python - 161
Damit kann wohl mehr golfen werden. gnibbler hat beim golf viel mitgeholfen.
quelle
Rubin, 63
Ähnlich wie die Python-Lösungen im Konzept.
Fügen Sie vor dem Code 2 Zeichen ein, z. B.
f=
wenn Sie eine benannte Funktion wünschen. Vielen Dank an MarkReed .quelle
C #
7365 BytesAls 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
delegate
Typ definieren:Und dann
quelle
Matlab (
6343)Die Eingabe erfolgt als Zeilenvektor, der an die Funktion übergeben wird
f
. Sof([-1, 3, 1, -2, 5, 2, 3, 4])
kehrt zum Beispiel zurück6
.Kürzere Version:
Oktave (31)
In Octave
bsxfun
kann dank automatischem Broadcasting entfernt werden:quelle
JavaScript (ES6) 80
82Siehe Kommentare - Die Byteanzahl beinhaltet nicht die Zuweisung zu F
Test In FireFox / Firebug - Konsole
Ausgabe
quelle
lambda
Lösungen müssen Sie den Funktionswert keiner tatsächlichen Variablen zuweisen, sodass Sie zwei Zeichen ablehnen können.Gelee , 10 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
05AB1E , 6 Bytes
Probieren Sie es online!
Erläuterung:
quelle
JavaScript (Node.js) , 71 Byte
Probieren Sie es online!
quelle
Add ++ , 27 Bytes
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:
Probieren Sie es online!
wo
func
ist 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 aussiehtWenn er
€{func}
angetroffen wird , bindet der€
Pope
das als linkes Argument an die Dyade und ordnet diese Teilfunktion zua, 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
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
A
Befehl ü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 machenDer obere Wert wird, natürlich hat die argument.You kann von dem allgemeinen Beispiel bemerkt , dass
bU
das ist auspacken Befehl dh die obere Anordnung auf den Stapel splats. Um die obige Konfiguration vorzunehmen, können wir den Code verwendenProbieren Sie es online!
Dies kann jedoch durch ein Byte verkürzt werden. Als Alias für
L,bU
können wir das~
Flag verwenden, um die Argumente vorher auf den Stack aufzuteilen und unser Konfigurationsbeispiel zu erstellenProbieren 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
quelle