17
\$\begingroup\$

2019 has come and probably everyone has noticed the peculiarity of this number: it's in fact composed by two sub-numbers (20 and 19) representing a sequence of consecutive descending numbers.

Challenge

Given a number x, return the length of the maximum sequence of consecutive, descending numbers that can be formed by taking sub-numbers of x.

Notes :

  • sub-numbers cannot contain leading zeros (e.g. 1009 cannot be split into 10,09)
  • consecutive and descending means that a number in the sequence must be equal to the previous number -1, or \$n_{i+1} = n_{i}-1\$ (e.g. 52 cannot be split into 5,2 because 5 and 2 are not consecutive, 2 ≠ 5 - 1)
  • the sequence must be obtained by using the full number, e.g. in 7321 you can't discard 7 and get the sequence 3,2,1
  • only one sequence can be obtained from the number, e.g. 3211098 cannot be split into two sequences 3,2,1 and 10,9,8

Input

  • An integer number (>= 0) : can be a number, or a string, or list of digits

Output

  • A single integer given the maximum number of decreasing sub-numbers (note that the lower-bound of this number is 1, i.e. a number is composed by itself in a descending sequence of length one)

Examples :

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

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code (i.e. TIO).
  • Also, adding an explanation for your answer is highly recommended.
\$\endgroup\$
  • 1
    \$\begingroup\$ Migrated from sandbox : codegolf.meta.stackexchange.com/questions/2140/… \$\endgroup\$ – digEmAll Jan 4 at 10:49
  • 1
    \$\begingroup\$ Is the test case 210 -> 2,1,0 wrong (same with 0 -> 0)? The tasks says "sub-numbers cannot contain leading zeros", is zero a special case? \$\endgroup\$ – BMO Jan 4 at 17:30
  • 2
    \$\begingroup\$ @BMO: well, here the topic is kinda phylosofical... :D to me, 0 is a number with no (useless) leading zero, so yes zero is a special case \$\endgroup\$ – digEmAll Jan 4 at 17:39
  • 2
    \$\begingroup\$ would you call these... condescending numbers? xD sorry that was like not even funny \$\endgroup\$ – HyperNeutrino Jan 6 at 3:03
  • \$\begingroup\$ Sorry, deleted my comment in which I asked about 212019. Seems I didn't read all the rules. \$\endgroup\$ – cyclaminist Jan 12 at 21:49

17 Answers 17

6
\$\begingroup\$

JavaScript (ES6), 56 bytes

A port of ArBo's Python answer is significantly shorter. However, it fails on some test cases because of too much recursion.

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

Try it online!


JavaScript (ES6), 66 bytes

Takes input as a string.

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

Try it online!

Commented

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
\$\endgroup\$
  • \$\begingroup\$ 54 bytes by implementing the changes to my code \$\endgroup\$ – ArBo Jan 15 at 15:50
5
\$\begingroup\$

Jelly,  15  9 bytes

Bugfix thanks to Dennis

ŻṚẆDfŒṖẈṀ

Try it online! (even 321 takes half a minute since the code is at least \$O(N^2)\$)

How?

ŻṚẆ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
\$\endgroup\$
5
\$\begingroup\$

Perl 6, 43 41 40 bytes

-1 byte thanks to nwellnhof

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

Try it online!

Regex based solution. I'm trying to come up with a better way to match from a descending list instead, but Perl 6 doesn't do partitions well

Explanation:

{                                        }  # 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
\$\endgroup\$
4
\$\begingroup\$

Python 3, 232 228 187 181 180 150 149 bytes

-1 thanks to @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])])

Try it online!

Initial ungolfed code:

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
\$\endgroup\$
  • 1
    \$\begingroup\$ s+1 for can be s+1for, (t(n[:j])-t(n[j:j+i])==1)*t(n[0]) can possibly be t(n[:j])-t(n[j:j+i])==1>=t(n[0]). \$\endgroup\$ – Jonathan Frech Jan 6 at 14:15
  • \$\begingroup\$ It seems that second suggestion doesn't work though it wouldn't bring anything because then you need space to separate expression from if. \$\endgroup\$ – Nishioka Jan 6 at 14:34
  • \$\begingroup\$ True ... alternative 149. \$\endgroup\$ – Jonathan Frech Jan 6 at 15:03
4
\$\begingroup\$

Python 2, 78 74 73 bytes

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)

Try it online!

-1 byte thanks to Arnauld

Takes input as a string. The program rather quickly runs into Python's recursion depth limit, but it can finish most of the test cases.

How it works

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice answer! a+c+1 can be shortened to a-~c. \$\endgroup\$ – Arnauld Jan 14 at 21:01
3
\$\begingroup\$

05AB1E, 10 bytes

ÝRŒʒJQ}€gà

Extremely slow, so the TIO below only works for test cases below 750..

Try it online.

Explanation:

Ý           # 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
\$\endgroup\$
  • 2
    \$\begingroup\$ Code golf - where adding 1 byte to your program to go from n! to n lg n just isn't worth it. \$\endgroup\$ – corsiKa Jan 5 at 20:49
3
\$\begingroup\$

Pyth, 16 bytes

lef!.EhM.+vMT./z

Try it online here, or verify all the test cases at once here.

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
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 26 bytes

F⊕LθF⊕Lθ⊞υ⭆κ⁻I…θιλI﹪⌕υθ⊕Lθ

Try it online! Link is to verbose version of code. Explanation:

F⊕Lθ

Loop i from 0 to the length of the input.

F⊕Lθ

Loop k from 0 to the length of the input.

⊞υ⭆κ⁻I…θ⊕ιλ

Calculate the first k numbers in the descending sequence starting from the number given by the first i digits of the input, concatenate them, and accumulate each resulting string in the predefined empty list.

I﹪⌕υθ⊕Lθ

Find the position of the first matching copy of the input and reduce it modulo 1 more than the length of the input.

Example: For an input of 2019 the following strings are generated:

 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 is then found at index 12, which is reduced modulo 5 to give 2, the desired answer.

\$\endgroup\$
3
\$\begingroup\$

Haskell, 87 bytes

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

Input is a list of digits.

Try it online!

Function # builds a list of all possible splits by looking at both

  • prepending the current number a to all splits returned by a recursive call with the rest of the input (x<-b#c), but only if the next number not zero (b>0) (or it's the last number in the input (c==[])) and a is one greater than the first number of the respective previous split x (a==x!!0+1).

and

  • appending the next digit b from the input list to the current number a and going on with the rest of the input ((10*a+b)#c)

Base case is when the input list is empty (i.e. does not pattern match (b:c)). The recursion starts with the current number a being 0 ((0#)), which never hits the first branch (prepending a to all previous splits), because it will never be greater than any number of the splits.

Take the length of each split and find the maximum (maximum.map length).

A variant with also 87 bytes:

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

which basically works the same way, but instead of keeping the whole split in a list, it only keeps a pair (r,x) of the length of the split r an the first number in the split x.

\$\endgroup\$
3
\$\begingroup\$

Python 3, 302 282 271 bytes

-10 bytes thanks to the tip by @ElPedro.

Takes input as a string. Basically, it takes increasing larger slices of the number from the left, and sees if for that slice of the number a sequence can be formed using all the numbers.

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Since you are using range 3 times you can define R=range outside of both functions and then use R(whatever) instead of range(whatever) to save 4 bytes. \$\endgroup\$ – ElPedro Jan 5 at 17:48
3
\$\begingroup\$

Japt, 27 bytes

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

Try it online! or Check most test cases

This doesn't score well, but it uses a unique method and there might be room to golf it a lot more. It also performs well enough that all test cases other than 201200199198 avoid timing out.

Explanation:

ò                              #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
\$\endgroup\$
  • \$\begingroup\$ I think this works for 27. \$\endgroup\$ – Shaggy Jan 5 at 10:30
  • \$\begingroup\$ 25 bytes \$\endgroup\$ – Shaggy Jan 5 at 10:43
  • \$\begingroup\$ @Shaggy both of those fail on input 21201 because they don't enforce that the sequence end aligns correctly (from my original version the "ends with a comma" line). This or this alternative works. \$\endgroup\$ – Kamil Drakari Jan 5 at 15:38
  • \$\begingroup\$ Ah, OK. In that case: 26 bytes \$\endgroup\$ – Shaggy Jan 5 at 15:46
  • \$\begingroup\$ @Shaggy That and the 28 byte solutions I had fail on 210 because there isn't a delimiter after 0. Here's a fixed 28 byte that works. \$\endgroup\$ – Kamil Drakari Jan 6 at 1:35
2
\$\begingroup\$

Jelly, 11 bytes

ŒṖḌ’Dɗ\ƑƇẈṀ

Byte for byte, no match for the other Jelly solution, but this one should be roughly \$O\left(n^{0.3}\right)\$.

Try it online!

How it works

ŒṖḌ’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.
\$\endgroup\$
2
\$\begingroup\$

Haskell, 65 bytes

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

Input is a string.

Try it online!

Completely different to my other answer. A simple brute force that tries all lists of consecutive descending numbers until it finds one that equals the input list.

If we limit the input number to 64-bit integers, we can save 6 bytes by looping y through [1..19], because the largest 64-bit integer has 19 digits and there's no need to test lists with more elements.

Haskell, 59 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 95 bytes

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

Another slow, brute-force solution.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Dyalog APL, 138 bytes

Bit of a mouthful, but it works fast for big numbers too. If you try it online, prefix the dfn by ⎕← and provide input on the right as a list of digits.

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

Explanation

First, the inner dfn on the right which recursively constructs a list of possible ways to partition (with ) the list of digits. For example 1 0 1 0 ⊂ 2 0 1 9 returns the nested vector (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.

We use 1, to add a column of 1s at the start and end up with a matrix of valid partitions for ⍵.

Now the function train on the left in parens. Due to the left argument to the train is the row of the partitions matrix and the right argument is the user input. The train is a pile of forks with an atop as the far left tine.

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

If the partition creates a sequence of descending numbers, the train returns the length of the sequence. Otherwise zero.

⍤1⊢ applies the function train between the user input and each row of the partitions matrix, returning a value for each row of the matrix. is necessary to disambiguate between operand to and argument to the derived function of .

⌈/ finds the maximum.

Could find a shorter algorithm but I wanted to try this way which is the most direct and declarative I could think of.

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! This is an impressive first post! \$\endgroup\$ – Riker Jan 12 at 21:47
1
\$\begingroup\$

TSQL, 169 bytes

Note: this can only be executed when the input can be converted to an integer.

Recursive sql used for looping.

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

Try it out

\$\endgroup\$
0
\$\begingroup\$

R, 101 bytes

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}

Try it online!

More than 2 weeks have passed without any R answer, so I decided to post my own :)

The code is pretty fast since it uses a "limited" brute force approach

Unrolled code and explanation :

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
}
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.