Go Coding with Asparagos: How Much Gazpacho Can We Make with Dynamic Programming?

#go #programming #algorithms #humor

One chef. One heatwave. Can Dynamic Programming save the gazpacho?

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 The World’s Biggest Gazpacho 🍅.

Problem

Everyone is suffering from the summer heat. One chef decides to surprise everyone by making the biggest gazpacho ever.

He needs as many tomatoes as possible. There are several tomato beds in the garden, but he can't gather them all. He wants to keep it a secret - nobody should notice anything suspicious for as long as possible.

So he comes up with a strategy: he’ll collect all the tomatoes from some beds and leave the others untouched — but he won’t leave two adjacent beds empty. Otherwise, someone might suspect something (especially the lemons - they’re always sticking their nose where it doesn’t belong).

Time is running out, the sun is burning, and we all want that delicious cold soup as soon as possible. How can the chef gather the maximum number of tomatoes? And how many tomatoes can he collect in total?

Input 🥒

A slice of integers representing tomato beds — each integer is the number of tomatoes in that bed.

Output 🫑

An integer — the maximum number of tomatoes the chef can collect without leaving two adjacent beds empty.

Examples 🧅:

Example 1

Input: [6, 3, 5, 10]
Output: 16

If we take tomatoes from the first bed, we have two options:
- Take tomatoes from the third bed: 6 + 5 = 11
- Take tomatoes from the last bed: 6 + 10 = 16
If we take tomatoes from the second bed, we can only take tomatoes from the last bed: 3 + 10 = 13

The best option gives us 16 tomatoes.
Example 2

Input: [3, 7, 2]
Output: 7

If we take tomatoes from the first bed, we can also take tomatoes from the last bed: 3 + 2 = 5

If we take tomatoes from the second bed, we can’t take any others, so we get 7 tomatoes.

The best option gives us 7 tomatoes.

Solution 💡

We iterate through the input slice. At each step, we calculate two values:

takeSum: the maximum number of tomatoes we can collect if we take tomatoes from the current bed.

notTakeSum: the maximum number of tomatoes we can collect if we skip the current bed.
Initially, both takeSum and notTakeSum are set to 0.
At each step:

If we take tomatoes from the current bed (num), we should have skipped the previous one. So the new takeSum becomes notTakeSum + num.

If we skip the current bed, it doesn’t matter whether we took or skipped the previous one - we just take the maximum of the previous takeSum and notTakeSum.
After processing all beds, the result is the maximum of takeSum and notTakeSum.

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

func collectTomatoes(beds []int) int {
    takeSum := 0
    notTakeSum := 0
    for _, num := range beds {
        takeSum, notTakeSum = notTakeSum+num, max(notTakeSum, takeSum)
    }
    return max(takeSum, notTakeSum)
}