DroneSeed challenge

droneseed.ts

const MIN_HEIGHT = 4
const MAX_HEIGHT = 8
const HEIGHT_DELTA = MAX_HEIGHT - MIN_HEIGHT

interface Path {
    startIndex: number
    startHeight: number
    endIndex: number
    endHeight: number
}

const planWayPoints = (dsm: number[]): number[] => {
    // Sanity check
    if (!dsm || dsm.length < 2) {
        throw new Error(`Invalid dsm ${dsm}`)
    }

    const segmentPossibilities: Path[][] = []
    const lastIndex = dsm.length - 1
    let startIndex = 0

    // Optimize for least amount of wayPoints
    while (startIndex < lastIndex) {
        // All longest paths will share same endIndex
        const paths = getLongestPaths(dsm, startIndex)
        startIndex = paths[0].endIndex
        segmentPossibilities.push(paths)
    }

    // Get low altitude waypoints from the segments
    const wayPoints = getLowAltitudeWayPoints(dsm, segmentPossibilities)

    // Fill start and end
    return wayPoints
}

// segmentPossibilities are sorted by altitude, so we just need to pick first path that connects all the segments
const getLowAltitudeWayPoints = (dsm: number[], segmentPossibilities: Path[][], index = 0): number[] => {
    const segments = segmentPossibilities[index]

    for (let segment of segments) {
        let connectedSegments = getConnectedSegments(segment, segmentPossibilities, index + 1)
        if (connectedSegments) {
            const wayPoints = new Array(dsm.length).fill(0)
            for (let segment of connectedSegments) {
                wayPoints[segment.startIndex] = segment.startHeight
                wayPoints[segment.endIndex] = segment.endHeight
            }

            return wayPoints
        }
    }

    return []
}


// Recursively search for connected segments
const getConnectedSegments = (segment: Path, segmentPossibilities: Path[][], index: number): Path[] => {
    if (index >= segmentPossibilities.length) {
        return [segment]
    }

    for (let connectingSegment of segmentPossibilities[index]) {
        // Matching end and startHeight
        if (segment.endHeight == connectingSegment.startHeight) {
            // There is a possible deep connection
            const connectedSegments = getConnectedSegments(connectingSegment, segmentPossibilities, index + 1)
            if (connectedSegments) {
                return [segment, ...connectedSegments]
            }
        }
    }

    return null
}

// Find longest paths from startIndex, endIndex will always be same for the paths returned
const getLongestPaths = (dsm: number[], startIndex: number, ): Path[] => {
    const paths: Path[] = []

    // Start with paths from start-end and move closer
    for (let endIndex = dsm.length - 1; endIndex > startIndex; --endIndex) {
        const startHeight = dsm[startIndex]
        const endHeight = dsm[endIndex]

        // TODO: This can be optimized with ray casting so we don't over permute
        // Try different permutations of start and end height
        // N^3 can be very expensive to compute
        for (let tryEndHeight = endHeight + MIN_HEIGHT; tryEndHeight <= (endHeight + MAX_HEIGHT); ++tryEndHeight) {
            for (let tryStartHeight = startHeight + MIN_HEIGHT; tryStartHeight <= (startHeight + MAX_HEIGHT); ++tryStartHeight) {
                if (isSegmentValid(dsm, startIndex, endIndex, tryStartHeight, tryEndHeight)) {
                    paths.push({ startIndex, endIndex, startHeight: tryStartHeight, endHeight: tryEndHeight })
                }
            }
        }

        // Found longest possible segments from start
        if (paths.length) {
            break;
        }
    }

    return paths
}

const numWaypoints = (dsm: number[]): number => {
    return dsm.filter(height => height > 0).length
}

// Helpers for isValidFlightPlan


const interpolateHeight = (index: number, startIndex: number, endIndex: number, startHeight: number, endHeight: number): number => {
    return startHeight + ((endHeight - startHeight) * ((index - startIndex) / (endIndex - startIndex)))
}

const isHeightValid = (dsm: number[], index: number, height: number): boolean => {
    return (height >= dsm[index] + MIN_HEIGHT) && (height <= dsm[index] + MAX_HEIGHT)
}

const isSegmentValid = (dsm: number[], startIndex: number, endIndex: number, startHeight: number, endHeight: number): boolean => {
    for (let i = startIndex; i <= endIndex; ++i) {
        // Interpolate height based on current position in segment
        const height = interpolateHeight(i, startIndex, endIndex, startHeight, endHeight)

        // Ensure Interpolated height is within range
        if (!isHeightValid(dsm, i, height)) {
            return false
        }
    }

    return true
}

const getNextWayPointIndex = (wayPoints: number[], startIndex: number): number => {
    let nextWayPointIndex = startIndex + 1

    // Return the index of the next non-zero way point height
    for (let len = wayPoints.length; nextWayPointIndex < len; ++nextWayPointIndex) {
        if (wayPoints[nextWayPointIndex] > 0) {
            break;
        }
    }

    return nextWayPointIndex;
}

const isValidFlightPlan = (dsm: number[], wayPoints: number[]): boolean => {
    // Ensure dsm and wayPoints have same size
    // Ensure start and end are valid heights 
    if (dsm.length != wayPoints.length || wayPoints.length < 2 || wayPoints[0] == 0 || wayPoints[wayPoints.length - 1] == 0) {
        return false
    }

    const lastIndex = dsm.length - 1
    let startIndex = 0, endIndex

    // Check each path segment
    do {
        endIndex = getNextWayPointIndex(wayPoints, startIndex)
        if (!isSegmentValid(dsm, startIndex, endIndex, wayPoints[startIndex], wayPoints[endIndex])) {
            return false;
        }
        startIndex = endIndex
    } while (endIndex != lastIndex)

    return true
}

// Simple assert to validate test case
const testAssert = (test: string, a: any, b: any) => {
    const aStr = JSON.stringify(a)
    const bStr = JSON.stringify(b)

    if (aStr !== bStr) {
        console.error(`FAIL: ${test}: ${aStr} != ${bStr}`)
    } else {
        console.log(`PASS: ${test}`)
    }
}

const runTests = () => {
    const example1_dsm = [0, 3, 6, 6, 10, 12, 5, 2, 1, 2]
    const example1_solution = [6, 0, 0, 0, 0, 16, 0, 0, 5, 6]
    const solution = planWayPoints(example1_dsm)

    testAssert("numWaypoints1", numWaypoints(example1_solution), 4)
    testAssert("isValidFlightPlan1", isValidFlightPlan(example1_dsm, example1_solution), true)
    testAssert("planWayPoints1", solution, example1_solution)

    const example2_dsm = [0, 8, 0];
    const example2_solution = [6, 0, 6];
    testAssert("numWaypoints2", numWaypoints(example2_solution), 2)
    testAssert("isValidFlightPlan2", isValidFlightPlan(example2_dsm, example2_solution), false)
    console.log(example2_dsm, planWayPoints(example2_dsm))

    const example3_dsm = [6, 0, 0, 0, 6];
    const example3_solution = [12, 0, 0, 0, 12];
    testAssert("numWaypoints3", numWaypoints(example3_solution), 2)
    testAssert("isValidFlightPlan3", isValidFlightPlan(example3_dsm, example3_solution), false)
    console.log(example3_dsm, planWayPoints(example3_dsm))
}

// Ensure we pass the given test cases
runTests()