Logic & Coding Dwarven Mining Expedition
Good luck.
import java.util.Random;
class dwarvenminingexpedition {
public static void main(String[] args)
{
/*
* Welcome to the Dwarven Mining Guild, ninnyhammer.
* Your assignment is to figure out the path with the most gems in it.
* You will be delving into a randomized cave, equipped with nothing more
* than a simple 'map' that shows you the layout of the cave, with
* values for each space.
* Nodes with values of '-1' are caved in, and require an explosive charge
* to open up. Since you're a brand new ninnyhammer working for the guild,
* you will only be equipped with 3 charges.
*
* We will only be providing you with enough food and water for you to make
* a single trip through the cave.
* You can only navigate through the cave once, so your path must be optimal to
* pick up the most amount of gems in a single pass.
*
* Godspeed, Dwarf.
*/
//Generate a randomized cave for the poor souls who have to do this assignment.
BinaryTree bigTree = new BinaryTree(10);
//bigTree.printTree(bigTree.root, 0);
bigTree.root.print();
//bigTree.preorder(bigTree.root);
/*
* Write your method here, the above code initializes the cave and gives you the necessary information to help visualzie.
*/
}
}
// Class containing left and right child
// of current node and key value
class Node {
int num;
Node left, right;
public Node(int num)
{
this.num = num;
left = right = null;
}
/*Use this instead to see your cave. */
public void print()
{
print("", this, false);
}
public void print(String prefix, Node n, boolean isLeft)
{
if (n != null) {
System.out.println (prefix + (isLeft ? "|-- " : "\\-- ") + n.num);
print(prefix + (isLeft ? "| " : " "), n.left, true);
print(prefix + (isLeft ? "| " : " "), n.right, false);
}
}
}
class BinaryTree
{
// Root of Binary Tree
Node root;
boolean leftOrRight = true;
static Random random;
// Constructors
BinaryTree(int num)
{
random = new Random();
root = generateRandomBinaryTree(num);
}
static Node generateRandomBinaryTree(int size)
{
if (size == 0)
return null;
// Choose random sizes for left and right subtrees
int leftSize = random.nextInt(size);
int rightSize = size - 1 - leftSize;
// Generate left and right subtrees recursively
Node leftSubtree = generateRandomBinaryTree(leftSize);
Node rightSubtree = generateRandomBinaryTree(rightSize);
// Create new node with random value
int rand = random.nextInt(50);
if(rand % 5 == 0) { rand = -1;}
Node root = new Node(rand);
// Assign left and right subtrees to children
root.left = leftSubtree;
root.right = rightSubtree;
return root;
}
//More so here for debugging purposes and for your teacher to have a chance at figuring out what the right answer is.
static void inorder(Node temp)
{
if (temp == null)
return;
inorder(temp.left);
System.out.print(temp.num + " ");
inorder(temp.right);
}
static void preorder(Node temp)
{
if (temp == null)
return;
System.out.print(temp.num + " ");
preorder(temp.left);
preorder(temp.right);
}
//A bit of mercy so you can somewhat visualize your tree.
//Unfortunately, your trees are randomized so the answer will change every time.
// static void printTree(Node node, int level)
// {
// if (node != null) {
// printTree(node.right, level + 1);
// System.out.println(" ".repeat(4 * level) + "-> " + node.num);
// printTree(node.left, level + 1);
// }
// }
/*I made a better visualization of your cave, ignore this piece of code. */
}
