Cedric's challenge, C port and analytic attempt

I was a bit disappointed that the C port of the previous code wasn't quite as fast as another approach which cached more state instead of generating the i'th value. The second attempt, using the bcd lists was comparable to John Wilson's Java version (1.3 seconds rather that 1.5 reported by the Java), and an attempt using bitsets a bit slower. Timings on Eee pc 900, Ubuntu hardy heron. The code is nrnat2.c.

The biggest jumps are between 9(descending digits) and 10(ascending) and 10(descending) and 12(ascending). Generating those four values will give the largest jump in a range.

The number of values will be the total of combinations: 9 + 9 * 9 + 9 * 9 * 8 ... up to the max value.

The total for 1..9 is 9*(9+1)/2 = 45;
For numbers 10 to 98 there are 9 numbers starting with each digit, so you have 450*9 for the first digit, and 9 lots of a odd sum, where there's one digit missing - so 9 * 45 - 45 for taking one digit out each time (the range is 0..9 instead of 1..9).

That gives a total up to 10 of 45

Up to 100 we get the 45 up to 10, 45 * 10 * 9 for the first digit shifted once repeated 9 times, and 40 * 9 for the second digit repeated 9 times (as the first digit is always non-zero, it biases the remaining digit's average by 0.5 from 4.5 to 4). So total for up to 100 is 45 + 45 * 10 * 9 + 40 * 9 = 4455.

Up to 1000 we get the values so far, 45 * 100 * 9 * 8 for the first digit shifted twice repeated 9 * 8 times - the number of combinations of the other digits. The remaining digits occur the same number of times as each other in each position and once for each value of the first digit, so you get 40 * 9 * 8 * 11 from them, so total is (4455 + 45 * 100 * 9 * 8 + 40 * 9 * 8 * 11) = 360135.

Similarly sum up to 10000 is (360135 + 45 * 1000 * 9 * 8 * 7 + 40 * 9 * 8 * 7 * 111) = 25277895

Simplifying, the sum of the values with n digits is (9!/(9-(n-1))!) * ( 45 * pow(10, n-1) + 40 * floor(pow(10, n-1) / 9) ) and the maximum jump is floor( ( 1203456789-1029876543 ) / pow(10, 10-n) )


Pete

A coding challenge

An implementation of the coding challenge of Cedric's.

Somewhat coloured by the fact I normally use python as a prototyping language prior to production coding in C++.

The combinations technique (using a bcd string instead of list) gets faster than the filtering technique for max somewhere between 1,000,0000 and 10,000,0000. As python is bytecode, it may be slower to bit-twiddle than use a dynamic list; IIRC it has to allocate memory to hold longs anyway, but getting it right in Python and then porting to something with good performance is the way I often work, and longs are fast in production programming languages.

import time

def has_repeat_digits(i, available = (1 << 10) - 1):
 digit = i % 10

 if available & (1 << digit):
  if i < 10:
   return False
  else:
   return has_repeat_digits(i // 10, available &~(1< else:
  return True

def brute_force_counter(max):
 for i in range(1, max):
  if not has_repeat_digits(i):
   yield(i)

def test(max, counter, timed_run = False):
 last_i = 0
 biggest_jump = 0,0,0
 total = 0
 start_time = time.time()

 for i in counter(max):
  if not timed_run:
   print i,
  total = total + i
  jump = i - last_i
  if jump > biggest_jump[0]:
   biggest_jump = jump, last_i, i
  last_i = i
 stop_time = time.time()
 print
 print 'total', total
 print 'biggest jump', biggest_jump
 if timed_run:
  print 'time', stop_time - start_time

# select the index'th permutation
# first digit is special case, is in range(1,10) rather than range(0,10)
# otherwise it's a standard permutation. Using BCD encoded value to represent
# remaining digits to select from rather than a list as deleting from a python
# list is O(length) whereas deleting a digit from the BCD is O(1), and I like
# fiddling with bits.
def bcd_select(index):
 if index < 10:
  return index

 pow = 1L
 fact = 1L
 digits_available = 10

 index = index - 1L

 while index >= fact * 9:
  index = index - fact * 9
  digits_available = digits_available - 1
  fact = fact * digits_available
  pow = pow * 10

 #~ print 'fact', fact, 'pow', pow, 'i', index, 'i//fact', index//fact

 # first digit is selected from 1..9
 available = 0x9876543210
 digits_available = 9
 sel = (index // fact)
 index = index - sel * fact
 sel = sel + 1
 available = (( available & ~((1 << ((sel + 1) << 2)) - 1)) >> 4) | ( available & ((1 << (sel << 2)) - 1) )
 acc = sel * pow
 pow = pow // 10
 fact = fact // 9
 #~ print fact
 while pow > 0:
  #~ print digits_available
  #~ print 'fact', fact, 'pow', pow, 'i', index, 'i//fact', index//fact
  #~ print 'available', digits_available, hex(available)
  sel = (index // fact)
  acc = acc + pow * (( available & (0xf << (sel << 2)) ) >> (sel << 2))
  available = (( available & ~((1 << ((sel + 1) << 2)) - 1)) >> 4) | ( available & ((1 << (sel << 2)) - 1) )
  index = index % fact
  pow = pow // 10
  digits_available = digits_available - 1
  fact = fact // digits_available

 return acc

def bcd_counter(max):
 index = 1
 while index < max:
  value = bcd_select(index)
  if value > max:
   break
  yield value
  index = index + 1

Eee's are good, Eee's are good

I got an Asus Eee PC the other week, and spent the weekend and the last few evenings putting Ubuntu 8.04 on it (compiz, Ubuntu studio themes, several desktop tweaks, scite text editor, installing wifi and other drivers). It's small and cute. The screen is surprisingly legible, even for tiny text at arms length, and it's smoother than my big laptop running compiz.

As I don't have a USB DVD drive, I installed off of a USB stick, which took a bit of persuading to boot, and then used rsync to copy the installation over to the flash drive on the computer. The various installation guides weren't much help getting it to boot off the internal drive - various settings around grub-install seemed to update the USB stick rather than the internal drive, but following the instructions from the grub manual to do a 'native' install did the trick. Once I'd done that it seemed to be OK, but it believed it had mounted /dev/sdb1 (the 16G internal drive) as /, whereas it had really mounted /dev/sda1 - the 4G internal 'system' drive. That was cured using UUID rather than /dev/sda1 in the grub menu.

Getting wifi to connect is still rather hit and miss - Wifi-radar seems to be the application which works for it. There are far too many wifi controller apps for Ubuntu, and the few I tried didn't seem to do anything. None have particularly good indication of why a connection isn't working.

[2008/06/14 - the issue was two-fold: instead of running cables everywhere, I was connecting into a wifi gaming adapter through a router, as I had two machines sharing the adapter, and that router appeared to be giving out DCHP addresses, even to other wifi devices, which mean DCHP wasn't working. As far as Wifi-radar and the network selector, wifi-radar was setting up the wifi correctly, but still needed network selector to turn off the ethernet. Doing that using sudo ifdown eth0 worked as well, and putting that command as a connection command makes everything work just by opening Wifi-radar then hitting connect.]

The GPS works fine with it. I haven't tried getting the web-cam working yet.

One odd thing is how rough the texture of the keys feels - I've had my larger laptop a couple of years now, and the home row is polished smooth. You can hold it at an angle to the light and see that Dvorak was right about letter frequency, except for the modifier keys.

On the map

Received a little gps 'mouse' receiver in the post today, and (having installed gpsd and python-gps) have got it running as a local service with my first google maps mashup. The server is here, it just shows a google map centred on the current location. I now need to wait until I get a mobile broadband dongle and the new tiny laptop I've ordered (Asus eee 900) and then can have gps on the road (though I don't really want to be using a laptop in the car unless I'm really lost)