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).


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.


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.


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:


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.


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.

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:


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’:


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


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.



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



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.


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





Tetris for Android in the Unity Engine – Part 2 (Player Input)

Hello all – this is the second part of the series of posts in which I have been developing the video game ‘Tetris’ for the Android platform using the ‘Unity’ engine. In this post, we will enable the player to move the falling blocks from left to right using buttons on the HUD (head-up display). Additionally, we will also implement a feature which enables the player to increase the rate of time and cause the falling blocks to fall faster – this feature is present in many other versions of the game.

The final product of this post of this post can be downloaded here.

In order to allow the player to give input, we need to add three buttons to the user interface – Unity has a UI development toolkit which allows us to do this relatively easily. In Unity, UI objects can be treated as actual GameObjects which are children of a ‘Canvas’ object – these UI objects contain certain components which allow them to function as various different interface elements (such as buttons, sliders and toggles). We need to add a ‘move block left’ button, a ‘move block right’ button and a ‘speed up time’ button – this can be done within the editor. Since the buttons are treated as GameObjects, they can be moved and shaped using the engine’s level editing tools.



Now, we can write the functions which will be called by the engine when the user presses the buttons. The ‘move left’ and ‘move right’ buttons only need to provide a response to tap actions – on the other hand, the ‘speed up time’ button must react to both being pressed and being released. First, we will write the functions called when the left/right movement buttons are pressed. The code which moves the tetrominoes downwards can be copied and edited slightly in order to provide functionality for moving them sideways – instead of looping through each block in the current tetromino and moving it down one row, we can loop through each block and move it either one column to the left or one column to the right. However, before moving any blocks, we need to loop through the entire tetromino and ensure that it is not already positioned on the very edge of the screen (we can do this by checking if any of its blocks are on the very left column or the very right column). If this check is passed, each block in the current tetromino can then be translated by one unit – the grid array which we created in the previous post must be updated in order to reflect this chance. The functions are have been made public in order for them to be called through UI input events.


In order to hook these public functions to their buttons, we set the ‘On Click ()’ option on the ‘Button’ components of the UI button objects which we added to the scene earlier.


Now, if the user presses the ‘move left’ button, the tetromino which is currently falling gets translated one column to the left, and if the user presses the ‘move right’ button, the tetromino which is currently falling gets translated one column to the right.

To speed up the falling block, the player must hold down the ‘speed up time’ button. Therefore, we need to implement two separate functions – one which reacts to the button being initially pressed down (this is where the button starts getting held down) and another which reacts to the button being released (where the button is no longer being held down). By default, the ‘Tick ()’ function which controls the falling tetrominoes is called once per second – in order to speed up the falling blocks, we cancel this pattern using the function ‘CancelInvoke ()’ and then use ‘InvokeRepeating ()’ in order to create a new calling pattern for the ‘Tick ()’ function with less time in between each call. The second argument to the new ‘InvokeRepeating ()’ call is set to 0.0f – this ensures that the ‘Tick ()’ function is instantly called when the ‘speed up time’ button is pressed (if this argument was not 0.0f, it would theoretically be possible for the player to completely freeze the block in mid-air by repeatedly pressing and releasing the ‘speed up time’ button). The same technique for speeding up the falling blocks is used to slow them down when the button is released – in the second function, we use ‘CancelInvoke ()’ to cancel the faster calling pattern before using ‘InvokeRepeating ()’ to replaced the cancelled pattern with the default calling pattern (which has 1-second intervals in between each tick).


We can then add ‘Event Trigger’ components to the ‘speed up time’ button, in order to hook these two public functions to their corresponding button events.


Now, the player has significantly control over the falling blocks in our version of Tetris – the blocks can be moved to the left, moved to the right, or pushed downwards at a higher speed. In the next post, we will start using the Unity editor to construct actual Tetrominoes (coloured groups of blocks) similar to those found in the original game.

The Coin Change Problem Solved with Dynamic Programming

The ‘Coin Change Problem’ is a well-known exercise in computer science. The idea is simple – given a certain number amount of money in cents (we will call this amount n), and infinite numbers of defined coin denominations, we want to calculate the number of ways we can make n by combining the coins we have been given.

For example, if we want to make 4 cents (n = 4), and the denominations available to us are 1, 2 and 3, we could make 4 cents in the following four ways:

{2,2}, {1,1,1,1}, {1,3}, {1,1,2}

Another example – if we want to make 10 cents (n = 10), and the denominations available to us are 2, 3, 5 and 6, we could make 10 cents in the following five ways:

{2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5}, {5,5}

The code I have written which solves the Coin Change Problem can be found here.

The most effective solution design for this problem uses a technique known as dynamic programming (we can also develop a program that finds solutions by brute force, but this is incredibly slow). The key idea to this technique is that certain large problems (say, finding the number of ways to make a large number of cents from a wide variety of different coin denominations) can be broken down into smaller sub-problems. These sub-problems can then be broken down further, until very small, easily-solvable problems with optimal solutions are obtained. From this logic, problems of this nature can be tackled by finding and solving the most trivial sub-problems, and extending the solutions to these sub-problems to more complex sub-problems until the final solution is obtained.

To apply dynamic programming to the Coin Change Problem, we first need to observe that there is only 1 way of making a sum of 0 (no matter what denominations we have available to us). Moreover, if we only have access to 1 coin denomination, then it is clear that there can be no more than 1 possible way to make every single sum (if a given number is divisible by the denomination, then there is 1 way to make that number, and if the number is not divisible by the denomination, then there is no possible way to make that number).

The next observation we can make is that we can represent the problem as a table – with a row for each coin denomination and (n+1) columns. The numbers in a given column represent the number of ways the index value of the column can be made using the coin denominations from each number’s row and the rows above. To solve the problem, we need to find the value at the bottom right of this table. We already know that there is only 1 way of making a sum of 0, so the first column can be filled with ones. Additionally, we have also already proven that there can be a maximum of 1 way of making every possible sum using only one coin denomination – therefore, the first row can be filled with either ones (for the columns with indices which are divisible by the first coin denomination) or zeroes (for the columns with indices which are not divisible by the first coin denomination).

After filling in the first column and the first row, we can progress onto filling the rest of the table, row-by-row. When we fill the second row of the table, we find the number of ways to make each column index using the first two coin denominations available to us. If the second coin denomination is greater than a given column index, we can set the value of the cell to the corresponding cell value in the row above (because the second coin denomination has no effect on the number of ways we can make the sum, since it has a greater value). However, if the second coin denomination is equal to or less than a given column index, we need to look at the number of ways we can include the second coin denomination in the sum. If the second coin denomination is equal to the sum, then we can set the value of the cell to the value of the corresponding value in the cell above incremented by 1 (since one new possible way of making the sum has been found – a single coin of the denomination equal to the target). Furthermore, if the second coin denomination is of a smaller value than the sum, we need to find the number of ways we can group the coins of the first two denominations together such that they sum to the difference between the sum and the second coin denomination. The key insight here is that we have already calculated this value previously (since we are iterating through the columns from left-to-right, with smaller sums being positioned towards the left). Therefore, we can set the value of our current cell to the sum of the value of the corresponding cell in the row above added to the value of the cell in the current row in the column indexed by the difference between the value of the current column and the value of the second coin denomination. This set of operations can be repeated for every single row in order to generate a full table. We can express this algorithm in a more concise form below (note that since every value in the first column is 1, we do not need to program any additional functionality for when the values of a given combination and the desired sum are equal):

  • For every row r:
    • Save the value of the coin denomination represented by the current row as v.
    • If r is the first row in the table:
      • For every column c:
        • If the index of c is evenly divisible by v:
          • Set table[r][c] to 1.
        • Else:
          • Set table[r][c] to 0.
    • Else
      • For every column c:
        • If v > column index:
          • Set table[r][c] to table[r-1][c].
        • Else if <= column index:
          • Set table[r][c] to (table[r-1][c] + table[r][cv]


When this algorithm is used to solve our first example (where we attempt to make 4 cents using coins with the denominations for 1, 2 and 3), the following table is generated:


We can see that the value of table[2][2] is set to (table [1][2] + table[2][0]). This shows that it is possible to make a sum of 2 cents using two 1-cent coins, or one 2-cent coin. This algorithm is repeated to construct the whole table, resulting in the value of table[3][4] being set to (table[2][4] + table[3][1]). The final value for table[3][4] shows that there are 3 possible ways to use only 1-cent coins and 2-cent coins to create a sum of 4, along with another single possible way which includes a 3-cent coin (resulting in the coin set {3,1}).


Developing Tetris for Android in the Unity Game Engine – Part 1 (Falling Blocks)

Hello all – due to having a fairly busy schedule as of late (owing to the run-up to my exams in May and June), I have been unable to make regular blog posts recently. However, enough progress has been made on my previously-mentioned computing-related side project for me to decide that it should not be kept under wraps for any longer. As the title suggests, the following series of posts will be about developing the video game ‘Tetris’ for the Android platform using the Unity game engine (an explanation of the game’s rules can be found here). This first post will be about developing the ‘backbone’ of the game (that is, the system which enables blocks to be generated at the top of the screen and fall).

This series of posts will assume a rudimentary knowledge of the Unity game engine (very basic ideas such as ‘GameObjects’ and ‘Components’ will not be explained in great detail).

The final product of this post can be downloaded here.

Our first task is to create a new Unity project directory – we do not need to import any of the pre-made asset packages (as none of them are necessary for our project). Normally, Tetris has 2D graphics, so we can opt to create a 2D project as opposed to a 3D one.

Screen Shot 2017-03-13 at 8.08.21 AM

After this is done, the main scene can be built (this should be done after setting the aspect ratio of the ‘game’ window to a ratio appropriate for the Android platform, such as 9:16). On my project, I positioned the main camera at (6,6,-10) and set its orthographic size to 11.6 – these settings allow for a grid with 18 rows, each 13 blocks wide.

Screen Shot 2017-03-13 at 8.09.18 AM

Next, we create a ‘prefab’ of an individual block. This can be done by dragging an object from the ‘hierarchy’ interface into the ‘assets’ interface. In the Unity game engine, prefabs are game objects saved as files within the game directory – these files can then be referenced in scripts, and copies of them can be created in the game world from these references. All of the scaling work has been done in the camera settings earlier, so the block prefab can just be a single cube with the dimensions (1,1,1). Later on, we will be able to design ‘tetrominoes’ (the slightly more complex shapes seen in the original game) using these block prefabs – for now, we will just use single blocks.

Screen Shot 2017-03-13 at 8.10.55 AMScreen Shot 2017-03-13 at 8.11.22 AM

Now, we can design the main script which handles the falling block system (I named it ‘MainControl.cs’). This script must be able to both keep track of all of the blocks in the grid and directly reference the blocks which are currently falling. We can achieve this by using a multidimensional array of ‘GameObject’ variables – the camera settings created earlier allow for us to use the x position of a block  as its column in the grid, and the y position of any block as its row in the grid (since the blocks are positioned at integer points along both axes). The script must also have a reference to the block prefab created earlier (so that new blocks can be generated). Furthermore, the script should also contain a variable holding the player’s score.

Screen Shot 2017-03-13 at 8.12.12 AM

In the original game, the blocks fall at a constant rate (unless they are sped up by the player – we will implement this feature in a later post). Moreover, they are translated directly from row to row, as opposed to being moved downwards in a continuous, smooth motion. Therefore, in order to process falling blocks, a function which is repeatedly called once every second can be used. In my code, I named this function ‘Tick’ – first, it checks if there are any blocks at all falling. If there are no blocks falling, it creates a new block using the ‘Instantiate’ function and adds it to the list of falling blocks. The ‘Instantiate’ function takes the block prefab as its first argument, and then the intended position and the rotation of the newly created block as its second and third arguments, respectively. Using the function ‘Random.Range’ while setting the value of the second argument of the ‘Instantiate’ functions enables blocks to be generated anywhere along the top row.

Screen Shot 2017-03-13 at 8.14.42 AM

If there are blocks falling, each of these blocks are processed in a loop. The loop initially iterates through each block and checks if the block has fallen onto a surface – this surface could either be the bottom of the grid, or the top of another block. Therefore, this check can be performed by first checking that the row (that is, the y position) of the block is not 0, and then checking that the value of the grid element exactly one row below the grid element of the current block is null (that is, no game objects are in that position in the grid). If this check returns true for any block in the list, then the list is cleared and all of the blocks in the list are frozen into their positions – since one of the blocks in the current ‘tetromino’ has fallen onto something. However, if this check never returns true, the ‘Translate’ function is used to move all of the blocks downwards by one row each (and the appropriate values in the grid array are updated).

Screen Shot 2017-03-13 at 8.17.42 AM.PNG

In order to ensure that the ‘Tick’ function is called once every second, the ‘InvokeRepeating’ function is used in ‘Start’ (which is called immediately after gameplay begins). Additionally, the grid is also initialised here.

Screen Shot 2017-03-13 at 8.32.21 AM.PNG

Now, we can drag this script onto any object in the scene – in my project, I attached it to the main camera. Our final result is a system which generates single blocks at the top of the grid in random positions along the x axis – these blocks then fall downwards until they either fall on top of other blocks or reach the bottom of the grid. When this happens, new blocks are created. In the next post, we will give the user the ability to control the movement of the blocks through input.