203.171.122.38: Linked to the output

203.171.122.38 — Tue, 21 Mar 2006 14:28:15 GMT

Linked to the output

←Older revision		Revision as of 14:28, 21 March 2006
Line 275:		Line 275:
	#print child.content, ' ',		#print child.content, ' ',
	#print ' '		#print ' '
		+
		+
		+	See the [[Diagram G script output]]

203.171.122.38: The script for drawing ASCII art trees for help with Diagram G and related problems

203.171.122.38 — Tue, 21 Mar 2006 14:27:13 GMT

The script for drawing ASCII art trees for help with Diagram G and related problems

New page

#18:30 Tuesday 21 March 2006
#By Evgeni Sergeev
#First, construct a tree. Then call propagateSubtreeWidths() on the root.
#Then call printTree() on the root.

import sys

class Node:
"""Represents a node in the tree. """
def __init__(self, content):
self.children = []
self.content = content
self.subtree_width = 1
self.root_offset = 0

def addChild(self, child):
self.children.append(child)

def propagateSubtreeWidths(self):
for child in self.children:
child.propagateSubtreeWidths()

if len(self.children) == 1:
self.subtree_width = self.children[0].subtree_width
self.root_offset = self.children[0].root_offset
elif len(self.children) == 0:
self.subtree_width = len(str(self.content)) + 1
self.root_offset = 0
else:
n = 0
for child in self.children:
n = n + child.subtree_width
self.subtree_width = n

right_child_relative_offset = self.subtree_width - \\
(self.children[len(self.children)-1].subtree_width - \\
self.children[len(self.children)-1].root_offset)

self.root_offset = (self.children[0].root_offset + \\
right_child_relative_offset) / 2

def printLineTwo(self):
n = self.root_offset - len(str(self.content))/2
if n < 0: n = 0
sys.stdout.write(' '*n)
sys.stdout.write(str(self.content))
sys.stdout.write(' '*(self.subtree_width - n - len(str(self.content))))

def printLineOne(self):
n = self.root_offset
sys.stdout.write(' '*n)
sys.stdout.write('|')
sys.stdout.write(' '*(self.subtree_width - n - 1))

def printLineThree(self, horizontal_char = '_'):
if len(self.children) > 0:
if len(self.children) == 1:
self.printLineOne()
elif len(self.children) == 0:
sys.stdout.write(' '*self.subtree_width)
else:
left_child_offset = self.children[0].root_offset

right_child_offset = self.subtree_width - \\
(self.children[len(self.children)-1].subtree_width - \\
self.children[len(self.children)-1].root_offset)

left_dashes = self.root_offset - left_child_offset - 1
right_dashes = right_child_offset - self.root_offset - 1

left_spaces = self.root_offset - left_dashes
right_spaces = self.subtree_width - left_spaces - left_dashes \\
- 1 - right_dashes

sys.stdout.write(' '*left_spaces)
sys.stdout.write(horizontal_char*left_dashes)
sys.stdout.write('|')
sys.stdout.write(horizontal_char*right_dashes)
sys.stdout.write(' '*right_spaces)

def addChildren(self, queue, levels, parent_level):
queue.extend(self.children)
new_levels = []
for child in self.children:
new_levels.append(parent_level + 1)
levels.extend(new_levels)

def printTree(self, upside_down = 0):
queue = [self]
levels = [0]
n = 0
#Breadth queue
while n < len(queue):
queue[n].addChildren(queue, levels, levels[n])
n = n + 1
#levels[n] contains the level of n

if not upside_down:
i = 0
while i < n:
start_of_level = i
end_of_level = i
while end_of_level < n and \\
levels[end_of_level] == levels[start_of_level]:
end_of_level = end_of_level + 1
end_of_level = end_of_level - 1

for item in range(start_of_level,end_of_level+1):
queue[item].printLineOne()
print ' '

for item in range(start_of_level,end_of_level+1):
queue[item].printLineTwo()
print ' '

for item in range(start_of_level,end_of_level+1):
queue[item].printLineThree()
print ' '

i = end_of_level + 1

else:
i = n - 1
while i >= 0:
start_of_level = i
end_of_level = i
while start_of_level >= 0 and \\
levels[end_of_level] == levels[start_of_level]:
start_of_level = start_of_level - 1
start_of_level = start_of_level + 1

for item in range(start_of_level,end_of_level+1):
queue[item].printLineThree('"')
print ' '

for item in range(start_of_level,end_of_level+1):
queue[item].printLineTwo()
print ' '

for item in range(start_of_level,end_of_level+1):
queue[item].printLineOne()
print ' '

i = start_of_level - 1

def outputTree(f, n):
n = n + 1
nodes = range(n-1)
i = 1
while i < n:
nodes[i-1] = Node(i)
if (f(i) != i):
nodes[f(i)-1].addChild(nodes[i-1])
i = i + 1

nodes[0].propagateSubtreeWidths()
nodes[0].printTree(upside_down = 1)

print "Diagram G up to n=55."
def G(n, cache={}): #cache is shared between calls (!)
if n == 0:
return 0

if n not in cache:
cache[n] = n - G(G(n-1))

return cache[n]

outputTree(G, 55)

print "\
\
Diagram H up to n=59."
def H(n, cache={}):
if n == 0:
return 0

if n not in cache:
cache[n] = n - H(H(H(n-1)))

return cache[n]

outputTree(H, 59)

print "\
\
Diagram I up to n=69."
def I(n, cache={}):
if n == 0:
return 0

if n not in cache:
cache[n] = n - I(I(I(I(n-1))))

return cache[n]

outputTree(I, 69)

print "\
\
Diagram J up to n=80."
def J(n, cache={}):
if n == 0:
return 0

if n not in cache:
cache[n] = n - J(J(J(J(J(n-1)))))

return cache[n]

outputTree(J, 80)

print "\
\
The tree for Q(n) up to n=64."
def Q(n, cache={}):
if n == 0:
return 0

if n not in cache:
cache[n] = n - Q(n-1)

return cache[n]

outputTree(Q, 64)

print "\
\
The mirror tree MG(n) up to n=55."

def L(n, cache={}):
if n == 1:
return 1

if n not in cache:
cache[n] = L(G(n)) + 1

return cache[n]

def F(n, cache={0:1, 1:1}):
if n == 1 or n == 0:
return 1

if n not in cache:
keys = cache.keys()
keys.sort(reverse=True)
max_known = keys[0]
a, b = F(max_known), F(max_known - 1)
for i in range(max_known + 1, n + 1):
a, b = a + b, a
cache[i] = a

return cache[n]

def M(n):
if n == 1:
return 1

return F(L(n)) - (n - F(L(n)-1)) + 1

def MG(n):
return M(G(M(n)))

outputTree(MG, 55)

#Debugging code.
#print nodes

#for node in nodes:
#print node.content, ': ',
#for child in node.children:
#print child.content, ' ',
#print ' '

Diagram G script - Revision history

203.171.122.38: Linked to the output

203.171.122.38: The script for drawing ASCII art trees for help with Diagram G and related problems