# Fastest Codeslinger 2008 Solutions

Submitted by clintc on April 2, 2008 - 8:31pm

Congratulations to Ian Taylor. He is the Fastest Codeslinger for 2008.

Ian took around 30 minutes to craft his solution in Ruby and post it to the local contest server.

A statement of the problem is here: http://www.gatorlug.org/node/199

Behold the winning entry:

# Ian Taylor # # Gatorlug 2008 Codeslinger Shootout Submission # # answer 358926471 $limit = 100000 def perm(a,b=[]) if a.empty? $limit -= 1 if $limit == 0 puts b.to_s exit end else a.each do |e| perm(a-[e],b+[e]) end end end a = (1..9).to_a perm(a)

**Jim Wilson** submitted this gem in Python:

# Jim Wilson's Python solution to the 2008 Codeslinger competition. This is # essentially a translation of Ian's winner with a little annotation to # make it comprehensible to my feeble brane. # # I stared at this thing until I thought my head would explode. I was # trying to think of Ian's code as a bottom-up approach; after I realized # it was obviously more top-down, it suddenly became crystal clear. # # NOTE for Rubyheads: Python "lists" are apparently Ruby "arrays". count = 0 # Permutation counter def permute(head, tail): # completed prefix, ordered set of leftovers global count # Static count for recursive routine if tail: # If still more items to tack onto end, for item in tail: # Loop through items (largest first): newhead = head+[item] # new prefix (a *separate* list!) newtail = list(tail) # new suffix (includes spurious "item") newtail.remove(item) # remove "item", earler appended to prefix permute(newhead, newtail) # handle (now-reduced) tail permutations else: # If no more items to add, count += 1 # count this valid permutation if count == 100000: # If 100,000th valid permutation, print head # print the digits (as a list) raise SystemExit # No need to go further. # Ian's solution is O(N!), where N is the number of items (digits) in the list. # Here's a (supposedly) O(N*N) solution. This approach was suggested to me by # Robert Munyen who was wasn't competing, but was solving it on a napkin. # # Of course, I'm too lazy to code it myself; this version was lifted almost # verbatim from: # # http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/126037 def NPerms(L): """ Returns factorial(len( )), the number of ways

can be permuted" """ return reduce(lambda x, y: x*y, range(1, len(L)+1), 1) def PermN (L, N): """ Returns the Nth permutation of list L. NOTE: L is devoured. """ N -= 1 # 1st, 2nd, 3rd, ... instead of 0th, 1st, 2nd, ... R = [] # Result P = NPerms(L) # Number of possible permutations N %= P while L: # Until list is devoured: P /= len(L) # Number possible permutation remaining D, N = N//P, N%P # L[D] is next digit of result R.append(L.pop(D)) # Remove digit from L, append it to R return R # We must call the O(N) function first since the O(N!) version exits when it # reaches the target permutation. On my machine, the first answer comes # immediately; the second arrives after a substantial pause. print PermN([1,2,3,4,5,6,7,8,9], 100000) permute([], [1,2,3,4,5,6,7,8,9])

**Robert Munyer** was trying to work things out on a napkin. He sent this in:

; For the person who wanted the algorithm that I was using (mentally) to get ; the answer using a napkin and calculator: it's below. On a computer, the ; speed is too fast to measure, because it gets the answer with only eight ; multiplications and eight divisions. ; ; To make it slow enough to measure, I had it calculate the googolth ; permutation, instead of just the hundred thousandth permutation, and I ran ; it on a 166 MHz pentium. It got that answer in 0.02 seconds. (defun shoot (num-cards index) (labels ((main-loop (index factorials in out) ; in & out are lists of cards (cond ((zerop index) (revappend out in)) (t (multiple-value-bind (quotient remainder) (truncate index (first factorials)) (let ((card (nth quotient in))) (main-loop remainder (rest factorials) (remove card in) (cons card out)))))))) ; the loop below just builds a list of cards and a list of factorials (do ((n 2 (+ 1 n)) (fact 1 (* n fact)) (cards '(1) (cons n cards)) (facts nil (cons fact facts))) ((> n num-cards) (main-loop (- index 1) facts (reverse cards) nil))))) ; > (shoot 9 100000) ; (3 5 8 9 2 6 4 7 1) ; ; > (shoot 70 (expt 10 100)) ; (59 31 14 44 33 24 51 1 29 9 17 12 43 61 69 70 53 21 65 36 68 30 41 19 66 34 ; 50 7 26 6 32 10 60 20 55 42 4 25 67 64 2 57 39 27 52 48 38 15 54 45 58 18 23 ; 37 3 22 13 16 46 40 56 11 62 63 49 8 35 28 47 5)

**Cain Norris** makes a pitch for Haskell with this:

While I didn't make it out for the contest, I'll go ahead and shill for Haskell by submitting a solution. I've written it out twice, one in good style, once in three lines. Same hopefully smart algorithm, and basically the same code, though. Both print "358926471"-- hopefully correct! Cain long pretty version ------------------- import Data.List main :: IO () main = putStrLn $ lexpermn "123456789" 99999 fact :: Int -> Int fact = product . enumFromTo 1 lexpermn :: (Eq a) => [a] -> Int -> [a] lexpermn [] _ = [] lexpermn xs n = x : lexpermn (delete x xs) (mod n m) where m = fact $ length xs - 1 i = div n m x = xs!!i 3 78col lines version --------------------- import Data.List; main = putStrLn $ lexpermn "123456789" 99999 lexpermn xs n = if xs == [] then [] else x : lexpermn (delete x xs) (mod n m) where m = product . enumFromTo 1 $ length xs - 1; i = div n m; x = xs!!i

**Edward Allcut** shows us that Bash can get the job done too:

#!/bin/bash shopt -s extglob nullglob declare -i TARGET=100000 declare -i FOUND=0 ITEMS="1 2 3 4 5 6 7 8 9" function remove() { echo "${2//$1?( )}" } function candidate() { FOUND=$(( FOUND + 1 )) #echo "Found $FOUND" if [[ $FOUND -eq $TARGET ]]; then echo "$1" exit fi } function gen() { if [[ $1 == *( ) ]]; then candidate "$2" return fi for i in $1; do gen "$(remove $i "$1")" "$2$i" done } # prints 358926471 gen "$ITEMS" ""

**Ian Taylor** doesn't want C to be left out:

// Ian Taylor// // Adapted from the algorithm from: // // The Art of Computer Programming // Volume 4: Generating All Tuples and Permutations // 7.2.1.2 #include #include void swap(char *a, char *b) { int temp = *a; *a = *b; *b = temp; } int main() { char a[] = "0123456789"; int n = strlen(a)-1; int i,j,k,l; for (i=0; i<=100000; i++) { // puts(a+1); for (j=n-1; a[j] >= a[j+1]; j--); for (l=n; a[j] >= a[l]; l--); swap(&a[j], &a[l]); for (k=j+1,l=n; k < l; k++,l--) swap(&a[k],&a[l]); } puts(a+1); return 0; }

## Times for the above solutions

Here is something quite telling...

I compiled all of the above as best I could. I did not do byte compiled versions of the python version (and I am not sure if you can with Ruby... pretty much clueless on that one.)

The times I got were the following:

Ruby - 1.8088 sec

Python - 1.052 sec

Bash - 234.271 sec

C - 0.001 sec

I think that the C version probably runs even faster than that, but the linux time command can't measure anything smaller... :)

I was going to do a Cobol version of this, but then I realized that would just be stupid. :)

## Apples to Oranges

The difference in computation time tells you more about the approach to solving the problem versus the language / environment chosen.

We had considered adding a time penalty for a strictly brute force approach. But, that introduced more complexity and the possibility of having to make a value judgment about the definition of "brute force approach". So, the contest stayed true to it's roots - whoever bangs out the code that produces the right answer first wins the contest.

## It isn't just the approach

It isn't just the approach to solving the problem in this case, I think. Note that those time measures include the time it takes for the system to fire up the interpreter for any of those pieces of code that have been done in a form that is interpreted code such as Perl. Having to have those interpreters fire up, interpret the code, then process the code takes up time. The C code has already been compiled down to a binary that simply runs natively, so you don't have to load up any sort of interpreter.

I do think it would be interesting to take a look at the times for these codes if the perl and other interpreted codes were byte-compiled.

## Benchmarking Is Hard

This is a great example of why Benchmarking Is Hard. Including the interpreter start-up time is appropriate, in certain situations (e.g. you'll be deploying a service under inetd or CGI, and you aren't allowed to have a daemon) but it's inappropriate in many more common situations (e.g. you'll be deploying a daemon).

## brute force

A nice feature of this problem is that you can choose whether to reward or penalize brute force, and even choose how much to reward or penalize it, just by adjusting the parameters. If the goal is to find the hundred thousandth permutation, brute force works great; but to find the googolth permutation, brute force could take longer than the Sun's remaining lifetime.

It think it would be fun to have a more difficult version of the problem as a sort of "extra credit round" that people can tackle after solving the main problem. Even if there's no trophy (coffee mug) for the extra credit round, it still would keep the excitement going a bit longer.