[Java] Maximise alternate picks on array - dynamic programming

Last time we saw how to find the maximum achievable value in a situation where two players alternate in picking items from an array boundaries. Solution works, but runs in O(2^N) which becomes quickly unacceptable.

If we introduce a bit more complexity, we can take that time and space down to O(N^2), which is still not awesome but definitely better than before. The key is to track calculations that have already been done to reuse those values later on; this translates in us keeping a matrix of size 2xN^2 where for each player we track the best pick at a specific point in time. When we get to evaluate that pick again, if the result is already cached, we can simply return it and avoid extra function calls.

This performance change can be easily tracked by keeping a global counter starting at 0 and increasing it by 1 at the beginning of the helper function. At the end of the algorithm we will see the total number of functions calls for both methods.

You can check my implementation of getMaxGoldFromPots on my Gist alongside some test cases in GoldPotsJTests.

Note: The test cases are exactly the same, therefore to try either approach simply rename the function calls in the JUnit tests.

[Java] Maximise alternate picks on array

Here's a simple game: gold pots with different amounts of coins are placed in a single line. Two players alternate in choosing one pot to pick from either side.
Find the maximum amount of gold a player can get.

And the solution is intuitive enough with only a big gotcha: while the game progresses, the same player does NOT always pick, therefore he will have turns where his total does NOT increase AND he is left with the WORST choice for the next turn.

This translates into a recursive algorithm where Math.max and Math.min are our friends. We must carefully track which player would get to pick during recursion and adapt the branching on PICK + MAX or only MIN depending on whose turn is it. The base case is when a single pot is left - and even here we must check for whose turn it is!

For complexity, since we are deciding between two options at each step, we get a scary O(2^N) time and space due to the stack recursion.

You can find my implementation of getMaxGoldFromPotsNoDP on my Gist alongside some test cases in GoldPotsJTests.

A slightly more complex solution that has overall better performance O(N^2) can be found in getMaxGoldFromPots instead.

[Java] Loop over digits in a number

Well of course we could just convert the number to String and take it up from there, but since we're real men who know about the modulo operator, we can instead do:

 while(number > 0) {  
  digit = number % 10;
  number /= 10; //discard the digit and advance to the next spot  
 }  

And would also be careful to declare number as a copy of our input number so as not to destroy it.

[Java] Count number of bits set to 1 in a byte type

Some more Java byte type related fun, how to count the number of bits set to 1 in a given byte.

 public int count(){  
  int tot = 0;  
   
  for(byte b = 0b00000001; b != 0b00000000; b = (byte)(b << 1)){  
   if((b & res) == b) tot++;  
  }  
   
  return tot;  
 }  

We can loop over it with some gotchas:

• properly initialize our loop variable as byte value: 0bVALUE and set the rightmost bit to 1, using the same length as our byte variable we want to test
• break the loop at 0b0, which is when we overflow with the shift
• convert back to byte with a cast the result of << operation
• check if the bit is set with a bitwise AND operation first

[Java] Set a specific bit in a byte type

First of all let's start by saying that quite counter intuitively, Boolean in Java is not a single bit but either a 32 or 64 bit entity while a boolean[] uses a byte for each element :)

Now that the shock is passed, let's see how to set a specific bit in a byte object:

 public void set(int bit){  
  byte b = (byte)(1 << (bit - 1));  
  res |= b;  
 }  

Assuming res is our byte variable. And yes, the cast is there since the shift operation << returns an int, therefore it must be cast back to byte type, otherwise the bitwise OR would later fail!

And the -1 is of course because we start with position 0 on the right. Note that using the bitwise OR will set the bit ONCE and never revert it back!

[Java] Regular expression matcher

Regular expressions are a pain, until they are not. Implementing a matcher is a double pain, and possibly the hardest exercise I've seen so far in terms of proper coding.

So many rules have to be carefully prioritised for it to succeed, even without fully supporting the common keywords. We have the following syntax:

• alphanumeric - matches exactly that character
• . - matches any character
• * - must follow . or an alphanumeric character, means we can match multiple instances of the preceding character
• ^ - must be the first character, means the matching has to begin from the start
• $ - must be the last character, means the matching has to occur at the end

In the absence of ^ and $, the match can occur anywhere in the string.

[Java] Fisher-Yates array shuffle

The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence. It can be coded to run in-place and in O(N) time where N is the input array size.

The idea is quite simple yet effective: while scanning the array from the end, select a random index with which to swap that element for among an always shrinking set of possibilities. Namely, use a getRandom function that accepts a floor and a ceiling as input and reduce the ceiling by 1 at each iteration, until the whole array has been processed.

You can check my implementation of FisherYatesShuffle on my Gist alongside some test cases in FisherYatesJTests.

Note: since we are supposed to generate truly random permutations of the input array, we have no simple way of checking for errors except to verify the output distribution itself to determine whether a bias exists or not. Therefore the current test could be extended to record for all the algorithm iterations the result of the shuffle and compare the results at the end among themselves.

[Java] Word squares tester

This exercise looked scarier than it is, although the real difficulty is not much on the algorithm itself but rather on the correct and clean implementation of it.

A “word square” is an ordered sequence of K different words of length K that, when written one word per line, reads the same horizontally and vertically. For example:

BALL
AREA
LEAD
LADY

Given an arbitrary list of words, return all the possible word squares it contains. Reordering is allowed.

For example, the input list:

[AREA, BALL, DEAR, LADY, LEAD, YARD]

should output:

[(BALL, AREA, LEAD, LADY), (LADY, AREA, DEAR, YARD)]

[Java] Calculate maximum capacity of 2D shaped object

This problem looked harder than it actually is:

Imagine an island that is in the shape of a bar graph. When it rains, certain areas of the island fill up with rainwater to form lakes. Any excess rainwater the island cannot hold in lakes will run off the island to the west or east and drain into the ocean.

Given an array of positive integers representing 2-D bar heights, design an algorithm (or write a function) that can compute the total volume (capacity) of water that could be held in all lakes on such an island given an array of the heights of the bars. Assume an elevation map where the width of each bar is 1.

Example: Given [1,3,2,4,1,3,1,4,5,2,2,1,4,2,2], return 15 (3 bodies of water with volumes of 1,7,7 yields total volume of 15)

[Java] Decompress k[value] format strings

Here is an interesting problem: decompress a compressed string.

Your input is a compressed string of the format number[string] and the decompressed output form should be the string written number times. For example:

3[abc]4[ab]c

Would be output as

abcabcabcababababc

Number can have more than one digit. For example, 10[a] is allowed, and just means aaaaaaaaaa

One repetition can occur inside another. For example, 2[3[a]b] decompresses into aaabaaab

Characters allowed as input include digits, small English letters and brackets [ ].

Digits are only to represent amount of repetitions.

Letters are just letters.

Brackets are only part of syntax of writing repeated substring.

Input is always valid, so no need to check its validity.

This can be done in one pass of the string by either applying recursion or explicitly using a stack for an additional O(N) space and overall O(N) time.

Gotchas are:

• treat 0 repetitions and missing k correctly
• remember that when concatenating data that comes from the stack we are actually prepending
• run a last round of popping after the string is fully parsed

You can check the implementation of decompress on my Gist alongside some test cases in DecompressJTests.

[Java] Neighbour evaluation concise logic

Here is a nice trick I was taught while doing some exercises. Consider the need to perform some loop over neighbouring places for example in an array or matrix or whatever, the basic idea would be to pick a starting point and queue up all valid points reachable from that which we did not visit yet. Assume a matrix M of size N:

A B C
D X F
G H I

And X is our starting point. We could do:

 if(i - 1 >= 0 && !visited.get(M[i - 1][j])) //do something  
 if(i - 1 >= 0 && j - 1 >= 0 && !visited.get(M[i - 1][j - 1])) //do something   
 if(i - 1 >= 0 && j + 1 < N && !visited.get(M[i - 1][j + 1])) //do something     
 if(j - 1 >= 0 && !visited.get(M[i][j - 1])) //do something  
 if(j + 1 < N && !visited.get(M[i][j + 1])) //do something  
 if(i + 1 < N && j - 1 >= 0 && !visited.get(M[i + 1][j - 1])) //do something  
 if(i + 1 < N && !visited.get(M[i + 1][j])) //do something  
 if(i + 1 < N && j + 1 < N && !visited.get(M[i + 1][j + 1])) //do something  

But here is an equivalent and more concise way of achieving the same. Consider the same matrix but focus on the changes on i and j you would do:

(-1,-1) (-1,0) (-1,+1)
(0,-1)     X   (0,+1)
(+1,-1) (+1,0) (+1,+1)

Then this can easily be converted into (and even adapted to more dimensions):

 int[] di = {-1, -1, -1, 0, 0, 1, 1, 1};  
 int[] dj = {0, -1, 1, -1, 1, -1, 0, 1};  
   
 for(int n = 0; n < di.length; n++){  
  int x = i + di[n], y = j + dj[n];  
  if(x >= 0 && x < N && y >= 0 && y < N && !visited.get(M[x][y])) //do something  
 }  

[Java] Find longest word that can be made as subsequence of given word

Here is another interesting problem: given a string and a list of strings, determine, if any, the longest string from the list that can be built as a subsequence of the given string, by only deleting characters in it. For example, given "asd" and {"a", "ccc", "sd", "sda"} return "sd".

The complex part when working with string is as usual the fact that we potentially need to scan the string many time over and over in order to reach our goal.

In this case, we could simply check for each given string in the list, if it can be built from the given input string by looping over that and match each character until we have our answer; this takes O(L) time where L is the length of the INPUT string for a SINGLE word. So overall we would need O(NxL) time where N is the number of strings in the list.

We know we can do some preprocessing to make our runtime better, at the expense of space of course. Since the input string can be very long and our result can start anywhere in there, we could do this in O(N+L) time by simultaneously process ALL words (N) for each character in the input string(L), using an additional O(N) space.

[Java] Minesweeper

Minesweeper. Do I need to say more?

The most interesting part is how to efficiently and randomly create the board.

There are many, many, many (and more) ways of doing so, I'll describe my idea here:

• the board size for an average game will not be so big that I can't afford to store an additional O(N^2) piece of information. This is the key point, without this assumption, the rest is not applicable!
• if I do store that piece of information, then I can acceptably randomize it in O(N)
• since the random distribution is from 1 to board_size (all the valid spots for a mine, N^2 spots) but the board is actually a matrix and therefore has 2 indices, I need a way to convert from the random spot to the matrix spot reliably
• if we have too many mines, it's best to randomly place empty spots instead
• after the initial placement, we need a pass on the matrix to fill the remaining spots with the correct count of the neighbouring mines

The randomization can be done with a call to Collections.shuffle, while the conversion from board spot to the matrix spot can be done easily after some considerations. Consider this sample matrix:

1 2 3
4 5 6
7 8 9

Given any of those numbers, can you determine the exact matrix location? Meaning can you return a i and j that indicate where that number would be placed in the matrix? For example 1 would be 0,0 and 8 would be 2,1.

Yes, but rows and columns have to be treated differently AND, since we do care about randomness but not precision, we can even avoid adjusting the result to reflect the exact position - we can't get the same position twice anyway.

For columns we can simply use the modulus operator, this way the last column is 0 and not 2, but since we are going for random spots we don't care to correct it. Basically we are flipping the matrix over on the Y axis :)

For rows instead, we can simply use division and then round the values UP to get something in range 1 .. board_length which we convert to 0-based.

The method looks like this (can be reduced to fewer lines, but debugging is easier this way!):

 private int decodeCoordinate(int value, boolean is_column){  
     //column we can find with modulus  
     //last column is 0 if we do this calculation, but we are going for random spots so we don't care to correct it  
     if(is_column) return value % fieldLength;  
   
     //rows we can find with a normal division and then picking the ceiling of it, converting to 0-based!  
     double a = (double) value, b = (double) fieldLength;  
     int c = (int) Math.ceil(a / b);  
     return c - 1;  
   }  

You can check the implementation on my Gist alongside some test cases in MinesweeperJTests. I plan to pick this up again to finish it, so some parts are extra and do not yet tie in to the final code :)

[Java] Make bricks and make chocolate problems

Among some exercises offered by Google, I found a couple interesting ones that are a bit harder to code cleanly than I would have thought: makeBricks and makeChocolate.

The basic idea is the same in both cases but the return value in one case is a simple yes/no while in the second case is a number:

We want to make a row of bricks that is goal meters long. We have a number of small bricks (1 meter each) and big bricks (5 meters each). Return true if it is possible to make the goal by choosing from the given bricks. - Yes they said inches but this is 2018 and we like our metric system :)

and

We want make a package of goal kilos of chocolate. We have small bars (1 kilo each) and big bars (5 kilos each). Return the number of small bars to use, assuming we always use big bars before small bars. Return -1 if it can't be done.