Nadchodzi rok 2019 i prawdopodobnie wszyscy zauważyli osobliwość tej liczby: w rzeczywistości składa się ona z dwóch pod-liczb (20 i 19) reprezentujących sekwencję kolejnych malejących liczb.

Wyzwanie

Biorąc pod uwagę liczbę x, zwróć długość maksymalnej sekwencji kolejnych, malejących liczb, które można utworzyć, przyjmując pod-liczby x.

Uwagi:

• cząstkowe wartości nie może zawierać zera (na przykład 1009nie może być podzielony 10, 09)
• kolejne i malejące oznaczają, że liczba w sekwencji musi być równa poprzedniej liczbie -1, lub $n_{i+1} = n_{i}-1$ (np. 52nie można podzielić na, 5,2ponieważ 5i 2nie są kolejne 2 ≠ 5 - 1)
• sekwencja musi być uzyskane za pomocą pełnego numeru, np 7321nie można odrzucić 7i uzyskać sekwencję 3, 2,1
• tylko sekwencja może być otrzymana z numerem, na przykład 3211098nie może być podzielona na dwie sekwencje 3, 2, 1i 10, 9,8

Wejście

• Liczba całkowita ( >= 0): może być liczbą, łańcuchem lub listą cyfr

Wynik

• Pojedyncza liczba całkowita z maksymalną liczbą malejących podliczb (zauważ, że dolna granica tej liczby to 1, tzn. Liczba składa się sama w malejącej sekwencji o długości jeden)

Przykłady:

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

Główne zasady:

• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
  Nie pozwól, aby języki gry w golfa zniechęcały Cię do publikowania odpowiedzi w językach niekodujących golfa. Spróbuj znaleźć możliwie najkrótszą odpowiedź na „dowolny” język programowania.
• Do odpowiedzi mają zastosowanie standardowe reguły z domyślnymi regułami We / Wy , więc możesz używać STDIN / STDOUT, funkcji / metody z odpowiednimi parametrami i typem zwracanych, pełnych programów. Twoja decyzja.
• Domyślne luki są zabronione.
• Jeśli to możliwe, dodaj link z testem kodu (tj. TIO ).
• Zalecane jest również dodanie wyjaśnienia do odpowiedzi.

Galaretka ,  15  9 bajtów

Bugfix dzięki Dennisowi

ŻṚẆDfŒṖẈṀ

Wypróbuj online! (321zajmujenawetpół minuty, ponieważ kod to co najmniej$O(N^2)$ )

W jaki sposób?

ŻṚẆ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 bajtów

Port odpowiedzi na Python ArBo jest znacznie krótszy. Jednak nie udaje się to w niektórych przypadkach testowych z powodu zbyt dużej rekurencji.

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

Wypróbuj online!

JavaScript (ES6), 66 bajtów

Pobiera dane wejściowe jako ciąg.

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++])

Wypróbuj online!

Skomentował

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 bajtów

-1 bajt dzięki nwellnhof

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

Wypróbuj online!

Rozwiązanie oparte na regeksie. Zamiast tego próbuję znaleźć lepszy sposób dopasowania z listy malejącej, ale Perl 6 nie radzi sobie dobrze z partycjami

Wyjaśnienie:

{                                        }  # 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 bajtów

-1 dzięki @ Jonathan Frech

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

Wypróbuj online!

Początkowy nie golfowy kod:

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 bajty

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)

Wypróbuj online!

_{-1 bajt dzięki Arnauldowi}

Pobiera dane wejściowe jako ciąg. Program dość szybko uruchamia limit głębokości rekurencji Pythona, ale może zakończyć większość przypadków testowych.

Jak to działa

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 bajtów

ÝRŒʒJQ}€gà

Bardzo powolny, więc poniższe TIO działa tylko dla przypadków testowych poniżej 750 ..

Wypróbuj online .

Wyjaśnienie:

Ý           # 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 bajtów

lef!.EhM.+vMT./z

Spróbuj go online tutaj , lub sprawdzić wszystkie przypadki testowe od razu tutaj .

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

Galaretka , 11 bajtów

ŒṖḌ’Dɗ\ƑƇẈṀ

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

Wypróbuj online!

Jak to działa

ŒṖḌ’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.

Węgiel drzewny , 26 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

Ｆ⊕Ｌθ

Pętla iod 0 do długości wejścia.

Ｆ⊕Ｌθ

Pętla kod 0 do długości wejścia.

⊞υ⭆κ⁻Ｉ…θ⊕ιλ

Oblicz pierwsze kliczby w kolejności malejącej, zaczynając od liczby podanej przez pierwsze icyfry danych wejściowych, połącz je i zsumuj każdy wynikowy ciąg na predefiniowanej pustej liście.

Ｉ﹪⌕υθ⊕Ｌθ

Znajdź pozycję pierwszej pasującej kopii wejścia i zmniejsz ją modulo o 1 więcej niż długość wejścia.

Przykład: Dla wejścia 2019generowane są następujące ciągi:

 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 znajduje się następnie przy indeksie 12, który jest zredukowany modulo 5, aby dać 2 pożądaną odpowiedź.

Haskell, 87 bajtów

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

Dane wejściowe to lista cyfr.

Wypróbuj online!

Funkcja #buduje listę wszystkich możliwych podziałów, patrząc na oba

• wstawianie bieżącego numeru ado wszystkich podziałów zwracanych przez wywołanie rekurencyjne z resztą input ( x<-b#c), ale tylko wtedy, gdy następny numer nie jest zero ( b>0) (lub jest ostatnim numerem na input ( c==[])) i ajest o jeden większy od pierwszego numer odpowiedniego poprzedniego podziału x( a==x!!0+1).

i

• dołączenie następnej cyfry bz listy wprowadzania do bieżącego numeru ai kontynuowanie reszty wprowadzania ( (10*a+b)#c)

Przypadek podstawowy występuje, gdy lista wejściowa jest pusta (tzn. Nie pasuje do wzorca (b:c)). Rekurencja rozpoczyna się od bieżącej liczby , która ajest 0( (0#)), która nigdy nie uderza w pierwszą gałąź (poprzedzając awszystkie poprzednie podziały), ponieważ nigdy nie będzie większa niż jakakolwiek liczba podziałów.

Weź długość każdego podziału i znajdź maksimum ( maximum.map length).

Wariant z 87 bajtami:

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

co w zasadzie działa w ten sam sposób, ale zamiast utrzymywać cały podział na liście, zachowuje tylko parę (r,x)długości podziału ri pierwszą liczbę w podziale x.

Python 3 , 302 282 271 bajtów

-10 bajtów dzięki wskazówce @ElPedro.

Pobiera dane wejściowe jako ciąg. Zasadniczo zajmuje coraz większe wycinki liczby od lewej i sprawdza, czy dla tego wycinka liczby można utworzyć sekwencję przy użyciu wszystkich liczb.

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

Wypróbuj online!

Japt , 27 bajtów

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

Wypróbuj online! lub Sprawdź większość przypadków testowych

To nie jest dobry wynik, ale używa unikalnej metody i może być miejsce na grę w golfa o wiele więcej. Działa również wystarczająco dobrze, aby wszystkie przypadki testowe inne niż 201200199198unikały przekroczenia limitu czasu.

Wyjaśnienie:

ò                              #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 bajtów

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

Dane wejściowe to ciąg znaków.

Wypróbuj online!

Zupełnie inna niż moja inna odpowiedź . Prosta brutalna siła, która wypróbowuje wszystkie listy kolejnych liczb malejących, dopóki nie znajdzie takiej, która jest równa liście wejściowej.

Jeśli mamy ograniczyć liczbę wejściowy 64-bitowych liczb całkowitych, możemy zaoszczędzić 6 bajtów poprzez zapętlenie ypoprzez [1..19], ponieważ największy 64-bitowa liczba całkowita ma 19 cyfr i nie ma potrzeby, aby list testowych z kilku elementów.

Haskell, 59 bajtów

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

Wypróbuj online!

Python 2 , 95 bajtów

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

Kolejne wolne, brutalne rozwiązanie.

Wypróbuj online!

Dyalog APL, 138 bajtów

Trochę kęs, ale działa również szybko dla dużych liczb. Jeśli wypróbujesz to online , poprzedź dfn przez ⎕←i podaj dane po prawej jako listę cyfr.

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

Wyjaśnienie

Po pierwsze, wewnętrzny dfn po prawej stronie, który rekurencyjnie tworzy listę możliwych sposobów podziału (z ⊂) listą cyfr. Na przykład 1 0 1 0 ⊂ 2 0 1 9zwraca zagnieżdżony wektor (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.

Używamy, 1,aby dodać kolumnę 1s na początku i kończyć macierz prawidłowych partycji dla ⍵.

Teraz pociąg funkcji po lewej stronie w parens. Ze względu ⍨na lewy argument do pociągu jest wiersz macierzy partycji, a prawy argument to dane wejściowe użytkownika. Pociąg jest stosem widelców ze szczytem jako skrajnie lewym palcem.

((≢⊂)×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.

Jeśli partycja tworzy sekwencję malejących liczb, pociąg zwraca długość sekwencji. W przeciwnym razie zero.

⍤1⊢stosuje ciąg funkcji między danymi wejściowymi użytkownika a każdym wierszem macierzy partycji, zwracając wartość dla każdego wiersza macierzy. ⊢jest konieczne, aby rozróżnić operand od ⍤argumentu dla pochodnej funkcji ⍤.

⌈/ znajduje maksimum.

Mogłem znaleźć krótszy algorytm, ale chciałem wypróbować ten sposób, który jest najbardziej bezpośredni i deklaratywny.

TSQL, 169 bajtów

Uwaga: można to wykonać tylko wtedy, gdy dane wejściowe można przekonwertować na liczbę całkowitą.

Rekurencyjny sql używany do zapętlania.

Gra w golfa:

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=@

Nie golfowany:

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=@

Wypróbuj to

R , 101 bajtów

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}

Wypróbuj online!

Minęły ponad 2 tygodnie bez żadnej odpowiedzi R, więc postanowiłem opublikować własną :)

Kod jest dość szybki, ponieważ wykorzystuje „ograniczone” podejście brutalnej siły

Kod i objaśnienie:

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
}