Even Tree [HackerRank]

Hi all, I’m sorry about not posting very frequently – thankfully, however, my exams will be coming to a close in the next two weeks, so I will be able to return to regular posting soon.

If you are unfamiliar with graph theory, I recommend that you read my previous post on the subject – it gives an introduction into the topic and the ways in which it appears in competitive programming.

Today, we will solve a relatively simple problem on graph theory which can be found on the ‘HackerRank’ website – given a tree (a graph with no cycles and where any node can be reached from any other node) of N nodes numbered from 1 (which is the root node) to N, our program must find the maximum number of edges it can remove from this tree to obtain a set of trees (commonly called a ‘forest’) where every tree has an even number of nodes.

The source code of my final solution to this problem can be found here.

The problem statement states that it is always possible to remove edges from the main tree to create a forest consisting of only trees with even numbers of nodes, so we do not need to concern ourselves with difficult edge cases. This brings us to a relatively simple solution: any ‘subtree’ (a smaller tree which is part of the main tree – it may have its own root separate from the main root) with an even number of nodes can be separated from the node connecting to its root – therefore, the maximum number of edges which can be removed from the tree to satisfy the problem statement is equal to the number of subtrees with even numbers of nodes. We have now reduced the problem to counting the number of nodes in each subtree.

Our first course of action is to devise a method for storing the tree – the technique I used is known as an ‘adjacency list’. In C++, this is essentially a vector where each element represents a node. For simple graphs like the ones used in this problem, each node can be represented by a vector of integers, with each integer representing a node which can be reached from the node represented by the vector itself. Initially our adjacency list will be empty, however, we will fill it by taking each edge from input as two integers (which represent the two nodes connected by the edge in question) connecting the deeper of the two nodes to the node closer to the root (not vice-versa! The edges in our list only need to be unidirectional).

EvenTree1.png

After creating the adjacency list, we can write a function which performs a depth-first traversal of the tree, counting the number of nodes in each subtree by travelling to each node in turn and counting the number of children it has and adding 1 to this value (this addition represents the current node, which acts as the root). We can do this elegantly using recursion – the numbers of nodes in the subtrees rooted at the deepest points of the tree are always 1 (as these nodes have no child nodes). By this logic, we can have our recurring function return 1 when it reaches a node with no child nodes, and in order to calculate the numbers of nodes in the other subtrees, we recur for every child node of each potential root node and save the sum of the results.

EvenTree2.png

Once we have calculated the number of nodes in every possible subtree of the main tree, we can just iterate through our results and increment our final answer by 1 every time we find a subtree with an even number of nodes. Once this process is complete, we can print out our final value.

EvenTree3.png

Tetris for Android in the Unity Engine – Part 3 (Tetrominoes)

Good day all – in this post, we will incorporate full ‘tetrominoes’ (shapes consisting of multiple squares) into our mobile ‘Tetris’ game. We have already finished implementing much of the functionality which does this, however, some of the code which was used to power the grid system when only single blocks were used will need to be rewritten in order to accommodate the more complex shapes. Additionally, we will also extend the code which moves the blocks sideways such that a tetromino will only be moved if there are no other fixed blocks in the path.

The final product of this post can be downloaded here.

Staying true to the original Tetris, our version will use the same tetromino shapes which the classic version used – as shown below:

tetprefabs2

In order to create these tetromino objects, we first need to create the ‘materials’ – these are Unity’s method of storing the ways 2D graphics are mapped onto 3D objects (note that we are using 3D cubes in our game, and they are made to appear 2D by the camera’s orthographic projection). In this case, creating the required materials is relatively simple, as each tetromino is a single solid colour. To create a new material, right-click the project directory, move to the ‘create’ drop-down menu and choose the ‘material’ option. This new material’s properties will then appear the in the inspector tab – from here, we switch the material’s type to ‘Unlit/Color’. We can then select the colour of the material using a hue/saturation grid by clicking on the sole ‘main colour option’. There are seven different tetromino colours used in the original Tetris, so we will create seven different materials.

makematerialmat_edit

Now that we have created the required materials, we can use the Unity editor to construct the actual tetromino prefabs – this can be done by dragging a copy of the ‘SingleBlock’ prefab created in the previous post into the scene tab, duplicating it to make multiple separate blocks and then using the level editing tools to create the desired shape. A material can then be dragged from the project tab onto a block in the scene view in order for the material to be applied to the block. The Unity editor boasts a useful feature called ‘vertex snapping’ – if the ‘V’ key is held, a vertex on a single game object can be selected, and then dragged onto a vertex of another object such that the two vertices occupy the same position in the world space. This feature can thus be used to position two cubes next to each other perfectly.

vs5.PNG
The level-editing features built into the Unity engine can be used to build replicas of every possible tetromino shape present in the original game (we only need to build a tetromino for every single colour we intend to use, as we will implement a block rotation mechanic later on). In order to convert a group of blocks into a single tetromino, select all of the blocks from a tetromino except one in the hierarchy and then drag the selected blocks onto the unselected block (effectively making the unselected block the ‘parent’ of the selected blocks). The model in the hierarchy will then appear as follows:

singletetmodel.PNG

The parent block of a tetromino can then be dragged into the project tab in order for a prefab to be created.

Once we have created the tetromino prefabs, we will need to alter the code we wrote in the previous posts such that it accommodates shapes consisting of multiple blocks. In the last post, we designed our ‘Tick ()’ function such that it processed every single falling block from a list of all falling blocks – so our first course of action now will be to create a new script for our tetromino models. This script should get attached to the parent blocks (as this makes accessing the child blocks relatively simple). In the ‘Start ()’ function of this script (the function which gets called as the object is instantiated), we first obtain access to the ‘MainControl’ script which we wrote in earlier posts. We also save every single block of the tetromino in question into a list of GameObjects using a ‘while’ loop – as each block is saved, it has its initial position saved into the grid array and is separated from the parent block.

Given the manner in which the ‘Tick ()’ function works (it iterates through a list of moving blocks and processes the movement of each block in turn), it is necessary for us to ensure that the blocks saved in the list of moving blocks are ordered by their positions along the axis, with the lowest blocks saved into the lowest array indices. This is because the ‘Tick ()’ functions sets the grid value referenced by a given object’s current position to ‘null’ (which effectively states that the variable references nothing) before moving the block downwards and updating the grid value referenced by the block’s new position. Therefore, if the blocks at the top of a tetromino (that is, a group of moving blocks) had their movement processed first, there is a high risk of their corresponding grid values being incorrectly reset to ‘null’ when the lower blocks are processed (since all blocks are moved downwards, this is guaranteed to happen if one block is one unit above another block, and is moved downwards first). This would cause blocks to appear to ‘fall through’ other blocks, since the values stored in the grid array are not representative of what is actually being shown on the screen. We can avoid this issue by making sure that the list of moving blocks in MainControl is always sorted appropriately. Since tetrominoes are relatively small – that is, they only consist of several block objects each, a simple selection sorting algorithm can be used to create a new, sorted list in the script attached to a tetromino’s parent block. Moreover, since this script has access to MainControl, the value of the list of moving blocks in MainControl can be directly assigned to the sorted list in the tetromino script.

One of the other issues which has cropped up as a result of multiple blocks falling at the same time is related to the check performed during every ‘Tick ()’ call – every time the function is executed, each block in the falling block list is checked to ensure if there are any blocks under it. If this is the case, all of the blocks in the list are frozen in place and the list is cleared. This logic allows falling squares to be stacked on top of each other, however, the tetromino models do contain blocks already positioned on top of each other (for instance, the square tetromino has two rows of blocks on top of each other, with the rows containing two blocks each). The problem here is that this code causes tetrominoes to become frozen while still falling (as the stacks of blocks in the tetrominoes causes the check mentioned earlier to return true). In order to remedy this, the algorithm must be able to distinguish between blocks with are part of the current falling tetromino, and blocks which have already fallen and are already frozen in place. This can be done using Unity’s ‘tag’ system, which allows us to give each GameObject in the world a string property which can be referenced within the code. In order to create a tag, we select the GameObject, open the tag menu from the inspector window, type in the string value of the new tag and then assign this tag value to the tag of the selected GameObject. The object’s tag can then be accessed within the code using ‘gameObject.tag’ – in our solution, we can create two tags: one which states that a block is moving and another which states that a block is frozen. Newly created tetrominoes should, by default, have all of their blocks use the ‘moving’ tag (so we need to assign this tag value to every block in every tetromino prefab. Furthermore, tetrominoes which have had their falls halted will have all of their blocks’ tag values switched to the ‘frozen’ tag. The screenshot below shows the ‘tag’ menu of a block in the yellow tetromino prefab – notice that it has already had its tag value set to ‘moving’:

tetrominos.png

The following screenshot shows how the mentioned fix has been implemented in the code:

tetblockunder

Another problem which we must tackle is accounting for the varying sizes of each tetromino object (since we are no longer working with 1×1 blocks, we run a risk of having out-of-bounds errors occur when we reference grid positions, if a tetromino is instantiated and positioned on the edges of the grid). this has been done by ensuring that the tetrominoes are not instantiated on the top row, and saving the width of each individual shape so that the value can be used to pick a suitable set of columns for each newly created set of blocks. In order to instantiate a tetromino instead of a single block, we can save all of the tetromino prefabs into an array (using the inspector) and then use ‘Random.Range ()’ to pseudo-randomly select a prefab to clone.

tetarray2.PNG

tetprefabs

The following images are of the final tetromino prefab script, and the changes to the block instantiation mechanics:

tetrominofunctetrominostart

tetrominoinstantiate.PNG

It is possible for the player to create an excessive number of falling tetrominoes through aggressively hitting the ‘speed up time’ button immediately after a new tetromino is created. In order to ensure that each newly created tetromino has an opportunity to be passed through the ‘Tick ()’ function at least once, we can introduce a boolean flag which is checked whenever we attempt to create a new set of falling blocks, and is reset whenever we perform a full ‘Tick ()’ with the current set.

This slideshow requires JavaScript.

Finally, we will edit the functions used to move tetrominoes left and right such that they do not cause the falling blocks to move if other blocks are in the way (in the last post, the functions only prevented movement if the blocks were on the edges of the grid). This is done relatively easily – we can check the values of the cells immediately to the left of right of each falling block, and if these values are not null (that is, a block is already in that grid cell), then the function returns without the blocks being moved.

tetrighttetrominoleft2

We have made great strides on this project! In the next post, we will implement the tetromino rotation mechanic.

 

 

 

 

The Leapfrog Problem

My mathematics teacher recently presented my class with an interesting problem he named the ‘Leapfrog Problem’. The idea revolves around a frog positioned on an infinitely large 2D plane – this frog can ‘leap over’ another point in this plane. When the frog performs this action, it covers the distance from its current position to the point, and then makes the same movement a second time. This motion can be thought of as the frog moving along a line where the point is the line’s midpoint.

Leapfrog1.png

In the ‘Leapfrog Problem’, the plane contains four points – one initial position for the frog, and three other points named A, B and C. These four points can be positioned anywhere on the plane. The frog first leaps over point A – after this has been done, the frog leaps over point B starting from its current position after its leap over point A. Then, the frog leaps over point C. This cycle repeats itself, with the frog leaping over A, B and C in turn once more. However, when the frog leaps over C a second time, it will always land at its initial position, regardless of how the origin and points A, B and C have been positioned. The objective of the problem is to prove why this is the case. In the images below, a relatively simple example of the frog’s movement is illustrated:

leapfrogaction1

leapfrogaction2

leapfrogaction3

leapfrogaction4

leapfrogaction5

leapfrogaction6

Solution 

Proving why the sequence of jumps always returns the frog to its starting position can be done elegantly using vectors. The key insight is that if we represent the position of the frog using a position vector (with the starting point as the origin) and we define three vectors (with each vector leading from the origin to one of the three points A, B or C), we can always calculate a route from the frog’s position to one of the three defined points. The vector representing this route can then be multiplied by 2, in order to give a vector which describes the ‘leaping’ motion.

Leapfrog7.png

In order to calculate a route from the frog’s position to one of the three defined points, we first invert the frog’s position vector (this gives a vector which leads from the frog’s position back to the origin) and then add the vector which leads from the origin to the target point. The vector which leads from the origin to point A can be defined as a, while the vector which leads from the origin to point B can be defined as b, and the vector which leads from the origin to point C can be defined as c. If we model the movement of the frog using vector manipulation, we can see that the frog’s position vector always evaluates to 0 after its second leap over the point C – this proves that the frog will always return to the origin.

LeapfrogVectorManipulation.PNG

Since we have not given any of our variables specific values – that is, we have only defined our vectors using the arbitrarily positioned points specified by the problem, and they always cancel each other out – neither the magnitude nor the direction of any of our vectors has any effect on the final outcome of the manipulation, we have shown that the frog will always return to the origin regardless of how its starting position and the points A, B and C have been positioned.

The original source for the Leapfrog Problem can be found here.

Interesting Geometry Questions from the Intermediate Maclaurin Mathematical Olympiad (Part 2 – 2010)

This post covers a second set of geometry problems from the Intermediate Maclaurin Mathematical Olympiad (a mathematics competition run by the UK Mathematics Trust, aimed at students of age 16). Like the problems in the previous post, these problems do not require knowledge beyond that of a GCSE-level student, they are more a test of one’s creativity and insight than a test of one’s knowledge of the subject.

Problem 1

geometrymaclaurinp1

The two key pieces of information in this problem’s description are that all three shapes are regular, and that they have an edge in common. Another way of phrasing this is that every visible line in the question’s diagram has the same length. Additionally, since all three shapes are regular, they all have their own sets of equal internal angles. We can calculate the size of a single internal angle from all three shapes using the formula below (where n is the number of sides the polygon has):

Sum of the interior angles of a polygon (degrees) = (n-2) * 180

Single internal angle (degrees) = Sum of the interior angles of a polygon (degrees) / n

Using this procedure, we acquire the following sizes for a single internal angle of each polygon:

  • 15-gon: 156 degrees
  • Heptagon: 900/7 degrees
  • Decagon: 144 degrees

In order to find the size of angle XYZ, we need to take into account two ideas: one being that the sum of the angles around a single point is 360 degrees, and another being that the sum of the angles inside a triangle is 180 degrees. To progress further towards a solution, we can first focus on the lower point of the side the three polygons have in common (this point will be named P). We can find the size of the angle XPY by subtracting 900/7 degrees and 144 degrees from 360 – doing this gives the value 612/7. Additionally, we can also find the size of the angle ZPY by subtracting 900/7 degrees from 156 degrees – doing this gives the value 192/7. Given that the lengths of the lines PZ and PY are equal (since every visible line in the question’s diagram has the same length), we can state that the triangle ZPY is an isosceles triangle, and we can find the angle PYZ by subtracting  192/7 degrees from 180 degrees and dividing the result by 2 – this gives the value 534/7. To find the size of the angle XYZ, we can subtract the size of the angle XYP from the size of the angle PYZ. Getting the size of the angle XYP can be done by subtracting the size of the angle XPY from 180, and dividing the result by 2. To find the size of the angle XPY, we can subtract the values 144 degrees and 900/7 degrees from 360 degrees to obtain the value 612/7. Subtracting this value from 180 degrees and dividing the result by 2 gives the value 324/7 for the size of the angle XYP. We can now find the size of the angle XYZ by subtracting 324/7 from 534/7; doing this gives the value 210/7, which simplifies to 30 degrees.

geometrymaclaurinp1working1

Problem 2

geometrymaclaurinp2

In order to tackle this question, we must be aware of the circle theorem which states that a triangle drawn inside a semicircle with the longest side being said semicircle’s diameter will always be a right-angled triangle. Therefore, the triangle formed by the three points C, A and D is a right-angled triangle. Given that we know that the length of this right-angled triangle’s hypotenuse is 4, we can use the Pythagoras Theorem to find the length of CD if we know the distance between the two points A and C.

A kite can be drawn inside the circle if a radius is drawn to the point C. A key characteristic of this kite is that the length from its lowest point to its highest point is 2 (because this length is the radius of the circle).

geometrymaclaurinp2working2

This kite can then be split into four right-angled triangles, with the side lengths shown in the image below:

geometrymaclaurinp2working1

In the drawing above, we acknowledge that the distance from the lowest point of the kite to the highest point is 2, and we split this distance at the line AC to form two lines of length x and 2-x. Additionally, we know that the shape above is symmetrical, so the line from its lowest point to its highest point bisects the line AC into two smaller lines of length y. Focusing on one of the two sides of the kite, we can use the Pythagoras Theorem to form the following equations:

geometrymaclaurinp2working3

geometrymaclaurinp2working4geometrymaclaurinp2working5

First we observe that x^2 and y^2 sum to 1, and then we can subtract this expression from the sum of y^2 and (2-x)^2 to obtain a linear equation which we can then solve to find the value of x. We can then substitute this value of x into our first equation in order to acquire the positive value of y (obviously, a negative value of y does exist, but here we disregard it because we are dealing with length).

Now we can go back to our original image of the circle – given that the line AC has a length of 2y, we can apply the Pythagorean Theorem as follows to find the length of CD (bearing in mind that the circle theorem mentioned at the start of the explanation for this problem states that the triangle ACD is right-angled).

geometrymaclaurinp2working7

Problem 3

geometrymaclaurinp3

This problem initially appears quite complex – it requires a crucial insight in order for it to be solved, however, with this insight, the solution to the problem is arguably the most concise and elegant out of the three solutions on this post. The various regions in the diagram are created by the intersections of two triangles with equal area, shown below:

We can see that these two triangles have equal area by looking at the formula below:

Area of a triangle = (base * perpendicular height) / 2

Given that the length of the base of one of the triangles is the perpendicular height of the other triangle, and that the multiplication operation is commutative, this formula returns the same value for the area of both triangles (we do not need to know any specific values for either the base or the height in order to see that this is the case). Additionally, this value for the areas of the triangles is equal to half the area of the entire diagram, because the triangles share their dimensions with the rectangle, and therefore the white area on the right diagram is equal to the shaded area on the left diagram – if we label the regions on the diagram in the manner shown below, we can form and solve a new equation based on this idea.

geometrymaclaurinp3working3

Looking at the two previous diagrams, the shaded area of the one on the left contains the regions ab and c, while the white area of the one on the right contains the regions of a and c, along with three regions of sizes 1, 2 and 3. Given that both sections have equal area, we can form and solve the following equation to find the area of region b, which is the shaded area in the original question’s diagram.

geometrymaclaurinp3working4

Conclusion

As the Maclaurin Olympiad draws closer, I will continue to make more posts on the problems it has given in the past. Additionally, I will also begin writing about an interesting computing-related side project of mine in the coming weeks – more about this project will be revealed soon.