## 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. Anonymous9:02 PM

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