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.

Delete this entry (admin only).