Problem
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≤h≤100. For all x-coordinates, 1≤x≤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<String> 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<Point> points = readPoints(line);
Collections.sort(points);
StringBuilder sb = new StringBuilder();
SortedMap<Integer, Integer> heights = new TreeMap<>();
int height = 0;
for (Point point : points) {
int newHeight = getNewHeight(height, point, heights);;
if (newHeight != height) {
sb.append(point.x).append(' ').append(newHeight).append(' ');
height = newHeight;
}
}
return sb.deleteCharAt(sb.length() - 1).toString();
}
private static int getNewHeight(int height, Point point, SortedMap<Integer, Integer> heights) {
if (point.isStart) {
Integer count = heights.get(point.y);
heights.put(point.y, count == null ? 1 : count + 1);
return Math.max(height, point.y);
}
Integer count = heights.get(point.y) - 1;
if (count == 0) {
heights.remove(point.y);
if (point.y == height) {
return heights.isEmpty() ? 0 : heights.lastKey();
}
return height;
}
heights.put(point.y, count);
return height;
}
private static List<Point> readPoints(String line) {
List<Point> 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));
}
return points;
}
private static class Point implements Comparable<Point> {
private final boolean isStart;
private final int x;
private final int y;
public Point(int x, int y, boolean isStart) {
this.x = x;
this.y = y;
this.isStart = isStart;
}
public int compareTo(Point other) {
int result = Integer.compare(this.x, other.x);
if (result == 0) {
if (this.isStart == other.isStart) {
return this.isStart ? Integer.compare(other.y, this.y) : Integer.compare(this.y, other.y);
}
return this.isStart ? -1 : 1;
}
return result;
}
}
private static class Scanner {
private final String line;
private final int length;
private int i;
public Scanner(final String line) {
this.line = line;
this.length = line.length();
}
public boolean hasNext() {
moveNext();
return this.i < this.length;
}
public int next() {
moveNext();
int n = 0;
int c;
while ((c = toInt(this.line.charAt(this.i))) != -1) {
n = n * 10 + c;
this.i++;
}
return n;
}
private void moveNext() {
while (this.i < this.length && toInt(this.line.charAt(this.i)) == -1) {
this.i++;
}
}
private static int toInt(char c) {
return (c >= '0' && c <= '9') ? c - '0' : -1;
}
}
}
Solution
Reading Points
you have the method and class:
private static List<Point> readPoints(String line) {
List<Point> 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<Point> readPoints(String line) {
List<Point> 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<Event> {
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 | 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<Integer,Integer> 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(nlogn) 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
Structure
Right now, you can only create a skyline for this one type of input format. To fix this, readPoints shouldn’t be part of getSkyline. Instead, getSkyline should accept a list of Point objects (which you created somewhere else, eg main).
Output
In your problem description it says: printing a list of points (x,h), but you are not formatting it like this (which makes it a bit hard to read the output).
Scanner Class
I think it’s good to have a class to parse input, but it is quite obvious that you didn’t really want to have such a class. Your variable naming is generally good, but in Scanner, you have names such as n, c, and i, which make the code hard to read. Scanner itself is also not a good name, Parser would be a better fit. moveNext could also be better named: move what next? To the next word/number/pair of numbers?
Your hasNext method also moves to next, which seems a little odd to me. I would try to rewrite the code so that it does not do this.
You might also want to include some kind of check/error handling for malformed input (although that’s not too important for a throw-away class like this).
Comments
A comment or two wouldn’t hurt your code. They are not strictly necessary, but it would help a reader to faster understand your code. For example:
PointConstructor JavaDoc: The start of what isisStartrevering to?Point:compareToJavaDoc: how are points sorted?getNewHeightJavaDoc: just a general comment on what this does.getSkyline: maybe an inline comment on how this works, or at least the name of the algorithm.
Misc
- you should use
@Overridefor overriding methods - if you implement comparable, you might also want to implement equals (
It is strongly recommended (though not required) that natural orderings be consistent with equals.). - unit tests are not necessary, but are always a good thing to verify functionality and to help while developing.