22
\$\begingroup\$

Given a string containing a sequence of ascending consecutive positive integers, but with no separators (such as 7891011), output a list of the separated integers. For that example, the output should be [7, 8, 9, 10, 11].

To disambiguate the possible outputs, we add the restriction that the output must always have at least two elements. This means that the output for 7891011 is definitely [7, 8, 9, 10, 11], and not the singleton list [7891011].

Test cases

1234          -> [1, 2, 3, 4]
7891011       -> [7, 8, 9, 10, 11]
6667          -> [66, 67]
293031323334  -> [29, 30, 31, 32, 33, 34]
9991000       -> [999, 1000]
910911        -> [910, 911]

Rules

Input must be taken as a single unseparated string, integer, or list of digits, in decimal only.

Output must be a proper list/array type, or a string with non-digit separators.

You may assume the input is always valid. This means you do not have to handle inputs like:

  • the empty string
  • 5 (the output would need to have length \$ < 2 \$)
  • 43 (cannot make an ascending sequence)
  • 79 (cannot make a consecutive sequence)
  • 66 (ditto)
  • 01 (zero is not a positive integer)

This is , so the shortest code in bytes wins.

\$\endgroup\$
7
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – pxeger
    Jun 28, 2022 at 11:28
  • \$\begingroup\$ For the third test case [6, 667] would be a valid answer too right? \$\endgroup\$
    – mousetail
    Jun 28, 2022 at 14:01
  • 4
    \$\begingroup\$ @mousetail No, the numbers must be consecutive. \$\endgroup\$
    – Fatalize
    Jun 28, 2022 at 14:02
  • 1
    \$\begingroup\$ The reason I asked is, the shortest input that would require the program to be able to detect more than one point where there is an increment in the number of digits is 9101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100, so programs that take an integer as input could employ a shortcut in their design such that they could detect only up to one such increment. Would such a shortcut be accepted as valid? \$\endgroup\$
    – Deadcode
    Jun 28, 2022 at 16:41
  • 5
    \$\begingroup\$ Is it possible for the input to be ambiguous? I suspect not, but a proof eludes me. \$\endgroup\$
    – Nitrodon
    Jun 28, 2022 at 20:28

22 Answers 22

15
\$\begingroup\$

Brachylog, 8 6 bytes

Ṁ∧⟦₂?c

Try it online!

Thanks to @UnrelatedString for -2 bytes.

Takes an integer as the output variable, and unifies the answer with the input variable (so the opposite of what is usually done).

Atrociously slow, as concatenation on integers computes constraints on the digits with powers of 10, instead of being "string" concatenation.

Explanation

Ṁ         The answer has 2 or more elements
 ∧        And
   ⟦₂?    The answer is a range between 2 integers
     ?c   The given input is the concatenation of this range
\$\endgroup\$
3
14
\$\begingroup\$

Regex (.NET) + x flag, 418 209 204 199 132 115 99 bytes

-209 bytes (418 → 209) thanks to Neil

(\5$|(.*(?=(0.*1|1.*2|2.*3|3.*4|4.*5|5.*6|6.*7|7.*8|8.*9)(?<=(.)))|(?=9+(?<4>1))).9*(?=(\2\4 0*)))*

Returns its result as the list of captures on the Balancing Group 1 stack.

Try it online!

# Main loop - Iterates once for each matched number in the squashed sequence.
# There is no need to anchor, because the input is guaranteed to be valid.
(                       # \1 = push matched number onto the Group 1 stack
    \5$                 # Stop immediately if the previous iteration identified
                        # this as being next, and there is nothing following it.
|
    # Using greedy quantifiers, the following, up to and including "9*",
    # matches the number with as many digits as possible that is followed by
    # the next consecutive number.
    (                   # \2 = the prefix portion of the number that won't
                        #      change when incremented
        .*
        (?=
            # Depending on this next digit, capture its incremented form in \4.
            # Only digits that do not carry when incremented are handled here.
            (
                0.*1 |
                1.*2 |
                2.*3 |
                3.*4 |
                4.*5 |
                5.*6 |
                6.*7 |
                7.*8 |
                8.*9
            )
            (?<=(.))    # \4
        )
    |
        # Treat a prefix of all 9s as a special case, because when incremented
        # it will be one digit longer, e.g. 999 -> 1000. In this case, \2 will
        # be empty.
        (?=
            9+
            (?<4>1)     # \4 - Technically this should capture "10", but since
                        #      our input is guaranteed to be valid, we can
                        #      assume that the "0*" below will match the
                        #      correct number of zeroes.
        )
    )
    .                   # Skip over the first digit that will be different when
                        # incremented.
    9*                  # Skip over the portion that will become all 0s when
                        # incremented.
    
    # Match the next consecutive number. This constraint is what tells the
    # above how many digits to match.
    (?=
        (               # \5 = Capture the next number. This allows the last
                        #      number in the sequence to be matched as a whole
                        #      unambiguously, in case its digits form their own
                        #      "nested" squashed sequence.
            \2
            \4          # Note that since this is followed by a "0", to get
                        # this to parse correctly we could either concatenate
                        # them as "\4[0]*", or enable the /x flag (ignore
                        # whitespace) and use "\4 0*".
            0*          # Technically this should match the same number of 0s
                        # however many 9s were matched by "9*" above, but since
                        # our input is guaranteed to be valid, we can assume it
                        # will do this without being forced, since none of the
                        # numbers in the sequence will have leading zeroes.
        )
    )
)*                      # Iterate as many times as possible, with minimum zero.

Solving this problem is a bit verbose in pure regex, since it has no concept of alphanumeric/ASCII order or sorting. So each digit needs to be handled as a separate case.

Rejecting invalid input takes 138 bytes: ^(\6$|(?!0)(.*(?=(0.*1|1.*2|2.*3|3.*4|4.*5|5.*6|6.*7|7.*8|8.*9)(?<=(.)))|(?=9+(?<4>10))).(9)*(?=(?(7)\7))(?=(\2\4(?<-5>0)*(?(5)^))(.*)))*$

Regex (PCRE) + x flag, 107 bytes

(\4$|(?|(.*)(?=(?:0.*1|1.*2|2.*3|3.*4|4.*5|5.*6|6.*7|7.*8|8.*9)(?<=(.)))|()(?=9+(1))).9*(?=(\2\3 0*))(?C))*

Returns its result using a (?C) callout to report each split point (the number of split points will be one less than the number of consecutive integers).

Try it online! - PCRE1
Try it online! - PCRE2 v10.33
Attempt This Online! - PCRE2 v10.40+

This is a straightforward port of the .NET version.

# Main loop - Iterates once for each matched number in the squashed sequence.
# There is no need to anchor, because the input is guaranteed to be valid.
(
    \4$                 # Stop immediately if the previous iteration identified
                        # this as being next, and there is nothing following it.
|
    # Using greedy quantifiers, the following, up to and including "9*",
    # matches the number with as many digits as possible that is followed by
    # the next consecutive number.
    (?|
        (.*)            # \2 = the prefix portion of the number that won't
                        #      change when incremented
        (?=
            # Depending on this next digit, capture its incremented form in \3.
            # Only digits that do not carry when incremented are handled here.
            (?:
                0.*1 |
                1.*2 |
                2.*3 |
                3.*4 |
                4.*5 |
                5.*6 |
                6.*7 |
                7.*8 |
                8.*9
            )
            (?<=(.))    # \3
        )
    |
        # Treat a prefix of all 9s as a special case, because when incremented
        # it will be one digit longer, e.g. 999 -> 1000. In this case, \2 will
        # be empty.
        ()              # \2 = empty prefix
        (?=
            9+
            (1)         # \3 - Technically this should capture "10", but since
                        #      our input is guaranteed to be valid, we can
                        #      assume that the "0*" below will match the
                        #      correct number of zeroes.
        )
    )
    .                   # Skip over the first digit that will be different when
                        # incremented.
    9*                  # Skip over the portion that will become all 0s when
                        # incremented.
    (?=
        (               # \4 = Capture the next number. This allows the last
                        #      number in the sequence to be matched as a whole
                        #      unambiguously, in case its digits form their own
                        #      "nested" squashed sequence.
            \2
            \3          # Note that since this is followed by a "0", to get
                        # this to parse correctly we could either concatenate
                        # them as "\3[0]*", or enable the /x flag (ignore
                        # whitespace) and use "\3 0*".
            0*          # Technically this should match the same number of 0s
                        # however many 9s were matched by "9*" above, but since
                        # our input is guaranteed to be valid, we can assume it
                        # will do this without being forced, since none of the
                        # numbers in the sequence will have leading zeroes.
        )
    )
    (?C)                # PCRE callout - report each split point to the caller
)*

Rejecting invalid input is not so straightforward to port from the .NET version, and takes 175 bytes: ^(?>\7$((9(?=9*\4\5(\3?+0)))*(?=(?(6)\6))\4\5\3?+)?|(?|(?!0)(.*)(?=(?:0.*1|1.*2|2.*3|3.*4|4.*5|5.*6|6.*7|7.*8|8.*9)(?<=(.)))|()(?=9+(10))).(?=(?1)(.*))9*(?=(\4\5 0*)\6)(?C))*$

Regex (PCRE2) + x flag, 166 bytes

(?=(.*))(?:^(?3)|((?<=(?=^((?|(.*)(?=(?:0.*1|1.*2|2.*3|3.*4|4.*5|5.*6|6.*7|7.*8|8.*9)(?<=(.)))|()(?=9+(1))).9*(?=(\4\5 0*)))*(?=\1$)(?>\6$|)(?(?=$)^)|(?2)).))(?3)|.+)

Returns its result as the list of individual matches.

Attempt This Online!

A lot of overhead is added to achieve this output method. Captures are not preserved from one individual match to the next, thus to avoid incorrectly splitting the last number, the regex must look all the way back to the start, then parse forward from there, for each individual match. There's no variable-length lookbehind in PCRE2, so it is emulated using recursion.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ 233 bytes: (\k<M>$|(.+)0(9)*(?=(?<M>\2[1](?<-3>0)*(?(3)^)))|(.*)((1)|(2)|(3)|(4)|(5)|(6)|(7)|(8))(9)*(?=(?<M>\4((?<-6>2)|(?<-7>3)|(?<-8>4)|(?<-9>5)|(?<-10>6)|(?<-11>7)|(?<-12>8)|(?<-13>9))(?<-14>0)*(?(14)^)))|(9)+(?=(?<M>1(?<-16>0)*(?(16)^))))* \$\endgroup\$
    – Neil
    Jun 28, 2022 at 20:58
  • 1
    \$\begingroup\$ A (?!0) would allow you to fold 0 into the same case, but I didn't think of that quickly enough. \$\endgroup\$
    – Neil
    Jun 28, 2022 at 21:00
  • \$\begingroup\$ @Neil And the (?!0) isn't even needed, because the question states we may assume the input is always valid. \$\endgroup\$
    – Deadcode
    Jun 28, 2022 at 21:17
  • \$\begingroup\$ Ugh, I was thinking "how can you capture the next digit you want to match later on?"... solution is so obvious once you see it. \$\endgroup\$
    – Neil
    Jun 28, 2022 at 23:14
  • 1
    \$\begingroup\$ Costs 35 bytes to turn it into a Retina program: Try it online! \$\endgroup\$
    – Neil
    Jun 28, 2022 at 23:40
7
\$\begingroup\$

Haskell, 62 bytes

f s=[[a..b]|a<-[1..],b<-[a..a+length s],([a..b]>>=show)==s]!!0

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Vyxal, 10 8 bytes

øṖ⌊'ḣtṡ⁼

Try it Online!

Incredibly slow for some inputs, reasonable for others.

Explained

øṖ⌊'ḣtṡ⁼
øṖ⌊      # All sublists of the input, as numbers
   '     # Keep only those where:
    ḣtṡ  #   The range between the first and last item
       ⁼ #   Exactly equals the original item
\$\endgroup\$
6
\$\begingroup\$

Julia, 71 bytes

! =length
*(s,a=1,b=a,j=join(a:b))=!j<!s ? s*a*-~b : j!=s ? s*-~a : a:b

Attempt This Online!

Takes a string as input and returns a range (2:5 == [2,3,4,5]).

A brute-force approach that's actually not that bad. a is the starting number and b the last number. We increment b until the list is too long and start over for a=a+1

\$\endgroup\$
5
\$\begingroup\$

R, 66 bytes

\(n)repeat for(i in 1:(T=T+1))if(n==Reduce(paste0,i:T))return(i:T)

Attempt This Online!

\$\endgroup\$
4
\$\begingroup\$

J, 37 bytes

0{<((=<@;\"1)#&,<\"1@])".\<@":@+/i.@#

Try it online!

Not much in the way of golfiness (and it could surely be golfed more), but it executes decently fast, solving the test cases effectively instantly.

\$\endgroup\$
4
\$\begingroup\$

Husk, 10 bytes

ḟo=⁰ṁsṁṫḣN

Try it online!

      ṁ  N  # map across all integers N & concatenate:
        ḣ   #  range 1..N
       ṫ    #  suffix series: 1..N, 2..N, 3..N, ...
ḟo          # now return the first series 
  =⁰        #  for which the input equals    
    ṁs      #  mapped & concatenated string representations
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 82 bytes

f=(S,i=s='')=>(k=s+=S[i++],g=q=>q==S?o:S.match(q)?g(q+k,o.push(k++)):f(S,i))(o=[])

Try it online!

Commented

f = (                 // f is a recursive function taking:
  S,                  //   S = input string
  i =                 //   i = pointer in S
  s = ''              //   s = current prefix extracted from S
) => (                //
  k = s += S[i++],    // append the next character from S to s,
                      // copy the prefix in k and increment i
  g = q =>            // g is a recursive function taking a string q
    q == S ?          //   if q is equal to S:
      o               //     success: return o[]
    :                 //   else:
      S.match(q) ?    //     if q is found in S (*):
        g(            //       do a recursive call:
          q + k,      //         append k to q (q is coerced to a
                      //         string if it's not already)
          o.push(k++) //         append k to o[] (and increment k)
        )             //       end of recursive call
      :               //     else:
        f(S, i)       //       try again with an additional character
)(o = [])             // initial call to g with s = o = []

(*) This doesn't mean that q is correct so far because it can be found in the middle of the string. The purpose of this test is rather to know when to give up.

\$\endgroup\$
4
\$\begingroup\$

Curry (KiCS2) + :set +first, 37 bytes

f(x#y)=[x..y]
x#y|y-x>0=[x..y]>>=show

Attempt This Online!

A port of Fatalize's Brachylog answer.

This does not work on PAKCS.

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

Python3, 142 bytes:

f=lambda x,l=[]:l if''==x else max(w,key=len)if(w:=[f(x[k+1:],l+[int(x[:k+1])])for k,_ in enumerate(x)if l==[]or int(x[:k+1])==l[-1]+1])else w

Try it online!

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

Pyth, 13 bytes

ef!-.+T1sMM./

Try it online!

Accepts a string as input.

ef!-.+T1sMM./
           ./  String partitions of the input
        sMM    Convert elements to integers
 f    T        Filter for paritions T such that:
    .+           The list of deltas between elements of T...
  !-   1         ...becomes empty when 1s are removed
e              Keep the last remaining partition
\$\endgroup\$
3
\$\begingroup\$

Jelly, 9 bytes

ŒṖḌIİƑ$ƇḢ

Try it online!

ŒṖ           Find every partition of the input's digits,
  Ḍ          and convert each slice in each partition back to an integer.
       Ƈ     Filter to only those which
   I         have forward differences
    İƑ$      which are all their own inverses (i.e. 1).
        Ḣ    Yield the first remaining partition (nontrivial).
\$\endgroup\$
3
\$\begingroup\$

Python 3.8 (pre-release), 94 bytes

f=lambda a,d=2,c=1:(r:=(*range(x:=int(a[:c]),x+d),))*(d*"%d"%r==a)or f(a,d:=d%len(a)+1,c+1//d)

Try it online!

Nothing too fancy here.

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

Charcoal, 28 bytes

FIEθ…θ⊕κFLθ⊞υI…ι⁺⊕ι⊕κΦυ⁼θ⪫ιω

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

FIEθ…θ⊕κ

Loop over all of the nontrivial prefixes of the input.

FLθ⊞υI…ι⁺⊕ι⊕κ

Create ranges of length 2 up to the length of the input starting at each prefix.

Φυ⁼θ⪫ιω

Find any ranges whose concatenation equals the original input.

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

JavaScript (Node.js), 51 bytes

n=>(g=s=>s.match(n.join`,?`)||g(s+[,++i]))(i='')[0]

Try it online!

Input an array of characters. Output comma separated numbers as a single string.

It passes all testcases listed here. But I still have no idea if this answer is correct or not. Failed testcases are welcomed and I will try to fix it some how.

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

05AB1E, 6 bytes

.œ.Δ¥P

Try it online or verify all test cases.

Explanation:

.œ      # Get all partitions of the (implicit) input (the partition-list is ordered from
        # longest (all single digits) to shortest (single original integer)) 
  .Δ    # Find the first which is truthy for:
    ¥   #  Pop and push the deltas / forward differences
     P  #  Take the product of that
        #  (only 1 is truthy in 05AB1E)
        # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

Prolog (SWI), 68 64 bytes

-4 bytes thanks to Steffan pointing out a golf I somehow missed

A+B:-nth1(X,_,_),between(1,X,Y),numlist(Y,X,B),concat_atom(B,A).

Try it online!

Pretty straightforward.

Explanation:

A+B:-                 % A predicate with an atom A and a list of numbers B
     nth1(X,_,_),       % Find a positive number X
     between(1,X,Y),    % And a number Y between 1 and X
     numlist(Y,X,B),    % Generate the range [Y,X] into B
     concat_atom(B,A).  % The concatenated list should be the same atom as A
\$\endgroup\$
0
2
\$\begingroup\$

Rust, 242 235 bytes

|t:Vec<u64>|(0..).map(|v|{let mut y=vec![];y.extend(t.iter().scan((v,0),|(a,b),c|Some(if *b*10+c==*a+1{*a=c+*b*10;*b=0;Some(*a)}else{*b=*b*10+c;None})));y.last().unwrap().and(Some(y.into_iter().flatten()))}).flatten().next().unwrap();

Tries every initial number till it finds one that completes the sequence. Playground

Saved 7 bytes by using let mut y=vec![];y.extend(X) unstead of let y:Vec<Option<u64>>=X.collect()

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

Python 3.8 (pre-release), 120 bytes

lambda s:g(s)[1]
g=lambda s:s and[j+[k]for i in range(-len(s),0)for j in g(s[:i])if{*j[-1:]}<={~-(k:=int(s[i:]))}]or[[]]

Try it online!

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

Raku, 44 bytes

{+«m/^(\d+?)+<?{1==all $0[1..*]Z-$0}>$/[0]}

Try it online!

The regex match m/.../ does the heavy lifting here.

  • ^ matches the start of the input string or number, as usual.
  • (\d+?)+ matches a sequence of groups of digits, each of minimal length such that the overall match succeeds.
  • <?{ ... }> is an assertion; the Raku code inside the braces must evaluate to a true value for the match to succeed. Inside the braces, $0 is a list of the matched digit groups. $0[1..*] Z- $0 is the tail of the list zipped using subtraction with the list; this is the list of differences between each adjacent pair of digit groups. 1 == all ... tests that all of them are equal to 1. If the assertion fails, the match backtracks to try a different group of digits.
  • $ matches the end of the input, as usual.

Finally, [0] extracts the first matching group--which is a list, since the group was followed by a quantifier--and converts those match objects to numbers.

\$\endgroup\$
1
  • \$\begingroup\$ You can remove the anchors, since it is always going to match the whole string, and invert the condition to save three bytes. \$\endgroup\$
    – Jo King
    Sep 18, 2022 at 6:50
1
\$\begingroup\$

JavaScript (Node.js), 71 bytes

f=(s,i,p='',...a)=>p==s?a:s.match(p)&&f(s,-~i,p+i,...a,i)||!p&&f(s,-~i)

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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