Java Coding Contest Results


Collapse Content

Results

Yesterday, Learneroo ran our first Java Coding Contest. Over 200 people signed up and over 30 solved at least one challenge. After some hiccups (we learn by doing!), the contest got underway and saw some great contestants and code! The final winners were:

1 - Egor Kulikov
1 - Fred
2 - Bantha
3 - Arthur Wong

Yes, there are two 1st place winners. Egor, the previous winner of Google Code Jam and other international contests, won with solid clean code. Fred solved the ordinary challenges and the early Java explorer challenges fairly, and then beat the later levels by hacking the game with reflection to delete all the enemies! We didn't have an explicit rule against reflection, so we decided to award both winners first place. Jetbrains kindly agreed to sponsor two copies of IntelliJ IDEA Ultimate, so both winners will receive the prize. (Didn't win? You can download IntelliJ IDEA from Jetbrain's site.)

Below is a quick explanation of some of the challenges.

Starting Challenge

This challenge was to test out the interface and your if statement. In Java, you need to make sure not to call an index out of bounds, so here's a solution:

static void doStuff(int[] ar){
    int sum=0;
    for(int i=0; i<ar.length; i++){
        sum+=ar[i];

        if((i<ar.length-1 && ar[i+1]==2) || (i>0 && ar[i-1]==2) ){
            sum+=ar[i];
        }
    }
    System.out.println(sum);
}

If you solved it in Ruby you could skip the out-of-bounds check:

def do_stuff(ar)
    sum=0
    ar.each_with_index do |num, i|
        sum += num
        if ar[i-1]==2 or ar[i+1]==2
            sum += num 
        end
    end
    puts sum
end

Correct Change

To do this problem efficiently, you should avoid using too many loops. An earlier correct change challenge asked if you could reach a sum with 2 coins, and could be solved with no loops. This one asks about 3 coins, so it makes sense to use 1 loop for it. Here is Egor's solution:

public static void doStuff(int[] ar){
    //the number of each coins
    int q1 = ar[0];
    int q11 = ar[1];
    int q111 = ar[2];
    int target = ar[3];

    // Go through all amounts of 111 coins until target
    for (int i = 0; i <= q111 && 111 * i <= target; i++) {
        //current = amount remaining when using `i` 111-coins
        int current = target - 111 * i; 
        //use as many 11's without going over
        int take11 = Math.min(q11, current / 11);
        current -= take11 * 11;
        //then check if the 1's can fill in the rest.
        if (current <= q1) {
            System.out.println(true);
            return;
        }
    }
    System.out.println(false);
}

Select Change

The tutorial on Backtracking covered the basic concepts for this challenge. For this challenge, you just need to keep track of how many coins in a row you selected. Here's one way to do that:

static void doStuff(int[] ar) { 
    int num = ar[0];
    int[] ar2 = Arrays.copyOfRange(ar, 1, ar.length);
    System.out.println(sumCoins(0, ar2, num, false));       
}   

static boolean sumCoins(int start, int[] nums, int target, boolean didPrev) {         
     if(start>=nums.length)
        return target == 0;  

     //ignore current coin, so target doesn't change
     boolean b = sumCoins(start+1, nums, target, false);

     //alternatively, take current coin:
     boolean a;
     if(didPrev) //skip next if would be 3-in-a-row
          a = sumCoins(start+2, nums, target-nums[start], false);
      else  //otherwise go on to next coin
          a = sumCoins(start+1, nums, target-nums[start], true);

      return a || b;
} 

Manhattan Meeting Place

To optimally solve this challenge, think about where the best meeting point would be on one street. The mean point? No, there's no reason to make multiple people walk to be closer to 1 far-away person.

Example:

0....5....0....5....0.......28
.PPPPPP.....................P

People are located at positions 1 through 6 in the above 'diagram' and at position 28. The mean is located at position 7. Should that be the meeting place?

If you move the meeting place from 7 to 6, you'll make it 1 unit closer to 6 people, and 1 unit farther for 1 person, for a gain of 5 overall. In fact, the meeting point should be shifted until there's an equal number on each side, i.e. the median. In the above diagram, that would be at point 4, which would leave 3 people to each side.

The same rule applies to a 2D grid. The best place to meet is the median of the x coordinates and the median of the y coordinates. Any shifting from this point (past a person's x or y values) would make the point further from more than half the people.

Thanks to everyone for participating!

Comments

All Node Comments
Contact Us
Sign in or email us at [email protected]