Implement the Thanos sorting algorithm
$begingroup$
The sorting algorithm goes like this:
While the list is not sorted, snap half of all items (remove them from the list). Continue until the list is sorted or only one item remains (which is sorted by default). This sorting algorithm may give different results based on implementation.
The item removal procedure is up to the implementation to decide, but the list should be half as long as before after one pass of the item removal procedure. Your algorithm may decide to remove either the first half or the list, the last half of the list, all odd items, all even items, one at a time until the list is half as long, or any not mentioned.
The input list can contain an arbitrary amount of items (within reason, let’s say up to 1000 items), not only perfectly divisible lists of 2^n items. You will have to either remove (n+1)/2 or (n-1)/2 items if the list is odd, either hardcoded or decided randomly during runtime. Decide for yourself: what would Thanos do if the universe contained an odd amount of living things?
The list is sorted if no item is smaller than any previous item. Duplicates may occur in the input, and may occur in the output.
Your program should take in an array of integers (via stdin or as parameters, either individual items or an array parameter), and return the sorted array (or print it to stdout).
Examples:
// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half
[1, 2, 4, 3, 5] could give different results:
// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]
or:
// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed
or:
// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed
or:
// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]
code-golf sorting
asked Mar 26 at 10:21
vrwimvrwim
1,15121016
$endgroup$
|
show 11 more comments
$begingroup$
The sorting algorithm goes like this:
While the list is not sorted, snap half of all items (remove them from the list). Continue until the list is sorted or only one item remains (which is sorted by default). This sorting algorithm may give different results based on implementation.
The item removal procedure is up to the implementation to decide, but the list should be half as long as before after one pass of the item removal procedure. Your algorithm may decide to remove either the first half or the list, the last half of the list, all odd items, all even items, one at a time until the list is half as long, or any not mentioned.
The input list can contain an arbitrary amount of items (within reason, let’s say up to 1000 items), not only perfectly divisible lists of 2^n items. You will have to either remove (n+1)/2 or (n-1)/2 items if the list is odd, either hardcoded or decided randomly during runtime. Decide for yourself: what would Thanos do if the universe contained an odd amount of living things?
The list is sorted if no item is smaller than any previous item. Duplicates may occur in the input, and may occur in the output.
Your program should take in an array of integers (via stdin or as parameters, either individual items or an array parameter), and return the sorted array (or print it to stdout).
Examples:
// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half
[1, 2, 4, 3, 5] could give different results:
// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]
or:
// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed
or:
// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed
or:
// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]
code-golf sorting
asked Mar 26 at 10:21
vrwimvrwim
1,15121016
$endgroup$
14
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
Mar 26 at 14:32
9
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
Mar 26 at 14:47
10
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
Mar 26 at 14:57
5
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
Mar 26 at 18:06
7
$begingroup$
Since there is so much freedom on how to remove half the elements, this could simplify to:Return the first out of order element. If there is no out of order element, return the list.
$endgroup$
– Ben J
Mar 26 at 19:34
|
show 11 more comments
$begingroup$
The sorting algorithm goes like this:
While the list is not sorted, snap half of all items (remove them from the list). Continue until the list is sorted or only one item remains (which is sorted by default). This sorting algorithm may give different results based on implementation.
The item removal procedure is up to the implementation to decide, but the list should be half as long as before after one pass of the item removal procedure. Your algorithm may decide to remove either the first half or the list, the last half of the list, all odd items, all even items, one at a time until the list is half as long, or any not mentioned.
The input list can contain an arbitrary amount of items (within reason, let’s say up to 1000 items), not only perfectly divisible lists of 2^n items. You will have to either remove (n+1)/2 or (n-1)/2 items if the list is odd, either hardcoded or decided randomly during runtime. Decide for yourself: what would Thanos do if the universe contained an odd amount of living things?
The list is sorted if no item is smaller than any previous item. Duplicates may occur in the input, and may occur in the output.
Your program should take in an array of integers (via stdin or as parameters, either individual items or an array parameter), and return the sorted array (or print it to stdout).
Examples:
// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half
[1, 2, 4, 3, 5] could give different results:
// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]
or:
// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed
or:
// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed
or:
// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]
code-golf sorting
asked Mar 26 at 10:21
vrwimvrwim
1,15121016
$endgroup$
The sorting algorithm goes like this:
While the list is not sorted, snap half of all items (remove them from the list). Continue until the list is sorted or only one item remains (which is sorted by default). This sorting algorithm may give different results based on implementation.
The item removal procedure is up to the implementation to decide, but the list should be half as long as before after one pass of the item removal procedure. Your algorithm may decide to remove either the first half or the list, the last half of the list, all odd items, all even items, one at a time until the list is half as long, or any not mentioned.
The input list can contain an arbitrary amount of items (within reason, let’s say up to 1000 items), not only perfectly divisible lists of 2^n items. You will have to either remove (n+1)/2 or (n-1)/2 items if the list is odd, either hardcoded or decided randomly during runtime. Decide for yourself: what would Thanos do if the universe contained an odd amount of living things?
The list is sorted if no item is smaller than any previous item. Duplicates may occur in the input, and may occur in the output.
Your program should take in an array of integers (via stdin or as parameters, either individual items or an array parameter), and return the sorted array (or print it to stdout).
Examples:
// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half
[1, 2, 4, 3, 5] could give different results:
// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]
or:
// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed
or:
// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed
or:
// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]
code-golf sorting
code-golf sorting
asked Mar 26 at 10:21
vrwimvrwim
1,15121016
asked Mar 26 at 10:21
vrwimvrwim
1,15121016
edited Mar 26 at 11:54
vrwim
asked Mar 26 at 10:21
vrwimvrwim
1,15121016
asked Mar 26 at 10:21
vrwimvrwim
1,15121016
asked Mar 26 at 10:21
vrwimvrwim
1,15121016
1,15121016
14
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
Mar 26 at 14:32
9
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
Mar 26 at 14:47
10
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
Mar 26 at 14:57
5
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
Mar 26 at 18:06
7
$begingroup$
Since there is so much freedom on how to remove half the elements, this could simplify to:Return the first out of order element. If there is no out of order element, return the list.
$endgroup$
– Ben J
Mar 26 at 19:34
|
show 11 more comments
14
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
Mar 26 at 14:32
9
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
Mar 26 at 14:47
10
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
Mar 26 at 14:57
5
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
Mar 26 at 18:06
7
$begingroup$
Since there is so much freedom on how to remove half the elements, this could simplify to:Return the first out of order element. If there is no out of order element, return the list.
$endgroup$
– Ben J
Mar 26 at 19:34
14
14
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
Mar 26 at 14:32
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
Mar 26 at 14:32
9
9
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
Mar 26 at 14:47
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
Mar 26 at 14:47
10
10
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
Mar 26 at 14:57
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
Mar 26 at 14:57
5
5
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
Mar 26 at 18:06
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
Mar 26 at 18:06
7
7
$begingroup$
Since there is so much freedom on how to remove half the elements, this could simplify to:
Return the first out of order element. If there is no out of order element, return the list.$endgroup$
– Ben J
Mar 26 at 19:34
$begingroup$
Since there is so much freedom on how to remove half the elements, this could simplify to:
Return the first out of order element. If there is no out of order element, return the list.$endgroup$
– Ben J
Mar 26 at 19:34
|
show 11 more comments
27 Answers
27
active
oldest
votes
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered Mar 26 at 11:50
Kirill L.Kirill L.
5,9631527
$endgroup$
2
$begingroup$
is.unsortedrather thanany(...)would also be 41 bytes.
$endgroup$
– Giuseppe
Mar 26 at 13:14
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
Mar 26 at 13:57
add a comment |
$begingroup$
Python 3, 38 42 39 bytes
q=lambda t:t>sorted(t)and q(t[::2])or t
Try it online!
-3 bytes thanks to @JoKing and @Quuxplusone
answered Mar 26 at 10:47
Sara JSara J
505210
$endgroup$
2
$begingroup$
40 bytes
$endgroup$
– Jo King
Mar 26 at 12:16
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)must be> sorted(t).
$endgroup$
– Quuxplusone
Mar 26 at 15:47
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered Mar 26 at 13:35
TFeldTFeld
16.3k21451
$endgroup$
add a comment |
$begingroup$
Perl 6, 30 bytes
$!={[<=]($_)??$_!!.[^*/2].&$!}
Try it online!
Recursive function that removes the second half of the list until the list is sorted.
Explanation:
$!={ } # Assign the function to $!
[<=]($_)?? # If the input is sorted
$_ # Return the input
!! # Else
.[^*/2] # Take the first half of the list (rounding up)
.&$! # And apply the function again
answered Mar 26 at 12:13
Jo KingJo King
26k363129
$endgroup$
add a comment |
$begingroup$
Brachylog (v2), 6 bytes
≤₁|ḍt↰
Try it online!
This is a function submission. Input from the left, output to the right, as usual. (The TIO link uses a command-line argument that automatically wraps the function into a full program, so that you can see it in action.)
Explanation
≤₁|ḍt↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
ḍ Split the list into two halves (as evenly as possible)
t Take the last (i.e. second) half
↰ Recurse {and output the result of the recursion}
Bonus round
≤₁|⊇ᵇlᵍḍhtṛ↰
Try it online!
The snap's meant to be random, isn't it? Here's a version of the program that choses the surviving elements randomly (while ensuring that half survive at each round).
≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
⊇ᵇ Find all subsets of the input (preserving order)
lᵍ Group them by length
ḍht Find the group with median length:
t last element of
h first
ḍ half (split so that the first half is larger)
ṛ Pick a random subset from that group
↰ Recurse
This would be rather shorter if we could reorder the elements, but whyever would a sorting algorithm want to do that?
$endgroup$
9
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
Mar 26 at 20:42
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
Mar 28 at 0:44
add a comment |
$begingroup$
Java 10, 106 97 bytes
L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}
-9 bytes thanks to @OlivierGrégoire.
Try it online.
Only leave the first halve of the list every iteration, and removes $frac{n+1}{2}$ items if the list-size is odd.
Explanation:
L->{ // Method with Integer-list as both parameter and return-type
for(;; // Loop indefinitely:
L=L.subList(0,L.size()/2)){
// After every iteration: only leave halve the numbers in the list
int p=1<<31, // Previous integer, starting at -2147483648
f=1; // Flag-integer, starting at 1
for(int i:L) // Inner loop over the integer in the list:
f=p>(p=i)? // If `a>b` in a pair of integers `a,b`:
0 // Set the flag to 0
: // Else (`a<=b`):
f; // Leave the flag the same
if(f>0) // If the flag is still 1 after the loop:
return L;}} // Return the list as result
answered Mar 26 at 14:29
Kevin CruijssenKevin Cruijssen
41.9k569217
$endgroup$
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}is shorter using streams, but I haven't been able to figure out how to avoid thejava.lang.IllegalStateException: stream has already been operated upon or closederror after returning the stream
$endgroup$
– Embodiment of Ignorance
Mar 26 at 21:09
$begingroup$
@EmbodimentofIgnorance this happens becausereduceis a terminal operation that closes the stream. You won't ever be able to callreducetwice on the same stream. You can create a new stream, though.
$endgroup$
– Olivier Grégoire
Mar 27 at 15:37
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
Mar 27 at 16:05
$begingroup$
@OlivierGrégoire That order looks so simple now that I see it.. Sometimes it takes a look from another angle to see the obvious others initially miss I guess. :) Thanks!
$endgroup$
– Kevin Cruijssen
Mar 27 at 18:17
1
$begingroup$
No worries, it wasn't obvious: I worked to get there. I tested at least 10 versions before finding that one ;)
$endgroup$
– Olivier Grégoire
Mar 28 at 13:02
add a comment |
$begingroup$
C# (Visual C# Interactive Compiler), 76 bytes
g=>{while(!g.OrderBy(x=>x).SequenceEqual(g))g=g.Take(g.Count()/2);return g;}
Try it online!
answered Mar 26 at 11:40
Expired DataExpired Data
4288
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 30 bytes
#//.x_/;Sort@x!=x:>x[[;;;;2]]&
Try it online!
@Doorknob saved 12 bytes
answered Mar 26 at 14:24
J42161217J42161217
13.6k21252
$endgroup$
1
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (x[[;;;;2]]).
$endgroup$
– Doorknob♦
Mar 28 at 3:40
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
Mar 28 at 10:24
$begingroup$
thought there could be some savings by usingOrderedQ, but couldn't make it work
$endgroup$
– Greg Martin
2 days ago
$begingroup$
@GregMartin I usedOrderedQin my very first approach (see edits)
$endgroup$
– J42161217
2 days ago
add a comment |
$begingroup$
JavaScript (ES6), 49 48 bytes
Saved 1 byte thanks to @tsh
Removes every 2nd element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a
Try it online!
answered Mar 26 at 14:38
ArnauldArnauld
80k797331
$endgroup$
$begingroup$
p++&1->a^=1
$endgroup$
– tsh
2 days ago
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
7 bytes alternative by @Grimy:
ΔÐ{Ê>äн
Removes the last $frac{n}{2}$ items (or $frac{n-1}{2}$ items if the list-size is odd) every iteration.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Explanation:
[ # Start an infinite loop:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Q # Sort a copy, and check if they are equal
# # If it is: Stop the infinite loop (and output the result implicitly)
ι # Uninterweave: halve the list into two parts; first containing all even-indexed
# items, second containing all odd-indexed items (0-indexed)
# i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
н # And only leave the first part
Δ # Loop until the result no longer changes:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Ê # Sort a copy, and check if they are NOT equal (1 if truthy; 0 if falsey)
> # Increase this by 1 (so 1 if the list is sorted; 2 if it isn't sorted)
ä # Split the list in that many parts
н # And only leave the first part
# (and output the result implicitly after it no longer changes)
answered Mar 26 at 11:11
Kevin CruijssenKevin Cruijssen
41.9k569217
$endgroup$
3
$begingroup$
You can useιinstead of2äif you switch to a keep every other element strategy.
$endgroup$
– Emigna
Mar 26 at 12:07
1
$begingroup$
Alternative 7 using the "remove the last half" strategy:ΔÐ{Ê>äн
$endgroup$
– Grimy
2 days ago
$begingroup$
@Grimy That's a pretty nice approach as well. Shall I add it to my post (crediting you of course), or do you want to post it as a separated answer?
$endgroup$
– Kevin Cruijssen
2 days ago
$begingroup$
Feel free to add it.
$endgroup$
– Grimy
2 days ago
add a comment |
$begingroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered Mar 26 at 20:09
G BG B
8,1261429
$endgroup$
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
Mar 26 at 20:41
add a comment |
$begingroup$
TI-BASIC (TI-84), 47 42 45 bytes
Ans→L1:Ans→L2:SortA(L1:While not(min(L1=Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans
Input list is in Ans.
Output is in Ans and is implicitly printed out.
Explanation:
Ans→L1 ;store the input into two lists
Ans→L2
SortA(L1 ;sort the first list
; two lists are needed because "SortA(" edits the list it sorts
While not(min(L1=Ans ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list
; removes (n+1)/2 elements if list has an odd length
L2→L1 ;store the new list into the first list (updates "Ans")
SortA(L1 ;sort the first list
End
Ans ;implicitly output the list when the loop ends
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
answered Mar 26 at 16:04
TauTau
716311
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered Mar 26 at 16:44
Erik the OutgolferErik the Outgolfer
32.9k429106
$endgroup$
add a comment |
$begingroup$
Haskell, 57 55 bytes (thanks to ASCII-only)
f x|or$zipWith(>)x$tail x=f$take(div(length x)2)x|1>0=x
Try it online!
Original Code:
f x|or$zipWith(>)x(tail x)=f(take(div(length x)2)x)|1>0=x
Try it online!
Ungolfed:
f xs | sorted xs = f (halve xs)
| otherwise = xs
sorted xs = or (zipWith (>) xs (tail xs))
halve xs = take (length xs `div` 2) xs
answered Mar 28 at 4:35
SacheraSachera
512
New contributor
Sachera is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Rɪᴋᴇʀ
Mar 28 at 5:20
$begingroup$
56
$endgroup$
– ASCII-only
Mar 28 at 5:38
$begingroup$
57 :(
$endgroup$
– ASCII-only
Mar 28 at 5:44
$begingroup$
55
$endgroup$
– ASCII-only
Mar 28 at 5:55
add a comment |
$begingroup$
MATL, 11 bytes
tv`1L)ttS-a
Try it online!
This works by removing every second item.
Explanation
t % Take a row vector as input (implicit). Duplicate
v % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
` % Do...while
1L) % Keep only odd-indexed entries (1-based, linear indexing)
t % Duplicate. This will leave a copy for the next iteration
tS % Duplicate, sort
-a % True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack
answered Mar 26 at 11:30
Luis MendoLuis Mendo
75.1k888291
$endgroup$
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
Mar 26 at 13:06
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
Mar 26 at 14:19
add a comment |
$begingroup$
Japt, 10 bytes
eUñ)?U:ßUë
Try it
eUñ)?U:ßUë :Implicit input of array U
e :Compare equality with
Uñ : U sorted
) :End compare
?U: :If true then return U else
ß :Run the programme again with input
Uë : Every second element of U
answered Mar 26 at 14:27
ShaggyShaggy
19.1k21768
$endgroup$
add a comment |
$begingroup$
Gaia, 9 bytes
eo₌⟪e2%⟫↻
Try it online!
There's a bit of a bug in the Gaia parser, probably because it hasn't been updated in 2 years.
I expected ₌ to add the same value to the stack, but alas, it adds a string rather than an array, which caused me no end of confusion.
Explanation:
e | eval input as a list
↻ | until
o | the list is sorted
₌ | push additional copy (as a string):
⟪e | eval as a list
2%⟫ | and take every 2nd elementanswered Mar 26 at 19:39
GiuseppeGiuseppe
17.3k31152
$endgroup$
add a comment |
$begingroup$
Java (JDK), 102 bytes
n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}
There's already a C# answer, so I decided to try my hand on a Java answer.
Try it online!
answered Mar 27 at 1:50
Embodiment of IgnoranceEmbodiment of Ignorance
2,248126
$endgroup$
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
Mar 28 at 14:35
add a comment |
$begingroup$
Husk, 6 bytes
ΩΛ<(←½
Try it online!
Explanation
ΩΛ<(←½
Ω Repeat until
Λ< all adjacent pairs are sorted (which means the list is sorted)
½ cut the list in two halves
← then keep the first half
answered Mar 27 at 5:10
LeoLeo
7,84811349
$endgroup$
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
Mar 27 at 20:11
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
Mar 27 at 22:51
$begingroup$
@MikeHoller As many other golfing languages, Husk uses a custom code page, in order to have access to more different characters: github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Leo
Mar 27 at 22:53
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
Mar 28 at 13:30
add a comment |
$begingroup$
Octave, 49 bytes
l=input('');while(~issorted(l))l=l(1:2:end);end;l
Try it online!
This was a journey where more boring is better. Note the two much more interesting entries below:
50 bytes
function l=q(l)if(~issorted(l))l=q(l(1:2:end));end
Try it online!
53 bytes
f(f=@(g)@(l){l,@()g(g)(l(1:2:end))}{2-issorted(l)}())
Try it online!
answered Mar 27 at 13:54
SanchisesSanchises
6,24712452
$endgroup$
add a comment |
$begingroup$
VDM-SL, 99 bytes
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int
A full program to run might look like this:
functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
answered Mar 26 at 12:20
Expired DataExpired Data
4288
$endgroup$
add a comment |
$begingroup$
Pyth, 10 bytes
.W!SIHhc2Z
Try it online here. This removes the second half on each iteration, rounding down. To change it to remove the first half, rounding up, change the h to e.
.W!SIHhc2ZQ Q=eval(input())
Trailing Q inferred
!SIH Condition function - input variable is H
SIH Is H invariant under sorting?
! Logical not
hc2Z Iteration function - input variable is Z
c2Z Split Z into 2 halves, breaking ties to the left
h Take the first half
.W Q With initial value Q, execute iteration function while condition function is true
answered Mar 27 at 16:07
SokSok
4,147925
$endgroup$
add a comment |
$begingroup$
Retina, 38 bytes
d+
*
/(_+),(?!1)/+`,_+(,?)
$1
_+
$.&
Try it online! Takes comma-separated numbers. Explanation:
d+
*
Convert to unary.
/(_+),(?!1)/+`
Repeat while the list is unsorted...
,_+(,?)
$1
... delete every even element.
_+
$.&
Convert to decimal.
answered Mar 26 at 15:01
NeilNeil
82.2k745178
$endgroup$
add a comment |
$begingroup$
C (gcc), 66 bytes
Snaps off the second half of the list each iteration (n/2+1 elements if the length is odd).
Try it online!
Takes input as a pointer to the start of an array of int followed by its length. Outputs by returning the new length of the array (sorts in-place).
t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}
Ungolfed version:
t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
l: // jump label, will be goto'ed after each snap
for(i = 0; i < n - 1; ) { // go through the whole array …
if(a[i] > a[++i]) { // … if two elements are in the wrong order …
n /= 2; // … snap off the second half …
goto l; // … and start over
}
}
a = n; // implicitly return the new length
}
answered Mar 27 at 15:42
O.O.BalanceO.O.Balance
1,3091418
$endgroup$
add a comment |
$begingroup$
Clojure, 65 bytes
(defn t[l](if(apply <= l)l(recur(take(/(count l)2)(shuffle l)))))
Try it online!
answered Mar 27 at 19:27
Ethan McCueEthan McCue
1212
$endgroup$
$begingroup$
45?
$endgroup$
– ASCII-only
Mar 28 at 6:36
$begingroup$
43? 42?
$endgroup$
– ASCII-only
Mar 28 at 6:42
add a comment |
$begingroup$
MATLAB, 57 bytes
Callable as f(a), where a=[1,2,3,4,5]
f=@(x)eval('while~isequal(sort(x),x);x=x(1:end/2);end;x')
Example of usage:
>> a = [1, 2, 4, 3, 5];
>> f(a)
a =
1 2
answered Mar 28 at 23:05
aaaaaaaaaaaa
3116
$endgroup$
add a comment |
$begingroup$
Zsh, 51 bytes
56 (+5) to call the function, 47 (-4) if not a function, but saved as an executable with a proper #! header (replace the recursive f call with $0).
f(){[ "$*" = "${${(n)@}[*]}" ]&&<<<$@||f $@[0,#/2]}
Try it online!
There is no "is-sorted" builtin in zsh, but there are some "sort-array" builtins. We use the parameter expansion flag n, but o or i would also work. We then have to use [*] and quote to induce joining. This is shorter than alternatives (like zipping them together and comparing pairwise).
answered 2 days ago
GammaFunctionGammaFunction
2616
$endgroup$
add a comment |
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f182221%2fimplement-the-thanos-sorting-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
27 Answers
27
active
oldest
votes
27 Answers
27
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered Mar 26 at 11:50
Kirill L.Kirill L.
5,9631527
$endgroup$
2
$begingroup$
is.unsortedrather thanany(...)would also be 41 bytes.
$endgroup$
– Giuseppe
Mar 26 at 13:14
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
Mar 26 at 13:57
add a comment |
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered Mar 26 at 11:50
Kirill L.Kirill L.
5,9631527
$endgroup$
2
$begingroup$
is.unsortedrather thanany(...)would also be 41 bytes.
$endgroup$
– Giuseppe
Mar 26 at 13:14
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
Mar 26 at 13:57
add a comment |
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered Mar 26 at 11:50
Kirill L.Kirill L.
5,9631527
$endgroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered Mar 26 at 11:50
Kirill L.Kirill L.
5,9631527
answered Mar 26 at 11:50
Kirill L.Kirill L.
5,9631527
answered Mar 26 at 11:50
Kirill L.Kirill L.
5,9631527
answered Mar 26 at 11:50
Kirill L.Kirill L.
5,9631527
5,9631527
2
$begingroup$
is.unsortedrather thanany(...)would also be 41 bytes.
$endgroup$
– Giuseppe
Mar 26 at 13:14
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
Mar 26 at 13:57
add a comment |
2
$begingroup$
is.unsortedrather thanany(...)would also be 41 bytes.
$endgroup$
– Giuseppe
Mar 26 at 13:14
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
Mar 26 at 13:57
2
2
$begingroup$
is.unsorted rather than any(...) would also be 41 bytes.$endgroup$
– Giuseppe
Mar 26 at 13:14
$begingroup$
is.unsorted rather than any(...) would also be 41 bytes.$endgroup$
– Giuseppe
Mar 26 at 13:14
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
Mar 26 at 13:57
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
Mar 26 at 13:57
add a comment |
$begingroup$
Python 3, 38 42 39 bytes
q=lambda t:t>sorted(t)and q(t[::2])or t
Try it online!
-3 bytes thanks to @JoKing and @Quuxplusone
answered Mar 26 at 10:47
Sara JSara J
505210
$endgroup$
2
$begingroup$
40 bytes
$endgroup$
– Jo King
Mar 26 at 12:16
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)must be> sorted(t).
$endgroup$
– Quuxplusone
Mar 26 at 15:47
add a comment |
$begingroup$
Python 3, 38 42 39 bytes
q=lambda t:t>sorted(t)and q(t[::2])or t
Try it online!
-3 bytes thanks to @JoKing and @Quuxplusone
answered Mar 26 at 10:47
Sara JSara J
505210
$endgroup$
2
$begingroup$
40 bytes
$endgroup$
– Jo King
Mar 26 at 12:16
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)must be> sorted(t).
$endgroup$
– Quuxplusone
Mar 26 at 15:47
add a comment |
$begingroup$
Python 3, 38 42 39 bytes
q=lambda t:t>sorted(t)and q(t[::2])or t
Try it online!
-3 bytes thanks to @JoKing and @Quuxplusone
answered Mar 26 at 10:47
Sara JSara J
505210
$endgroup$
Python 3, 38 42 39 bytes
q=lambda t:t>sorted(t)and q(t[::2])or t
Try it online!
-3 bytes thanks to @JoKing and @Quuxplusone
answered Mar 26 at 10:47
Sara JSara J
505210
edited Mar 26 at 18:45
answered Mar 26 at 10:47
Sara JSara J
505210
answered Mar 26 at 10:47
Sara JSara J
505210
answered Mar 26 at 10:47
Sara JSara J
505210
505210
2
$begingroup$
40 bytes
$endgroup$
– Jo King
Mar 26 at 12:16
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)must be> sorted(t).
$endgroup$
– Quuxplusone
Mar 26 at 15:47
add a comment |
2
$begingroup$
40 bytes
$endgroup$
– Jo King
Mar 26 at 12:16
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)must be> sorted(t).
$endgroup$
– Quuxplusone
Mar 26 at 15:47
2
2
$begingroup$
40 bytes
$endgroup$
– Jo King
Mar 26 at 12:16
$begingroup$
40 bytes
$endgroup$
– Jo King
Mar 26 at 12:16
$begingroup$
39 bytes thanks to TFeld's observation that any permutation
!= sorted(t) must be > sorted(t).$endgroup$
– Quuxplusone
Mar 26 at 15:47
$begingroup$
39 bytes thanks to TFeld's observation that any permutation
!= sorted(t) must be > sorted(t).$endgroup$
– Quuxplusone
Mar 26 at 15:47
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered Mar 26 at 13:35
TFeldTFeld
16.3k21451
$endgroup$
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered Mar 26 at 13:35
TFeldTFeld
16.3k21451
$endgroup$
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered Mar 26 at 13:35
TFeldTFeld
16.3k21451
$endgroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered Mar 26 at 13:35
TFeldTFeld
16.3k21451
answered Mar 26 at 13:35
TFeldTFeld
16.3k21451
answered Mar 26 at 13:35
TFeldTFeld
16.3k21451
answered Mar 26 at 13:35
TFeldTFeld
16.3k21451
16.3k21451
add a comment |
add a comment |
$begingroup$
Perl 6, 30 bytes
$!={[<=]($_)??$_!!.[^*/2].&$!}
Try it online!
Recursive function that removes the second half of the list until the list is sorted.
Explanation:
$!={ } # Assign the function to $!
[<=]($_)?? # If the input is sorted
$_ # Return the input
!! # Else
.[^*/2] # Take the first half of the list (rounding up)
.&$! # And apply the function again
answered Mar 26 at 12:13
Jo KingJo King
26k363129
$endgroup$
add a comment |
$begingroup$
Perl 6, 30 bytes
$!={[<=]($_)??$_!!.[^*/2].&$!}
Try it online!
Recursive function that removes the second half of the list until the list is sorted.
Explanation:
$!={ } # Assign the function to $!
[<=]($_)?? # If the input is sorted
$_ # Return the input
!! # Else
.[^*/2] # Take the first half of the list (rounding up)
.&$! # And apply the function again
answered Mar 26 at 12:13
Jo KingJo King
26k363129
$endgroup$
add a comment |
$begingroup$
Perl 6, 30 bytes
$!={[<=]($_)??$_!!.[^*/2].&$!}
Try it online!
Recursive function that removes the second half of the list until the list is sorted.
Explanation:
$!={ } # Assign the function to $!
[<=]($_)?? # If the input is sorted
$_ # Return the input
!! # Else
.[^*/2] # Take the first half of the list (rounding up)
.&$! # And apply the function again
answered Mar 26 at 12:13
Jo KingJo King
26k363129
$endgroup$
Perl 6, 30 bytes
$!={[<=]($_)??$_!!.[^*/2].&$!}
Try it online!
Recursive function that removes the second half of the list until the list is sorted.
Explanation:
$!={ } # Assign the function to $!
[<=]($_)?? # If the input is sorted
$_ # Return the input
!! # Else
.[^*/2] # Take the first half of the list (rounding up)
.&$! # And apply the function again
answered Mar 26 at 12:13
Jo KingJo King
26k363129
answered Mar 26 at 12:13
Jo KingJo King
26k363129
answered Mar 26 at 12:13
Jo KingJo King
26k363129
answered Mar 26 at 12:13
Jo KingJo King
26k363129
26k363129
add a comment |
add a comment |
$begingroup$
Brachylog (v2), 6 bytes
≤₁|ḍt↰
Try it online!
This is a function submission. Input from the left, output to the right, as usual. (The TIO link uses a command-line argument that automatically wraps the function into a full program, so that you can see it in action.)
Explanation
≤₁|ḍt↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
ḍ Split the list into two halves (as evenly as possible)
t Take the last (i.e. second) half
↰ Recurse {and output the result of the recursion}
Bonus round
≤₁|⊇ᵇlᵍḍhtṛ↰
Try it online!
The snap's meant to be random, isn't it? Here's a version of the program that choses the surviving elements randomly (while ensuring that half survive at each round).
≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
⊇ᵇ Find all subsets of the input (preserving order)
lᵍ Group them by length
ḍht Find the group with median length:
t last element of
h first
ḍ half (split so that the first half is larger)
ṛ Pick a random subset from that group
↰ Recurse
This would be rather shorter if we could reorder the elements, but whyever would a sorting algorithm want to do that?
$endgroup$
9
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
Mar 26 at 20:42
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
Mar 28 at 0:44
add a comment |
$begingroup$
Brachylog (v2), 6 bytes
≤₁|ḍt↰
Try it online!
This is a function submission. Input from the left, output to the right, as usual. (The TIO link uses a command-line argument that automatically wraps the function into a full program, so that you can see it in action.)
Explanation
≤₁|ḍt↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
ḍ Split the list into two halves (as evenly as possible)
t Take the last (i.e. second) half
↰ Recurse {and output the result of the recursion}
Bonus round
≤₁|⊇ᵇlᵍḍhtṛ↰
Try it online!
The snap's meant to be random, isn't it? Here's a version of the program that choses the surviving elements randomly (while ensuring that half survive at each round).
≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
⊇ᵇ Find all subsets of the input (preserving order)
lᵍ Group them by length
ḍht Find the group with median length:
t last element of
h first
ḍ half (split so that the first half is larger)
ṛ Pick a random subset from that group
↰ Recurse
This would be rather shorter if we could reorder the elements, but whyever would a sorting algorithm want to do that?
$endgroup$
9
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
Mar 26 at 20:42
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
Mar 28 at 0:44
add a comment |
$begingroup$
Brachylog (v2), 6 bytes
≤₁|ḍt↰
Try it online!
This is a function submission. Input from the left, output to the right, as usual. (The TIO link uses a command-line argument that automatically wraps the function into a full program, so that you can see it in action.)
Explanation
≤₁|ḍt↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
ḍ Split the list into two halves (as evenly as possible)
t Take the last (i.e. second) half
↰ Recurse {and output the result of the recursion}
Bonus round
≤₁|⊇ᵇlᵍḍhtṛ↰
Try it online!
The snap's meant to be random, isn't it? Here's a version of the program that choses the surviving elements randomly (while ensuring that half survive at each round).
≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
⊇ᵇ Find all subsets of the input (preserving order)
lᵍ Group them by length
ḍht Find the group with median length:
t last element of
h first
ḍ half (split so that the first half is larger)
ṛ Pick a random subset from that group
↰ Recurse
This would be rather shorter if we could reorder the elements, but whyever would a sorting algorithm want to do that?
$endgroup$
Brachylog (v2), 6 bytes
≤₁|ḍt↰
Try it online!
This is a function submission. Input from the left, output to the right, as usual. (The TIO link uses a command-line argument that automatically wraps the function into a full program, so that you can see it in action.)
Explanation
≤₁|ḍt↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
ḍ Split the list into two halves (as evenly as possible)
t Take the last (i.e. second) half
↰ Recurse {and output the result of the recursion}
Bonus round
≤₁|⊇ᵇlᵍḍhtṛ↰
Try it online!
The snap's meant to be random, isn't it? Here's a version of the program that choses the surviving elements randomly (while ensuring that half survive at each round).
≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
⊇ᵇ Find all subsets of the input (preserving order)
lᵍ Group them by length
ḍht Find the group with median length:
t last element of
h first
ḍ half (split so that the first half is larger)
ṛ Pick a random subset from that group
↰ Recurse
This would be rather shorter if we could reorder the elements, but whyever would a sorting algorithm want to do that?
edited Mar 26 at 19:37
community wiki
2 revs
ais523
9
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
Mar 26 at 20:42
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
Mar 28 at 0:44
add a comment |
9
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
Mar 26 at 20:42
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
Mar 28 at 0:44
9
9
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
Mar 26 at 20:42
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
Mar 26 at 20:42
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
Mar 28 at 0:44
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
Mar 28 at 0:44
add a comment |
$begingroup$
Java 10, 106 97 bytes
L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}
-9 bytes thanks to @OlivierGrégoire.
Try it online.
Only leave the first halve of the list every iteration, and removes $frac{n+1}{2}$ items if the list-size is odd.
Explanation:
L->{ // Method with Integer-list as both parameter and return-type
for(;; // Loop indefinitely:
L=L.subList(0,L.size()/2)){
// After every iteration: only leave halve the numbers in the list
int p=1<<31, // Previous integer, starting at -2147483648
f=1; // Flag-integer, starting at 1
for(int i:L) // Inner loop over the integer in the list:
f=p>(p=i)? // If `a>b` in a pair of integers `a,b`:
0 // Set the flag to 0
: // Else (`a<=b`):
f; // Leave the flag the same
if(f>0) // If the flag is still 1 after the loop:
return L;}} // Return the list as result
answered Mar 26 at 14:29
Kevin CruijssenKevin Cruijssen
41.9k569217
$endgroup$
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}is shorter using streams, but I haven't been able to figure out how to avoid thejava.lang.IllegalStateException: stream has already been operated upon or closederror after returning the stream
$endgroup$
– Embodiment of Ignorance
Mar 26 at 21:09
$begingroup$
@EmbodimentofIgnorance this happens becausereduceis a terminal operation that closes the stream. You won't ever be able to callreducetwice on the same stream. You can create a new stream, though.
$endgroup$
– Olivier Grégoire
Mar 27 at 15:37
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
Mar 27 at 16:05
$begingroup$
@OlivierGrégoire That order looks so simple now that I see it.. Sometimes it takes a look from another angle to see the obvious others initially miss I guess. :) Thanks!
$endgroup$
– Kevin Cruijssen
Mar 27 at 18:17
1
$begingroup$
No worries, it wasn't obvious: I worked to get there. I tested at least 10 versions before finding that one ;)
$endgroup$
– Olivier Grégoire
Mar 28 at 13:02
add a comment |
$begingroup$
Java 10, 106 97 bytes
L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}
-9 bytes thanks to @OlivierGrégoire.
Try it online.
Only leave the first halve of the list every iteration, and removes $frac{n+1}{2}$ items if the list-size is odd.
Explanation:
L->{ // Method with Integer-list as both parameter and return-type
for(;; // Loop indefinitely:
L=L.subList(0,L.size()/2)){
// After every iteration: only leave halve the numbers in the list
int p=1<<31, // Previous integer, starting at -2147483648
f=1; // Flag-integer, starting at 1
for(int i:L) // Inner loop over the integer in the list:
f=p>(p=i)? // If `a>b` in a pair of integers `a,b`:
0 // Set the flag to 0
: // Else (`a<=b`):
f; // Leave the flag the same
if(f>0) // If the flag is still 1 after the loop:
return L;}} // Return the list as result
answered Mar 26 at 14:29
Kevin CruijssenKevin Cruijssen
41.9k569217
$endgroup$
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}is shorter using streams, but I haven't been able to figure out how to avoid thejava.lang.IllegalStateException: stream has already been operated upon or closederror after returning the stream
$endgroup$
– Embodiment of Ignorance
Mar 26 at 21:09
$begingroup$
@EmbodimentofIgnorance this happens becausereduceis a terminal operation that closes the stream. You won't ever be able to callreducetwice on the same stream. You can create a new stream, though.
$endgroup$
– Olivier Grégoire
Mar 27 at 15:37
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
Mar 27 at 16:05
$begingroup$
@OlivierGrégoire That order looks so simple now that I see it.. Sometimes it takes a look from another angle to see the obvious others initially miss I guess. :) Thanks!
$endgroup$
– Kevin Cruijssen
Mar 27 at 18:17
1
$begingroup$
No worries, it wasn't obvious: I worked to get there. I tested at least 10 versions before finding that one ;)
$endgroup$
– Olivier Grégoire
Mar 28 at 13:02
add a comment |
$begingroup$
Java 10, 106 97 bytes
L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}
-9 bytes thanks to @OlivierGrégoire.
Try it online.
Only leave the first halve of the list every iteration, and removes $frac{n+1}{2}$ items if the list-size is odd.
Explanation:
L->{ // Method with Integer-list as both parameter and return-type
for(;; // Loop indefinitely:
L=L.subList(0,L.size()/2)){
// After every iteration: only leave halve the numbers in the list
int p=1<<31, // Previous integer, starting at -2147483648
f=1; // Flag-integer, starting at 1
for(int i:L) // Inner loop over the integer in the list:
f=p>(p=i)? // If `a>b` in a pair of integers `a,b`:
0 // Set the flag to 0
: // Else (`a<=b`):
f; // Leave the flag the same
if(f>0) // If the flag is still 1 after the loop:
return L;}} // Return the list as result
answered Mar 26 at 14:29
Kevin CruijssenKevin Cruijssen
41.9k569217
$endgroup$
Java 10, 106 97 bytes
L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}
-9 bytes thanks to @OlivierGrégoire.
Try it online.
Only leave the first halve of the list every iteration, and removes $frac{n+1}{2}$ items if the list-size is odd.
Explanation:
L->{ // Method with Integer-list as both parameter and return-type
for(;; // Loop indefinitely:
L=L.subList(0,L.size()/2)){
// After every iteration: only leave halve the numbers in the list
int p=1<<31, // Previous integer, starting at -2147483648
f=1; // Flag-integer, starting at 1
for(int i:L) // Inner loop over the integer in the list:
f=p>(p=i)? // If `a>b` in a pair of integers `a,b`:
0 // Set the flag to 0
: // Else (`a<=b`):
f; // Leave the flag the same
if(f>0) // If the flag is still 1 after the loop:
return L;}} // Return the list as result
answered Mar 26 at 14:29
Kevin CruijssenKevin Cruijssen
41.9k569217
edited Mar 27 at 18:16
answered Mar 26 at 14:29
Kevin CruijssenKevin Cruijssen
41.9k569217
answered Mar 26 at 14:29
Kevin CruijssenKevin Cruijssen
41.9k569217
answered Mar 26 at 14:29
Kevin CruijssenKevin Cruijssen
41.9k569217
41.9k569217
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}is shorter using streams, but I haven't been able to figure out how to avoid thejava.lang.IllegalStateException: stream has already been operated upon or closederror after returning the stream
$endgroup$
– Embodiment of Ignorance
Mar 26 at 21:09
$begingroup$
@EmbodimentofIgnorance this happens becausereduceis a terminal operation that closes the stream. You won't ever be able to callreducetwice on the same stream. You can create a new stream, though.
$endgroup$
– Olivier Grégoire
Mar 27 at 15:37
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
Mar 27 at 16:05
$begingroup$
@OlivierGrégoire That order looks so simple now that I see it.. Sometimes it takes a look from another angle to see the obvious others initially miss I guess. :) Thanks!
$endgroup$
– Kevin Cruijssen
Mar 27 at 18:17
1
$begingroup$
No worries, it wasn't obvious: I worked to get there. I tested at least 10 versions before finding that one ;)
$endgroup$
– Olivier Grégoire
Mar 28 at 13:02
add a comment |
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}is shorter using streams, but I haven't been able to figure out how to avoid thejava.lang.IllegalStateException: stream has already been operated upon or closederror after returning the stream
$endgroup$
– Embodiment of Ignorance
Mar 26 at 21:09
$begingroup$
@EmbodimentofIgnorance this happens becausereduceis a terminal operation that closes the stream. You won't ever be able to callreducetwice on the same stream. You can create a new stream, though.
$endgroup$
– Olivier Grégoire
Mar 27 at 15:37
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
Mar 27 at 16:05
$begingroup$
@OlivierGrégoire That order looks so simple now that I see it.. Sometimes it takes a look from another angle to see the obvious others initially miss I guess. :) Thanks!
$endgroup$
– Kevin Cruijssen
Mar 27 at 18:17
1
$begingroup$
No worries, it wasn't obvious: I worked to get there. I tested at least 10 versions before finding that one ;)
$endgroup$
– Olivier Grégoire
Mar 28 at 13:02
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;} is shorter using streams, but I haven't been able to figure out how to avoid the java.lang.IllegalStateException: stream has already been operated upon or closed error after returning the stream$endgroup$
– Embodiment of Ignorance
Mar 26 at 21:09
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;} is shorter using streams, but I haven't been able to figure out how to avoid the java.lang.IllegalStateException: stream has already been operated upon or closed error after returning the stream$endgroup$
– Embodiment of Ignorance
Mar 26 at 21:09
$begingroup$
@EmbodimentofIgnorance this happens because
reduce is a terminal operation that closes the stream. You won't ever be able to call reduce twice on the same stream. You can create a new stream, though.$endgroup$
– Olivier Grégoire
Mar 27 at 15:37
$begingroup$
@EmbodimentofIgnorance this happens because
reduce is a terminal operation that closes the stream. You won't ever be able to call reduce twice on the same stream. You can create a new stream, though.$endgroup$
– Olivier Grégoire
Mar 27 at 15:37
1
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
Mar 27 at 16:05
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
Mar 27 at 16:05
$begingroup$
@OlivierGrégoire That order looks so simple now that I see it.. Sometimes it takes a look from another angle to see the obvious others initially miss I guess. :) Thanks!
$endgroup$
– Kevin Cruijssen
Mar 27 at 18:17
$begingroup$
@OlivierGrégoire That order looks so simple now that I see it.. Sometimes it takes a look from another angle to see the obvious others initially miss I guess. :) Thanks!
$endgroup$
– Kevin Cruijssen
Mar 27 at 18:17
1
1
$begingroup$
No worries, it wasn't obvious: I worked to get there. I tested at least 10 versions before finding that one ;)
$endgroup$
– Olivier Grégoire
Mar 28 at 13:02
$begingroup$
No worries, it wasn't obvious: I worked to get there. I tested at least 10 versions before finding that one ;)
$endgroup$
– Olivier Grégoire
Mar 28 at 13:02
add a comment |
$begingroup$
C# (Visual C# Interactive Compiler), 76 bytes
g=>{while(!g.OrderBy(x=>x).SequenceEqual(g))g=g.Take(g.Count()/2);return g;}
Try it online!
answered Mar 26 at 11:40
Expired DataExpired Data
4288
$endgroup$
add a comment |
$begingroup$
C# (Visual C# Interactive Compiler), 76 bytes
g=>{while(!g.OrderBy(x=>x).SequenceEqual(g))g=g.Take(g.Count()/2);return g;}
Try it online!
answered Mar 26 at 11:40
Expired DataExpired Data
4288
$endgroup$
add a comment |
$begingroup$
C# (Visual C# Interactive Compiler), 76 bytes
g=>{while(!g.OrderBy(x=>x).SequenceEqual(g))g=g.Take(g.Count()/2);return g;}
Try it online!
answered Mar 26 at 11:40
Expired DataExpired Data
4288
$endgroup$
C# (Visual C# Interactive Compiler), 76 bytes
g=>{while(!g.OrderBy(x=>x).SequenceEqual(g))g=g.Take(g.Count()/2);return g;}
Try it online!
answered Mar 26 at 11:40
Expired DataExpired Data
4288
answered Mar 26 at 11:40
Expired DataExpired Data
4288
answered Mar 26 at 11:40
Expired DataExpired Data
4288
answered Mar 26 at 11:40
Expired DataExpired Data
4288
4288
add a comment |
add a comment |
$begingroup$
Wolfram Language (Mathematica), 30 bytes
#//.x_/;Sort@x!=x:>x[[;;;;2]]&
Try it online!
@Doorknob saved 12 bytes
answered Mar 26 at 14:24
J42161217J42161217
13.6k21252
$endgroup$
1
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (x[[;;;;2]]).
$endgroup$
– Doorknob♦
Mar 28 at 3:40
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
Mar 28 at 10:24
$begingroup$
thought there could be some savings by usingOrderedQ, but couldn't make it work
$endgroup$
– Greg Martin
2 days ago
$begingroup$
@GregMartin I usedOrderedQin my very first approach (see edits)
$endgroup$
– J42161217
2 days ago
add a comment |
$begingroup$
Wolfram Language (Mathematica), 30 bytes
#//.x_/;Sort@x!=x:>x[[;;;;2]]&
Try it online!
@Doorknob saved 12 bytes
answered Mar 26 at 14:24
J42161217J42161217
13.6k21252
$endgroup$
1
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (x[[;;;;2]]).
$endgroup$
– Doorknob♦
Mar 28 at 3:40
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
Mar 28 at 10:24
$begingroup$
thought there could be some savings by usingOrderedQ, but couldn't make it work
$endgroup$
– Greg Martin
2 days ago
$begingroup$
@GregMartin I usedOrderedQin my very first approach (see edits)
$endgroup$
– J42161217
2 days ago
add a comment |
$begingroup$
Wolfram Language (Mathematica), 30 bytes
#//.x_/;Sort@x!=x:>x[[;;;;2]]&
Try it online!
@Doorknob saved 12 bytes
answered Mar 26 at 14:24
J42161217J42161217
13.6k21252
$endgroup$
Wolfram Language (Mathematica), 30 bytes
#//.x_/;Sort@x!=x:>x[[;;;;2]]&
Try it online!
@Doorknob saved 12 bytes
answered Mar 26 at 14:24
J42161217J42161217
13.6k21252
edited Mar 28 at 10:22
answered Mar 26 at 14:24
J42161217J42161217
13.6k21252
answered Mar 26 at 14:24
J42161217J42161217
13.6k21252
answered Mar 26 at 14:24
J42161217J42161217
13.6k21252
13.6k21252
1
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (x[[;;;;2]]).
$endgroup$
– Doorknob♦
Mar 28 at 3:40
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
Mar 28 at 10:24
$begingroup$
thought there could be some savings by usingOrderedQ, but couldn't make it work
$endgroup$
– Greg Martin
2 days ago
$begingroup$
@GregMartin I usedOrderedQin my very first approach (see edits)
$endgroup$
– J42161217
2 days ago
add a comment |
1
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (x[[;;;;2]]).
$endgroup$
– Doorknob♦
Mar 28 at 3:40
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
Mar 28 at 10:24
$begingroup$
thought there could be some savings by usingOrderedQ, but couldn't make it work
$endgroup$
– Greg Martin
2 days ago
$begingroup$
@GregMartin I usedOrderedQin my very first approach (see edits)
$endgroup$
– J42161217
2 days ago
1
1
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (
x[[;;;;2]]).$endgroup$
– Doorknob♦
Mar 28 at 3:40
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (
x[[;;;;2]]).$endgroup$
– Doorknob♦
Mar 28 at 3:40
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
Mar 28 at 10:24
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
Mar 28 at 10:24
$begingroup$
thought there could be some savings by using
OrderedQ, but couldn't make it work$endgroup$
– Greg Martin
2 days ago
$begingroup$
thought there could be some savings by using
OrderedQ, but couldn't make it work$endgroup$
– Greg Martin
2 days ago
$begingroup$
@GregMartin I used
OrderedQ in my very first approach (see edits)$endgroup$
– J42161217
2 days ago
$begingroup$
@GregMartin I used
OrderedQ in my very first approach (see edits)$endgroup$
– J42161217
2 days ago
add a comment |
$begingroup$
JavaScript (ES6), 49 48 bytes
Saved 1 byte thanks to @tsh
Removes every 2nd element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a
Try it online!
answered Mar 26 at 14:38
ArnauldArnauld
80k797331
$endgroup$
$begingroup$
p++&1->a^=1
$endgroup$
– tsh
2 days ago
add a comment |
$begingroup$
JavaScript (ES6), 49 48 bytes
Saved 1 byte thanks to @tsh
Removes every 2nd element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a
Try it online!
answered Mar 26 at 14:38
ArnauldArnauld
80k797331
$endgroup$
$begingroup$
p++&1->a^=1
$endgroup$
– tsh
2 days ago
add a comment |
$begingroup$
JavaScript (ES6), 49 48 bytes
Saved 1 byte thanks to @tsh
Removes every 2nd element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a
Try it online!
answered Mar 26 at 14:38
ArnauldArnauld
80k797331
$endgroup$
JavaScript (ES6), 49 48 bytes
Saved 1 byte thanks to @tsh
Removes every 2nd element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a
Try it online!
answered Mar 26 at 14:38
ArnauldArnauld
80k797331
edited 2 days ago
answered Mar 26 at 14:38
ArnauldArnauld
80k797331
answered Mar 26 at 14:38
ArnauldArnauld
80k797331
answered Mar 26 at 14:38
ArnauldArnauld
80k797331
80k797331
$begingroup$
p++&1->a^=1
$endgroup$
– tsh
2 days ago
add a comment |
$begingroup$
p++&1->a^=1
$endgroup$
– tsh
2 days ago
$begingroup$
p++&1 -> a^=1$endgroup$
– tsh
2 days ago
$begingroup$
p++&1 -> a^=1$endgroup$
– tsh
2 days ago
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
7 bytes alternative by @Grimy:
ΔÐ{Ê>äн
Removes the last $frac{n}{2}$ items (or $frac{n-1}{2}$ items if the list-size is odd) every iteration.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Explanation:
[ # Start an infinite loop:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Q # Sort a copy, and check if they are equal
# # If it is: Stop the infinite loop (and output the result implicitly)
ι # Uninterweave: halve the list into two parts; first containing all even-indexed
# items, second containing all odd-indexed items (0-indexed)
# i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
н # And only leave the first part
Δ # Loop until the result no longer changes:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Ê # Sort a copy, and check if they are NOT equal (1 if truthy; 0 if falsey)
> # Increase this by 1 (so 1 if the list is sorted; 2 if it isn't sorted)
ä # Split the list in that many parts
н # And only leave the first part
# (and output the result implicitly after it no longer changes)
answered Mar 26 at 11:11
Kevin CruijssenKevin Cruijssen
41.9k569217
$endgroup$
3
$begingroup$
You can useιinstead of2äif you switch to a keep every other element strategy.
$endgroup$
– Emigna
Mar 26 at 12:07
1
$begingroup$
Alternative 7 using the "remove the last half" strategy:ΔÐ{Ê>äн
$endgroup$
– Grimy
2 days ago
$begingroup$
@Grimy That's a pretty nice approach as well. Shall I add it to my post (crediting you of course), or do you want to post it as a separated answer?
$endgroup$
– Kevin Cruijssen
2 days ago
$begingroup$
Feel free to add it.
$endgroup$
– Grimy
2 days ago
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
7 bytes alternative by @Grimy:
ΔÐ{Ê>äн
Removes the last $frac{n}{2}$ items (or $frac{n-1}{2}$ items if the list-size is odd) every iteration.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Explanation:
[ # Start an infinite loop:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Q # Sort a copy, and check if they are equal
# # If it is: Stop the infinite loop (and output the result implicitly)
ι # Uninterweave: halve the list into two parts; first containing all even-indexed
# items, second containing all odd-indexed items (0-indexed)
# i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
н # And only leave the first part
Δ # Loop until the result no longer changes:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Ê # Sort a copy, and check if they are NOT equal (1 if truthy; 0 if falsey)
> # Increase this by 1 (so 1 if the list is sorted; 2 if it isn't sorted)
ä # Split the list in that many parts
н # And only leave the first part
# (and output the result implicitly after it no longer changes)
answered Mar 26 at 11:11
Kevin CruijssenKevin Cruijssen
41.9k569217
$endgroup$
3
$begingroup$
You can useιinstead of2äif you switch to a keep every other element strategy.
$endgroup$
– Emigna
Mar 26 at 12:07
1
$begingroup$
Alternative 7 using the "remove the last half" strategy:ΔÐ{Ê>äн
$endgroup$
– Grimy
2 days ago
$begingroup$
@Grimy That's a pretty nice approach as well. Shall I add it to my post (crediting you of course), or do you want to post it as a separated answer?
$endgroup$
– Kevin Cruijssen
2 days ago
$begingroup$
Feel free to add it.
$endgroup$
– Grimy
2 days ago
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
7 bytes alternative by @Grimy:
ΔÐ{Ê>äн
Removes the last $frac{n}{2}$ items (or $frac{n-1}{2}$ items if the list-size is odd) every iteration.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Explanation:
[ # Start an infinite loop:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Q # Sort a copy, and check if they are equal
# # If it is: Stop the infinite loop (and output the result implicitly)
ι # Uninterweave: halve the list into two parts; first containing all even-indexed
# items, second containing all odd-indexed items (0-indexed)
# i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
н # And only leave the first part
Δ # Loop until the result no longer changes:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Ê # Sort a copy, and check if they are NOT equal (1 if truthy; 0 if falsey)
> # Increase this by 1 (so 1 if the list is sorted; 2 if it isn't sorted)
ä # Split the list in that many parts
н # And only leave the first part
# (and output the result implicitly after it no longer changes)
answered Mar 26 at 11:11
Kevin CruijssenKevin Cruijssen
41.9k569217
$endgroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
7 bytes alternative by @Grimy:
ΔÐ{Ê>äн
Removes the last $frac{n}{2}$ items (or $frac{n-1}{2}$ items if the list-size is odd) every iteration.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Explanation:
[ # Start an infinite loop:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Q # Sort a copy, and check if they are equal
# # If it is: Stop the infinite loop (and output the result implicitly)
ι # Uninterweave: halve the list into two parts; first containing all even-indexed
# items, second containing all odd-indexed items (0-indexed)
# i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
н # And only leave the first part
Δ # Loop until the result no longer changes:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Ê # Sort a copy, and check if they are NOT equal (1 if truthy; 0 if falsey)
> # Increase this by 1 (so 1 if the list is sorted; 2 if it isn't sorted)
ä # Split the list in that many parts
н # And only leave the first part
# (and output the result implicitly after it no longer changes)
answered Mar 26 at 11:11
Kevin CruijssenKevin Cruijssen
41.9k569217
edited 2 days ago
answered Mar 26 at 11:11
Kevin CruijssenKevin Cruijssen
41.9k569217
answered Mar 26 at 11:11
Kevin CruijssenKevin Cruijssen
41.9k569217
answered Mar 26 at 11:11
Kevin CruijssenKevin Cruijssen
41.9k569217
41.9k569217
3
$begingroup$
You can useιinstead of2äif you switch to a keep every other element strategy.
$endgroup$
– Emigna
Mar 26 at 12:07
1
$begingroup$
Alternative 7 using the "remove the last half" strategy:ΔÐ{Ê>äн
$endgroup$
– Grimy
2 days ago
$begingroup$
@Grimy That's a pretty nice approach as well. Shall I add it to my post (crediting you of course), or do you want to post it as a separated answer?
$endgroup$
– Kevin Cruijssen
2 days ago
$begingroup$
Feel free to add it.
$endgroup$
– Grimy
2 days ago
add a comment |
3
$begingroup$
You can useιinstead of2äif you switch to a keep every other element strategy.
$endgroup$
– Emigna
Mar 26 at 12:07
1
$begingroup$
Alternative 7 using the "remove the last half" strategy:ΔÐ{Ê>äн
$endgroup$
– Grimy
2 days ago
$begingroup$
@Grimy That's a pretty nice approach as well. Shall I add it to my post (crediting you of course), or do you want to post it as a separated answer?
$endgroup$
– Kevin Cruijssen
2 days ago
$begingroup$
Feel free to add it.
$endgroup$
– Grimy
2 days ago
3
3
$begingroup$
You can use
ι instead of 2ä if you switch to a keep every other element strategy.$endgroup$
– Emigna
Mar 26 at 12:07
$begingroup$
You can use
ι instead of 2ä if you switch to a keep every other element strategy.$endgroup$
– Emigna
Mar 26 at 12:07
1
1
$begingroup$
Alternative 7 using the "remove the last half" strategy:
ΔÐ{Ê>äн$endgroup$
– Grimy
2 days ago
$begingroup$
Alternative 7 using the "remove the last half" strategy:
ΔÐ{Ê>äн$endgroup$
– Grimy
2 days ago
$begingroup$
@Grimy That's a pretty nice approach as well. Shall I add it to my post (crediting you of course), or do you want to post it as a separated answer?
$endgroup$
– Kevin Cruijssen
2 days ago
$begingroup$
@Grimy That's a pretty nice approach as well. Shall I add it to my post (crediting you of course), or do you want to post it as a separated answer?
$endgroup$
– Kevin Cruijssen
2 days ago
$begingroup$
Feel free to add it.
$endgroup$
– Grimy
2 days ago
$begingroup$
Feel free to add it.
$endgroup$
– Grimy
2 days ago
add a comment |
$begingroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered Mar 26 at 20:09
G BG B
8,1261429
$endgroup$
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
Mar 26 at 20:41
add a comment |
$begingroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered Mar 26 at 20:09
G BG B
8,1261429
$endgroup$
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
Mar 26 at 20:41
add a comment |
$begingroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered Mar 26 at 20:09
G BG B
8,1261429
$endgroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered Mar 26 at 20:09
G BG B
8,1261429
answered Mar 26 at 20:09
G BG B
8,1261429
answered Mar 26 at 20:09
G BG B
8,1261429
answered Mar 26 at 20:09
G BG B
8,1261429
8,1261429
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
Mar 26 at 20:41
add a comment |
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
Mar 26 at 20:41
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
Mar 26 at 20:41
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
Mar 26 at 20:41
add a comment |
$begingroup$
TI-BASIC (TI-84), 47 42 45 bytes
Ans→L1:Ans→L2:SortA(L1:While not(min(L1=Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans
Input list is in Ans.
Output is in Ans and is implicitly printed out.
Explanation:
Ans→L1 ;store the input into two lists
Ans→L2
SortA(L1 ;sort the first list
; two lists are needed because "SortA(" edits the list it sorts
While not(min(L1=Ans ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list
; removes (n+1)/2 elements if list has an odd length
L2→L1 ;store the new list into the first list (updates "Ans")
SortA(L1 ;sort the first list
End
Ans ;implicitly output the list when the loop ends
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
answered Mar 26 at 16:04
TauTau
716311
$endgroup$
add a comment |
$begingroup$
TI-BASIC (TI-84), 47 42 45 bytes
Ans→L1:Ans→L2:SortA(L1:While not(min(L1=Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans
Input list is in Ans.
Output is in Ans and is implicitly printed out.
Explanation:
Ans→L1 ;store the input into two lists
Ans→L2
SortA(L1 ;sort the first list
; two lists are needed because "SortA(" edits the list it sorts
While not(min(L1=Ans ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list
; removes (n+1)/2 elements if list has an odd length
L2→L1 ;store the new list into the first list (updates "Ans")
SortA(L1 ;sort the first list
End
Ans ;implicitly output the list when the loop ends
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
answered Mar 26 at 16:04
TauTau
716311
$endgroup$
add a comment |
$begingroup$
TI-BASIC (TI-84), 47 42 45 bytes
Ans→L1:Ans→L2:SortA(L1:While not(min(L1=Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans
Input list is in Ans.
Output is in Ans and is implicitly printed out.
Explanation:
Ans→L1 ;store the input into two lists
Ans→L2
SortA(L1 ;sort the first list
; two lists are needed because "SortA(" edits the list it sorts
While not(min(L1=Ans ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list
; removes (n+1)/2 elements if list has an odd length
L2→L1 ;store the new list into the first list (updates "Ans")
SortA(L1 ;sort the first list
End
Ans ;implicitly output the list when the loop ends
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
answered Mar 26 at 16:04
TauTau
716311
$endgroup$
TI-BASIC (TI-84), 47 42 45 bytes
Ans→L1:Ans→L2:SortA(L1:While not(min(L1=Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans
Input list is in Ans.
Output is in Ans and is implicitly printed out.
Explanation:
Ans→L1 ;store the input into two lists
Ans→L2
SortA(L1 ;sort the first list
; two lists are needed because "SortA(" edits the list it sorts
While not(min(L1=Ans ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list
; removes (n+1)/2 elements if list has an odd length
L2→L1 ;store the new list into the first list (updates "Ans")
SortA(L1 ;sort the first list
End
Ans ;implicitly output the list when the loop ends
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
answered Mar 26 at 16:04
TauTau
716311
edited Mar 27 at 3:56
answered Mar 26 at 16:04
TauTau
716311
answered Mar 26 at 16:04
TauTau
716311
answered Mar 26 at 16:04
TauTau
716311
716311
add a comment |
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered Mar 26 at 16:44
Erik the OutgolferErik the Outgolfer
32.9k429106
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered Mar 26 at 16:44
Erik the OutgolferErik the Outgolfer
32.9k429106
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered Mar 26 at 16:44
Erik the OutgolferErik the Outgolfer
32.9k429106
$endgroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered Mar 26 at 16:44
Erik the OutgolferErik the Outgolfer
32.9k429106
answered Mar 26 at 16:44
Erik the OutgolferErik the Outgolfer
32.9k429106
answered Mar 26 at 16:44
Erik the OutgolferErik the Outgolfer
32.9k429106
answered Mar 26 at 16:44
Erik the OutgolferErik the Outgolfer
32.9k429106
32.9k429106
add a comment |
add a comment |
$begingroup$
Haskell, 57 55 bytes (thanks to ASCII-only)
f x|or$zipWith(>)x$tail x=f$take(div(length x)2)x|1>0=x
Try it online!
Original Code:
f x|or$zipWith(>)x(tail x)=f(take(div(length x)2)x)|1>0=x
Try it online!
Ungolfed:
f xs | sorted xs = f (halve xs)
| otherwise = xs
sorted xs = or (zipWith (>) xs (tail xs))
halve xs = take (length xs `div` 2) xs
answered Mar 28 at 4:35
SacheraSachera
512
New contributor
Sachera is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Rɪᴋᴇʀ
Mar 28 at 5:20
$begingroup$
56
$endgroup$
– ASCII-only
Mar 28 at 5:38
$begingroup$
57 :(
$endgroup$
– ASCII-only
Mar 28 at 5:44
$begingroup$
55
$endgroup$
– ASCII-only
Mar 28 at 5:55
add a comment |
$begingroup$
Haskell, 57 55 bytes (thanks to ASCII-only)
f x|or$zipWith(>)x$tail x=f$take(div(length x)2)x|1>0=x
Try it online!
Original Code:
f x|or$zipWith(>)x(tail x)=f(take(div(length x)2)x)|1>0=x
Try it online!
Ungolfed:
f xs | sorted xs = f (halve xs)
| otherwise = xs
sorted xs = or (zipWith (>) xs (tail xs))
halve xs = take (length xs `div` 2) xs
answered Mar 28 at 4:35
SacheraSachera
512
New contributor
Sachera is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Rɪᴋᴇʀ
Mar 28 at 5:20
$begingroup$
56
$endgroup$
– ASCII-only
Mar 28 at 5:38
$begingroup$
57 :(
$endgroup$
– ASCII-only
Mar 28 at 5:44
$begingroup$
55
$endgroup$
– ASCII-only
Mar 28 at 5:55
add a comment |
$begingroup$
Haskell, 57 55 bytes (thanks to ASCII-only)
f x|or$zipWith(>)x$tail x=f$take(div(length x)2)x|1>0=x
Try it online!
Original Code:
f x|or$zipWith(>)x(tail x)=f(take(div(length x)2)x)|1>0=x
Try it online!
Ungolfed:
f xs | sorted xs = f (halve xs)
| otherwise = xs
sorted xs = or (zipWith (>) xs (tail xs))
halve xs = take (length xs `div` 2) xs
answered Mar 28 at 4:35
SacheraSachera
512
New contributor
Sachera is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Haskell, 57 55 bytes (thanks to ASCII-only)
f x|or$zipWith(>)x$tail x=f$take(div(length x)2)x|1>0=x
Try it online!
Original Code:
f x|or$zipWith(>)x(tail x)=f(take(div(length x)2)x)|1>0=x
Try it online!
Ungolfed:
f xs | sorted xs = f (halve xs)
| otherwise = xs
sorted xs = or (zipWith (>) xs (tail xs))
halve xs = take (length xs `div` 2) xs
answered Mar 28 at 4:35
SacheraSachera
512
New contributor
Sachera is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
answered Mar 28 at 4:35
SacheraSachera
512
New contributor
Sachera is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Mar 28 at 4:35
SacheraSachera
512
answered Mar 28 at 4:35
SacheraSachera
512
512
New contributor
Sachera is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Sachera is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Sachera is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Rɪᴋᴇʀ
Mar 28 at 5:20
$begingroup$
56
$endgroup$
– ASCII-only
Mar 28 at 5:38
$begingroup$
57 :(
$endgroup$
– ASCII-only
Mar 28 at 5:44
$begingroup$
55
$endgroup$
– ASCII-only
Mar 28 at 5:55
add a comment |
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Rɪᴋᴇʀ
Mar 28 at 5:20
$begingroup$
56
$endgroup$
– ASCII-only
Mar 28 at 5:38
$begingroup$
57 :(
$endgroup$
– ASCII-only
Mar 28 at 5:44
$begingroup$
55
$endgroup$
– ASCII-only
Mar 28 at 5:55
1
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Rɪᴋᴇʀ
Mar 28 at 5:20
$begingroup$
Welcome to PPCG!
$endgroup$
– Rɪᴋᴇʀ
Mar 28 at 5:20
$begingroup$
56
$endgroup$
– ASCII-only
Mar 28 at 5:38
$begingroup$
56
$endgroup$
– ASCII-only
Mar 28 at 5:38
$begingroup$
57 :(
$endgroup$
– ASCII-only
Mar 28 at 5:44
$begingroup$
57 :(
$endgroup$
– ASCII-only
Mar 28 at 5:44
$begingroup$
55
$endgroup$
– ASCII-only
Mar 28 at 5:55
$begingroup$
55
$endgroup$
– ASCII-only
Mar 28 at 5:55
add a comment |
$begingroup$
MATL, 11 bytes
tv`1L)ttS-a
Try it online!
This works by removing every second item.
Explanation
t % Take a row vector as input (implicit). Duplicate
v % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
` % Do...while
1L) % Keep only odd-indexed entries (1-based, linear indexing)
t % Duplicate. This will leave a copy for the next iteration
tS % Duplicate, sort
-a % True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack
answered Mar 26 at 11:30
Luis MendoLuis Mendo
75.1k888291
$endgroup$
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
Mar 26 at 13:06
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
Mar 26 at 14:19
add a comment |
$begingroup$
MATL, 11 bytes
tv`1L)ttS-a
Try it online!
This works by removing every second item.
Explanation
t % Take a row vector as input (implicit). Duplicate
v % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
` % Do...while
1L) % Keep only odd-indexed entries (1-based, linear indexing)
t % Duplicate. This will leave a copy for the next iteration
tS % Duplicate, sort
-a % True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack
answered Mar 26 at 11:30
Luis MendoLuis Mendo
75.1k888291
$endgroup$
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
Mar 26 at 13:06
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
Mar 26 at 14:19
add a comment |
$begingroup$
MATL, 11 bytes
tv`1L)ttS-a
Try it online!
This works by removing every second item.
Explanation
t % Take a row vector as input (implicit). Duplicate
v % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
` % Do...while
1L) % Keep only odd-indexed entries (1-based, linear indexing)
t % Duplicate. This will leave a copy for the next iteration
tS % Duplicate, sort
-a % True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack
answered Mar 26 at 11:30
Luis MendoLuis Mendo
75.1k888291
$endgroup$
MATL, 11 bytes
tv`1L)ttS-a
Try it online!
This works by removing every second item.
Explanation
t % Take a row vector as input (implicit). Duplicate
v % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
` % Do...while
1L) % Keep only odd-indexed entries (1-based, linear indexing)
t % Duplicate. This will leave a copy for the next iteration
tS % Duplicate, sort
-a % True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack
answered Mar 26 at 11:30
Luis MendoLuis Mendo
75.1k888291
edited Mar 26 at 14:18
answered Mar 26 at 11:30
Luis MendoLuis Mendo
75.1k888291
answered Mar 26 at 11:30
Luis MendoLuis Mendo
75.1k888291
answered Mar 26 at 11:30
Luis MendoLuis Mendo
75.1k888291
75.1k888291
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
Mar 26 at 13:06
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
Mar 26 at 14:19
add a comment |
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
Mar 26 at 13:06
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
Mar 26 at 14:19
2
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
Mar 26 at 13:06
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
Mar 26 at 13:06
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
Mar 26 at 14:19
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
Mar 26 at 14:19
add a comment |
$begingroup$
Japt, 10 bytes
eUñ)?U:ßUë
Try it
eUñ)?U:ßUë :Implicit input of array U
e :Compare equality with
Uñ : U sorted
) :End compare
?U: :If true then return U else
ß :Run the programme again with input
Uë : Every second element of U
answered Mar 26 at 14:27
ShaggyShaggy
19.1k21768
$endgroup$
add a comment |
$begingroup$
Japt, 10 bytes
eUñ)?U:ßUë
Try it
eUñ)?U:ßUë :Implicit input of array U
e :Compare equality with
Uñ : U sorted
) :End compare
?U: :If true then return U else
ß :Run the programme again with input
Uë : Every second element of U
answered Mar 26 at 14:27
ShaggyShaggy
19.1k21768
$endgroup$
add a comment |
$begingroup$
Japt, 10 bytes
eUñ)?U:ßUë
Try it
eUñ)?U:ßUë :Implicit input of array U
e :Compare equality with
Uñ : U sorted
) :End compare
?U: :If true then return U else
ß :Run the programme again with input
Uë : Every second element of U
answered Mar 26 at 14:27
ShaggyShaggy
19.1k21768
$endgroup$
Japt, 10 bytes
eUñ)?U:ßUë
Try it
eUñ)?U:ßUë :Implicit input of array U
e :Compare equality with
Uñ : U sorted
) :End compare
?U: :If true then return U else
ß :Run the programme again with input
Uë : Every second element of U
answered Mar 26 at 14:27
ShaggyShaggy
19.1k21768
edited Mar 26 at 15:54
answered Mar 26 at 14:27
ShaggyShaggy
19.1k21768
answered Mar 26 at 14:27
ShaggyShaggy
19.1k21768
answered Mar 26 at 14:27
ShaggyShaggy
19.1k21768
19.1k21768
add a comment |
add a comment |
$begingroup$
Gaia, 9 bytes
eo₌⟪e2%⟫↻
Try it online!
There's a bit of a bug in the Gaia parser, probably because it hasn't been updated in 2 years.
I expected ₌ to add the same value to the stack, but alas, it adds a string rather than an array, which caused me no end of confusion.
Explanation:
e | eval input as a list
↻ | until
o | the list is sorted
₌ | push additional copy (as a string):
⟪e | eval as a list
2%⟫ | and take every 2nd elementanswered Mar 26 at 19:39
GiuseppeGiuseppe
17.3k31152
$endgroup$
add a comment |
$begingroup$
Gaia, 9 bytes
eo₌⟪e2%⟫↻
Try it online!
There's a bit of a bug in the Gaia parser, probably because it hasn't been updated in 2 years.
I expected ₌ to add the same value to the stack, but alas, it adds a string rather than an array, which caused me no end of confusion.
Explanation:
e | eval input as a list
↻ | until
o | the list is sorted
₌ | push additional copy (as a string):
⟪e | eval as a list
2%⟫ | and take every 2nd elementanswered Mar 26 at 19:39
GiuseppeGiuseppe
17.3k31152
$endgroup$
add a comment |
$begingroup$
Gaia, 9 bytes
eo₌⟪e2%⟫↻
Try it online!
There's a bit of a bug in the Gaia parser, probably because it hasn't been updated in 2 years.
I expected ₌ to add the same value to the stack, but alas, it adds a string rather than an array, which caused me no end of confusion.
Explanation:
e | eval input as a list
↻ | until
o | the list is sorted
₌ | push additional copy (as a string):
⟪e | eval as a list
2%⟫ | and take every 2nd elementanswered Mar 26 at 19:39
GiuseppeGiuseppe
17.3k31152
$endgroup$
Gaia, 9 bytes
eo₌⟪e2%⟫↻
Try it online!
There's a bit of a bug in the Gaia parser, probably because it hasn't been updated in 2 years.
I expected ₌ to add the same value to the stack, but alas, it adds a string rather than an array, which caused me no end of confusion.
Explanation:
e | eval input as a list
↻ | until
o | the list is sorted
₌ | push additional copy (as a string):
⟪e | eval as a list
2%⟫ | and take every 2nd elementanswered Mar 26 at 19:39
GiuseppeGiuseppe
17.3k31152
answered Mar 26 at 19:39
GiuseppeGiuseppe
17.3k31152
answered Mar 26 at 19:39
GiuseppeGiuseppe
17.3k31152
answered Mar 26 at 19:39
GiuseppeGiuseppe
17.3k31152
17.3k31152
add a comment |
add a comment |
$begingroup$
Java (JDK), 102 bytes
n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}
There's already a C# answer, so I decided to try my hand on a Java answer.
Try it online!
answered Mar 27 at 1:50
Embodiment of IgnoranceEmbodiment of Ignorance
2,248126
$endgroup$
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
Mar 28 at 14:35
add a comment |
$begingroup$
Java (JDK), 102 bytes
n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}
There's already a C# answer, so I decided to try my hand on a Java answer.
Try it online!
answered Mar 27 at 1:50
Embodiment of IgnoranceEmbodiment of Ignorance
2,248126
$endgroup$
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
Mar 28 at 14:35
add a comment |
$begingroup$
Java (JDK), 102 bytes
n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}
There's already a C# answer, so I decided to try my hand on a Java answer.
Try it online!
answered Mar 27 at 1:50
Embodiment of IgnoranceEmbodiment of Ignorance
2,248126
$endgroup$
Java (JDK), 102 bytes
n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}
There's already a C# answer, so I decided to try my hand on a Java answer.
Try it online!
answered Mar 27 at 1:50
Embodiment of IgnoranceEmbodiment of Ignorance
2,248126
answered Mar 27 at 1:50
Embodiment of IgnoranceEmbodiment of Ignorance
2,248126
answered Mar 27 at 1:50
Embodiment of IgnoranceEmbodiment of Ignorance
2,248126
answered Mar 27 at 1:50
Embodiment of IgnoranceEmbodiment of Ignorance
2,248126
2,248126
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
Mar 28 at 14:35
add a comment |
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
Mar 28 at 14:35
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
Mar 28 at 14:35
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
Mar 28 at 14:35
add a comment |
$begingroup$
Husk, 6 bytes
ΩΛ<(←½
Try it online!
Explanation
ΩΛ<(←½
Ω Repeat until
Λ< all adjacent pairs are sorted (which means the list is sorted)
½ cut the list in two halves
← then keep the first half
answered Mar 27 at 5:10
LeoLeo
7,84811349
$endgroup$
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
Mar 27 at 20:11
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
Mar 27 at 22:51
$begingroup$
@MikeHoller As many other golfing languages, Husk uses a custom code page, in order to have access to more different characters: github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Leo
Mar 27 at 22:53
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
Mar 28 at 13:30
add a comment |
$begingroup$
Husk, 6 bytes
ΩΛ<(←½
Try it online!
Explanation
ΩΛ<(←½
Ω Repeat until
Λ< all adjacent pairs are sorted (which means the list is sorted)
½ cut the list in two halves
← then keep the first half
answered Mar 27 at 5:10
LeoLeo
7,84811349
$endgroup$
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
Mar 27 at 20:11
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
Mar 27 at 22:51
$begingroup$
@MikeHoller As many other golfing languages, Husk uses a custom code page, in order to have access to more different characters: github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Leo
Mar 27 at 22:53
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
Mar 28 at 13:30
add a comment |
$begingroup$
Husk, 6 bytes
ΩΛ<(←½
Try it online!
Explanation
ΩΛ<(←½
Ω Repeat until
Λ< all adjacent pairs are sorted (which means the list is sorted)
½ cut the list in two halves
← then keep the first half
answered Mar 27 at 5:10
LeoLeo
7,84811349
$endgroup$
Husk, 6 bytes
ΩΛ<(←½
Try it online!
Explanation
ΩΛ<(←½
Ω Repeat until
Λ< all adjacent pairs are sorted (which means the list is sorted)
½ cut the list in two halves
← then keep the first half
answered Mar 27 at 5:10
LeoLeo
7,84811349
answered Mar 27 at 5:10
LeoLeo
7,84811349
answered Mar 27 at 5:10
LeoLeo
7,84811349
answered Mar 27 at 5:10
LeoLeo
7,84811349
7,84811349
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
Mar 27 at 20:11
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
Mar 27 at 22:51
$begingroup$
@MikeHoller As many other golfing languages, Husk uses a custom code page, in order to have access to more different characters: github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Leo
Mar 27 at 22:53
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
Mar 28 at 13:30
add a comment |
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
Mar 27 at 20:11
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
Mar 27 at 22:51
$begingroup$
@MikeHoller As many other golfing languages, Husk uses a custom code page, in order to have access to more different characters: github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Leo
Mar 27 at 22:53
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
Mar 28 at 13:30
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
Mar 27 at 20:11
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
Mar 27 at 20:11
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
Mar 27 at 22:51
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
Mar 27 at 22:51
$begingroup$
@MikeHoller As many other golfing languages, Husk uses a custom code page, in order to have access to more different characters: github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Leo
Mar 27 at 22:53
$begingroup$
@MikeHoller As many other golfing languages, Husk uses a custom code page, in order to have access to more different characters: github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Leo
Mar 27 at 22:53
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
Mar 28 at 13:30
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
Mar 28 at 13:30
add a comment |
$begingroup$
Octave, 49 bytes
l=input('');while(~issorted(l))l=l(1:2:end);end;l
Try it online!
This was a journey where more boring is better. Note the two much more interesting entries below:
50 bytes
function l=q(l)if(~issorted(l))l=q(l(1:2:end));end
Try it online!
53 bytes
f(f=@(g)@(l){l,@()g(g)(l(1:2:end))}{2-issorted(l)}())
Try it online!
answered Mar 27 at 13:54
SanchisesSanchises
6,24712452
$endgroup$
add a comment |
$begingroup$
Octave, 49 bytes
l=input('');while(~issorted(l))l=l(1:2:end);end;l
Try it online!
This was a journey where more boring is better. Note the two much more interesting entries below:
50 bytes
function l=q(l)if(~issorted(l))l=q(l(1:2:end));end
Try it online!
53 bytes
f(f=@(g)@(l){l,@()g(g)(l(1:2:end))}{2-issorted(l)}())
Try it online!
answered Mar 27 at 13:54
SanchisesSanchises
6,24712452
$endgroup$
add a comment |
$begingroup$
Octave, 49 bytes
l=input('');while(~issorted(l))l=l(1:2:end);end;l
Try it online!
This was a journey where more boring is better. Note the two much more interesting entries below:
50 bytes
function l=q(l)if(~issorted(l))l=q(l(1:2:end));end
Try it online!
53 bytes
f(f=@(g)@(l){l,@()g(g)(l(1:2:end))}{2-issorted(l)}())
Try it online!
answered Mar 27 at 13:54
SanchisesSanchises
6,24712452
$endgroup$
Octave, 49 bytes
l=input('');while(~issorted(l))l=l(1:2:end);end;l
Try it online!
This was a journey where more boring is better. Note the two much more interesting entries below:
50 bytes
function l=q(l)if(~issorted(l))l=q(l(1:2:end));end
Try it online!
53 bytes
f(f=@(g)@(l){l,@()g(g)(l(1:2:end))}{2-issorted(l)}())
Try it online!
answered Mar 27 at 13:54
SanchisesSanchises
6,24712452
answered Mar 27 at 13:54
SanchisesSanchises
6,24712452
answered Mar 27 at 13:54
SanchisesSanchises
6,24712452
answered Mar 27 at 13:54
SanchisesSanchises
6,24712452
6,24712452
add a comment |
add a comment |
$begingroup$
VDM-SL, 99 bytes
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int
A full program to run might look like this:
functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
answered Mar 26 at 12:20
Expired DataExpired Data
4288
$endgroup$
add a comment |
$begingroup$
VDM-SL, 99 bytes
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int
A full program to run might look like this:
functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
answered Mar 26 at 12:20
Expired DataExpired Data
4288
$endgroup$
add a comment |
$begingroup$
VDM-SL, 99 bytes
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int
A full program to run might look like this:
functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
answered Mar 26 at 12:20
Expired DataExpired Data
4288
$endgroup$
VDM-SL, 99 bytes
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int
A full program to run might look like this:
functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
answered Mar 26 at 12:20
Expired DataExpired Data
4288
answered Mar 26 at 12:20
Expired DataExpired Data
4288
answered Mar 26 at 12:20
Expired DataExpired Data
4288
answered Mar 26 at 12:20
Expired DataExpired Data
4288
4288
add a comment |
add a comment |
$begingroup$
Pyth, 10 bytes
.W!SIHhc2Z
Try it online here. This removes the second half on each iteration, rounding down. To change it to remove the first half, rounding up, change the h to e.
.W!SIHhc2ZQ Q=eval(input())
Trailing Q inferred
!SIH Condition function - input variable is H
SIH Is H invariant under sorting?
! Logical not
hc2Z Iteration function - input variable is Z
c2Z Split Z into 2 halves, breaking ties to the left
h Take the first half
.W Q With initial value Q, execute iteration function while condition function is true
answered Mar 27 at 16:07
SokSok
4,147925
$endgroup$
add a comment |
$begingroup$
Pyth, 10 bytes
.W!SIHhc2Z
Try it online here. This removes the second half on each iteration, rounding down. To change it to remove the first half, rounding up, change the h to e.
.W!SIHhc2ZQ Q=eval(input())
Trailing Q inferred
!SIH Condition function - input variable is H
SIH Is H invariant under sorting?
! Logical not
hc2Z Iteration function - input variable is Z
c2Z Split Z into 2 halves, breaking ties to the left
h Take the first half
.W Q With initial value Q, execute iteration function while condition function is true
answered Mar 27 at 16:07
SokSok
4,147925
$endgroup$
add a comment |
$begingroup$
Pyth, 10 bytes
.W!SIHhc2Z
Try it online here. This removes the second half on each iteration, rounding down. To change it to remove the first half, rounding up, change the h to e.
.W!SIHhc2ZQ Q=eval(input())
Trailing Q inferred
!SIH Condition function - input variable is H
SIH Is H invariant under sorting?
! Logical not
hc2Z Iteration function - input variable is Z
c2Z Split Z into 2 halves, breaking ties to the left
h Take the first half
.W Q With initial value Q, execute iteration function while condition function is true
answered Mar 27 at 16:07
SokSok
4,147925
$endgroup$
Pyth, 10 bytes
.W!SIHhc2Z
Try it online here. This removes the second half on each iteration, rounding down. To change it to remove the first half, rounding up, change the h to e.
.W!SIHhc2ZQ Q=eval(input())
Trailing Q inferred
!SIH Condition function - input variable is H
SIH Is H invariant under sorting?
! Logical not
hc2Z Iteration function - input variable is Z
c2Z Split Z into 2 halves, breaking ties to the left
h Take the first half
.W Q With initial value Q, execute iteration function while condition function is true
answered Mar 27 at 16:07
SokSok
4,147925
answered Mar 27 at 16:07
SokSok
4,147925
answered Mar 27 at 16:07
SokSok
4,147925
answered Mar 27 at 16:07
SokSok
4,147925
4,147925
add a comment |
add a comment |
$begingroup$
Retina, 38 bytes
d+
*
/(_+),(?!1)/+`,_+(,?)
$1
_+
$.&
Try it online! Takes comma-separated numbers. Explanation:
d+
*
Convert to unary.
/(_+),(?!1)/+`
Repeat while the list is unsorted...
,_+(,?)
$1
... delete every even element.
_+
$.&
Convert to decimal.
answered Mar 26 at 15:01
NeilNeil
82.2k745178
$endgroup$
add a comment |
$begingroup$
Retina, 38 bytes
d+
*
/(_+),(?!1)/+`,_+(,?)
$1
_+
$.&
Try it online! Takes comma-separated numbers. Explanation:
d+
*
Convert to unary.
/(_+),(?!1)/+`
Repeat while the list is unsorted...
,_+(,?)
$1
... delete every even element.
_+
$.&
Convert to decimal.
answered Mar 26 at 15:01
NeilNeil
82.2k745178
$endgroup$
add a comment |
$begingroup$
Retina, 38 bytes
d+
*
/(_+),(?!1)/+`,_+(,?)
$1
_+
$.&
Try it online! Takes comma-separated numbers. Explanation:
d+
*
Convert to unary.
/(_+),(?!1)/+`
Repeat while the list is unsorted...
,_+(,?)
$1
... delete every even element.
_+
$.&
Convert to decimal.
answered Mar 26 at 15:01
NeilNeil
82.2k745178
$endgroup$
Retina, 38 bytes
d+
*
/(_+),(?!1)/+`,_+(,?)
$1
_+
$.&
Try it online! Takes comma-separated numbers. Explanation:
d+
*
Convert to unary.
/(_+),(?!1)/+`
Repeat while the list is unsorted...
,_+(,?)
$1
... delete every even element.
_+
$.&
Convert to decimal.
answered Mar 26 at 15:01
NeilNeil
82.2k745178
answered Mar 26 at 15:01
NeilNeil
82.2k745178
answered Mar 26 at 15:01
NeilNeil
82.2k745178
answered Mar 26 at 15:01
NeilNeil
82.2k745178
82.2k745178
add a comment |
add a comment |
$begingroup$
C (gcc), 66 bytes
Snaps off the second half of the list each iteration (n/2+1 elements if the length is odd).
Try it online!
Takes input as a pointer to the start of an array of int followed by its length. Outputs by returning the new length of the array (sorts in-place).
t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}
Ungolfed version:
t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
l: // jump label, will be goto'ed after each snap
for(i = 0; i < n - 1; ) { // go through the whole array …
if(a[i] > a[++i]) { // … if two elements are in the wrong order …
n /= 2; // … snap off the second half …
goto l; // … and start over
}
}
a = n; // implicitly return the new length
}
answered Mar 27 at 15:42
O.O.BalanceO.O.Balance
1,3091418
$endgroup$
add a comment |
$begingroup$
C (gcc), 66 bytes
Snaps off the second half of the list each iteration (n/2+1 elements if the length is odd).
Try it online!
Takes input as a pointer to the start of an array of int followed by its length. Outputs by returning the new length of the array (sorts in-place).
t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}
Ungolfed version:
t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
l: // jump label, will be goto'ed after each snap
for(i = 0; i < n - 1; ) { // go through the whole array …
if(a[i] > a[++i]) { // … if two elements are in the wrong order …
n /= 2; // … snap off the second half …
goto l; // … and start over
}
}
a = n; // implicitly return the new length
}
answered Mar 27 at 15:42
O.O.BalanceO.O.Balance
1,3091418
$endgroup$
add a comment |
$begingroup$
C (gcc), 66 bytes
Snaps off the second half of the list each iteration (n/2+1 elements if the length is odd).
Try it online!
Takes input as a pointer to the start of an array of int followed by its length. Outputs by returning the new length of the array (sorts in-place).
t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}
Ungolfed version:
t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
l: // jump label, will be goto'ed after each snap
for(i = 0; i < n - 1; ) { // go through the whole array …
if(a[i] > a[++i]) { // … if two elements are in the wrong order …
n /= 2; // … snap off the second half …
goto l; // … and start over
}
}
a = n; // implicitly return the new length
}
answered Mar 27 at 15:42
O.O.BalanceO.O.Balance
1,3091418
$endgroup$
C (gcc), 66 bytes
Snaps off the second half of the list each iteration (n/2+1 elements if the length is odd).
Try it online!
Takes input as a pointer to the start of an array of int followed by its length. Outputs by returning the new length of the array (sorts in-place).
t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}
Ungolfed version:
t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
l: // jump label, will be goto'ed after each snap
for(i = 0; i < n - 1; ) { // go through the whole array …
if(a[i] > a[++i]) { // … if two elements are in the wrong order …
n /= 2; // … snap off the second half …
goto l; // … and start over
}
}
a = n; // implicitly return the new length
}
answered Mar 27 at 15:42
O.O.BalanceO.O.Balance
1,3091418
answered Mar 27 at 15:42
O.O.BalanceO.O.Balance
1,3091418
answered Mar 27 at 15:42
O.O.BalanceO.O.Balance
1,3091418
answered Mar 27 at 15:42
O.O.BalanceO.O.Balance
1,3091418
1,3091418
add a comment |
add a comment |
$begingroup$
Clojure, 65 bytes
(defn t[l](if(apply <= l)l(recur(take(/(count l)2)(shuffle l)))))
Try it online!
answered Mar 27 at 19:27
Ethan McCueEthan McCue
1212
$endgroup$
$begingroup$
45?
$endgroup$
– ASCII-only
Mar 28 at 6:36
$begingroup$
43? 42?
$endgroup$
– ASCII-only
Mar 28 at 6:42
add a comment |
$begingroup$
Clojure, 65 bytes
(defn t[l](if(apply <= l)l(recur(take(/(count l)2)(shuffle l)))))
Try it online!
answered Mar 27 at 19:27
Ethan McCueEthan McCue
1212
$endgroup$
$begingroup$
45?
$endgroup$
– ASCII-only
Mar 28 at 6:36
$begingroup$
43? 42?
$endgroup$
– ASCII-only
Mar 28 at 6:42
add a comment |
$begingroup$
Clojure, 65 bytes
(defn t[l](if(apply <= l)l(recur(take(/(count l)2)(shuffle l)))))
Try it online!
answered Mar 27 at 19:27
Ethan McCueEthan McCue
1212
$endgroup$
Clojure, 65 bytes
(defn t[l](if(apply <= l)l(recur(take(/(count l)2)(shuffle l)))))
Try it online!
answered Mar 27 at 19:27
Ethan McCueEthan McCue
1212
answered Mar 27 at 19:27
Ethan McCueEthan McCue
1212
answered Mar 27 at 19:27
Ethan McCueEthan McCue
1212
answered Mar 27 at 19:27
Ethan McCueEthan McCue
1212
1212
$begingroup$
45?
$endgroup$
– ASCII-only
Mar 28 at 6:36
$begingroup$
43? 42?
$endgroup$
– ASCII-only
Mar 28 at 6:42
add a comment |
$begingroup$
45?
$endgroup$
– ASCII-only
Mar 28 at 6:36
$begingroup$
43? 42?
$endgroup$
– ASCII-only
Mar 28 at 6:42
$begingroup$
45?
$endgroup$
– ASCII-only
Mar 28 at 6:36
$begingroup$
45?
$endgroup$
– ASCII-only
Mar 28 at 6:36
$begingroup$
43? 42?
$endgroup$
– ASCII-only
Mar 28 at 6:42
$begingroup$
43? 42?
$endgroup$
– ASCII-only
Mar 28 at 6:42
add a comment |
$begingroup$
MATLAB, 57 bytes
Callable as f(a), where a=[1,2,3,4,5]
f=@(x)eval('while~isequal(sort(x),x);x=x(1:end/2);end;x')
Example of usage:
>> a = [1, 2, 4, 3, 5];
>> f(a)
a =
1 2
answered Mar 28 at 23:05
aaaaaaaaaaaa
3116
$endgroup$
add a comment |
$begingroup$
MATLAB, 57 bytes
Callable as f(a), where a=[1,2,3,4,5]
f=@(x)eval('while~isequal(sort(x),x);x=x(1:end/2);end;x')
Example of usage:
>> a = [1, 2, 4, 3, 5];
>> f(a)
a =
1 2
answered Mar 28 at 23:05
aaaaaaaaaaaa
3116
$endgroup$
add a comment |
$begingroup$
MATLAB, 57 bytes
Callable as f(a), where a=[1,2,3,4,5]
f=@(x)eval('while~isequal(sort(x),x);x=x(1:end/2);end;x')
Example of usage:
>> a = [1, 2, 4, 3, 5];
>> f(a)
a =
1 2
answered Mar 28 at 23:05
aaaaaaaaaaaa
3116
$endgroup$
MATLAB, 57 bytes
Callable as f(a), where a=[1,2,3,4,5]
f=@(x)eval('while~isequal(sort(x),x);x=x(1:end/2);end;x')
Example of usage:
>> a = [1, 2, 4, 3, 5];
>> f(a)
a =
1 2
answered Mar 28 at 23:05
aaaaaaaaaaaa
3116
answered Mar 28 at 23:05
aaaaaaaaaaaa
3116
answered Mar 28 at 23:05
aaaaaaaaaaaa
3116
answered Mar 28 at 23:05
aaaaaaaaaaaa
3116
3116
add a comment |
add a comment |
$begingroup$
Zsh, 51 bytes
56 (+5) to call the function, 47 (-4) if not a function, but saved as an executable with a proper #! header (replace the recursive f call with $0).
f(){[ "$*" = "${${(n)@}[*]}" ]&&<<<$@||f $@[0,#/2]}
Try it online!
There is no "is-sorted" builtin in zsh, but there are some "sort-array" builtins. We use the parameter expansion flag n, but o or i would also work. We then have to use [*] and quote to induce joining. This is shorter than alternatives (like zipping them together and comparing pairwise).
answered 2 days ago
GammaFunctionGammaFunction
2616
$endgroup$
add a comment |
$begingroup$
Zsh, 51 bytes
56 (+5) to call the function, 47 (-4) if not a function, but saved as an executable with a proper #! header (replace the recursive f call with $0).
f(){[ "$*" = "${${(n)@}[*]}" ]&&<<<$@||f $@[0,#/2]}
Try it online!
There is no "is-sorted" builtin in zsh, but there are some "sort-array" builtins. We use the parameter expansion flag n, but o or i would also work. We then have to use [*] and quote to induce joining. This is shorter than alternatives (like zipping them together and comparing pairwise).
answered 2 days ago
GammaFunctionGammaFunction
2616
$endgroup$
add a comment |
$begingroup$
Zsh, 51 bytes
56 (+5) to call the function, 47 (-4) if not a function, but saved as an executable with a proper #! header (replace the recursive f call with $0).
f(){[ "$*" = "${${(n)@}[*]}" ]&&<<<$@||f $@[0,#/2]}
Try it online!
There is no "is-sorted" builtin in zsh, but there are some "sort-array" builtins. We use the parameter expansion flag n, but o or i would also work. We then have to use [*] and quote to induce joining. This is shorter than alternatives (like zipping them together and comparing pairwise).
answered 2 days ago
GammaFunctionGammaFunction
2616
$endgroup$
Zsh, 51 bytes
56 (+5) to call the function, 47 (-4) if not a function, but saved as an executable with a proper #! header (replace the recursive f call with $0).
f(){[ "$*" = "${${(n)@}[*]}" ]&&<<<$@||f $@[0,#/2]}
Try it online!
There is no "is-sorted" builtin in zsh, but there are some "sort-array" builtins. We use the parameter expansion flag n, but o or i would also work. We then have to use [*] and quote to induce joining. This is shorter than alternatives (like zipping them together and comparing pairwise).
answered 2 days ago
GammaFunctionGammaFunction
2616
edited yesterday
answered 2 days ago
GammaFunctionGammaFunction
2616
answered 2 days ago
GammaFunctionGammaFunction
2616
answered 2 days ago
GammaFunctionGammaFunction
2616
2616
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f182221%2fimplement-the-thanos-sorting-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
14
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
Mar 26 at 14:32
9
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
Mar 26 at 14:47
10
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
Mar 26 at 14:57
5
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
Mar 26 at 18:06
7
$begingroup$
Since there is so much freedom on how to remove half the elements, this could simplify to:
Return the first out of order element. If there is no out of order element, return the list.$endgroup$
– Ben J
Mar 26 at 19:34