diff --git a/journal.txt b/journal.txt new file mode 100644 index 0000000..86a7be6 --- /dev/null +++ b/journal.txt @@ -0,0 +1,19 @@ +Success! You've managed to infiltrate Commander Lambda's evil organization, and finally earned yourself an entry-level position as a Minion on their space station. From here, you just might be able to subvert Commander Lambda's plans to use the LAMBCHOP doomsday device to destroy Bunny Planet. Problem is, Minions are the lowest of the low in the Lambda hierarchy. Better buck up and get working, or you'll never make it to the top... + +Next time Bunny HQ needs someone to infiltrate a space station to rescue bunny workers, you're going to tell them to make sure 'stay up for 48 hours straight scrubbing toilets' is part of the job description. It's only fair to warn people, after all. + +You survived a week in Commander Lambda's organization, and you even managed to get yourself promoted. Hooray! Henchmen still don't have the kind of security access you'll need to take down Commander Lambda, though, so you'd better keep working. Chop chop! + +Rumor has it the bunny trainers are inexplicably fond of bananas. You're an apple person yourself, but you file the information away for future reference. You never know when you might need to bribe a trainer (or three)... + +The perks are definitely better as a Henchman than as a Minion. You're even allowed to sleep lying down! + +Awesome! Commander Lambda was so impressed by your efforts that you've been promoted to personal assistant. You'll be helping the Commander directly, which means you'll have access to all of Lambda's files -- including the ones on the LAMBCHOP doomsday device. This is the chance you've been waiting for. Can you use your new access to finally topple Commander Lambda's evil empire? + +Commander Lambda has six suits, three dress uniforms, four casual outfits, and one Dress-Uniform-For-Important-Speeches-Only. You know this because you've already had to take all of them to the dry cleaner's. Twice! + +Who the heck puts clover and coffee creamer in their tea? Commander Lambda, apparently. When you signed up to infiltrate the organization you didn't think you'd get such an up-close and personal look at these more... unusual tastes. + +One of these days you're going to manage to glimpse Commander Lambda's password over their shoulder. But the Commander is very careful about security and you haven't managed it yet... + +Excellent! You've destroyed Commander Lambda's doomsday device and saved Bunny Planet! But there's one small problem: the LAMBCHOP was a wool-y important part of the space station, and when you blew it up, you triggered a chain reaction that's tearing the station apart. Can you rescue the bunny workers and escape before the entire thing explodes? \ No newline at end of file diff --git a/level-1/the-cake-is-not-a-lie/Problem.png b/level-1/the-cake-is-not-a-lie/Problem.png new file mode 100644 index 0000000..d189561 Binary files /dev/null and b/level-1/the-cake-is-not-a-lie/Problem.png differ diff --git a/level-1/the-cake-is-not-a-lie/Solution.java b/level-1/the-cake-is-not-a-lie/Solution.java new file mode 100644 index 0000000..22d60c8 --- /dev/null +++ b/level-1/the-cake-is-not-a-lie/Solution.java @@ -0,0 +1,21 @@ +public class Solution { + public static int solution(String x) { + //assume entire cake can be fully split + + for(int i = x.length() - 1; i > 0; i--) { //max amount of slices will be the same even if we rotate the cake + int t = countSlice(x.split(x.substring(i), -1)); //slice the cake and count the slices + + if(t != -1) return t; //smallest slice is always the most possible slice; return on first valid slice and stop + } + + return 1; //if no slices are valid returns the lowest possible slice, aka the entire cake + } + + public static int countSlice(String[] split) { + for(String s : split) { //if not empty it means there are leftovers; Lambda would be enraged + if(!s.isEmpty()) return -1; //stop and return invalid count + } + + return split.length - 1; //valid slices; check count from split tokens + } +} \ No newline at end of file diff --git a/level-2/p1-power-hungry/Problem.png b/level-2/p1-power-hungry/Problem.png new file mode 100644 index 0000000..7a7da2b Binary files /dev/null and b/level-2/p1-power-hungry/Problem.png differ diff --git a/level-2/p1-power-hungry/Solution.java b/level-2/p1-power-hungry/Solution.java new file mode 100644 index 0000000..b8376d2 --- /dev/null +++ b/level-2/p1-power-hungry/Solution.java @@ -0,0 +1,32 @@ +import java.util.Arrays; +import java.math.BigInteger; + +public class Solution { + public static String solution(int[] xs) { + //assume xs never drops below 1 element as stated in the constraint + + int negCount = 0, remove = -1; + + Arrays.sort(xs); + + for(int i = 0; i < xs.length; i++) { + int x = xs[i]; + + if(x < 0) { + negCount++; + remove = i; //get last negative value's index to be removed + } + } + + if(xs.length > 1 && remove != -1 && negCount % 2 != 0) xs[remove] = 0; //if a remove value is found and it's not the only value, and negative count is not even (multiplying will return negative) + + BigInteger result = BigInteger.ZERO; //initialize big integer since it can get pretty big according to the readme + + for(int x : xs) { + if(x != 0) + result = result == BigInteger.ZERO ? BigInteger.valueOf(x) : result.multiply(BigInteger.valueOf(x)); //only multiply non zero values; zero values are almost always discardable + } + + return result.max(BigInteger.valueOf(xs[xs.length - 1])).toString(); //check if result is smaller than largest value in array (usually for catching 0s that we discarded) + } +} \ No newline at end of file diff --git a/level-2/p2-hey-i-already-did-that/Problem.png b/level-2/p2-hey-i-already-did-that/Problem.png new file mode 100644 index 0000000..b4777d8 Binary files /dev/null and b/level-2/p2-hey-i-already-did-that/Problem.png differ diff --git a/level-2/p2-hey-i-already-did-that/Solution.java b/level-2/p2-hey-i-already-did-that/Solution.java new file mode 100644 index 0000000..0542aee --- /dev/null +++ b/level-2/p2-hey-i-already-did-that/Solution.java @@ -0,0 +1,53 @@ +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; + +public class Solution { + public static int solution(String n, int b) { + List cycle = new ArrayList<>(); + List prevCycle = null; + + int k = n.length(); + + boolean repeat = false; + while (!repeat) { + //obtain sorted x and y + char[] chars = n.toCharArray(); + Arrays.sort(chars); + String y = new String(chars); //y is ascending, not x + + StringBuilder sb = new StringBuilder(y); + String x = sb.reverse().toString(); + + //calculate z with base + int z = Integer.parseInt(x, b) - Integer.parseInt(y, b); + //obtain n with base + n = Integer.toString(z, b); + + //prepend zeroes + int prependCount = k - n.length(); + if (prependCount > 0) { + char[] prepend = new char[prependCount]; + Arrays.fill(prepend, '0'); + n = new String(prepend) + n; + } + + //check if we are in a cycle + int search = cycle.indexOf(n); + if (search != -1 && search != cycle.lastIndexOf(n)) //if the value is found more than once in the list + cycle = cycle.subList(search + 1, cycle.size()); //remove irrelevant values before it since we are only interested in the cycle + + cycle.add(n); + + if (prevCycle != null) //if it aint null it would always have a value + prevCycle.add(prevCycle.remove(0)); //rotate cycle for checking + + if (cycle.equals(prevCycle)) //if what we did is equivalent to rotating the list, we found it + repeat = true; + + prevCycle = new ArrayList<>(cycle); //reset prevCycle + } + + return cycle.size() / 2; + } +} \ No newline at end of file diff --git a/level-3/p1-bomb-baby/Problem.png b/level-3/p1-bomb-baby/Problem.png new file mode 100644 index 0000000..f8f6c0b Binary files /dev/null and b/level-3/p1-bomb-baby/Problem.png differ diff --git a/level-3/p1-bomb-baby/Solution.java b/level-3/p1-bomb-baby/Solution.java new file mode 100644 index 0000000..8e400f1 --- /dev/null +++ b/level-3/p1-bomb-baby/Solution.java @@ -0,0 +1,33 @@ +import java.math.BigInteger; + +public class Solution { + public static String solution(String x, String y) { + BigInteger m = new BigInteger(x), f = new BigInteger(y); + + boolean found = false; + BigInteger count = BigInteger.ZERO; + while (!found && (m.signum() == 1 && f.signum() == 1)) { //loop when not found and values are not negative + int comp = m.compareTo(f); + if (comp > 0) { + BigInteger[] vals = f.equals(BigInteger.ONE) ? //dividing one is the only case where it will not be equivalent to multiple subtraction, thus we must make an exception + new BigInteger[] { BigInteger.ONE, m.subtract(f) } : m.divideAndRemainder(f); + count = count.add(vals[0]); + m = vals[1]; + } else if (comp < 0) { + BigInteger[] vals = m.equals(BigInteger.ONE) ? //as above + new BigInteger[] { BigInteger.ONE, f.subtract(m) } : f.divideAndRemainder(m); + count = count.add(vals[0]); + f = vals[1]; + } else { + if (m.equals(BigInteger.ONE)) { //no need to check f since they are equal + found = true; + } else { + throw new IllegalStateException(); //it should never be possible for two non-1 values to be equal under the bomb replication constraints + } + } + } + + return found ? count.toString() : "impossible"; + + } +} \ No newline at end of file diff --git a/level-3/p2-find-the-access-codes/Problem.png b/level-3/p2-find-the-access-codes/Problem.png new file mode 100644 index 0000000..dd057bf Binary files /dev/null and b/level-3/p2-find-the-access-codes/Problem.png differ diff --git a/level-3/p2-find-the-access-codes/Solution.java b/level-3/p2-find-the-access-codes/Solution.java new file mode 100644 index 0000000..422bba4 --- /dev/null +++ b/level-3/p2-find-the-access-codes/Solution.java @@ -0,0 +1,18 @@ +public class Solution { + public static int solution(int[] l) { + int count = 0; + + for(int i = 0; i < l.length; i++) { + for(int j = i + 1; j < l.length; j++) { //since index i < j search onwards for the second number + if(l[j] % l[i] == 0) { //if second number is divisible move on the finding the third + for(int k = j + 1; k < l.length; k++) { //same logic as loop above for the third number + if(l[k] % l[j] == 0) count++; //found a tuple since third is divisible by second + } + } + + } + } + + return count; + } +} \ No newline at end of file diff --git a/level-3/p3-doomsday-fuel/Problem.png b/level-3/p3-doomsday-fuel/Problem.png new file mode 100644 index 0000000..1be08b4 Binary files /dev/null and b/level-3/p3-doomsday-fuel/Problem.png differ diff --git a/level-3/p3-doomsday-fuel/Solution.java b/level-3/p3-doomsday-fuel/Solution.java new file mode 100644 index 0000000..e5073bb --- /dev/null +++ b/level-3/p3-doomsday-fuel/Solution.java @@ -0,0 +1,191 @@ +import java.util.stream.IntStream; + +public class Solution { + + public static int[] solution(int[][] m) { + double[][] matrix = new double[m.length][m.length]; //A, assume square matrix as stated + + //find terminal layers + int[] sums = new int[m.length]; //stored for later use + int firstTerminal = m.length; + + for (int i = 0; i < m.length; i++) { + sums[i] = IntStream.of(m[i]).sum(); + if (sums[i] != 0) { //only normalize for non terminal states + for (int j = 0; j < m[0].length; j++) { + matrix[i][j] = m[i][j] / (double) sums[i]; + } + } else { + firstTerminal--; + } + } + + //exceptional case return + + if(sums[0] == 0) { //s0 is terminal; cannot reach all other states + int[] fin = new int[m.length + 1]; + fin[0] = fin[m.length] = 1; + return fin; + } + + //continue computing + + int pointer = 0; + //move terminal states to the end + for (int i = 0; i < m.length; i++) { + if (sums[i] == 0) { + boolean swapped = false; + int origPos =(int) matrix[i][0]; //store orig pos in first cell of terminal vector since its unused anyways + if(origPos == 0) origPos = ++pointer; + + for (int j = i + 1; j < m.length; j++) { + if (sums[j] != 0) { //find earliest non terminal state to swap place + sums[i] = sums[j]; //update sums + sums[j] = 0; + + for (int k = 0; k < m.length; k++) { + matrix[i][k] = matrix[j][k]; //swap row + matrix[j][k] = 0; //always zero in terminal state vector + } + + for (int k = 0; k < m.length; k++) { + double temp = matrix[k][i]; + matrix[k][i] = matrix[k][j]; //swap column + matrix[k][j] = temp; + } + + matrix[j][0] = origPos; + swapped = true; + break; + } + } + + if(!swapped) matrix[i][0] = origPos; //if not swapped, its original + } + } + + int qSize = firstTerminal; + + for (int i = 0; i < qSize; i++) { // I - Q, where Q is sub square matrix of A in the non terminal region + for (int j = 0; j < qSize; j++) { + matrix[i][j] = (i == j ? 1 : 0) - matrix[i][j]; + } + } + + //start inversing Q + double[][] inverse = new double[qSize][qSize]; + + //minor and cofactor calculation + for (int i = 0; i < qSize; i++) { + for (int j = 0; j < qSize; j++) { + inverse[i][j] = Math.pow(-1, i + j) * determinant(minor(matrix, i, j, qSize), qSize - 1); + } + } + + //swap elements with determinant + double det = 1 / determinant(matrix, qSize); + for (int i = 0; i < qSize; i++) { + for (int j = 0; j <= i; j++) { + double temp = inverse[i][j]; + inverse[i][j] = inverse[j][i] * det; + inverse[j][i] = temp * det; + } + } + + //multiply inverse Q with terminal state sub matrix + double[] w = new double[matrix.length - firstTerminal]; + + for (int i = 0; i < w.length; i++) { + double sum = 0; + for (int k = 0; k < qSize; k++) { + sum += matrix[k][i + firstTerminal] * inverse[0][k]; //only need first row results + } + w[i] = sum; + } + + //turn into fractions + int[][] fractions = new int[w.length][2]; + int gcd = 1; + for (int i = 0; i < fractions.length; i++) { + int origPos = (int) matrix[i + firstTerminal][0] - 1; //fetch original pos from matrix + int[] f = decimalToFraction(w[i]); + fractions[origPos][0] = f[0]; + fractions[origPos][1] = f[1]; + if (f[1] != 1) //ignore denominator=1 + gcd = (gcd * f[1]) / gcd(gcd, f[1]); //LCM + } + + //get common denominator and populate the final returning array + int[] finalRes = new int[fractions.length + 1]; + for (int i = 0; i < fractions.length; i++) { + finalRes[i] = fractions[i][0] * (gcd / fractions[i][1]); + } + finalRes[fractions.length] = gcd; + + return finalRes; + } + + /** + * START MATRIX HELPER METHODS + * * assumes square matrixes only + */ + + private static double determinant(double[][] matrix, int n) { + if (matrix.length == 1 || n == 1) + return matrix[0][0]; + + double det = 0; + for (int i = 0; i < n; i++) { + det += Math.pow(-1, i) * matrix[0][i] * determinant(minor(matrix, 0, i, n), n - 1); + } + + return det; + } + + private static double[][] minor(double[][] matrix, int row, int column, int n) { + int size = n - 1; + double[][] minor = new double[size][size]; + + for (int i = 0; i < n; i++) { + for (int j = 0; i != row && j < n; j++) { + if (j != column) { + minor[i < row ? i : i - 1][j < column ? j : j - 1] = matrix[i][j]; + } + } + } + + return minor; + } + + /** + * START FRACTION HELPER METHODS + */ + + private static final double EPSILON = 1e-6; + + private static int[] decimalToFraction(double d) { + int xF = (int) Math.round(d); + int yF = 1; + double error = Math.abs(d - xF); + for (int y = 2; error > EPSILON; y++) { + int x = (int) (d * y); + for (int i = 0; i < 2; i++) { + double e = Math.abs(d - ((double) x / y)); + if (e < error) { + xF = x; + yF = y; + error = e; + } + x++; + } + } + return new int[] { xF, yF }; + } + + private static int gcd(int a, int b) { + if (a == 0) + return b; + + return gcd(b % a, a); + } +} \ No newline at end of file