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

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)

Python and EA

For my current contract, I'm part of a team producing scripts which define interfaces to equipment in a satellite communications system for monitoring and control. Various interfaces, serial, low-level TCP and SNMP.

The application is fairly old - originated on Unix in early 1990s, ported to MFC late 1990s - and there are many links between the various configuration files. It's a high reliability system, so uses the classic pattern of a watchdog process with spawns the active processes, monitors them for liveliness, CPU and memory use, and respawns them or kills them in event of failure.

The goal is to use Enterprise Architect for modelling the system in UML. EA has a limited custom code generation - one file per class, poor tree walking functionality - which is just sufficient to create the interface scripts, but none of the other configuration which is more highly intertwined - for each rack or group of racks of equipment to be monitored, there's a server which runs a set of monitoring processes, each monitoring a set of instances of the equipment. Various parts of the configuration, such as the port ID of each server process, need to be put into different configuration files, so the desired layout of generated files doesn't follow EA's assumptions.

Also, there needs to be a parser for the configurations which reverse engineers a UML model from the configuration files - we don't want to have to generate the UML models for existing equipments by hand.

So I started writing a little parser in Python which generated an XMI file for import into EA. That worked well enough, and impressed the line manager, so have been spending the last couple of days fleshing it out.

EA doesn't quite treat tagged values as first-class citizens of UML, relegating them to a second window (though it's nice to have them docked and always visible, but that could apply to all the panes in the properties dialogs). So I wanted a table view which looked like the config file layout, of all the extra tagged values we're using to define the application specific properities used to implement the attributes of the equipment in the configuration files.

I've been using GTK for that - I've played with GTK a bit in C, and quite like it's level of abstraction and simple event model. It's not too hard to get things working in Python (some of the handling of attributes is a bit counter intuitive), and it mostly looks native (compared to Java or Gecko, or even EA's UI, which I believe is written in C#, but isn't using WinAPI menus).

I quite like Python, but it's a bit too imperitive for my taste, and there's no type system to tell you if you've put a right-handed vector into a left-handed library, or referenced an attribute of an object which doesn't exist. But being able to create a simple dialog with a REPL (read/eval/print/loop) in it to do the initial exploration of the EA COM automation interface was very handy.

The thing I dislike most in Python is that it doesn't actually use indentation to indicate blocks (I read Ken Arnold's chapter in The Best Software Writing over the weekend, and think I agree). It uses the colon character to indicate a block, and following a colon you have to use indentation. I'm always just doing the indentation, and forgetting the colons.