《互联网产品的服务端架构·交易、增长与平台化》4.2 叠加规则与最优解

// file: internal/coupon/stack.go
// tier: L1
// verify: go test ./internal/coupon/

package coupon

import (
	"errors"
	"fmt"
	"sort"
)

var (
	// ErrNegativeOrder 表示订单金额为负数。
	ErrNegativeOrder = errors.New("coupon: negative order amount")
	// ErrDuplicateCoupon 表示同一张券被传入两次。
	ErrDuplicateCoupon = errors.New("coupon: duplicate coupon id")
	// ErrEmptyCouponID 表示券实例缺少 ID。
	ErrEmptyCouponID = errors.New("coupon: empty coupon id")
)

// Coupon 是一张已经发到用户手里的券。Stackable 表示它能否与其他券叠加；
// 不可叠加券在一次下单中最多使用一张，并且不能和任何其他券同时使用。
type Coupon struct {
	ID             string
	Kind           Kind
	Value          int64
	MinAmountCents int64
	Stackable      bool
}

// Plan 是一组选中的券和它们带来的总优惠。IDs 按字典序排列，保证同一个
// 输入永远得到同一个结果，便于缓存、审计和测试。
type Plan struct {
	IDs           []string
	DiscountCents int64
}

// Best 在给定订单金额下选出优惠最大的一组券。规则如下：
//
//   - 不可叠加券最多选一张，且选中后不能再使用其他券；
//   - 可叠加券可以任意组合，每张券的优惠都按原始订单金额独立计算；
//   - 总优惠不能超过订单金额，金额券也不能把订单减成负数；
//   - 百分比折扣按分计算并向下取整；
//   - 优惠金额相同时，按排序后的 ID 列表字典序取较小者。
//
// 空券列表返回零优惠的 Plan 和 nil，表示“这个订单没有券可用”，不是错误。
func Best(coupons []Coupon, amountCents int64) (Plan, error) {
	if amountCents < 0 {
		return Plan{}, fmt.Errorf("%w: %d", ErrNegativeOrder, amountCents)
	}

	seen := make(map[string]struct{}, len(coupons))
	stackableIDs := make([]string, 0, len(coupons))
	stackableDiscounts := make([]int64, 0, len(coupons))
	var best Plan

	for _, c := range coupons {
		if c.ID == "" {
			return Plan{}, ErrEmptyCouponID
		}
		if _, ok := seen[c.ID]; ok {
			return Plan{}, fmt.Errorf("%w: %s", ErrDuplicateCoupon, c.ID)
		}
		seen[c.ID] = struct{}{}

		d, err := discountOf(c, amountCents)
		if err != nil {
			return Plan{}, err
		}
		if c.Stackable {
			if d > 0 {
				stackableIDs = append(stackableIDs, c.ID)
				stackableDiscounts = append(stackableDiscounts, d)
			}
			continue
		}
		cand := Plan{IDs: []string{c.ID}, DiscountCents: d}
		if better(cand, best) {
			best = cand
		}
	}

	total := int64(0)
	for _, d := range stackableDiscounts {
		if total >= amountCents-d {
			total = amountCents
			break
		}
		total += d
	}
	if total > 0 {
		sort.Strings(stackableIDs)
		cand := Plan{IDs: stackableIDs, DiscountCents: total}
		if better(cand, best) {
			best = cand
		}
	}
	return best, nil
}

// discountOf 计算单张券在原始订单金额上的优惠。门槛未达到时返回 0，
// 但券本身仍然必须是合法的；非法券不能因为“反正用不上”而被静默忽略。
func discountOf(c Coupon, amountCents int64) (int64, error) {
	if c.MinAmountCents < 0 {
		return 0, fmt.Errorf("%w: min %d", ErrInvalidTemplate, c.MinAmountCents)
	}
	switch c.Kind {
	case KindAmount:
		if c.Value <= 0 {
			return 0, fmt.Errorf("%w: amount value %d", ErrInvalidValue, c.Value)
		}
	case KindPercent:
		if c.Value < 1 || c.Value > 100 {
			return 0, fmt.Errorf("%w: percent value %d", ErrInvalidValue, c.Value)
		}
	default:
		return 0, fmt.Errorf("%w: %q", ErrInvalidKind, c.Kind)
	}
	if amountCents < c.MinAmountCents {
		return 0, nil
	}
	if c.Kind == KindAmount {
		if c.Value >= amountCents {
			return amountCents, nil
		}
		return c.Value, nil
	}
	// 先除后乘，避免 amountCents*Value 在大额订单上溢出 int64。
	return amountCents/100*c.Value + amountCents%100*c.Value/100, nil
}

// better 判断 a 是否优于 b：先比优惠金额，再比排序后的 ID 列表字典序。
func better(a, b Plan) bool {
	if a.DiscountCents != b.DiscountCents {
		return a.DiscountCents > b.DiscountCents
	}
	for i := 0; i < len(a.IDs) && i < len(b.IDs); i++ {
		if a.IDs[i] != b.IDs[i] {
			return a.IDs[i] < b.IDs[i]
		}
	}
	return len(a.IDs) < len(b.IDs)
}

// file: internal/coupon/stack_test.go
// tier: L1
// verify: go test ./internal/coupon/

package coupon

import (
	"errors"
	"reflect"
	"testing"
)

func TestBestEmptyCoupons(t *testing.T) {
	got, err := Best(nil, 10000)
	if err != nil {
		t.Fatalf("Best = %v, want nil", err)
	}
	if got.DiscountCents != 0 || len(got.IDs) != 0 {
		t.Fatalf("Best = %+v, want zero plan", got)
	}
}

func TestBestPrefersStackableCombination(t *testing.T) {
	coupons := []Coupon{
		{ID: "a-nonstack", Kind: KindAmount, Value: 3000},
		{ID: "b-stack", Kind: KindAmount, Value: 2000, Stackable: true},
		{ID: "c-stack", Kind: KindAmount, Value: 2000, Stackable: true},
	}
	got, err := Best(coupons, 10000)
	if err != nil {
		t.Fatalf("Best = %v, want nil", err)
	}
	if got.DiscountCents != 4000 {
		t.Fatalf("DiscountCents = %d, want 4000", got.DiscountCents)
	}
	if !reflect.DeepEqual(got.IDs, []string{"b-stack", "c-stack"}) {
		t.Fatalf("IDs = %v, want [b-stack c-stack]", got.IDs)
	}
}

func TestBestPrefersLargerSingleNonStackable(t *testing.T) {
	coupons := []Coupon{
		{ID: "a-nonstack", Kind: KindAmount, Value: 5000},
		{ID: "b-stack", Kind: KindAmount, Value: 2000, Stackable: true},
		{ID: "c-stack", Kind: KindAmount, Value: 2000, Stackable: true},
	}
	got, err := Best(coupons, 10000)
	if err != nil {
		t.Fatalf("Best = %v, want nil", err)
	}
	if got.DiscountCents != 5000 || !reflect.DeepEqual(got.IDs, []string{"a-nonstack"}) {
		t.Fatalf("Best = %+v, want 5000 via a-nonstack", got)
	}
}

func TestBestTieBreaksBySortedIDs(t *testing.T) {
	coupons := []Coupon{
		{ID: "b", Kind: KindAmount, Value: 1000},
		{ID: "a", Kind: KindAmount, Value: 1000},
	}
	got, err := Best(coupons, 10000)
	if err != nil {
		t.Fatalf("Best = %v, want nil", err)
	}
	if !reflect.DeepEqual(got.IDs, []string{"a"}) {
		t.Fatalf("IDs = %v, want [a]", got.IDs)
	}
}

func TestBestCapsDiscountAtOrderAmount(t *testing.T) {
	coupons := []Coupon{
		{ID: "a-stack", Kind: KindAmount, Value: 6000, Stackable: true},
		{ID: "b-stack", Kind: KindAmount, Value: 6000, Stackable: true},
	}
	got, err := Best(coupons, 10000)
	if err != nil {
		t.Fatalf("Best = %v, want nil", err)
	}
	if got.DiscountCents != 10000 {
		t.Fatalf("DiscountCents = %d, want 10000", got.DiscountCents)
	}
}

func TestBestRespectsMinAmountAndFloorsPercent(t *testing.T) {
	coupons := []Coupon{{ID: "p", Kind: KindPercent, Value: 33, MinAmountCents: 1000}}
	if got, err := Best(coupons, 999); err != nil || got.DiscountCents != 0 {
		t.Fatalf("Best below min = %+v, %v; want zero plan", got, err)
	}
	got, err := Best(coupons, 1000)
	if err != nil {
		t.Fatalf("Best = %v, want nil", err)
	}
	if got.DiscountCents != 330 {
		t.Fatalf("DiscountCents = %d, want 330", got.DiscountCents)
	}
	got, err = Best([]Coupon{{ID: "p", Kind: KindPercent, Value: 50}}, 101)
	if err != nil || got.DiscountCents != 50 {
		t.Fatalf("floor = %+v, %v; want 50", got, err)
	}
}

func TestBestRejectsBadInput(t *testing.T) {
	if _, err := Best(nil, -1); !errors.Is(err, ErrNegativeOrder) {
		t.Fatalf("negative amount = %v, want ErrNegativeOrder", err)
	}
	if _, err := Best([]Coupon{{ID: "x", Kind: Kind("gift"), Value: 1}}, 100); !errors.Is(err, ErrInvalidKind) {
		t.Fatalf("bad kind = %v, want ErrInvalidKind", err)
	}
	if _, err := Best([]Coupon{{ID: "x", Kind: KindPercent, Value: 0}}, 100); !errors.Is(err, ErrInvalidValue) {
		t.Fatalf("bad value = %v, want ErrInvalidValue", err)
	}
	dup := []Coupon{
		{ID: "same", Kind: KindAmount, Value: 100},
		{ID: "same", Kind: KindAmount, Value: 200},
	}
	if _, err := Best(dup, 1000); !errors.Is(err, ErrDuplicateCoupon) {
		t.Fatalf("duplicate = %v, want ErrDuplicateCoupon", err)
	}
}

cd .local/checks/webapp-lab && go test ./internal/coupon/ -run 'TestBest' -count=1 -v

=== RUN   TestBestEmptyCoupons
--- PASS: TestBestEmptyCoupons (0.00s)
=== RUN   TestBestPrefersStackableCombination
--- PASS: TestBestPrefersStackableCombination (0.00s)
=== RUN   TestBestPrefersLargerSingleNonStackable
--- PASS: TestBestPrefersLargerSingleNonStackable (0.00s)
=== RUN   TestBestTieBreaksBySortedIDs
--- PASS: TestBestTieBreaksBySortedIDs (0.00s)
=== RUN   TestBestCapsDiscountAtOrderAmount
--- PASS: TestBestCapsDiscountAtOrderAmount (0.00s)
=== RUN   TestBestRespectsMinAmountAndFloorsPercent
--- PASS: TestBestRespectsMinAmountAndFloorsPercent (0.00s)
=== RUN   TestBestRejectsBadInput
--- PASS: TestBestRejectsBadInput (0.00s)
PASS
ok  	webapp/internal/coupon	0.241s