Page 1 of 4
Jeux du Sort
Posted: Tue Jan 13, 2009 11:54 am
by MichaBln
So, which Alogrithm did you use (if you wanna share that with us).
Man, did I made a bad choice ... Bubble Sort, just since it came to my mind first and is pretty easy to implement. I should have roughly estimated the cycle-count befor starting to code ... .
I'm not one of the guys who can make such insane code like tails or tog (as adum says ... I'd relly like to see an example) ... its not my field of programming, but I'm learning.
So my first working solution took way to much cycles, like 14k ... fortunatly optimizing brought me below the 10k.
The KOTH-Challenge for this one with like a little over 1200 Cycles (tails) is clearly out of my world ... anyways, very nice challenge.
Michael
Posted: Tue Jan 13, 2009 3:25 pm
by efe
@MichaBln: I also used Bubble Sort for this one.
Have a look at my solution:
Code: Select all
@s\1s/,x?s$1\
..1..\+1>1^./........$
..\s/x1+s/1^1<1^1<@s\:$\
.../\~~~~\/s?-+89x+1/\1^1<1^1<3^1>1^1>$
...8s~~~~~1
...5?~~~~~v
...*-~~~~~1
...4\+79x+/
...\+1s/x1<p1^P~1\
.......\/s?-+88x+/
........\1<p!
It takes about 5000 cycles to sort 16 integers.
Posted: Tue Jan 13, 2009 4:06 pm
by MichaBln
Hi, here is mine ... yeah I'm not so good at it, i still wanted to remove that ugly "return" on the bottom and replace it by "@/$" but it worked like that (the outer loop just runs 14 times, fortunatly the test case wasn't the worst case (totally inverted).
Code: Select all
28*s/1-,12^>x?\72*+ s/1-\ /+x?\ 28*+s/1-11^<px?\!
\ / /. / /}2]{{13^> \\P+4*85 /
\ .. / } />+1^21/
.\53*s/s/@s\1-11^<12^1+<:s/s\x?\\
. \ / \ / $.
\.............................../
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
EDIT: It does look odd since the lines are broken in the forum ....
Anyways, thanks for your solution I'm going to take a closer look at it.
Michael
Posted: Tue Jan 13, 2009 8:00 pm
by tails
Hi, here is mine.
Code: Select all
010>0s/1+,12^>xs/11^1-<12^<\/s/?x97+-?\1s/11^<p94*8+P1+x97+-?\11^<p!
. - \:./ . \.................../
. 1 \11^1\ .
. \>^21>-1^31<^21<-/ .
\.............................../
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
This code does insertion sort. It takes about 3900 cycles.
My code for KOTH is quite different from this one.
MichaBln wrote:The KOTH-Challenge for this one with like a little over 1200 Cycles (tails) is clearly out of my world ...
Threading is our friend.
With 32 threads, we have more than 30000 thread-cycles within 1200 cycles!
EDIT: The lines got broken as well.
EDIT: I think I have found how to preserve the lines. Please ignore those a's at the bottom.
Posted: Tue Jan 20, 2009 2:39 pm
by Karian
I implemented this one with the idea of having a pretty fast solution. Offcourse, this way of working is absolete for the fast challenge, since that one is about 64 integers. At least it learned me playing with some threads.
The code isn't that nicely ordered, it wasn't going for being small anyway. It completes in about 1300 cycles.
Code: Select all
44*s/x?\48*55ws/\ /\s>3^20\
, | 1 \/ /x\/ P
s - | ? g
\/&/ \=/ 1
s s | 1
/\89+1v-0,1089+s/1-x?\1[?/s\1[xp1^?/!
+| | x
1| s 6
}| \/?-^/
\/ sx
\2s=>4^\
s< /16/
\\4^:
s| 4
|> ^
|1 ?
s^ \4^2<1\
|\6x/s\ ^
s :=<2/
\==s=s/
Posted: Tue Jan 27, 2009 9:16 pm
by wrtlprnft
Probably the worst one yet (in this thread as well as for me personally):
Code: Select all
8888888******20>0s/,12^>1+\ /v1[1^\
/\? -*82x/ 1 0
\s/0110<s/12^<x20<-?s\0^2^:=\ 1
P /1v/ 1 1 1 >
* /\?=-*82x+1v1[=s/s==s/s/s=0/
4 \1[p20<12\
\+92/s?x-1>v/
!
The uglyness of the eights is because i realized I was sorting in the wrong order when I tried to submit it… so I needed a three-letter method of pushing a huge number to avoid reordering my code.
Then again, the entire code is ugly (it searches for the smallest number, prints it, replaces it by a huge one, 16 times), and the example input I used for testing was just barely within the limit. But the debugged version passed on the first try, so I guess it's not cheating.
Posted: Fri Feb 13, 2009 9:42 pm
by Broker
ok, and here is mine - if someone is interested...
Code: Select all
1s/s/,x?\ ? 1s/x1<p x2^-1+?\!
\1 s/x1<2^1vx?\? ? 1>\ \ P-1*59+1 /
\ +1 : 2^ s/x1-1<1^1>x2^-?\?1> \
\ +1 / \ -1 /
\ +1 /
Posted: Sat May 23, 2009 1:00 am
by megabreit
Funny how all those Superhack programs look like; mine looks a bit like an anteater, others look like space ships or Karians chicken.
Mine is also a bubble sort, this seamed to be sufficient for this challenge.
Code: Select all
\/011>3\ /.\
,\,\ /s\5*x1+v1vs/28*v2v1v1^1^: .
,/\, 3 \.....\ 1 .
,,,, \[1>110......\ . v .
,,,, . . x .
,,,, /*2+P1\ . . 1 .
\/\/ 7 - . . 1 .
6 . . . > .
!:1xpvx/s*82[1:0<11:0x-1v2/s/
Sadly enough the next challenge is a KOTH again. The barrier is (from my point of view) too high for those who started late into the challenges. It's just frustrating and leaves no motivation to try.
On the way to the next non-KOTH...
Posted: Sat Jun 06, 2009 5:15 pm
by therethinker
Heh, mine are never pretty like everyone else's
Code: Select all
%53*}?/,00<x?\\
\ >00-1/{
/<12^<\/12^<12^<1\4
^ / :/ 44
2/ x/s/s \ ^*
1 /1-\ >1
\\?/\ \>^21/-
s/ /s \s -1x/
\/ \+1-xx?/0 \
!/?-*82x+1p<^11\s/
\67*2+P /
I used a algo. very similar to heapsort, only without a heap. I iterated over all the elements on [0, n] and if it was greater than the # at spot n, they were swapped. I repeated this, decrementing n each time. It should be n!, if I'm correct, but it's not coded well and it took 8.6k cycles for 16 integers. (I did use loops to get the input & output, though)
Posted: Mon Dec 21, 2009 4:41 pm
by Force4
Wow! Those SuperHack programs are indeed sexy. Adum should make up a "SuperHack Art challenge":lol:.
Mine is ugly though, I'm really not that good at it...
Code: Select all
/===================================================\
| /============================\ |
| | /=\ | | /==================\
%,110>s\,011>s\10<v1^1^:s\1vs/11<1+0^11>10<:s/10<1+0^10>88+:s/110>ps\31gPp10<1+0^10>88+:s/!
\=====/ \=/ \=/ \=/
paddingpaddingpaddingpaddingpaddingpaddingpaddingpaddingpaddingpaddingpaddingpaddingpadding
So yeah.. bubble sort that took around 8,000 cycles, because of those ugly loop returns.
Anyway that was good fun!
Posted: Tue Jan 11, 2011 1:36 am
by MrBlueSky
I used shellsort.
Code: Select all
read:.%0s/,12^>1+0^82*-?\\
.........\______________/|
......./__________?______/
.......|...................../__\
sort:..\021>s/21<22>21<1+23>s\@s/122<<123<<\
.............|..................../________:s/23<1+23>23<28*-?$22<21<\/21<1+21>21<35*-?\\
.............|....................\23<22>.s\_/.......................|\..............\.||
.............\_______________________________________________________|_______________|_/|
................................................................/____/...............|..|
swap:...........................................................\12^<12^<14^>12^>?.?./..|
......../_______________________________________________________________________________/
print:..\0s/11^<p1+0^82*-?\!
...........\P+2*67________/
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8000+ cycles
Posted: Tue Aug 23, 2011 4:53 am
by compudemon
its bubble sort yay and it looks like the enterprise
Code: Select all
44*s/x?\35*+s/0s/=12^<12^<\
/21,|-1/ /-1|[1\?-^2x+1\s:12^<12^<1\
\^>=/ \x?/\ \=/s=>^21>^4/
/+8*94\s+1p<01/
\P11^<|px35*-\
\+1!s?=/
_____________________________________
3550~ cycles
Posted: Thu Jul 12, 2012 3:20 pm
by dangermouse
i implemented a Quicksort:
Code: Select all
%01s/,1^2>1+x28*1+-?\\
\===============/|
/=======*281========?/
\s/@s\x?\1s/x2<px28*-?\! /41<31<\ /21<51<$
\==/ | \=P*+294=+1/ /41<31<:s/===s\=21<51<:$
\x2^-?\?=?=$ \=?\ \=/ $ /s/21<2<61>31<2<21<2>61<31<2>\
/============/ /?=/ /=\ /=>12+1<12=\ | | |
\1^2<1^2<+2d11>1^21>x31>1^41>x51>s/31<21<:s/=s/=31<2<11<:s\s\==21<2<11<:s/21<31<:=/ |
\=\ \=/ \=>13-1<13/ \=/ | |
\===========================================/s===========>12+1<12>13-1<13/
it does not fit on the right, so you have to imagine how it goes
it should not be to difficult though.
Posted: Sun Mar 24, 2013 9:07 pm
by dxer
Some kind of insertion sort, 1130 cycles for the best case and 5210 for the worst case.
Code: Select all
0@s\@=@=@=@=,1vxs/01^<1^x?\3[s/1+$
s /02^>==/ 1 |
/==P\ \>v40\ - [
1 * /=:^1^1<^20v1/ 4
v 4 \s\==============/
p +
1 6
- 5
\01^:!
Posted: Fri Mar 29, 2013 1:41 pm
by avrrobot
Here is my Code:
Code: Select all
0s/1+,x1\ / s/ \
/0\? >^3/ \v1:\s
\s/1+xs/1+12^<12^<1^1^/\\
\/@[1\?-+88x>^31>^31 /
\x87+-?$88+s/11^<p1-x?\!
\ P*4+29/
Takes around 5700 Cycles and uses Bubblesort.