Re: code128.py

Robin Becker <[email protected]> Mon, 4 Jan 2016 14:04:06 +0000
Newsgroups	gmane.comp.python.reportlab.user
Message-ID	<[email protected]>
Hi Klaas,

had a chance to look at this code and figured out you're doing a forward pass 
over the translated sets.

Nothing terribly wrong with the code, but I did come to the conclusion that we 
might be missing something related to the actual optimality


I ran this code as a test

ttdigskf.py

rom string import digits
def _trailingDigitsToC(self, l):
	# Optimization: trailing digits -> set C double-digits

	i = 0
	nl = []
	while i < len(l):
		startpos = i
		rl = ['TO_C']
		savings = -1 # the TO_C costs one character
		while i < len(l):
			if l[i] in (['START_B','TO_A','TO_B']):
				set = 'TO' + l[i][-2:]
				break
			elif l[i] == '\xf1':
				rl.append(l[i])
				i += 1
				continue
			elif len(l[i]) == 1 and l[i] in digits \
			 and len(l[i+1]) == 1 and l[i+1] in digits:
				rl.append(l[i] + l[i+1])
				i += 2
				savings += 1
				continue
			else:
				break

		if savings > 0:
			nl = nl + rl
			if not l[i]=='STOP':
				nl.append(set)
			nl.append(l[i])
		else:
			nl = nl + l[startpos:i+1]
		i += 1
	return nl

for x,l in enumerate((
		'START_B b b b b 1 2 3 4 5 6 b b b STOP',
		'START_B b b b b 1 2 3 4 5 b b b STOP',
		'START_B b b b b 1 2 3 4 b b b STOP',
		'START_B b b b b 1 2 3 b b b STOP',
		'START_B b b b b 1 2 b b b STOP',
		'START_B b b b b 1 b b b STOP',
		'START_B b b b b 1 2 3 4 5 6 TO_A a a STOP',
		'START_B b b b b 1 2 3 4 TO_A a a STOP',
		'START_B b b b b 1 2 3 TO_A a a STOP',
		'START_B b b b b 1 2 TO_A a a STOP',
		'START_B b b b b 1 TO_A a a STOP',
		'START_B b b b b 1 2 3 4 5 6 STOP',
		'START_B b b b b 1 2 3 4 5 STOP',
		'START_B b b b b 1 2 3 4 STOP',
		'START_B b b b b 1 2 3 STOP',
		'START_B b b b b 1 2 STOP',
		'START_B b b b b 1 STOP',
		)):
	l = l.split()
	lo = _trailingDigitsToC(None, l)
	print '%2d: %s(%d) --> %s(%d)' % (x,' '.join(l),len(l),' '.join(lo),len(lo))

result is

C:\code\hg-repos\reportlab>tmp\ttdigskf.py
  0: START_B b b b b 1 2 3 4 5 6 b b b STOP(15) --> START_B b b b b TO_C 12 34 
56 TO_B b b b STOP(14)
  1: START_B b b b b 1 2 3 4 5 b b b STOP(14) --> START_B b b b b TO_C 12 34 
TO_B 5 b b b STOP(14)
  2: START_B b b b b 1 2 3 4 b b b STOP(13) --> START_B b b b b TO_C 12 34 TO_B 
b b b STOP(13)
  3: START_B b b b b 1 2 3 b b b STOP(12) --> START_B b b b b 1 2 3 b b b STOP(12)
  4: START_B b b b b 1 2 b b b STOP(11) --> START_B b b b b 1 2 b b b STOP(11)
  5: START_B b b b b 1 b b b STOP(10) --> START_B b b b b 1 b b b STOP(10)
  6: START_B b b b b 1 2 3 4 5 6 TO_A a a STOP(15) --> START_B b b b b TO_C 12 
34 56 TO_A TO_A a a STOP(14)
  7: START_B b b b b 1 2 3 4 TO_A a a STOP(13) --> START_B b b b b TO_C 12 34 
TO_A TO_A a a STOP(13)
  8: START_B b b b b 1 2 3 TO_A a a STOP(12) --> START_B b b b b 1 2 3 TO_A a a 
STOP(12)
  9: START_B b b b b 1 2 TO_A a a STOP(11) --> START_B b b b b 1 2 TO_A a a STOP(11)
10: START_B b b b b 1 TO_A a a STOP(10) --> START_B b b b b 1 TO_A a a STOP(10)
11: START_B b b b b 1 2 3 4 5 6 STOP(12) --> START_B b b b b TO_C 12 34 56 STOP(10)
12: START_B b b b b 1 2 3 4 5 STOP(11) --> START_B b b b b TO_C 12 34 TO_B 5 
STOP(11)
13: START_B b b b b 1 2 3 4 STOP(10) --> START_B b b b b TO_C 12 34 STOP(9)
14: START_B b b b b 1 2 3 STOP(9) --> START_B b b b b 1 2 3 STOP(9)
15: START_B b b b b 1 2 STOP(8) --> START_B b b b b 1 2 STOP(8)
16: START_B b b b b 1 STOP(7) --> START_B b b b b 1 STOP(7)

where clearly something is wrong with #6, #7  (TO_A duplicated) and #2, #12 
switches to C without a net gain (because we needed a TO_B to go back).

I changed the algorithm slightly to avoid doing some work early and this version 
appears to work slightly better

def _trailingDigitsToC(self, l):
	# Optimization: trailing digits -> set C double-digits

	i = 0
	nl = []
	while i < len(l):
		startpos = i
		rl = []
		savings = -1 # the TO_C costs one character
		while i < len(l):
			if l[i] in (['START_B','TO_A','TO_B']):
				j = i
				break
			elif l[i] == '\xf1':
				rl.append(l[i])
				i += 1
				continue
			elif len(l[i]) == 1 and l[i] in digits \
			 and len(l[i+1]) == 1 and l[i+1] in digits:
				rl.append(l[i] + l[i+1])
				i += 2
				savings += 1
				continue
			else:
				break

		ta = not (l[i]=='STOP' or j==i)
		if savings > int(ta):
			nl += ['TO_C']+rl
			if ta:
				nl.append('TO'+l[j][-2:])
			nl.append(l[i])
		else:
			nl += l[startpos:i+1]
		i += 1
	return nl


if I use that then the tests show this

C:\code\hg-repos\reportlab>tmp\ttdigs.py
  0: START_B b b b b 1 2 3 4 5 6 b b b STOP(15) --> START_B b b b b TO_C 12 34 
56 TO_B b b b STOP(14)
  1: START_B b b b b 1 2 3 4 5 b b b STOP(14) --> START_B b b b b 1 2 3 4 5 b b 
b STOP(14)
  2: START_B b b b b 1 2 3 4 b b b STOP(13) --> START_B b b b b 1 2 3 4 b b b 
STOP(13)
  3: START_B b b b b 1 2 3 b b b STOP(12) --> START_B b b b b 1 2 3 b b b STOP(12)
  4: START_B b b b b 1 2 b b b STOP(11) --> START_B b b b b 1 2 b b b STOP(11)
  5: START_B b b b b 1 b b b STOP(10) --> START_B b b b b 1 b b b STOP(10)
  6: START_B b b b b 1 2 3 4 5 6 TO_A a a STOP(15) --> START_B b b b b TO_C 12 
34 56 TO_A a a STOP(13)
  7: START_B b b b b 1 2 3 4 TO_A a a STOP(13) --> START_B b b b b TO_C 12 34 
TO_A a a STOP(12)
  8: START_B b b b b 1 2 3 TO_A a a STOP(12) --> START_B b b b b 1 2 3 TO_A a a 
STOP(12)
  9: START_B b b b b 1 2 TO_A a a STOP(11) --> START_B b b b b 1 2 TO_A a a STOP(11)
10: START_B b b b b 1 TO_A a a STOP(10) --> START_B b b b b 1 TO_A a a STOP(10)
11: START_B b b b b 1 2 3 4 5 6 STOP(12) --> START_B b b b b TO_C 12 34 56 STOP(10)
12: START_B b b b b 1 2 3 4 5 STOP(11) --> START_B b b b b 1 2 3 4 5 STOP(11)
13: START_B b b b b 1 2 3 4 STOP(10) --> START_B b b b b TO_C 12 34 STOP(9)
14: START_B b b b b 1 2 3 STOP(9) --> START_B b b b b 1 2 3 STOP(9)
15: START_B b b b b 1 2 STOP(8) --> START_B b b b b 1 2 STOP(8)
16: START_B b b b b 1 STOP(7) --> START_B b b b b 1 STOP(7)

what do you think?
-- 
Robin Becker