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.