15
\$\begingroup\$

Given as input a positive nonzero integer n >= 10 and a sequence of digits 0-9 (which may be taken as a string or a list), find the first contiguous subsequence of digits in the sequence that sums to n and output the start and end indexes. You may use zero- or one-based indexing. If no such subsequence exists, your program may output any constant value.

Examples

These examples use zero-based indexing.

Input: 10 123456789
Output: 0 3
Input: 32 444444444
Output: 0 7
Input: 15 123456789
Output: 0 4
Input: 33 444444444
Output: No solutions

This is , so shortest program wins!

\$\endgroup\$
8
  • 2
    \$\begingroup\$ Is it ok to output as start, length instead of start, end? \$\endgroup\$
    – mousetail
    Commented Jan 10, 2023 at 13:53
  • 2
    \$\begingroup\$ @mousetail Nope. \$\endgroup\$
    – Ginger
    Commented Jan 10, 2023 at 18:27
  • 1
    \$\begingroup\$ @NahuelFouilleul Yes, as long as you make that clear in your answer. \$\endgroup\$
    – Ginger
    Commented Jan 10, 2023 at 18:27
  • 2
    \$\begingroup\$ A test case resulting in a non-zero offset would help in ensuring correctness. \$\endgroup\$
    – Kjetil S
    Commented Jan 10, 2023 at 20:30
  • 3
    \$\begingroup\$ Indices is the correct plural in a mathematical context. (But databases have indexes.) \$\endgroup\$
    – Neil
    Commented Jan 10, 2023 at 22:58

23 Answers 23

6
\$\begingroup\$

Excel (ms365), 155 bytes

Assuming list as input and 0-indexed output:

enter image description here

Formula in C1:

=LET(x,TOCOL(B:B,1),y,COUNT(x),REDUCE("No solutions",SEQUENCE(y),LAMBDA(a,b,IFERROR(HSTACK(y-b,y-b+MATCH(A1,SCAN(0,DROP(x,y-b),LAMBDA(c,d,c+d)),0)-1),a))))

The idea here is to use SCAN() to iterate from each element in reversed order in column B and MATCH() the value in A1 against each resulting array. If found, then HSTACK() both the current iteration and the position the element is found.

Unfortunately this process is rather verbose in Excel, but fun to attempt this challenge nonetheless.


enter image description here enter image description here enter image description here

\$\endgroup\$
1
  • 1
    \$\begingroup\$ No solutions can be x, since it's allowed to output any constant value. 🤷 \$\endgroup\$ Commented Jan 11, 2023 at 7:37
5
\$\begingroup\$

><> (Fish), 126 bytes

i01:}r[l0$>:?v~]}r4[{:}]=?v1+$:@$:@l5-$-)?v20.
/[-2lr@@+@:$@/    ;n+oan:$/-3lr1;?=-2l:+1~/ 
\}]r1-a0.                 \[}]r20.

Try it

Explanation

enter image description here

Takes the array of characters as the initial value of the stack and the target as the input over STDIN. Outputs nothing if no solution exists, and an exclusive range if it does.

i01 push the target value, the start of the range, and the length to the stack.

:}r[l0$>: Push the top "length" elements of the stack to a new stack. Set it's length, that's the amount of elements we want to compare.

@$:@+@@rl2-]}]r1-a0. This adds the top of the stack to the accumulator, rotates the stack, then subtract one from the number of remaining rotations necessary.

~]} pop 0, the remaining number of rotations, and combine the stack back with the previous. Now the sum of the top N elements of the input are on top of the stack.

r4[{:}]= Copy the target sum to the end of the input.

=?v
   \$:nao+n;

If the sum equals the target, output.

1+$:@$:@15-$-)?v Add one to the length. If it's greater than the remaining length of the list go down.

~1+:l2-=?; Add one to the starting value. If it's greater than the length of the input exit.

1rl3-[}]r Set the length back to 1. Shift the rest of the stack over one so it starts at the second position.

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

05AB1E, 11 bytes

ā<ã.Δ¹sŸèOQ

Inputs in the order sequence, n.
0-based output; will output -1 if no result can be found; and [i,i] if n is a single digit that's present in the input-sequence.

Try it online or verify all test cases.

Explanation:

ā            # Push a list in the range [1, length of the first (implicit) input sequence]
 <           # Decrease each by to make it a 0-based [1,length)
  ã          # Cartesian power of 2 to get all possible pairs of this list
   .Δ        # Find the first pair that's truthy for:
     ¹       #  Push the first input-sequence again
      s      #  Swap so the current pair is at the top
       Ÿ     #  Pop and push a list in the range of this pair
        Ù    #  Uniquify this list (in case the pair was [a,a])
         è   #  Index each into the first input-sequence
          O  #  Sum these digits together
           Q #  Check if this sum is equal to the second (implicit) input
             # (after which the result is output implicitly)
\$\endgroup\$
5
\$\begingroup\$

Vyxal g, 11 bytes

ẏ:Ẋ'ƒṡ¹İ∑⁰=

Try it Online!

A simple little approach.

Explained

ẏ:Ẋ'ƒṡ¹İ∑⁰=
ẏ:              # The range [0, len(input)), twice.
  Ẋ             # cartesian product of the two lists and sort to get the first
   '            # get all items of that where
    ƒṡ          # the list turned into an inclusive range between the two numbers
      ¹İ        # indexed into the sequence of numbers
        ∑⁰=     # summed equals n
# g flag gets the smallest pair
\$\endgroup\$
1
5
\$\begingroup\$

Python 3.8 (pre-release), 75 bytes

f=lambda v,l,a=0,b=1:v==(q:=sum(l[a:b]))and(a,b-1)or f(v,l,a+(q>v),b+(q<v))

Try it online!

Switched to a list of integers instead of a string for -9 bytes

old:

f=lambda v,l,a=0,b=1:v==(q:=sum(map(int,l[a:b])))and(a,b-1)or f(v,l,a+(q>v),b+(q<v))

Try it online!

Takes an integer and a string as input. Returns a tuple with start and end index if a solution is found, and an error if not.

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

JavaScript (ES6), 64 bytes

-1 thanks to @l4m2

Expects (n)(array). Returns either [start, end] or false.

n=>a=>a.some((_,i)=>a.some((v,j)=>j<i||(s-=v)?0:o=[i,j],s=n))&&o

Try it online!

Commented

n =>               // n = target sum
a =>               // a[] = array of digits
a.some((_, i) =>   // for each digit at index i in a[]:
  a.some((v, j) => //   for each digit v at index j in a[]:
    j < i ||       //     if j is less than i
    (s -= v)       //     or subtracting v from s
    ?              //     does not result in 0:
      0            //       do nothing
    :              //     else:
      o = [i, j],  //       set o = [i, j] and exit
    s = n          //     start with s = n
  )                //   end of inner some()
)                  // end of outer some()
&& o               // if successful, return o[]
\$\endgroup\$
1
  • 1
    \$\begingroup\$ tio.run/… \$\endgroup\$
    – l4m2
    Commented Jan 10, 2023 at 16:56
4
\$\begingroup\$

Japt, 15 bytes

ðÊï æÈrõ xgU ¶V

Try it

ðÊï æÈrõ xgU ¶V     :Implicit input of digit array U and integer V
ð                   :0-based indices of elements of U that are truthy under
 Ê                  :  Factorial
  ï                 :Cartesian product with itself
    æ               :First element/pair that returns true when
     È              :Passed through the following function
      r             :  Reduce by
       õ            :    Inclusive range
         x          :  Reduce by addition after
          gU        :    Indexing each into U
             ¶V     :  Is equal to V?
\$\endgroup\$
4
\$\begingroup\$

R 4.1, 78 bytes 71 bytes 65 bytes

v1.2 65 bytes

-5 bytes thanks to pajonk:

  1. -4 for pointing out that F <- F + 1;k <- m[, F];sum(s[k:k[2]]) can be expressed as sum(s[(k <- m[, F <- F + 1]):k[2]]). This also means you can lose the curly braces as the expression is on one line, and you do not need semi-colons.
  2. -1 because while(a!=b) can actually be expressed as while(a-b). This is safe as negative numbers are also TRUE when coerced to logical.

(And also -1 byte by pointing out I had miscounted.)

\(s,n,m=combn(seq(s),2)){while(sum(s[(k=m[,F<-F+1]):k[2]])-n)0
k}

[Attempt This Online!]https://ato.pxeger.com/run?1=m72waMGSNAUb3aWlJWm6FjcdYzSKdfJ0cm2T83OT8jSKUws1ijV1jDQ1q8szMnNSNYpLczWKozWybXOjddxsdN20DWM1rbKjjWJjNXXzNA24smuhBrkpK4SkFpcoJCcWpxZzpWkYWlnqKBgaaAKZRakFGiZgjo6CsZEmXNIUQ9JYE2LaggUQGgA)

v 1.1 71 bytes

\(s,n,m=combn(seq(s),2)){while({F=F+1;k<-m[,F];sum(s[k:k[2]])!=n})0
k}

-7 bytes thanks to Giuseppe

Two changes:

  1. Not replacing seq() with the unary - as it's only being used once (I was using it twice before and failed to notice that was no longer the case).

  2. Replacing j with F is yet another ludicrous thing that R allows you to do that I would never have tried in the vein of these coercion tips by @rturnbull (link from Giuseppe - thanks). For non-R uses, T and F are built-in aliases for TRUE and FALSE. This means you can do this:

T == TRUE # TRUE
F == FALSE # TRUE
F == TRUE # FALSE
F  <- F+1
F == FALSE # FALSE
F == TRUE # TRUE

I have no idea why this is allowed in R but it's saved 5 characters compared with initialising j.

v.1.0 78 bytes

\(s,n,`-`=seq,j=0,m=combn(-s,2)){while({j=j+1;k<-m[,j];sum(s[k:k[2]])!=n})0
k}

Attempt this online

How?

This is a function which expects a vector, s and a target value n, as arguments. Basically it does this:

  1. Uses combn() to create a m, a matrix of all possible length 2 combinations of the indices of s. E.g. combn(1:5,2) produces:
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    1    1    1    1    2    2    2    3    3     4
[2,]    2    3    4    5    3    4    5    4    5     5
  1. Loops through the columns of this to subset s, using row 1 as the start index and row 2 as the end index.

  2. Breaks the loop if the subset adds up to n. It exits with an error if there is no solution. I wasn't entirely clear if an error counts as a constant, but this nice Python answer behaves in the same way, which I took as a green light.

  3. There are a couple of golfing tricks both from Giuseppe. Taking advantage of how seq(s) behaves if s is a vector and reassigning the unary - with `-` = seq, means we can do m = combn(-s, 2) instead of the positively verbose m = combn(seq_along(s), 2).

The test cases are included in the footer of ATO link. Only my second Code Golf answer ever so very interested in any suggestions / improvements.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ As nice as the seq trick is, it's shorter to just use it directly since you're only using it once, so combn(seq(s),2), and using F instead of j should save another few: ATO \$\endgroup\$
    – Giuseppe
    Commented Jan 11, 2023 at 15:19
  • \$\begingroup\$ @Giuseppe you're right! I was using it twice in a previous version. I had no idea you could increment T and F like that. So on the first iteration of the loop, F==FALSE is FALSE and F==TRUE is TRUE. That is truly bonkers. Thanks for the suggestions. \$\endgroup\$
    – SamR
    Commented Jan 11, 2023 at 15:26
  • \$\begingroup\$ Yes, F is initialized to FALSE which gets coerced to a numeric (specifically, 0) when you do the addition; similarly, T is initialized to TRUE which converts to 1 when you do arithmetic. This tip has some additional examples of implicit type conversions, but there are others; notably F and T will coerce to "FALSE" and "TRUE", respectively, when converted to a character \$\endgroup\$
    – Giuseppe
    Commented Jan 11, 2023 at 15:30
  • 1
    \$\begingroup\$ 1. I think your solution is actually 70 bytes. 2. 66 bytes by inlining what's possible and getting rid of semicolons and braces. \$\endgroup\$
    – pajonk
    Commented Aug 21, 2023 at 18:26
  • 1
    \$\begingroup\$ Another -1 byte by replacing != with - -- sorry I missed it the in the previous golf. \$\endgroup\$
    – pajonk
    Commented Aug 22, 2023 at 4:46
3
\$\begingroup\$

Perl 5 List::Util, 82 bytes

sub{$s=pop;($i,$j)=($_%@_,int$_/@_),$s-sum(@_[$i..$j])||return($i,$j)for 0..@_*@_}

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ -13 bytes using nested for syntax \$\endgroup\$ Commented Jan 10, 2023 at 16:59
  • 1
    \$\begingroup\$ otherwise another 71 bytes with a regex, if 1-based indexing accepted for the end \$\endgroup\$ Commented Jan 10, 2023 at 17:02
  • \$\begingroup\$ @NahuelFouilleul – I was sure one for would be shorter than two. But there you go :-) \$\endgroup\$
    – Kjetil S
    Commented Jan 10, 2023 at 20:33
  • \$\begingroup\$ @NahuelFouilleul – Nice, I thought about regex but not this inner (??{}) magic. Your answer can be shortened to 62 bytes. \$\endgroup\$
    – Kjetil S
    Commented Jan 10, 2023 at 20:56
3
\$\begingroup\$

Pyth, 18 bytes

KEhfqQs:KhTheT^UK2

Try it online!

Takes n, sequence as separate inputs. Outputs [start, end] or an index error if no sequence exists.

Explanation

                      # implicitly assign Q = eval(input())
KE                    # assign K = eval(input())
              ^  2    # cartesian product of two copies of
               UK     # range(len(K))
   f                  # filter this on lambda T
      s               #   sum of
       :KhTheT        #   slice K from first element of product to second element plus 1
    qQ                #   equals Q
  h                   # take the first element (this will give us the indices if they exist or an index error if they don't)
\$\endgroup\$
3
\$\begingroup\$

Jelly, 12 bytes

Jṗ2r/ị³S=ʋƇḢ

Try it online!

Full program, that takes a list of digits and an integer \$n\$, and outputs the 1-indexed indices, or 0 if there's no solution.

How it works

Jṗ2r/ị³S=ʋƇḢ - Main link. Takes a list of digits D on the left, and n on the right
J            - Indices; [1, 2, ..., len(D)]
 ṗ2          - Cartesian square
         ʋƇ  - Filter the indices on the dyad f([i, j], n):
   r/        -   Range; [i, i+1, ..., j-1, j]
     ị³      -   Index into D
       S     -   Sum
        =    -   Does that equal n?
           Ḣ - Take the first pair, or zero if there's no solution
\$\endgroup\$
3
\$\begingroup\$

C (clang), 90 88 bytes

i;j;a;f(*s,n){for(a=i=-1;s[++i]*a;)for(a=n,j=i;a*s[j];)a-=s[j++]-48;*s++=!a*i-1;*s=j-1;}

Try it online!

Saved 2 bytes thanks to ceilingcat!!!

Inputs a pointer to a wide charater string of the sequence and \$n\$.
Returns the first and last position in the array referenced by the input pointer or \$-1\$ if no sum exists.

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

Thunno, \$ 25 \log_{256}(96) \approx \$ 20.58 bytes

LRDZ!gAu1+:z0sAISz1=kAJ0~

Takes a list of digits, then a number. Outputs 0 if it doesn't find the subsequence.

Explanation

LRDZ!gAu1+:z0sAISz1=kAJ0~  # Implicit input
LR                         # range(len(input))
  DZ!                      # Cartesian product with itself
     g              k      # Filter for items where the following is truthy:
      Au                   #  Dump the pair onto the stack
        1+                 #  Add one to the last one (because of how Thunno's range works)
          :                #  Range between the two numbers
             sAI           #  Indexed into 
           z0              #  The first input (this will return a list)
                S          #  The sum of this list
                 z1=       #  Equals the second input?
                     AJ    # After the filter, get the first item of the list
                       0~  # If the list was empty, push 0

Screenshots

Screenshot 1 Screenshot 2

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

Desmos, 79 bytes

L=[1...l.length]
T=[0^{(l[I...E].total-s)^2}(I,E)forE=L,I=L]
f(s,l)=T[T.x>0][1]

\$f\$ returns a point (I,E) that has the starting index I and the ending index E as the \$x\$ and \$y\$ coordinates, respectively, and returns the answer one-indexed.

For no solution, \$f\$ returns the point (undefined,undefined).

Note that because of the limitations of Desmos, this will not work for input lists longer than \$100\$ elements.

Try It On Desmos!

Try It On Desmos! - Prettified

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

C (clang), 76 bytes

Takes a list of digits and a number as input and returns \$[start, end)\$.

i;j;f(*l,s,n){for(i=j=0;n<0|s/~j*n;)n-=n>0?l[j++]:-l[i++];l[1]=j;*l=n?-1:i;}

How it works

i;j;             // start and end of the sliding window, respectively.
f(*l, s, n) {    // input a list of integers, its size and the number.
  for(           // main loop
    i = j = 0;   // start with i = 0 and j = 0 (empty window)
    n < 0 |      // the sum of elements in the window exceeds n, we will remove elements in the next iteration
    s / ~j * n;) // j < l and the sum of elements does not match n
      n -=       // subtract from n:
        n > 0 ?  // if n > 0 ...
          l[j++] // increase the window size.
        :        // else (n < 0) ...
         -l[i++] // decrease the window size.
      ;          // end main loop
  l[1] = j;      // l doubles as return placeholder. l[1] is the end of the window.
  *l =           // l[0] is:
    n ?          // if n != 0 ...
      -1         // there was no solution, set it to -1.
    :            // else (n == 0) ...
      i;         // we found the solution, set it to the start of the window.
}

Try it online!

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

Julia, 69 65 47 bytes

~=:;y^x=argmax(k->sum(x[k])==y,(q=keys(x)).~q')

Attempt This Online!

Uses 1-based indexing. Prints the range 1:1 if no solution exists.

  • -4 bytes thanks to MarcMush: Replace 1:length(x) with keys(x)

  • -18 bytes (!!) thanks to MarcMush: Improve range generation

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can use keys instead of 1:length \$\endgroup\$
    – MarcMush
    Commented Jan 18, 2023 at 14:10
  • \$\begingroup\$ 47 bytes \$\endgroup\$
    – MarcMush
    Commented Jun 16, 2023 at 22:08
1
\$\begingroup\$

Charcoal, 25 bytes

NθI⌊ΦEη⟦κ⌕EηΣ✂ηκ⊕μ¹θ⟧⊕↨ι⁰

Try it online! Link is to verbose version of code. Outputs None if there is no solution. Explanation:

Nθ                          First input as a number
      η                     Second input
     E                     Map over digits 
        κ                   Current index
           η                Second input
          E                 Map over digits
              η             Second input
             ✂    ¹         Sliced from
               κ            Outer index to
                 μ          Inner index
                ⊕           Incremented
            Σ               Take the sum
         ⌕                  Find index of
                   θ        First input
       ⟦            ⟧       Make into list
    Φ                       Filtered where
                      ↨ι⁰   Last element
                     ⊕      Is not `-1`
   ⌊                        Take the minimum (first if it exists)
  I                         Cast to string
                            Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Factor + math.combinatorics math.unicode, 69 bytes

[| n s | s length iota 2 [ last2 s subseq Σ n = ] find-combination ]

Try it online!

Returns a 0-based start index and 1-based end index. Returns f if there is no solution.

\$\endgroup\$
1
\$\begingroup\$

C99:

int main() {
    int x = 22;
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, n = sizeof(a) / sizeof(int);
    
    int i = 0, j = 0, s = 0;
    while ((s < x && j < n) || (s > x && i < n))
        s += s < x ? a[j++] : -a[i++];

    printf("found: %d, i: %d, j: %d", s == x, i, j - 1);
    return 0;
}

The algorithm actually takes 66 bytes:

inti=0,j=0,s=0;while((s<x&&j<n)||(s>x&&i<n))s+=s<x?a[j++]:-a[i++];

Try it!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 71 bytes

x#y=take 1[[s,e]|i<-[[0..length x-1]],s<-i,e<-i,sum[x!!i|i<-[s..e]]==y]

Try it online!

Haskell, 77 bytes

x#y=take 1[[s,e]|let m=length x-1,s<-[0..m],e<-[s..m],sum[x!!i|i<-[s..e]]==y]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Ruby, 58 56 bytes

Returns nil if no subsequence is found.

-2 bytes thanks to Value Ink

->n,a{(b=*0...a.size).product(b).find{a[_1.._2].sum==n}}

Attempt This Online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Skip the brackets; (b=*0...a.size) works just fine. \$\endgroup\$
    – Value Ink
    Commented Aug 21, 2023 at 21:01
0
\$\begingroup\$

Arturo, 79 bytes

$[n,a][l:-size a 1loop 0..l'x[loop x..l'y[if n=sum slice a x y->return[x,y]]]0]

Try it

Returns [start end+1] or 0 if there's no solution.

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

Scala, 91 bytes

Golfed version. Try it online!

(a,t)=>a.indices.flatMap(s=>(s until a.length).filter(e=>a.slice(s,e+1).sum==t).map((s,_)))

Ungolfed version. Try it online!

object Main {

  def findSubarrays(arr: Array[Int], target: Int): Seq[(Int, Int)] = {
    for {
      start <- arr.indices
      end <- start until arr.length
      if arr.slice(start, end + 1).sum == target
    } yield (start, end)
  }

  def main(args: Array[String]): Unit = {
    val numbers = "12345".map(_.asDigit).toArray
    val target = 12
    println(findSubarrays(numbers, target))
  }

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