Find Array Runs

Question

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

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 code-golf so least number of bytes wins.

Answer 1

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!

Answer 2

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

Answer 3

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!

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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!

Answer 8

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!

Answer 9

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!

Answer 10

Jelly, 41 bytes

ŒṖIE€Ạ$>Ẉ2eƊƲƇṪµ.ịṚj⁾to;IḢ⁾by;ẋ⁻1$ƲƊµḊ¡€K

Try it online!

Full program.

Answer 11

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!

Answer 12

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!

Answer 13

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

Answer 14

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'

Answer 15

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.

Answer 16

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.