Покрытие Skyline мазками кисти

43

Учитывая список неотрицательных целочисленных высот горизонта, ответьте, сколько непрерывных горизонтальных мазков кистью в 1 единицу необходимо, чтобы покрыть его.

[1,3,2,1,2,1,5,3,3,4,2]визуализируется как:

      5    
      5  4 
 3    5334 
 32 2 53342
13212153342

нужно девять мазков:

      1    
      2  3 
 4    5555 
 66 7 88888
99999999999

Примеры

[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

Адам
источник
Для заинтересованных пользователей с высокой репутацией: на основе этого согласно этому .
Адам
2
Итак, все мазки кисти горизонтальны?
TSH
1
@tsh Хорошая мысль. Добавлен.
Адам
Это был не Codegolf, но у меня был этот вопрос для теста кода интервью около года назад.
luizfzs

Ответы:

35

JavaScript (Node.js) , 38 байт

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

Попробуйте онлайн!

Просто жадный алгоритм, который сканирует слева направо, рисует только линии, если это необходимо, и рисует его как можно дольше.

Спасибо Арно, сэкономь 2 3 байта

ТТГ
источник
@ Арнаулд хороший улов. полностью забыл это.
TSH
Как ты это понял?
Адам
@ Adám Ничего волшебного. Когда я впервые прочитал вопрос, меня смутило то, как искать, пока я не понял, что все линии только горизонтальные. И тогда эта формула просто пришла мне в голову , естественно ....
TSH
4
магия кажется подходящим словом для описания этого процесса.
Адам
1
Хотя это и является источником широко распространенного в настоящее время алгоритма, он объясняется здесь .
Адам
28

05AB1E ,  8 7  5 байт

Сохранено 2 байта благодаря @Adnan

0š¥þO

Попробуйте онлайн!

Как?

Это использует алгоритм, который был впервые найден @tsh . Если вам понравился этот ответ, не забудьте также подтвердить его ответ !

Каждый раз, когда небоскреб ниже или выше предыдущего, его можно покрасить «бесплатно», просто растягивая мазки.

Например, рисование небоскребов и на рисунке ниже ничего не стоит.BC

С другой стороны, нам нужно 2 новых мазка, чтобы нарисовать небоскреб , независимо от того, будут ли они использоваться повторно после этого или нет.E

здания

Для первого небоскреба нам всегда нужно столько мазков, сколько в нем этажей.

Превращая это в математику:

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

Если мы добавим к списку, это можно упростить до:0

S=i=1nmax(hihi1,0)

комментарии

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
источник
Я думаю, что 0š¥ʒd}Oэкономит вам байт.
г-н Xcoder
@ Don'tbeax-tripledot Я редактировал свой ответ именно на это, когда увидел твой комментарий;)
Арно
4
Прекрасное объяснение.
Адам
1
Замена ʒd}на þдолжна сэкономить вам два байта.
Аднан
@ Аднан Ах, хорошо. Благодарность!
Арно
7

Python 3 , 37 байт

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

Попробуйте онлайн!

-5 байт при переходе на Python 3, благодаря Sarien


Python 2 , 47 43 42 байта

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

Попробуйте онлайн!

Alt:

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

Попробуйте онлайн!

TFeld
источник
В Python 3 вы можете отказаться от [: -1], сэкономив 5 байт.
Сариен
@Sarien Спасибо: D, я не знал, что карта отличается в Python 2 и 3
TFeld
7

Haskell , 32 байта

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

Попробуйте онлайн!

Улучшение решения Линн, которое отслеживает предыдущий элемент, pа не смотрит на следующий элемент. Это делает базовый случай и рекурсивный вызов короче в обмен на необходимость вызова (0%).

max(h-p)0может быть max h p-pдля той же длины.

XNOR
источник
5

K (ок) , 12 7 байт

-5 байт благодаря ngn!

К (ок) порт решения 05AB1E Arnauld (и решение JavaScript TSH в):

+/0|-':

Попробуйте онлайн!

J 15 байт

Порт AJ решения 05AB1E Арнаулда (и решения JavaScript от tsh):

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

Попробуйте онлайн!

Мое наивное решение:

J , 27 байт

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

Попробуйте онлайн!

Гален Иванов
источник
2
ОК: каждый prior ( ':) использует неявный элемент тождества ( 0for -) перед списком, поэтому в 0,этом нет необходимости. Вы можете опустить { x}состав:+/0|-':
ngn
@ngn Спасибо! Видимо, я забыл это: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
Гален Иванов
5

Haskell , 34 32 байта

2 байта обрезаны Линн

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

Попробуйте онлайн!

Итак, для начала у нас есть zipWith(-). Это берет два списка и производит новый список их попарных различий. Затем мы объединяем это с xи (0:x). (0:)это функция, которая добавляет ноль в начало списка и, комбинируя его с, zipWith(-)мы получаем различия между последовательными элементами этого списка с нулем в начале. Затем мы обращаем все отрицательные в ноль с помощью (max 0<$>). Это создает новый список, где каждый элемент - это число новых штрихов, которые должны быть запущены в каждой башне. Чтобы получить общую сумму, мы просто суммируем их sum.

Мастер пшеницы
источник
2
g x=sum$max 0<$>zipWith(-)x(0:x)составляет 32 байта :)
Линн
Как естьsum.zipWith((max 0.).(-))<*>(0:)
Линн
@Lynn Ваш второй будет нуждаться в дополнительных скобках, так как .приоритет имеет более высокий, чем <*>.
Пшеничный волшебник
3

Japt , 8 байт

-2 байта от @Shaggy

mîT Õ¸¸è

объяснение

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

Попробуйте онлайн!

Луис Фелипе Де Иисус Муньос
источник
8 байтов:mîT Õ¸¸è
лохматый
1
Между A.y()прочим, приятное использование отступов.
Лохматый
3

MATL , 8 байт

0whd3Y%s

Попробуйте онлайн!

В значительной степени алгоритм Арно. Сохраненный один байт (спасибо @LuisMendo) путем приведения uint64вместо того, чтобы выбирать )положительные записи.

Sanchises
источник
3

Japt , 7 6 байт

änT fq

Попытайся

1 байт сохранен благодаря Оливеру.

ä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
мохнатый
источник
1
6 байтов
Оливер
Хороший, @Oliver; не подумал бы об этом.
Лохматый
2

Сетчатка 0.8.2 , 21 байт

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

1

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Объяснение:

\d+
$*

Преобразовать в одинарный.

(1+)(?=,\1)

Удалите все перекрытия со следующей башней, которая не требует нового удара.

1

Подсчитайте оставшиеся удары.

Нил
источник
2

Common Lisp, 88 87 байт

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

без уменьшенная

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

Попробуй это

Когда одна башня окрашена, она берет количество мазков, равное ее высоте. Эти мазки преобразуются во все последующие, что обозначается здесь вычитанием высоты текущей башни из всех других башен (и самой себя, но это не имеет значения). Если следующая башня короче, она будет выталкиваться к отрицательному числу, и это отрицательное число будет впоследствии вычитаться из последующих башен (указывая на мазки кисти, которые не могли быть переведены из предыдущей башни в следующую). На самом деле это просто вычитает число из всех высот башни, включая предыдущие, но это не имеет значения, потому что мы больше не смотрим на предыдущие.

Charlim
источник
Добро пожаловать в PPCG. Не могли бы вы предоставить ссылку на среду онлайн-тестирования для простоты проверки?
Джонатан Фрех
Да, конечно. rextester.com/TKBU14782 Ответ будет обновлен в ближайшее время
Чарлим
Отлично сработано. +1 за хороший, рабочий первый пост. Получайте удовольствие от игры в гольф.
Джонатан Фрех
1

05AB1E , 13 10 байт

Z>Lε@γPO}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)
Кевин Круйссен
источник
1

C # (интерактивный компилятор Visual C #) с флагом /u:System.Math, 47 байтов

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

Попробуйте онлайн!

Старая версия, с флагом /u:System.Math, 63 байта

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

Я чувствую, что это решение более элегантно, чем первое. Он проходит через массив с кортежем из двух значений в качестве начального значения, собирает значения и сохраняет перед ним значение во второй части кортежа.

Попробуйте онлайн!

Воплощение невежества
источник
1

Pyth, 8 байт

s>#0.++0

Еще один порт изумительного ответа @ tsh . Принимает сумму ( s) положительных значений ( >#0) дельт (. +) Входных данных с добавленным 0 ( +0Qконечный Q выводится).

Попробуйте онлайн здесь или проверьте все тестовые примеры сразу здесь .

Метод соединения строк, 10 байтов

Это было решение, которое я написал, прежде чем просматривать другие ответы.

lcj.t+d*LN

Тестирование.

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
источник
1

Clojure, 50 байтов

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

Попробуйте онлайн! (Почему это ничего не печатает?)

#( ; 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.
Попытка создания учетной записи
источник
Добро пожаловать в PPCG! Я ничего не знаю о Clojure, но быстрый поиск показывает, что вам нужно будет оценить ленивый цикл for. Попробуйте онлайн! (Совет: вы можете использовать кнопку ссылки для автоматического форматирования вашего ответа). Надеюсь, вы останетесь и повеселиться!
Джо Кинг
1

Java (JDK) , 57 байт

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

Попробуйте онлайн!

Другой порт TSH «s Javascript ответ . Поэтому убедитесь, что вы проголосовали за них.

Обратите внимание, что я использовал вычитание вместо сложения, потому что это позволило мне написать (p=x)правильный операнд в том же выражении.

Оливье Грегуар
источник
0

MATL , 15 14 13 байт

ts:<~"@Y'x]vs

Ввод - это вектор-столбец, использующий в ;качестве разделителя.

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

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
Луис Мендо
источник
0

Perl 5, 21 байт

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

TIO

Как

  • -p+ }{+ $\трюк
  • // соответствует пустой строке, так что для следующей строки postmatch $' будет содержать предыдущую строку
  • $\+=$_>$'&&$_-$'накапливать разницу между текущей строкой и предыдущей, если current больше, чем предыдущая (также может быть записано $\+=$_-$' if$_>$', но perl не анализирует $\+=$_-$'if$_>$'то же самое)
Науэль Фуйе
источник