Наступил 2019 год, и, вероятно, все заметили особенность этого числа: на самом деле оно состоит из двух под номерами (20 и 19), представляющих последовательность последовательных убывающих чисел.

Вызов

Для заданного числа xверните длину максимальной последовательности последовательных убывающих чисел, которые можно сформировать, взяв под номера x.

Примечания :

• под номера не могут содержать начальные нули (например, 1009не могут быть разбиты на 10, 09)
• последовательный и нисходящий означает, что число в последовательности должно быть равно предыдущему числу -1, или (например, не может быть разбит на, потому что и не являются последовательными, )$n_{i+1} = n_{i}-1$525,2522 ≠ 5 - 1
• последовательность должна быть получена с использованием полного числа, например, 7321вы не можете отказаться 7и получить последовательность 3, 2,1
• только одна последовательность может быть получена из числа, например , 3211098не может быть разделен на две последовательности 3, 2, 1и 10, 9,8

вход

• Целое число ( >= 0): может быть числом или строкой, или списком цифр

Выход

• Одно целое число с учетом максимального числа убывающих подузлов (обратите внимание, что нижняя граница этого числа равна 1, т.е. число составляется само по себе в порядке убывания длины один)

Примеры :

2019         --> 20,19           --> output : 2
201200199198 --> 201,200,199,198 --> output : 4
3246         --> 3246            --> output : 1
87654        --> 8,7,6,5,4       --> output : 5
123456       --> 123456          --> output : 1
1009998      --> 100,99,98       --> output : 3
100908       --> 100908          --> output : 1
1110987      --> 11,10,9,8,7     --> output : 5
210          --> 2,1,0           --> output : 3
1            --> 1               --> output : 1
0            --> 0               --> output : 1
312          --> 312             --> output : 1
191          --> 191             --> output : 1

Основные правила:

• Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.
  Не позволяйте языкам кода-гольфа отговаривать вас от публикации ответов на языках, не относящихся к кодексу. Попробуйте придумать как можно более короткий ответ для «любого» языка программирования.
• Стандартные правила применяются к вашему ответу с правилами ввода / вывода по умолчанию , поэтому вам разрешено использовать STDIN / STDOUT, функции / метод с правильными параметрами и типом возврата, полные программы. Ваш звонок.
• По умолчанию лазейки запрещены.
• Если возможно, добавьте ссылку с тестом для вашего кода (например, TIO ).
• Кроме того, добавление объяснения для вашего ответа настоятельно рекомендуется.

Желе ,  15  9 байт

Исправлено благодаря Денису

ŻṚẆDfŒṖẈṀ

Попробуйте онлайн! (даже321занимает полминуты, так как код по крайней мере)$O(N^2)$

Как?

ŻṚẆDfŒṖẈṀ - Link: integer, n
Ż         - [0..n]
 Ṛ        - reverse
  Ẇ       - all contiguous slices (of implicit range(n)) = [[n],...,[2],[1],[0],[n,n-1],...,[2,1],[1,0],...,[n,n-1,n-2,...,2,1,0]]
   D      - to decimal (vectorises)
     ŒṖ   - partitions of (implicit decimal digits of) n
    f     - filter discard from left if in right
       Ẉ  - length of each
        Ṁ - maximum

JavaScript (ES6), 56 байт

Порт ответа Python от ArBo значительно короче. Однако в некоторых тестовых случаях это не удается из-за слишком большой рекурсии.

f=(n,a=0,c=0,s)=>a<0?f(n,a-~c):n==s?c:f(n,--a,c+1,[s]+a)

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

JavaScript (ES6), 66 байт

Принимает ввод в виде строки.

f=(s,n=x='',o=p=n,i=0)=>s[i++]?o==s?i:f(s,--n,o+n,i):f(s,p+s[x++])

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

комментарии

f = (               // f = recursive function taking:
  s,                //   s = input number, as a string
  n =               //   n = counter
  x = '',           //   x = position of the next digit to be added to p
  o = p = n,        //   o = generated output; p = prefix
  i = 0             //   i = number of consecutive descending numbers
) =>                //
  s[i++] ?          // increment i; if s[i] was defined:
    o == s ?        //   if o is matching s:
      i             //     stop recursion and return i
    :               //   else:
      f(            //     do a recursive call with:
        s,          //       s unchanged
        --n,        //       n - 1
        o + n,      //       (n - 1) appended to o
        i           //       i unchanged (but it was incremented above)
      )             //     end of recursive call
  :                 // else:
    f(              //   this is a dead end; try again with one more digit in the prefix:
      s,            //     s unchanged
      p + s[x++]    //     increment x and append the next digit to p
    )               //   end of recursive call

Perl 6 , 43 41 40 байт

-1 байт благодаря nwellnhof

{/(<-[0]>.*?|0)+<?{[==] 1..*Z+$0}>/;+$0}

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

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

Объяснение:

{                                        }  # Anonymous code block
 /                                /;        # Match in the input
   <-[0]>.*?      # Non-greedy number not starting with 0
            |0    # Or 0
  (           )+  # Repeatedly for the rest of the number
                <?{             }>  # Where
                        1..*Z+$0       # Each matched number plus the ascending numbers
                                       # For example 1,2,3 Z+ 9,8,7 is 10,10,10
                   [==]                # Are all equal
                                    +$0  # Return the length of the list

Python 3 , 232 228 187 181 180 150 149 байт

-1 благодаря @ Джонатану Фреху

e=enumerate
t=int
h=lambda n,s=1:max([1]+[i-len(n[j:])and h(n[j:],s+1)or s+1for j,_ in e(n)for i,_ in e(n[:j],1)if(t(n[:j])-t(n[j:j+i])==1)*t(n[0])])

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

Исходный негольфированный код:

def count_consecutives(left, right, so_far=1):
    for i,_ in enumerate(left, start=1):
        left_part_of_right, right_part_of_right = right[:i], right[i:]
        if (int(left) - int(left_part_of_right)) == 1:
            if i == len(right):
                return so_far + 1
            return count_consecutives(left_part_of_right, right_part_of_right, so_far + 1)
    return so_far

def how_many_consecutives(n):
    for i, _ in enumerate(n):
        left, right = n[:i], n[i:]
        for j, _ in enumerate(left, start=1):            
            left_part_of_right = right[:j]
            if int(left) - int(left_part_of_right) == 1 and int(n[i]) > 0:     
                return count_consecutives(left, right)
    return 1

Python 2 , 78 74 73 байта

l=lambda n,a=0,c=0,s="":c*(n==s)or a and l(n,a-1,c+1,s+`a-1`)or l(n,a-~c)

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

_{-1 байт благодаря Арно}

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

Как это устроено

l=lambda n,                              # The input number, in the form of a string
         a=0,                            # The program will attempt to reconstruct n by
                                         #  building a string by pasting decreasing
                                         #  numbers, stored in a, after each other.
         c=0,                            # A counter of the amount of numbers
         s="":                           # The current constructed string
              c*(n==s)                   # Return the counter if s matches n
              or                         # Else
              a and l(n,a-1,c+1,s+`a-1`) # If a is not yet zero, paste a-1 after s
              or                         # Else
              l(n,a-~c)                  # Start again, from one higher than last time

05AB1E , 10 байтов

ÝRŒʒJQ}€gà

Чрезвычайно медленно, поэтому TIO ниже работает только для тестовых случаев ниже 750 ..

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

Объяснение:

Ý           # Create a list in the range [0, (implicit) input]
            #  i.e. 109 → [0,1,2,...,107,108,109]
 R          # Reverse it
            #  i.e. [0,1,2,...,107,108,109] → [109,108,107,...,2,1,0]
  Π        # Get all possible sublists of this list
            #  i.e. [109,108,107,...,2,1,0]
            #   → [[109],[109,108],[109,108,107],...,[2,1,0],[1],[1,0],[0]]
   ʒ  }     # Filter it by:
    J       #  Where the sublist joined together
            #   i.e. [10,9] → "109"
            #   i.e. [109,108,107] → "109108107"
     Q      #  Are equal to the (implicit) input
            #   i.e. 109 and "109" → 1 (truthy)
            #   i.e. 109 and "109108107" → 0 (falsey)
       €g   # After filtering, take the length of each remaining inner list
            #  i.e. [[109],[[10,9]] → [1,2]
         à  # And only leave the maximum length (which is output implicitly)
            #  i.e. [1,2] → 2

Pyth, 16 байт

lef!.EhM.+vMT./z

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

lef!.EhM.+vMT./z   Implicit: z=input as string
             ./z   Get all divisions of z into disjoint substrings
  f                Filter the above, as T, keeping those where the following is truthy:
          vMT        Parse each substring as an int
        .+           Get difference between each pair
      hM             Increment each
   !.E               Are all elements 0? { NOT(ANY(...)) }
 e                 Take the last element of the filtered divisions
                     Divisions are generated with fewest substrings first, so last remaining division is also the longest
l                  Length of the above, implicit print

Желе , 11 байт

ŒṖḌ’Dɗ\ƑƇẈṀ

$O\left(n^{0.3}\right)$

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

Как это устроено

ŒṖḌ’Dɗ\ƑƇẈṀ  Main link. Argument: n (integer)

ŒṖ           Yield all partitions of n's digit list in base 10.
        Ƈ    Comb; keep only partitions for which the link to the left returns 1.
       Ƒ       Fixed; yield 1 if calling the link to the left returns its argument.
      \          Cumulatively reduce the partition by the link to the left.
     ɗ             Combine the three links to the left into a dyadic chain.
  Ḍ                  Undecimal; convert a digit list into an integer.
   ’                 Decrement the result.
    D                Decimal; convert the integer back to a digit list.

Древесный уголь , 26 байт

Ｆ⊕ＬθＦ⊕Ｌθ⊞υ⭆κ⁻Ｉ…θιλＩ﹪⌕υθ⊕Ｌθ

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

Ｆ⊕Ｌθ

Цикл iот 0 до длины входа.

Ｆ⊕Ｌθ

Цикл kот 0 до длины входа.

⊞υ⭆κ⁻Ｉ…θ⊕ιλ

Вычислить первые kчисла в нисходящей последовательности, начиная с числа, заданного первыми iцифрами ввода, объединить их и накапливать каждую результирующую строку в предварительно определенном пустом списке.

Ｉ﹪⌕υθ⊕Ｌθ

Найдите положение первой совпадающей копии ввода и уменьшите ее по модулю 1 больше, чем длина ввода.

Пример: для ввода 2019генерируются следующие строки:

 0
 1  0
 2  0-1
 3  0-1-2
 4  0-1-2-3
 5  
 6  2
 7  21
 8  210
 9  210-1
10  
11  20
12  2019
13  201918
14  20191817
15  
16  201
17  201200
18  201200199
19  201200199198
20  
21  2019
22  20192018
23  201920182017
24  2019201820172016

2019 затем находится по индексу 12, который уменьшается по модулю 5, чтобы дать 2, желаемый ответ.

Haskell, 87 байт

maximum.map length.(0#)
a#(b:c)=[a:x|c==[]||b>0,x<-b#c,a==x!!0+1]++(10*a+b)#c
a#b=[[a]]

Ввод представляет собой список цифр.

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

Функция #создает список всех возможных разбиений, глядя на оба

• добавление текущего номера aко всем расщеплениям, возвращаемым рекурсивным вызовом с остальной частью input ( x<-b#c), но только если следующий номер не равен нулю ( b>0) (или это последний номер в input ( c==[])) и aон на единицу больше первого номер соответствующего предыдущего разбиения x( a==x!!0+1).

и

• добавление следующей цифры bиз списка ввода к текущему номеру aи продолжение с остальной частью ввода ( (10*a+b)#c)

Базовый случай, когда входной список пуст (т.е. не соответствует шаблону (b:c)). Рекурсия начинается с текущего числа, aявляющегося 0( (0#)), которое никогда не попадает в первую ветвь ( aпредшествует всем предыдущим расщеплениям), потому что оно никогда не будет больше, чем любое число расщеплений.

Возьмите длину каждого разделения и найдите максимум ( maximum.map length).

Вариант также с 87 байтами:

fst.maximum.(0#)
a#(b:c)=[(r+1,a)|c==[]||b>0,(r,x)<-b#c,a==x+1]++(10*a+b)#c
a#b=[(1,a)]

который в основном работает аналогичным образом, но вместо сохранения всего разбиения в списке он сохраняет только пару (r,x)длин разбиения rи первое число в разбиении x.

Python 3 , 302 282 271 байт

-10 байт благодаря подсказке @ElPedro.

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

R=range
I=int
L=len
def g(n,m,t=1):
 for i in R(1,L(m)+1):
  if I(m)==I(n[:i])+1:
   if i==L(n):return-~t
   return g(n[i:],n[:i],t+1)
 return 1
def f(n):
 for i in R(L(n)):
  x=n[:i]
  for j in R(1,L(x)+1):
   if (I(x)==I(n[i:i+j])+1)*I(n[i]):return g(n[i:],x)
 return 1

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

Japt , 27 байт

ò pÊÔpÊqÊfl²i1Uì q"l?"¹ÌèÊÉ

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

Это не очень хорошо, но он использует уникальный метод, и, возможно, есть место для игры в гольф намного больше. Он также работает достаточно хорошо, чтобы все тестовые случаи, кроме как 201200199198избежать тайм-аута.

Объяснение:

ò                              #Get the range [0...input]
  pÊ                           #Add an "l" to the end
    Ô                          #Reverse it
     pÊ                        #Add an "l" to the end
       qÊ                      #Add an "l" between each number and turn to a string
         f            ¹        #Find the substrings that match this regex:
          l²                   # The string "ll"
            i1                 # With this inserted between the "l"s:
              Uì               #  All the digits of the input
                 q"l?"         #  With optional spaces between each one
                       Ì       #Get the last match
                        èÊ     #Count the number of "l"s
                          É    #Subtract 1

Haskell, 65 байт

f i=[y|x<-[0..],y<-[1..length i],i==(show=<<[x+y-1,x+y-2..x])]!!0

Ввод - это строка.

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

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

Если ограничить ввод число до 64-битных целых чисел, мы можем сохранить 6 байт, обернув yчерез [1..19], потому что самое большое 64-разрядное целое число имеет 19 цифр , и нет никакой необходимости тестирования списков с большим количеством элементов.

Haskell, 59 байт

f i=[y|x<-[0..],y<-[1..19],i==(show=<<[x+y-1,x+y-2..x])]!!0

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

Python 2 , 95 байт

lambda n:max(j-i for j in range(n+1)for i in range(-1,j)if''.join(map(str,range(j,i,-1)))==`n`)

Другое медленное, грубое решение.

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

Dyalog APL, 138 байтов

Немного глоток, но он работает быстро и для больших чисел. Если вы попробуете это онлайн , добавьте префикс dfn by ⎕←и введите справа текст в виде списка цифр.

{⌈/⍵((≢⊂)×1∧.=2-/10⊥¨⊂)⍨⍤1⊢1,{⍬≡1↓⍵:↑⍬1⋄0=⊃⍵:0,∇1↓⍵⋄↑,0 1∘.,⊂⍤1∇1↓⍵}1↓⍵}

объяснение

Во-первых, внутренний dfn справа, который рекурсивно создает список возможных способов разбить (с ⊂) список цифр. Например, 1 0 1 0 ⊂ 2 0 1 9возвращает вложенный вектор (2 0)(1 9).

{
   ⍬≡1↓⍵: ↑⍬1       ⍝ Edge case: If ⍵ is singleton list, return the column matrix (0 1)
   0=⊃⍵: 0,∇1↓⍵     ⍝ If head of ⍵ is 0, return 0 catenated to this dfn called on tail ⍵
   ↑,0 1∘.,⊂⍤1∇1↓⍵  ⍝ Finds 1 cat recursive call on tail ⍵ and 0 cat recursive call on ⍵. 
}                    ⍝ Makes a matrix with a row for each possibility.

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

Теперь функция тренируется слева в паранах. Из- ⍨за левого аргумента в последовательность входит строка матрицы разделов, а правый аргумент - ввод пользователя. Поезд представляет собой кучу вилок с верхним левым зубцом.

((≢⊂)×1∧.=2-/10⊥¨⊂)⍨     ⍝ ⍨ swaps left and right arguments of the train.
                  ⊂       ⍝ Partition ⍵ according to ⍺. 
             10⊥¨         ⍝ Decode each partition (turns strings of digits into numbers)
          2-/             ⍝ Difference between adjacent cells
      1∧.=                ⍝ All equal 1?
   ⊂                      ⍝ Partition ⍵ according to ⍺ again
  ≢                       ⍝ Number of cells (ie number of partitions)
     ×                    ⍝ Multiply.

Если раздел создает последовательность убывающих чисел, поезд возвращает длину последовательности. В противном случае ноль.

⍤1⊢применяет последовательность функций между пользовательским вводом и каждой строкой матрицы разделов, возвращая значение для каждой строки матрицы. ⊢необходимо различать между операндом ⍤и аргументом производной функции от ⍤.

⌈/ находит максимум.

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

TSQL, 169 байт

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

Рекурсивный sql используется для зацикливания.

Golfed:

DECLARE @ varchar(max) = '1211109876';

WITH C as(SELECT left(@,row_number()over(order by 1/0))+0t,@+null z,0i
FROM spt_values UNION ALL
SELECT t-1,concat(z,t),i+1FROM C WHERE i<9)SELECT
max(i)FROM C WHERE z=@

Ungolfed:

DECLARE @ varchar(max) = '1211109876';

WITH C as
(
  SELECT
    left(@,row_number()over(order by 1/0))+0t,
    @+null z,
    0i
  FROM
    spt_values
  UNION ALL
  SELECT
    t-1,
    concat(z,t),
    i+1
  FROM C
  WHERE i<9
)
SELECT max(i)
FROM C
WHERE z=@

Попробуйте это

R 101 байт

function(a,N=nchar(a)){for(x in 1:N)F=max(F,which(Reduce(paste0,seq(substr(a,1,x),,-1,N),a=T)==a));F}

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

Больше 2 недель прошло без ответа R, поэтому я решил опубликовать свой собственный :)

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

Развернутый код и объяснение:

function(a){                  # get string a as input (e.g. "2019")

  N = nchar(a)                # set N = length of a (e.g. 4)
  Y = 0                       # initialize Y = 0 (in the actual code we abuse F)

  for(x in 1:N){              # for x in 1 ... N    

    S = substr(a,1,x)         # get the first x characters of a (e.g. "20" for x=2)

    Q = seq(S,,-1,N)          # create a decreasing sequence (step = -1) 
                              # of length N starting from S converted into integer
                              # (e.g. Q = c(20,19,18,17) for x=2)

    R = Reduce(paste0,Q,a=T)  # concatenate all the increasing sub-sequences of Q
                              # (e.g. R = c("20","2019","201918","20191817") for x=2)

    I = which(R == a)         # Get the index where R == a, if none return empty vector
                              # (e.g. I = 2 for x=2)

    Y = max(Y,I)              # store the maximum index found into Y
  }
  return(Y)                   # return Y
}