Wybierz najdłuższy kij

13

Jesteś młodym maniakiem programowania i mieszkasz z 2 innymi najlepszymi przyjaciółmi. Co tydzień jeden z was musi wykonywać wszystkie obowiązki w domu, a ty decydujesz, czyja to kolej, wybierając kij. Ten, kto wybiera najkrótszy kij, przegrywa i wykonuje wszystkie obowiązki.

Ponieważ wszyscy jesteście programistami i uwielbiacie układać puzzle, zmodyfikowaliście „Wybierz najkrótszy kij” w układankę komputerową.

Oto zasady układanki.

  1. Otrzymasz macierz 2D, w której każda kolumna reprezentuje drążek.
  2. W każdej kolumnie 1 oznacza część kija, a 0 to puste miejsce
  3. Przechodząc od góry do dołu w każdej kolumnie, początkowo masz, 0a jak tylko klikniesz a 1, kij zaczął się, a reszta kolumny zostanie wypełniona 1tylko
  4. Możesz napisać swój program, aby wybrać jedną kolumnę. Rozmiar kija w tej kolumnie określa zwycięzcę / przegranego. Rozmiar kija == liczba 1s w tej kolumnie.
  5. Jednak program ten może mieć jedynie liniową złożoność w najgorszym przypadku.

Ponieważ wszyscy jesteście programistami, będziecie wiedzieć, czy czyjś program przekracza limit czasu.

Twoim zadaniem jest:

  • Napisz program lub funkcję, która akceptuje dane wejściowe w formacie 2D lub w tablicy ciągów.
  • Dane wejściowe można pobrać z STDIN / prompt / console lub argumentu funkcji.
  • Jeśli czytasz dane wejściowe ze STDIN / zachęty, możesz założyć, że odczyt danych wejściowych i przekształcenie ich w tablicę zajmuje 0 czasu (nawet jeśli kod do tego musi być w odpowiedzi)
  • Określ kolumnę z najdłuższym w niej drążkiem.
  • Dane wyjściowe mogą być wartością zwracaną przez funkcję lub do STDOUT / console / alert.
  • Program / funkcja musi mieć liniową złożoność w najgorszym przypadku, O(m+n)gdzie mjest liczba wierszy i nliczba kolumn.

Dane wejściowe mogą mieć jeden z następujących formatów:

Tablica 2D:

[ [0, 0, 0, 0],
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [1, 1, 1, 1] ]

Tablica ciągów:

[ "0000", "1000", "1101", "1111" ]

Dane wejściowe będą miały następujące właściwości:

  • Rozmiar tablicy nie jest znany, załóż prostokąt o dowolnym rozmiarze
  • W dowolnej kolumnie od góry do dołu, jeśli zobaczysz 1, to wszystko poniżej będzie jednym
  • Dozwolone drążki z pustymi kolumnami (tj. O długości 0) .

To jest golf golfowy, więc wygrywa najkrótszy kod ! *

Wyjaśnij kod lub podaj wersję bez golfa (aby zweryfikować złożoność czasu) wraz z jednym z dwóch oczekiwanych formatów wejściowych.

AKTUALIZACJA Złożoność czasu liniowego oznacza tutaj O (n + m), gdzie n jest rozmiarem kolumny, a m jest rozmiarem wiersza. (Dla tych, którzy byli niejasni)

AKTUALIZACJA 2 Zdecydowanie można to zrobić w czasie liniowym. A jeśli publikujesz odpowiedź, możesz opóźnić opublikowanie logiki / algorytmu o kilka dni na uczciwą walkę :)

AKTUALIZACJA 3 Przejrzę wszystkie odpowiedzi w ciągu kilku godzin, aby sprawdzić złożoność czasu i program :)

Optymalizator
źródło
2
Twierdziłbym, że nie można tego zrobić w O (n + m), ponieważ każda komórka może zawierać kluczową wartość (tj. Pierwszą „1” najdłuższego drążka / kolumny). Musisz więc spojrzeć na każdą komórkę, która zajmuje O (n * m).
Falko,
Czy mogą być puste kolumny?
Martin Ender,
@Optimizer: Oh, rozumiem. Masz rację. :)
Falko,
11
Nie można tego zrobić w O (n + m). Po przekonwertowaniu danych wejściowych na format umożliwiający losowy dostęp, pozostałym przetwarzaniem może być O (n + m), ale trzeba napisać program, aw najgorszym przypadku, gdy jedyną 1na wejściu jest ostatnia komórka, to konieczne jest odczytanie całego wejścia. Nawet jeśli standardowa biblioteka języka fałszuje losowy dostęp do stdin, w scenach buforuje go, a więc zajmuje to czas Omega (n * m).
Peter Taylor
2
Jeśli chcesz pozwolić ludziom „ po prostu stworzyć funkcję, która akceptuje tablicę ”, pytanie nie powinno zawierać stwierdzenia, że ​​muszą napisać program. A jeśli potrzebujesz rozwiązań, które są w O (N ^ 0,5), gdzie N jest rozmiarem wejściowym, nie powinieneś prosić o rozwiązania czasu liniowego. Liniowe rozwiązanie czasowe może odczytać cały sygnał wejściowy.
Peter Taylor

Odpowiedzi:

4

GolfScript, 45 znaków

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

Pobiera dane wejściowe jako tablicę ciągów, zwraca (oparty na 0) indeks najwyższej kolumny. Działa w iteracjach O ( wiersze + kolumny ), a każda iteracja powinna zająć zasadniczo stały czas (przynajmniej przy założeniu arytmetyki czasu stałego). Jedynymi operacjami tablicowymi / ciągowymi wykonanymi w pętli są wyszukiwanie elementów ( =) i przyjmowanie długości ciągu ( ,), przy czym oba zajmują stały czas w GolfScript.

Wypróbuj online.

Wyjaśnienie:

Podobnie jak większość rozwiązań tutaj, ten kod działa, zaczynając od lewego dolnego rogu matrycy, przechodząc w górę lub w prawo, w zależności od tego, czy bieżącym elementem macierzy jest 1 czy 0, i śledząc kolumnę, w której ostatnio przesunął się w górę .

Na początku programu przypisuję tablicę wejściową do zmiennej ^, jej długość (tj. Liczbę wierszy) do yi 0 do x. Wartość 0 jest również pozostawiana na stosie; podczas następnej pętli zostanie zastąpiony indeksem najwyższej kolumny.

W głównej pętli ^y(=x=wyodrębnia x-ty znak y-1-tego wiersza w ^. To faktycznie zwraca kod ASCII znaku, więc 2%jest konieczne, aby usunąć wszystkie oprócz ostatniego bitu. Jako szczególny przypadek, jeśli yjest równe 0 (co może się zdarzyć, jeśli najwyższa znaleziona kolumna do tej pory sięga aż do górnego rzędu), bit wyszukany faktycznie będzie pochodził z ostatniego rzędu w macierzy (indeks -1), ale następujące y*zmusza go do zera, tworząc w ten sposób wirtualny wiersz zerowy u góry macierzy.

Dodaje się ifnastępnie wykonać jedną z dwóch bloków kodu poprzedzający go, w zależności od tego, czy spojrzał w górę bit jest niezerowe (prawda) lub zero (fałsz). Jeśli niezerowa, yjest zmniejszana o jeden, a bieżąca wartość xzastępuje najwyższy indeks kolumny na stosie (ze starą wartością tymczasowo pozostawioną nad nim). Jeśli zero, xjest po prostu zwiększane o jeden (i tymczasowo pozostawione na stosie, na szczycie najwyższego indeksu kolumny).

Na koniec ^0=wyodrębnia pierwszy wiersz macierzy, ,zwraca jego długość i <porównuje go z indeksem kolumny tymczasowo pozostawionym na stosie (który będzie równy, xjeśli został tylko zwiększony) Jeśli indeks jest mniejszy niż długość wiersza, pętla powtarza się

Ps. Na podstawie moich testów powinno być możliwe skrócenie tego programu o jeden znak poprzez zastąpienie testu długości łańcucha ,<na końcu pętli >, który przecina łańcuch o podanym indeksie i zwraca część końcową (która będzie pusta i zatem false na końcu pętli). Jednak podczas wycinania takiego ciągu wydaje się być zaimplementowana jako ciągła operacja w GolfScript (lub raczej w Ruby, który GolfScript działa na nim), nie znalazłem jednak żadnej oficjalnej dokumentacji, która to potwierdza. Dla bezpieczeństwa wybrałem nieco dłuższą, ale zdecydowanie O (1), wersję powyżej.

Ilmari Karonen
źródło
6

Rubinowy, 83 75 68 66 63 bajtów

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

Definiuje funkcję, fktóra przyjmuje postać tablicy 2D jako dane wejściowe.

Zaczynam w lewym dolnym rogu, śledząc maksymalną długość kija (właściwie minus to) i odpowiednią kolumnę. W każdej kolumnie, jeśli nadal są 1s powyżej poprzedniej maksymalnej długości drążka, podchodzę do końca i pamiętam nową maksymalną długość i kolumnę. Oznacza to, że iteruję raz wzdłuż kolumn i co najwyżej raz wzdłuż rzędów (konkretnie iteruję do maksymalnej długości drążka), co jest dokładnie O(m+n).

Martin Ender
źródło
@Optimizer Nie widziałem twojej drugiej edycji, dopóki jej nie opublikowałem, więc i tak była w historii edycji. Właśnie dlatego umieściłem go w spoilerze dla osób, które chcą to rozgryźć.
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
źródło
Czy to ma działać w Pythonie 2 lub 3? Jak powinien wyglądać wkład?
feersum
1
@feersum Python 2, tablica tablic.
Justin
@feersum: Quincunx ma rację. Dane wejściowe to tablica 2D liczb całkowitych, jak sugerowałeś.
Falko
Czy nie iwyjdziesz poza granice, jeśli kij zajmuje całą kolumnę?
xnor
1
Niestety, ale wygląda na to zmienia jsię liczyć z 0przerwami warunku pętli i*j.
xnor
2

C, 64 bajty

Edycja: dowiedziałem się, że pytanie dotyczy lokalizacji najdłuższej kolumny, a nie jej długości.

Pierwsza linia to kod w golfa, a reszta to przykładowe wywołanie.

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
źródło
Imponujący! Czy możesz przypadkiem wstawić litery intsygnatury funkcji, czy nie działa to z powodu zawartych tam wskaźników?
Martin Ender
1
Dane wejściowe powinny zawierać tylko tablicę. Nie możesz powiedzieć programowi o rozmiarze tablicy.
Optymalizator
Zaraz, czy to naprawdę działa? Wydaje się, że zwraca długość najdłuższego kija, a nie jego pozycję: ideone.com/YEzqzl
Martin Ender
2
@Optimizer, który jest w zasadzie niemożliwy w C.
Martin Ender
Być może, ale takie jest pytanie :)
Optymalizator
2

C #: 236 znaków

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

bez golfa:

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
źródło
2

PHP 5,4 - 108 bajtów

(113 jeśli uwzględnisz <?php)

Format wejściowy: tablica będzie czytana jako ciąg JSON.

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

Dodano spację dla czytelności - wszystkie znaki nowej linii i spacje wiodące można usunąć.

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

Wersja skrócona:

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

To rodzaj kradzieży algorytmu tutaj Martinowi, ale fajnie jest bawić się językami, które nie są tu tak często spotykane XD

Niet the Dark Absol
źródło
@ MartinBüttner „Ukradłem” twój algorytm, więc powinien być teraz O (n + m). Myślę, że to prawda XD
Niet the Dark Absol
Można wymienić $s=json_decode($argv[1]);$t=count($s)-1;z $t=count($s=json_decode($argv[1]))-1;(-3 bajtów).
Blackhole,
@Blackhole Rzeczywiście możesz. Dziękuję Ci!
Niet the Dark Absol
@Blackhole Myślę, że to zepsułoby funkcjonalność. Wykona zadania, nawet jeśli warunek nie zostanie spełniony.
Niet the Dark Absol
@Blackhole Nadal go psuje, obawiam się, że XD $t--musi się zdarzyć tylko wtedy, gdy warunek jest spełniony.
Niet the Dark Absol
2

Kobra - 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
Obrzydliwe
źródło
2

C ++ :: 78

W przeciwieństwie do innych rozwiązań C jest to cały program. (nie jest wymagane wywołanie, nie trzeba podawać funkcji rozmiaru tablicy). Niestety oznacza to, że jest ono dłuższe, niż maintrzeba użyć zamiast nazwy funkcji jednoznakowej, muszę interpretować dane wejściowe, a następnie wypisywać odpowiedź, gdy inne rozwiązanie obsługuje to „gdzie indziej”. Również mój pierwszy golf.
skompilowany z g++ file.cpp -include iostream, uruchom z ./a 000 010 110 111(na przykład) == tablicą ciągów (uważam, że jest to dozwolone w specyfikacji pytania)

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

Powyższa wersja wyświetla bieżące najlepsze znalezione do tej pory podczas każdej iteracji. Ostatnia cyfra wyjściowa jest odpowiedzią. Przejście z przetwarzania z lewego dolnego rogu zamiast dolnego prawego i 0indeksowania zmniejszyło to rozwiązanie o 10 (!) Znaków.
przełączenie na c ++ upuszcza przesyłanie o jeden znak więcej, ponieważ std::cout<<jest krótsze niż, putchar(-48)i powinno także wyraźnie obsługiwać więcej niż 9 drążków z odpowiednim wyjściem (chociaż może być trudniej rozróżnić każde wyjście)
Usunięcie pola odpowiedzi i wysłanie go bezpośrednio wycina kolejne 6 znaków. Teraz wyświetla najlepszy prąd tylko wtedy, gdy przesuwa się w górę, co odcina przynajmniej część mocy wyjściowej.
Cały plik ma teraz tylko 78 bajtów - zbliżając się do funkcji jedynego rozwiązania drugiegoCzastosowania przedkładania. (z dużą ilością dodatkowego kodu do obsługi tej funkcji).

Jak poniżej opis jest nieaktualny:

cjest globalny, więc jest inicjalizowany z 0
rliczbą wejść (wierszy) +1 (nazwa programu)
vto tablica ciągów znaków z v[0]niepoprawnością (nazwa programu)
Ponieważ jest zindeksowana 0, rjest poza zakresem, więc zmniejsza się.
Chociaż r!=0(wskazując na prawidłowy ciąg) i znak cw łańcuchu nie jest null terminator '\0'
jeśli postać nie „0” jest
udać się wiersz ( r) i kolumny (wyjście c)
jeszcze przejść do następnej kolumny ( c)

zrobić

Czy mogę jeszcze pograć w golfa?

Kod bez golfa (z dodatkowym wyjściem):

#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);
}
Używa długości ciągów, aby znaleźć liczbę kolumn i argc, aby znaleźć liczbę wierszy. Zaczynając w prawym dolnym rogu, postępuje według tych prostych zasad: Jeśli komórka jest kijem, a następnie przejdź w górę, ustaw odpowiedź na bieżącą kolumnę. Jeśli komórka nie jest kijem, przesuń się w lewo. O (n + m): ponieważ przesuwa się tylko w górę i w lewo, może mieć tylko odczyt max n + m. Wychodzi wcześniej, jeśli spadnie z górnej lub lewej strony tablicy.

Baldrickk
źródło
1

OCaml - 144 znaków

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)

Pobiera dane int array arraywejściowe i zaczyna od dołu po lewej stronie, przesuwając w górę lub w prawo, jeśli widzi a 1lub a 0. Liczba kolumn zaczyna się od 0.

Stosowanie

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

Nie golfił

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
źródło
0

T-SQL - 71 64

Bierze tabelę A jako dane wejściowe

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

A zapytanie brzmi

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

SQLFiddle

Zwraca pierwszy wiersz z tabeli uporządkowanej według r, gdzie jest 1 w ciągu a.

TOP(1) ogranicza wynik do pierwszego zwróconego wiersza.

CHARINDEX('1',A) zwraca pozycję pierwszej 1 w ciągu lub zero, jeśli nie zostanie znaleziona.

WHERE A LIKE'%1%' Filtruje do wierszy, w których A zawiera 1

ORDER BY R zapewnia odczyt tabeli z góry na dół

MickyT
źródło
Czy możesz wyjaśnić, co się dzieje w tym kodzie? : D Brak doświadczenia z T-SQL
Optymalizator
Rozumiem, więc czy filtrowanie w każdym wierszu nie jest operacją O (n * m)? tj. nieliniowa złożoność czasu.
Optymalizator
Trudno powiedzieć. Aparat SQL sprawdzi wszystkie wiersze pod kątem 1 w kolumnie. Zwróci tylko pierwszy wiersz, który się kwalifikuje. W tej sytuacji skanuje cały stół. Filtruje wiersze z kolumną zawierającą 1. Sortuje wyniki w kolumnie tożsamości i zwraca pierwszy wynik.
MickyT,
Spójrz na to w następujący sposób: Co, jeśli Twoje wiersze mają postać „0000”, „0000”, „0000”, „0001”. W takim przypadku będzie musiał przejść do ostatniego wiersza i do ostatniego znaku w wierszu, aby dowiedzieć się o obecności 1
Optimizer
1
Więc tak, to jest O (m * n) :)
Optimizer
0

Delphi 122 znaków

Westchnienie ... to taki obszerny język.

Aktualizacja: musiałem dodać 6 znaków przy zmianie funkcji typu powrotu z I na liczbę całkowitą. Funkcja nadal kompilowana, ponieważ program testowy miał „typ I = liczba całkowita;” instrukcja pozostała z wcześniejszej wersji programu.

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;
Pingwin
źródło
Czy wykonujesz wywołanie Pos () w każdym wierszu (w twoim przypadku łańcuchu) tablicy?
Optymalizator
@Optimiser Tak, program przeszukuje każdy ciąg w tablicy (używając „inc (n)”), aż znajdzie „1”. Pierwsza znaleziona „1” będzie najwyższą (lub równą najwyższą) „1”, więc jej pozycja w łańcuchu (łańcuchy są oznaczone w delphi 1) będzie pozycją najdłuższej kolumny. Rutyna kończy się niepowodzeniem, jeśli w tablicy nie ma żadnych „1”, ale wierzę, że byłoby to zepsute wejście, ponieważ nie byłoby wtedy „najdłuższego drążka” do znalezienia.
Penguino,
1
Po pierwsze, jest to prawidłowy sygnał wejściowy: "0000", "0010", "1111"po drugie, odpowiedź nie spełnia wymogu liniowej złożoności czasu
Optymalizator
@Optimizer Tak, to byłoby prawidłowe wejście i poprawnie identyfikuje trzeci drążek. Ale po napisaniu postu zdałem sobie sprawę, że przekonwertowałem mój prawidłowy program N rzędu, który używał tablic, na niepoprawny program N ^ 2 rzędu, który używał łańcuchów (ścigając redukcję z ~ 160 znaków).
Penguino
0

schemat - 236 znaków

Nawet dłużej niż wersja delphi ... prawdopodobnie istnieje sposób, aby zrobić to znacznie wydajniej dzięki schematowi. A nawet gorzej - właśnie zauważyłem, że to porządek m * n.

(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 jest listą formularza ”((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1)). Myślę, że to uczciwa reprezentacja danych wejściowych tablicy 2D dla schematu.

(sl) sumuje n-ty element każdej z podlist listy listy nuimberów, więc (s '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1))) zwróci (3 2 1 2).

(ul) zwraca „indeks” największego wpisu na liście liczb (za pomocą funkcji pomocniczej t), więc (u ”(3 2 1 2)) zwróci 1 (jako największy element„ 3 na liście ” (3 2 1 2) znajduje się w pozycji 1).

Pingwin
źródło
Podsumowanie wszystkich list podrzędnych jest operacją O (m * n).
Martin Ender
0

Rakieta 70

Gra w golfa:

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

Zakłada, że ​​dane wejściowe to tablica dwuwymiarowa, która w Racket byłaby listą:

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

Nie golfowany:

(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

Zwraca indeks kolumny z najdłuższym drążkiem.

Matthew Butterick
źródło
Więc w zasadzie przeglądasz każdą kolumnę i liczysz liczbę 1?
Optymalizator
Rozumiem co masz na myśli. Algorytm zaktualizowany.
Matthew Butterick
Nadal ma to najgorszy przypadek złożoności O (m * n) (w przypadku, gdy nie ma go 1w matrycy lub tylko w dolnym rzędzie).
Martin Ender
0

JavaScript, ES6, 76 znaków

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

Pobiera tablicę danych wejściowych tablicy.

Optymalizator
źródło
0

JavaScript ES6, 65 bajtów

Przyjmuje oba formaty wejściowe

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

Wyjaśniono:

Iteruje od dołu do góry. Wykorzystuje String.prototype.indexOf()lub Array.prototype.indexOf()zależy od danych wejściowych dla każdej wartości. Znajduje pierwszy indeks każdego wiersza z 1 od poprzedniego przesunięcia, jeśli nie znajdzie żadnego, ustawia tzmienną na ostatnie przesunięcie i nie wykonuje już indexOfwywołań.

George Reith
źródło
indexOfdziała w jednym O(log n)lub O(n), więc ogólny algorytm nigdy nie będzie O(m + n)
włączony
@Optimizer Tak, zdałem sobie sprawę, że to było O (m * n), nie myślałem prosto.
George Reith,
@Optimizer ZaktualizowanoO(m+n)
George Reith