A programming challenge

halbig.py

"""
Write logic that dynamically outputs a string of 35 characters.
The string is composed of 7 distinct letters. Each letter is used 5 times.
Any subset of 3 characters must be unique from any other subset of 3 characters.
Any subset of 3 characters can only have zero or ONE of the same letter.
"""
from collections import Counter
from itertools import permutations

def sequences(seq, n=3):
	"""
	Find all the contiguous sub-sequences of length `n` of sequence `seq`.
	>>> sequences([0, 1, 7, 3, 4, 5, 10])
	[[0, 1, 7], [1, 7, 3], [7, 3, 4], [3, 4, 5], [4, 5, 10]]
	>>> sequences('ABCDEF')
	['ABC', 'BCD', 'CDE', 'DEF']
	"""
	assert n < len(seq), 'n must be less than seq'
	subseqs = []
	for i, _ in enumerate(seq):
		subseq = seq[i:i+n]
		if len(subseq) != n:
			continue
		subseqs.append(subseq)
	return subseqs

def sequences_are_unique(seqs):
	return len(seqs) == len({s for s in seqs})

def test(s):
	""" The solution has to pass this test. """
	assert len(s) == 35, 'The string must have a length of 35'
	assert len(set(s)) == 7, 'The string must be composed of 7 unique characters'
	assert set(Counter(s).values()) == {5}, 'Each letter must be used exactly 5 times.'
	assert sequences_are_unique(sequences(s)), 'Any subset of 3 characters must be unique'

def solve(chars='PROBLEM'):
	assert len(chars) == 7, 'I need 7 characters.'
	assert len(chars) == len(set(chars)), 'Characters must be unique.'

	# This gives us the correct set, now we need to rearrange the subsets
	s = chars * 5
	
	# The algorithm is to get the first sub-sequence that's used more than once 
	# in the string, replace the first occuranceof that subsequence with another 
	# permutation, and repeat until the string contains unique sub-sequences.
	seqs = sequences(s)
	used_permutations = set()

	while not sequences_are_unique(seqs):
		most_common = Counter(seqs).most_common()[0][0]
		perms = [''.join(p) for p in permutations(most_common) 
							if ''.join(p) not in used_permutations]
		new_permutation = perms[0]
		# print 'Replace %s with %s' % (most_common, new_permutation)
		s = s.replace(most_common, new_permutation, 1)
		used_permutations.add(most_common)
		seqs = sequences(s)
		# print s

	return s


if __name__ == '__main__':
	import doctest
	doctest.testmod()

	a = solve()
	test(a)
	print a