Permission / Role Assignment Solver (Go)
Topics: backtracking, constraint satisfaction, RBAC
Problem
A rollout needs to assign a set of access-control roles to users. Each role can only go to one of
its eligible users, and separation-of-duty rules say some pairs of roles can never be held
by the same person (e.g. the person who requests a change shouldn't also be the one who
approves it). Find an assignment of every role to an eligible user that satisfies every
separation-of-duty constraint, or prove there isn't one.
type Role struct {
Name string
EligibleUsers []string
ConflictsWith []string
}
func Assign(roles []Role) (map[string]string, bool)
EligibleUsers is the pool of users who may hold this role.ConflictsWith is symmetric: if A.ConflictsWith contains B, then A and B can never be
held by the same user, even if B.ConflictsWith doesn't mention A.- A user may hold multiple roles, as long as none of them conflict with each other.
Assign returns a map from role name to assigned user and true, or nil, false if no valid
assignment exists.
approver eligible: alice, bob conflicts with: requester
requester eligible: alice
Assign({approver, requester}) -> {"approver": "bob", "requester": "alice"}, true
Key concepts
- One choice point per role: for each role, in order, try each eligible user; if a choice
leads to a dead end later, undo it and try the next user. This is the same "try a choice,
recurse, undo on dead end" shape as the other backtracking challenges, applied one role at a
time.
- Why backtracking: in the example above,
alice is approver's first eligible user, and
assigning her there looks fine in isolation — until requester is considered, whose only
eligible user is also alice, and requester conflicts with approver. The solver must undo
approver -> alice and retry with approver -> bob, which leaves alice free for requester.
- Conflicts are checked against the user, not the role: a candidate assignment
role -> user is
rejected if user already holds some other role that conflicts with role (checked in both
directions, since ConflictsWith is symmetric).
- Proving infeasibility: if every eligible user for some role conflicts with an assignment
already made — and every alternative for earlier roles has been exhausted too — the search
reports
false.
The Role struct is provided; you implement Assign.
Run
go test -v ./challenges/role-assignment/go/
Sign in to submit your solution.