Dada una lista de altura del horizonte entero no negativo, responda cuántos trazos de pincel horizontal ininterrumpido de 1 unidad de altura se necesitan para cubrirlo.

[1,3,2,1,2,1,5,3,3,4,2], visualizado como:

      5    
      5  4 
 3    5334 
 32 2 53342
13212153342

necesita nueve pinceladas:

      1    
      2  3 
 4    5555 
 66 7 88888
99999999999

Ejemplos

[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

JavaScript (Node.js) , 38 bytes

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

Pruébalo en línea!

Simplemente un algoritmo codicioso que escanea de izquierda a derecha, solo dibuja líneas si es necesario y lo dibuja el mayor tiempo posible.

Gracias Arnauld, ahorre 2 3 bytes

05AB1E ,  8 7  5 bytes

Guardado 2 bytes gracias a @Adnan

0š¥þO

Pruébalo en línea!

¿Cómo?

Esto está utilizando el algoritmo que fue encontrado por primera vez por @tsh . Si te gusta esta respuesta, ¡asegúrate de votarla también!

Cada vez que un rascacielos es más bajo o más alto que el anterior, se puede pintar 'gratis' simplemente extendiendo las pinceladas.

Por ejemplo, pintar los rascacielos $B$ y $C$ en la figura a continuación no cuesta nada.

Por otro lado, necesitamos 2 nuevas pinceladas para pintar el rascacielos $E$ , sin importar si serán reutilizadas después de eso o no.

Para el primer rascacielos, siempre necesitamos tantas pinceladas como pisos.

Convirtiendo esto en matemáticas:

Si anteponemos a la lista, esto se puede simplificar a:$0$

Comentado

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

Python 3 , 37 bytes

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

Pruébalo en línea!

_{-5 bytes cambiando a Python 3, gracias a Sarien}

Python 2 , 47 43 42 bytes

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

Pruébalo en línea!

Alt:

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

Pruébalo en línea!

Haskell , 32 bytes

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

Pruébalo en línea!

Una mejora en la solución de Lynn que rastrea el elemento anterior en plugar de mirar el siguiente elemento. Esto acorta el caso base y la llamada recursiva a cambio de la necesidad de invocar (0%).

max(h-p)0podría ser max h p-pde la misma longitud.

Haskell , 35 bytes

f(a:b:c)=max(a-b)0+f(b:c)
f a=sum a

Pruébalo en línea!

La línea 2 podría ser f[a]=asi no tuviera que manejar el caso [].

K (oK) , 12 7 bytes

-5 bytes gracias a ngn!

Un puerto k (oK) de la solución 05AB1E de Arnauld (y la solución JavaScript de tsh):

+/0|-':

Pruébalo en línea!

J , 15 bytes

Puerto AJ de la solución 05AB1E de Arnauld (y la solución JavaScript de tsh):

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

Pruébalo en línea!

Mi ingenua solución:

J , 27 bytes

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

Pruébalo en línea!

Haskell , 34 32 bytes

2 bytes recortados por Lynn

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

Pruébalo en línea!

Entonces para empezar tenemos zipWith(-). Esto toma dos listas y produce una nueva lista de sus diferencias por pares. Luego lo combinamos con xy (0:x). (0:)es una función que agrega cero al frente de una lista y al combinarla zipWith(-)obtenemos las diferencias entre los elementos consecutivos de esa lista con un cero al frente. Luego convertimos todos los negativos a cero con (max 0<$>). Esto crea una nueva lista donde cada elemento es el número de nuevos trazos que deben iniciarse en cada torre. Para obtener el total solo sumamos estos sum.

Japt , 8 bytes

-2 bytes de @Shaggy

mîT Õ¸¸è

Explicación

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

Pruébalo en línea!

MATL , 8 bytes

0whd3Y%s

Pruébalo en línea!

Prácticamente el algoritmo de @ Arnauld. Se guardó un byte (gracias @LuisMendo) al enviar en uint64lugar de seleccionar )entradas positivas.

Jalea , 5 bytes

Un puerto de mi respuesta 05AB1E , que en sí es similar a la respuesta @tsh JS .

ŻI0»S

Pruébalo en línea!

Comentado

Ż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

Japt , 7 6 bytes

änT fq

Intentalo

1 byte guardado gracias a Oliver.

ä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

R , 30 bytes

sum(pmax(0,diff(c(0,scan()))))

Pruébalo en línea!

Portar de solución @Arnauld que a su vez deriva del gran solución @tsh

Retina 0.8.2 , 21 bytes

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

1

Pruébalo en línea! El enlace incluye casos de prueba. Explicación:

\d+
$*

Convierte a unario.

(1+)(?=,\1)

Elimine todas las superposiciones con la siguiente torre, que no necesita un nuevo trazo.

1

Cuente los trazos restantes.

Lisp común, 88 87 bytes

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

no minificado

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

Pruébalo

Cuando se pinta una torre, requiere una cantidad de pinceladas igual a su altura. Estas pinceladas se traducen en todas las siguientes, lo que se indica aquí restando la altura de la torre actual de todas las otras torres (y de sí mismo, pero eso no importa). Si la siguiente torre es más corta, entonces será empujada a un número negativo, y este número negativo se restará posteriormente de las torres que siguen (lo que indica pinceladas que no se pudieron traducir de una torre anterior a las siguientes). En realidad, solo resta el número de todas las alturas de la torre, incluidas las anteriores, pero esto no importa porque no volvemos a ver las anteriores.

05AB1E , 13 10 bytes

Z>Lε@γPO}O

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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)

C # (compilador interactivo de Visual C #) con indicador /u:System.Math, 47 bytes

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

Pruébalo en línea!

Versión antigua, con bandera /u:System.Math, 63 bytes.

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

Siento que esta solución es más elegante que la primera. Atraviesa la matriz con una tupla de dos valores como valor inicial, recogiendo valores y almacena el valor antes que él en la segunda parte de la tupla.

Pruébalo en línea!

Pyth, 8 bytes

s>#0.++0

Otro puerto de la maravillosa respuesta de @ tsh . Toma la suma ( s) de los valores positivos ( >#0) de los deltas (. +) De la entrada con 0 antepuesto ( +0Q, Q final inferido).

Pruébelo en línea aquí , o verifique todos los casos de prueba a la vez aquí .

Método de unión de cadenas, 10 bytes

Esta fue la solución que escribí antes de buscar las otras respuestas.

lcj.t+d*LN

Banco de pruebas.

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

Clojure, 50 bytes

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

Pruébalo en línea! (¿Por qué esto no imprime nada?)

#( ; 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.

Java (JDK) , 57 bytes

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

Pruébalo en línea!

Otro puerto de TSH 's respuesta Javascript . Así que asegúrate de haberlos votado.

Tenga en cuenta que usé la resta en lugar de la suma porque me permitió escribir (p=x)como operando correcto en la misma declaración.

MATL , 15 14 13 bytes

ts:<~"@Y'x]vs

La entrada es un vector de columna, que se usa ;como separador.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

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

Perl 5, 21 bytes

$\+=$_>$'&&$_-$';//}{

TIO

Cómo

• -p+ }{+ $\truco
• //coincide con la cadena vacía de modo que para la siguiente línea el postmatch $'contendrá la línea anterior
• $\+=$_>$'&&$_-$'para acumular la diferencia entre la línea actual y la anterior si la actual es mayor que la anterior (también se podría escribir $\+=$_-$' if$_>$', pero Perl no analiza $\+=$_-$'if$_>$'lo mismo)

Stax , 8 bytes

Φ┐Γ╟φφ.╨

Ejecutar y depurarlo

Utiliza el enfoque ampliamente utilizado de la solución JavaScript de tsh.

Wolfram Language (Mathematica) , 34 bytes

Un puerto de @Arnauld 's solución .

Tr@Select[{##,0}-{0,##},#>0&]&@@#&

Pruébalo en línea!