Skip to content

Instantly share code, notes, and snippets.

@lgtout lgtout/HomeGuesser.groovy
Last active Mar 10, 2017

Embed
What would you like to do?
Home location guesser for Sense360
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
}
}
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()
}
}
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()}"
}
@lgtout

This comment has been minimized.

Copy link
Owner Author

commented Mar 10, 2017

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.