Assignment 2 - The Mines of Moria

All submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s Academic Dishonesty and Plagiarism policies.

Story

Dwarves love digging for treasure and our lovely dwarves at the Moria Gold Digging Company of Middle-Earth are no exception. In fact, they have perfected their method of mining gold: they dig a straight line until they find gold and only at locations where they previously found this precious metal they branch out to search in different directions. To maintain the stability of their mining operation and avoid collapsing tunnels, they take extra care to ensure that none of their tunnels links up with any existing ones. In other words, their mining tunnels form. a tree.

The administrative section of the Moria Gold Digging Company has hired you to assist them with keeping track of what tunnels exist and how much gold can be found at each location. As the dwarves mine gold from existing locations and look around, the available gold at each location may need to be updated.

To allow for efficient retrieval of the most prosperous locations of gold, you’re asked to maintain for each node of the tree the sum of the k highest amounts of gold in the subtree rooted at that node. Note that k is given to you at construction time and won’t change during the execution, but you can’t assume anything about the value of k itself; it can be anything between 1 and n (the number of nodes in the tree).

Unfortunately for the dwarves, the land of Middle-Earth isn’t exactly stable. Because of this, occasionally the tunnels move, changing the edges within our tree. After extensive research, the dwarves discovered that their tunnels always form. a tree, even after the tunnels are changed, but which gold locations are connected can change.

And finally, dwarves do sometimes dig too deep… This causes lava from the core of Middle-Earth to engulf their tunnels, destroying them in the process. The extreme heat, however, also melts all the gold and deposits it at the root of the engulfed subtree. Our data structure should be able to handle these changes as well.

Informally, our implementation should support the following operations:

l Update the amount of gold available at a node.

l Insert a new node, connecting it to an existing one. This helps to keep track of the newly dug tunnels.

l Return the summed value of the k highest amounts of gold in the subtree of a given node.

l Move the subtree rooted at a given node. This models the changing tunnels of Middle-Earth.

l Keep track of the effects of lava by removing subtrees and updating the amount of gold stored.

All operations need to maintain that every node correctly stores the sum of the k highest gold locations in its subtree.

Your Task

Maintain a tree where each node in the tree holds a gold value as its key, as well as the property k_sum. The value of the "k_sum" is equivalent to the summed gold value of the k highest gold values in the subtree of the node.

Example with k = 1:

Move Subtree

You must also support the move_subtree(node_a, node_b) function, where the subtree rooted at node_a is made into a child of node_b. If node_b already has children, your function should make node_a the last child. You must ensure that the k_sum property is correct for all nodes, after moving the subtree. You can assume that node_b isn’t in the subtree of node_a and you don’t have to check for this.

Example:

Melt Subtree

Your tree must support the melt_subtree(node_a) operation. When called, the function removes the subtree rooted at node_a and update the gold value of node_a with the sum of the gold in its (removed) subtree. You must ensure that the k_sum property is correct for all nodes, after moving the subtree.

Example:

You should strive to make your implementation as efficient as possible. Note that while we don’t explicitly test for the efficiency of your implementation, using inefficient implementations may cause timeouts on Ed.

TO IMPLEMENT:

You will need to implement these functions:

node.py

__init_

add_child

update_gold

return_k_sum

tree.py

put

ove_subtree

melt_subtree

(Note, you can add additional functions and variables to the classes as you see fit, so feel free to modify and extend those as long as you leave the existing function signatures and variables intact.)

Code

node.py

Functions

__init__(gold, k):

Initialises the properties of the node.

add_child(child_node):

Adds the child node as the last child of the node.

Runs calculations for updating the k_sum

is_external():

Checks if the node is a leaf.

get_children() (OR node.children):

Returns the children of that node.

update_gold(gold):

Sets the gold of the node.

Runs calculations for updating the k_sum.

return_k_sum() (OR node.k_sum):

Returns the k_sum of that node.

tree.py:

The main tree file, holds all interaction with trees and nodes.

Functions

put(node_a, node_b)

Add node B as the last child to node A.

move_subtree(node_a, node_b)

Move node A to become the last child of node B.

Runs calculations for updating the k_sum.

melt_subtree(node)

Removes the subtree of the node and updates the node’s gold with the sum of the gold in its subtree

Runs calculations for updating the k_sum.

Testing

We have provided you with some test cases in the tests directory of this repository. We will be using unit tests provided with the unittest package of python.

Running Tests

From the base directory (the one with node.py and tree.py), run

python -m unittest -v test_sample_tree.py test_sample_node.py

Or, running all the tests by:

python -m unittest -vv

"""

Tree Node

----------

This class represents an individual Node in a Tree.

Each Node consists of the following properties:

- children: List of child Nodes

- parent: Pointer to the parent Node in the tree

- gold: The gold at this point

- k_sum: The sum of the k highest gold values in the subtree rooted at this node

The class also supports the following functions:

- add_child(Node): Adds the given Node as a child

- is_external(): Returns True if the Node is a leaf node

- get_children(): Returns the children of this node

- update_gold(int): Updates the gold value at this node to the given value

- return_k_sum(): Returns the k_sum at this node

Your task is to complete the following functions which are marked by the TODO comment.

Note that your Node should automatically update the k_sum when the subtree changes (if branches change or gold values are updated!)

You are free to add properties and functions to the class as long as the given signatures remain identical

"""

class Node():

# These are the defined properties as described above

children: list['Node']

parent: 'Node'

gold: int

k_sum: int

k: int

def __init__(self, gold: int, k: int) -> None:

"""

The constructor for the Node class.

:param gold: The gold of the node.

:param k: Value used to calculate k_sum.

"""

# TODO Initialize the properties of the node

def add_child(self, node: 'Node') -> None:

"""

Adds the given node as a child of the current node.

The given node is guaranteed to be new and not a child of any other node.

:param node: The node to add as the child

"""

# TODO Add the given node as the right child of the current node

def is_external(self) -> bool:

"""

Returns True if the node is a leaf node.

:return: True if the node is a leaf node.

"""

return len(self.children) == 0

def update_gold(self, gold: int) -> None:

"""

Updates the gold of the current node.

:param gold: The new gold of the node.

"""

# TODO Update the gold of the node

def get_children(self) -> list['Node']:

"""

Returns the children of the current node.

:return: The children of the current node.

"""

return self.children

def return_k_sum(self) -> int:

"""

Returns the k_sum of the current node.

:return: The k_sum of the current node.

"""

# TODO Return the k_sum of the node