Mixing
A “Sorting†algorithm
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
There is a "sorting algorithm" sometimes called Stalin sort in which in order to sort a list you simply remove elements from the list until it is sorted in increasing order. For example the list
[1, 2, 4, 5, 3, 6, 6]
When "sorted" using Stalin sort becomes
[1, 2, 4, 5, 6, 6]
The three was removed because it was out of order.
Now obviously there are many ways to remove elements to sort a list. For example any list with less than two elements must be sorted so by just removing enough elements blindly we can always sort a list. Since this is the case we only care about the longest possible result from a Stalin sort.
Your task will be to take a list of positive integers and output the length of the longest sorted (increasing) list that can be arrived at by removing elements from the original list. That is find the length of the longest sorted (possibly non-contiguous) sub-list.
Sorted lists can have the same element more than once in a row. You do not need to support the empty list unless your program itself is empty.
Scoring
Your answer will be scored by the length of its own longest possible Stalin sort. Programs will be interpreted as a sequence of bytes rather than characters, and their order will be the natural one that arises by interpreting the bytes as numbers. Lower scores are better.
This is not code-golf
Test cases
[1, 2, 4, 5, 3, 6, 6] -> 6
[19, 2] -> 1
[3, 3, 4, 3] -> 3
[10] -> 1
[1, 2, 4, 9] -> 4
[1, 90, 2, 3, 4, 5] -> 5
[1, 90, 91, 2, 3, 4, 5] -> 5
code-challenge sorting
asked 1 hour ago
Post Left Ghost Hunter
34.2k10150359
 |Â
show 1 more comment
up vote
6
down vote
favorite
There is a "sorting algorithm" sometimes called Stalin sort in which in order to sort a list you simply remove elements from the list until it is sorted in increasing order. For example the list
[1, 2, 4, 5, 3, 6, 6]
When "sorted" using Stalin sort becomes
[1, 2, 4, 5, 6, 6]
The three was removed because it was out of order.
Now obviously there are many ways to remove elements to sort a list. For example any list with less than two elements must be sorted so by just removing enough elements blindly we can always sort a list. Since this is the case we only care about the longest possible result from a Stalin sort.
Your task will be to take a list of positive integers and output the length of the longest sorted (increasing) list that can be arrived at by removing elements from the original list. That is find the length of the longest sorted (possibly non-contiguous) sub-list.
Sorted lists can have the same element more than once in a row. You do not need to support the empty list unless your program itself is empty.
Scoring
Your answer will be scored by the length of its own longest possible Stalin sort. Programs will be interpreted as a sequence of bytes rather than characters, and their order will be the natural one that arises by interpreting the bytes as numbers. Lower scores are better.
This is not code-golf
Test cases
[1, 2, 4, 5, 3, 6, 6] -> 6
[19, 2] -> 1
[3, 3, 4, 3] -> 3
[10] -> 1
[1, 2, 4, 9] -> 4
[1, 90, 2, 3, 4, 5] -> 5
[1, 90, 91, 2, 3, 4, 5] -> 5
code-challenge sorting
asked 1 hour ago
Post Left Ghost Hunter
34.2k10150359
1
In short: output the length of the longest (non-strictly) increasing sequence.
– user202729
1 hour ago
I suggest adding a scorer to the post.
– user202729
1 hour ago
Any tiebreak condition?
– Zacharý
52 mins ago
@Zacharý No, I think.
– user202729
48 mins ago
@Zacharý The default tiebreaker is submission time.
– Dennis♦
47 mins ago
 |Â
show 1 more comment
up vote
6
down vote
favorite
up vote
6
down vote
favorite
There is a "sorting algorithm" sometimes called Stalin sort in which in order to sort a list you simply remove elements from the list until it is sorted in increasing order. For example the list
[1, 2, 4, 5, 3, 6, 6]
When "sorted" using Stalin sort becomes
[1, 2, 4, 5, 6, 6]
The three was removed because it was out of order.
Now obviously there are many ways to remove elements to sort a list. For example any list with less than two elements must be sorted so by just removing enough elements blindly we can always sort a list. Since this is the case we only care about the longest possible result from a Stalin sort.
Your task will be to take a list of positive integers and output the length of the longest sorted (increasing) list that can be arrived at by removing elements from the original list. That is find the length of the longest sorted (possibly non-contiguous) sub-list.
Sorted lists can have the same element more than once in a row. You do not need to support the empty list unless your program itself is empty.
Scoring
Your answer will be scored by the length of its own longest possible Stalin sort. Programs will be interpreted as a sequence of bytes rather than characters, and their order will be the natural one that arises by interpreting the bytes as numbers. Lower scores are better.
This is not code-golf
Test cases
[1, 2, 4, 5, 3, 6, 6] -> 6
[19, 2] -> 1
[3, 3, 4, 3] -> 3
[10] -> 1
[1, 2, 4, 9] -> 4
[1, 90, 2, 3, 4, 5] -> 5
[1, 90, 91, 2, 3, 4, 5] -> 5
code-challenge sorting
asked 1 hour ago
Post Left Ghost Hunter
34.2k10150359
There is a "sorting algorithm" sometimes called Stalin sort in which in order to sort a list you simply remove elements from the list until it is sorted in increasing order. For example the list
[1, 2, 4, 5, 3, 6, 6]
When "sorted" using Stalin sort becomes
[1, 2, 4, 5, 6, 6]
The three was removed because it was out of order.
Now obviously there are many ways to remove elements to sort a list. For example any list with less than two elements must be sorted so by just removing enough elements blindly we can always sort a list. Since this is the case we only care about the longest possible result from a Stalin sort.
Your task will be to take a list of positive integers and output the length of the longest sorted (increasing) list that can be arrived at by removing elements from the original list. That is find the length of the longest sorted (possibly non-contiguous) sub-list.
Sorted lists can have the same element more than once in a row. You do not need to support the empty list unless your program itself is empty.
Scoring
Your answer will be scored by the length of its own longest possible Stalin sort. Programs will be interpreted as a sequence of bytes rather than characters, and their order will be the natural one that arises by interpreting the bytes as numbers. Lower scores are better.
This is not code-golf
Test cases
[1, 2, 4, 5, 3, 6, 6] -> 6
[19, 2] -> 1
[3, 3, 4, 3] -> 3
[10] -> 1
[1, 2, 4, 9] -> 4
[1, 90, 2, 3, 4, 5] -> 5
[1, 90, 91, 2, 3, 4, 5] -> 5
code-challenge sorting
code-challenge sorting
asked 1 hour ago
Post Left Ghost Hunter
34.2k10150359
asked 1 hour ago
Post Left Ghost Hunter
34.2k10150359
edited 1 hour ago
asked 1 hour ago
Post Left Ghost Hunter
34.2k10150359
asked 1 hour ago
Post Left Ghost Hunter
34.2k10150359
asked 1 hour ago
Post Left Ghost Hunter
34.2k10150359
34.2k10150359
1
In short: output the length of the longest (non-strictly) increasing sequence.
– user202729
1 hour ago
I suggest adding a scorer to the post.
– user202729
1 hour ago
Any tiebreak condition?
– Zacharý
52 mins ago
@Zacharý No, I think.
– user202729
48 mins ago
@Zacharý The default tiebreaker is submission time.
– Dennis♦
47 mins ago
 |Â
show 1 more comment
1
In short: output the length of the longest (non-strictly) increasing sequence.
– user202729
1 hour ago
I suggest adding a scorer to the post.
– user202729
1 hour ago
Any tiebreak condition?
– Zacharý
52 mins ago
@Zacharý No, I think.
– user202729
48 mins ago
@Zacharý The default tiebreaker is submission time.
– Dennis♦
47 mins ago
1
1
In short: output the length of the longest (non-strictly) increasing sequence.
– user202729
1 hour ago
In short: output the length of the longest (non-strictly) increasing sequence.
– user202729
1 hour ago
I suggest adding a scorer to the post.
– user202729
1 hour ago
I suggest adding a scorer to the post.
– user202729
1 hour ago
Any tiebreak condition?
– Zacharý
52 mins ago
Any tiebreak condition?
– Zacharý
52 mins ago
@Zacharý No, I think.
– user202729
48 mins ago
@Zacharý No, I think.
– user202729
48 mins ago
@Zacharý The default tiebreaker is submission time.
– Dennis♦
47 mins ago
@Zacharý The default tiebreaker is submission time.
– Dennis♦
47 mins ago
 |Â
show 1 more comment
5 Answers
5
active
oldest
votes
up vote
1
down vote
Stax, 4 maximal length stalin sort
SM
Run and debug it
It works like this.
S powerset of input
Â
up vote
1
down vote
Python 2, 132 bytes, score 6
If I understand scoring right, I used ord() to convert code characters. Result is surprisingly low.
I=input()
S=2**len(I)
r=
for i in range(S):
l=[c for b,c in zip(bin(i+S)[3:],I)if'1'==b]
if sorted(l)==l:r+=len(l),
print max(r)
Try it online!
answered 1 hour ago
Dennis♦
183k32293725
add a comment |Â
up vote
1
down vote
Haskell, Score 8, 51 bytes
(e:d)%f|f>e=d%f|y<-d=(1+y%e)`max`(d%f)
c%b=0
a=(%0)
Try it online!
The longest sorted sublist is
%%()``df
answered 41 mins ago
Post Left Ghost Hunter
34.2k10150359
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Stax, 4 maximal length stalin sort
S:^fF%Ã…Â’P Main link. Argument: A (array)
Ã…Â’P Powerset; yield P, the array of all sub-arrays of A.
Ʋ Vier; combine the preceding four links into a monadic chain...
} and apply the chain to the right argument (P).
Ƈ Comb; only keep arrays for which the link to the left returns 1.
ṢƑ Sort fixed; yield 1 if sorting doesn't alter the array.
Z Zip; read the filtered powerset by columns.
L Take the length.
answered 1 hour ago
Dennis♦
183k32293725
Jelly, length  4 2
ṢƑƇZLƲ}ŒP
Try it online!
Bytes in Jelly's code page
183 146 144 90 76 169 125 19 80
How it works
ṢƑƇZLƲ}ŒP Main link. Argument: A (array)
Ã…Â’P Powerset; yield P, the array of all sub-arrays of A.
Ʋ Vier; combine the preceding four links into a monadic chain...
} and apply the chain to the right argument (P).
Ƈ Comb; only keep arrays for which the link to the left returns 1.
ṢƑ Sort fixed; yield 1 if sorting doesn't alter the array.
Z Zip; read the filtered powerset by columns.
L Take the length.
answered 1 hour ago
Dennis♦
183k32293725
edited 43 mins ago
answered 1 hour ago
Dennis♦
183k32293725
answered 1 hour ago
Dennis♦
183k32293725
answered 1 hour ago
Dennis♦
183k32293725
183k32293725
add a comment |Â
add a comment |Â
up vote
1
down vote
Haskell, Score 8, 51 bytes
(e:d)%f|f>e=d%f|y<-d=(1+y%e)`max`(d%f)
c%b=0
a=(%0)
Try it online!
The longest sorted sublist is
%%()``df
answered 41 mins ago
Post Left Ghost Hunter
34.2k10150359
add a comment |Â
up vote
1
down vote
Haskell, Score 8, 51 bytes
(e:d)%f|f>e=d%f|y<-d=(1+y%e)`max`(d%f)
c%b=0
a=(%0)
Try it online!
The longest sorted sublist is
%%()``df
answered 41 mins ago
Post Left Ghost Hunter
34.2k10150359
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Haskell, Score 8, 51 bytes
(e:d)%f|f>e=d%f|y<-d=(1+y%e)`max`(d%f)
c%b=0
a=(%0)
Try it online!
The longest sorted sublist is
%%()``df
answered 41 mins ago
Post Left Ghost Hunter
34.2k10150359
Haskell, Score 8, 51 bytes
(e:d)%f|f>e=d%f|y<-d=(1+y%e)`max`(d%f)
c%b=0
a=(%0)
Try it online!
The longest sorted sublist is
%%()``df
answered 41 mins ago
Post Left Ghost Hunter
34.2k10150359
answered 41 mins ago
Post Left Ghost Hunter
34.2k10150359
answered 41 mins ago
Post Left Ghost Hunter
34.2k10150359
answered 41 mins ago
Post Left Ghost Hunter
34.2k10150359
34.2k10150359
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f174964%2fa-sorting-algorithm%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
In short: output the length of the longest (non-strictly) increasing sequence.
– user202729
1 hour ago
I suggest adding a scorer to the post.
– user202729
1 hour ago
Any tiebreak condition?
– Zacharý
52 mins ago
@Zacharý No, I think.
– user202729
48 mins ago
@Zacharý The default tiebreaker is submission time.
– Dennis♦
47 mins ago