Project Euler Problem 8: Largest product in a series

Problem

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Solution

Two optimizations I made to make the program quicker are

• Keep the previous product value, when it is not 0, divide the previous product value by the number at index-1, and multiply the result by the number at index+12. 
• Check if the current sequence of numbers contains any 0s, if it does, move on to the next index. (I use bit operation to determine this. It's probably overkill, but I was so obsessed with the idea of 'going through the array only once') 

To explain the logic of determining whether a sequence of digits contains any 0s using bit operation, let's assume the length is sequence is 4, and here is a sample sequence 2708209487.

Firstly, we are checking 2708. Iterate from left to right, when we see a 0 we push a 1 to a queue, when we see a none 0, we push a 0 to the queue. The result is 0100 (decimal number 4).  The code to achieve this is

 if (numAt(i) == 0){   
   zeros |= 1 << j;    
 }   

When the result > 0, it means the sequence contains a 0.

The next sequence to check is 7082. We could repeat the previous step, but we don't have to. We can simply get rid of the right most digit of the previous result and left pad with new digit, in this case, 2.

Here is the relevant code.

 int result = previousZeros >> 1;   //Get rid of the right most digit
 if (numAt(index+NUMBER-1)==0){   
   result |= 1 << (NUMBER - 1);  //Left pad a 0 or 1 for the new digit 
 }  

Complete code

      private static final int NUMBER = 13;  
      private static final String STR =   
      "73167176531330624919225119674426574742355349194934"+  
      "96983520312774506326239578318016984801869478851843"+  
      "85861560789112949495459501737958331952853208805511"+  
      "12540698747158523863050715693290963295227443043557"+  
      "66896648950445244523161731856403098711121722383113"+  
      "62229893423380308135336276614282806444486645238749"+  
      "30358907296290491560440772390713810515859307960866"+  
      "70172427121883998797908792274921901699720888093776"+  
      "65727333001053367881220235421809751254540594752243"+  
      "52584907711670556013604839586446706324415722155397"+  
      "53697817977846174064955149290862569321978468622482"+  
      "83972241375657056057490261407972968652414535100474"+  
      "82166370484403199890008895243450658541227588666881"+  
      "16427171479924442928230863465674813919123162824586"+  
      "17866458359124566529476545682848912883142607690042"+  
      "24219022671055626321111109370544217506941658960408"+  
      "07198403850962455444362981230987879927244284909188"+  
      "84580156166097919133875499200524063689912560717606"+  
      "05886116467109405077541002256983155200055935729725"+  
      "71636269561882670428252483600823257530420752963450";  
      public static void main(String[] args) {  
           long previousProduct = calulateProduct(0, 0);  
           long greatestProduct = previousProduct;  
           int zeros = zeros(0);  
           for (int i=1; i<STR.length()-NUMBER; i++){  
                zeros = zeros(i, zeros);  
                if (zeros == 0){  
                     long product = calulateProduct(i, previousProduct);  
                     previousProduct = product;  
                     if (product > greatestProduct){  
                          greatestProduct = product;  
                     }       
                }else{  
                     previousProduct = 0;  
                }  
           }  
           System.out.println(greatestProduct);  
      }  
      private static long calulateProduct(int index, long previousProduct) {  
           if (previousProduct > 0){  
                return previousProduct / numAt(index-1) * numAt(index+NUMBER-1);   
           }  
           long product = 1;  
           for (int i=index; i<index+NUMBER; i++){  
                product *= (long)numAt(i);  
           }  
           return product;  
      }  
      private static int zeros(int index){  
           int zeros = 0;  
           for (int i=index, j=0; i<index+NUMBER; i++,j++){  
                if (numAt(i) == 0){  
                     zeros |= 1 << j;   
                }  
           }  
           return zeros;  
      }  
      private static int zeros(int index, int previousZeros){  
           if (previousZeros == -1){  
                return zeros(index);  
           }  
           int result = previousZeros >> 1;  
           if (numAt(index+NUMBER-1)==0){  
                result |= 1 << (NUMBER - 1);  
           }  
           return result;  
      }  
      private static long numAt(int index){  
           return Long.valueOf(STR.charAt(index)+"");  
      }  

Project Euler Problem 7: 10001st prime

Problem

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Solution

Some optimization includes

• Use an array to store found prime numbers to check future prime number candidate
• Only check numbers 6k+1 and 6k-1, because we know other number can either be divided by 2 or 3.

      private static final int NUMBER = 10001;  
      private static final long[] primeNumbers = new long[NUMBER-1];  
      public static void main(String[] args) {  
           primeNumbers[0]=3L;  
           int index = 1;  
           for (int i=6; index < NUMBER - 1; i+=6){ //Because we start at 3 instead of 2  
                for (int j=-1; j <= 1; j+=2){ //Only test 6K+1 and 6k-1  
                     if (isPrimeNumber(i+j, index)){  
                          primeNumbers[index]=i+j;  
                          index++;  
                     }  
                     if (index >= NUMBER - 1){  
                          break;  
                     }  
                }  
           }       
           System.out.println(primeNumbers[index-1]);  
      }  
      private static boolean isPrimeNumber(long number, int index){  
           double sqrt = Math.sqrt(number);  
           for (int i = 0; primeNumbers[i] <= sqrt; i++){  
                if (number % primeNumbers[i] == 0){  
                     return false;  
                }  
           }  
           return true;  
      }  

Project Euler Problem 5: Smallest multiple

Problem

 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

 What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

Attempt 1: Count the occurrences of the prime factor for each number, and multiply them all.

      private static Map<Integer, Integer> primeNumberOccurrence = new HashMap<>();  
      public static void main(String[] args) {  
           for (int i=2; i<=20; i++){  
                updatePrimeNumberOccurrence(i);  
           }  
           int total = 1;  
           for (int key : primeNumberOccurrence.keySet()){  
                int occurrence = primeNumberOccurrence.get(key);  
                total *= Math.pow(key, occurrence);  
           }  
           System.out.println(total);  
      }  
      private static void updatePrimeNumberOccurrence(int number){  
           int divisor = 2;  
           int divisorCount = 0;  
           while(number > 1){  
                if(number % divisor == 0){  
                     number = number / divisor;  
                     divisorCount++;  
                }else{  
                     update(divisor, divisorCount);  
                     divisor++;  
                     divisorCount = 0;  
                }  
           }  
           update(divisor, divisorCount);  
      }  
      private static void update(int divisor, int divisorCount){  
           if (divisorCount != 0){  
                int oldCount = primeNumberOccurrence.get(divisor) != null ? primeNumberOccurrence.get(divisor) : 0;  
                if (divisorCount > oldCount){  
                     primeNumberOccurrence.put(divisor, divisorCount);  
                }  
           }  
      }  

Attempt 2: Use greatest common factor

      private static final int NUMBER = 20;  
      public static void main(String[] args) {  
           int total = NUMBER;  
           for (int i = NUMBER-1; i >= 2; i--){  
                //greatest common factor  
                total *= i / BigInteger.valueOf(total).gcd(BigInteger.valueOf(i)).intValue();  
           }  
           System.out.println(total);  
      }  

Project Euler Problem 4: Largest palindrome product

Problem

A palindromic number reads the same both ways.

The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

Solution

The efficiency of checking if a number is palindrome can certainly be improved, but I am more focused on optimization on two for loops.

• Start from 999 backwards, and start j=i instead of 999
• Check product > current largest palindrome first instead of checking product is palindrome first
• break inner loop when we know the rest product cannot be larger than the current largest palindrome

      public static void main(String[] args) {  
           long largestPalindrome = 0;  
           for (int i = 999; i >= 100; i--){  
                for (int j = i; j >= 100; j--){  
                     long product = i * j;  
                     if (product > largestPalindrome){  
                          if (isPalindrome(product)){  
                               largestPalindrome = product;  
                               break;  
                          }  
                     }else{  
                          break;  
                     }  
                }  
           }  
           System.out.println(largestPalindrome);  
      }  
      private static boolean isPalindrome(long product) {  
           String s = String.valueOf(product);  
           return reverse(s).equals(s);  
      }  
      private static String reverse(String s) {  
           String r = "";  
           for (int i=s.length()-1; i>=0; i--){  
                r += s.charAt(i);  
           }  
           return r;  
      }  

Project Euler Problem 3: Largest prime factor

Problem

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Solution


If the while loop condition changes to divisor < number, it will be extremely slow for number like 600851475145

      public static void main(String[] args) {            
           long number = 600851475143L;  
           long divisor = 2;  
           while((divisor * divisor) <= number){  
                if(number%divisor==0){  
                     number = number/divisor ;  
                }  
                divisor++;  
           }  
           System.out.println(number);  
      }  

Blackjack house edge

Statistically speaking, Blackjack is probably the only casino game where you can win money in the long run.

Inspired by the movie <21>, I decided to write a Java program (https://github.com/sunmingtao/blackjack) to find out the house edge for the following two scenarios:

1. The player employs the basic strategy.
2. The player counts the card and bets only when the situation favours him.

What is basic strategy?

Basic strategy, simply put, is the strategy that enables you to lose the least money to the casino in the long run. Given a hand against a specific dealer’s face up card, the strategy chart will tell you which action to take. If you decide to disobey the strategy chart, it will cause you to lose more money.

Since  Blackjack’s rules vary from casino to casino, there is a basic strategy for each set of rules.

My program assumes the use of American rules (with hole card), as opposed to European/Australian rules (without hole card). Also assumed is the following variation of rules, which is quite common in America.

• Hole card games — dealer peeks for blackjack on 10s and Ace upcards.
• The dealer must stand on Soft-17.
• Blackjack payout is 3 to 2 odds.
• 21 on split Aces cannot count as a player blackjack.
• We can double down on any hand total.
• We can double down after splitting.
• We can split hands up to three times, making four total hands.
• We can split Aces only once, and only take one card to split Aces.
• Unlike 10-valued cards can be split; 10-card and Jack, etc.
• Late surrender is allowed.

Here is the basic strategy chart corresponding to the above rules.

S = Stand
H = Hit
Dh = Double (if not allowed, then hit)
Ds = Double (if not allowed, then stand)
SP = Split
SU = Surrender (if not allowed, then hit)

How do I work out the house edge?

First off, I don’t know how to calculate the precise odds mathematically. There are so many combinations that I think it’s only theoretically possible to do the precise calculation. But precision doesn’t really matter here. Knowing a range is more than sufficient to help us make a decision. If we know the house edge of Baccarat falls between 0.5% and 0.6% while Baccarat is 1%-1.2%, we want to stay a bit away from Baccarat table.

The approach I take is Monte Carlo method, which is to simulate the game played between player and dealer for a large number of times.

Number of hands simulated	House edge
89412575	0.36
89411293	0.38
89409262	0.35

We see a house edge between 0.35% and 0.38%. This means if we bet $100 every time, after 100 hands, we are expected to lose 35-38 dollars on average.

Now let’s see how card counting reverses the house edge.

How does card counting work?

The more big cards (10-A) remain in the deck, the more advantage shifts to the player’s side.  The rationale behind this system is that with more big cards remaining, the player is more likely to hit a natural blackjack, which pays 3 to 2. And the dealer is more likely to bust because he is obliged to hit on 4 or 5 while the player can choose to stand. 

To count card is simple, start the counter as 0, when you see 2-6, add 1 to the counter. When you see 10-A, subtract 1 from the counter. Do nothing when you see 7-9. 

We call the value of this counter as ‘running count’. The casino normally uses 6-8 decks of cards, so we need to translate our information into ‘true count’, which means the ‘running count’ per remaining deck. 

For example, the ‘running count’ is 5, and there are about 5 decks of cards remaining. The ‘true count’ would be 1. 

So when can you start betting? When ‘true count’ >= 1. At least it’s what the online article says. However, my program actually proves using ‘running count’ is almost as effective as ‘true count’.

Let's compare the result between true count and running count.

When true count > 1

Number of hands simulated	Number of hands bet	House edge per hand bet	House edge per hand dealt
89413874	28600935	-1.10	-0.35
89411394	28576145	-1.07	-0.34
89409522	28573179	-1.08	-0.35

When running count > 1

Number of hands simulated	Number of hands bet	House edge per hand bet	House edge per hand dealt
89409623	39847047	-0.73	-0.32
89412203	39847047	-0.77	-0.34
89412267	39816672	-0.79	-0.35

We see a player advantage in both cases. While it is undeniable that true count's edge is significantly higher than running count's in terms of 'per hand bet' (1.08 vs 0.77), it doesn't mean you can make significantly more money using true count. We must take the opportunity cost into consideration.

While using true count, there is only roughly 30% of the time when you can bet. The rest of time you have to sit out. It's highly unlikely you can tap into this idle period to make any money because you still need to be preoccupied with keeping track of the count. Consequently the real house edge that will reflect in your hourly earning rate is based on the total hands dealt, whether you play or not. And when we compare the house edge per hand dealt, the difference can hardly be said to have any statistical significance.

Finally let's do some rough estimate for a card counting pro's hourly rate. Suppose a dealer deals 100 hands an hour and the pro bets $100 every time, he's then earning $35 an hour on average. Double the stake, he will be earning $70 an hour. To stay under the radar, his stake probably can't go higher than that. Otherwise the casino will soon catch on and ban him. Upping the stake will also face the bankroll issue. We must bear in mind that the $35 or the $70 hourly rate doesn't mean you will be constantly earning this amount hour by hour like ordinary office workers do. You could win $500 this hour and lose $300 next hour. If you don't have a bankroll large enough, chances are you will go broke before you get a chance to win it back.

List all possible combinations

First attempt:

      public static <T> List<List<T>> allCombination(List<T> list, int n){  
           List<List<T>> result = new ArrayList<>();  
           if (n > 0){  
                for (int i=0; i<list.size(); i++){  
                     List<T> sublist = list.subList(i+1, list.size());  
                     if (sublist.size() >= n-1){  
                          List<List<T>> subAllCombination = allCombination(sublist, n-1);  
                          if (subAllCombination.size() > 0){  
                               for (List<T> strList : subAllCombination){  
                                    List<T> entry = new ArrayList<>();  
                                    entry.add(list.get(i));  
                                    entry.addAll(strList);  
                                    result.add(entry);  
                               }       
                          }else{  
                               List<T> entry = new ArrayList<>();  
                               entry.add(list.get(i));  
                               result.add(entry);  
                          }       
                     }  
                }  
           }  
           return result;  
      }  

Second attempt:

      public static <T> List<List<T>> allCombo(List<T> list, int n){  
           List<List<T>> result = new ArrayList<>();  
           push(list, n, new ArrayList<T>(), result);  
           return result;  
      }  
      private static <T> void push(List<T> list, int n, List<T> items, List<List<T>> result) {  
           if (n == 0){  
                result.add(new ArrayList<>(items));  
                return;  
           }  
           for (int i=0; i<list.size(); i++){  
                items.add(list.get(i));  
                push(list.subList(i+1, list.size()), n-1, items, result);       
                items.remove(items.size()-1);  
           }       
      }  

Testing code:

      public static void main(String[] args){  
           List<String> list = Arrays.asList("A","B","C","D","E");  
           for (List<String> str : allCombo(list, 3)){  
                System.out.println(str);  
           }  
      }  

Result:

[A, B, C]
[A, B, D]
[A, B, E]
[A, C, D]
[A, C, E]
[A, D, E]
[B, C, D]
[B, C, E]
[B, D, E]
[C, D, E]