# Find Array Runs

Find the runs inside an array

A run is defined as three or more numbers that increment from the previous with a constant step. For example [1,2,3] would be a run with step 1, [1,3,5,7] would be a run with step 2, and [1,2,4,5] is not a run.

We can express these runs by the notation "i to j by s" where i is the first number of the run, j is the last number of the run, and s is the step. However, runs of step 1 will be expressed "i to j".

So using the arrays before, we get:

• [1,2,3] -> "1to3"

• [1,3,5,7] -> "1to7by2"

• [1,2,4,5] -> "1 2 4 5"

In this challenge, it is your task to do this for arrays that may have multiple runs.

Example Python code with recursion:

def arr_comp_rec(a, start_index):
# Early exit and recursion end point
if start_index == len(a)-1:
return str(a[-1])
elif start_index == len(a):
return ''

# Keep track of first delta to compare while searching
first_delta = a[start_index+1] - a[start_index]
last = True
for i in range(start_index, len(a)-1):
delta = a[i+1] - a[i]
if delta != first_delta:
last = False
break
# If it ran through the for loop, we need to make sure it gets the last value
if last: i += 1

if i - start_index > 1:
# There is more than 2 numbers between the indexes
if first_delta == 1:
# We don't need by if step = 1
return "{}to{} ".format(a[start_index], a[i]) + arr_comp_rec(a, i+1)
else:
return "{}to{}by{} ".format(a[start_index], a[i], first_delta) + arr_comp_rec(a, i+1)
else:
# There is only one number we can return
return "{} ".format(a[start_index]) + arr_comp_rec(a, i)


IO is flexible

Input

Array of sorted positive ints (no duplicates)

Output

String of the runs separated by a space, or a string array of the runs

Does not need to be greedy in a particular direction

Can have trailing whitespace

Test Cases

In: [1000, 1002, 1004, 1006, 1008, 1010]
Out: "1000to1010by2"

In: [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
Out: "1to3 5 8 13 21 34 55 89 144 233"

In: [10, 20, 30, 40, 60]
Out: "10to40by10 60"

In: [5, 6, 8, 11, 15, 16, 17]
Out: "5 6 8 11 15to17"

In: [1, 2, 3, 4, 5, 6, 7, 9, 11, 13, 15, 30, 45, 50, 60, 70, 80, 90, 91, 93]
Out: "1to7 9to15by2 30 45 50to90by10 91 93"


This is so least number of bytes wins.

• related – Luis felipe De jesus Munoz Aug 26 '18 at 23:23
• Must it be greedy left-to-right? (i.e. can [4, 5, 6, 7, 9, 11, 13, 15] not be 4to6 7to15by2?) – Jonathan Allan Aug 26 '18 at 23:44
• @JonathanAllan No, it does not necessarily need to be left greedy. – WretchedLout Aug 27 '18 at 0:01
• I suppose there will be no duplicate entries? – Shieru Asakoto Aug 27 '18 at 1:18
• Only Positive Integers. @Οurous Trailing whitespace acceptable. – WretchedLout Aug 27 '18 at 3:19

# Jelly,  42  40 bytes

-2 thanks to Kevin Cruijssen (filter out twos, ḟ2, rather than replacing twos with zeros, 2,0y)

ŒṖIE×LƲ€ḟ2SƊÞṪµ.ịU,Iḟ1ƊQ€Fż“to“by”ṁṖƊ$)K  A full program printing the result. (As a monadic Link a list containing a mixture of integers and characters would be yielded) Try it online! (Too inefficient for the largest test-case to complete within 60s, so I removed [1,2,3,4].) ### How? ŒṖIE×LƲ€ḟ2SƊÞṪµ.ịU,Iḟ1ƊQ€Fż“to“by”ṁṖƊ$)K - Main Link: list of numbers
ŒṖ                                       - all partitions
ƊÞ                            - sort by last three links as a monad:
Ʋ€                                 -   last four links as a monad for €ach:
I                                      -     incremental differences (of the part)
E                                     -     all equal?
L                                   -     length (of the part)
×                                    -     multiply
ḟ2                               -   filter discard twos
S                              -   sum
Ṫ                           - tail (gets us the desired partition of the input)
µ                       )  - perform this monadic chain for €ach:
.                         -   literal 0.5
ị                        -   index into (the part) - getting [tail,head]
U                       -   upend - getting [head,tail]
Ɗ                  -   last three links as a monad:
I                     -     incremental differences (of the part)
1                   -     literal one
ḟ                    -     filter discard (remove the ones)
,                      -   pair -> [[head,tail],[deltasWithoutOnes]]
Q€                -   de-duplicate €ach -> [[head,tail],[delta]] or [[head,tail],[]] or [[loneValue],[]]
F               -   flatten -> [head,tail,delta] or [head,tail] or [loneValue]
$- last two links as a monad: Ɗ - last three links as a monad: “to“by” - literal list [['t', 'o'], ['b', 'y']] Ṗ - pop (get flattened result without rightmost entry) ṁ - mould ["to","by"] like that (i.e. ["to","by"] or ["to"] or []) ż - zip together K - join with spaces - implicit print  • 'by' should not be used if step = 1 – WretchedLout Aug 27 '18 at 3:25 • oh Gawwwd :p Thanks for the heads-up! – Jonathan Allan Aug 27 '18 at 3:30 • 2,0ySƲÞ can be golfed to ḟ2SƊÞ for -2 bytes. – Kevin Cruijssen Aug 28 '18 at 9:42 • @KevinCruijssen very true, nice golf, thanks – Jonathan Allan Aug 28 '18 at 17:02 • @KevinCruijssen FYI I remember why that was there now - originally I was trying to do my sorting with a product, P, rather than a sum S and would have needed the zeros. – Jonathan Allan Aug 28 '18 at 17:21 # Swift, 246 bytes func f(_ a:[Int]){ var c=a.count,m=a+a,z=0,r:String="" for i in 1..<c{m[i]-=a[i-1];if m[i]==m[i-1]{m[i-1]=0}};m[0]=1 for i in 0..<c{if m[i]==0 {z=1}else if z==0{r+=" \(a[i])"}else{r+="to\(a[i])"+(m[i]>1 ? "by\(m[i])":"");z=0;m[i+1]=1}} print(r) }  Try it online! • Welcome to Programming Puzzles & Code Golf! Very nice first answer. I hope you'll stay around because the Swift community here is... really small! – Mr. Xcoder Aug 27 '18 at 8:23 • This saves you a couple of bytes – Mr. Xcoder Aug 27 '18 at 8:26 # K (ngn/k), 102 bytes {1_,//${H:" ",h:*x;l:+/&\x=h+(!#x)*d:--/2#x;$[l>2;(H;"to";x l-1;(~d=1)#,"by",d;o l_x);l;H,o 1_x;""]}x}  Try it online! # JavaScript (ES6), 129 bytes Returns an array of strings. a=>(a.map((n,i)=>n+[n-a[i+1]||''])+'').replace(/(\d+)(-\d+)(?:,\d+\2)+,(\d+)/g,(_,a,b,c)=>a+'to'+(~b?c+'by'+-b:c)).split(/-\d+,/)  Try it online! ## How? ### Step #1 We first append to each number a suffix consisting of a leading '-' followed by the difference with the next number, except for the last entry which is left unchanged. This new array is coerced to a string. (a.map((n, i) => n + [n - a[i + 1] || '']) + '')  Example: Input : [ 1, 2, 3, 5, 9, 11, 13, 20 ] Output: "1-1,2-1,3-2,5-4,9-2,11-2,13-7,20"  ### Step #2 We identify all runs in the resulting string and replace them with the appropriate notation. .replace( /(\d+)(-\d+)(?:,\d+\2)+,(\d+)/g, (_, a, b, c) => a + 'to' + (~b ? c + 'by' + -b : c) )  Example: Input : "1-1,2-1,3-2,5-4,9-2,11-2,13-7,20" Output: "1to3-2,5-4,9to13by2-7,20"  ### Step #3 Finally, we split the string on the remaining suffixes, including the trailing commas. .split(/-\d+,/)  Example: Input : "1to3-2,5-4,9to13by2-7,20" Output: [ '1to3', '5', '9to13by2', '20' ]  # Ruby, 125 118 bytes ->a{i=y=0;a.chunk{|x|-y+y=x}.map{|z,w|2-i<(s=w.size)?"#{w[i*s]}to#{w[~i=0]}"+"by#{z}"*(z<=>1)+' ':' '*i+w*' '*i=1}*''}  Try it online! ### Explanation Ruby's Enumerable has a useful chunk method that does precisely what we need here - it groups items by consecutive runs of the same return value from the block, in our case - the difference between the current (x) and previous (y) value. The caveat is that such strategy won't capture the first element of the run, e.g. here only the two last elements are grouped together: Input: [5, 6, 8, 11, 15, 16, 17] Grouped: [[5, [5]], [1, [6]], [2, [8]], [3, [11]], [4, [15]], [1, [16, 17]]]  Therefore, while mapping to the correctly formatted strings, when we encounter a new potential run (chunk with > 1 item), we must track if the previous item was single (i=1) or already used in another run (i=0). If there is an unused single item, it becomes the starting point of the run, and lowers the chunk size threshold from 3 to 2. # R, 180 175 bytes r=rle(c(0,diff(a<-scan())));for(j in 1:sum(1|r$l)){l=r$l[j];v=r$v[j];i=T+l-1;cat("if"(l>2-F,paste0(a[T][!F],"to",a[i],"by"[v>1],v[v>1]," "),c("",a[T:i])[-3^F]));T=i+1;F=l<3-F}


Try it online!

Conceptually, this is a port of my Ruby answer, though obviously quite a bit different technically.

5 bytes saved by JayCe.

• I wanted to to something with rle but was too lazy... you can save 1 byte doing sum(1|x) in place of length(x): TIO – JayCe Aug 30 '18 at 13:51
• Actually you can have just 1 cat  for 175 bytes: TIO – JayCe Aug 30 '18 at 13:59
• Ah, great, thanks! – Kirill L. Aug 30 '18 at 16:30

# R, 238 217 bytes

Thanks @digEmAll for -19 bytes.

function(v,R=rle(diff(v)),L=R$l,S=sum(L|1),Y=0)if(!S)cat(v)else for(i in 1:S){D=R$v[i]
N=L[i]-F
if(N>1){N=N+1
cat(v[Y+1],'to',v[Y+N],'by'[D>1],D[D>1],' ',sep='')
F=1}else{N=N+(i==S)
if(N>0)cat(v[Y+1:N],'')
F=0}
Y=Y+N}


Try it online!

• use F instead of n as it's already initialized to 0, which should save a few bytes, I think. – Giuseppe Aug 28 '18 at 19:43
• This one is frustrating. You're nearly there by just using split, diff and rle. Unfortunately, the greedy search for runs means a lot of fiddling. – J.Doe Aug 29 '18 at 10:08
• 214 bytes Almost there, the only problem is the uncorrect spacing sometimes... – digEmAll Aug 29 '18 at 12:13
• That 'by'[D>1] is a good trick. – J.Doe Aug 29 '18 at 12:54
• This seems to work fine 217 bytes – digEmAll Aug 29 '18 at 18:46

# JavaScript (Node.js), 177 173 bytes

a=>{for(h=t=p=d=0,o=[];(c=a[t])||h<t;p=c,t++)d||!c?c-p!=d?(o.push(...[[a[h]+"to"+p+(d>1?"by"+d:"")],[p],[p-d,p]][t-h<3?t-h:0]),d=0,h=t--):0:!d&&t-h?d=c-p:0;return o.join }


Try it online!

# Clean, 208 ... 185 bytes

import StdEnv,Data.List,Text
l=length
$[]=""$k=last[u<+(if(v>[])("to"<+last v<+if(u<v!!0-1)("by"<+(v!!0-u))"")"")+" "+ $t\\i=:[u:v]<-inits k&t<-tails k|l(nub(zipWith(-)i v))<2&&l i<>2]  Try it online! # Jelly, 41 bytes ŒṖIE€Ạ$>Ẉ2eƊƲƇṪµ.ịṚj⁾to;IḢ⁾by;ẋ⁻1$ƲƊµḊ¡€K  Try it online! Full program. # Python 2, 170 166 bytes def f(a): j=len(a) while j>2: l,r=a[:j:j-1];s=(r-l)/~-j if a[:j]==range(l,r+1,s):return[l+'to%d'%r+'by%d'%s*(s>1)]+f(a[j:]) j-=1 return a and[a[0]]+f(a[1:])  Try it online! • I'm not sure if this output format is valid; the runs should all be strings, no? – Erik the Outgolfer Aug 27 '18 at 11:56 • @EriktheOutgolfer Fixed – TFeld Aug 27 '18 at 12:01 # Python 2, 138 136 bytes -2 bytes thanks to Erik the Outgolfer. r=[];d=0 for n in input()+[0]: a=n-([n]+r)[-1] if(a-d)*d: if r[2:]:r=["%dto"%r[0]+r[-1]+"by%s"%d*(1%d)] print r.pop(0), r+=n,;d=a  Try it online! # gvm (commit 2612106) bytecode, 108 bytes Expects the size of the array in one line, then the members each in one line. Hexdump: > hexdump -C findruns.bin 00000000 e1 0a 00 10 00 e1 0b 00 ff c8 92 00 f4 f7 10 00 |................| 00000010 01 b0 20 03 00 ff 0a 01 a2 01 c8 92 00 f4 01 c0 |.. .............| 00000020 03 00 ff 0a 02 d0 72 01 0a 03 c8 92 00 f4 05 b0 |......r.........| 00000030 20 a2 02 c0 02 02 6a 03 8b 00 ff f6 06 b0 20 a2 | .....j....... .| 00000040 02 f4 ce 0a 02 c8 92 00 f6 07 6a 03 8b 00 ff f6 |..........j.....| 00000050 f2 b9 66 01 a2 02 00 01 8a 03 f6 05 b9 69 01 a2 |..f..........i..| 00000060 03 92 00 f4 ac c0 74 6f 00 62 79 00 |......to.by.| 0000006c  Test runs: > echo -e "7\n5\n6\n8\n11\n15\n16\n17\n" | ./gvm findruns.bin 5 6 8 11 15to17 > echo -e "20\n1\n2\n3\n4\n5\n6\n7\n9\n11\n13\n15\n30\n45\n50\n60\n70\n80\n90\n91\n93\n" | ./gvm findruns.bin 1to7 9to15by2 30 45 50to90by10 91 93  Manually assembled from this: 0100 e1 rud ; read length of array 0101 0a 00 sta$00             ; -> to $00 0103 10 00 ldx #$00            ; loop counter
readloop:
0105  e1        rud                     ; read unsigned number
0106  0b 00 ff  sta     $ff00,x ; store in array at ff00 0109 c8 inx ; next index 010a 92 00 cpx$00             ; length reached?
010c  f4 f7     bne     readloop        ; no -> read next number
010e  10 00     ldx     #$00 ; loop counter 0110 01 ; 'lda$20b0', to skip next instruction
runloop:
0111  b0 20     wch     #' '            ; write space character
0113  03 00 ff  lda     $ff00,x ; load next number from array 0116 0a 01 sta$01             ; -> to $01 0118 a2 01 wud$01             ; and output
011a  c8        inx                     ; next index
011b  92 00     cpx     $00 ; length reached? 011d f4 01 bne compare ; if not calculate difference 011f c0 hlt ; done compare: 0120 03 00 ff lda$ff00,x         ; load next number from array
0123  0a 02     sta     $02 ; -> to$01
0125  d0        sec                     ; calculate ...
0126  72 01     sbc     $01 ; ... difference ... 0128 0a 03 sta$03             ; ... to $03 012a c8 inx ; next index 012b 92 00 cpx$00             ; length reached?
012d  f4 05     bne     checkrun        ; if not check whether we have a run
012f  b0 20     wch     #' '            ; output space
0131  a2 02     wud     $02 ; output number 0133 c0 hlt ; done checkrun: 0134 02 02 lda$02             ; calculate next ...
0136  6a 03     adc     $03 ; ... expected number in run 0138 8b 00 ff cmp$ff00,x         ; compare with real next number
013b  f6 06     beq     haverun         ; ok -> found a run
013d  b0 20     wch     #' '            ; otherwise output space ...
013f  a2 02     wud     $02 ; ... and number 0141 f4 ce bne runloop ; and repeat searching for runs haverun: 0143 0a 02 sta$02             ; store number to $02 0145 c8 inx ; next index 0146 92 00 cpx$00             ; length reached?
0148  f6 07     beq     outputrun       ; yes -> output this run
014a  6a 03     adc     $03 ; calculate next expected number 014c 8b 00 ff cmp$ff00,x         ; compare with real next number
014f  f6 f2     beq     haverun         ; ok -> continue parsing run
outputrun:
0151  b9 66 01  wtx     str_to          ; write "to"
0154  a2 02     wud     $02 ; write end number of run 0156 00 01 lda #$01            ; compare #1 with ...
0158  8a 03     cmp     $03 ; ... step size 015a f6 05 beq skip_by ; equal, then skip output of "by" 015c b9 69 01 wtx str_by ; output "by" 015f a2 03 wud$03             ; output step size
skip_by:
0161  92 00     cpx     $00 ; length of array reached? 0163 f4 ac bne runloop ; no -> repeat searching for runs 0165 c0 hlt ; done str_to: 0166 74 6f 00 ; "to" str_by: 0169 62 79 00 ; "by" 016c  # 05AB1E (legacy), 49 50 bytes .œʒε¥Ë}P}Σ€g2KO>}¤εD©g≠i¬s¤„toý¬®¥0èDU≠i„byX««]˜ðý  Way too long, but I'm already glad it's working. This challenge is a lot harder than it looks imo.. Can without a doubt be golfed further. Σ€g2KO>}¤ is a port of 2,0ySƲÞṪ from @JonathanAllan's Jelly answer (thanks!). Try it online. (NOTE: Times out for the big test cases.) +1 byte as bug-fix because 0 is always put at a trailing position when sorting. Explanation: .œ # Get all partions of the (implicit) input-list # i.e. [1,2,3,11,18,20,22,24,32,33,34] # → [[[1],[2],[3],[11],[18],[20],[22],[24],[32],[33],[34]], # [[1],[2],[3],[11],[18],[20],[22],[24],[32],[33,34]], # [[1],[2],[3],[11],[18],[20],[22],[24],[32,33],[34]], # ...] ʒ } # Filter this list by: ε } # Map the current sub-list by: ¥Ë # Take the deltas, and check if all are equal # i.e. [1,2,3] → [1,1] → 1 # i.e. [1,2,3,11] → [1,1,8] → 0 P # Check if all sub-list have equal deltas Σ } # Now that we've filtered the list, sort it by: €g # Take the length of each sub-list # i.e. [[1,2,3],[11,18],[20,22,24],[32,33],[34]] # → [3,2,3,2,1] # i.e. [[1,2,3],[11],[18,20,22,24],[32,33,34]] # → [3,1,4,3] 2K # Remove all 2s # i.e. [3,2,3,2,1] → ['3','3','1'] O # And take the sum # i.e. ['3','3','1'] → 7 # i.e. [3,1,4,3] → 11 > # And increase the sum by 1 (0 is always trailing when sorting) ¤ # And then take the last item of this sorted list # i.e. for input [1,2,3,11,18,20,22,24,32,33,34] # → [[1,2,3],[11],[18,20,22,24],[32,33,34]] ε # Now map each of the sub-lists to: D© # Save the current sub-list in the register g≠i # If its length is not 1: # i.e. [11] → 1 → 0 (falsey) # i.e. [18,20,22,24] → 4 → 1 (truthy) ¬s¤ # Take the head and tail of the sub-list # i.e. [18,20,22,24] → 18 and 24 „toý # And join them with "to" # i.e. 18 and 24 → ['18to24', '18to20to22to24'] ¬ # (head to remove some access waste we no longer need) # i.e. ['18to24', '18to20to22to24'] → '18to24' ® # Get the sub-list from the register again ¥ # Take its deltas # i.e. [18,20,22,24] → [2,2,2] 0è # Get the first item (should all be the same delta) # i.e. [2,2,2] → 2 DU # Save it in variable X ≠i # If the delta is not 1: # i.e. 2 → 1 (truthy) „byX« # Merge "by" with X # i.e. 2 → 'by2' « # And merge it with the earlier "#to#" # i.e. '18to24' and 'by2' → '18to24by2' ] # Close the mapping and both if-statements ˜ # Flatten the list # i.e. ['1to3',[11],'18to24by2','32to34'] # → ['1to3',11,'18to24by2','32to34'] ðý # And join by spaces (which we implicitly output as result) # i.e. ['1to3',11,'18to24by2','32to34'] # → '1to3 11 18to24by2 32to34'  # Perl 5, 154 bytes {my(@r,$r);@r&&(@$r<2||$$r[1]-$$r[0]==$_-$$r[-1])?push@r,_:push@r,r=[_]for@_;join" ",map@_<3?@_:("$$_[0]to$$_[-1]by".($$_[1]-$$_[0]))=~s/by1//r,@r}  Same with spaces, newlines, #comments and sub by: sub by { my(@r,r); @r && # if at least one run candidate exists and... ( @r<2 # ...just one elem so far ||$$r[1]-$$r[0] == _-$$r[-1] ) # ...or diff is same
? push @$r,$_                    # then add elem to curr. run candidate
: push @r, $r=[$_]                # else start new run cand. with curr elem
for @_;
join " ",
map @$_<3 # is it a run? ? @$_                                             # no, just output the numbers
: ("$$_[0]to$$_[-1]by".($$_[1]-$$_[0]))=~s/by1$//r, # yes, make run, delete by1 @r # loop run candidates }  Try it online! ...for passing tests from OP. # Retina 0.8.2, 77 bytes \d+$*
(1+)(?= \1(1+))
$1:$2
1:(1+) (1+:\1 )+(1+)
1to$3by$1
:1+|by1\b

1+
$.&  Try it online! Link includes test cases. Explanation: \d+$*


Convert to unary.

(1+)(?= \1(1+))
$1:$2


Compute consecutive differences.

1:(1+) (1+:\1 )+(1+)
1to$3by$1


Convert runs to to...by syntax.

:1+|by1\b


Remove unconverted differences and by1.

1+
\$.&


Convert to decimal.