Go Coding with Asparagos: Saving Apples from Pies

#go #programming #humor #algorithms

Can a single train save apples from the pie threat?

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 Apple Escape 🍎.

Problem

The season of Apple Pies has begun. All the apples are leaving their homes in search of a safer place. Nobody wants to end up in a pie anymore — it’s just not trendy. A smoothie is better, or at least a strudel.

There is a train going in one direction with a limited number of seats. Apples travel in groups: each group wants to board the train at point X and leave at point Y.

Can the train take every apple without exceeding its seats?

Input 🍐

trips []Trip - information about group trips. Each Trip has a start point from, an end point to, and the group size num.

capacity int - the number of seats on the train.

Output 🍊

true if the train can carry all apples without exceeding capacity at any point; false otherwise.

Examples 🍋:

Example 1

Input: trips = {{from: 2, to: 7, num: 1}, {from: 0, to: 2, num: 3}, {from: 1, to: 3, num: 2}}, capacity = 5

Output: true

At point 0, the train takes 3 apples.

Then, at point 1, it takes 2 more apples, so now all 5 seats are occupied.

At point 2, 3 apples leave the train. At the same time, 1 apple boards the train. Now there are 3 apples on board.

At point 3, 2 apples leave the train. Only 1 apple remains, which will leave at point 7.

The apples on board never exceeded the train’s capacity.
Example 2

Input: trips = {{from: 0, to: 2, num: 3}, {from: 1, to: 3, num: 2}}, capacity = 4

Output: false

At point 0, the train takes 3 apples.

At point 1, it should take 2 more apples. That would require 5 seats, but the capacity is 4, so the train can't take them.

Solution 💡

First, we build a list of events: each trip creates a pick-up event at from and a drop-off event at to. We sort events by location in ascending order. When two events have the same location, put drop-offs before pick-ups. In this case, the freed seats can be reused immediately. Each event contains: location, num (group size), and isFrom (whether it is a pick-up or drop-off).
We iterate through the events and update the current number of apples on the train num. If it's a drop-off, we subtract the size of the group from num. Otherwise, we add the group size to num.
If at any point a pick-up would exceed capacity, return false.
Otherwise, return true.

type Trip struct {
    from int
    to   int
    num  int
}

type Event struct {
    location int
    num      int
    isFrom   bool
}

func canSaveAllApples(trips []Trip, capacity int) bool {
    events := make([]Event, 0, 2*len(trips))
    for _, trip := range trips {
        events = append(events, Event{trip.from, trip.num, true}, Event{trip.to, trip.num, false})
    }
    slices.SortFunc(events, func(a, b Event) int {
        if a.location != b.location {
            return cmp.Compare(a.location, b.location)
        }
        if a.isFrom == b.isFrom {
            return 0
        }
        if !a.isFrom {
            return -1
        }
        return 1
    })
    num := 0
    for _, event := range events {
        if !event.isFrom {
            num -= event.num
            continue
        }
        if capacity-num < event.num {
            return false
        }
        num += event.num
    }
    return true
}