(if only as a starting point, towards a better solution)
so, here is a naive, brute-force backtracking (in ECMAScript 5) I was thinking of, which should always find a solution if there is any, along with the trace of it.
This could certainly be adapted, likewise, to explore and return all the possible solutions (if more than one), along with their traces:
https://jsfiddle.net/YSharpLanguage/w2zoz3us
function fulfilled(solution, requirements, attended, relaxer, index) {
function newRequirement(original, isRelaxed) {
if (isRelaxed) {
var i = original.courses.indexOf(relaxer),
// Exclude the relaxer course from
// the courses of a relaxed requirement
newCourses = original.courses.slice(0, i).
concat(original.courses.slice(i + 1)),
// Decrement the weight of a relaxed requirement
newWeight = original.weight - 1;
return {
id: original.id,
weight: newWeight,
courses: newCourses
};
}
else {
return original;
}
}
function someUnfulfilled() {
// True if any unfulfilled requirement,
// false otherwise
return requirements.find(function(requirement) {
return requirement.weight > 0;
}) != null;
}
// Are we trying to relax some requirement
// by a given (relaxer) course, or are we
// merely at the bottom of the call stack?
if (typeof index !== "undefined") {
// ... yes, we are relaxing a requirement; so make
// a new requirement list differing only by it,
// at index, relaxed by the relaxer course
var relaxed = requirements[index];
requirements = requirements.map(function(requirement) {
return newRequirement(requirement, requirement.id === relaxed.id);
});
}
// Is there any unfulfilled requirement?
if (someUnfulfilled()) {
// Is there any more courses being attended?
if (attended.length > 0) {
// Current course, head of the attended courses:
var course = attended[0];
for (var i = 0; i < requirements.length; i++) {
var candidate;
// Try to relax only the unfulfilled requirements:
if ((candidate = requirements[i]).weight > 0) {
// Remaining courses, after the current one:
var remaining = attended.slice(1);
// Can the current course contribute to the solution
// by relaxing the candidate (i-th) requirement?
if (
(candidate.courses.indexOf(course) >= 0) &&
(fulfilled(solution, requirements, remaining, course, i))
) {
// Yes, it could; so, record its contribution,
// and backtrack with a success signal
solution.push({ course: course, requirement: candidate.id });
return true;
} else {
// (Keep iterating through the requirements)
}
} else {
// (Ignore the already fulfilled requirements)
}
}
// The current course cannot relax any requirement,
// and also contribute to the solution by doing so;
// so, backtrack with a failure signal
return false;
} else {
// Not enough of attended courses to fulfill the requirements;
// so, backtrack with a failure signal
return false;
}
} else {
// All the requirements have been fulfilled by now,
// so, backtrack with a success signal
return true;
}
}
E.g.,
(as in your question's example)
var allRequirements =
[
{ id: "R1", weight: 2, courses: [ 'A', 'B', 'C', 'D' ] },
{ id: "R2", weight: 1, courses: [ 'A', 'B' ] }
],
aSolution = [ ],
input = [ 'A', 'B', 'C', 'D' ];
fulfilled(aSolution, allRequirements, input)
aSolution.reverse()
yields:
aSolution === [
{
"course": "A",
"requirement": "R1"
},
{
"course": "B",
"requirement": "R2"
},
{
"course": "C",
"requirement": "R1"
}
]
while,
allRequirements =
[
{ id: "R1", weight: 3, courses: [ 'A', 'B', 'C', 'D' ] },
{ id: "R2", weight: 2, courses: [ 'A', 'B', 'E' ] }
];
aSolution = [ ];
input = [ 'A', 'B', 'C', 'D', 'E' ];
fulfilled(aSolution, allRequirements, input)
aSolution.reverse()
yields:
aSolution === [
{
"course": "A",
"requirement": "R1"
},
{
"course": "B",
"requirement": "R2"
},
{
"course": "C",
"requirement": "R1"
},
{
"course": "D",
"requirement": "R1"
},
{
"course": "E",
"requirement": "R2"
}
]
'HTH,
