Wähle den längsten Stock

13

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.

  1. Sie erhalten eine 2D-Matrix, in der jede Spalte einen Stab darstellt.
  2. In jeder Spalte steht 1 für einen Teil des Sticks und 0 für ein Leerzeichen
  3. Wenn von oben nach unten in jeder Spalte gehen, zunächst haben Sie 0‚s und sobald Sie einen Hit 1, hat der Stick gestartet und den Rest der Säule wird mit gefüllt wird 1nur
  4. 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.
  5. 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)wobei mdie Anzahl der Zeilen und ndie 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 :)

Optimierer
quelle
2
Ich würde argumentieren, dass dies in O (n + m) nicht möglich ist, da jede Zelle den entscheidenden Wert enthalten könnte (dh die erste "1" des längsten Stabs / der längsten Spalte). Sie müssen sich also jede Zelle ansehen, die O (n * m) benötigt.
Falko
Könnte es leere Spalten geben?
Martin Ender
@Optimizer: Oh, ich verstehe. Du hast recht. :)
Falko
11
Es kann nicht in O (n + m) durchgeführt werden. Nachdem die Eingabe in ein Format konvertiert wurde, das den wahlfreien Zugriff ermöglicht, kann die verbleibende Verarbeitung 0 (n + m) sein. Sie müssen jedoch ein Programm schreiben, und im schlimmsten Fall ist die einzige 1in 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).
Peter Taylor
2
Wenn Sie Leuten erlauben möchten, " einfach eine Funktion zu erstellen, die ein Array akzeptiert ", sollte die Frage nicht besagen, dass sie ein Programm schreiben müssen. Und wenn Sie Lösungen in O (N ^ 0,5) benötigen, wobei N die Größe der Eingabe ist, sollten Sie nicht nach linearen Zeitlösungen fragen. Eine lineare Zeitlösung kann die gesamte Eingabe lesen.
Peter Taylor

Antworten:

4

GolfScript, 45 Zeichen

:^,:y;0:x{^y(=x=2%y*{y(:y;x\}{x):x}if^0=,<}do

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) yund 0 bis x. 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=das x-te Zeichen der y-1-ten Zeile in ^. Dies gibt tatsächlich den ASCII-Code des Zeichens zurück, sodass 2%alle bis auf das letzte Bit gelöscht werden müssen. In einem Sonderfall, wenn ygleich 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 folgende y*Befehl erzwingt den Wert Null, wodurch effektiv eine virtuelle Nullenreihe am oberen Rand der Matrix erstellt wird.

Das Folgende ifführt dann einen der beiden vorhergehenden Codeblöcke aus, abhängig davon, ob das gesuchte Bit nicht Null (wahr) oder Null (falsch) ist. Wenn yder Wert nicht Null ist, wird er um eins verringert, und der aktuelle Wert von xersetzt den höchsten Spaltenindex auf dem Stapel (wobei der alte Wert vorübergehend oben bleibt). Wenn Null, xwird 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 wird xwenn 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.

Ilmari Karonen
quelle
6

Ruby, 83 75 68 66 63 Bytes

f=->m{m[b=c=i=0].map{(c=i;b-=1)while(r=m[b-2])&&r[i]>0;i+=1};c}

Definiert eine Funktion, fdie die 2D-Array-Form als Eingabe annimmt.

Ich fange unten links an und verfolge die maximale Stocklänge (eigentlich minus das) und die entsprechende Spalte. Wenn es in jeder Spalte immer noch 1s über der vorherigen maximalen Stocklänge gibt, gehe ich den Stock bis zum Ende hoch und erinnere mich an die neue maximale Länge und Spalte. Das bedeutet, dass ich einmal entlang der Spalten und höchstens einmal entlang der Zeilen iteriere (genauer gesagt, ich iteriere bis zur maximalen Stablänge), was genau ist O(m+n).

Martin Ender
quelle
@Optimizer Ich habe deine zweite Bearbeitung erst gesehen, nachdem ich sie veröffentlicht habe. Sie war also sowieso im Bearbeitungsverlauf. Deshalb habe ich es einfach in einen Spoiler für Leute gesteckt, die es selbst herausfinden wollen.
Martin Ender
4

Python 2 - 71, 69, 73, 75 81

j=i=-1
M=input()
for m in M[0]:
 j+=1
 while-i<len(M)and M[i][j]:i-=1;J=j
print J
Falko
quelle
Soll dies in Python 2 oder 3 ausgeführt werden? Wie soll die Eingabe aussehen?
Feersum
1
@feersum Python 2, das Array von Arrays.
Justin
@feersum: Quincunx ist richtig. Die Eingabe ist, wie Sie vorgeschlagen haben, ein 2D-Array von Ints.
Falko
Werden Sie keine iGrenzen überschreiten, wenn ein Stock eine ganze Spalte einnimmt?
Xnor
1
Entschuldigung, aber es sieht so jaus 0, als würde sich die Schleifenbedingung ändern, um von Unterbrechungen zu zählen i*j.
Xnor
2

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.

g(int m,int n,int**a,int*r){for(*r=n;n*m;a[m][n]?m--,*r=n:--n);}

/* usage:
    m = number of rows
    n = number of columns
    a = 1-based 2D array such that a[i][j] gives the value at the ith row and jth column
    r = address of return value 
    Returns (to r) the 1-indexed location of a column with the longest length, or 0 if n=0
    */

int main()
{
    int flat[4*4] = {1, 0, 0, 0,
                     1, 0, 0, 1,
                     1, 1, 0, 1,
                     1, 1, 1, 1};
    int*twoD[4] = {flat-1,flat+3,flat+7,flat+11};
    int ret;
    g(4,4,twoD-1,&ret);
    printf("%d", ret);
    return 0;
}

// old function which determines longest length (65 bytes)
f(int m,int n,int**a,int*r){for(*r=m;n*m;a[m][n]?m--:--n);*r-=m;}
Feersum
quelle
Beeindruckend! Können Sie das ints in der Funktionssignatur zufällig verwerfen oder funktioniert das nicht aufgrund der darin enthaltenen Zeiger?
Martin Ender
1
Die Eingabe sollte nur das Array enthalten. Sie können dem Programm die Größe des Arrays nicht mitteilen.
Optimierer
Warten Sie, funktioniert das tatsächlich? Dies scheint die Länge des längsten Stocks und nicht seine Position zurückzugeben: ideone.com/YEzqzl
Martin Ender
2
@Optimizer, das ist im Grunde unmöglich in C.
Martin Ender
Könnte sein, aber das ist die Frage :)
Optimierer
2

C #: 236 Zeichen

int p(int[,] a){int y=0,s=0,i=0,x;for(;++y<=a.GetUpperBound(0);)for(x=i;x<=a.GetUpperBound(1);){if(a[y,x++]==0)break;s=y;i++;}return s;}

ungolfed:

int p(int[,] a)
{
    int selectedRow=0;
    int maxLength=0;
    for(var y = 0; y<=a.GetUpperBound(0); y++)
        for(var x=maxLength; x<=a.GetUpperBound(1); x++)
        {
            if(a[y,x++]==0)
                break;
            selectedRow=y;
            maxLength++;
        }
    return selectedRow;
}
Stephan Schinkel
quelle
2

PHP 5.4 - 108 Bytes

(113, wenn Sie die <?php)

Eingabeformat: Array wird als JSON-String gelesen.

php longest_stick.php "[[0, 0, 0, 0],[1, 0, 0, 0],[1, 1, 0, 1],[1, 1, 1, 1]]"

Leerzeichen zur besseren Lesbarkeit hinzugefügt - alle Zeilenumbrüche und führenden Leerzeichen können entfernt werden.

<?php
$t=count($s=json_decode($argv[1]))-1;
foreach($s[0] as $k=>$_)
    while($s[$t][$k]) {
        $t--;
        $l = $k;
    }
echo $l?:0;

Verkleinerte Version:

<?php $t=count($s=json_decode($argv[1]))-1;foreach($s[0] as $k=>$_)while($s[$t][$k]){$t--;$l=$k;}echo $l?:0;

Ich habe Martin hier den Algorithmus gestohlen, aber es ist schön, mit Sprachen herumzuspielen, die hier nicht so häufig vorkommen

Niet the Dark Absol
quelle
@ MartinBüttner Ich habe deinen Algorithmus "gestohlen", also sollte es jetzt O (n + m) sein. Ich denke, es ist richtig XD
Niet the Dark Absol
Sie können ersetzen $s=json_decode($argv[1]);$t=count($s)-1;mit $t=count($s=json_decode($argv[1]))-1;(-3 Bytes).
Blackhole
@ Blackhole In der Tat können Sie. Vielen Dank!
Niet the Dark Absol
@Blackhole Ich denke das würde die Funktionalität brechen. Es führt die Zuweisungen aus, auch wenn die Bedingung nicht erfüllt ist.
Niet the Dark Absol
@Blackhole Noch bricht es, ich fürchte XD $t--muss nur passieren, wenn die Bedingung erfüllt ist.
Niet the Dark Absol
2

Cobra - 98

def f(a)
    s,x,y=0,0,a.count-1
    while y+1and x<a[0].count
        while a[y][x],y,s=y-1,x
        x+=1
    print s
Οurous
quelle
2

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

int c;main(int r,char**v){for(r--;r*v[r][c];v[r][c]-48?std::cout<<c,r--:++c);}

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 0Indizierung reduzierten diese Lösung um 10 (!) Zeichen.
Wenn Sie zu c ++ wechseln, wird die Übermittlung um ein Zeichen std::cout<<kürzer als putchar(-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ähertCVorlage verwendet. (mit viel zusätzlichem Code zur Unterstützung dieser Funktion).

Die folgende Beschreibung ist nicht mehr aktuell:

cist global, also wird initialisiert mit 0
rist die Anzahl der Eingaben (Zeilen) +1 (Name des Programms)
vist das Array der Zeichenfolgen v[0], die ungültig sind (Name des Programms)
Da es mit 0 indiziert ist, rist es außerhalb der Grenzen, also dekrementieren.
Solange r!=0(auf eine gültige Zeichenfolge zeigend) und das Zeichen cin der Zeichenfolge nicht das Null-Abschlusszeichen ist, '\0'
wenn das Zeichen nicht "0" ist,
gehen Sie eine Zeile nach oben ( r) und geben Sie die Spalte aus ( c).
Andernfalls gehen Sie zur nächsten Spalte (c )

getan

Kann ich das noch weiter Golf spielen?

Ungolfed Code (mit extra Ausgabe):

#include <stdio.h>
#include <string.h>

int main(int argc, char* argv[])
{
  int rows = argc-1;
  int cols = strlen(argv[1]);
  int ans;

  printf("rows: %d, cols: %d\n",rows, cols);

  while((rows)&&cols)
  {
    if (argv[rows][cols-1]-'0')
    {
      printf("stick @%d,%d\n",cols,rows);
      ans = cols;
      rows--;
    }
    else
    {
      printf("no stick @%d,%d\n",cols,rows);
      cols--;
    }
  }
  printf("%d",ans);
}
Es verwendet die Länge der Zeichenfolgen, um die Anzahl der Spalten zu ermitteln, und argc, um die Anzahl der Zeilen zu ermitteln. Beginnend in der unteren rechten Ecke folgt es diesen einfachen Regeln: Wenn die Zelle ein Stab ist, dann gehe nach oben, setze die Antwort auf die aktuelle Spalte. Wenn die Zelle kein Stab ist, gehen Sie nach links. O (n + m): Da es sich nur nach oben und links bewegt, kann es nur maximal n + m Lesevorgänge haben. Es wird vorzeitig beendet, wenn es oben oder links vom Array abfällt.

Baldrickk
quelle
1

OCaml - 144 Zeichen

let s a=Array.(let rec f i j m=if i=0then m else if a.(i).(j)=0then if j=length a.(i)-1then m else f i(j+1)m else f(i-1)j j in f(length a-1)0 0)

Nimmt ein int array arrayals Eingabe und beginnt von unten links, bewegt sich nach oben oder rechts, wenn es ein 1oder ein sieht 0. Die Spaltenanzahl beginnt bei 0.

Verwendung

 s [| [| 0; 0; 0; 0 |]; [| 0; 0; 1; 0|]; [| 1; 0; 1; 0 |]; [| 1; 1; 1; 0 |]; [| 1; 1; 1; 1 |] |];;
 - : int = 2

Ungolfed

let s a = Array.(
  let rec f i j m = (* m is the longest stick seen so far *)
    if i=0 then m (* A column is full: this is the longest possible stick and j=m anyway *)
    else if a.(i).(j)=0 then (* current column is shorter than a previously seen stick *)
      if j=length a.(i)-1 then m (* we have examined all columns, just return m *)
      else f i(j+1) m (* start examining next column *)
    else f (i-1) j j (* current column is longer than all the ones previously seen. Check how long the stick is *)
  in
  f (length a-1) 0 0)
Virgile
quelle
0

T-SQL - 71 64

Übernimmt Tabelle A als Eingabe

SELECT IDENTITY(INT, 1, 1) R, A INTO A
FROM (VALUES
 ('0000')
,('1000')
,('1101')
,('1111')
) AS A(A)

Und die Abfrage ist

SELECT TOP(1)CHARINDEX('1',A)FROM A WHERE A LIKE'%1%' ORDER BY R

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ält

ORDER BY R stellt sicher, dass die Tabelle von oben nach unten gelesen wird

MickyT
quelle
Können Sie erklären, was in diesem Code vor sich geht? : D Keine Erfahrung mit T-SQL
Optimizer
Ich verstehe, ist die Filterung für jeden Zeilenteil also keine O (n * m) -Operation? dh nicht lineare Zeitkomplexität.
Optimierer
Schwer zu sagen. Die SQL-Engine überprüft alle Zeilen auf eine 1 in der Spalte. Es wird nur die erste Zeile von oben nach unten zurückgegeben, die qualifiziert ist. In dieser Situation wird also der gesamte Tisch durchsucht. Filtert die Zeilen mit der Spalte, die 1 enthält. Sortiert die Ergebnisse in der Identitätsspalte und gibt das erste Ergebnis zurück.
MickyT
Betrachten Sie es wie folgt: Was ist, wenn Ihre Zeilen "0000", "0000", "0000", "0001" lauten. In diesem Fall muss es bis zur letzten Zeile und bis zum letzten Zeichen der Zeile gehen, um
festzustellen,
1
Also ja, es ist O (m * n) dann :)
Optimierer
0

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.

function S(A:array of string):integer;var n,c:integer;begin n:=0; repeat c:=Pos('1',A[n]);inc(n) until c>0; result:=c;end;
Pinguino
quelle
Machst du den Pos () -Aufruf in jeder Zeile (in deinem Fall String) des Arrays?
Optimierer
@Optimiser Ja, das Programm durchsucht jeden String im Array (mit 'inc (n)'), bis es eine '1' findet. Die erste gefundene '1' ist die höchste (oder gleich hohe) '1', sodass ihre Position in der Zeichenfolge (Zeichenfolgen sind in Delphi 1-ndexiert) die Position der längsten Spalte ist. Die Routine schlägt fehl, wenn sich keine Einsen im Array befinden, aber ich glaube, dass dies eine fehlerhafte Eingabe wäre, da dann kein "längster Stick" zu finden wäre.
Penguino
1
Dies ist also zuallererst eine gültige Eingabe: "0000", "0010", "1111" Zweitens erfüllt Ihre Antwort nicht die Anforderung der linearen Zeitkomplexität
Optimierer
@Optimizer Ja, das wäre eine gültige Eingabe und identifiziert den 3. Stick korrekt. Nachdem ich den Post geschrieben hatte, wurde mir klar, dass ich mein gültiges Order N-Programm, das Arrays verwendet, in ein ungültiges Order N ^ 2-Programm umgewandelt hatte, das Strings verwendete (eine Reduzierung von ~ 160 Zeichen).
Penguino
0

Schema - 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.

(define (s l) (cond ((eq? (cdr l) '()) (car l)) (else (map + (car l) (s (cdr l)))))) (define (u l) (define (t n p q l) (cond ((eq? l '()) p) ((< n (car l)) (t (car l) q (+ 1 q) (cdr l))) (else (t n p (+ 1 q) (cdr l))))) (t 0 0 1 (s l)))

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

Pinguino
quelle
Das Summieren aller Unterlisten ist eine O (m * n) -Operation.
Martin Ender
0

Schläger 70

Golf gespielt:

(define(h m)(for/last([r m]#:final(memv 1 r))(length(takef r even?))))

Angenommen, die Eingabe ist ein zweidimensionales Array, das in Racket eine Liste von Listen wäre:

(define m 
  '((0 0 0 0)
    (1 0 0 0)
    (1 1 0 1)
    (1 1 1 1)))

Ungolfed:

(define (h m)
  ;; step through rows, stopping at the first that contains a 1
  (for/last ([r m] #:final (memv 1 r)) 
    (length (takef r even?)))) ; pop off the leading zeroes to get the column index

Gibt den Spaltenindex mit dem längsten Stick zurück.

Matthew Butterick
quelle
Sie gehen also im Grunde genommen jede Spalte durch und zählen die Anzahl der 1?
Optimierer
Ich verstehe dein Argument. Algorithmus aktualisiert.
Matthew Butterick
Dies hat immer noch eine Worst-Case-Komplexität von O (m * n) (für den Fall, dass es kein 1in der Matrix oder nur in der unteren Reihe gibt).
Martin Ender
0

JavaScript, ES6, 76 Zeichen

W=a=>(j=>{for(k=i=a.length-1;~i&~j;)a[i][j]?(k=j,i--):j--})(a[0].length-1)|k

Übernimmt ein Array von Array-Eingaben.

Optimierer
quelle
0

JavaScript ES6, 65 Byte

Nimmt beide Eingabeformate auf

f=(a,t)=>a.reduceRight((p,c)=>t+1?t:(x=c.indexOf(1,p))+1?x:t=p,0)

Erklärt:

Iteriert von unten nach oben. Verwendet String.prototype.indexOf()oder Array.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 die tVariable auf den letzten Offset und führt keine indexOfAufrufe mehr durch .

George Reith
quelle
indexOfarbeitet entweder in O(log n)oderO(n) , so dass der gesamte Algorithmus niemals inO(m + n)
Optimizer
@Optimizer Yeah erkannte, dass sein O (m * n) nicht klar dachte.
George Reith
@Optimizer Aktualisiert zu seinO(m+n)
George Reith