ForrestTerrain.java

ForrestTerrain.java

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package fmidemo;

public class ForestTerrain {
    
    static int findLargestAreaAround(char[][] terrain, boolean[][] visited, int i, int j) {
        if (visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        int areaSize = 1;
        // Up
        if (i > 0 && terrain[i - 1][j] == terrain[i][j]) {
            areaSize += findLargestAreaAround(terrain, visited, i - 1, j);
        }
        // Down
        if (i < terrain.length - 1 && terrain[i + 1][j] == terrain[i][j]) {
            areaSize += findLargestAreaAround(terrain, visited, i + 1, j);
        }
        // Left
        if (j > 0 && terrain[i][j - 1] == terrain[i][j]) {
            areaSize += findLargestAreaAround(terrain, visited, i, j - 1);
        }
        // Right
        if (j < terrain[0].length - 1 && terrain[i][j + 1] == terrain[i][j]) {
            areaSize += findLargestAreaAround(terrain, visited, i, j + 1);
        }
        return areaSize;
    }
    
    static int findLargestArea(char[][] terrain) {
        boolean[][] visited = new boolean[terrain.length][terrain[0].length];
        int currentLargest = 0;
        for (int i = 0; i < terrain.length; i++) {
            for (int j = 0; j < terrain[0].length; j++) {
                if (terrain[i][j] == '4') {
                    int areaSize = findLargestAreaAround(terrain, visited, i, j);
                    if (areaSize > currentLargest) {
                        currentLargest = areaSize;
                    }
                }
            }
        }
        return currentLargest;
    }
    
    public static void main(String[] args) {
        char[][] terrain = new char[][]{
            { 'R', 'R', '1', '4', '1', '2' },
            { '1', 'R', '4', '4', '4', '2' },
            { 'S', '4', '4', 'R', '4', '3' },
            { '4', '4', 'S', 'S', '4', '4' } 
        };
        System.out.println(findLargestArea(terrain));
        
    }
}

SortedLinkedList.java

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package fmidemo;

class LinkedList<T> {
    T value;
    LinkedList next;
    public LinkedList(T num) {
        this.value = num;
    }
    public void append(LinkedList<T> item) {
        item.next = this.next;
        this.next = item;
    }
}
public class SortedLinkedLists {
    
    static LinkedList<Integer> findBiggestSmallerThan(LinkedList<Integer> list, int num) {
        LinkedList<Integer> result = null;
        for (LinkedList<Integer> element = list; element != null; element = element.next) {
            if (element.value < num && (result == null || element.value > result.value)) {
                result = element;
            }
        }
        return result;
    }
    
    static boolean isSorted(LinkedList<Integer> list) {
        for (LinkedList<Integer> element = list; element.next != null; element = element.next) {
            LinkedList<Integer> next = element.next;
            // element.next.value doesn't work, WTF JAVA, HOW DO YOU SUCK SO MUCH
            if (element.value > next.value) {
                return false;
            }
        }
        return true;
    }
    static LinkedList<Integer> mergeSorted(LinkedList<LinkedList<Integer>> lists) {
        LinkedList<Integer> resultHead = null;
        
        for (LinkedList<LinkedList<Integer>> it = lists; it != null; it = it.next) {
            if (!isSorted(it.value)) {
                continue;
            }
            for (LinkedList<Integer> element = it.value; element != null; element = element.next) {
                LinkedList<Integer> newNode = new LinkedList<Integer>(element.value);
                if (resultHead == null) {
                    resultHead = newNode;
                    continue;
                }
                LinkedList<Integer> smaller = findBiggestSmallerThan(resultHead, newNode.value);
                if (smaller == null) {
                    // There was no smaller value; the current one is the smallest
                    newNode.next = resultHead;
                    resultHead = newNode;
                }
                else {
                    smaller.append(newNode);
                }
            }
        }
        
        return resultHead;
    }
    
    static <T> LinkedList<T> createList(T[] data) {
        LinkedList<T> head = new LinkedList<T>(data[0]);
        LinkedList<T> current = head;
        for (int i = 1; i < data.length; i++) {
            current.append(new LinkedList<T>(data[i]));
            current = current.next;
        }
        return head;
    }
    
    static void printList(LinkedList<Integer> list) {
        for (LinkedList<Integer> element = list; element != null; element = element.next) {
            System.out.print(element.value);
            System.out.print(' ');
        }
        System.out.println();
    }
    public static void main(String[] args) {
        LinkedList<Integer> list1 = createList(new Integer[]{5, -5, 4});
        LinkedList<Integer> list2 = createList(new Integer[]{-42, -300, -1000});
        LinkedList<Integer> list3 = createList(new Integer[]{0, 777, 6666});
        
        LinkedList<LinkedList<Integer>> lists = new LinkedList<LinkedList<Integer>>(list1);
        lists.next = new LinkedList<LinkedList<Integer>>(list2);
        lists.next.next = new LinkedList<LinkedList<Integer>>(list3);
        
        LinkedList<Integer> merged = mergeSorted(lists);
        
        printList(merged);
    }
}