## 2008-06-28

### 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 timedef 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 Truedef 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:   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 accdef bcd_counter(max): index = 1 while index < max:  value = bcd_select(index)  if value > max:   break  yield value  index = index + 1`

Labels: ,