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\$
  • \$\begingroup\$ Is it okay to return true instead of 1? And do we have to handle an empty list? \$\endgroup\$ – Jo King Oct 8 '18 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\$ – Sriotchilism O'Zaic Oct 8 '18 at 7:12
  • 2
    \$\begingroup\$ Suggested test cases: [] => 0, [0] => 1, [3,2,1] => 1, [1,2,1,2] => 2 \$\endgroup\$ – Sok Oct 8 '18 at 8:22
  • \$\begingroup\$ Would you mind elaborating on the 'score' a bit more? \$\endgroup\$ – ouflak Oct 8 '18 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 '18 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\$
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\$
  • 1
    \$\begingroup\$ Looks like the whitespace in 1+a : b is not necessary, so this is 62 bytes. \$\endgroup\$ – Max Yekhlakov Oct 8 '18 at 10:08
  • \$\begingroup\$ @MaxYekhlakov You're right, I don't know how I missed that. \$\endgroup\$ – Delfad0r Oct 8 '18 at 11:42
  • \$\begingroup\$ Your code returns 1 for the empty list, where it should return 0 \$\endgroup\$ – Jo King Oct 10 '18 at 7:52
  • \$\begingroup\$ @Jo King Indeed, I had missed the discussion in the comments. Fixing that right now. \$\endgroup\$ – Delfad0r Oct 10 '18 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\$
  • \$\begingroup\$ This should work for 46 bytes and the same score. \$\endgroup\$ – Arnauld Oct 7 '18 at 16:18
  • 1
    \$\begingroup\$ @Arnauld added 5 spaces to your suggestion so that it's now a score 2 \$\endgroup\$ – Shieru Asakoto Oct 8 '18 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\$
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\$
2
\$\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\$
  • \$\begingroup\$ So [[&(*+*)]] works like [+]? Amazing... \$\endgroup\$ – nwellnhof Oct 8 '18 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 '18 at 12:02
  • 1
    \$\begingroup\$ I was going to try something like: {max 0,|.[[X..] ^$_ xx 2].map({+$_ if [<=] $_})} \$\endgroup\$ – Brad Gilbert b2gills Oct 19 '18 at 18:40
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\$
  • \$\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\$ – ETHproductions Oct 8 '18 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\$
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\$
  • 2
    \$\begingroup\$ Score of 5. Try it online! \$\endgroup\$ – mypetlion Oct 9 '18 at 20:55
  • 2
    \$\begingroup\$ Indent with tabs to get a score of 4. \$\endgroup\$ – mypetlion Oct 9 '18 at 21:15
  • \$\begingroup\$ @mypetition: D'oh! Thought this was code golf... editing my answer now. \$\endgroup\$ – Chas Brown Oct 10 '18 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 '18 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 '18 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\$
  • \$\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\$ – Misha Lavrov Oct 7 '18 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\$
  • \$\begingroup\$ Shouldn't byte be int, since byte would be restricted to 8 bits? \$\endgroup\$ – Jo King Oct 8 '18 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 '18 at 2:29
  • \$\begingroup\$ Yes, since the input is a list of integers \$\endgroup\$ – Jo King Oct 10 '18 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\$
  • \$\begingroup\$ Ok, i got it, i will edit it shortly. \$\endgroup\$ – Syed Hamza Hassan Oct 8 '18 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\$ – Syed Hamza Hassan Oct 8 '18 at 5:54
  • \$\begingroup\$ I have updated score and link please check. \$\endgroup\$ – Syed Hamza Hassan Oct 8 '18 at 6:12
  • \$\begingroup\$ Ok, I gave updated. \$\endgroup\$ – Syed Hamza Hassan Oct 8 '18 at 6:39
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – Jo King Oct 8 '18 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
\$\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
    \$\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 '18 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.