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
$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
$endgroup$
12
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
2 days ago
6
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
2 days ago
9
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
2 days ago
5
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
2 days ago
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
2 days ago
|
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
$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
edited 2 days ago
vrwim
asked 2 days ago
vrwimvrwim
1,13621016
1,13621016
12
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
2 days ago
6
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
2 days ago
9
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
2 days ago
5
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
2 days ago
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
2 days ago
|
show 11 more comments
12
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
2 days ago
6
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
2 days ago
9
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
2 days ago
5
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
2 days ago
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
2 days ago
12
12
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
2 days ago
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
2 days ago
6
6
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
2 days ago
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
2 days ago
9
9
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
2 days ago
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
2 days ago
5
5
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
2 days ago
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
2 days ago
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
2 days ago
$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
2 days ago
|
show 11 more comments
26 Answers
26
active
oldest
votes
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
$endgroup$
2
$begingroup$
is.unsorted
rather thanany(...)
would also be 41 bytes.
$endgroup$
– Giuseppe
2 days ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
2 days ago
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
$endgroup$
2
$begingroup$
40 bytes
$endgroup$
– Jo King
2 days ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)
must be> sorted(t)
.
$endgroup$
– Quuxplusone
2 days ago
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
$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
$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
2 days ago
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
yesterday
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
$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 closed
error after returning the stream
$endgroup$
– Embodiment of Ignorance
2 days ago
$begingroup$
@EmbodimentofIgnorance this happens becausereduce
is a terminal operation that closes the stream. You won't ever be able to callreduce
twice on the same stream. You can create a new stream, though.
$endgroup$
– Olivier Grégoire
yesterday
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
yesterday
$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
yesterday
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
13 hours ago
add a comment |
$begingroup$
JavaScript (ES6), 49 bytes
Removes every 2nd element, starting with either the first or the second one depending on the parity of the first unsorted element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>p++&1)):a
Try it online!
$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!
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 30 bytes
#//.x_/;Sort@x!=x:>x[[;;;;2]]&
Try it online!
@Doorknob saved 12 bytes
$endgroup$
1
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (x[[;;;;2]]
).
$endgroup$
– Doorknob♦
22 hours ago
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
15 hours ago
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
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 it's 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
$endgroup$
3
$begingroup$
You can useι
instead of2ä
if you switch to a keep every other element strategy.
$endgroup$
– Emigna
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!
$endgroup$
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
2 days ago
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.
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
$endgroup$
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
$endgroup$
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
2 days ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
2 days ago
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
$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 element
$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!
$endgroup$
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
11 hours ago
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
$endgroup$
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
yesterday
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
yesterday
$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
yesterday
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
12 hours ago
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!
$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
New contributor
$endgroup$
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Riker
20 hours ago
$begingroup$
56
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
57 :(
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
55
$endgroup$
– ASCII-only
20 hours ago
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])
$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
$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.
$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
}
$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!
$endgroup$
$begingroup$
45?
$endgroup$
– ASCII-only
19 hours ago
$begingroup$
43? 42?
$endgroup$
– ASCII-only
19 hours ago
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
$endgroup$
add a comment |
Your Answer
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
26 Answers
26
active
oldest
votes
26 Answers
26
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!
$endgroup$
2
$begingroup$
is.unsorted
rather thanany(...)
would also be 41 bytes.
$endgroup$
– Giuseppe
2 days ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
2 days ago
add a comment |
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
$endgroup$
2
$begingroup$
is.unsorted
rather thanany(...)
would also be 41 bytes.
$endgroup$
– Giuseppe
2 days ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
2 days ago
add a comment |
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
$endgroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered 2 days ago
Kirill L.Kirill L.
5,9131526
5,9131526
2
$begingroup$
is.unsorted
rather thanany(...)
would also be 41 bytes.
$endgroup$
– Giuseppe
2 days ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
2 days ago
add a comment |
2
$begingroup$
is.unsorted
rather thanany(...)
would also be 41 bytes.
$endgroup$
– Giuseppe
2 days ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
2 days ago
2
2
$begingroup$
is.unsorted
rather than any(...)
would also be 41 bytes.$endgroup$
– Giuseppe
2 days ago
$begingroup$
is.unsorted
rather than any(...)
would also be 41 bytes.$endgroup$
– Giuseppe
2 days ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
2 days ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
2 days ago
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
$endgroup$
2
$begingroup$
40 bytes
$endgroup$
– Jo King
2 days ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)
must be> sorted(t)
.
$endgroup$
– Quuxplusone
2 days ago
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
$endgroup$
2
$begingroup$
40 bytes
$endgroup$
– Jo King
2 days ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)
must be> sorted(t)
.
$endgroup$
– Quuxplusone
2 days ago
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
$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
edited 2 days ago
answered 2 days ago
Sara JSara J
485210
485210
2
$begingroup$
40 bytes
$endgroup$
– Jo King
2 days ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)
must be> sorted(t)
.
$endgroup$
– Quuxplusone
2 days ago
add a comment |
2
$begingroup$
40 bytes
$endgroup$
– Jo King
2 days ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)
must be> sorted(t)
.
$endgroup$
– Quuxplusone
2 days ago
2
2
$begingroup$
40 bytes
$endgroup$
– Jo King
2 days ago
$begingroup$
40 bytes
$endgroup$
– Jo King
2 days ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation
!= sorted(t)
must be > sorted(t)
.$endgroup$
– Quuxplusone
2 days ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation
!= sorted(t)
must be > sorted(t)
.$endgroup$
– Quuxplusone
2 days ago
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
$endgroup$
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
$endgroup$
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
$endgroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered 2 days ago
TFeldTFeld
16.2k21450
16.2k21450
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
$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
$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
$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 2 days ago
Jo KingJo King
25.7k362129
25.7k362129
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
2 days ago
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
yesterday
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
2 days ago
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
yesterday
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 2 days ago
community wiki
2 revs
ais523
9
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
2 days ago
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
yesterday
add a comment |
9
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
2 days ago
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
yesterday
9
9
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
2 days ago
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
2 days ago
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
yesterday
$begingroup$
@djechlin the infinity byte is why you must go for the head and especially the jaw.
$endgroup$
– The Great Duck
yesterday
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
$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 closed
error after returning the stream
$endgroup$
– Embodiment of Ignorance
2 days ago
$begingroup$
@EmbodimentofIgnorance this happens becausereduce
is a terminal operation that closes the stream. You won't ever be able to callreduce
twice on the same stream. You can create a new stream, though.
$endgroup$
– Olivier Grégoire
yesterday
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
yesterday
$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
yesterday
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
13 hours ago
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
$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 closed
error after returning the stream
$endgroup$
– Embodiment of Ignorance
2 days ago
$begingroup$
@EmbodimentofIgnorance this happens becausereduce
is a terminal operation that closes the stream. You won't ever be able to callreduce
twice on the same stream. You can create a new stream, though.
$endgroup$
– Olivier Grégoire
yesterday
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
yesterday
$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
yesterday
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
13 hours ago
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
$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
edited yesterday
answered 2 days ago
Kevin CruijssenKevin Cruijssen
41.8k568217
41.8k568217
$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 closed
error after returning the stream
$endgroup$
– Embodiment of Ignorance
2 days ago
$begingroup$
@EmbodimentofIgnorance this happens becausereduce
is a terminal operation that closes the stream. You won't ever be able to callreduce
twice on the same stream. You can create a new stream, though.
$endgroup$
– Olivier Grégoire
yesterday
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
yesterday
$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
yesterday
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
13 hours ago
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 closed
error after returning the stream
$endgroup$
– Embodiment of Ignorance
2 days ago
$begingroup$
@EmbodimentofIgnorance this happens becausereduce
is a terminal operation that closes the stream. You won't ever be able to callreduce
twice on the same stream. You can create a new stream, though.
$endgroup$
– Olivier Grégoire
yesterday
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
yesterday
$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
yesterday
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
13 hours ago
$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
2 days ago
$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
2 days ago
$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
yesterday
$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
yesterday
1
1
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
yesterday
$begingroup$
97 bytes
$endgroup$
– Olivier Grégoire
yesterday
$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
yesterday
$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
yesterday
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
13 hours ago
$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
13 hours ago
add a comment |
$begingroup$
JavaScript (ES6), 49 bytes
Removes every 2nd element, starting with either the first or the second one depending on the parity of the first unsorted element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>p++&1)):a
Try it online!
$endgroup$
add a comment |
$begingroup$
JavaScript (ES6), 49 bytes
Removes every 2nd element, starting with either the first or the second one depending on the parity of the first unsorted element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>p++&1)):a
Try it online!
$endgroup$
add a comment |
$begingroup$
JavaScript (ES6), 49 bytes
Removes every 2nd element, starting with either the first or the second one depending on the parity of the first unsorted element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>p++&1)):a
Try it online!
$endgroup$
JavaScript (ES6), 49 bytes
Removes every 2nd element, starting with either the first or the second one depending on the parity of the first unsorted element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>p++&1)):a
Try it online!
edited 2 days ago
answered 2 days ago
ArnauldArnauld
79.9k797330
79.9k797330
add a comment |
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!
$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!
$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!
$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 2 days ago
Expired DataExpired Data
4186
4186
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
$endgroup$
1
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (x[[;;;;2]]
).
$endgroup$
– Doorknob♦
22 hours ago
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
15 hours ago
add a comment |
$begingroup$
Wolfram Language (Mathematica), 30 bytes
#//.x_/;Sort@x!=x:>x[[;;;;2]]&
Try it online!
@Doorknob saved 12 bytes
$endgroup$
1
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (x[[;;;;2]]
).
$endgroup$
– Doorknob♦
22 hours ago
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
15 hours ago
add a comment |
$begingroup$
Wolfram Language (Mathematica), 30 bytes
#//.x_/;Sort@x!=x:>x[[;;;;2]]&
Try it online!
@Doorknob saved 12 bytes
$endgroup$
Wolfram Language (Mathematica), 30 bytes
#//.x_/;Sort@x!=x:>x[[;;;;2]]&
Try it online!
@Doorknob saved 12 bytes
edited 15 hours ago
answered 2 days ago
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♦
22 hours ago
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
15 hours 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♦
22 hours ago
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
15 hours ago
1
1
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (
x[[;;;;2]]
).$endgroup$
– Doorknob♦
22 hours ago
$begingroup$
Instead of taking the first half, you could save some bytes by taking every other element (
x[[;;;;2]]
).$endgroup$
– Doorknob♦
22 hours ago
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
15 hours ago
$begingroup$
@Doorknob yes of course...
$endgroup$
– J42161217
15 hours ago
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
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 it's 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
$endgroup$
3
$begingroup$
You can useι
instead of2ä
if you switch to a keep every other element strategy.
$endgroup$
– Emigna
2 days ago
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
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 it's 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
$endgroup$
3
$begingroup$
You can useι
instead of2ä
if you switch to a keep every other element strategy.
$endgroup$
– Emigna
2 days ago
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
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 it's 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
$endgroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
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 it's 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
edited 2 days ago
answered 2 days ago
Kevin CruijssenKevin Cruijssen
41.8k568217
41.8k568217
3
$begingroup$
You can useι
instead of2ä
if you switch to a keep every other element strategy.
$endgroup$
– Emigna
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
2 days ago
3
3
$begingroup$
You can use
ι
instead of 2ä
if you switch to a keep every other element strategy.$endgroup$
– Emigna
2 days ago
$begingroup$
You can use
ι
instead of 2ä
if you switch to a keep every other element strategy.$endgroup$
– Emigna
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!
$endgroup$
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
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!
$endgroup$
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
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!
$endgroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered 2 days ago
G BG B
8,1261429
8,1261429
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
2 days ago
add a comment |
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
2 days ago
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
2 days ago
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
2 days ago
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.
$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.
$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.
$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.
edited yesterday
answered 2 days ago
TauTau
686211
686211
add a comment |
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
$endgroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered 2 days ago
Erik the OutgolferErik the Outgolfer
32.9k429106
32.9k429106
add a comment |
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
$endgroup$
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
2 days ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
2 days ago
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
$endgroup$
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
2 days ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
2 days ago
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
$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
edited 2 days ago
answered 2 days ago
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
2 days ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
2 days ago
add a comment |
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
2 days ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
2 days ago
2
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
2 days ago
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
2 days ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
2 days ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
2 days ago
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
$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
$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
$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
edited 2 days ago
answered 2 days ago
ShaggyShaggy
19.1k21667
19.1k21667
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 element
$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 element
$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 element
$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 element
answered 2 days ago
GiuseppeGiuseppe
17.2k31152
17.2k31152
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!
$endgroup$
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
11 hours ago
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!
$endgroup$
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
11 hours ago
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!
$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 2 days ago
Embodiment of IgnoranceEmbodiment of Ignorance
2,248126
2,248126
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
11 hours ago
add a comment |
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
11 hours ago
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
11 hours ago
$begingroup$
Time to try F# :)
$endgroup$
– aloisdg
11 hours ago
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
$endgroup$
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
yesterday
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
yesterday
$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
yesterday
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
12 hours ago
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
$endgroup$
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
yesterday
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
yesterday
$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
yesterday
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
12 hours ago
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
$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 yesterday
LeoLeo
7,84811349
7,84811349
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
yesterday
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
yesterday
$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
yesterday
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
12 hours ago
add a comment |
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
yesterday
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
yesterday
$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
yesterday
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
12 hours ago
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
yesterday
$begingroup$
This is 11 bytes, not 6. › echo -n "ΩΛ<(←½" | wc --bytes 11
$endgroup$
– Mike Holler
yesterday
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
yesterday
$begingroup$
@MikeHoller github.com/barbuz/Husk/wiki/Codepage
$endgroup$
– Xan
yesterday
$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
yesterday
$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
yesterday
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
12 hours ago
$begingroup$
Thank you, I learned something today :)
$endgroup$
– Mike Holler
12 hours ago
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!
$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!
$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!
$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 yesterday
SanchisesSanchises
6,24712452
6,24712452
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
New contributor
$endgroup$
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Riker
20 hours ago
$begingroup$
56
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
57 :(
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
55
$endgroup$
– ASCII-only
20 hours ago
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
New contributor
$endgroup$
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Riker
20 hours ago
$begingroup$
56
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
57 :(
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
55
$endgroup$
– ASCII-only
20 hours ago
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
New contributor
$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
New contributor
edited 1 hour ago
New contributor
answered 21 hours ago
SacheraSachera
212
212
New contributor
New contributor
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Riker
20 hours ago
$begingroup$
56
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
57 :(
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
55
$endgroup$
– ASCII-only
20 hours ago
add a comment |
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Riker
20 hours ago
$begingroup$
56
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
57 :(
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
55
$endgroup$
– ASCII-only
20 hours ago
1
1
$begingroup$
Welcome to PPCG!
$endgroup$
– Riker
20 hours ago
$begingroup$
Welcome to PPCG!
$endgroup$
– Riker
20 hours ago
$begingroup$
56
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
56
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
57 :(
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
57 :(
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
55
$endgroup$
– ASCII-only
20 hours ago
$begingroup$
55
$endgroup$
– ASCII-only
20 hours ago
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])
$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])
$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])
$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 2 days ago
Expired DataExpired Data
4186
4186
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
$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
$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
$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 yesterday
SokSok
4,127925
4,127925
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.
$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.
$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.
$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 2 days ago
NeilNeil
82.1k745178
82.1k745178
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
}
$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
}
$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
}
$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 yesterday
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!
$endgroup$
$begingroup$
45?
$endgroup$
– ASCII-only
19 hours ago
$begingroup$
43? 42?
$endgroup$
– ASCII-only
19 hours ago
add a comment |
$begingroup$
Clojure, 65 bytes
(defn t[l](if(apply <= l)l(recur(take(/(count l)2)(shuffle l)))))
Try it online!
$endgroup$
$begingroup$
45?
$endgroup$
– ASCII-only
19 hours ago
$begingroup$
43? 42?
$endgroup$
– ASCII-only
19 hours ago
add a comment |
$begingroup$
Clojure, 65 bytes
(defn t[l](if(apply <= l)l(recur(take(/(count l)2)(shuffle l)))))
Try it online!
$endgroup$
Clojure, 65 bytes
(defn t[l](if(apply <= l)l(recur(take(/(count l)2)(shuffle l)))))
Try it online!
answered yesterday
Ethan McCueEthan McCue
1212
1212
$begingroup$
45?
$endgroup$
– ASCII-only
19 hours ago
$begingroup$
43? 42?
$endgroup$
– ASCII-only
19 hours ago
add a comment |
$begingroup$
45?
$endgroup$
– ASCII-only
19 hours ago
$begingroup$
43? 42?
$endgroup$
– ASCII-only
19 hours ago
$begingroup$
45?
$endgroup$
– ASCII-only
19 hours ago
$begingroup$
45?
$endgroup$
– ASCII-only
19 hours ago
$begingroup$
43? 42?
$endgroup$
– ASCII-only
19 hours ago
$begingroup$
43? 42?
$endgroup$
– ASCII-only
19 hours ago
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
$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
$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
$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 3 hours ago
aaaaaaaaaaaa
3116
3116
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
12
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
2 days ago
6
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
2 days ago
9
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
2 days ago
5
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
2 days ago
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
2 days ago