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 są 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 :)

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.

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

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

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

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

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

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

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.

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)

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ół

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;

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

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.

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.

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