12
\$\begingroup\$

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:

Example input one

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

Example output one

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

Example input two

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

Example output two

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;
    }
  }
}
\$\endgroup\$
  • \$\begingroup\$ Can we assume that a building will always be on x = 1? (I will answer tomorrow) \$\endgroup\$ – Funky Oct 16 '14 at 14:29
  • \$\begingroup\$ @TheFailure, I don't believe so. The original problem statement in is the link, which may be clearer. \$\endgroup\$ – mjolka Oct 16 '14 at 20:15
8
+50
\$\begingroup\$

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(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

\$\endgroup\$
  • \$\begingroup\$ Great answer, I've learned a lot from this. Could you please provide a link to the papers you mention? \$\endgroup\$ – mjolka Oct 16 '14 at 20:19
  • \$\begingroup\$ Updated to include some references (some of the papers I read were more complicated than necessary and dealt with fuzziness and incomplete data). Note the last reference is a novel approach. \$\endgroup\$ – rolfl Oct 16 '14 at 21:30
6
\$\begingroup\$

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:

  • Point Constructor JavaDoc: The start of what is isStart revering to?
  • Point:compareTo JavaDoc: how are points sorted?
  • getNewHeight JavaDoc: 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

\$\endgroup\$
  • \$\begingroup\$ Sorry about the confusion with the output format, the output samples (and code) use the correct format as specified by CodeEval. Good point about unit tests, they helped me greatly in getting this correct, I just didn't include them in the question. \$\endgroup\$ – mjolka Oct 14 '14 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.