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