Go Coding with Asparagos: Can oranges sow the seeds of discord in linear time?

#go #programming #humor #beginners

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 Orange seeds 🍊.

Can one orange tree start a citrus empire?

Problem

After the successful election victory, the fruits decided to expand their power and capture as much territory as possible (you can find the backstory of how fruits gained power in the Veggie Kingdom here).

The oranges were given an important mission: they should plant orange trees along the entire alley. The alley is a narrow strip of land divided into sectors. Only one tree can be planted per sector (orange trees need their privacy, they are definitely introverts).

Each tree can throw seeds to nearby sectors, but only within its maximum throwing distance. For example, if a tree stands at sector N and its maximum throwing distance is K, it can throw seeds to every sector in the interval [N +1, N + K]. A new tree grows in each sector that receives a seed.

The goal of the orange trees is to plant a tree at the last sector of the alley. They start at the first sector. It's guaranteed that they'll succeed, because oranges never fail their missions.

The question is: what's the minimum number of throws they need to complete the mission?

Input 🍎

A slice of integers — each integer represents the maximum distance a seed can be thrown from that sector.

Examples 🍉:

Example 1

Input: [3, 1, 5, 1, 1]

Output: 2: the tree at sector 0 throws to sector 2, and the tree at sector 2 throws to the last sector.
Example 2

Input: [1, 3, 16, 1, 1, 5, 1]

Output: 3: the tree at sector 0 throws to sector 1, the tree at sector 1 throws to sector 2, and the tree ar sector 2 throws to the last sector.
Example 3

Input: [1]

Output: 0: we're already at the last sector.

Solution 💡

We need three variables:

• throws: the number of throws we've already made.

• maxInd: the farthest index we can currently reach using the current number of throws.

• nextMaxInd: the farthest index we can reach with one more throw (throws + 1).
We iterate through the input slice sectors. At each step:

• If we've already reached the last sector maxInd >= len(sectors)-1, the current number of throws is the answer.

• If the current index ind is beyond maxInd, we update maxInd to nextMaxInd and increment throws.

• Otherwise, we update nextMaxInd: we can now potentially reach sector ind+distance, which can be farther than current nextMaxInd.

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func sowTheSeedsOfDiscord(sectors []int) int {
    maxInd := 0
    nextMaxInd := 0
    throws := 0
    for ind, distance := range sectors {
        if maxInd >= len(sectors)-1 {
            return throws
        }
        if ind > maxInd {
            maxInd = nextMaxInd
            nextMaxInd = ind + distance
            throws++
        } else {
            nextMaxInd = max(nextMaxInd, ind+distance)
        }
    }
    return throws
}