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

Labels: ,

0 Comments:

Post a comment

<< Home