Go Coding with Asparagos: Coconuts Never Roll Alone

#go #programming #humor #algorithms

What happens when coconuts start racing?

Hi! I'm Asparagos - an asparagus who codes in Go. Here you’ll find everyday problems that a typical veggie might struggle with — and my Go solutions to them. Today we are solving the problem of Coconut Race 🥥.

Problem

Coconuts are having a race! Just for fun. After all, there's no real need to hurry when you're a coconut.

Each coconut starts from a certain position and has its own speed. They're all rolling in the same direction toward a common finish line.

Whenever one coconut catches up with another, they merge into a coconut bouquet and continue rolling together at the speed of the slowest coconut in the group.

How many bouquets will reach the finish line?

Input 🥭

position []int - the starting positions of the coconuts.

speed []int - the speeds of the coconuts.

target int - the finish line; all coconuts are rolling toward this point.

Output 🍍

An integer representing the number of coconut bouquets that reach the target.

Examples 🍌:

Example 1

Input: position = [1, 3, 18], speed = [5, 1, 3], target = 20

Output: 2

The first coconut (from position 1, speed 5) catches up to the second one (position 3, speed 1) before reaching the target.

They form a bouquet and move together at speed 1.

The third coconut (position 18, speed 3) reaches the target before the bouquet catches up.

So, there are 2 bouquets at the finish.
Example 2

Input: position = [2, 0, 4], speed = [3, 7, 1], target = 10

Output: 1

The coconut starting from 0 (speed 7) quickly catches up to the one at 2 (speed 3).

Together they move at speed 3 and catch up to the coconut at 4 (speed 1) before reaching the target.

All three coconuts finish as a single bouquet.

Solution 💡

First, we sort the coconuts by their starting positions.
Then, we iterate through the coconuts from right to left. We keep track of the current bouquet using two variables:

bouquetPos — the position of the last bouquet,
bouquetSpeed — the speed of the last bouquet.
For each coconut, we check whether it can reach the current bouquet (canReach()). A coconut can merge with the bouquet if it catches up to it before the bouquet itself reaches the finish.
If the coconut can't reach the bouquet, then no other coconut behind it will be able to reach that bouquet either. Why? Because to get there, they would first need to catch up to the current coconut, and then move at its speed. So, if the current coconut can’t make it, nobody else can.

In this case, we increase the count of bouquets res. The current coconut now becomes the new bouquet, so we update bouquetPos and bouquetSpeed.
In the end, we return res + 1, because the very last bouquet wasn’t counted during the loop.

func canReach(leftPos, rightPos, leftSpeed, rightSpeed, target int) bool {
    if leftPos == rightPos {
        return true
    }
    if leftSpeed <= rightSpeed {
        return false
    }
    approachSpeed := leftSpeed - rightSpeed
    approachDist := rightPos - leftPos
    rightDist := target - rightPos
    return approachDist*rightSpeed <= approachSpeed*rightDist
}

type Coconut struct {
    pos   int
    speed int
}

func countCoconutBouquets(target int, position []int, speed []int) int {
    if len(position) == 0 {
        return 0
    }
    coconuts := make([]Coconut, 0, len(position))
    for i, pos := range position {
        coconuts = append(coconuts, Coconut{pos: pos, speed: speed[i]})
    }
    slices.SortFunc(coconuts, func(a, b Coconut) int { return a.pos - b.pos })

    lastInd := len(coconuts) - 1
    bouquetPos := coconuts[lastInd].pos
    bouquetSpeed := coconuts[lastInd].speed
    res := 0
    for i := len(coconuts) - 2; i >= 0; i-- {
        curPos := coconuts[i].pos
        curSpeed := coconuts[i].speed
        if canReach(curPos, bouquetPos, curSpeed, bouquetSpeed, target) {
            continue
        }
        res++
        bouquetPos = curPos
        bouquetSpeed = curSpeed
    }
    return res + 1
}