#!/usr/bin/python

import sys
import time

def clone(A):
	result = []
	for item in A:
		result.append(item)
	return result

def equal(A, B):
	if (len(A) != len(B)): return False
	n = len(A)
	i = 0
	while (i < n):
		if (A[i] != B[i]): return False
		i += 1
	return True

def contained(A, L):
	for B in L:
		if (equal(A, B)): return True
	return False

def sub(n, V, L):
	global count, E
	L = clone(L)
	L.append(clone(V))
	k = 0
	while (k < n):
		V[k] = 1 - V[k]
		if (contained(V, L)):
			pass
		elif (equal(V, E)):
			count += 1
		else:
			sub(n, V, L)
		V[k] = 1 - V[k]
		k += 1

def sub2(n):
	L = []
	V = [0]*n
	E = [1]*n
	R = [0]*(2**n)
	stack = [(V, L)]
	while (len(stack)):
		V, L = stack.pop()
		L.append(clone(V))
		k = 0
		while (k < n):
			V[k] = 1 - V[k]
			if (contained(V, L)):
				pass
			elif (equal(V, E)):
				R[len(L)] += 1
			else:
				stack.append((clone(V), clone(L)))
			V[k] = 1 - V[k]
			k += 1
	return R

def old():
	t = time.time()
	R = sub2(int(sys.argv[1]))
	t = time.time() - t

	i = 0
	count = 0
	while (i < len(R)):
		if (R[i] == 0): i += 1; continue
		print 'L='+str(i)+', N='+str(R[i])
		count += R[i]
		i += 1

	print 'Total: '+str(count)
	print 'Time taken: '+str(t)+' seconds'

def calcshapes(n, l):
	# e.g. UUDDUU for n=4, l=8
	#      UUDDUUDU for n=4, l=10
	#      UUU for n=5, l=5
	number = (l-n)/2 # number of D's
	length = l-4 # length of string when ignoring the first and last characters, which must be U's
	if (length <= 0) or (number == 0): return ['U'*l]
	result = []; i = range(number)
	while (i[number-1] < length):
		ar = ['U']*length
		for j in i:
			ar[j] = 'D'
		j = 0
		while (j < len(i)):
			i[j] += 1
			if (j == len(i)-1): break
			if (i[j+1] == i[j]):
				k = 0
				while (k <= j):
					i[k] = k
					k += 1
			else:
				break
			j += 1
		j = 0; k = 2; ok = True
		while (j < length):
			if (ar[j] == 'U'):
				k += 1
			else:
				k -= 1
			if (k <= 0) or (k >= n):
				ok = False
				break
			j += 1
		if ok: result.append('UU'+''.join(ar)+'UU')
	return result

n = int(sys.argv[1])
l = n
lmax = (2**n) - (3 + (-1)**n)/2
ctotal = 0; ctime = 0
print '# Generating shapes for dimension: '+str(n)
print 'shapes = ['
while (l <= lmax):
	t = time.time()
	r = calcshapes(n, l)
	t = time.time() - t
	total = len(r)
	ctotal += total
	ctime += t
	if (l > n): print ','
	print str(r)
	print '# Length: '+str(l)
	print '# Total: '+str(total)+', cumulative total: '+str(ctotal)
	print '# Time: '+str(t)+'s, cumulative time: '+str(ctime)+'s'
	l += 2
print ']'
print '# Finished'