hello everyone
the event where you have to guess who wrote code will now start!
for this first round, the challenge is: sort a list of integers.
competition rules and information:
code must be valid python 3
maximum size of each entry is 20kb
i will run your code by passing the input to the function entry defined by your program, and i will interpret whatever that function returns as your output. so if your code doesn't provide a function called entry it obviously won't work.
your submission can't do anything to damage or mess with the machine on which i run this, or anything else obviously not wanted. you can do basically anything else you want though, as long as the output is valid.
for this round, the input will be passed as a normal python list of normal python integers, and i expect your output to be the same. you can assume all the integers are non-negative.
if you have any questions or feedback please ask me.
good luck!
fromtypingimportList# Sort a list of integersdefentry(data:List[str]):swap=Falsefori,(one,two)inenumerate(zip(data,data[1:])):iftwo>one:# Swaps itemsdata[i],data[i+1]=data[i+1],data[i]swap=True# Checks if we need to recurifswap:returnentry(data)else:returndata.reverse()ordata
# good sort in python# copyright (c) 2021# all rights reserved# do not distribute!importrandomdefentry(apiolist):# I use algorithms!fromcopyimportdeepcopy,copyimportcopyaha=deepcopy(copy.deepcopy(apiolist))# deepercopy# Okay! Sort attempt one!Listsorted_yesSir=copy.copy(copy.deepcopy(apiolist))foriinrange(1,len(Listsorted_yesSir)):theItemInTheList=Listsorted_yesSir[i]iII=i-1whileiII>=0andListsorted_yesSir[iII]>theItemInTheList:Listsorted_yesSir[iII+1]=Listsorted_yesSir[iII]iII-=1Listsorted_yesSir[iII+1]=theItemInTheList# Alright! Sort attempt two !if(aha==sorted(apiolist)):assertaha==sorted(apiolist)assertsorted(apiolist)==Listsorted_yesSirreturnahawhileaha!=Listsorted_yesSir:random.shuffle(aha)# Do some checks to enusre we succeeded.!assertaha!=apiolistassertstr(aha)!=str(apiolist)thanks=ahalist.sort(thanks)assertthanks==ahauwu=apiolistlist.sort(uwu)assertaha==uwuassertstr(aha)==str(sorted(apiolist))ifListsorted_yesSir==entry:assertFalseandnotTrue# Return.returnaha
importsqlite3defentry(input):values=','.join([f"({x})"forxininput])cur=sqlite3.connect("sort.db").cursor()cur.execute(f"select val from\ (select 0 as val union all values {values}) input\ order by val limit -1 offset 1")return[row[0]forrowincur.fetchall()]
fromdataclassesimportdataclass,fieldimportstringimportfunctoolsimportoperatorimportrandom@dataclassclassSymbol:name:str@dataclassclassQuote:content:any# Raised in case of fatal parsing errors, i.e. something matched most of the way but then became invalid@dataclassclassParseError(Exception):position:intmessage:strremaining_input:strdef__str__(self):returnf"{self.message} at position {self.position}"# Raised if the current parser cannot run on the current inputclassNoParse(Exception):pass# approximate grammar# symbol ::= [^'0-9()" \t\n][^'()" \t\n]+# int ::= -? [0-9]+# str ::= '"' [^"]+ '"'# whitespace ::= [ \t\n]+# list ::= '(' (expr whitespace)+ ')'# quoted ::= ' expr# expr ::= symbol | int | str | list | quoted# Recursive descent parserclassParser:def__init__(self,s):self.s=sself.pos=0# Helper function for parsing errorsdeferror(self,msg):raiseParseError(self.pos,msg,self.s[self.pos:])# Gets the current character being parseddefcurrent(self):try:returnself.s[self.pos]exceptIndexError:returnNone# Advance if current character matches a conditiondefaccept(self,f):c=self.current()ifc:match=f(c)ifcallable(f)elsecinfifmatch:self.pos+=1returnc# Advance if current character matches a condition, else switch to alternate parserdefexpect(self,f):x=self.accept(f)ifnotx:raiseNoParsereturnx# Advance if current character matches a condition, else raise parse errordefexpect_strong(self,f,m):x=self.accept(f)ifnotx:self.error(m)returnx# Try multiple parsers in sequencedefchoose(self,parsers):forparserinparsers:try:returnparser()exceptNoParse:pass# Parse an integer. Does not actually support negative numbers due to parsing ambiguities.defint(self):buf=self.expect("1234567890")whilec:=self.accept("1234567890"):buf+=creturnint(buf)# Parse a string. No escape sequences are supported.defstr(self):ifnotself.expect('"'):returnbuf=""whilec:=self.accept(lambdax:True):ifc=='"':returnbufbuf+=cself.error("unterminated string")# Parse a symbol.defsymbol(self):buf=self.expect(lambdax:xnotin"'0123456789()\"\t\n ")whilec:=self.accept(lambdax:xnotin"'()\"\t\n "):buf+=creturnSymbol(buf)# Parse a quoted expr.defquoted(self):self.expect("'")returnQuote(self.expr())# Skip whitespacedefwhitespace(self):whileself.accept(" \t\n"):pass# Parse a list of exprsdeflist(self):self.expect("(")items=[]defwhitespace_expr():self.whitespace()r=self.expr()self.whitespace()returnrwhile(x:=whitespace_expr())!=None:items.append(x)self.expect_strong(")","unterminated list")returnitemsdefexpr(self):returnself.choose([self.list,self.str,self.int,self.quoted,self.symbol])# Parse an entire program; error on trailing things, allow whitespace at start/enddefparse(self):self.whitespace()expr=self.expr()self.whitespace()ifself.pos!=len(self.s):self.error(f"trailing {repr(self.s[self.pos:])}")returnexpr# The environment is a stack of increasingly general scopes.classEnvironment:binding_stack:list[dict[str,any]]def__init__(self,s):self.binding_stack=sdef__getitem__(self,key):forbindingsinself.binding_stack:ifbindings.get(key)!=None:returnbindings.get(key)raiseKeyError(key)def__setitem__(self,key,value):self.binding_stack[0][key]=valuedefchild(self,initial_bindings=None):ifinitial_bindings==None:initial_bindings={}returnEnvironment([initial_bindings]+self.binding_stack)@dataclassclassFunction:params:list[str]body:anyenvironment:Environmentname:str="[anonymous]"def__repr__(self):returnf"<{self.name}({', '.join(self.params)})>"# Evaluator with some tail recursion optimization capability. Env/scope handling is mildly broken and only per-function instead of per-expr.# special forms:# let: define functions or values# either mutate the existing environment or create a new temporary one# functions are (let (x y z) (+ x y z)), values are (let x "string")# if used as (let thing "stuff"), works mutably# if used as (let otherthing "not stuff" (+ otherthing " but things")) then creates new scope# cond: do different things based on some conditionals# used as (cond (condition1 action1) (condition2 action2)) - the expr corresponding to the first true condition is evaluated# do: group side-effectful exprs together - evaluate them in sequence and return the last one# lambda: define functions without binding them to a namedefevaluate(x,env):whileTrue:ifisinstance(x,list):# special form handlingifisinstance(x[0],Symbol):name=x[0].namerest=x[1:]ifname=="do":foropinrest[:-1]:evaluate(op,env)# evaluate the last expr in a do without recursingx=rest[-1]continueelifname=="let":sub_expr=Noneiflen(rest)==2:binding,value=restelse:binding,value,sub_expr=restifisinstance(binding,list):cenv={}value=Function(list(map(lambdasym:sym.name,binding[1:])),value,env.child(cenv),binding[0].name)cenv[binding[0].name]=valuebinding=binding[0]else:value=evaluate(value,env)ifsub_expr:# evaluate the sub-expr nonrecursivelyx=sub_exprenv=env.child({binding.name:value})continueelse:env[binding.name]=valuereturnelifname=="cond":# Check each condition in turn. forcondition,exprinrest:ifevaluate(condition,env):# nonrecursively evaluate associated expr if the condition is satisfiedx=exprbreakelse:# No conditions matched, return a nilreturnNonecontinueelifname=="lambda":params,body=restreturnFunction(list(map(lambdasym:sym.name,params)),body,env)val=evaluate(x[0],env)# evaluate user-defined functionifisinstance(val,Function):params=dict(zip(val.params,map(lambdax:evaluate(x,env),x[1:])))env=val.environment.child(params)x=val.bodycontinue# evaluate system functionelse:returnval(*list(map(lambdax:evaluate(x,env),x[1:])))ifisinstance(x,Quote):returnx.contentifisinstance(x,Symbol):returnenv[x.name]returnx# Sorting functionality, as well as some other things in here for testing# Uses a tail-recursive continuation-passing-style Haskell-style quicksort (so not actually that quick)expr=Parser("""(do (let (id x) x) (let (snd xs) (head (tail xs))) (let (take_rec out xs n) (cond ((= n 0) out) (true (take_rec (cons (head xs) out) (tail xs) (- n 1))) )) (let (reverse_rec xs a) (cond ((= xs '()) a) (true (reverse_rec (tail xs) (cons (head xs) a))) )) (let (drop xs n) (cond ((= n 0) xs) (true (drop (tail xs) (- n 1))) )) (let (take xs n) (reverse_rec (take_rec '() xs n) '())) (let (count_rec xs n) (cond ((= n 0) xs) (true (count_rec (cons n xs) (- n 1))) )) (let (count n) (count_rec '() n)) (let (filter_rec xs pred acc) (cond ((= xs '()) acc) (true (filter_rec (tail xs) pred (cond ((pred (head xs)) (cons (head xs) acc)) (true acc) ))) )) (let (filter pred xs) (reverse (filter_rec xs pred '()))) (let (partition_rec xs pred acc) (cond ((= xs '()) acc) (true (partition_rec (tail xs) pred (cond ((pred (head xs)) (list (cons (head xs) (head acc)) (snd acc))) (true (list (head acc) (cons (head xs) (snd acc)))) ))) )) (let (qsort xs cont) (cond ((= xs '()) (cont '())) (true (do (let h (head xs)) (let t (tail xs)) (let part_result (partition_rec t (lambda (x) (< x h)) '(() ()))) (qsort (head part_result) (lambda (ls) (qsort (snd part_result) (lambda (rs) (cont (+ ls (list h) rs)))))) )) )))""").parse()env=Environment([{"+":lambda*args:functools.reduce(operator.add,args),"-":operator.sub,"*":lambda*args:functools.reduce(operator.mul,args),"/":operator.floordiv,"head":lambdaxs:Noneiflen(xs)==0elsexs[0],"tail":lambdaxs:xs[1:],"cons":lambdax,xs:[x]+xs,"reverse":lambdaxs:xs[::-1],# can be implemented inside the language, but this is much faster"length":len,"print":print,"=":operator.eq,"!=":operator.ne,">":operator.gt,"<":operator.lt,">=":operator.ge,"<=":operator.le,"rand":lambda:random.randint(0,1),"true":True,"false":False,"nil":None,"list":lambda*args:list(args),}])evaluate(expr,env)defentry(to_sort):returnevaluate([Symbol("qsort"),Quote(to_sort),Symbol("id"),to_sort],env)
words=[]things={}now=[]array=[]stack=[]#anyone can modify this Forth for other chalenges in the competition#I release all rights to the codedefentry(thing):foriinrange(len(array)):delarray[0]foriinrange(len(thing)):array.append(thing[i])forth(": countless dup 1 + length for do: get item < if do: 1 + ; ; ; : put goal while do: dup get item == ; do: 1 + ; dup get swap item set store item ; 0 length 1 - for do: (i) dup dup dup (i i i i) get (i i i item) store item (i i i) countless (i i g) dup (i i g g) store goal (i i g) != if do: (i) put (i) while do: (i) dup (i i) goal (i i g) != ; do: (i) put (i) dup (i i) countless (i g') store goal (i) ; (i) item (i item) set ; ;")returnarraydefnext():next=words[0]delwords[0]returnnextdefnextAndCompile():thing=next()whilethinginnow:things[thing]()thing=next()returnthingdefpop():pop=stack[-1]delstack[-1]returnpopdefpush(thing):stack.append(thing)defword(func,name=None,do_now=False):ifname==None:name=str(func).split()[1]things[name]=funcifdo_now:now.append(name)returnfuncdefeq():push(pop()==pop())word(eq,"==")defnotEq():push(pop()!=pop())word(notEq,"!=")defplus():push(pop()+pop())word(plus,"+")defminus():push(-pop()+pop())word(minus,"-")deflessThan():push(pop()>pop())word(lessThan,"<")deffunc():thing=nextAndCompile()x=[]word=nextAndCompile()whileword!=";":x.append(word)word=nextAndCompile()deffunc():words.reverse()words.append(x)words.reverse()things[thing]=funcword(func,":")defdo():x=[]thing=nextAndCompile()whilething!=";":x.append(thing)thing=nextAndCompile()words.reverse()words.append(x)words.reverse()word(do,"do:",True)defend():returnword(end,";")@worddeflength():push(len(array))@worddefget():push(array[pop()])@worddefset():print("Modified")array[pop()]=pop()@worddefdup():thing=pop()push(thing)push(thing)defcomments(thing):brackets=Falsedone=""foriinrange(len(thing)):ifthing[i]=="(":brackets=Trueifthing[i]==")":brackets=Falseelifbrackets==False:done=done+thing[i]returndone@worddefswap():a=pop()b=pop()push(a)push(b)@worddefstore():name=nextAndCompile()thing=pop()defget_value():push(thing)things[name]=get_valuedefforLoop():body=nextAndCompile()stop=pop()start=pop()words.reverse()foriinrange(start,stop):words.append(body)words.append(start+stop-i-1)words.reverse()word(forLoop,"for")defwhileLoop():condition=nextAndCompile()body=nextAndCompile()thing=[condition,"if",[body,"while",condition,body]]words.reverse()words.append(thing)words.reverse()word(whileLoop,"while")@worddefdebug():print(pop())@worddefdebugAt():print(next())defifStatement():body=nextAndCompile()ifpop():words.reverse()words.append(body)words.reverse()word(ifStatement,"if")defforth(forth):ifcompile!=True:forth=comments(forth)forth=forth.split()forthinginrange(len(forth)):thing=forth[thing]words.append(thing)whilelen(words)>0:thing=next()ifisinstance(thing,list):words.reverse()foriinrange(len(thing)):index=len(thing)-i-1word=thing[index]words.append(word)words.reverse()else:try:stack.append(int(thing))except:thing=things[thing]thing()
#!/bin/python3fromcollectionsimportCounterdefcountsort(input_array):'Sorts and returns a given list using counting sort.'# Storing counts of each integerinteger_counts=Counter(input_array)# Cascade positional valuesforkeyinrange(min(input_array),max(input_array)+1):integer_counts[key]+=integer_counts[key-1]# Build output arrayoutput_array=[0foriinrange(len(input_array))]forelementinreversed(input_array):output_array[integer_counts[element]-1]=elementinteger_counts[element]-=1returnoutput_arraydefentry(input_array):returncountsort(input_array)
# Function to sort a list in ascending order.defentry(list_to_be_sorted):# The standard library function sorted() takes a list and sorts it in ascending order.returnsorted(list_to_be_sorted)
post a comment