12
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Is it okay to return true instead of 1? And do we have to handle an empty list? \$\endgroup\$
    – Jo King
    Oct 8, 2018 at 5:28
  • \$\begingroup\$ For your first one, whatever meta consensus is on numeral output you may do, I don't recall True being a substitute for 1 but it may be. You should be able to handle the empty list (Output is of course 0). \$\endgroup\$
    – Wheat Wizard
    Oct 8, 2018 at 7:12
  • 2
    \$\begingroup\$ Suggested test cases: [] => 0, [0] => 1, [3,2,1] => 1, [1,2,1,2] => 2 \$\endgroup\$
    – Sok
    Oct 8, 2018 at 8:22
  • \$\begingroup\$ Would you mind elaborating on the 'score' a bit more? \$\endgroup\$
    – ouflak
    Oct 8, 2018 at 9:58
  • 1
    \$\begingroup\$ @ouflak I'm not sure what more there is to say on the score. Convert your submission to a list of bytes and pass it through your own program and that's your score. If scores are equal, the tie-breaker is the bytecount \$\endgroup\$
    – Jo King
    Oct 8, 2018 at 10:19

21 Answers 21

6
\$\begingroup\$

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.
\$\endgroup\$
0
5
\$\begingroup\$

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).

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Looks like the whitespace in 1+a : b is not necessary, so this is 62 bytes. \$\endgroup\$ Oct 8, 2018 at 10:08
  • \$\begingroup\$ @MaxYekhlakov You're right, I don't know how I missed that. \$\endgroup\$
    – Delfad0r
    Oct 8, 2018 at 11:42
  • \$\begingroup\$ Your code returns 1 for the empty list, where it should return 0 \$\endgroup\$
    – Jo King
    Oct 10, 2018 at 7:52
  • \$\begingroup\$ @Jo King Indeed, I had missed the discussion in the comments. Fixing that right now. \$\endgroup\$
    – Delfad0r
    Oct 10, 2018 at 8:12
5
\$\begingroup\$

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>[ ]&&$
\$\endgroup\$
2
  • \$\begingroup\$ This should work for 46 bytes and the same score. \$\endgroup\$
    – Arnauld
    Oct 7, 2018 at 16:18
  • 1
    \$\begingroup\$ @Arnauld added 5 spaces to your suggestion so that it's now a score 2 \$\endgroup\$ Oct 8, 2018 at 0:00
4
\$\begingroup\$

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 ġ1 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
\$\endgroup\$
3
\$\begingroup\$

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.

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

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

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

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
\$\endgroup\$
3
  • \$\begingroup\$ So [[&(*+*)]] works like [+]? Amazing... \$\endgroup\$
    – nwellnhof
    Oct 8, 2018 at 11:41
  • \$\begingroup\$ @nwellnhof Yeah, there's a few caveats like you can't have any whitespace (at all), but you can even use it with Z and X. Try it online! \$\endgroup\$
    – Jo King
    Oct 8, 2018 at 12:02
  • 1
    \$\begingroup\$ I was going to try something like: {max 0,|.[[X..] ^$_ xx 2].map({+$_ if [<=] $_})} \$\endgroup\$ Oct 19, 2018 at 18:40
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ I was going to suggest possibly using \u in some places, but then you have to have 00 followed by a digit which is 3 anyway... \$\endgroup\$ Oct 8, 2018 at 18:32
1
\$\begingroup\$

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

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

Stax, score 3 (15 bytes)

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

Run and debug it

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

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...

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Score of 5. Try it online! \$\endgroup\$
    – mypetlion
    Oct 9, 2018 at 20:55
  • 2
    \$\begingroup\$ Indent with tabs to get a score of 4. \$\endgroup\$
    – mypetlion
    Oct 9, 2018 at 21:15
  • \$\begingroup\$ @mypetition: D'oh! Thought this was code golf... editing my answer now. \$\endgroup\$
    – Chas Brown
    Oct 10, 2018 at 1:31
  • \$\begingroup\$ Funny that removing the m=1,o=[1] part doesn't end up saving any bytes once we reduce the score \$\endgroup\$
    – Jo King
    Oct 10, 2018 at 3:39
  • \$\begingroup\$ @Jo King: Chuckle! I kept hoping that by squirming in that way, I could chip off another byte; but no such luck! \$\endgroup\$
    – Chas Brown
    Oct 10, 2018 at 4:30
1
\$\begingroup\$

Dyalog APL, score 2, 20 bytes

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

Try it online!

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ The correct way to use patterns would have us do Max[Length/@SequenceCases[#,_?OrderedQ]]&, but _?Or is an increasing subsequence of length 4. (As is _?AnyCamelCaseCommand.) \$\endgroup\$ Oct 7, 2018 at 17:10
0
\$\begingroup\$

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]
\$\endgroup\$
3
  • \$\begingroup\$ Shouldn't byte be int, since byte would be restricted to 8 bits? \$\endgroup\$
    – Jo King
    Oct 8, 2018 at 10:17
  • \$\begingroup\$ @JoKing I am not exactly sure what you mean. Do you mean that I should change the byte class to int class? \$\endgroup\$
    – Jaden Lee
    Oct 10, 2018 at 2:29
  • \$\begingroup\$ Yes, since the input is a list of integers \$\endgroup\$
    – Jo King
    Oct 10, 2018 at 2:47
0
\$\begingroup\$

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.
\$\endgroup\$
5
  • \$\begingroup\$ Ok, i got it, i will edit it shortly. \$\endgroup\$ Oct 8, 2018 at 5:44
  • \$\begingroup\$ Please check, i have made a function in which input can be given. As per my sample string answer would be [2,4,5,6,7,7,7] Score is 7. \$\endgroup\$ Oct 8, 2018 at 5:54
  • \$\begingroup\$ I have updated score and link please check. \$\endgroup\$ Oct 8, 2018 at 6:12
  • \$\begingroup\$ Ok, I gave updated. \$\endgroup\$ Oct 8, 2018 at 6:39
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – Jo King
    Oct 8, 2018 at 6:49
0
\$\begingroup\$

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
\$\endgroup\$
0
0
\$\begingroup\$

Ruby, 64 bytes

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

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Note that this is not code-golf. Your current score is 6. Also, your code does not handle the empty list (where the output should be 0) \$\endgroup\$
    – Jo King
    Oct 10, 2018 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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