Longest Increasing Substring

Question

Given a list of positive integers, write code that finds the length of longest contiguous sub-list that is increasing (not strictly). That is the longest sublist such that each element is greater than or equal to the last.

For example if the input was:

\$[1,1,2,1,1,4,5,3,2,1,1]\$

The longest increasing sub-list would be \$[1,1,4,5]\$, so you would output \$4\$.

Your answer will be scored by taking its source as a list of bytes and then finding the length of the longest increasing sub-list of that list. A lower score is the goal. Ties are broken in favor of programs with fewer overall bytes.

Answer 1

Pyth, score 2 (8 bytes)

lefSIT.:

Try it here!

Code points [108, 101, 102, 83, 73, 84, 46, 58]. Another shorter solution, leSI#.: scores 3, but its code points are [108, 101, 83, 73, 35, 46, 58], which are very close to a score of 1, actually. Rearranging a bit may help Nevermind, the substrings built-in is .: which cannot be rearranged, so the lowest score must be 2 if the program makes use of it.

How?

lefSIT.:     Full program. Accepts either a list or a string from STDIN.
      .:     Substrings.
  f  T       Only keep those that are...
   SI        Sorting-Invariant.
le           Length of the last item.

Answer 2

JavaScript (Node.js), score 3, 53 46 bytes score 2, 51 50 bytes

-7 bytes thanks @Arnauld

+5 +4 spaces in exchange of -1 score

a=> a.map($= p=n=>$=(p<=(p=n)?++ x:x=1)<$?$: x)&&$

Try it online!

Assumes non-empty input. 61 bytes if empty list must be handled. Score 2 still.

a=> a.map($= p=n=>$=(p<=(p=n)?++ x:x=1)<$?$: x)&& a.length&&$

Try it online!

...or 58 if returning false is allowed. Score 2 still.

a=> a.map($= p=n=>$=(p<=(p=n)?++ x:x=1)<$?$: x)&& a>[ ]&&$

Answer 3

Haskell, score 2, 66 64 61 60 65 bytes

• -2 bytes thanks to Max Yekhlakov
• -1 byte thanks to nimi
• +5 bytes to handle the empty list

foldr1 max.g
g[]=[0]
g(x:y:z)|x>y=1: g(y:z)
g(_:y)|a:b<-g y=1+a:b

Try it online! (verifies itself).

I never thought I could get a score of 2 with Haskell, and yet here I am!

Function g computes the lengths of all the increasing substrings recursively. foldr1 max.g takes the maximum of those lengths (foldr1 max is equivalent to maximum, but with a lower score).

Answer 4

Husk, 5 bytes, score = 2

00000000: bc6d 4cdc 14                   ▲mLġ≥

Try it online!

It's unlikely to get a score lower than 2 with Husk because ġ¹ has a really high codepoint and there needs to be something before it to get the maximum and length. An attempt could be made with trying to use multiple functions but \n would be before any helper functions which has a really low codepoint so anything after it would create an increasing byte-sequence of at least length 2.

_{1: This seems like the best way to use for the comparison operators would need to follow the various split functions like ↕ (span).}

Explanation

▲mLġ≥  -- example input: [1,1,2,1,1,4,5,3,2,1,1]
   ġ≥  -- group elements by geq: [[1,1,2],[1,1,4,5],[3],[2],[1,1]]
 mL    -- map length: [3,4,1,1,2]
▲      -- maximum: 4

Answer 5

MATL, score 2, 13 bytes

d0< ~Y'w)X>sQ

Input can be:

• An array of numbers.
• A string enclosed with single quotes. Single quotes within the string are escaped by duplicating.

MATL uses ASCII encoding. The codepoints of the above code are

100, 48, 60, 32, 126, 89, 39, 119, 41, 88, 62, 115, 81

Try it online!

Explanation

d     % Implicit input. Consecutive differences (of code points) 
0<    % Less than 0? Element-wise. Gives true or false
      % Space. This does nothing; but it breaks an increasing substring
~     % Negate
Y'    % Run-length encoding. Gives array of true/false and array of lengths
w     % Swap
)     % Index. This keeps only lenghts of runs of true values
X>    % Maximum. Gives empty array if input is empty
s     % Sum. This turns empty array into 0
Q     % Add 1. Implicit display

Answer 6

Retina 0.8.2, 40 bytes, score 3

\d+
$*
(?<=(1+)),(?!\1)
¶
T`1`_
^O`
\G,?

Try it online! Link includes itself as byte codes as input. Explanation:

\d+
$*

Convert to unary.

(?<=(1+)),(?!\1)
¶

Split on decreasing pairs.

T`1`_

Delete the digits.

^O`

Sort the commas in reverse order. (I would normally write this as O^ but can't do that here for obvious reasons.)

\G,?

Count the longest comma run, and add one to include the final number.

Answer 7

Japt -h, 6 bytes, score 2

Don't think a score of 1 is possible. Should work with strings & character arrays too.

ò>¹mÊn

Try it - included test case is the charcodes of the solution.

---

Explanation

ò          :Partition after each integer
 >         :  That's greater than the integer that follows it
  ¹        :End partition
   m       :Map
    Ê      :  Length
     n     :Sort
           :Implicitly output last element

Answer 8

Pascal (FPC), score 2

111 bytes

var a,b,c,t:bYte;bEgIn repeat read(a); iNc(c); if a<b then c:=1; if c>t then t:= c;b:= a;until eOf;write(t)eNd.

Try it online!

Assumes non-empty input. Numbers are taken from standard input separated by spaces.

Answer 9

Jelly, 8 bytes, score 2

^{There is probably a score 1 solution somehow...}

IṠµṣ-ZL‘

Try it online!

Source code as a list of byte values:

[73, 205, 9, 223, 45, 90, 76, 252]

How?

IṠµṣ-ZL‘ - Link: list of integers  e.g. [ 1, 1, 2, 1, 1, 4, 5, 3, 2, 1, 1]
I        - increments                    [ 0, 1,-1, 0, 3, 1,-2,-1,-1, 0]
 Ṡ       - sign                          [ 0, 1,-1, 0, 1, 1,-1,-1,-1, 0]
  µ      - start a new monadic chain (a low byte to stop score being 3)
    -    - literal minus one             -1
   ṣ     - split at                      [[0, 1], [0, 1, 1], [], [], [0]]
     Z   - transpose                     [[0, 0, 0], [1, 1], 1]
      L  - length                        3
       ‘ - increment                     4

Answer 10

Perl 6, score 2, 46 bytes

{my&g=1+*×*;+max 0,|[\[&g]] [ |@_] Z>=0,|@_ }

Try it online!

Handles the empty list. The original code was:

{my&g=1+*×*;+max 0,|[\[&g]] @_ Z>=0,|@_}

So only 5 extra bytes to reduce the score to 2.

Edit: Ah, I figured out how to remove the assignment, but then I can't get that score below 3 because of the )]]...

Explanation:

{                                  }  # Anonymous code block
 my&g=     ;  # Assign to &g an anonymous Whatever lambda
      1+*×*   # That multiplies the two inputs together and adds 1
                            @_ Z  0,|@_   # Zip the list with itself off-set by one
                                >=        # And check if each is equal or larger than the previous
                                         # e.g. [5,7,7,1] => [1,1,1,0]
                    [\[&g]]  # Triangular reduce it by the function declared earlier
                          # This results in a list of the longest substring at each index
                          # e.g. [5,7,7,1] => [1,2,3,1]
            +max 0,|      # And return the max value from this list, returning 0 if empty

Answer 11

05AB1E, score 3 (9 bytes)

Œʒ¥dP}éθg

Can most likely be a score of 2 somehow.

Code points of the program-bytes: [140,1,90,100,80,125,233,9,103] (two sublists of length 3: [1,90,100] and [80,125,233])

Try it online.

Explanation:

Π           # Sublists
 ʒ   }       # Filter by:
  ¥          #  Take the deltas
   d         #  Check for each whether the number is >= 0
    P        #  And check if it was truthy for all deltas
      é      # Then sort by length
       θ     # Take the last element
        g    # And take its length as result

Answer 12

Powershell, score 3, 44 bytes

($args|%{$i*=$_-ge$p;$p=$_;(++$i)}|sort)[-1]

Test script:

$f = {

(
    $args|%{        # for each integer from argument list
        $i*=$_-ge$p # -ge means >=.
                    # This statement multiplies the $i by the comparison result.
                    # A result of a logical operator is 0 or 1.
                    # So, we continue to count a current sequence or start to count a new sequence
        $p=$_       # let $p stores a 'previous integer'
        (++$i)      # increment and return incremented as length of a current sequence
    }|sort          # sort lengthes 
)[-1]               # take last one (maximum)

}

@(
    ,(4, 1,1,2,1,1,4,5,3,2,1,1)
) | % {
    $e,$a = $_
    $r = &$f @a
    "$($r-eq$e): $r"
}

Output:

True: 4

Explanation:

• The script takes integers as argument list (spaltting).
• Each integer maps by a function to legnth of contiguous sub-list that is increasing (not strictly). Then the script sorts lengthes and take a last (maximum) (...|sort)[-1].

---

Powershell 6, score 3, 43 bytes

$args|%{$i*=$_-ge$p;$p=$_;(++$i)}|sort -b 1

Same as above. One difference: sort -b 1 is shortcut for sort -Bottom 1 and means 1 element from the end of sorted array. So we need not an index [-1].

Answer 13

Java (JDK), score 3, 94 bytes

a->{int m=0,p=0,x=0,i=0,n;while(i<a.length){n=a[i++];m=(p<=(p=n)?++x:(x=1)) <m?m:x;}return m;}

Try it online!

Port of my (with suggestions from Arnauld) JS answer. etu in return and hil in while make it impossible to golf to score 2.

for cannot be used here because:

• ;for is ascending
• for cannot be used at the beginning of the lambda body (scope restrictions). It is possible to wrap it with {} but apparently using while saves bytes.

Answer 14

Stax, score 3 (15 bytes)

Z|[F|]F:^!C_%|M

Run and debug it

Answer 15

Python 2, score 5, 87 bytes score 2, 101 93 92 101 bytes

lambda a,m=1,o=[1]:max(reduce(lambda B,c:[B[:-m]+[B[-m]+m],B+o][c[0]>c[m]],zip(a,a[m:]), o)) *(a>[ ])

Try it online!

Ooops! Thought this was code-golf first time through...

Answer 16

Dyalog APL, score 2, 20 bytes

{⍵≡⍬:0⋄⌈/≢¨⍵⊂⍨1,2>/⍵}

Try it online!

Answer 17

Wolfram Language (Mathematica), score 3, 45 bytes

Max[Length/@SequenceCases[#,x_/;OrderedQ@x]]&

Try it online!

SequenceCases and OrderedQ by themselves give a score of 3, so the score can't be improved without changing the approach significantly.

Answer 18

Kotlin, Score 6, 119 bytes

 fun x(a : IntArray){var m=1;var k=0;var d=1;while(k<a.size-1){if(a[k]<=a[k+1])m++;else{if(d<m)d=m;m=1};k++};println(d)}

Try Online

Explanation

1. Step 1: Check for previous value to next value
2. Step 2: If previous value is less or equal then add plus 1 keep doing while condition is true
3. Step 3: check previous count with next count, keep highest count in variable d.

Answer 19

Java (JDK), 126 bytes, Score 6

Golfed

private static int l(byte[] o){int m=0;int c=1;int p=0;for(byte i:o){if(m<c){m=c;}if(i>=p){p= i;c++;}else{c=1;p=0;}}return m;}

Ungolfed

private static int longest(byte[] input) {
    int maxc = 0;
    int consec = 1;
    int prev = 0;
    for (byte i : input) {
        if (maxc < consec) {
            maxc = consec;
        }
        if (i >= prev) {
            prev = i;
            consec++;
        }
        else {
            consec = 1;
            prev = 0;
        }
    }
    return maxc;
}

Input

[112, 114, 105, 118, 97, 116, 101, 32, 115, 116, 97, 116, 105, 99, 32, 105, 110, 116, 32, 108, 40, 98, 121, 116, 101, 91, 93, 32, 111, 41, 123, 105, 110, 116, 32, 109, 61, 48, 59, 105, 110, 116, 32, 99, 61, 49, 59, 105, 110, 116, 32, 112, 61, 48, 59, 102, 111, 114, 40, 98, 121, 116, 101, 32, 105, 58, 111, 41, 123, 105, 102, 40, 109, 60, 99, 41, 123, 109, 61, 99, 59, 125, 105, 102, 40, 105, 62, 61, 112, 41, 123, 112, 61, 32, 105, 59, 99, 43, 43, 59, 125, 101, 108, 115, 101, 123, 99, 61, 49, 59, 112, 61, 48, 59, 125, 125, 114, 101, 116, 117, 114, 110, 32, 109, 59, 125]

Answer 20

Kotlin, Score 4, 67 bytes

{a:IntArray->var i=0;var p=0;a.map{if(it<p){i=0};p=it;(++i)}.max()}

Main idea is: Transform each integer to length of contiguous sub-sequences that is increasing (not strictly). Return maximum.

• a.map{...} - for each integer in the array do
• if(it<p){i=0} - if current integer is less then a previous integer, then reset counter
• p=it - store current integer in the previous
• (++i) - increment counter and return value of the expression
• .max() - get maximun of all length

Answer 21

Ruby, 64 bytes

->e{e.size.downto(1).find{|l|e.each_cons(l).find{|c|c==c.sort}}}

Try it online!