Cobrindo um horizonte com pinceladas

43

Dada uma lista de altura do horizonte inteiro não negativa, responda quantas pinceladas horizontais ininterruptas com 1 unidade de altura são necessárias para cobri-la.

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

      5    
      5  4 
 3    5334 
 32 2 53342
13212153342

precisa de nove pinceladas:

      1    
      2  3 
 4    5555 
 66 7 88888
99999999999

Exemplos

[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ão
fonte
Para usuários de alta reputação interessados: com base nisso , de acordo com isso .
Adám 04/02
2
Então, todas as pinceladas são horizontais?
tsh
1
@tsh Bom ponto. Adicionado.
Adám 04/02
Não era um codegolf, mas eu fiz essa pergunta para um teste de código de entrevista cerca de um ano atrás.
luizfzs 6/02

Respostas:

35

JavaScript (Node.js) , 38 bytes

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

Experimente online!

Simplesmente um algoritmo ganancioso que escaneia da esquerda para a direita, apenas desenha linhas se necessário e desenha o maior tempo possível.

Obrigado Arnauld, economize 2 3 bytes

tsh
fonte
@ Arnauld boa captura. esqueci totalmente.
tsh
Como você percebeu isso?
Adám 04/02
@ Adám Nada de mágico. Na primeira vez que li a pergunta, fiquei confuso sobre como pesquisar até perceber que todas as linhas são horizontais apenas. E então esta fórmula me veio à mente naturalmente ...
tsh
4
magia parece uma palavra adequada para descrever esse processo.
Adám 04/02
1
Embora essa seja a origem do algoritmo agora amplamente usado, é explicado aqui .
Adám
28

05AB1E ,  8 7  5 bytes

Guardado 2 bytes graças a @Adnan

0š¥þO

Experimente online!

Quão?

Isso está usando o algoritmo encontrado pela primeira vez por @tsh . Se você gosta desta resposta, não deixe de votar também na resposta !

Cada vez que um arranha-céu é menor ou igual ao anterior, ele pode ser pintado 'de graça', simplesmente estendendo as pinceladas.

Por exemplo, pintar arranha-céus B e C na figura abaixo não custa nada.

Por outro lado, precisamos de duas pinceladas novas para pintar o arranha-céu E , independentemente de serem reutilizadas depois ou não.

edifícios

Para o primeiro arranha-céu, sempre precisamos de tantas pinceladas quanto de pisos.

Transformando isso em matemática:

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

Se anexarmos à lista, isso poderá ser simplificado para:0

S=i=1nmax(hihi1,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
Arnauld
fonte
Eu acho que 0š¥ʒd}Oeconomiza um byte.
Sr. Xcoder
@ Don'tbeax-tripledot Eu estava editando minha resposta exatamente quando vi seu comentário;)
Arnauld
4
Linda explicação.
Adám 04/02
1
Substituir ʒd}por þdeve economizar dois bytes.
Adnan
@ Adnan Ah, que bom. Obrigado!
Arnauld
7

Python 3 , 37 bytes

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

Experimente online!

-5 bytes mudando para Python 3, graças a Sarien


Python 2 , 47 43 42 bytes

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

Experimente online!

Alt:

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

Experimente online!

TFeld
fonte
No Python 3, você pode abandonar o [: -1], economizando 5 bytes.
Sarien 04/02
@ Sarien Obrigado: D, eu não sabia que o mapa é diferente nos python 2 e 3
TFeld 04/02
7

Haskell , 32 bytes

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

Experimente online!

Uma melhoria na solução de Lynn que rastreia o elemento anterior em pvez de olhar para o próximo elemento. Isso torna o caso base e a chamada recursiva mais curtos em troca da necessidade de chamar (0%).

max(h-p)0pode ter max h p-po mesmo comprimento.

xnor
fonte
5

K (oK) , 12 7 bytes

-5 bytes graças a ngn!

Uma porta k (oK) da solução 05AB1E da Arnauld (e a solução JavaScript da tsh):

+/0|-':

Experimente online!

J , 15 bytes

Porta AJ da solução 05AB1E da Arnauld (e solução JavaScript da tsh):

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

Experimente online!

Minha solução ingênua:

J , 27 bytes

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

Experimente online!

Galen Ivanov
fonte
2
oK: cada prior ( ':) usa um elemento de identidade implícito ( 0for -) antes da lista, portanto, 0,é desnecessário. você pode omitir { x}para torná-lo uma composição:+/0|-':
ngn
@ngn Obrigado! Aparentemente eu esqueci isso: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 Ivanov
5

Haskell , 34 32 bytes

2 bytes aparados por Lynn

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

Experimente online!

Então, para começar, temos zipWith(-). Isso leva duas listas e produz uma nova lista de suas diferenças aos pares. Em seguida, combinamos com xe (0:x). (0:)é uma função que adiciona zero à frente de uma lista e, combinando-a zipWith(-), obtemos as diferenças entre elementos consecutivos dessa lista com um zero na frente. Então nós zeramos todos os negativos (max 0<$>). Isso cria uma nova lista onde cada elemento é o número de novos traçados que devem ser iniciados em cada torre. Para obter o total, basta somar isso sum.

Assistente de Trigo
fonte
2
g x=sum$max 0<$>zipWith(-)x(0:x)é de 32 bytes :)
Lynn
Como estásum.zipWith((max 0.).(-))<*>(0:)
Lynn
@ Lynn Seu segundo vai precisar de parênteses extras, já que ele .tem precedência maior do que <*>.
Wheat Wizard
3

Japonês , 8 bytes

-2 bytes de @Shaggy

mîT Õ¸¸è

Explicação

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

Experimente online!

Luis felipe De jesus Munoz
fonte
8 bytes:mîT Õ¸¸è
Shaggy
1
Bom uso do A.y()estofamento, a propósito.
Shaggy
3

MATL , 8 bytes

0whd3Y%s

Experimente online!

Praticamente o algoritmo de @ Arnauld. Salvou um byte (obrigado @LuisMendo) ao transmitir, em uint64vez de selecionar )entradas positivas.

Sanchises
fonte
3

Geléia , 5 bytes

Uma porta da minha resposta 05AB1E , que é semelhante à resposta @tsh JS .

ŻI0»S

Experimente online!

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
Arnauld
fonte
3

Japonês , 7 6 bytes

änT fq

Tente

1 byte economizado graças 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
Shaggy
fonte
1
6 bytes
Oliver
Bom, @ Oliver; não teria pensado nisso.
Shaggy
2

Retina 0.8.2 , 21 bytes

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

1

Experimente online! O link inclui casos de teste. Explicação:

\d+
$*

Converta para unário.

(1+)(?=,\1)

Exclua todas as sobreposições da próxima torre, que não precisam de um novo golpe.

1

Conte os traços restantes.

Neil
fonte
2

Lisp comum, 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))

não 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)))

Teste-o

Quando uma torre é pintada, são necessárias várias pinceladas iguais à sua altura. Essas pinceladas são traduzidas para todas as seguintes, as quais são indicadas aqui subtraindo a altura da torre atual de todas as outras torres (e ela mesma, mas isso não importa). Se uma torre a seguir for mais curta, ela será empurrada para um número negativo, e esse número negativo será subtraído das torres que se seguem (indicando pinceladas que não puderam ser traduzidas de uma torre anterior para as próximas). Na verdade, apenas subtrai o número de todas as alturas da torre, incluindo as anteriores, mas isso não importa, porque não olhamos para as anteriores novamente.

Charlim
fonte
Bem-vindo ao PPCG. Você poderia fornecer um link para um ambiente de teste on-line para facilitar a verificação?
Jonathan Frech
Sim absolutamente. rextester.com/TKBU14782 A resposta será atualizada em breve
Charlim
Bem feito. +1 para uma boa postagem em funcionamento. Divirta-se jogando golfe.
Jonathan Frech
1

05AB1E , 13 10 bytes

Z>Lε@γPO}O

Experimente online ou verifique todos os casos de teste .

Explicação:

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
fonte
1

C # (compilador interativo do Visual C #) com sinalizador /u:System.Math, 47 bytes

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

Experimente online!

Versão antiga, com sinalizador /u:System.Math, 63 bytes

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

Eu sinto que esta solução é mais elegante que a primeira. Ele percorre a matriz com uma tupla de dois valores como valor inicial, captando valores e armazenando o valor antes dele na segunda parte da tupla.

Experimente online!

Modalidade de ignorância
fonte
1

Pitão, 8 bytes

s>#0.++0

Mais um exemplo da maravilhosa resposta de @ tsh . Toma a soma ( s) dos valores positivos ( >#0) dos deltas (. +) Da entrada com 0 prefixado ( +0Q, Q à direita inferido).

Experimente online aqui ou verifique todos os casos de teste de uma vez aqui .

Método de união de cadeias, 10 bytes

Esta foi a solução que escrevi antes de procurar as outras respostas.

lcj.t+d*LN

Suíte de teste.

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
fonte
1

Clojure, 50 bytes

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

Experimente online! (Por que isso não 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.
Tentei criar uma conta
fonte
Bem-vindo ao PPCG! Não sei nada sobre o Clojure, mas uma pesquisa rápida mostra que você precisará avaliar o loop for lento. Experimente Online! (Dica: você pode usar o botão de link para formatar automaticamente sua resposta). Espero que você fique por aqui e se divirta!
Jo King
1

Java (JDK) , 57 bytes

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

Experimente online!

Outro porto de TSH 's resposta Javascript . Portanto, verifique se você os votou positivamente.

Observe que eu usei subtração em vez de adição porque me permitiu escrever (p=x)como operando certo na mesma instrução.

Olivier Grégoire
fonte
0

MATL , 15 14 13 bytes

ts:<~"@Y'x]vs

Entrada é um vetor de coluna, usando ;como separador.

Experimente online! Ou verifique todos os casos de teste .

Explicação

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
fonte
0

Perl 5, 21 bytes

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

TIO

Como

  • -p+ }{+ $\truque
  • //corresponde à sequência vazia, para que, para a próxima linha, a pós- $'correspondência contenha a linha anterior
  • $\+=$_>$'&&$_-$'acumular diferença entre a linha atual e a anterior se a corrente for maior que a anterior (também pode ser escrita $\+=$_-$' if$_>$', mas o perl não analisa $\+=$_-$'if$_>$'o mesmo)
Nahuel Fouilleul
fonte
0

Stax , 8 bytes

Φ┐Γ╟φφ.╨

Execute e depure

Usa a abordagem amplamente usada da solução JavaScript da tsh.

wastl
fonte