Ski in Singapore problem from: http://geeks.redmart.com/2015/01/07/skiing-in-singapore-a-coding-diversion/

SkiInSingapore.kt

@file:Suppress("NOTHING_TO_INLINE")

import java.io.BufferedReader
import java.io.File
import java.io.InputStream
import java.io.InputStreamReader
import kotlin.system.measureTimeMillis

// Kotlin 1.2.0 (probably 1.6.0 will work as well)
//
// This process encodes each path step as:
//    altitude :: distance from end of path :: delta altitude to end of path :: processed state :: winning direction
//
// We never process a node more than once, it is calculated from that point down to the bottom of its
// possible paths, and records the values upwards from the end as it exits recursion.
//
// Therefore if we intersect with a node that is aready solved, we just inherit its values and
// use those to calculate the current node.  If we encounter a node that is pending, we bounce off.
// Although technically we could never encounter a pending node in a depth first search since it would
// be our own path and we cannot go back uphill to those nodes.
//
// The sample encoded would look something like:
//
//  4:1:2:T 8:4:7:T 7:1:4:T 3:0:0:T
//  2:0:0:T 5:3:4:T 9:4:8:T 3:0:0:T
//  6:3:5:T 3:2:2:T 2:1:1:T 5:2:4:T
//  4:0:0:T 4:3:3:T 1:0:0:T 6:3:5:T
//
// TIME complexity is O(n*m)
// SPACE complexity is O(n*m)
//
// space could be reduced to using an 2D array of longs with encoding as:
//           11 bits altitude
//           32 bits distance to end
//           11 bits drop to end
//            2 bits processed
//            8 bits delta (not required, just makes collection of path faster)
//          ---
//           64 bits
// this would improve data locality and performance as well.
//
// and also by reducing the object allocations for tracking points (MapPoint could be primitive y,x)
//

typealias Mountain = Array<Array<PathStep>>

data class MapDelta(val y: Int, val x: Int)
data class MapPoint(val y: Int, val x: Int) {
    fun apply(delta: MapDelta): MapPoint = MapPoint(y + delta.y, x + delta.x)
}

val ALLOWED_SKI_TURNS = arrayOf(MapDelta(-1, 0), MapDelta(0, -1), MapDelta(+1, 0), MapDelta(0, +1))


// extension functions to make other code more readable

inline operator fun Mountain.contains(point: MapPoint) = point.y in this.indices && point.x in this[0].indices
inline operator fun Mountain.get(point: MapPoint) = this[point.y][point.x]

// encoding of our map

enum class StepState { untouched, pending, solved }

data class PathStep(val altitude: Short,
                    var distanceToEnd: Int = 0,
                    var dropToEnd: Short = 0,
                    var state: StepState = StepState.untouched,
                    var nextStep: PathStep? = null) {
    val pathLength: Int get() = distanceToEnd + 1

    inline fun isBestedBy(other: PathStep): Boolean {
        val stepsWithNeighbor = other.distanceToEnd + 1
        val dropWithNeighbor = (altitude - other.altitude + other.dropToEnd).toShort()
        return ((distanceToEnd == stepsWithNeighbor && dropWithNeighbor > dropToEnd)
                || distanceToEnd < stepsWithNeighbor)
    }
}

data class SkiSlope(val startAltitude: Short, val endAltitude: Short, val path: List<Short>) {
    val altitudeDelta: Short = (startAltitude - endAltitude).toShort()
    val pathLength: Int = path.size
}

fun findLongestSkiSlope(mapGrid: Mountain): SkiSlope {

    fun visitMapPoint(currentPoint: MapPoint, currentStep: PathStep): PathStep? {
        if (currentStep.state == StepState.solved) return currentStep
        assert (currentStep.state != StepState.pending) {
            "we should never be able to reach a pending node, that would mean skiing uphill" 
        }

        currentStep.state = StepState.pending
        everyTurn@ for (delta in ALLOWED_SKI_TURNS) {
            val nextPoint = currentPoint.apply(delta)
            if (nextPoint !in mapGrid) continue@everyTurn
            val nextStep = mapGrid[nextPoint]
            if (currentStep.altitude <= nextStep.altitude) continue@everyTurn
            visitMapPoint(nextPoint, nextStep)?.also { validStep ->
                if (currentStep.isBestedBy(validStep)) {
                    currentStep.distanceToEnd = validStep.distanceToEnd + 1
                    currentStep.dropToEnd = (currentStep.altitude - validStep.altitude + validStep.dropToEnd).toShort()
                    currentStep.nextStep = validStep
                }
            }
        }
        currentStep.state = StepState.solved
        return currentStep
    }

    fun visitMapPoint(currentPoint: MapPoint): PathStep? {
        if (currentPoint !in mapGrid) return null
        return visitMapPoint(currentPoint, mapGrid[currentPoint])
    }

    fun calculateAllPathsAndFindBestStart(): PathStep {
        var topOfTheSlope: PathStep = mapGrid[0][0]
        mapGrid.indices.forEach { py ->
            mapGrid[py].indices.map { px -> MapPoint(py, px) }.forEach { point ->
                visitMapPoint(point)?.also { currentStep ->
                    if (topOfTheSlope.isBestedBy(currentStep)) {
                        topOfTheSlope = currentStep
                    }
                }
            }
        }
        return topOfTheSlope
    }

    // process the mountain in an optimal manner
    val topOfTheSlope = calculateAllPathsAndFindBestStart()

    // traverse the best path to generate results
    val finalSkiPath = generateSequence(topOfTheSlope) { it.nextStep }
            .map { it.altitude }.toList()

    val result = SkiSlope(finalSkiPath.first(), finalSkiPath.last(), finalSkiPath)

    // assert known values to check our code
    assert(topOfTheSlope.altitude == result.startAltitude) { "Mismatch altitude" }
    assert(topOfTheSlope.pathLength == result.pathLength) { "Mismatch path length" }
    assert(topOfTheSlope.dropToEnd == result.altitudeDelta) { "Mismatch altitude delta" }

    return result
}

fun parseMountain(data: InputStream): Mountain {
    // TODO: assumes input data is well formatted
    return BufferedReader(InputStreamReader(data)).use { stream ->
        val (_, height) = stream.readLine().split(' ').map(String::toInt)
        Array(height) {
            stream.readLine().split(' ').map(String::toShort).map { PathStep(it) }.toTypedArray()
        }
    }
}

fun main(args: Array<String>) {
    fun runTestOnData(data: InputStream, title: String) {
        println()
        println("Running test '${title}':")
        val smallTime = measureTimeMillis {
            val results = findLongestSkiSlope(parseMountain(data))
            println("Starting Altitude: ${results.startAltitude}")
            println("Path length:       ${results.pathLength}")
            println("Altitude Delta:    ${results.altitudeDelta}")
            println("Path:\n${results.path}")
        }
        println("ran in ${smallTime}ms")
        println()
    }

    val smallTest = """
                    4 4
                    4 8 7 3
                    2 5 9 3
                    6 3 2 5
                    4 4 1 6
                    """.trimIndent().trim()
    runTestOnData(smallTest.toByteArray().inputStream(), "Small 4x4 sample data")

    val inputFile = File(args[0])
    if (!inputFile.exists()) {
        throw IllegalArgumentException("Input file $inputFile does not exist!")
    }

    runTestOnData(inputFile.inputStream(), inputFile.toString())
}