Pokrycie Skyline pociągnięciami pędzla

43

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

Adám
źródło
Dla zainteresowanych użytkowników z dużą liczbą powtórzeń: w oparciu o to zgodnie z tym .
Adám
2
Czy wszystkie pociągnięcia pędzlem są poziome?
tsh
1
@tsh Dobra uwaga. Dodany.
Adám
To nie był kodegolf, ale miałem to pytanie do testu kodu wywiadu około rok temu.
luizfzs

Odpowiedzi:

35

JavaScript (Node.js) , 38 bajtów

a=>a.map(v=>(n+=v>p&&v-p,p=v),p=n=0)|n

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 2 3 bajty

tsh
źródło
@Arnauld nice catch. zupełnie o tym zapomniałem.
tsh
Jak sobie to uświadomiłeś?
Adám
@ Adám Nic magicznego. Kiedy po raz pierwszy przeczytałem pytanie, byłem zdezorientowany, jak wyszukiwać, dopóki nie zdałem sobie sprawy, że wszystkie linie są tylko poziome. A potem ta formuła przyszła mi do głowy naturalnie ...
tsh
4
magia wydaje się być odpowiednim słowem do opisania tego procesu.
Adám
1
Chociaż jest to początek powszechnie stosowanego algorytmu, wyjaśniono go tutaj .
Adám
28

05AB1E ,  8 7  5 bajtów

Zaoszczędź 2 bajty dzięki @Adnan

0š¥þO

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ów B i C na poniższym rysunku nic nie kosztuje.

E

Budynki

W przypadku pierwszego wieżowca zawsze potrzebujemy tyle pociągnięć pędzlem, ile jest w nim podłóg.

Przekształcając to w matematykę:

S=h0+i=1nmax(hihi1,0)

Jeśli dodamy do listy, można to uprościć:0

S=i=1nmax(hihi1,0)

Skomentował

0š¥þO     # expects a list of non-negative integers  e.g. [10, 9, 8, 9]
0š        # prepend 0 to the list                    -->  [0, 10, 9, 8, 9]
  ¥       # compute deltas                           -->  [10, -1, -1, 1]
   þ      # keep only values made of decimal digits
          # (i.e. without a minus sign)              -->  ["10", "1"]
    O     # sum                                      -->  11
Arnauld
źródło
Myślę, że 0š¥ʒd}Ooszczędza bajt.
Pan Xcoder
@ Don'tbeax-tripledot Edytowałem swoją odpowiedź dokładnie tak, jak zobaczyłem twój komentarz;)
Arnauld
4
Piękne wyjaśnienie.
Adám
1
Zastąpienie ʒd}przez þpowinno zaoszczędzić dwa bajty.
Adnan
@Adnan Ah, miło. Dzięki!
Arnauld
7

Python 3 , 37 bajtów

lambda a:sum(a)-sum(map(min,a[1:],a))

Wypróbuj online!

-5 bajtów, przechodząc na Python 3, dzięki Sarien


Python 2 , 47 43 42 bajtów

lambda a:sum(a)-sum(map(min,a[1:],a[:-1]))

Wypróbuj online!

Alt:

lambda a:sum(a)-sum(map(min,zip(a[1:],a)))

Wypróbuj online!

TFeld
źródło
W Pythonie 3 możesz porzucić [: -1], oszczędzając 5 bajtów.
Sarien
@ Sarien Dzięki: D, nie wiedziałem, że mapa jest inna w Pythonie 2 i 3
TFeld
7

Haskell , 32 bajty

(0%)
p%(h:t)=max(h-p)0+h%t
p%_=0

Wypróbuj online!

Ulepszenie rozwiązania Lynn, które śledzi poprzedni element pzamiast 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)0może być max h p-ptej samej długości.

xnor
źródło
5

K (oK) , 12 7 bajtów

-5 bajtów dzięki ngn!

Port k (oK) rozwiązania 05AB1E Arnaulda (i rozwiązania JavaScript tsh):

+/0|-':

Wypróbuj online!

J , 15 bajtów

Port AJ rozwiązania 05AB1E Arnaulda (i rozwiązania JavaScript tsh):

1#.0>./2-~/\0,]

Wypróbuj online!

Moje naiwne rozwiązanie:

J , 27 bajtów

1#.2(1 0-:])\0,@|:@,~1$~"0]

Wypróbuj online!

Galen Iwanow
źródło
2
ok: każdy przed ( ':) używa elementu niejawnej tożsamości ( 0dla -) przed listą, więc nie 0,jest to konieczne. możesz pominąć { x}tworzenie kompozycji:+/0|-':
ngn
@ngn Thanks! Najwyraźniej zapomniałem o tym: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
Galen Iwanow
5

Haskell , 34 32 bajty

2 bajty przycięte przez Lynn

g x=sum$max 0<$>zipWith(-)x(0:x)

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 z xi (0:x). (0:)jest funkcją, która dodaje zero na początku listy i łącząc ją z zipWith(-), 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 je sum.

Kreator pszenicy
źródło
2
g x=sum$max 0<$>zipWith(-)x(0:x)ma 32 bajty :)
Lynn
Jak jestsum.zipWith((max 0.).(-))<*>(0:)
Lynn
@ Lynn Twój drugi będzie wymagał dodatkowych nawiasów, ponieważ .ma wyższy priorytet niż <*>.
Wheat Wizard
3

Japt , 8 bajtów

-2 bajty z @Shaggy

mîT Õ¸¸è

Wyjaśnienie

mîT Õ¸¸è      Full program. Implicit input U
                e.g. U = [2,0,2]
mîT             Map each item X and repeat T(0) X times
                     U = ["00","","00"]
    Õ           Transpose rows with columns
                     U = ["0 0","0 0"]
     ¸¸         Join using space and then split in space
                     U = ["0","0","0","0"]
        è       Return the count of the truthy values

Wypróbuj online!

Luis Felipe De Jesus Munoz
źródło
8 bajtów:mîT Õ¸¸è
Kudłaty
1
A.y()Nawiasem mówiąc, miłe użycie obicia.
Kudłaty
3

MATL , 8 bajtów

0whd3Y%s

Wypróbuj online!

Prawie algorytm @ Arnaulda. Zapisano jeden bajt (dzięki @LuisMendo), przesyłając uint64zamiast wybierania )pozytywnych wpisów.

Sanchises
źródło
3

Galaretka , 5 bajtów

Port mojej odpowiedzi 05AB1E , która sama w sobie jest podobna do @tsh JS answer .

ŻI0»S

Wypróbuj online!

Skomentował

ŻI0»S    - main link, expecting a list of non-negative integers  e.g. [10, 9, 8, 9]
Ż        - prepend 0                                             -->  [0, 10, 9, 8, 9]
 I       - compute the deltas                                    -->  [10, -1, -1, 1]
  0»     - compute max(0, v) for each term v                     -->  [10, 0, 0, 1]
    S    - sum                                                   -->  11
Arnauld
źródło
3

Japt , 7 6 bajtów

änT fq

Spróbuj

1 bajt zapisany dzięki Oliverowi.

änT xwT    :Implicit input of integer array
än         :Consecutive differences / Deltas
  T        :  After first prepending 0
    f      :Filter elements by
     q     :  Square root (The square root of a negative being NaN)
           :Implicitly reduce by addition and output
Kudłaty
źródło
1
6 bajtów
Oliver
Niezły, @Oliver; nie pomyślałbym o tym.
Kudłaty
2

Retina 0.8.2 , 21 bajtów

\d+
$*
(1+)(?=,\1)

1

Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:

\d+
$*

Konwertuj na unary.

(1+)(?=,\1)

Usuń wszystkie zakładki z następną wieżą, które nie wymagają nowego pociągnięcia.

1

Policz pozostałe pociągnięcia.

Neil
źródło
2

Common Lisp, 88 87 bajtów

(lambda(s)(let((o 0))(dolist(c s)(incf o(max 0 c))(mapl(lambda(y)(decf(car y)c))s))o))

nie zminimalizowane

(lambda (skyline)
  (let ((output 0))
    (dolist (current-skyscraper-height skyline)
      (incf output (max 0 current-skyscraper-height))
      (mapl (lambda (skyscraper)
              (decf (car skyscraper) current-skyscraper-height))
            skyline))
    output)))

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.

Charlim
źródło
Witamy w PPCG. Czy możesz podać link do internetowego środowiska testowego, aby ułatwić weryfikację?
Jonathan Frech
Tak, absolutnie. rextester.com/TKBU14782 Odpowiedź zostanie wkrótce zaktualizowana
Charlim
Dobra robota. +1 za fajny, działający pierwszy post. Miłej gry w golfa.
Jonathan Frech
1

05AB1E , 13 10 bajtów

Z>Lε@γPO}O

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

Z            # Get the maximum of the (implicit) input-list
 >           # Increase it by 1 (if the list only contains 0s)
  L          # Create a list in the range [1, max]
   ε         # Map each value to:
    @        #  Check if this value is >= for each value in the (implicit) input
     γ       #  Split into chunks of adjacent equal digits
      P      #  Take the product of each inner list
       O     #  Take the sum
        }O   # And after the map: take the sum (which is output implicitly)
Kevin Cruijssen
źródło
1

C # (interaktywny kompilator Visual C #) z flagą /u:System.Math, 47 bajtów

n=>n.Select((a,i)=>i<1?a:Max(a-n[i-1],0)).Sum()

Wypróbuj online!

Stara wersja, z flagą /u:System.Math, 63 bajty

n=>n.Aggregate((0,0),(a,b)=>(a.Item1+Max(0,b-a.Item2),b)).Item1

Wydaje 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!

Wcielenie ignorancji
źródło
1

Pyth, 8 bajtów

s>#0.++0

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.

lcj.t+d*LN

Zestaw testowy.

lcj.t+d*LNQ   Implicit: Q=eval(input()), b=<newline>, N=<quote mark>
              Trailing Q inferred
        L Q   Map each element of Q...
       * N    ... to N repeated that many times
     +b       Prepend a newline
   .t         Transpose, padding with spaces
  j           Join on newlines
 c            Split on whitespace
l             Take the length, implicit print
Sok
źródło
1

Clojure, 50 bajtów

#((reduce(fn[[s n]i][(+(max(- i n)0)s)i])[0 0]%)0)

Wypróbuj online! (Dlaczego nic nie drukuje?)

#( ; begin anonymous function
    (reduce
        (fn [[s n] i] ; internal anonymous reducing function, destructures accumulator argument into a sum and the previous item
            [(+ (max (- i n) 0) s ; the sum part of the accumulator becomes the previous sum plus the larger of zero and the difference between the current number and the last one, which is how many new strokes need to be started at this point
            i]) ; ...and the previous item part becomes the current item
        [0 0] ; the initial value of the accumulator gives no strokes yet, and nothing for them to cover yet
        %) ; reduce over the argument to the function
    0) ; and get the sum element of the last value of the accumulator.
Próbowałem utworzyć konto
źródło
Witamy w PPCG! Nic nie wiem o Clojure, ale szybkie wyszukiwanie pokazuje, że musisz ocenić leniwą pętlę for. Wypróbuj online! (Wskazówka: możesz użyć przycisku linku, aby automatycznie sformatować swoją odpowiedź). Mam nadzieję, że zostaniesz i będziesz się dobrze bawić!
Jo King
1

Java (JDK) , 57 bajtów

a->{int s=0,p=0;for(int x:a)s-=(x>p?p:x)-(p=x);return s;}

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.

Olivier Grégoire
źródło
0

MATL , 15 14 13 bajtów

ts:<~"@Y'x]vs

Dane wejściowe to wektor kolumny, używany ;jako separator.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

t       % Implicit input: column vector. Duplicate
s       % Sum
:       % Range from 1 to that. Gives a row vector
<~      % Greater or equal? Element-wise with broadcast
"       % For each column
  @     %   Push current columnn
  Y'    %   Run-length encoding. Gives vector of values (0, 1) and vector of lengths
  x     %   Delete vector of lengths
]       % End
v       % Vertically concatenate. May give an empty array
s       % Sum. Implicit display
Luis Mendo
źródło
0

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

Stax , 8 bajtów

Φ┐Γ╟φφ.╨

Uruchom i debuguj

Wykorzystuje powszechnie stosowane podejście z rozwiązania JavaScript tsh.

pustkowie
źródło