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