UVA - 824 - Coast Tracker

This article will explain my thought process to solve a problem called Coast Tracker (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Geometry, Graph

Objective

Given:

The position and direction of a robot.
List of positions and surface types around the robot.
8 orientation types: north, north-west, west, south-west, south, south-east, east, north-east.
2 surface types: land and water.
Sea located at the right-side of the robot.

We want to:

Find the next direction of the robot.

Glossary

Geometry — A branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures.
Graph — A structure consisting of a set of objects where some pairs of the objects are related.

Observation

We could use geometry to model the position of the robot and surfaces as a point in a 2 dimensional space (x and y). For robot, there is an orientation as well, and the term that is used to describe position and orientation is pose.

Next, since we are only given information about the immediate neighbor surfaces, we could reconstruct the surfaces in a 9x9 grid. This is possible by calculating the relative position of the surface positions to the robot position.

After that, we want to travel along the shoreline, which should be on the right side of the robot. In order to achieve this, we want the robot to scan the surfaces in anti-clockwise direction, starting from the first right orientation, which should be 225 degree relative to the current orientation of the robot. The first land that is discovered is the shoreline.

Algorithm

The relative position can be calculated by subtracting the surface position with the robot position. Since array couldn’t have negative index, we want to place the center position for the robot at (1, 1), and this means we need to add the relative position with that point.

The anti-clockwise scan can be implemented iteratively process the 8 orientation, starting from the orientation that is 225 degree relative to the current orientation, or in other words (orientation + 5) mod 8.

The time complexity of this solution is O({total directions}) or O(10^1).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 824 - Coast Tracker
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=765
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        for (int caseId = 1; in.hasNextInt(); caseId++) {
            final int x = in.nextInt();
            final boolean isEOF = x == -1;
            if (isEOF) break;

            final Input input = new Input();
            input.caseId = caseId;
            input.robot = new Pose(new Point(x, in.nextInt()), in.nextInt());
            input.surfaces = new Surface[8];
            for (int i = 0; i < 8; i++) {
                input.surfaces[i] = new Surface(new Point(in.nextInt(), in.nextInt()), in.nextInt());
            }

            final Output output = process.process(input);
            out.println(output.orientation);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int caseId;
    public Pose robot;
    public Surface[] surfaces;
}

class Output {
    public int caseId;
    public int orientation;
}

class Process {
    private static final Point CENTER_POSITION = new Point(1, 1);

    public Output process(final Input input) {
        final Output output = new Output();
        output.caseId = input.caseId;

        final int[][] grid = new int[3][3];
        grid[CENTER_POSITION.x][CENTER_POSITION.y] = SurfaceType.LAND;
        for (final Surface surface : input.surfaces) {
            final Point relativePosition = surface.position.subtract(input.robot.position).add(CENTER_POSITION);
            grid[relativePosition.x][relativePosition.y] = surface.surfaceType;
        }

        for (int i = 0; i < 8; i++) {
            final int nextOrientation = (input.robot.orientation + 5 + i) % 8;
            final Point nextPosition = CENTER_POSITION.move(nextOrientation);
            final int nextSurface = grid[nextPosition.x][nextPosition.y];

            if (nextSurface == SurfaceType.LAND) {
                output.orientation = nextOrientation;
                break;
            }
        }

        return output;
    }
}

class Surface {
    public final Point position;
    public final int surfaceType;

    Surface(final Point position, final int surfaceType) {
        this.position = position;
        this.surfaceType = surfaceType;
    }
}

class Pose {
    public final Point position;
    public final int orientation;

    public Pose(final Point position, final int orientation) {
        this.position = position;
        this.orientation = orientation;
    }
}

class Point {
    public final int x;
    public final int y;

    public Point(final int x, final int y) {
        this.x = x;
        this.y = y;
    }

    public Point add(final Point o) {
        return new Point(x + o.x, y + o.y);
    }

    public Point subtract(final Point o) {
        return new Point(x - o.x, y - o.y);
    }

    public Point move(final int orientation) {
        switch (orientation) {
            case Orientation.NORTH:
                return new Point(x, y + 1);
            case Orientation.NORTH_WEST:
                return new Point(x - 1, y + 1);
            case Orientation.WEST:
                return new Point(x - 1, y);
            case Orientation.SOUTH_WEST:
                return new Point(x - 1, y - 1);
            case Orientation.SOUTH:
                return new Point(x, y - 1);
            case Orientation.SOUTH_EAST:
                return new Point(x + 1, y - 1);
            case Orientation.EAST:
                return new Point(x + 1, y);
            case Orientation.NORTH_EAST:
                return new Point(x + 1, y + 1);
        }
        return this;
    }
}

class Orientation {
    public static final int NORTH = 0;
    public static final int NORTH_WEST = 1;
    public static final int WEST = 2;
    public static final int SOUTH_WEST = 3;
    public static final int SOUTH = 4;
    public static final int SOUTH_EAST = 5;
    public static final int EAST = 6;
    public static final int NORTH_EAST = 7;
}

class SurfaceType {
    public static final int WATER = 0;
    public static final int LAND = 1;
}