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.
- Otrzymasz macierz 2D, w której każda kolumna reprezentuje drążek.
- W każdej kolumnie 1 oznacza część kija, a 0 to puste miejsce
- Przechodząc od góry do dołu w każdej kolumnie, początkowo masz,
0
a jak tylko klikniesz a1
, kij zaczął się, a reszta kolumny zostanie wypełniona1
tylko - 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.
- 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)
gdziem
jest liczba wierszy in
liczba 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 :)
źródło
1
na 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).Odpowiedzi:
GolfScript, 45 znaków
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) doy
i 0 dox
. 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ębniax
-ty znaky-1
-tego wiersza w^
. To faktycznie zwraca kod ASCII znaku, więc2%
jest konieczne, aby usunąć wszystkie oprócz ostatniego bitu. Jako szczególny przypadek, jeśliy
jest 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ącey*
zmusza go do zera, tworząc w ten sposób wirtualny wiersz zerowy u góry macierzy.Dodaje się
if
nastę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,y
jest zmniejszana o jeden, a bieżąca wartośćx
zastępuje najwyższy indeks kolumny na stosie (ze starą wartością tymczasowo pozostawioną nad nim). Jeśli zero,x
jest 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,x
jeś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.źródło
Rubinowy,
8375686663 bajtówDefiniuje funkcję,
f
która przyjmuje postać tablicy 2D jako dane wejściowe.źródło
Python 2 -
71, 69, 73, 7581źródło
i
wyjdziesz poza granice, jeśli kij zajmuje całą kolumnę?j
się liczyć z0
przerwami warunku pętlii*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.
źródło
int
sygnatury funkcji, czy nie działa to z powodu zawartych tam wskaźników?C #: 236 znaków
bez golfa:
źródło
PHP 5,4 - 108 bajtów
(113 jeśli uwzględnisz
<?php
)Format wejściowy: tablica będzie czytana jako ciąg JSON.
Dodano spację dla czytelności - wszystkie znaki nowej linii i spacje wiodące można usunąć.
Wersja skrócona:
To rodzaj kradzieży algorytmu tutaj Martinowi, ale fajnie jest bawić się językami, które nie są tu tak często spotykane XD
źródło
$s=json_decode($argv[1]);$t=count($s)-1;
z$t=count($s=json_decode($argv[1]))-1;
(-3 bajtów).$t--
musi się zdarzyć tylko wtedy, gdy warunek jest spełniony.Kobra - 98
źródło
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ż
main
trzeba 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)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
0
indeksowania 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 drugiego
C
zastosowania przedkładania. (z dużą ilością dodatkowego kodu do obsługi tej funkcji).Jak poniżej opis jest nieaktualny:
Czy mogę jeszcze pograć w golfa?
Kod bez golfa (z dodatkowym wyjściem):
źródło
OCaml - 144 znaków
Pobiera dane
int array array
wejściowe i zaczyna od dołu po lewej stronie, przesuwając w górę lub w prawo, jeśli widzi a1
lub a0
. Liczba kolumn zaczyna się od0
.Stosowanie
Nie golfił
źródło
T-SQL -
7164Bierze tabelę A jako dane wejściowe
A zapytanie brzmi
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 1ORDER BY R
zapewnia odczyt tabeli z góry na dółźródło
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.
źródło
"0000", "0010", "1111"
po drugie, odpowiedź nie spełnia wymogu liniowej złożoności czasuschemat - 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.
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).
źródło
Rakieta 70
Gra w golfa:
Zakłada, że dane wejściowe to tablica dwuwymiarowa, która w Racket byłaby listą:
Nie golfowany:
Zwraca indeks kolumny z najdłuższym drążkiem.
źródło
1
?1
w matrycy lub tylko w dolnym rzędzie).JavaScript, ES6, 76 znaków
Pobiera tablicę danych wejściowych tablicy.
źródło
JavaScript ES6, 65 bajtów
Przyjmuje oba formaty wejściowe
Wyjaśniono:
Iteruje od dołu do góry. Wykorzystuje
String.prototype.indexOf()
lubArray.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, ustawiat
zmienną na ostatnie przesunięcie i nie wykonuje jużindexOf
wywołań.źródło
indexOf
działa w jednymO(log n)
lubO(n)
, więc ogólny algorytm nigdy nie będzieO(m + n)
O(m+n)