CodeEval's SkyScrapers challenge

This is a solution to CodeEval's SkyScrapers challenge.

You are given a list of triples \$(l, h, r)\$. Each triple represents an axis-aligned rectangle, with top-left corner at \$(l, h)\$ and bottom-right corner at \$(r, 0)\$. You can imagine these rectangles as buildings against a skyline.

The task is to "draw" the skyline, by printing a list of points \$(x, h)\$ where the line drawing of the skyline changes from horizontal to vertical, and \$h\$ is the height of the vertical line.

For all heights \$h\$, \$1 \leq h \leq 100\$. For all \$x\$-coordinates, \$1 \leq x \leq 10{,}000\$. There are at most \$1{,}000\$ rectangles/buildings.

Examples:

Input: (1,2,3);(2,4,6);(4,5,5);(7,3,11);(9,2,14);(13,7,15);(14,3,17)

Output: 1 2 2 4 4 5 5 4 6 0 7 3 11 2 13 7 15 3 17 0

Input: (1,2,6);(9,23,22);(22,6,24);(8,14,19);(23,12,30)

Output: 1 2 6 0 8 14 9 23 22 6 23 12 30 0

The solution uses a sweep-line algorithm to find the points where the height of the outline changes.

Scanner is a silly class to parse the ridiculous input format. In an ideal world it wouldn't exist, but it shaved off a significant amount of time.

```
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

class Main {
public static void main(String[] args) {
try {
List lines = Files.readAllLines(Paths.get(args[0]), StandardCharsets.UTF_8);
for (String line : lines) {
System.out.println(getSkyline(line));
}
} catch (IOException e) {
e.printStackTrace();
}
}

private static String getSkyline(String line) {
List points = readPoints(line);
Collections.sort(points);
StringBuilder sb = new StringBuilder();
SortedMap heights = new TreeMap<>();
int height = 0;
for (Point point : points) {
int newHeight = getNewHeight(

Reading Points

you have the method and class:

private static List readPoints(String line) {
    List points = new ArrayList<>();
    Scanner scanner = new Scanner(line);
    while (scanner.hasNext()) {
      int left = scanner.next();
      int height = scanner.next();
      int right = scanner.next();
      points.add(new Point(left, height, true));
      points.add(new Point(right, height, false));
    }
  }

This is to process data of the form:

(1,2,6);(9,23,22);(22,6,24);(8,14,19);(23,12,30)

The common way in Java to process input like this is to use a Matcher:

private static final Pattern POINT_PATTERN = Pattern.compile("\\((\\d+),(\\d+),(\\d+)\\);?");

  private static List readPoints(String line) {
    List points = new ArrayList<>();
    Matcher matcher = POINT_PATTERN.matcher(line);
    while (matcher.find()) {
        int left   = Integer.parseInt(matcher.group(1));
        int height = Integer.parseInt(matcher.group(2));
        int right  = Integer.parseInt(matcher.group(3));
        points.add(new Point(left, height, true));
        points.add(new Point(right, height, false));
    }
    return points;
  }

Note that the matcher looks for three comma-separated number-groups inside explicit parenthesis, with an optional trailing semi-colon. The parenthesis around the \\d+ in the pattern makes those available as groups. The (expanded) pattern is:

\(    (\d+)   ,   (\d+)   ,   (\d+)   \)    ;?

      ^^^^^       ^^^^^       ^^^^^         ^^
      | Group 1
                  | Group 2
                              | Group 3
                                            | Optional ;

That would significantly simplify the code.

Point

Your Point class implements Comparable. This is nice, but whenever you have a natural order implied with a class, you should also override equals() and hashCode() (the contract is that any two objects which have compareTo() return 0, should also be equals().

The 'y' variable is also a bit of a poor name, I would prefer the name 'height'. While we are naming things, I would call the 'Point' class 'Event' too.

I used some bit-shifting to pre-calculate the hashCode.

I ended up with:

private static class Event implements Comparable {

    private final boolean isStart;
    private final int x;
    private final int height;
    private final int hash;

    public Event(int x, int height, boolean isStart) {
        this.x = x;
        this.height = height;
        this.isStart = isStart;
        this.hash = ((isStart ? 1 : -1) * x) ^ (height >> 16);
    }

    @Override
    public int hashCode() {
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        return obj == this || ((obj instanceof Event) && hashCode() == obj.hashCode() && compareTo((Event)obj) == 0);
    }

    @Override
    public int compareTo(Event other) {
        int result = Integer.compare(this.x, other.x);
        if (result != 0) {
            return result;
        }
        if (this.isStart == other.isStart) {
            return this.isStart ? Integer.compare(other.height, this.height) : Integer.compare(this.height, other.height);
        }
        return this.isStart ? -1 : 1;
    }

}

Algorithm

It took me a while to understand the algorithm.

In general, i dislike the use of a Map because it is ugly that you have to check for the null value before you can increment the count (the value is a Counter of sorts).

This part is something I believe should have been rewritten as a separate class. A HeightTracker class perhaps. The class could have a mutable inner class called Counter that can be incremented/decremented in place. When it decrements to 0, it auto-removes from the Map. The removal of the autoboxing may lead to performance improvements, but those will be small.

The other observation I have is that the SortedMap should probably have a custom comparator that sorts in reverse-height order. This is another small item, but it is more intuitive to me to have a call to heights.firstKey() rather than heights.lastKey()

The HeightTracker may even be better off as a completely custom class without the SortedMap at all. I would have to rewrite it myself to see.

Apart from these issues, the algorithm strikes me as being sound. It's not quite the same as some papers I read on the subject, but the performance time-complexity of \$O(n \log{n})\$ is in line with expectations.

I do have an issue with the multi-responsibility method though, building the skyiline and appending to the StringBuilder at the same time. For more flexibility and cleaner code, you should produce list of events from the getSkyline and only then convert those events to the String output... Single Responsibility Principle

Resources

• Algorithmist description of the Skyline problem, and possible solutions.

• UCSD evaluation (pdf)

• A good blog about the problem (Szabolcs Andrási)

• Wikipedia page on sweep-line solutions

• D

StackExchange Code Review Q#66626, answer score: 9