Monday, July 28, 2008

Cedric's Coding Challenge

I came across a programming challenge on Cedric Beust's blog and thought I'd have a go at it. The goal is to write a counter function that counts from 1 to max but only returns numbers whose digits don't repeat. It has been solved by many users in a number of different ways using languages such as Java, C, Perl, Erlang, Javascript, C#, Groovy, Haskell, AS3, C, Fan, LUA, J, OCaml, Factor, Forth, Lisp, Ursala and Prolog. I am going to write a Unix Shell program to solve it (simply because this hasn't been tried by anyone else yet).

My Shell Solution:

#!/usr/bin/sh
#
# Counts from 1 to max and prints numbers whose digits
# don't repeat. Displays the biggest jump and the total
# count of numbers.
# Author: sharfah

max=$1
counter=1
prev=$counter
maxdiff=0
total=0

while ( [ $counter -le $max ] )
do
    echo $counter | grep '\(.\).*\1' > /dev/null
    if [ $? -ne 0 ]
    then
        echo "$counter"
        total=`expr $total + 1`
        diff=`expr $counter - $prev`
        if [ $diff -gt $maxdiff ]
        then
            maxdiff=$diff
            from=$prev
            to=$counter
        fi
        prev=$counter
    fi
    counter=`expr $counter + 1`
done
echo "Biggest jump is $maxdiff:$from->$to"
echo "Total count of numbers is $total"
Output
Run on an Intel(R) Xeon(R) CPU 2.33GHz 8 CPU, SUSE LINUX Enterprise Server 9, it produced:
sharfah@starship:~> time ./beust.sh 10000 > beust.log
   38.68s real    12.71s user    25.80s system

sharfah@starship:~> tail beust.log
9867
9870
9871
9872
9873
9874
9875
9876
Biggest jump is 105:1098->1203
Total count of numbers is 5274
When run on Solaris 10, it took 1m26.219s.

If you think you can make this go faster, let me know how in the comments section!

1 comment:

  1. I came in looking for a search engine plugin howto, and lost... an embarrassing amount of time. Thanks for the plugin post, that was very useful.

    You can get a bit of a speedup on your shellscript by not spawning so many greps. My beust2.sh:

    yes "" | head -$1 | cat -n | tr -d [:blank:] | grep -v '\(.\).*\1' | \
    (
    total=0;
    maxdiff=0;
    from=0;
    to=0;
    while read current;
    do
    echo $current;
    total=`expr 0$total + 1`;
    diff=`expr $current - 0$last`;
    if [ $diff -gt 0$maxdiff ];
    then
    maxdiff=$diff;
    from=$current;
    to=$last;
    fi;
    last=$current;
    done;
    echo "Biggest jump is $maxdiff:$from->$to";
    echo "Total count of numbers is $total";
    )

    And times:
    beust.sh 10000
    user 0m37.758s
    beust2.sh 10000
    user 0m9.613s

    I couldn't think of a way to get the largest gap - maybe there's a way using sort and uniq on tagged numbers? I think I'll hand over the baton... hey! I even got an Olympics ref in!

    ReplyDelete