UVA - 10203 - Snow Clearing

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

Keywords: Geometry, Graph, Chinese Postman Problem

Objective

Given:

A hangar coordinate.
List of intersection coordinates.
List of roads between intersections.
Road specifications.
1. Goes perfectly straight between 2 intersections.
2. Consist of 2 lanes that goes in the opposite direction.
3. Speed of 20 km/h when plowing.
4. Speed of 50 km/h when driving.
5. Can turn to any directions on an intersections.

We want to:

Find the minimum total times to plow every lanes.

Glossary

Geometry — A branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures.
Pythagoras Theorem — A theorem that relates to the lengths of the three sides of a right-angled triangle.
Graph — A structure consisting of a set of objects where some pairs of the objects are related.
Chinese Postman Problem (CPP) — A mathematical problem in graph theory that involves finding the shortest closed path or circuit that visits all edges of a graph at least once.

Observation

We can model the hangar, intersection, road, and lane as a geometry object. Hangar and intersection are formed from x and y coordinates, thus we can model it as a point. Road and lane goes straight between 2 intersections, thus we can model it as a line between 2 points.

Next, we could use pythagoras theorem to find the distance of the lines. Since the points are known, we could put it into the pythagoras equation a^2 + b^2 = c^2 to get the distance.

Furthermore, we can model the geometry objects as a weighted graph, where the intersection points are the vertices, the lane lines are the edges, and the lane distances are the weights. Since the lane has a direction, so the graph can be classified as a directed weighted graph.

After that, we want to find the shortest closed path that visits every edges at least once, which is similar to the concept of CPP. We don’t care about the exact path, only the total distances matters.

To reach the minimum theoretical distance, we are required to visit visit every edges exactly once. The big question, is such a path always possible on the graph? The graph has a unique properties where it is both directed and undirected at the same time. You must visit every lanes, and in that sense, it is a directed graph. However, it is always possible to travel forward and backward, and in that sense, it is an undirected graph. In this particular problem, travel forward and backward is mandatory for plowing, so it is safe to assume that we will eventually required to return to the previous vertices during the graph traversal, so we could say that such a path (visiting every edges exactly once) is always possible by visiting every unvisited vertices and returning when there are no such vertices. The minimum distance is equals to the total lane distances or equals to twice the amount of the total road distances.

After the minimum distance is known, divide it by the plowing speed to get the minimum time.

Algorithm

Both the pythagoras theorem, total distances, and total times calculation is a simple math formula. We just need to be careful with the rounding to avoid getting a wrong answer.

The time complexity of this solution is O({total roads}).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.time.Duration;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * 10203 - Snow Clearing
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1144
 */
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();

        final int totalTestCases = in.nextInt();
        in.nextLine();
        for (int caseId = 1; caseId <= totalTestCases; caseId++) {
            final Input input = nextInput(caseId, in);
            final Output output = process.process(input);
            printOutput(caseId, out, output);
        }

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

    private static Input nextInput(final int caseId, final Scanner in) {
        final Point hangar = new Point(in.nextLong(), in.nextLong());
        in.nextLine();

        final LinkedList<String[]> roadLines = new LinkedList<>();
        while (in.hasNextLong()) {
            final String line = in.nextLine();
            if (line.isEmpty()) break;
            roadLines.addLast(line.split(" "));
        }
        final Line[] roads = roadLines.stream()
            .map(roadLine -> new Line(
                    new Point(Long.parseLong(roadLine[0]), Long.parseLong(roadLine[1])),
                    new Point(Long.parseLong(roadLine[2]), Long.parseLong(roadLine[3]))
                )
            )
            .toArray(Line[]::new);

        final Input input = new Input();
        input.caseId = caseId;
        input.hangar = hangar;
        input.roads = roads;
        return input;
    }

    private static void printOutput(final int caseId, final PrintWriter out, final Output output) {
        if (caseId > 1) out.println();
        out.format("%d:%02d\n", output.hours, output.minutes);
    }
}

class Input {
    public int caseId;
    public Point hangar;
    public Line[] roads;
}

class Output {
    public int caseId;
    public long hours;
    public long minutes;
}

class Process {
    private static final double PLOWING_SPEED = 20;

    public Output process(final Input input) {
        final double totalDistances = Arrays.stream(input.roads)
            .mapToDouble(Line::distance)
            .sum();
        final double totalTimes = 2 * totalDistances * 60 / (PLOWING_SPEED * 1000);
        final Duration duration = Duration.ofMinutes(Math.round(totalTimes));

        final Output output = new Output();
        output.caseId = input.caseId;
        output.hours = duration.toHours();
        output.minutes = duration.minusHours(output.hours).toMinutes();
        return output;
    }
}

class Line {
    public final Point a;
    public final Point b;

    public Line(final Point a, final Point b) {
        this.a = a;
        this.b = b;
    }

    public double distance() {
        final long dx = Math.abs(a.x - b.x);
        final long dy = Math.abs(a.y - b.y);

        return Math.sqrt((dx * dx) + (dy * dy));
    }
}

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

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