OptiBus problem solver

Output

  |6:30|6:45|7:00|7:15|7:30|7:45|8:00|8:15|8:30|8:45|9:00|9:15|9:30|9:45|10:00|
01| 12 | 12 | 12 | 12 |  7 |  7 |  7 |  7 |  6 |  6 |  6 |  6 |    |    |    |
02| 15 | 15 | 15 | 15 |    | 10 | 10 | 10 | 10 |    |  9 |  9 |  9 |  9 |    |
03|    |    |  1 |  1 |  1 |  1 | 16 | 16 | 16 | 16 |  5 |  5 |  5 |  5 |    |
04|    |    |  4 |  4 |  4 |  4 |  8 |  8 |  8 |  8 |    |    |    |    |    |
05|    |    |    | 11 | 11 | 11 | 11 | 13 | 13 | 13 | 13 |    |    |    |    |
06|    |    |    | 14 | 14 | 14 | 14 |    |    |    |    |    |    |    |    |
07|    |    |    |    |  2 |  2 |  2 |  2 | 17 | 17 | 17 | 17 |    |    |    |
08|    |    |    |    |  3 |  3 |  3 |  3 |free|    | 18 | 18 | 18 | 18 |    |

package.kt

package com.yoavst.kotlin

import java.util.*

public fun main(args: Array<String>) {
    var linesSorted = lines.sortBy { it.startTime }
    if (linesSorted.size() != 0) {
        val buses = ArrayList<Bus>()

        // Step 1:
        var firstHour = lines.first().startTime
        var count = 0
        for (line in linesSorted) {
            if (firstHour == line.startTime) {
                buses.add(Bus(buses.size() + 1).add(line))
                count++
            } else break
        }
        linesSorted = linesSorted.subList(count, linesSorted.size())
        // Step 2:
        var problematicLines = ArrayList<Line>()
        lines@ for (line in linesSorted) {
            var problematic = false
            for (bus in buses) {
                if (bus.lastTime == line.startTime && bus in line) {
                    bus.add(line)
                    continue@lines
                } else if (bus.lastTime < line.startTime) problematic = true
            }
            if (problematic)
                problematicLines.add(line)
            else buses.add(Bus(buses.size() + 1).add(line))
        }
        // Step 3:
        while (problematicLines.size() > 0) {
            val bestLine = (problematicLines map { it to optimal(buses, it) } minBy { it.second.first })!!
            if (bestLine.second.first != -1) {
                val bus = buses[bestLine.second.second]
                if (bestLine.second.third) {
                    bus.add(freeLine(bus.lastTime, bus.currentDest!!, bestLine.first.start))
                }
                bus.add(bestLine.first)
                problematicLines.remove(bestLine.first)
            } else throw IllegalArgumentException()
        }

        // Step 4: Print it
        val gap = "    "
        print("  |")
        for (i in 0..14) {
            print(t(i) + '|')
        }
        buses.forEach { bus ->
            println()
            print(bus.id.wrap() + "|")
            for (i in 0..14) {
                print(center(bus.getLineIn(i) ?: gap) + "|")
            }
        }
    }
}

fun optimal(buses: List<Bus>, line: Line): Triple<Int, Int, Boolean> {
    var optimalScore: Int = Int.MAX_VALUE
    var optimalPosition: Int = -1
    var doesNeedFreePass: Boolean = false
    buses.forEachIndexed { position, bus ->
        val score: Int
        var freePass: Boolean = false
        if (bus in line) {
            if (line.startTime - bus.lastTime >= 0)
                score = (line.startTime - bus.lastTime) * 2
            else score = -1
        } else {
            if (line.startTime - (bus.lastTime + 1) >= 0) {
                score = 8 + (line.startTime - (bus.lastTime + 1))
                freePass = true
            } else score = -1
        }
        if (score != -1 && score < optimalScore) {
            doesNeedFreePass = freePass
            optimalPosition = position
            optimalScore = score
        }
    }
    return Triple(optimalScore, optimalPosition, doesNeedFreePass)
}

enum class Dest {
    A, B, C, D
}

data class Line(public val id: String, public val startTime: Int, public val endTime: Int, public val start: Dest, public val end: Dest) {
    override fun toString(): String {
        return "Line $id :: ${t(startTime)} -> ${t(endTime)} :: $start -> $end"
    }

    public fun contains(bus: Bus): Boolean {
        return bus.currentDest == null || bus.currentDest == start
    }
}

class Bus(public val id: Int) {
    public val lines: MutableList<Line> = ArrayList()

    public fun add(line: Line): Bus {
        lines.add(line)
        return this
    }

    public fun getLineIn(time: Int): String? {
        for (it in lines) {
            if (it.startTime <= time && it.endTime > time) return it.id
        }
        return null
    }

    public val currentDest: Dest?
        get() {
            return lines.lastOrNull()?.end
        }
    public val lastTime: Int
        get() {
            return lines.lastOrNull()?.endTime ?: 0
        }
}

fun hourLine(id: Int, startHour: Int, start: Dest, end: Dest): Line = Line(id.toString(), startHour, startHour + 4, start, end)
fun freeLine(startHour: Int, start: Dest, end: Dest): Line = Line("free", startHour, startHour + 1, start, end)

val lines: List<Line> = listOf(
        hourLine(1, t("7:00"), Dest.B, Dest.A),
        hourLine(2, t("7:30"), Dest.B, Dest.A),
        hourLine(3, t("7:30"), Dest.B, Dest.C),
        hourLine(4, t("7:00"), Dest.B, Dest.C),
        hourLine(5, t("9:00"), Dest.B, Dest.C),
        hourLine(6, t("8:30"), Dest.B, Dest.A),
        hourLine(7, t("7:30"), Dest.C, Dest.B),
        hourLine(8, t("8:00"), Dest.C, Dest.B),
        hourLine(9, t("9:00"), Dest.C, Dest.B),
        hourLine(10, t("7:45"), Dest.D, Dest.C),
        hourLine(11, t("7:15"), Dest.D, Dest.C),
        hourLine(12, t("6:30"), Dest.D, Dest.C),
        hourLine(13, t("8:15"), Dest.C, Dest.D),
        hourLine(14, t("7:15"), Dest.C, Dest.D),
        hourLine(15, t("6:30"), Dest.C, Dest.D),
        hourLine(16, t("8:00"), Dest.A, Dest.B),
        hourLine(17, t("8:30"), Dest.A, Dest.B),
        hourLine(18, t("9:00"), Dest.A, Dest.B)
)

fun t(time: String): Int {
    val data = time.split(':') map { it.toInt() }
    return (data[0] - 6) * 4 + (data[1] / 15) - 2 // - 30 minutes, since it start on 6:30
}

fun Int.wrap(): String {
    return if (this < 10) return "0" + toString()
    else toString()
}

fun center(text: String): String {
    when (text.length()) {
        0 -> return "    "
        1 -> return "  $text "
        2 -> return " $text "
        3 -> return " $text"
        4 -> return text
        else -> throw IllegalArgumentException()
    }
}

fun t(time: Int): String {
    val data = intArrayOf(time / 4, time % 4)
    if (data[1] >= 2) return (data[0] + 6 + 1).toString() + ":" + if (data[1] == 2) "00" else "15"
    else return (data[0] + 6).toString() + ":" + if (data[1] == 1) "45" else "30"
}