Go Coding with Asparagos: Lemon Squeezy, Dynamic Easy

#go #programming #humor #algorithms

When life gives you lemons, make a quiz team!

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 Lemon Squeezy 🍋.

Problem

Summer is over, lemonade is out of fashion, but the lemons refuse to waste time. They've formed a team called "Lemon Squeezy" and are aiming to win the annual pub quiz.

Now they must decide who joins the team. Each lemon has two attributes: IQ and age. They want a team with the maximum total IQ. But lemons have fragile citrus egos: no lemon will play in a team with a younger lemon who has a higher IQ.

Can they quickly figure out who should be in the team? And what will the total IQ of "Lemon Squeezy" be?

Input 🍊

iqs []int - IQ of each lemon.
ages []int - age of each lemon.

Output 🍐

An integer — the maximum total IQ of a team with no conflicts. A conflict exists if a younger lemon has a higher IQ than the older lemon. Lemons of the same age never conflict, regardless of IQ.

Examples 🍈:

Example 1

Input: iqs = [1, 2, 3], ages = [10, 15, 20]

Output: 6

All lemons can be in the same team.
Example 2

Input: iqs = [4, 9, 20], ages = [20, 10, 15]

Output: 29

The team consists of the second and third lemons. The first lemon can’t be included because its IQ = 4 is lower than the IQ of the second lemon, who is younger.
Example 2

Input: iqs = [17, 24, 50], ages = [46, 37, 5]

Output: 50

The team consists of a single lemon — the last one. Any other combination would include a younger lemon with a higher IQ than an older lemon, causing a conflict.

Solution 💡

First, we sort all lemons by age. If two lemons have the same age, we sort them by IQ. We also create a slice teamIQs, where teamIQs[i] is the maximum total IQ of the team that contains the lemon at index i.
We iterate through the sorted lemons. For each lemon, we first set teamIQs[i] to the current lemon's IQ: at least the team consisting of just the i-th lemon is valid.
For each lemon, we iterate through all previous lemons and try to find a previous team to which the current lemon can be added without conflicts.

In the team at index prevInd, the lemon with the maximum IQ is the lemon at prevInd (otherwise that lemon could not have been added, because it would be older with a smaller IQ, given our sorting).

Therefore, if the current lemon's IQ is greater than or equal to the prevInd lemon's IQ, we can add the current lemon to teamIQs[prevInd] without conflicts. Among all such possible teams, we take the one with the maximum total IQ.
As we go, we update maxTeamIQ — the maximum total IQ over all conflict-free teams.

type Lemon struct {
    iq  int
    age int
}

func findBestTeamIQ(iqs []int, ages []int) int {
    lemons := make([]Lemon, len(iqs))
    for i, iq := range iqs {
        lemons[i] = Lemon{iq: iq, age: ages[i]}
    }
    slices.SortFunc(lemons, func(a, b Lemon) int {
        if a.age == b.age {
            return cmp.Compare(a.iq, b.iq)
        }
        return cmp.Compare(a.age, b.age)
    })

    teamIQs := make([]int, len(lemons))
    maxTeamIQ := 0
    for i, lemon := range lemons {
        teamIQs[i] = lemon.iq
        for prevInd := 0; prevInd < i; prevInd++ {
            if lemons[prevInd].iq > lemon.iq {
                continue
            }
            newIQ := teamIQs[prevInd] + lemon.iq
            if newIQ > teamIQs[i] {
                teamIQs[i] = newIQ
            }
        }
        if teamIQs[i] > maxTeamIQ {
            maxTeamIQ = teamIQs[i]
        }
    }
    return maxTeamIQ
}