Island Counting: Flood Fill vs Hash Deduping

insland.java

package scratch;

import java.util.*;

public class islands {

  public static void main(String args[]){

    boolean map[][] = generateIslands(180, 50, new Random(287), 25, 15, .3);
    System.out.println(drawMap(map));
    System.out.println("Flood count:" + floodCount(map));
    System.out.println("Hash Count:" + hashCount(map));

    int amount = 5000;
    boolean maps[][][] = new boolean[amount][][];

    System.out.println("Generating " + amount +" maps for speed test...");
    for(int seed = 0; seed < amount; seed++){
      maps[seed] = generateIslands(180, 50, new Random(seed), 25, 15, .3);
    }
    System.out.println("testing flood...");
    long flood_start = System.nanoTime();
    int flood_result[] = new int[amount];
    for(int seed = 0; seed < amount; seed++){
      flood_result[seed] = floodCount(maps[seed]);
      flood_result[seed] = floodCount(maps[seed]);
      flood_result[seed] = floodCount(maps[seed]);
    }
    long flood_end = System.nanoTime();

    System.out.println("testing hash dedupe...");
    long hash_start = System.nanoTime();
    int hash_result[] = new int[amount];
    for(int seed = 0; seed < amount; seed++){
      hash_result[seed] = hashCount(maps[seed]);
      hash_result[seed] = hashCount(maps[seed]);
      hash_result[seed] = hashCount(maps[seed]);
    }
    long hash_end = System.nanoTime(); 

    int same_result = 0 ;
    for(int k=0;k<amount;k++){
      if(hash_result[k] == flood_result[k]){
        same_result++;
      }else{
        System.out.println("mismatch seed:" + k + " flood:" + flood_result[k] +" hash:" + hash_result[k]);
      }
    }
    System.out.println("Matching results:" + same_result +"/" + amount);
    System.out.println("Flood time:" + (flood_end-flood_start));
    System.out.println("Hash time:" + (hash_end-hash_start));  
    System.out.println("Hashing speed up:" + (flood_end-flood_start)/(double)(hash_end-hash_start)); 
  }

  // Flood fills when hits new land. Counts number of floods.
  public static int floodCount(boolean map[][]){
    boolean checked[][] = new boolean[map.length][map[0].length];
    int count = 0 ;
    for(int x = 0; x < map.length; x++){
      for(int y  = 0; y < map[x].length; y++){
        if(map[x][y] && !checked[x][y]){
          count++;
          Queue<Point> queue = new LinkedList<Point>();
          queue.add(new Point(x,y));
          checked[x][y] = true;
          while(!queue.isEmpty()){
            Point p = queue.poll();
            if(p.x > 0 && !checked[p.x-1][p.y] && map[p.x-1][p.y]){
              checked[p.x-1][p.y]  = true;
              queue.add(new Point(p.x-1,p.y));
            }
            if(p.y > 0 && !checked[p.x][p.y-1] && map[p.x][p.y-1]){
              checked[p.x][p.y-1] = true;
              queue.add(new Point(p.x,p.y-1));
            }
            if(p.x+1 < map.length && !checked[p.x+1][p.y] && map[p.x+1][p.y]){
              checked[p.x+1][p.y] = true;
              queue.add(new Point(p.x+1,p.y));
            }
            if(p.y+1 < map[p.x].length && !checked[p.x][p.y+1] && map[p.x][p.y+1]){
              checked[p.x][p.y+1] = true;
              queue.add(new Point(p.x,p.y+1));
            }
          }
        }
      }
    }
    return count;
  }

  // Marks simply connected regions with numbers and maintains a table of numbers that mpa to the same island.
  public static int hashCount(boolean map[][]){
    int label[][] = new int[map.length][map[0].length];
    int count = 0 ;
    Hashtable<Integer,Integer> dupes = new Hashtable<Integer,Integer>();
    for(int x = 0; x < map.length; x++){
      for(int y  = 0; y < map[x].length; y++){
        if(map[x][y]){
          boolean has_left = x > 0 && map[x-1][y] ;
          boolean has_up = y > 0 && map[x][y-1] ;
          if(has_left && has_up && label[x][y-1] != label[x-1][y]){
            int left = label[x-1][y];
            int up = label[x][y-1];
            while(dupes.containsKey(left)){
              left = dupes.get(left);
            }
            while(dupes.containsKey(up)){
              up = dupes.get(up);
            }
            if(up!=left){
              int min = Math.min(up,  left);
              int max = Math.max(up,  left);
              dupes.put(max,min);
              label[x][y] = min;
            }else{
              label[x][y] = up;
            }
          }else if(has_up){
            label[x][y] = label[x][y-1];
          }else if(has_left){
            label[x][y] = label[x-1][y];
          }else{
            count++;
            label[x][y] = count;
          }
        }
      }
    }
    return count - dupes.size();
  }

  // Generates a random continent-like island arrangement.
  public static boolean[][] generateIslands(int width, int height, Random rand, int seeds, int expand, double chance){
    boolean map[][] = new boolean[width][height];
    for(int k = 0;k < seeds; k++){
      int x = rand.nextInt(width);
      int y = rand.nextInt(height);
      map[x][y] = true;
    }
    for(int k=0;k<expand;k++){
      map = expand(map, rand, chance);
    }
    return map;
  }

  // Expand land for generating simply continuous regions.
  public static boolean[][] expand(boolean map[][]){
    boolean new_map[][] = new boolean[map.length][map[0].length];
    for(int x = 0; x < map.length; x++){
      for(int y  = 0; y < map[x].length; y++){
        new_map[x][y] = map[x][y] 
            || (x+1 < map.length && map[x+1][y])
            || (x-1 >= 0 && map[x-1][y])
            || (y+1 < map[x].length && map[x][y+1])
            || (y-1 >= 0 && map[x][y-1]);
      }
    }
    return new_map;
  }

  // Probabilistically add land near existing land.
  // Used for generating interesting continuous island regions.
  public static boolean[][] expand(boolean map[][], Random rand, double chance){
    boolean new_map[][] = new boolean[map.length][map[0].length];
    for(int x = 0; x < map.length; x++){
      for(int y  = 0; y < map[x].length; y++){
        new_map[x][y] = map[x][y] 
            || (x+1 < map.length && map[x+1][y] && rand.nextDouble() < chance)
            || (x-1 >= 0 && map[x-1][y] && rand.nextDouble() < chance)
            || (y+1 < map[x].length && map[x][y+1] && rand.nextDouble() < chance)
            || (y-1 >= 0 && map[x][y-1] && rand.nextDouble() < chance);
      }
    }
    return new_map;
  }

  // Draw an island map.
  public static String drawMap(boolean map[][]){
    String map_string = "";
    for(int y  = 0; y < map[0].length; y++){
      String row_string = y == 0 ? "" : "\n";
      for(int x = 0; x < map.length; x++){
        if(map[x][y]){
          row_string+="O";
        }else{
          row_string+="-";
        }
      }
      map_string += row_string;
    }
    return map_string;
  }

  // Draws a map of integers by mapping to individual characters.
  public static String drawMap(int map[][]){
    String map_string = "";
    char[] alphabet = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()~".toCharArray();
    for(int y  = 0; y < map[0].length; y++){
      String row_string = y == 0 ? "" : "\n";
      for(int x = 0; x < map.length; x++){
        row_string+=alphabet[map[x][y]%alphabet.length];
      }
      map_string += row_string;
    }
    return map_string;
  }

  // Used for debugging hash fill.
  public static String drawMap(int map[][], Hashtable<Integer,Integer> dupes){
    String map_string = "";
    char[] alphabet = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()~".toCharArray();

    //Collapse dupe table.
    Enumeration<Integer> a = dupes.keys();
    while(a.hasMoreElements()){
      int key = a.nextElement();
      int value = dupes.get(key);
      while(dupes.containsKey(value)){
        value = dupes.get(value);
      }
      dupes.put(key,value);
    }

    for(int y  = 0; y < map[0].length; y++){
      String row_string = y == 0 ? "" : "\n";
      for(int x = 0; x < map.length; x++){
        if(dupes.containsKey(map[x][y])){
          map[x][y] = dupes.get(map[x][y]);
        }
        row_string+=alphabet[map[x][y]%alphabet.length];
      }
      map_string += row_string;
    }
    return map_string;
  }

  // Used for queue locations in flodd fill.
  static class Point{
    public int x, y;
    public Point(int x, int y){
      this.x = x;
      this.y = y ;
    }

  }

}