Problem

Permission / Role Assignment Solver (C)

Topics: backtracking, constraint satisfaction, RBAC

Problem

Assign each role in an access-control rollout to one of its eligible users, honoring separation-of-duty constraints: no single user may hold two roles that conflict.

typedef struct {
    const char *name;
    const char *const *eligible;  int neligible;   // users allowed to hold this role
    const char *const *conflicts; int nconflicts;  // roles that can't share a user (symmetric)
} Role;

bool assign_roles(const Role *roles, int n, const char **out_user);

Find an assignment of every role to one of its eligible users such that no user holds two conflicting roles. On success, write out_user[i] = the user assigned to roles[i] and return true; otherwise return false.

Key concepts

One role at a time, backtrack on dead ends: for roles[idx], try each eligible user that doesn't conflict with a role already given to that same user; recurse on the next role; if it can't be completed, undo and try the next user. A greedy first pick that strands a later role gets revisited.
Conflicts are symmetric: if approver lists requester in conflicts, the rule applies even though requester doesn't list approver. Check both roles' conflict lists.
Only assigned roles constrain: a conflict partner that hasn't been assigned yet imposes nothing — which is exactly why naive ordering needs backtracking.
No eligible users for some role means no solution.

The out_user[] array doubles as the working assignment — no allocation.

Run

cc -std=c11 -O2 -Wall tests.c -o /tmp/rbac && /tmp/rbac

Leaderboard score: lower is better, 1.0 ≈ reference

#	Name	score	ns/op	allocs

Output

No submission yet.