Home location guesser for Sense360

HomeGuesser.groovy

package com.sense360

class HomeGuesser {

    /**
     * A location, consisting of latitude and longitude.
     * Rounds coordinates provided to 3 decimal places.
     * Compares by value, not reference.
     */
    static class Location {

        final Float latitude
        final Float longitude

        Location() {
            latitude = null
            longitude = null
        }

        Location(float latitude, float longitude) {
            this.latitude = Math.round(latitude * 1000) / 1000F
            this.longitude = Math.round(longitude * 1000) / 1000F
        }

        final static NONE = new Location()

        boolean equals(o) {
            if (this.is(o)) return true
            if (!(o instanceof Location)) return false

            Location location = (Location) o

            if (Float.compare(location.latitude, latitude) != 0) return false
            if (Float.compare(location.longitude, longitude) != 0) return false

            return true
        }

        int hashCode() {
            int result
            result = (latitude != +0.0f ? Float.floatToIntBits(latitude) : 0)
            result = 31 * result + (longitude != +0.0f ? Float.floatToIntBits(longitude) : 0)
            return result
        }

    }


    /**
     * A visit, with location and arrival and departure times.
     */
    static class Visit {

        float latitude
        float longitude
        Date arrival
        Date departure

        Visit(float latitude, float longitude, Date arrival, Date departure) {
            this.latitude = latitude
            this.longitude = longitude
            this.arrival = arrival
            this.departure = departure
        }

    }

    /**
     * An interval, with start and end dates.
     */
    static class Interval {

        Date start
        Date end

        Interval(Date start, Date end) {
            this.start = start
            this.end = end
        }

    }

    /**
     * The start of the 8pm - 8am window, on the
     * same day as a visit's arrival.  This may be
     * rolled back by one day later in processing.
     *
     * @param visitStart A visit's arrival.
     * @return The start of the 8pm - 8am window.
     */
    static Date getWindowStart(Date visitStart) {
        def windowStart = Calendar.getInstance()
        windowStart.setTime(visitStart)
        windowStart.set(Calendar.HOUR_OF_DAY, 20)
        windowStart.set(Calendar.MINUTE, 0)
        windowStart.set(Calendar.SECOND, 0)
        windowStart.getTime()
    }

    /**
     * The end of the 8pm - 8am window, on the day
     * following a visit's arrival.  This may be
     * rolled back by one day later in processing.
     *
     * @param visitStart A visit's arrival.
     * @return The end of the 8pm - 8am window.
     */
    static Date getWindowEnd(Date visitStart) {
        def windowEnd = Calendar.getInstance()
        windowEnd.setTime(visitStart)
        windowEnd.add(Calendar.HOUR_OF_DAY, 12)
        windowEnd.getTime()
    }

    /**
     * Rolls back the 8pm - 8am window by one day if
     * the visit arrival time is before the window's
     * start.
     *
     * @param interval An 8pm - 8am window.
     * @param visitStart A visit's arrival.
     * @return The same 8pm - 8am window, or the prior day's.
     */
    static Interval rollBackIfVisitStartsBeforeInterval(
            Interval interval, Date visitStart) {
        if (visitStart.before(interval.start)) {
            def calendar = Calendar.getInstance()
            calendar.setTime(interval.start)
            calendar.roll(Calendar.DATE, false)
            def start = calendar.getTime()
            calendar.setTime(interval.end)
            calendar.roll(Calendar.DATE, false)
            def end = calendar.getTime()
            return new Interval(start, end)
        }
        return interval
    }

    /**
     * Rolls an 8pm - 8am window forward by 24 hours.
     *
     * @param interval An 8pm - 8am window.
     * @return An 8pm - 8am window, rolled forward by
     * a day.
     */
    static Interval rollForward(Interval interval) {
        def calendar = Calendar.getInstance()
        calendar.setTime(interval.start)
        calendar.roll(Calendar.DATE, true)
        def start = calendar.getTime()
        calendar.setTime(interval.end)
        calendar.roll(Calendar.DATE, true)
        def end = calendar.getTime()
        new Interval(start, end)
    }

    /**
     * Milliseconds in a minute.
     */
    static final millisecondsPerMinute = 60000

    /**
     * Milliseconds in an hour.
     */
    static final int millisecondsPerHour = millisecondsPerMinute * 60

    /**
     * Milliseconds in 30 hours.
     */
    static final int minimumIntervalSumRequired = millisecondsPerHour * 30

    /**
     * Entry point.
     * Guesses home location, if possible.
     *
     * @param visits A {@code List} of {@code Visit}s
     * @return If a valid guess is possible, a {@code Location} with
     * rounded coordinates.  Otherwise {@code Location.NONE}.
     */
    static Location guess(List<Visit> visits){
        def home = Location.NONE

        // Create a map of location to intervals spent in
        // each 8pm - 8am window.

        def locationOverlaps = new HashMap<Location, List<Interval>>()
        visits.each { Visit visit ->
            def location = new Location(visit.latitude, visit.longitude)
            def overlaps = locationOverlaps.get(location)
            if (overlaps == null) {
                overlaps = new ArrayList<Interval>()
                locationOverlaps.put(location, overlaps)
            }
            def window = new Interval(
                    getWindowStart(visit.arrival),
                    getWindowEnd(visit.arrival))
            rollBackIfVisitStartsBeforeInterval(
                    window, visit.arrival)
            while (true) {
                def overlapStart = (visit.arrival.before(window.start)
                        ? window.start : visit.arrival)
                def overlapEnd = (visit.departure.before(window.end)
                        ? visit.departure : window.end)
                if (overlapStart.before(overlapEnd)) {
                    overlaps << new Interval(overlapStart, overlapEnd)
                }
                window = rollForward(window)
                if (window.start.after(visit.departure)) break
            }
        }

        // Reduce our map of location to intervals to one of
        // location to total duration spent in each location.
        // While we're at it, filter out any locations where
        // duration spent at a location is not >= 30 hours.

        def locationOverlapDurations = new HashMap<Location, Integer>()
        locationOverlaps.each {
            Location location, List<Interval> overlaps ->
                def sumMinutes = (int) overlaps.sum {
                    Interval interval ->
                        ((interval.end.getTime() -
                                interval.start.getTime()) /
                                millisecondsPerMinute)
                }
                if (sumMinutes > minimumIntervalSumRequired) {
                    locationOverlapDurations.put(location, sumMinutes)
                }
        }

        // If there are any locations left after filtering,
        // sort our map of location to total duration, in
        // ascending order.  The last entry is the most
        // likely candidate for the home location.

        if (!locationOverlapDurations.isEmpty()) {
            def sortedLocationOverlapDurations =
                    locationOverlapDurations.sort { a, b -> a.value <=> b.value }
            home = sortedLocationOverlapDurations.keySet().last()
        }

        home
    }

}

HomeGuesserSpec.groovy

package com.sense360

import spock.lang.Specification
import spock.lang.Unroll
import com.sense360.HomeGuesser.Visit
import com.sense360.HomeGuesser.Location

class HomeGuesserSpec extends Specification {

    @Unroll
    'guess home - static cases'(
            List<Visit> visits,
            Location expected) {

        expect:
        HomeGuesser.guess(visits) == expected

        where:
        [visits, expected] << [
                {
                    // NOTE: 12/0 means 12hr during 8pm - 8am,
                    // 0hr during 8am - 8pm

                    // 12/0 at one location
                    def start = new Date(2017, 3, 1, 20, 0)
                    Calendar calendar = Calendar.getInstance()
                    calendar.setTime(start)
                    def end = calendar.roll(Calendar.DATE, true)
                    def home = Location.NONE
                    [new Visit(1, 2, start, end), home]
                }(),
                {
                    // 40/0 at one location
                    // TODO Incomplete
                    def start = new Date(2017, 3, 1, 20, 0)
                    Calendar calendar = Calendar.getInstance()
                    calendar.setTime(start)
                    def end = calendar.roll(Calendar.DATE, true)
                    def home = Location.NONE
                    [new Visit(1, 2, start, end), home]
                }(),
                {
                    // 30/0 hours at one location between 8pm and 8am
                    // over 4 days in a single visit
                    def start = new Date(2017, 3, 1, 20, 0)
                    Calendar calendar = Calendar.getInstance()
                    calendar.setTime(start)
                    def additionalHours = roundUp(1, 30 / 8 * 24 * 10)
                    calendar.roll(Calendar.HOUR_OF_DAY, additionalHours)
                    def end = calendar.getTime()
                    def home = new Location(1,2)
                    [new Visit(1, 2, start, end), home]
                }(),
                {
                    // 30 hours at one location between 8pm and 8am
                    // over 4 days in multiple visits
                    // TODO Incomplete
                    def home = new Location(1,2)
                    def start = new Date(2017, 3, 1, 20, 0)
                    Calendar calendar = Calendar.getInstance()
                    calendar.setTime(start)
                    def additionalHours = roundUp(1, 30 / 8 * 24 * 10)
                    calendar.roll(Calendar.HOUR_OF_DAY, additionalHours)
                    def end = calendar.getTime()
                    [new Visit(home.latitude, home.longitude, start, end), home]
                }
        ]
    }

    //http://stackoverflow.com/a/4561783/369722
    private static int roundUp(int n, BigDecimal m) {
        return m.setScale(n, BigDecimal.ROUND_HALF_UP).toInteger()
    }

}

scratch.groovy

def visitStart = Calendar.getInstance()
visitStart.set(Calendar.HOUR_OF_DAY, 20)
visitStart.set(Calendar.MINUTE, 0)
visitStart.set(Calendar.SECOND, 0)
println visitStart.getTime()
def visitStartTime = visitStart.getTime()

def visitEnd = (Calendar) visitStart.clone()
visitEnd.roll(Calendar.DATE, true)
visitEnd.set(Calendar.HOUR_OF_DAY, 8)
println visitEnd.getTime()
def visitEndTime = visitEnd.getTime()

def windowStart = Calendar.getInstance()
windowStart.setTime(visitStartTime)
windowStart.set(Calendar.HOUR_OF_DAY, 20)
windowStart.set(Calendar.MINUTE, 0)
windowStart.set(Calendar.SECOND, 0)
println windowStart.getTime()

def windowEnd = Calendar.getInstance()
windowEnd.setTime(visitEndTime)
windowEnd.add(Calendar.HOUR_OF_DAY, 12)
println windowEnd.getTime()

if (visitStart.before(windowStart)) {
    windowStart.roll(Calendar.DATE, false)
    windowEnd.roll(Calendar.DATE, false)
}

println "windowStart ${windowStart.getTime()}"
println "windowEnd ${windowEnd.getTime()}"

def overlaps = []

while (true) {
    def overlapStart = (Calendar) (visitStart.before(windowStart)
            ? windowStart : visitStart).clone()
    def overlapEnd = (Calendar) (visitEnd.before(windowEnd)
            ? visitEnd : windowEnd).clone()
    print(overlapStart, overlapEnd)
    if (overlapStart.before(overlapEnd))
        overlaps << [overlapStart, overlapEnd]
    windowStart.roll(Calendar.DATE, true)
    windowEnd.roll(Calendar.DATE, true)
    if (windowStart.after(visitEnd)) break
}

def print(Calendar start, Calendar end) {
    println "start ${start.getTime()}"
    println "end ${end.getTime()}"
}

overlaps.each { List<Calendar> overlap ->
    println "${overlap[0].getTime()} to ${overlap[1].getTime()}"
}

All I had time to run before the 4 hrs were up was scratch.groovy. I used that script to work out my idea for rolling windows of 8pm - 8am windows. And to figure out how to use and manipulate Date and Calendar.

Later, after the 4 hours were up, I spent about an hour on HomeGuesserSpec.groovy. My intent was to use it to do some initial verification of the solution using hardcoded test inputs, before attempting randomly generated inputs. But it had been a rollercoaster of a day, and I ran out of steam.

So instead, I switched to adding comments to HomeGuesser.groovy. The solution compiles OK but I doubt it can be executed without runtime exceptions. As such, assessing correctness will rely on reading the code. I hope the comments make that effort at least a little easier.