Skip navigation.
Home
Freedom is contagious.

Fastest Codeslinger 2008 Solutions

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(<list>)), the number of ways <list> 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])
</list></list>

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;
}

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

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

clintc's picture

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

Note that those time measures include the time it takes for the system to fire up the interpreter

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

having to make a value judgment about the definition of "brute force approach".

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.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.