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:

CoinChangeTable.png

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.