Skip to content

Instantly share code, notes, and snippets.

@StaticallyTypedRice
Last active March 18, 2024 16:24
Show Gist options
  • Save StaticallyTypedRice/b4503d567e05721c1c5122b70d5ce41b to your computer and use it in GitHub Desktop.
Save StaticallyTypedRice/b4503d567e05721c1c5122b70d5ce41b to your computer and use it in GitHub Desktop.
Thanos Sort
import random
import typing.List
def thanos_sort(a: List[int]) -> List[int]:
'''Removes half of the list until it's perfectly balanced, like all things should be.'''
def _perfectly_balanced(a: List[int]) -> bool:
like_all_things_should_be = True
for i in range(1, len(a)):
if a[i] < a[i-1]:
like_all_things_should_be = False
break
return like_all_things_should_be
def _snap(a: List[int]) -> List[int]:
numbers_that_dont_feel_so_good = random.sample(range(len(a)), round(len(a)/2, 0))
b = []
for i in range(len(a)):
if i not in numbers_that_dont_feel_so_good:
b.append(a[i])
return b
while not _perfectly_balanced(a):
a = _snap(a)
return a
'''LICENSE:
The MIT License (MIT)
Copyright (c) 2019 Richie Zhang
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
'''
@ppshobi
Copy link

ppshobi commented Mar 26, 2019

Ha ha... this is actually fun sort

@Mm2PL
Copy link

Mm2PL commented Mar 26, 2019

You are missing a colon on line 11 and an import (typing.List). Also don't calling List wont help. Use the square brackets (like def func_name(arg_name: List[str]) -> List[int]:)

@StaticallyTypedRice
Copy link
Author

You are missing a colon on line 11 and an import (typing.List). Also don't calling List wont help. Use the square brackets (like def func_name(arg_name: List[str]) -> List[int]:)

Fixed. Thanks!!

@j3pic
Copy link

j3pic commented Mar 27, 2019

You have a bug: If a number appears more than once in the list and that number doesn't feel so good, then both copies of the number get removed, leading to more than half of the array being wiped from existence.

@palmersaccount
Copy link

Is there potentially a way to only half the data in the list once? As I see it, this script halves the list until there is only one element left. I would like to use this to "snap" half of an image, but this version doesn't really work well for it.

@StaticallyTypedRice
Copy link
Author

StaticallyTypedRice commented Apr 21, 2019

Is there potentially a way to only half the data in the list once? As I see it, this script halves the list until there is only one element left. I would like to use this to "snap" half of an image, but this version doesn't really work well for it.

One way might be to use random.sample on the list directly, though I'm not sure what that is doing internally or if it's actually more efficient than my implementation.

@palmersaccount
Copy link

palmersaccount commented Apr 29, 2019

One way might be to use random.sample on the list directly, though I'm not sure what that is doing internally or if it's actually more efficient than my implementation.

I'm using this for a picture using Pillow, and I ended up figuring it out using Numpy arrays. I flattened the 3d array for the pixels into a 2d array of (x, y) coordinates for the 3d array, and sampled half of them. If you want to see, I've got it in my repo.

@gt1459
Copy link

gt1459 commented Sep 8, 2019

`def find():
a = int(input())
if a%2==0 and a<=16 and a>=1:
x = input()
print(x)
l = splitint(x)
print(l)
p= lcheck(l)
print(p)
r = rcheck(l)
print(r)
return max(p,r)

else:
    print("enter the array length correctly")
    find()

def lcheck(l):
n = len(l)
m= sorted(l)
if l==m:
return len(l)
else:
n=n//2
l=l[:n-1]
if len(l)>1:
return lcheck(l)
else:
return 1
def rcheck(l):
n = len(l)
m= sorted(l)
if l==m:
return len(l)
else:
n=n//2
l=l[n:]
if len(l)>1:
return rcheck(l)
else:
return 1
def splitint(x):
l = x.split()
l = list(map(int,l))
return l
find()`

this is my attempt... there are many problems in this. But i am tired of giving more time to it.

@Rudxain
Copy link

Rudxain commented Oct 14, 2022

I've got it in my repo.

@wolfembers The link is broken now. I tried searching the commit history but didn't find it. Was the file deleted or renamed?

@palmersaccount
Copy link

palmersaccount commented Oct 14, 2022 via email

@Rudxain
Copy link

Rudxain commented Oct 14, 2022

Good morning. I removed all the separate files and consolidated them all into the main pixelsort.py file. It is contained as a function in there. Fair warning though, I haven’t updated that side of the repo in a couple years. Expect some errors. Thanks for checking it out though! You’re the first user that’s reached out. Have a good one!

Thank you for the info. And don't worry, I'll be careful!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment