Jeux du Sort

MichaBln · Post by **MichaBln** » Tue Jan 13, 2009 11:54 am

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

efe · Post by **efe** » Tue Jan 13, 2009 3:25 pm

@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.

MichaBln · Post by **MichaBln** » Tue Jan 13, 2009 4:06 pm

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

tails · Post by **tails** » Tue Jan 13, 2009 8:00 pm

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.

Karian · Post by **Karian** » Tue Jan 20, 2009 2:39 pm

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/

wrtlprnft · Post by **wrtlprnft** » Tue Jan 27, 2009 9:16 pm

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.

Broker · Post by **Broker** » Fri Feb 13, 2009 9:42 pm

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                                          /

megabreit · Post by **megabreit** » Sat May 23, 2009 1:00 am

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...

therethinker · Post by **therethinker** » Sat Jun 06, 2009 5:15 pm

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)

Force4 · Post by **Force4** » Mon Dec 21, 2009 4:41 pm

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!

MrBlueSky · Post by **MrBlueSky** » Tue Jan 11, 2011 1:36 am

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

compudemon · Post by **compudemon** » Tue Aug 23, 2011 4:53 am

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

dangermouse · Post by **dangermouse** » Thu Jul 12, 2012 3:20 pm

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.

dxer · Post by **dxer** » Sun Mar 24, 2013 9:07 pm

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^:!

avrrobot · Post by **avrrobot** » Fri Mar 29, 2013 1:41 pm

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.