Code for hashcode2018

copy.kt

package com.yoavst.testing

import java.io.File
import java.util.*
import kotlin.math.absoluteValue
import kotlin.math.max

interface Locatable {
    val x: Int
    val y: Int
}

data class Location(override val x: Int, override val y: Int) : Locatable {
    override fun toString(): String = "($x,$y)"
    companion object {
        val Zero = Location(0, 0)
    }
}

data class Trip(val id: Int, val start: Location, val end: Location, val startTime: Int, val finishTime: Int) {
    val distance = dist(start, end)
}

class Car(val id: Int, val rides: MutableList<Trip> = ArrayList(), var nextEndTime: Int = 0) : Locatable, Comparable<Car> {
    var location: Location = Location.Zero
    override val x: Int
        get() = location.x
    override val y: Int
        get() = location.y

    override fun equals(other: Any?): Boolean = other is Car && other.id == id
    override fun hashCode(): Int = id
    override fun compareTo(other: Car): Int = nextEndTime - other.nextEndTime
}

fun dist(loc1: Locatable, loc2: Locatable): Int = (loc1.x - loc2.x).absoluteValue + (loc1.y - loc2.y).absoluteValue

private var lastTime: Long = 0
fun tick(name: String) {
    val current = System.currentTimeMillis()
    if (lastTime == 0L) {
        println("Starting count: $name, Time now: $current")
    } else {
        println("$name, Time now: $current, Delta: ${current - lastTime}")
    }
    lastTime = current
}

fun main(args: Array<String>) {
    val start = System.currentTimeMillis()
    tick("Starting")
    val inFile = File("a.in")
    val outFile = File("a.out")
    inFile.reader().useLines { lines ->
        val iter = lines.iterator()
        val (r, c, f, n, b, t) = iter.next().split(" ")
        val carsCount = f.toInt()
        val bonus = b.toInt()
        val steps = t.toInt()
        val rides = n.toInt()
        val initialTrips: MutableList<Trip> = ArrayList(rides)
        for ((i, line) in iter.withIndex()) {
            val data = line.split(' ', limit = 6)
            initialTrips += Trip(i, Location(data[0].toInt(), data[1].toInt()), Location(data[2].toInt(), data[3].toInt()), data[4].toInt(), data[5].toInt())
        }
        tick("Loaded from file")

        val queue = PriorityQueue<Car>(carsCount)
        val cars = ArrayList<Car>(carsCount)
        repeat(carsCount) { id ->
            val car = Car(id)
            queue += car
            cars += car
        }
        tick("Loaded into the queue")

        val trips = filterImpossibleTrips(initialTrips, cars, 0, byEndTime = true, byBonus = false)
        tick("Filtered impossible trips")

        var currentTurn = 0
        var finishedYet = 1
        tick("Starting the fun")
        while (currentTurn < steps && cars.isNotEmpty() && trips.isNotEmpty()) {
            val car = queue.poll()
            currentTurn = car.nextEndTime

            finishedYet++
            if (finishedYet % 300 == 0) {
                tick("Reached: $finishedYet")
            }

            val ride = bestTripForCar(car, trips, currentTurn, bonus)
            if (ride != null) {
                assignRideToCar(car, ride, currentTurn)
                trips.remove(ride)
                queue += car
            }
        }

        tick("Done!")
        outFile.printWriter().use { writer ->
            for (car in cars) {
                writer.write(car.rides.size.toString())
                writer.write(" ")
                for (ride in car.rides) {
                    writer.write("${ride.id} ")
                }
                writer.println()
            }
        }
        tick("Realy really done!")
    }
    val end = System.currentTimeMillis()
    println("Total time: ${end - start}ms")
}

private fun points(loc: Locatable, trip: Trip, currentTurn: Int, bonus: Int): Int {
    val d = dist(loc, trip.start)
    if (d + trip.distance + currentTurn > trip.finishTime)
        return 0
    else if (d + currentTurn < trip.startTime)
        return bonus + trip.distance
    return trip.distance
}

private fun bestEndTime(loc: Locatable, trip: Trip, currentTurn: Int): Int = max(trip.startTime, currentTurn + dist(loc, trip.start)) + trip.distance

private fun bestTripForCar(car: Car, trips: List<Trip>, currentTurn: Int, bonus: Int): Trip? {
    val trip = trips.minBy { trip ->
        val points = points(car, trip, currentTurn, bonus)
        if (points == 0)
            Int.MAX_VALUE
        else
            score(bestEndTime(car, trip, currentTurn), points, currentTurn)
    }!!
    return trip.takeIf { points(car, it, currentTurn, bonus) > 0 }
}

private fun assignRideToCar(car: Car, ride: Trip, currentTurn: Int) {
    car.rides += ride
    car.nextEndTime = bestEndTime(car, ride, currentTurn)
    car.location = ride.end
}

private inline fun score(time: Int, points: Int, currentTurn: Int) = (time - currentTurn) - points

private fun filterImpossibleTrips(trips: List<Trip>, cars: List<Locatable>, currentTurn: Int, byEndTime: Boolean, byBonus: Boolean): MutableList<Trip> {
    val filtered = ArrayList<Trip>(trips.size)
    for (trip in trips) {
        val start = trip.start
        val distance = dist(cars.minBy { dist(it, start) }!!, start)
        if (byBonus && distance + trip.startTime > trip.finishTime)
            continue
        if (byEndTime && max(trip.startTime, currentTurn + distance) + trip.distance > trip.finishTime)
            continue
        filtered += trip
    }
    return filtered
}

operator fun <T> List<T>.component6(): T = get(5)

optimized.kt

package com.yoavst.testing

import java.io.File
import java.util.*
import kotlin.collections.ArrayList
import kotlin.math.absoluteValue
import kotlin.math.max

fun main(args: Array<String>) {
    val start = System.currentTimeMillis()
    tick("Starting")
    val inFile = File("a.in")
    val outFile = File("a.out")
    inFile.reader().useLines { lines ->
        val iterator = lines.iterator()
        val (_, _, f, n, b, t) = iterator.next().split(" ")
        val carsCount = f.toInt()
        val bonus = b.toInt()
        val steps = t.toInt()
        val rides = n.toInt()
        val trips: MutableList<Trip> = ArrayList(rides)
        for ((i, line) in iterator.withIndex()) {
            val data = line.split(' ', limit = 6)
            trips += Trip(i, data[0].toInt(), data[1].toInt(), data[2].toInt(), data[3].toInt(), data[4].toInt(), data[5].toInt())
        }
        tick("Loaded from file")

        val queue = PriorityQueue<Car>(carsCount)
        val cars = ArrayList<Car>(carsCount)
        repeat(carsCount) { id ->
            val car = Car(id)
            queue += car
            cars += car
        }
        tick("Loaded into the queue")

        loop(queue, trips, steps, bonus)
        val end = System.currentTimeMillis()
        println("Total logic time: ${end - start}ms")
        outFile.printWriter().use { writer ->
            for (car in cars) {
                writer.write(car.rides.size.toString())
                writer.write(" ")
                for (ride in car.rides) {
                    writer.write("${ride.id} ")
                }
                writer.println()
            }
        }
        tick("Done writing!")
    }
    val end = System.currentTimeMillis()
    println("Total time: ${end - start}ms")
}

private fun loop(queue: PriorityQueue<Car>, trips: MutableList<Trip>, steps: Int, bonus: Int) {
    var currentTurn = 0
    var finishedYet = 1
    tick("Starting the fun")
    while (currentTurn < steps && trips.isNotEmpty()) {
        val car = queue.poll()
        currentTurn = car.nextEndTime

        finishedYet++
        if (finishedYet % 300 == 0) {
            tick("Reached: $finishedYet")
        }

        val ride = bestTripForCar(car, trips, currentTurn, bonus)
        if (ride != null) {
            assignRideToCar(car, ride, currentTurn)
            trips.removeAt(lastIndex)
            queue += car
        }
    }

    tick("Done!")
}

private class Trip(@JvmField val id: Int, @JvmField val startX: Int, val startY: Int, @JvmField val endX: Int, @JvmField val endY: Int, @JvmField val startTime: Int, @JvmField val finishTime: Int) {
    @JvmField
    val distance = dist(startX, startY, endX, endY)

    override fun equals(other: Any?): Boolean = other is Trip && other.id == id
    override fun hashCode(): Int = id
}

private class Car(@JvmField val id: Int, @JvmField val rides: MutableList<Trip> = ArrayList(), @JvmField var nextEndTime: Int = 0) : Comparable<Car> {
    @JvmField
    var x: Int = 0
    @JvmField
    var y: Int = 0

    override fun equals(other: Any?): Boolean = other is Car && other.id == id
    override fun hashCode(): Int = id
    override fun compareTo(other: Car): Int = nextEndTime - other.nextEndTime
}

private fun dist(car: Car, endX: Int, endY: Int): Int = (car.x - endX).absoluteValue + (car.y - endY).absoluteValue
private fun dist(startX: Int, startY: Int, endX: Int, endY: Int) = (startX - endX).absoluteValue + (startY - endY).absoluteValue

private fun points(car: Car, trip: Trip, currentTurn: Int, bonus: Int): Int = points(dist(car, trip.startX, trip.startY), trip, currentTurn, bonus)
private fun points(dist: Int, trip: Trip, currentTurn: Int, bonus: Int): Int {
    if (dist + trip.distance + currentTurn > trip.finishTime)
        return 0
    else if (dist + currentTurn < trip.startTime)
        return bonus + trip.distance
    return trip.distance
}

private fun bestEndTime(dist: Int, trip: Trip, currentTurn: Int): Int = max(trip.startTime, currentTurn + dist) + trip.distance
private fun bestEndTime(car: Car, trip: Trip, currentTurn: Int): Int = bestEndTime(dist(car, trip.startX, trip.startY), trip, currentTurn)

private fun score(time: Int, points: Int, currentTurn: Int) = (time - currentTurn) - points

private var lastIndex = 0
@Suppress("UseWithIndex")
private fun bestTripForCar(car: Car, trips: MutableList<Trip>, currentTurn: Int, bonus: Int): Trip? {
    var minIndex = 0
    var minItem = trips.first()
    var minScore = Int.MAX_VALUE
    // We want the index of delete optimization, and withIndex() allocate iterator + unboxing
    var i = 0
    for (trip in trips) {
        val dist = dist(car, trip.startX, trip.startY)
        val points = points(dist, trip, currentTurn, bonus)
        val score = if (points == 0) Int.MAX_VALUE else score(bestEndTime(dist, trip, currentTurn), points, currentTurn)
        if (score < minScore) {
            minIndex = i
            minItem = trip
            minScore = score
        }
        i++
    }

    lastIndex = minIndex
    return minItem.takeIf { points(car, it, currentTurn, bonus) > 0 }
}

private fun assignRideToCar(car: Car, ride: Trip, currentTurn: Int) {
    car.rides += ride
    car.nextEndTime = bestEndTime(car, ride, currentTurn)
    car.x = ride.endX
    car.y = ride.endY
}

private operator fun <T> List<T>.component6(): T = get(5)

private var lastTime: Long = 0
fun tick(name: String) {
    val current = System.currentTimeMillis()
    if (lastTime == 0L) {
        println("Starting count: $name, Time now: $current")
    } else {
        println("$name, Time now: $current, Delta: ${current - lastTime}")
    }
    lastTime = current
}

original.py

import queue as Q
import time as t

R = C = F = N = B = T = None

last = 0


def tick(name):
    global last
    current = t.time()
    if last == 0:
        print("Starting count:", name, "Time now:", current)
    else:
        print(name, "Time now:", current, "Delta:", current - last)
    last = current


class Location(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.loc = self

    def __str__(self):
        return "(" + str(self.x) + "," + str(self.y) + ")"


class Trip(object):
    def __init__(self, id, a, b, x, y, s, f):
        self.id = id
        self.start = Location(a, b)
        self.end = Location(x, y)
        self.startTime = s
        self.finishTime = f
        self.distance = dist(self.start, self.end)


class Car(object):
    def __init__(self, id, loc):
        self.id = id
        self.loc = loc
        self.rides = []
        self.next_end_time = 0

    def __lt__(self, other):
        return self.next_end_time < other.next_end_time


def main():
    global Rows, Columns, Cars, Bonus, Steps
    tick("Starting")
    in_file = 'a.in'
    out_file = 'a.out'

    trips = []
    with open(in_file) as f:
        for i, line in enumerate(iter(f)):
            line = line.strip()
            if i == 0:
                r, c, f, n, b, t = list(map(int, line.split()))
                Rows = r
                Columns = c
                Cars = f
                Rides = n
                Bonus = b
                Steps = t
            else:
                cur_trip = Trip(i - 1, *list(map(int, line.split())))
                trips.append(cur_trip)

    tick("Loaded from file")
    cars = [Car(i, Location(0, 0)) for i in range(Cars)]
    tick("Created cars array")
    ### LOGIC GOES HERE ###
    trips = filter_impossible_trips(trips, cars, 0, by_endtime=True, by_bouns=False)
    tick("Filtered impossible trips")
    carsQueue = Q.PriorityQueue()
    for car in cars:
        carsQueue.put(car)

    currentTurn = 0
    finishTime = 1
    tick("Starting the fun")
    while currentTurn < Steps and not carsQueue.empty() and len(trips):
        car = carsQueue.get()
        currentTurn = car.next_end_time
        finishTime += 1
        if finishTime % 300 == 0:
            tick("Reached: " + str(finishTime))
        ride = best_trip_for_car(car, trips, currentTurn, Bonus)
        if ride:
            assign_ride_to_car(car, ride, currentTurn)
            trips.remove(ride)
            carsQueue.put(car)

    tick("Done")
    allocation = (cars[i].rides for i in range(Cars))
    tick("Really done")
    ### LOGIC ENDS HERE ###

    with open(out_file, 'w') as f:
        for route in allocation:
            f.write('{} '.format(len(route)))
            for ride in route:
                f.write('{} '.format(ride))
            f.write('\n')
    tick("Done writing to file")


def can_get_points(loc, trip, current_turn, bonus):
    d = dist(loc, trip.start)
    if d + trip.distance + current_turn > trip.finishTime:
        return 0
    if d + current_turn < trip.startTime:
        return bonus + trip.distance
    return trip.distance


def dist(loc1, loc2):
    return abs(loc1.loc.x - loc2.loc.x) + abs(loc1.loc.y - loc2.loc.y)


def best_end_time(car, trip, now_time):
    return max(trip.startTime, now_time + dist(car.loc, trip.start)) + trip.distance


def best_trip_for_car(car, trips, now_time, bonus):
    best_trip = trips[0]
    i = 0
    current_value = 280341289056
    for trip in trips:
        p = can_get_points(car, trip, now_time, bonus)
        if p != 0:
            time = best_end_time(car, trip, now_time)
            val = value(time, p, now_time)
            if val < current_value:
                current_value = val
                best_trip = trip
        i += 1
    if not can_get_points(car, best_trip, now_time, bonus):
        return None
    return best_trip


def value(time, score, now_time):
    return (time - now_time) - score


def assign_ride_to_car(car, trip, now_time):
    car.rides.append(trip.id)
    car.next_end_time = best_end_time(car, trip, now_time)
    car.loc = trip.end


def filter_impossible_trips(trips, cars, current_turn, by_endtime=True, by_bouns=False):
    filtered = []
    for trip in trips:
        d_from_vehicles = min(dist(trip.start, car.loc) for car in cars)
        if by_bouns and d_from_vehicles > (trip.startTime - current_turn):
            continue
        if by_endtime and (trip.distance + trip.startTime > trip.finishTime) or (
                d_from_vehicles + trip.distance + current_turn > trip.finishTime):
            continue
        filtered.append(trip)
    return filtered


if __name__ == '__main__':
    before = t.time()
    main()
    after = t.time()
    print("Total:", after - before)