À partir d’une liste de hauteur d’horizon entier non négatif, indiquez le nombre de coups de pinceau horizontaux ininterrompus d’une unité de hauteur nécessaires pour la recouvrir.
[1,3,2,1,2,1,5,3,3,4,2]
, visualisé comme:
5
5 4
3 5334
32 2 53342
13212153342
nécessite neuf coups de pinceau:
1
2 3
4 5555
66 7 88888
99999999999
Exemples
[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
Réponses:
JavaScript (Node.js) , 38 octets
Essayez-le en ligne!
Tout simplement un algorithme glouton qui balaie de gauche à droite, ne trace des lignes que si nécessaire, et le plus longtemps possible.
Merci Arnauld, économisez
23 octetsla source
05AB1E ,
8 75 octets2 octets sauvés grâce à @Adnan
Essayez-le en ligne!
Comment?
Ceci utilise l'algorithme qui a été trouvé pour la première fois par @tsh . Si vous aimez cette réponse, assurez-vous de la faire revenir également!
Chaque fois qu'un gratte-ciel est plus bas ou plus haut que le précédent, il peut être peint «gratuitement» en prolongeant simplement les coups de pinceau.
Par exemple, peindre les gratte-ciel et dans la figure ci-dessous ne coûte rien.B C
D'autre part, nous avons besoin de 2 nouveaux coups de pinceau pour peindre le gratte-ciel , peu importe qu'ils soient réutilisés ou non.E
Pour le premier gratte-ciel, nous avons toujours besoin d'autant de coups de pinceau que de sols.
En tournant ça en maths:
Si nous ajoutons à la liste, ceci peut être simplifié comme suit:0
Commenté
la source
0š¥ʒd}O
vous sauve un octet.ʒd}
parþ
devrait vous faire économiser deux octets.Python 3 , 37 octets
Essayez-le en ligne!
-5 octets en passant à Python 3, grâce à Sarien
Python 2 ,
474342 octetsEssayez-le en ligne!
Alt:
Essayez-le en ligne!
la source
Haskell , 32 octets
Essayez-le en ligne!
Une amélioration de la solution de Lynn qui suit l'élément précédent
p
au lieu de regarder l'élément suivant. Cela raccourcit le scénario de base et l'appel récursif en échange de la nécessité d'invoquer(0%)
.max(h-p)0
pourrait êtremax h p-p
pour la même longueur.la source
Haskell , 35 octets
Essayez-le en ligne!
La ligne 2 pourrait être
f[a]=a
si je n'avais pas aussi à traiter le cas[]
.la source
K (oK) ,
12 à7 octets-5 octets grâce à ngn!
Un port k (oK) de la solution 05AB1E d’Arnauld (et de la solution JavaScript de tsh):
Essayez-le en ligne!
J , 15 octets
Port AJ de la solution 05AB1E d'Arnauld (et de la solution JavaScript de tsh):
Essayez-le en ligne!
Ma solution naïve:
J , 27 octets
Essayez-le en ligne!
la source
':
) utilise un élément d'identité implicite (0
pour-
) avant la liste, il0,
est donc inutile. vous pouvez omettre{
x}
d'en faire une composition:+/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 octets2 octets coupés par Lynn
Essayez-le en ligne!
Donc pour commencer nous avons
zipWith(-)
. Cela prend deux listes et produit une nouvelle liste de leurs différences par paires. Nous le combinons ensuite avecx
et(0:x)
.(0:)
est une fonction qui ajoute zéro au début d'une liste et en la combinant aveczipWith(-)
nous obtenons les différences entre les éléments consécutifs de cette liste avec un zéro au début. Ensuite, nous mettons tous les négatifs à zéro avec(max 0<$>)
. Cela crée une nouvelle liste où chaque élément est le nombre de nouveaux traits qui doivent être démarrés à chaque tour. Pour obtenir le total, nous les additionnons simplement avecsum
.la source
g x=sum$max 0<$>zipWith(-)x(0:x)
est 32 octets :)sum.zipWith((max 0.).(-))<*>(0:)
.
a une priorité plus élevée que<*>
.Japt , 8 octets
-2 octets de @Shaggy
Explication
Essayez-le en ligne!
la source
mîT Õ¸¸è
A.y()
rembourrage.MATL , 8 octets
Essayez-le en ligne!
Joli algorithme de @ Arnauld. Sauvegardé d'un octet (merci @LuisMendo) en utilisant
uint64
plutôt que de sélectionner)
des entrées positives.la source
Gelée , 5 octets
Un port de ma réponse 05AB1E , qui est semblable à @tsh JS answer .
Essayez-le en ligne!
Commenté
la source
Japt ,
7 à6 octetsL'essayer
1 octet enregistré grâce à Oliver.
la source
R , 30 octets
Essayez-le en ligne!
Portage de solution @Arnauld qui dérive à son tour de grande solution @tsh
la source
Retina 0.8.2 , 21 octets
Essayez-le en ligne! Le lien inclut des cas de test. Explication:
Convertir en unaire.
Supprimez tous les chevauchements avec la tour suivante, qui n'ont pas besoin d'un nouveau trait.
Comptez les coups restants.
la source
Common Lisp,
8887 octetsnon minifié
Essaye-le
Quand une tour est peinte, il faut un nombre de coups de pinceau égal à sa hauteur. Ces coups de pinceau se traduisent par tous les suivants, ce qui est indiqué ici en soustrayant la hauteur de la tour actuelle de toutes les autres tours (et elle-même, mais cela n'a pas d'importance). Si une tour suivante est plus courte, elle sera poussée à un nombre négatif et ce nombre négatif sera ensuite soustrait des tours suivantes (indiquant les coups de pinceau qui n'ont pas pu être traduits d'une tour précédente). En fait, il ne fait que soustraire le nombre de toutes les hauteurs de tour, y compris les précédentes, mais cela n'a pas d'importance, car nous ne regardons plus les précédentes.
la source
05AB1E ,
13 à10 octetsEssayez-le en ligne ou vérifiez tous les cas de test .
Explication:
la source
C # (compilateur interactif Visual C #) avec indicateur
/u:System.Math
, 47 octetsEssayez-le en ligne!
Ancienne version, avec drapeau
/u:System.Math
, 63 octetsJ'ai l'impression que cette solution est plus élégante que la première. Il parcourt le tableau avec un tuple à deux valeurs comme valeur de départ, en sélectionnant des valeurs, et stocke la valeur qui le précède dans la seconde partie du tuple.
Essayez-le en ligne!
la source
Pyth, 8 octets
Encore une autre réponse merveilleuse de @ tsh . Prend la somme (
s
) des valeurs positives (>#0
) des deltas (. +) De l'entrée avec 0 en préfixe (+0Q
Q inféré).Essayez-le en ligne ici ou vérifiez tous les cas de test en même temps ici .
Méthode de jonction de chaînes, 10 octets
C’est la solution que j’ai écrite avant de parcourir les autres réponses.
Suite de tests.
la source
Clojure, 50 octets
Essayez-le en ligne! (Pourquoi cela n'imprime-t-il rien?)
la source
Java (JDK) , 57 octets
Essayez-le en ligne!
Un autre port de la réponse Javascript de tsh . Donc, assurez-vous de les avoir votés.
Notez que j'ai utilisé la soustraction au lieu de l'addition, car cela me permettait d'écrire en
(p=x)
tant qu'opérande droit dans la même instruction.la source
MATL ,
151413 octetsL'entrée est un vecteur de colonne, utilisant
;
comme séparateur.Essayez-le en ligne! Ou vérifiez tous les cas de test .
Explication
la source
Perl 5, 21 octets
TIO
Comment
-p
+}{
+$\
astuce//
correspond à une chaîne vide de sorte que pour la ligne suivante, postmatch$'
contienne la ligne précédente$\+=$_>$'&&$_-$'
accumuler la différence entre la ligne courante et précédente si le courant est supérieur au précédent, (pourrait également être écrit$\+=$_-$' if$_>$'
, mais Perl n'analyse pas de$\+=$_-$'if$_>$'
la même façon)la source
Stax , 8 octets
Exécuter et déboguer
Utilise l'approche largement utilisée de la solution JavaScript de tsh.
la source
Wolfram Language (Mathematica) , 34 octets
Un port de @Arnauld de solution .
Essayez-le en ligne!
la source