Feature Flag Compatibility Solver (Go)
Topics: backtracking, constraint satisfaction, configuration
Problem
A rollout wants to enable a set of feature flags. Some flags require others (sometimes one of
several alternatives), and some flags exclude each other. Find a compatible set to enable, or
prove there isn't one.
type Flag struct {
Name string
Excludes []string // can't be enabled alongside any of these
Requires [][]string // for each group, at least one must also be enabled
}
func Enable(flags []Flag, want []string) (map[string]bool, bool)
Excludes is symmetric: if A.Excludes contains B, then A and B can never both be
enabled, even if B.Excludes doesn't mention A.Requires is a list of groups. For each group, at least one member must end up enabled.
A single-element group ({"x"}) is a plain "must also enable x"; a multi-element group
({"x", "y"}) is a choice — enabling either satisfies it.
Enable returns the resulting set (a superset of want, with everything Requires pulls in) and
true, or nil, false if every combination conflicts.
new-ui requires (fast-path OR legacy-path)
fast-path excludes legacy-path
metrics-v2 excludes fast-path
Enable({new-ui, metrics-v2}) -> {new-ui, metrics-v2, legacy-path}, true
Key concepts
- Two kinds of work items: an "enable flag X" obligation (check
Excludes, then queue X's
Requires groups) and a "satisfy this OR-group" obligation. Only the OR-group is a choice
point — everything else is forced.
- Why backtracking: in the example above,
fast-path would satisfy new-ui's requirement, and
if the solver tries it first it looks fine — until metrics-v2 (also wanted) turns out to
exclude it. The solver must undo enabling fast-path and retry the OR-group with
legacy-path. This is exactly the "try a choice, recurse, undo on dead end" shape, just like
N-Queens or Sudoku.
- Proving infeasibility: if every option in some OR-group conflicts with something already
enabled, the search must try them all before reporting
false.
The Flag struct is provided; you implement Enable.
Run
go test -v ./challenges/feature-flag-solver/go/
Sign in to submit your solution.