Наименьшее количество смежных монотонных подпоследовательностей

23

Описание задачи

Монотонная подпоследовательность представляет собой последовательность чисел , [a1, a2, ..., an]таких , что

a1 <= a2 <= ... <= anили a1 >= a2 >= ... >= an. [1, 3, 3, 7, 9, 13, 13, 100]является монотонной (неубывающей) подпоследовательностью, а также [9, 4, 4, 3, 0, -10, -12](эта не возрастает), но [1, 3, 6, 9, 8]не является. Если задан список целых чисел (в любом приемлемом формате), выведите наименьшее число N, чтобы последовательность этих целых чисел можно было разбить на Nмонотонные последовательности.

Примеры

[1, 3, 7, 5, 4, 2] -> [[1, 3, 7], [5, 4, 2]] -> 2
[1, 2, 3, 4, 5, 6] -> [1, 2, 3, 4, 5, 6]     -> 1
[3, 1, 5, 5, 6]    -> [[3, 1], [5, 5, 6]]    -> 2
[4, 6, 8, 9, 1, 6] -> [[4, 6, 8, 9], [1, 6]] -> 2
[3, 3, 3, 3]       -> [[3, 3, 3, 3]]         -> 1
[7]                -> [[7]]                  -> 1
[]                 -> []                     -> anything (you don't actually have to handle an empty list case)
[1, 3, 2, -1, 6, 9, 10, 2, 1, -12] -> [[1, 3], [2, -1], [6, 9, 10], [2, 1, -12]] -> 4
shooqie
источник
Чтобы уточнить, подпоследовательности должны быть смежными, верно?
Згарб
@ Zgarb Да, они делают.
shooqie
3
Я бы порекомендовал добавить тестовый пример, в котором последовательности не всегда идут в обратном направлении: [4,4,8,8,1,4,5] -> 2
Натан Меррилл,
@NathanMerrill: Хороший вопрос, добавил один.
shooqie
Когда вы пишете это для пустой строки, получается 0 / undefined, что это звучит так, как будто это должно быть либо 0, либо представление undefinedна нашем языке, но из вашего комментария к ответу Джонатана Аллана на желе это выглядит как undefinedсредство anything... Какой из них это? ? Во втором случае я бы предложил писать anythingвместоundefined
Dada

Ответы:

6

Брахилог , 12 байт

~c:{<=|>=}al

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

Это возвращается false.для пустого списка [].

объяснение

(?)~c                 Take a list of sublists which when concatenated result in the Input
     :{<=|>=}a        Each sublist must be either increasing or decreasing
              l(.)    Output is the length of that list

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

Fatalize
источник
Что такое аргумент "Z" в ссылке TIO? (Кажется, это часть программы, как аргумент командной строки).
Джонатан Аллан
@JonathanAllan Этот аргумент является выходным. В идеале, если бы мы могли настроить интерфейс TIO, были бы вход и выход, а не аргументы. Аргумент: Zпотому что Zэто имя переменной; поэтому мы говорим «вызовите эту программу с выводом в качестве переменной». Вы можете изменить Zв любой другой прописной буквы ; это просто имя переменной. Причина, по которой этот аргумент существует, состоит в том, чтобы позволить возможность на самом деле установить вывод для чего-то, а не для переменной.
Роковая
(Например, если вы установите выход 4в этом примере, он скажет вам, если это правильно или нет )
Fatalize
1
@JonathanAllan Любой язык, подобный Прологу, выглядит следующим образом: предикаты могут только успешно завершиться или потерпеть неудачу и не возвращают никакого значения. Таким образом, чтобы получить результат, нужно иметь переменный аргумент для предиката, который будет объединен с результатом.
Роковая
1
@JonathanAllan Это в конечном итоге потерпит неудачу, 3потому что не найдет ни одного списка подсписков, где все являются монотонными и имеют длину 3. Это займет много времени, потому что он попробует все возможные списки подсписков, даже те, которые на самом деле длиннее, чем 3 элемента, потому что длина проверяется после нахождения списка. Ибо 5он говорит, trueпотому что действительно есть хотя бы один список длины 5с монотонными подсписками, который работает. Таким образом, эта программа возвращает наименьшую длину, когда выходные данные являются переменными и существует ли какой-либо список этой длины, который работает, если выходные данные являются целыми числами.
Роковая
4

Perl, 65 байт

62 байта кода + 3 байта для -nфлага.

monot_seq.pl:

#!perl -n
s/\S+ /($_<=>$&)*($&<=>$')-$g>=0?$g=1:$.++;$g--;$_=$&/ge,$_=$.

Введите ввод без окончательного перевода строки с числами, разделенными пробелами:

$ echo -n "1 3 2 -1 6 9 10 2 1 -12" | perl -M5.010 monot_seq.pl
4

-5 байтов благодаря @ Габриэлю Бенами.

папа
источник
Сохранить 5 байтов, превратившись ($&<=>$1)*($1<=>$2)||$1==$2в($&<=>$1)*($1<=>$2)>=0
Габриэль Бенами
@GabrielBenamy Действительно, спасибо.
Дада
2

Mathematica, 111 байт

d=#[[2]]-#[[1]]&;r=Rest;f@{n_}:=1;f@k__:=If[d@k==0,f@r@k,g[k Sign@d@k]];g@{n_}:=1;g@k__:=If[d@k>0,g@r@k,1+f@r@k]

Именованная функция, fпринимающая непустой список чисел (целые или даже вещественные числа). Работает спереди назад, многократно отбрасывая первый элемент и отслеживая, сколько подпоследовательностей необходимо. Более подробный:

d = #[[2]] - #[[1]] &;         function: difference of the first two elements
r = Rest;                      function: a list with its first element dropped
f@{n_} := 1;                   f of a length-1 list equals 1
f@k__ := If[d@k == 0, f@r@k,   if the first two elements are equal, drop one
                                 element and call f again ...
            g[k Sign@d@k]];  ... otherwise call the helper function g on the
                                 list, multiplying by -1 if necessary to ensure
                                 that the list starts with an increase
g@{n_} := 1;                   g of a length-1 list equals 1
g@k__ := If[d@k > 0, g@r@k,    if the list starts with an increase, drop one
                                 element and call g again ...
            1 + f@r@k];        ... otherwise drop one element, call f on the
                                 resulting list, and add 1
Грег Мартин
источник
d=#2-#&@@#&;Кроме того, определение fили gкак унарный оператор ±, вероятно, сэкономит несколько байтов.
Мартин Эндер
2

Желе , 19 байт

IṠḟ0E
ŒṖÇ€€0e$Ðḟḅ1Ṃ

TryItOnline! или запустить все тесты (пустой список приводит к1)

Как?

IṠḟ0E - Link 1, test for monotonicity: a sublist
I     - incremental differences
 Ṡ    - sign {fall:-1; same:0; rise:1}
  ḟ0  - filter out the zeros
    E - all equal?

ŒṖÇ€€0e$Ðḟḅ1Ṃ - Main link
ŒṖ            - all partitions of the input list
  Ç€€         - call last link (1) as a monad for €ach for €ach
        Ðḟ    - filter out results:
       $      -    last two links as a monad
     0e       -        contains zero?
          ḅ1  - convert from unary (vectorises)
            Ṃ - minimum

(Я не уверен, что это самый подходящий метод, чтобы минимизировать количество байтов, хотя)

Джонатан Аллан
источник
@shooqie - Можем ли мы вернуть какое-либо значение для пустого списка с учетом «неопределенного» комментария? Это возвращает 1(что я на самом деле думаю, имеет больше смысла, чем 0).
Джонатан Аллан
1
Я имею в виду, что это undefinedзначит - результат не имеет значения.
shooqie
2

Perl 98 97 96 79 байт

($a,$b)=($a<=>$b)*($b<=>$c)<0?($c,shift,$d++):($b,$c)while$c=shift;say$d+1 if$a

Ввод предоставляется в виде списка чисел, разделенных пробелами, предоставляемых во время выполнения, например

perl -M5.010 monotonic.pl 1 3 2 -1 6 9 10 2 1 -12
4

(4 - это выход)

Удобочитаемый:

($a,$b)=($a<=>$b)*($b<=>$c)<0
    ?($c,shift,$d++)
    :($b,$c)
  while$c=shift;
say$d+1
  if$a

«Оператор космического корабля» <=>возвращает -1, если LHS <RHS, 0, если LHS = RHS, и +1, если LHS> RHS. При сравнении трех последовательных элементов , $a,$b,$cчтобы определить , если они монотонные, необходимо только определить , что это не тот случай , что именно один из $a<=>$b, $b<=>$cявляется 1 , а другим -1 - что происходит только тогда , когда их продукт -1. Если либо $a==$bили $b==$c, то последовательность является монотонной, и произведение равно 0. Если $a < $b < $c, тогда оба результата приводят к -1, и -1 * -1 = 1. Если $a > $b > $c, то оба они приводят к 1, а 1 * 1 = 1. В любом случае последовательность является монотонной, и мы хотим продолжить.

Если произведение меньше 0, мы знаем, что последовательность не является монотонной, и мы отбрасываем значения, которые $a,$bмы в данный момент храним, и увеличиваем счетчик подпоследовательностей. В противном случае мы продвигаемся на один номер вперед.

Ничего не возвращает, если вход пустой, иначе возвращает наименьшее количество смежных монотонных подпоследовательностей

Габриэль Бенами
источник
Вам не нужно пробел между 1и if(или, может быть, вы делаете на старых Perl, но на последних вы не делаете). Также вы можете (возможно) заменить shiftна pop. Тем не менее, есть некоторые тестовые случаи, в которых ваш код не работает: 6 3 6 3(вы печатаете 3 вместо 2), 4 3 2 1(вы печатаете 2 вместо 1). Использование popвместо shiftрешения тех, но создать новые ( 1 2 3 4печатает 3 вместо 1) ...
Дада
1

C # 6, 297 209 байт

using System.Linq;int G(int[] a)=>a.Any()?a.SkipWhile((x,i)=>i<1||x>=a[i-1]).Count()<a.SkipWhile((x,i)=>i<1||x<=a[i-1]).Count()?G(a.Select(x=>-x).ToArray()):G(a.SkipWhile((x,i)=>i<1||x<=a[i-1]).ToArray())+1:0;

Разгромленный с объяснениями

int G(int[] a)=>
    a.Any()
        ?a.SkipWhile((x,i)=>i<1||x>=a[i-1]).Count()<a.SkipWhile((x,i)=>i<1||x<=a[i-1]).Count()   // If a begins by decreasing (including whole a decreasing)...
            ?G(a.Select(x=>-x).ToArray())   // ... Then flip sign to make a begins by increasing
            :G(a.SkipWhile((x,i)=>i<1||x<=a[i-1]).ToArray())+1   // ... Else skip the increasing part, recursively find the remaining part number, then add 1
        :0;   // Return 0 if a is empty
Ссылка Ng
источник
1

JavaScript (ES6), 69 байт

f=(d,c,b,...a)=>1/b?(d>c)*(b>c)+(d<c)*(b<c)?1+f(b,...a):f(d,b,...a):1

Принимает ввод как несколько параметров. Работает путем рекурсивного сравнения первых трех элементов, чтобы увидеть, являются ли они монотонными, если это так, удаляет средний элемент, так как он бесполезен, если нет, удаляет первые два элемента и запускает новую последовательность.

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

Clojure, 97 байт

#((reduce(fn[[C i]s](let[S(conj C s)](if(or(apply <= S)(apply >= S))[S i][[s](inc i)])))[[]1]%)1)

reduceотслеживает текущую подпоследовательность и вычисляет, сколько раз <=и >=условия не выполняются. Последний 1берет 2-й элемент из результата (являющийся счетчиком i).

NikoNyrh
источник