This week I decided to start learning a new programming language. While surfing the web I somehow got to Google Code Jam site and practice page. So I though that it might be a good idea to do try solving problems using java and then code the same solution in a one or more language. The first exercise was All Your Base. Alien encrypted the number of seconds before the war begins in a single string. We know that each character represents a digit but we don't know what base are they using.
The idea is pretty simple:
We want to pick the minimum base and compose a minimum number in that base.
The base of the minimum number is determined by number of unique digits.
Now we build the minimum number:
The first digit will be 1, since it cannot start with 0, thus the second digit will be 0.
Now we pass over the inputs string and each digit we replace with the next available number in our base in ascending order
.
I first coded it on java:
Next mission was doing it on groovy, it is easier for me since you can use java libraries and the learning curve is pretty fast. It is the first time that I tried groovy. My goal was to minimize the number of lines as much as possible. Not sure if this is the best practice, but it produces the same result.
The idea is pretty simple:
We want to pick the minimum base and compose a minimum number in that base.
The base of the minimum number is determined by number of unique digits.
Now we build the minimum number:
The first digit will be 1, since it cannot start with 0, thus the second digit will be 0.
Now we pass over the inputs string and each digit we replace with the next available number in our base in ascending order
.
I first coded it on java:
package one;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.math.BigInteger;
import java.util.LinkedHashMap;
import java.util.Scanner;
public class AllYourBase {
/**
* @param args
* @throws FileNotFoundException
*/
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner(new BufferedReader(new FileReader(new File("C:/Users/dell/Desktop/A-large-practice.in"))));
Integer numOfTimes = 0;
if(sc.hasNextLine()){
numOfTimes = Integer.parseInt(sc.nextLine());
}
int i=1;
while(sc.hasNextLine()){
String input = sc.nextLine();
String result = calculateResult(input, i );
System.out.printf("Case #%d: %s\n", i , result);
i++;
}
}
private static String calculateResult(String input, int i) {
LinkedHashMap<String, String> decryption = new LinkedHashMap<String, String>();
char[] result = input.toCharArray();
int numOfOccurance = 0;
for (int j = 0; j < result.length; j++) {
String count = decryption.get(result[j] + "");
if (count == null) {
if (numOfOccurance == 0) {
decryption.put(result[j] + "", getCharacter(1));
} else if (numOfOccurance == 1) {
decryption.put(result[j] + "", getCharacter(0));
} else {
decryption.put(result[j] + "", getCharacter(numOfOccurance));
}
numOfOccurance++;
}
}
StringBuffer strResult = new StringBuffer();
for (int j = 0; j < result.length; j++) {
strResult.append(decryption.get(result[j] + ""));
}
int base = decryption.size();
//Base cannot be unary.
if(base == 1){
base = 2;
}
return convertToDecimal(strResult, base);
}
static String chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
private static String getCharacter(int i) {
return chars.charAt(i)+"";
}
private static String convertToDecimal(StringBuffer strResult, int base) {
BigInteger intt = new BigInteger(strResult.toString(), base);
return intt.toString(10);
}
}
Next mission was doing it on groovy, it is easier for me since you can use java libraries and the learning curve is pretty fast. It is the first time that I tried groovy. My goal was to minimize the number of lines as much as possible. Not sure if this is the best practice, but it produces the same result.
package ex1
class AllYourBase {
static String calculateResult(String input) {
LinkedHashMap<Character, String> decryption = new LinkedHashMap<String, String>();
def digits = "1023456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int numOfOccurance = 0;
def decryptedNumber = input.collect({value ->
if (decryption[value] == null) {
decryption[value] = digits[numOfOccurance++];
}
decryption[value];
}
).join("");
int base = decryption.size() == 1 ? 2 : decryption.size();
return new BigInteger(decryptedNumber,base).toString(10);
}
static void main(def args){
int i=1;
new File(args[0]).eachLine(1 , { line -> if(i != 1){
printf ("Case #%d: %s\n", i-1 , calculateResult(line));
}; i++; })
}
}
Next thing is to code the same solution in a functional language. Since I like the comfort of JVM, it might be on Clojure.
