Codegolf - Наименьшее Количество Смежных Монотонных Подпоследовательностей

А монотонная подпоследовательность — это последовательность чисел \$a_1, a_2, ..., a_n\$ такая, что

$$a_1 \le a_2 \le ... \le a_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
 

is a monotonic (non-decreasing) subsequence, as well as N \text{или} \\ N is not. Given a list of integers (in any reasonable format), output the smallest number [1, 3, 6, 9, 8] a_1 \ge a_2 \ge ... \ge a_n$$ [9, 4, 4, 3, 0, -10, -12] monotonic sequences.

(этот показатель не возрастает), но

[1, 3, 3, 7, 9, 13, 13, 100]

такие, что последовательность этих целых чисел можно разбить на

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ŒṖỤ€IṠƑƊƇẈṂ - Main link. Takes an array A on the left
ŒṖ          - Yield all partitions of A

ƊƇ   - Keep those partitions for which the following is true:

€        -   Over each sublist in the partition:

Ụ         -     Grade up; Sort its indices by its values

I       -   Increments

Ƒ     -   Is this invariant under:

Ṡ      -     Convert to sign

This (ṠƑ) is a trick that returns 1 if the list contains only

-1, 1 and 0s. As we're working with the indices, not the values,

we will never have duplicate elements, and so no 0. The increments

will either be all 1 or -1 iff the ordered indices are in directly

ascending or descending order, i.e. the values are sorted in

either ascending or descending order

Ẉ  - Get the lengths of each kept partition

Ṃ - Get the minimum
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

Это возвращает 1 for the empty list ŒṖỤ€IṠƑƊƇẈṂ .

Объяснение

i

Это вернет самый маленький, потому что 1 will generate choice points from the smallest number of sublists to the biggest.

Перл, 65 байт

62 байта кода + 3 байта для >= flag.

monot_seq.pl:

<=

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

reduce

-5 байт благодаря @Gabriel Benamy.

Математика, 111 байт

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

Именованная функция f=(d,c,b,...a)=>1/b?(d>c)*(b>c)+(d<c)*(b<c)?1+f(b,...a):f(d,b,...a):1 taking a nonempty list of numbers (integers or even reals). Works from front to back, discarding the first element repeatedly and keeping track of how many subsequences are needed. More verbose:

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 ||answer||

Желе, 19 байты

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;

Попробуйте онлайн! или запустить все тесты (пустой список приводит к $a,$b )

Как?

$a > $b > $c

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

Perl, 98 97 96 79 байт

$a < $b < $c

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

$b==$c

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

Читабельно:

$a==$b

«Оператор космического корабля» $b<=>$c returns -1 if LHS < RHS, 0 if LHS = RHS, and +1 if LHS > RHS. When comparing three sequential elements $a<=>$b чтобы определить, являются ли они монотонными, необходимо лишь убедиться, что дело не в том, что именно один из $a,$b,$c , <=> равно 1, а другое - -1, что происходит только тогда, когда их произведение равно -1. Если либо ($a,$b)=($a<=>$b)*($b<=>$c)<0 ?($c,shift,$d++) :($b,$c) while$c=shift; say$d+1 if$a or perl -M5.010 monotonic.pl 1 3 2 -1 6 9 10 2 1 -12 4 , то последовательность монотонна и произведение равно 0. Если ($a,$b)=($a<=>$b)*($b<=>$c)<0?($c,shift,$d++):($b,$c)while$c=shift;say$d+1 if$a , then both result in -1, and -1 * -1 = 1. If 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 , то они оба дают 1 и 1 * 1 = 1. В любом случае последовательность монотонна, и мы хотим продолжить.

Если произведение меньше 0, мы знаем, что последовательность не монотонна, и отбрасываем значения 1 we're currently holding, and increment our subsequence counter. Otherwise, we move forward one number.

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

С#6, 297 209 байт

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

Негольф с пояснениями

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 ||answer||

JavaScript (ES6), 69 байт

f

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

Кложур, 97 байт

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]

$ echo -n "1 3 2 -1 6 9 10 2 1 -12" | perl -M5.010 monot_seq.pl 4 keeps track of the current subsequence and calculates how many times #!perl -n s/\S+ /($_<=>$&)*($&<=>$')-$g>=0?$g=1:$.++;$g--;$_=$&/ge,$_=$. и -n conditions fail. Last ~c берет второй элемент из результата (являясь счетчиком (?)~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 ).

Желе, 11 байт

[]

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

Пустой список дает результат false.

Как это работает

~c:{<=|>=}al