Biorąc pod uwagę nieujemną liczbę całkowitą wysokości linii horyzontu, odpowiedz, ile nieprzerwanych pociągnięć pędzla o wysokości 1 jednostki potrzeba do jej pokrycia.
[1,3,2,1,2,1,5,3,3,4,2]
, wizualizowane jako:
5
5 4
3 5334
32 2 53342
13212153342
potrzebuje dziewięciu pociągnięć pędzla:
1
2 3
4 5555
66 7 88888
99999999999
Przykłady
[1,3,2,1,2,1,5,3,3,4,2]
→ 9
[5,8]
→ 8
[1,1,1,1]
→ 1
[]
→ 0
[0,0]
→ 0
[2]
→ 2
[2,0,2]
→ 4
[10,9,8,9]
→ 11
Odpowiedzi:
JavaScript (Node.js) , 38 bajtów
Wypróbuj online!
Po prostu zachłanny algorytm, który skanuje od lewej do prawej, rysuje linie tylko w razie potrzeby i rysuje tak długo, jak to możliwe.
Dzięki Arnauld, zapisz
23 bajtyźródło
05AB1E ,
8 75 bajtówZaoszczędź 2 bajty dzięki @Adnan
Wypróbuj online!
W jaki sposób?
Korzysta z algorytmu, który został po raz pierwszy znaleziony przez @tsh . Jeśli podoba Ci się ta odpowiedź, pamiętaj, aby głosować również na jej odpowiedź !
Za każdym razem, gdy wieżowiec jest niższy lub tak wysoki jak poprzedni, można go pomalować „za darmo”, po prostu przedłużając pociągnięcia pędzla.
Na przykład malowanie wieżowcówB i C na poniższym rysunku nic nie kosztuje.
W przypadku pierwszego wieżowca zawsze potrzebujemy tyle pociągnięć pędzlem, ile jest w nim podłóg.
Przekształcając to w matematykę:
Jeśli dodamy do listy, można to uprościć:0
Skomentował
źródło
0š¥ʒd}O
oszczędza bajt.ʒd}
przezþ
powinno zaoszczędzić dwa bajty.Python 3 , 37 bajtów
Wypróbuj online!
-5 bajtów, przechodząc na Python 3, dzięki Sarien
Python 2 ,
474342 bajtówWypróbuj online!
Alt:
Wypróbuj online!
źródło
Haskell , 32 bajty
Wypróbuj online!
Ulepszenie rozwiązania Lynn, które śledzi poprzedni element
p
zamiast patrzeć na następny element. To sprawia, że podstawowy przypadek i połączenie rekurencyjne są krótsze w zamian za konieczność wywołania(0%)
.max(h-p)0
może byćmax h p-p
tej samej długości.źródło
Haskell , 35 bajtów
Wypróbuj online!
Linia 2 mogłaby być,
f[a]=a
gdybym nie musiał również zajmować się sprawą[]
.źródło
K (oK) ,
127 bajtów-5 bajtów dzięki ngn!
Port k (oK) rozwiązania 05AB1E Arnaulda (i rozwiązania JavaScript tsh):
Wypróbuj online!
J , 15 bajtów
Port AJ rozwiązania 05AB1E Arnaulda (i rozwiązania JavaScript tsh):
Wypróbuj online!
Moje naiwne rozwiązanie:
J , 27 bajtów
Wypróbuj online!
źródło
':
) używa elementu niejawnej tożsamości (0
dla-
) przed listą, więc nie0,
jest to konieczne. możesz pominąć{
x}
tworzenie kompozycji:+/0|-':
Some primitive verbs result in a different special-cased initial value: +, *, - and & are provided with 0, 1, 0 or the first element of the sequence, respectively
Haskell ,
3432 bajty2 bajty przycięte przez Lynn
Wypróbuj online!
Na początek mamy
zipWith(-)
. To zajmuje dwie listy i tworzy nową listę różnic między nimi. Następnie łączymy to zx
i(0:x)
.(0:)
jest funkcją, która dodaje zero na początku listy i łącząc ją zzipWith(-)
, uzyskujemy różnice między kolejnymi elementami tej listy z zerami na początku listy. Następnie zamieniamy wszystkie ujemne na zero za pomocą(max 0<$>)
. Spowoduje to utworzenie nowej listy, w której każdy element jest liczbą nowych pociągnięć, które należy rozpocząć w każdej wieży. Aby uzyskać sumę, sumujemy jesum
.źródło
g x=sum$max 0<$>zipWith(-)x(0:x)
ma 32 bajty :)sum.zipWith((max 0.).(-))<*>(0:)
.
ma wyższy priorytet niż<*>
.Japt , 8 bajtów
-2 bajty z @Shaggy
Wyjaśnienie
Wypróbuj online!
źródło
mîT Õ¸¸è
A.y()
Nawiasem mówiąc, miłe użycie obicia.MATL , 8 bajtów
Wypróbuj online!
Prawie algorytm @ Arnaulda. Zapisano jeden bajt (dzięki @LuisMendo), przesyłając
uint64
zamiast wybierania)
pozytywnych wpisów.źródło
Galaretka , 5 bajtów
Port mojej odpowiedzi 05AB1E , która sama w sobie jest podobna do @tsh JS answer .
Wypróbuj online!
Skomentował
źródło
Japt ,
76 bajtówSpróbuj
1 bajt zapisany dzięki Oliverowi.
źródło
R , 30 bajtów
Wypróbuj online!
Przenoszenie rozwiązania @Arnauld, które z kolei wywodzi się z doskonałego rozwiązania @tsh
źródło
Retina 0.8.2 , 21 bajtów
Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:
Konwertuj na unary.
Usuń wszystkie zakładki z następną wieżą, które nie wymagają nowego pociągnięcia.
Policz pozostałe pociągnięcia.
źródło
Common Lisp,
8887 bajtównie zminimalizowane
Sprawdź to
Po pomalowaniu jednej wieży potrzeba kilku pociągnięć pędzla równych jej wysokości. Te pociągnięcia pędzla przekładają się na wszystkie następujące, o czym tutaj chodzi, odejmując wysokość bieżącej wieży od wszystkich innych wież (i samej, ale to nie ma znaczenia). Jeśli kolejna wieża jest krótsza, zostanie przesunięta do liczby ujemnej, a ta liczba ujemna zostanie następnie odjęta od kolejnych wież (wskazując pociągnięcia pędzla, których nie można było przetłumaczyć z poprzedniej wieży na następne). W rzeczywistości po prostu odejmuje liczbę od wszystkich wysokości wieży, w tym poprzednich, ale to nie ma znaczenia, ponieważ nie patrzymy ponownie na poprzednie.
źródło
05AB1E ,
1310 bajtówWypróbuj online lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie:
źródło
C # (interaktywny kompilator Visual C #) z flagą
/u:System.Math
, 47 bajtówWypróbuj online!
Stara wersja, z flagą
/u:System.Math
, 63 bajtyWydaje mi się, że to rozwiązanie jest bardziej eleganckie niż pierwsze. Przechodzi przez tablicę z krotką o dwóch wartościach jako wartością początkową, zbierając wartości i przechowuje wartość przed nią w drugiej części krotki.
Wypróbuj online!
źródło
Pyth, 8 bajtów
Kolejny port cudownej odpowiedzi @ tsh . Pobiera sumę (
s
) dodatnich wartości (>#0
) delt (. +) Danych wejściowych z 0 poprzedzonymi (+0Q
, wywnioskowano końcowe Q).Spróbuj go online tutaj , lub sprawdzić wszystkie przypadki testowe od razu tutaj .
Metoda łączenia ciągów, 10 bajtów
To było rozwiązanie, które napisałem przed przeglądaniem innych odpowiedzi.
Zestaw testowy.
źródło
Clojure, 50 bajtów
Wypróbuj online! (Dlaczego nic nie drukuje?)
źródło
Java (JDK) , 57 bajtów
Wypróbuj online!
Kolejny port TSH „s Javascript odpowiedź . Upewnij się więc, że ich oceniłeś.
Zauważ, że użyłem odejmowania zamiast dodawania, ponieważ pozwoliło mi to napisać
(p=x)
jako poprawny operand w tej samej instrukcji.źródło
MATL ,
151413 bajtówDane wejściowe to wektor kolumny, używany
;
jako separator.Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie
źródło
Perl 5, 21 bajtów
TIO
W jaki sposób
-p
+}{
+$\
trik//
dopasowuje pusty ciąg, aby w następnym wierszu postmatch$'
zawierał poprzedni wiersz$\+=$_>$'&&$_-$'
aby kumulować różnicę między bieżącą linią a poprzednią, jeśli prąd jest większy niż poprzedni (można również zapisać$\+=$_-$' if$_>$'
, ale Perl nie analizuje$\+=$_-$'if$_>$'
tego samego)źródło
Stax , 8 bajtów
Uruchom i debuguj
Wykorzystuje powszechnie stosowane podejście z rozwiązania JavaScript tsh.
źródło
Wolfram Language (Mathematica) , 34 bajty
Port @Arnauld „s rozwiązania .
Wypróbuj online!
źródło