# Demo entry 1463337

**CS223**

Submitted by **Erik**
on Mar 04, 2015 at 22:32

Language: Python. Code size: 2.9 kB.

from random import * from operator import * #import matplotlib.pyplot as plt nodes = [] generatedCount = 0 def mark(nodeNum): #mark node if not currently marked if nodes[nodeNum] == 0: nodes[nodeNum] = 1 if nodeNum % 2 == 0 and nodeNum != 0: #node is even sibling = nodeNum - 1 parent = nodeNum/2 - 1 if nodes[sibling] != nodes[parent]: #if node is marked, parent is marked, and sibling is marked if nodes[sibling] == 0: return 1 + mark(sibling) else: return 1 + mark(parent) else: return 1 elif nodeNum % 2 == 1: sibling = nodeNum + 1 parent = (nodeNum-1)/2 if nodes[sibling] != nodes[parent]: #if node is marked, parent is marked, and sibling is marked if nodes[sibling] == 0: return 1 + mark(sibling) else: return 1 + mark(parent) else: return 1 else: return 1 return 0 def randomPermutation(lst): for x in range(len(lst)): num1 = randrange(0,len(lst)) temp = lst[x] lst[x] = lst[num1] lst[num1] = temp return lst def fillTree1(n): N = 2**n -1 global nodes nodes = [0]*N generatedCount = 0 marked = 0 while marked < N: num = randrange(0,N) marked += mark(num) generatedCount += 1 return generatedCount def fillTree2(n): N = 2**n -1 global nodes nodes = [0]*N generatedCount = 0 marked = 0 eligible = [0]*N for x in range(len(eligible)): eligible[x] = x eligible = randomPermutation(eligible) while marked < N: marked += mark(eligible[generatedCount]) generatedCount += 1 return generatedCount def fillTree3(n): N = 2**n -1 global nodes nodes = [0]*N generatedCount = 0 marked = 0 while marked < N: num = randrange(0,N) while nodes[num] == 1: num = randrange(0,N) marked += mark(num) generatedCount += 1 return generatedCount divList = [10.0]*21 #need to do ten times each vals1 = [0]*11 for x in range(10): for x in range(10,21): vals1[x-10] += fillTree1(x) vals1 = map(div, vals1, divList) print vals1 #need to do ten times each vals2 = [0]*1 for x in range(20): for x in range(10,21): vals2[x-10] += fillTree2(x) vals2 = map(div, vals2, divList) print vals2 #need to do ten times each vals3 = [0]*21 for x in range(20): for x in range(10,31): vals3[x-10] += fillTree3(x) vals3 = map(div, vals3, divList) print vals3

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.