Sie sind ein junger Programmierer, der mit Ihren beiden besten Freunden zusammenlebt. Jede Woche muss einer von euch alle Aufgaben des Hauses erledigen und ihr entscheidet, wer an der Reihe ist, indem ihr einen Stock auswählt. Derjenige, der den kürzesten Stock auswählt, verliert und erledigt alle Aufgaben.
Da Sie alle Programmierer sind und gerne Rätsel erstellen, haben Sie den "Pick the Shortest Stick" in ein Computerpuzzle verwandelt.
Hier sind die Regeln des Puzzles.
- Sie erhalten eine 2D-Matrix, in der jede Spalte einen Stab darstellt.
- In jeder Spalte steht 1 für einen Teil des Sticks und 0 für ein Leerzeichen
- Wenn von oben nach unten in jeder Spalte gehen, zunächst haben Sie
0
‚s und sobald Sie einen Hit1
, hat der Stick gestartet und den Rest der Säule wird mit gefüllt wird1
nur - Sie können Ihr Programm schreiben, um eine Spalte auszuwählen. Die Größe des Schlägers in dieser Spalte bestimmt den Gewinner / Verlierer. Stickgröße == Anzahl der Einsen in dieser Spalte.
- Dieses Programm kann jedoch nur eine lineare Zeitkomplexität im ungünstigsten Fall aufweisen.
Da Sie alle Programmierer sind, wissen Sie, ob das Programm eines anderen die zeitliche Komplexitätsgrenze überschreitet.
Ihre Aufgabe ist es:
- Schreiben Sie ein Programm oder eine Funktion, die Eingaben in einem 2D-Format oder einem Array von Zeichenfolgen akzeptiert.
- Die Eingabe kann über STDIN / prompt / console oder ein Funktionsargument erfolgen.
- Wenn Sie die Eingabe von STDIN / prompt lesen, können Sie davon ausgehen, dass das Lesen der Eingabe und das Konvertieren in ein Array 0-mal dauert (obwohl der Code dafür in Ihrer Antwort vorhanden sein muss).
- Bestimmen Sie die Säule mit dem längsten Stock.
- Die Ausgabe kann der Rückgabewert der Funktion oder STDOUT / console / alert sein.
- Das Programm / die Funktion muss eine lineare Zeitkomplexität im ungünstigsten Fall haben,
O(m+n)
wobeim
die Anzahl der Zeilen undn
die Anzahl der Spalten ist.
Die Eingabe kann in einem der folgenden Formate erfolgen:
2D-Array:
[ [0, 0, 0, 0],
[1, 0, 0, 0],
[1, 1, 0, 1],
[1, 1, 1, 1] ]
Reihe von Zeichenfolgen:
[ "0000", "1000", "1101", "1111" ]
Die Eingabe hat folgende Eigenschaften:
- Die Größe des Arrays ist unbekannt. Nehmen Sie ein Rechteck beliebiger Größe an
- Wenn Sie in einer Spalte von oben nach unten eine 1 sehen, ist alles unten eine Eins
- Leere Spalten (dh 0-Länge) Stöcke sind erlaubt.
Dies ist ein Code-Golf, also gewinnt der kürzeste Code ! *
Bitte erläutern Sie Ihren Code oder geben Sie die unbenutzte Version (um die zeitliche Komplexität zu überprüfen) zusammen mit dem von Ihnen erwarteten Eingabeformat an.
UPDATE Die lineare Zeitkomplexität bedeutet hier O (n + m), wobei n die Spaltengröße und m die Zeilengröße ist. (Für diejenigen, die unklar waren)
UPDATE 2 Dies kann definitiv in linearer Zeit erfolgen. Und wenn Sie eine Antwort veröffentlichen, können Sie die Veröffentlichung der Logik / des Algorithmus für einen fairen Kampf um ein paar Tage verschieben :)
UPDATE 3 Ich werde in ein paar Stunden alle Antworten durchgehen, um die Zeitkomplexität und das Programm zu überprüfen :)
quelle
1
in der Eingabe die allerletzte Zelle Es ist notwendig, die gesamte Eingabe zu lesen. Selbst wenn die Standardbibliothek einer Sprache einen zufälligen Zugriff auf stdin fälscht, puffert sie diese unter den Szenen und die dafür benötigte Zeit ist Omega (n * m).Antworten:
GolfScript, 45 Zeichen
Nimmt die Eingabe als ein Array von Zeichenfolgen und gibt den (0-basierten) Index der höchsten Spalte zurück. Es wird in O- Iterationen ( Zeilen + Spalten ) ausgeführt, und jede Iteration sollte im Wesentlichen eine konstante Zeit dauern (zumindest unter der Annahme einer Arithmetik mit konstanter Zeit). Die einzigen Array- / String-Operationen, die in der Schleife ausgeführt werden, sind Element-Lookups (
=
) und die Länge eines Strings (,
), die beide in GolfScript eine konstante Zeit beanspruchen.Probieren Sie es online aus.
Erläuterung:
Wie die meisten Lösungen hier funktioniert dieser Code, indem er in der unteren linken Ecke der Matrix beginnt, nach oben oder rechts geht, je nachdem, ob das aktuelle Element der Matrix 1 oder 0 ist, und die Spalte verfolgt, in der es zuletzt nach oben verschoben wurde .
Zu Beginn des Programms weise ich der Variablen das Eingabearray zu
^
, seine Länge (dh die Anzahl der Zeilen)y
und 0 bisx
. Der Wert 0 bleibt ebenfalls auf dem Stapel; Während der folgenden Schleife wird es durch den Index der höchsten Spalte ersetzt.Extrahiert in der Hauptschleife
^y(=x=
dasx
-te Zeichen dery-1
-ten Zeile in^
. Dies gibt tatsächlich den ASCII-Code des Zeichens zurück, sodass2%
alle bis auf das letzte Bit gelöscht werden müssen. In einem Sonderfall, wenny
gleich 0 ist (was passieren kann, wenn die höchste gefundene Spalte bis zur obersten Zeile reicht), wird das nachgeschlagene Bit tatsächlich von der letzten Zeile in der Matrix (Index -1) kommen, aber Der folgendey*
Befehl erzwingt den Wert Null, wodurch effektiv eine virtuelle Nullenreihe am oberen Rand der Matrix erstellt wird.Das Folgende
if
führt dann einen der beiden vorhergehenden Codeblöcke aus, abhängig davon, ob das gesuchte Bit nicht Null (wahr) oder Null (falsch) ist. Wenny
der Wert nicht Null ist, wird er um eins verringert, und der aktuelle Wert vonx
ersetzt den höchsten Spaltenindex auf dem Stapel (wobei der alte Wert vorübergehend oben bleibt). Wenn Null,x
wird einfach um eins inkrementiert (und vorübergehend auf dem Stapel über dem höchsten Spaltenindex belassen).Schließlich
^0=
extrahiert die erste Zeile der Matrix,,
kehrt seine Länge, und<
vergleicht sie mit dem Spaltenindex auf dem Stapel vorübergehend verlassen (das gleich wirdx
wenn es nur inkrementiert) Wenn der Index geringer ist, dass die Länge der Zeile, die Schleife wiederholt.Ps. Basierend auf meinen Tests sollte es möglich sein, dieses Programm um ein Zeichen zu verkürzen, indem der Stringlängentest
,<
am Ende der Schleife durch ersetzt wird>
, der den String am angegebenen Index abschneidet und den Endteil (der leer sein wird, und zurückgibt also falsch, am Ende der Schleife). Während das Schneiden einer solchen Zeichenfolge in GolfScript (oder besser gesagt in Ruby, auf dem GolfScript läuft) als eine Operation mit konstanter Zeit implementiert zu sein scheint , habe ich keine offizielle Dokumentation gefunden, die dies sagt. Aus Sicherheitsgründen habe ich mich für die etwas längere, aber definitiv O (1) -Version entschieden.quelle
Ruby,
8375686663 BytesDefiniert eine Funktion,
f
die die 2D-Array-Form als Eingabe annimmt.quelle
Python 2 -
71, 69, 73, 7581quelle
i
Grenzen überschreiten, wenn ein Stock eine ganze Spalte einnimmt?j
aus0
, als würde sich die Schleifenbedingung ändern, um von Unterbrechungen zu zähleni*j
.C 64 Bytes
Bearbeiten: Ich habe erfahren, dass die Frage nach der Position der längsten Spalte und nicht nach ihrer Länge fragt.
Die erste Zeile ist der Golfcode und der Rest ist der Beispielaufruf.
quelle
int
s in der Funktionssignatur zufällig verwerfen oder funktioniert das nicht aufgrund der darin enthaltenen Zeiger?C #: 236 Zeichen
ungolfed:
quelle
PHP 5.4 - 108 Bytes
(113, wenn Sie die
<?php
)Eingabeformat: Array wird als JSON-String gelesen.
Leerzeichen zur besseren Lesbarkeit hinzugefügt - alle Zeilenumbrüche und führenden Leerzeichen können entfernt werden.
Verkleinerte Version:
Ich habe Martin hier den Algorithmus gestohlen, aber es ist schön, mit Sprachen herumzuspielen, die hier nicht so häufig vorkommen
quelle
$s=json_decode($argv[1]);$t=count($s)-1;
mit$t=count($s=json_decode($argv[1]))-1;
(-3 Bytes).$t--
muss nur passieren, wenn die Bedingung erfüllt ist.Cobra - 98
quelle
C ++ :: 78
Im Gegensatz zur anderen C-Lösung ist dies das gesamte Programm. (Kein Aufruf erforderlich, die Funktion muss nicht über die Größe des Arrays informiert werden.) Leider bedeutet dies, dass es länger ist, da
main
anstelle eines einzelnen Zeichens ein Funktionsname verwendet werden muss, ich muss die Eingabe interpretieren und dann die Antwort ausgeben, wobei die andere Lösung das "anderswo" behandelt. Auch mein erster Code Golf.kompiliert mit
g++ file.cpp -include iostream
, laufe mit./a 000 010 110 111
(zum Beispiel) == Array von Strings (ich glaube das ist in der Fragenspezifikation erlaubt)Die obige Version gibt bei jeder Iteration die aktuell besten Ergebnisse aus. Die endgültige Ausgabeziffer ist die Antwort. Das Umschalten von der Verarbeitung von links unten anstelle von rechts unten und die
0
Indizierung reduzierten diese Lösung um 10 (!) Zeichen.Wenn Sie zu c ++ wechseln, wird die Übermittlung um ein Zeichen
std::cout<<
kürzer alsputchar(-48)
und es sollten ausdrücklich mehr als 9 Sticks mit korrekter Ausgabe unterstützt werden. Es gibt jetzt nur den Strom am besten aus, wenn es nach oben fährt, wodurch zumindest ein Teil der Ausgabe abgeschnitten wird.
Die gesamte Datei ist jetzt nur noch 78 Bytes groß - eine Lösung, die sich der der anderen nur annähert
C
Vorlage verwendet. (mit viel zusätzlichem Code zur Unterstützung dieser Funktion).Die folgende Beschreibung ist nicht mehr aktuell:
Kann ich das noch weiter Golf spielen?
Ungolfed Code (mit extra Ausgabe):
quelle
OCaml - 144 Zeichen
Nimmt ein
int array array
als Eingabe und beginnt von unten links, bewegt sich nach oben oder rechts, wenn es ein1
oder ein sieht0
. Die Spaltenanzahl beginnt bei0
.Verwendung
Ungolfed
quelle
T-SQL -
7164Übernimmt Tabelle A als Eingabe
Und die Abfrage ist
SQLFiddle
Dies gibt die erste Zeile aus der Tabelle a zurück, die nach r geordnet ist, wobei die Zeichenfolge a eine 1 enthält.
TOP(1)
Beschränkt das Ergebnis auf die erste zurückgegebene Zeile.CHARINDEX('1',A)
Gibt die Position der ersten 1 in der Zeichenfolge oder Null zurück, wenn sie nicht gefunden wird.WHERE A LIKE'%1%'
Filtert nach Zeilen, in denen A eine 1 enthältORDER BY R
stellt sicher, dass die Tabelle von oben nach unten gelesen wirdquelle
Delphi 122 Zeichen
Seufz ... es ist so eine voluminöse Sprache.
Update: musste 6 Zeichen in wechselnder Funktion den Rückgabetyp von I auf Integer setzen. Die Funktion, die immer noch als Testprogramm kompiliert wurde, hatte den Wert "Typ I = Ganzzahl;" Anweisung von einer früheren Version des Programms übrig.
quelle
"0000", "0010", "1111"
Zweitens erfüllt Ihre Antwort nicht die Anforderung der linearen ZeitkomplexitätSchema - 236 Zeichen
Sogar länger als die Delphi-Version ... es gibt wahrscheinlich eine Möglichkeit, dies mit Schema viel effizienter zu machen. Und noch schlimmer - mir ist gerade aufgefallen, dass es Auftrag m * n ist.
l ist eine Liste der Form '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1)). Ich denke, das ist eine faire Darstellung einer 2D-Array-Eingabe für Schema.
(sl) summiert die n-ten Elemente jeder der Unterlisten einer Liste von Listen von Zahlen, so dass (s '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1))) würde zurückkehren (3 2 1 2).
(ul) gibt den 'Index' des größten Eintrags einer Liste von Zahlen zurück (unter Verwendung der Hilfsfunktion t), daher gibt (u '(3 2 1 2)) 1 zurück (als das größte Element' 3 in der Liste ') (3 2 1 2) befindet sich an Position 1).
quelle
Schläger 70
Golf gespielt:
Angenommen, die Eingabe ist ein zweidimensionales Array, das in Racket eine Liste von Listen wäre:
Ungolfed:
Gibt den Spaltenindex mit dem längsten Stick zurück.
quelle
1
?1
in der Matrix oder nur in der unteren Reihe gibt).JavaScript, ES6, 76 Zeichen
Übernimmt ein Array von Array-Eingaben.
quelle
JavaScript ES6, 65 Byte
Nimmt beide Eingabeformate auf
Erklärt:
Iteriert von unten nach oben. Verwendet
String.prototype.indexOf()
oderArray.prototype.indexOf()
abhängig von der Eingabe für jeden Wert. Findet den ersten Index jeder Zeile mit einer 1 vom vorherigen Offset. Findet er keine, setzt er diet
Variable auf den letzten Offset und führt keineindexOf
Aufrufe mehr durch .quelle
indexOf
arbeitet entweder inO(log n)
oderO(n)
, so dass der gesamte Algorithmus niemals inO(m + n)
O(m+n)