Bedecken einer Skyline mit Pinselstrichen

43

Beantworten Sie bei einer nicht negativen Liste der Skyline-Höhen ganzzahlig, wie viele ununterbrochene horizontale Pinselstriche mit einer Höhe von 1 Einheit erforderlich sind, um die Skyline abzudecken.

[1,3,2,1,2,1,5,3,3,4,2], visualisiert als:

      5    
      5  4 
 3    5334 
 32 2 53342
13212153342

braucht neun Pinselstriche:

      1    
      2  3 
 4    5555 
 66 7 88888
99999999999

Beispiele

[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

Adam
quelle
Für interessierte High-rep Benutzer: auf Basierend dies gemäß diesem .
Adám
2
Alle Pinselstriche sind also horizontal?
Dienstag,
1
@tsh Guter Punkt. Hinzugefügt.
Adám
Es war kein Codegolf, aber ich hatte diese Frage für einen Interview-Code-Test vor etwa einem Jahr.
luizfzs

Antworten:

35

JavaScript (Node.js) , 38 Byte

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

Probieren Sie es online!

Einfach ein gieriger Algorithmus, der von links nach rechts scannt, nur bei Bedarf Linien zeichnet und diese so lange wie möglich zeichnet.

Danke Arnauld, spare 2 3 Bytes

tsh
quelle
@ Arnauld schöner Fang. total vergessen.
Dienstag,
Wie haben Sie das realisiert?
Adám
@Adám Nichts Magisches. Als ich das erste Mal die Frage las, war ich verwirrt darüber, wie ich suchen sollte, bis mir klar wurde, dass alle Linien nur horizontal sind. Und dann kam mir diese Formel ganz natürlich in den Sinn ...
Dienstag,
4
Magie scheint ein passendes Wort zu sein, um diesen Prozess zu beschreiben.
Am
1
Während dies der Ursprung des heute weit verbreiteten Algorithmus ist, wird er hier erklärt .
Adám
28

05AB1E ,  8 7  5 Bytes

2 Bytes dank @Adnan gespart

0š¥þO

Probieren Sie es online!

Wie?

Hierbei wird der Algorithmus verwendet, der zuerst von @tsh gefunden wurde . Wenn Ihnen diese Antwort gefällt, stellen Sie sicher, dass Sie auch die Antwort positiv bewerten !

Jedes Mal, wenn ein Wolkenkratzer niedriger als oder so hoch wie der vorherige ist, kann er durch einfaches Ausfahren der Pinselstriche "kostenlos" bemalt werden.

Das Malen der Wolkenkratzer und in der folgenden Abbildung kostet beispielsweise nichts.BC

Auf der anderen Seite brauchen wir 2 neue Pinselstriche, um Wolkenkratzer zu malen , egal ob sie danach wiederverwendet werden oder nicht.E

Gebäude

Für den ersten Wolkenkratzer brauchen wir immer so viele Pinselstriche, wie Böden darin sind.

Das in Mathematik umwandeln:

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

Wenn wir der Liste voranstellen , kann dies vereinfacht werden, um:0

S=i=1nmax(hihi1,0)

Kommentiert

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
quelle
Ich denke, 0š¥ʒd}Ospart dir ein Byte.
Mr. Xcoder
@ Don'tbeax-tripledot Ich bearbeitete meine Antwort genau darauf, als ich Ihren Kommentar sah;)
Arnauld
4
Schöne Erklärung.
Am
1
Durch Ersetzen ʒd}durch þsollten Sie zwei Bytes sparen.
Adnan
@Adnan Ah, schön. Vielen Dank!
Arnauld
7

Haskell , 32 Bytes

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

Probieren Sie es online!

Eine Verbesserung von Lynns Lösung , die das vorherige Element verfolgt, panstatt das nächste Element zu betrachten. Dies verkürzt den Basisfall und den rekursiven Aufruf, wenn ein Aufruf erforderlich ist (0%).

max(h-p)0könnte max h p-pfür die gleiche Länge sein.

xnor
quelle
5

K (OK) , 12 7 Bytes

-5 Bytes dank ngn!

Ein k (oK) -Port der 05AB1E-Lösung von Arnauld (und der JavaScript-Lösung von tsh):

+/0|-':

Probieren Sie es online!

J , 15 Bytes

AJ-Port der 05AB1E-Lösung von Arnauld (und der JavaScript-Lösung von tsh):

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

Probieren Sie es online!

Meine naive Lösung:

J , 27 Bytes

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

Probieren Sie es online!

Galen Ivanov
quelle
2
OK: every prior ( ':) verwendet ein implizites Identitätselement ( 0for -) vor der Liste, 0,ist also nicht erforderlich. Sie können es unterlassen { x}, eine Komposition daraus zu machen:+/0|-':
ngn
@ngn Danke! Anscheinend habe ich das vergessen: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 von Lynn getrimmt

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

Probieren Sie es online!

Also zu Beginn haben wir zipWith(-). Dies nimmt zwei Listen und erzeugt eine neue Liste ihrer paarweisen Unterschiede. Wir kombinieren es dann mit xund (0:x). (0:)ist eine Funktion, die der Vorderseite einer Liste eine Null hinzufügt. Durch die Kombination mit dieser Funktion erhalten zipWith(-)wir die Unterschiede zwischen aufeinanderfolgenden Elementen dieser Liste mit einer Null an der Vorderseite. Dann setzen wir alle negativen auf Null mit (max 0<$>). Dadurch wird eine neue Liste erstellt, in der jedes Element die Anzahl der neuen Striche angibt, die an jedem Turm gestartet werden müssen. Um die Summe zu erhalten, addieren wir diese einfach mit sum.

Weizen-Assistent
quelle
2
g x=sum$max 0<$>zipWith(-)x(0:x)ist 32 Bytes :)
Lynn
Wie es istsum.zipWith((max 0.).(-))<*>(0:)
Lynn
@Lynn Ihre zweite benötigt zusätzliche Klammern, da diese .eine höhere Priorität haben als <*>.
Weizen-Zauberer
3

Japt , 8 Bytes

-2 Bytes von @Shaggy

mîT Õ¸¸è

Erläuterung

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

Probieren Sie es online!

Luis Felipe De Jesus Munoz
quelle
8 Bytes:mîT Õ¸¸è
Shaggy
1
Übrigens netter Gebrauch von A.y()'s Polsterung.
Shaggy
3

MATL , 8 Bytes

0whd3Y%s

Probieren Sie es online!

So ziemlich der Algorithmus von @ Arnauld. 1 Byte gespart (danke @LuisMendo), indem auf positive Einträge gewechselt wurde, uint64anstatt sie auszuwählen ).

Sanchises
quelle
3

Gelee , 5 Bytes

Ein Port meiner 05AB1E-Antwort , der selbst der @tsh JS-Antwort ähnelt .

ŻI0»S

Probieren Sie es online!

Kommentiert

Ż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
quelle
3

Japt , 7 6 Bytes

änT fq

Versuch es

Dank Oliver 1 Byte gespart.

ä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
Zottelig
quelle
1
6 Bytes
Oliver
Netter, @Oliver; daran hätte ich nicht gedacht.
Shaggy
2

Retina 0.8.2 , 21 Bytes

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

1

Probieren Sie es online! Link enthält Testfälle. Erläuterung:

\d+
$*

In Unary konvertieren.

(1+)(?=,\1)

Löschen Sie alle Überlappungen mit dem nächsten Turm, für die kein neuer Strich erforderlich ist.

1

Zählen Sie die verbleibenden Striche.

Neil
quelle
2

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

nicht minimiert

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

Probier es aus

Wenn ein Turm bemalt ist, sind mehrere Pinselstriche erforderlich, die seiner Höhe entsprechen. Diese Pinselstriche werden in alle folgenden übersetzt, was hier durch Subtrahieren der Höhe des aktuellen Turms von allen anderen Türmen (und von sich selbst, aber das spielt keine Rolle) angezeigt wird. Wenn ein nachfolgender Turm kürzer ist, wird er auf eine negative Zahl verschoben, und diese negative Zahl wird anschließend von den nachfolgenden Türmen abgezogen (was auf Pinselstriche hinweist, die nicht von einem vorherigen Turm auf den nächsten übertragen werden konnten). Es subtrahiert tatsächlich nur die Anzahl von allen Turmhöhen, einschließlich der vorherigen, aber das spielt keine Rolle, da wir die vorherigen nicht noch einmal betrachten.

Charlim
quelle
Willkommen bei PPCG. Können Sie möglicherweise einen Link zu einer Online-Testumgebung bereitstellen, um die Überprüfung zu vereinfachen?
Jonathan Frech
Ja absolut. rextester.com/TKBU14782 Die Antwort wird in Kürze aktualisiert
Charlim
Gut gemacht. +1 für einen schönen, funktionierenden ersten Beitrag. Viel Spaß beim Golfen.
Jonathan Frech
1

05AB1E , 13 10 Bytes

Z>Lε@γPO}O

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

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

C # (Visual C # Interactive Compiler) mit Flag /u:System.Math, 47 Byte

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

Probieren Sie es online!

Alte Version, mit Flag /u:System.Math, 63 Bytes

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

Ich finde, diese Lösung ist eleganter als die erste. Es durchläuft das Array mit einem zweiwertigen Tupel als Startwert, nimmt Werte auf und speichert den Wert davor im zweiten Teil des Tupels.

Probieren Sie es online!

Verkörperung der Ignoranz
quelle
1

Pyth, 8 Bytes

s>#0.++0

Noch eine Portierung von @ tshs wunderbarer Antwort . Nimmt die Summe ( s) der positiven Werte ( >#0) der Deltas (. +) Der Eingabe mit vorangestelltem Wert ( 0 +0Q, gefolgt von Q).

Versuchen Sie es online hier oder überprüfen alle Testfälle auf einmal hier .

Zeichenkettenverbindungsmethode, 10 Bytes

Dies war die Lösung, die ich geschrieben habe, bevor ich die anderen Antworten durchgesehen habe.

lcj.t+d*LN

Testsuite.

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

Clojure, 50 Bytes

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

Probieren Sie es online! (Warum druckt das nichts?)

#( ; 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.
Versucht, ein Konto zu erstellen
quelle
Willkommen bei PPCG! Ich weiß nichts über Clojure, aber eine schnelle Suche zeigt, dass Sie die Lazy for-Schleife bewerten müssen. Probieren Sie es online! (Tipp: Sie können die Link-Schaltfläche verwenden, um Ihre Antwort automatisch zu formatieren.) Hoffe du bleibst dabei und hast Spaß!
Jo King
1

Java (JDK) , 57 Byte

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

Probieren Sie es online!

Ein weiterer Hafen von tsh ist Javascript Antwort . Stellen Sie also sicher, dass Sie sie positiv bewertet haben.

Beachten Sie, dass ich anstelle der Addition die Subtraktion verwendet habe, weil ich damit (p=x)in der gleichen Anweisung als rechter Operand schreiben konnte .

Olivier Grégoire
quelle
0

MATL , 15 14 13 Bytes

ts:<~"@Y'x]vs

Die Eingabe ist ein Spaltenvektor, der ;als Trennzeichen verwendet wird.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

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

Perl 5, 21 Bytes

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

TIO

Wie

  • -p+ }{+ $\trick
  • //Entspricht einer leeren Zeichenfolge, sodass die Nachanpassung für die nächste Zeile $'die vorherige Zeile enthält
  • $\+=$_>$'&&$_-$'um die Differenz zwischen der aktuellen und der vorherigen Zeile zu akkumulieren, wenn die aktuelle größer als die vorherige ist (könnte auch geschrieben werden $\+=$_-$' if$_>$', aber Perl parst nicht $\+=$_-$'if$_>$'dasselbe)
Nahuel Fouilleul
quelle