Argon 2015 - TrekAndSwim

In this post I am going to discuss the solution for another great Codility problem.
Because of the copyrights I can't paste the problem description here so to view the problem click here.

As you may know most of the Codility problems are tricky and when Codility marks it as hard you should realize that you are going to squeeze your mind to get it resolved so I really envy those who could solve this issue from the first time in less than 30 mins. sometimes I really wish to contact any of them to see how brilliant they are, However lets start thinking in this problem and how to resolve it.

I am going briefly summarize how I think in this problem and how I resolved it.

first imagine you have this array

                                                             {1, 1, 0, 1, 0, 0, 1, 1, 0, 0}

So I am going to get the position of the first ZERO ( which meets the requirement of the tourist to enjoy swimming in the sea), also I am going to get the position of the last ONE.
                                                            {1, 1, 0, 1, 0, 0, 1, 1,0,0}
In our example the position of the first ZERO is 2  and the position of the last ONE is 7.

Now lets get the longest sea trip that starts from the first zero and ends with zero. ( it should end with Zero even if adding ones wont make it fail).
                                                           
                                                            {1, 1, 0, 1, 0, 0, 1, 1, 0, 0}

Now we realized that the tourist have chance to spend the vacation the way he wants ( first part on the sea and the second part hiking in the mountain)

                                                            {1, 1, 0, 1, 0, 0, 1, 1, 0, 0}

But our tourist here is pretty greedy he is looking for the longest vacation so we should try to expand the vacation as much as we can.

it can be done by iterating on the vacation from the last day to the start day and see if we can add hiking days to the second part without making the sea trip fails also we should add hiking days from the first part to the second part IF AND ONLY IF it will let the second part eligible to get more swim days from the rest of the reaming available days.

In our example we can't add more hiking days from the first part to the second part because it will lead that the second part of the vacation won't meet the criteria so the whole vacation will fail but the second part already eligible to add more days from the reaming days on its right.

so we can add one more day from its right

                                                            {1, 1, 0, 1, 0, 0, 1, 1, 0, 0}

lets get to the first part of the vacation. the question ?? is it eligible to add more days from its left ?  the answer simply yes so we should calculate how many days we should add from left ( expand the first part to left).

in our example we can add one more day from the left.

                                                            {1, 1, 0, 1, 0, 0, 1, 1, 0, 0}

Now we got the longest possible vacation.

lets move to translating the description above to a java code.

package trekandswim;

import java.util.Arrays;

/**
 *
 * @author ahmad
 */
public class TrekAndSwim {


    public static void main(String[] args) {
        // TODO code application logic here
        TrekAndSwim tr = new TrekAndSwim();
        int A[];
        int result = 0;
        
        
        
        
        //////////Test the the results 
        A = new int[]{1, 1, 0, 1, 0, 0, 1, 1, 0, 0};
        result = tr.solution(A);
        System.out.println("===========");
        System.out.println("The Result is    " + result);
        System.out.println("****************************************");

    }

    public int solution(int[] A) {
      

        int firstzero = -1;
        int lastone = -1;
        int seaDaysCount = 0;
        int seaEndIndex = 0;
        int seaArraySize = 0;

        int mountainStartIndex = 0;
        
        /////get the first zero and last one 
        for (int i = 0; i < A.length; i++) {
            if (firstzero == -1 && A[i] == 0) {
                firstzero = i;
            }
            if (A[i] == 1) {
                lastone = i;
            }
        }
        // return 0 if  no days for swim or no days for hike or no no hike day after a swim day
        if (firstzero == -1 || lastone == -1 || firstzero >= lastone) {
            return 0;
        }
        
        //get the longest sea trip that ends with ZERO
        int totalNumOfZeros = 0;
        for (int i = firstzero; i <= lastone; i++) {

            if (i == firstzero) {
                seaEndIndex = i;
            }
            if (A[i] == 0) {
                totalNumOfZeros++;
            }

            if (A[i] == 0&&seaTripNotFail(i - firstzero + 1, totalNumOfZeros)) {
                seaDaysCount = totalNumOfZeros;
                seaEndIndex = i;
            }

        }
        
        /// get the sea trip size
        seaArraySize = seaEndIndex - firstzero + 1;

        if (mountainStartIndex - seaEndIndex > 1) {
            return 0;
        }
        int startItrator = lastone;
        int tempones = 0;
        int tempZeros = 0;
        int tempEffectiveZeros = 0;
        int extraDays = 0;
        //check the possiblity of expanding the second part to the right by either adding more hike days from the first part or if the second part already adds elgiable to add more sea days from its right
        while (startItrator > firstzero) {
            if (extraDays + lastone >= A.length-1) {
                break;
            }
            if (startItrator > seaEndIndex) {
                if (A[startItrator] == 1) {
                    tempones++;
                    int newExtraDays = getExtraDays(tempones, tempZeros);
                    if (newExtraDays > extraDays) {
                        extraDays = newExtraDays;
                    }
                } else if (A[startItrator] == 0) {
                    tempZeros++;
                }
            } else {
                if (A[startItrator] == 1) {
                    tempones++;
                    int newExtraDays = getExtraDays(tempones, tempZeros);
                    if (newExtraDays > extraDays) {
                        int newArraySize = startItrator - firstzero + 1;
                        if (seaTripNotFail(newArraySize, seaDaysCount - tempEffectiveZeros)) {
                            extraDays = newExtraDays;
                            seaArraySize=newArraySize;
                            seaEndIndex=startItrator-1;
                            seaDaysCount=seaDaysCount - tempEffectiveZeros;
                            tempEffectiveZeros=0;
                        }
                    }
                } else if (A[startItrator] == 0) {
                    tempZeros++;
                    tempEffectiveZeros++;
                }
            }
             startItrator--;

        }
//      check if the first part elgiable to expand left or no 
        int expantionValue = arrayExpandLeft(firstzero, seaDaysCount, seaArraySize, A);
        firstzero -= expantionValue;
        seaArraySize += expantionValue;
        
        int mountainTripDuration=lastone-seaEndIndex+extraDays;
        return seaArraySize+mountainTripDuration;

    }
 /// methods to get number of zeros that we can add to the seond part withought making it fail ( the number of ones should be greater than the number of zeros)
    int getExtraDays(int numOfOnes, int numOfZeros) {

        return numOfOnes - numOfZeros - 1;
    }

   
  // method to expand the first part of the trip  to the left side 
    int arrayExpandLeft(int firstzero, int seaDaysCount, int seaArraySize, int[] A) {
        int expantionValue = 0;
        while (seaTripHasExtraSwimDays(seaArraySize, seaDaysCount) && firstzero > 0) {
            if (firstzero == 0) {
                break;
            }

            firstzero--;
            seaArraySize++;
            expantionValue++;

        }
        return expantionValue;
    }
     // cheack if the seatrip is ok with this size and this number of zeros  
    boolean seaTripNotFail(int seaArraySize, int numOfZeros) {

        return numOfZeros - (seaArraySize - numOfZeros) >= 1;
    }
  // cheack if the seatrip is elgiable to add more ones 
    boolean seaTripHasExtraSwimDays(int seaArraySize, int numOfZeros) {

        return numOfZeros - (seaArraySize - numOfZeros) > 1;
    }

}

Future training - BinaryGap

Here is another codility problem solution from the codility lessons (BinaryGap- Find longest sequence of zeros in binary representation of an integer.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
 public int solution(int N) {
  // write your code in Java SE 8
  int numberOfGapes = 0;
  int maxGapLength = 0;
  boolean isStartWithOne = false;
  boolean isEndWithOne = false;
  while (N > 0) {
   if (N % 2 == 0) {
    if (isStartWithOne) {
     numberOfGapes++;
    }
   } else {
    if (!isStartWithOne) {
     isStartWithOne = true;
    } else {
     maxGapLength = Math.max(maxGapLength, numberOfGapes);
     numberOfGapes = 0;
    }
   }
   N = N / 2;
  }
  return maxGapLength;
 }
}

Future training - StrSymmetryPoint

Here is another codility problem solution from the codility lessons (StrSymmetryPoint - Find a symmetry point of a string, if any.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
 public int solution(String S) {

  // write your code in Java SE 8
  if (S.length() == 1) return 0;
  else if (S.length() == 0 || S.length() % 2 == 0) return -1;
  else {
   int len = S.length();
   int half = (len / 2);
   for (int i = 0; i < half; i++) {
    if (S.charAt(i) != S.charAt((len - 1) - i)) return -1;
   }
   return (len / 2);
  }
 }
}

Future training-OddOccurrencesInArray

Here is another codility problem solution from the codility lessons (OddOccurrencesInArray - Find value that occurs in odd number of elements.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
// XORing any 2 similar number will give us zero 
//Zoring Zero with any number will give us the number
class Solution {
 public int solution(int[] A) {
  // write your code in Java SE 8
  int unPairedNum = A[0];
  for (int i = 1; i < A.length; i++) {
   unPairedNum = unPairedNum ^ A[i];
  }
  return unPairedNum;
 }
}

Future training - TreeHeight

Here is another codility problem solution from the codility lessons (TreeHeight -Compute the height of a binary tree.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
 public int solution(Tree T) {
                // to remove the first node from the calculation
  return computeTreeHeight(T) - 1;
 }

 private int computeTreeHeight(Tree T) {
  if (T == null) return 0;
  int leftT = 1 + computeTreeHeight(T.l);
  int rightT = 1 + computeTreeHeight(T.r);

  return Math.max(rightT, leftT);
 }
}

Prefix Sums - GenomicRangeQuery

Here is another codility problem solution from the codility lessons (GenomicRangeQuery-Find the minimal nucleotide from a range of sequence DNA..) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
	HashMap < Integer, Integer > ListOfA = new HashMap < Integer, Integer > ();
	HashMap < Integer, Integer > ListOfC = new HashMap < Integer, Integer > ();
	HashMap < Integer, Integer > ListOfG = new HashMap < Integer, Integer > ();
	HashMap < Integer, Integer > ListOfT = new HashMap < Integer, Integer > ();
	public int[] solution(String S, int[] P, int[] Q) {
		// write your code in Java SE 8
		int sum = getSum(S);
		fillMap(S);
		int[] queries = new int[P.length];
		for (int i = 0; i < P.length; i++) {
			int startIndex = P[i];
			int endIndex = Q[i];
			int sumA = ListOfA.get(endIndex) - ListOfA.get(startIndex);

			if (S.charAt(startIndex) == 'A') sumA++;

			if (sumA > 0) {
				queries[i] = 1;
			} else {
				int sumC = ListOfC.get(endIndex) - ListOfC.get(startIndex);
				if (S.charAt(startIndex) == 'C') sumC++;

				if (sumC > 0) {
					queries[i] = 2;
				} else {
					int sumG = ListOfG.get(endIndex) - ListOfG.get(startIndex);
					if (S.charAt(startIndex) == 'G') sumG++;

					if (sumG > 0) {
						queries[i] = 3;
					} else {
						int sumT = ListOfT.get(endIndex) - ListOfT.get(startIndex);
						if (S.charAt(startIndex) == 'T') sumT++;

						if (sumT > 0) {
							queries[i] = 4;
						}
					}
				}
			}

			// System.out.println(queries[i]+"========"+P[i]+"========"+Q[i]);
		}

		// System.out.println(S);

		return queries;
	}

	private void fillMap(String S) {
		int sumA = 0;
		int sumC = 0;
		int sumG = 0;
		int sumT = 0;
		int len = S.length();
		for (int i = 0; i < len; i++) {
			char c = S.charAt(i);
			switch (c) {
				case 'A':
					sumA++;
					break;
				case 'C':
					sumC++;
					break;
				case 'G':
					sumG++;
					break;
				case 'T':
					sumT++;
					break;

			}
			ListOfA.put(i, sumA);
			ListOfC.put(i, sumC);
			ListOfG.put(i, sumG);
			ListOfT.put(i, sumT);


		}

	}
	private int getSum(String S) {
		int sum = 0;
		int len = S.length();
		for (int i = 0; i < len; i++) {
			sum += mapChartoInt(S.charAt(i));
		}
		return sum;

	}
	private int mapChartoInt(char c) {
		int mappedVal = -1;
		switch (c) {
			case 'A':
				mappedVal = 1;
				break;
			case 'C':
				mappedVal = 2;
				break;
			case 'G':
				mappedVal = 3;
				break;
			case 'T':
				mappedVal = 4;
				break;

		}
		return mappedVal;
	}
}

Prefix Sums - PassingCars

Here is another codility problem solution from the codility lessons (PassingCars-Count the number of passing cars on the road.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

class Solution {
	public int solution(int[] A) {
		// write your code in Java SE 8
		boolean isZero = false;
		int zeroCount = 0;
		int pairCount = 0;

		for (int i = 0; i < A.length; i++) {
			if (A[i] == 0) {
				isZero = true;
				zeroCount++;
			} else if (A[i] == 1) {
				if (isZero) {
					pairCount = pairCount + zeroCount;
					if (pairCount > 1000000000) return -1;
				} else {
					continue;
				}
			}

		}


		return pairCount;
	}
}