I'm trying to write an algorithm that takes a list of events (in this case, screenings of movies - each movie usually has more than one screening, although that's not always the case) and returns the best possible combination of events, i.e. the one that sacrifices the least amount of movies.
I came up with this algorithm which I applied manually, but I'm trying to turn it into code and having some trouble. What I did (manually) was go screening by screening, checking whether it had conflicts with any other screening. If it did, it would resolve the conflicts (let's say it's a conflict between the first screenings of Movie A and Movie B) by choosing one of the two conflicting movies* (Movie A), deleting all other screenings for Movie A, and deleting that screening of Movie B. After doing that, it would look for another screening of Movie B, check whether it had any conflicts, and repeat the process.
* Usually the one I was currently checking, but some criteria could affect the decision, e.g. if one of the two conflicting movies had a free (conflict-less) screening somewhere else, I would just choose that one and resolve the conflict that way. Conversely, if one of the two movies had no other screenings, I would choose that one.
Eventually this "branch" would end up arriving at a free (conflict-less) screening, which would mean the entire branch was solved (i.e. all of the movies involved could be watched without sacrificing any others), or it would arrive at a stalemate, which would mean that this combination of decisions did not lead to a perfect solution. In this case, one would go back up a level of recursion (i.e. go back one decision) and try choosing the other screening. If that didn't work, go back up another level and try again. If there was no combination of decisions in that branch that led to a solved branch, a decision had to be made by the human to sacrifice one of the movies that was causing the issue.
That's pretty much what I'm trying to code, and I wrote an attempt at it in a very stream-of-consciousness way just trying to get it out quickly cause I was excited, not thinking far ahead and just fixing issues as they came up. It worked for the movie festival I was trying it on, which was somewhat small (no more than 4 screenings at the same time), but crashed when I tried it on a larger one (6 screenings at the same time sometimes). It exceeds the maximum stack size, probably because of a problem in the code although I'm not sure if it might just be running correctly and just getting into those levels of recursion. On this note, not sure whether this would be better solved with a while loop instead of recursively.
Yesterday I decided to scrap the algorithm I wrote and start from scratch in a better planned manner, and found the main 2 issues I see looking into the future are:
- The ability for the algorithm to "go back" and switch its previous decision when a branch failed. This is a core mechanic of the algorithm but I'm struggling to think of a good way to code it. In my previous one I implemented a "checkpoint" system where, if a branch failed, it would revert back to the last checkpoint and continue on from there, and if it succeeded, it would mark that one as the new checkpoint. But that only worked top-level, and not for "internal" decisions.
- The fact that most schedules will have more than one solution. If the solution is perfect (i.e. no movies sacrificed), then the issue is very minor in that either way you won't be missing any movies, and at most you'll be deprived of choosing between a few screenings of the same movies. But if there is no perfect solution, now the choice might be between having to decide between 2 movies that you really wanna watch, and between 2 movies that you don't care about that much. This means that the algorithm would need to go over every single possible combination of screenings to find the best possible one(s), and if there's no perfect solution it would show you the different possibilities. But this would be brute forcing the problem which (unless strictly necessary) is not really what I'm looking for.
I'd appreciate any help or guidance in the matter. For reference, I'm writing this in Typescript React Next.js, but I think this is a more general CS question so again, any help is appreciated.
The current algorithm as well as mock data can be found here: https://jsfiddle.net/procz/82n3jxLb/
const findBestSchedule = (
screeningData: IScreening[],
movies: IMovie[]
): IScreening[] => {
const debugLog = (type: string, args) => {
if (!DEBUG_LOG) return;
if (type === "process") {
return console.log(
`processing ${findMovie(
movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs - called from ${
args.calledFrom
}, currentArray:`,
args.screenings
);
}
if (type === "conflict") {
return console.log(
`conflict between ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} ${args.screening1.date.getDate()} ${args.screening1.date.getHours()}hs and ${findMovie(
movies,
args.screening2
).name.toUpperCase()} ${args.screening2.date.getDate()} ${args.screening2.date.getHours()}hs`
);
}
if (type === "free") {
return console.log(
`${findMovie(
args.movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs is free, deleting all other ${findMovie(
args.movies,
args.screening
).name.toUpperCase()}`
);
}
if (type === "recursion") {
return console.log(args.recursionLevel, args.array);
}
if (type === "unsolvable") {
return console.log(
`unsolvable conflict between ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} and ${findMovie(
args.movies,
args.screening2
).name.toUpperCase()}, backtracking`
);
}
if (type === "decision") {
return console.log(
`recursion level: ${args.recursionLevel} - choosing ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} ${args.screening1.date.getDate()} ${args.screening1.date.getHours()}hs, deleting ${findMovie(
args.movies,
args.screening2
).name.toUpperCase()} ${args.screening2.date.getDate()} ${args.screening2.date.getHours()}hs, deleting all other ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()}`
);
}
if (type === "noConflict") {
return console.log(
`no conflicts found for ${findMovie(
args.movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs, deleting all other ${findMovie(
args.movies,
args.screening
).name.toUpperCase()}`
);
}
};
const sortedScreenings = [...screeningData].sort(
(a, b) => b.date.getTime() - a.date.getTime()
);
let latestScreeningArray = sortedScreenings;
let recursionLevel = 0;
let lastSafeArray = latestScreeningArray;
let lastSafeRecursionLevel = recursionLevel;
const processScreening = (
screenings: IScreening[],
screening: IScreening,
calledFrom ? : string
): boolean => {
debugLog("process", {
screening,
calledFrom,
screenings
});
const findConflictingScreenings = (
screenings: IScreening[],
screening: IScreening
): IScreening[] => {
if (!screenings) return [];
return [...screenings].filter(
(otherScreening) =>
screening.id !== otherScreening ? .id &&
screeningsOverlap(screening, otherScreening, movies)
);
};
const conflictingScreenings = findConflictingScreenings(
screenings,
screening
);
if (conflictingScreenings.length) {
const resolveConflict = (
screening: IScreening,
otherScreening: IScreening
): boolean => {
debugLog("conflict", {
screening1: screening,
screening2: otherScreening,
movies,
});
const findNextScreenings = (
screenings: IScreening[],
screening: IScreening
): IScreening[] => {
return [...screenings]
.reverse()
.filter(
(currentScreening) =>
currentScreening.id !== screening.id &&
findMovie(movies, currentScreening).id ===
findMovie(movies, screening).id
);
};
const findFreeScreening = (
screenings: IScreening[],
screening: IScreening
): IScreening => {
return findNextScreenings(screenings, screening).find(
(nextScreening) =>
!findConflictingScreenings(screenings, nextScreening).length
);
};
const freeOtherScreening = findFreeScreening(
latestScreeningArray,
otherScreening
);
const freeScreening = findFreeScreening(
latestScreeningArray,
screening
);
if (freeOtherScreening || freeScreening) {
/* FREE SCREENING */
debugLog("free", {
screening: freeOtherScreening || freeScreening,
movies,
});
latestScreeningArray = deleteAllOtherScreenings(
latestScreeningArray,
freeOtherScreening || freeScreening,
movies
);
return true;
} else {
/* NO FREE SCREENINGS */
const decideAndMoveToNextStep = (
screenings: IScreening[],
screening1: IScreening,
screening2: IScreening
): boolean => {
latestScreeningArray = removeScreening(
deleteAllOtherScreenings(screenings, screening1, movies),
screening2
);
debugLog("recursion", {
recursionLevel,
array: latestScreeningArray,
});
recursionLevel ;
const nextStepOfBranchIsSolvable = processScreening(
latestScreeningArray,
findNextScreenings(screenings, screening2)[0],
`decideAndMoveToNextStep`
);
if (!nextStepOfBranchIsSolvable) {
debugLog("unsolvable", {
movies,
screening1,
screening2
});
latestScreeningArray = screenings;
}
return nextStepOfBranchIsSolvable;
};
const nextScreeningOfOther = findNextScreenings(
latestScreeningArray,
otherScreening
)[0];
if (nextScreeningOfOther) {
debugLog("decision", {
recursionLevel,
movies,
screening1: screening,
screening2: otherScreening,
});
return decideAndMoveToNextStep(
latestScreeningArray,
screening,
otherScreening
);
} else {
const nextScreening = findNextScreenings(
latestScreeningArray,
screening
)[0];
if (nextScreening) {
debugLog("decision", {
recursionLevel,
movies,
screening1: otherScreening,
screening2: screening,
});
return decideAndMoveToNextStep(
latestScreeningArray,
otherScreening,
screening
);
} else {
debugLog("unsolvable", {
movies,
screening1: screening,
screening2: otherScreening,
});
return false;
}
}
}
};
for (let i = conflictingScreenings.length - 1; i >= 0; i--) {
const branchResolved = resolveConflict(
screening,
[...conflictingScreenings].reverse()[i]
);
if (!branchResolved) {
latestScreeningArray = lastSafeArray;
break;
}
}
debugLog("noConflicts", {
movies,
screening
});
debugLog("recursion", {
recursionLevel,
array: latestScreeningArray
});
if (recursionLevel > 0) {
recursionLevel--;
}
return true;
} else {
const updatedScreenings = deleteAllOtherScreenings(
screenings,
screening,
movies
);
latestScreeningArray = updatedScreenings;
if (recursionLevel > 0) {
recursionLevel--;
}
return false;
}
};
for (let i = latestScreeningArray.length - 1; i >= 0; i--) {
if (!!latestScreeningArray[i]) {
lastSafeArray = latestScreeningArray;
lastSafeRecursionLevel = recursionLevel;
processScreening(
latestScreeningArray,
latestScreeningArray[i],
"overarching"
);
}
}
return latestScreeningArray;
};
CodePudding user response：
I would suggest mixed integer programming. There’s a library javascript-lp-solver available on NPM, which is probably OK for light use like this.
The basic idea is to have a 0–1 variable for each movie indicating whether we see any screening of that movie, and a 0–1 variable for each screening indicating whether we see that screening. We want to maximize the number of movies seen (or maybe some more complicated linear function).
There are two kinds of constraints. For each time, we cannot attend more than one screening during that time (for each time, the sum of the screening variables at that time is less than or equal to 1). This is handled in the code below with a sweep-line algorithm. For each movie, we can’t see it unless we attend one of its screenings (for each movie, sum of screening variables for that movie minus movie variable greater than or equal to 0).
I implemented this in JavaScript below (poorly, since I’m not fluent, and the API on this library is not the best).
const movies = [
{
id: 1,
runtime: 121,
},
{
id: 2,
runtime: 116,
},
{
id: 3,
runtime: 144,
},
{
id: 4,
runtime: 96,
},
{
id: 5,
runtime: 108,
},
{
id: 6,
runtime: 117,
},
{
id: 7,
runtime: 92,
},
{
id: 8,
runtime: 110,
},
{
id: 9,
runtime: 90,
},
{
id: 10,
runtime: 99,
},
{
id: 11,
runtime: 62,
},
{
id: 12,
runtime: 116,
},
{
id: 13,
runtime: 85,
},
{
id: 14,
runtime: 92,
},
{
id: 15,
runtime: 85,
},
{
id: 16,
runtime: 90,
},
{
id: 17,
runtime: 103,
},
{
id: 18,
runtime: 113,
},
{
id: 19,
runtime: 72,
},
{
id: 20,
runtime: 109,
},
{
id: 21,
runtime: 109,
},
{
id: 22,
runtime: 142,
},
{
id: 23,
runtime: 96,
},
{
id: 24,
runtime: 73,
},
{
id: 25,
runtime: 86,
},
{
id: 26,
runtime: 106,
},
{
id: 27,
runtime: 97,
},
{
id: 28,
runtime: 100,
},
{
id: 29,
runtime: 146,
},
{
id: 30,
runtime: 146,
},
{
id: 31,
runtime: 146,
},
{
id: 32,
runtime: 108,
},
{
id: 33,
runtime: 89,
},
{
id: 34,
runtime: 126,
},
{
id: 35,
runtime: 121,
},
{
id: 36,
runtime: 150,
},
{
id: 37,
runtime: 108,
},
{
id: 38,
runtime: 103,
},
{
id: 39,
runtime: 130,
},
{
id: 40,
runtime: 83,
},
{
id: 41,
runtime: 136,
},
{
id: 42,
runtime: 85,
},
{
id: 43,
runtime: 179,
},
{
id: 44,
runtime: 106,
},
{
id: 45,
runtime: 107,
},
{
id: 46,
runtime: 93,
},
{
id: 47,
runtime: 75,
},
{
id: 48,
runtime: 86,
},
{
id: 49,
runtime: 80,
},
{
id: 50,
runtime: 80,
},
];
const screenings = [
{
id: 1,
date: "2021-11-18T23:15:00.000Z",
movieId: 18,
},
{
id: 2,
date: "2021-11-20T14:15:00.000Z",
movieId: 19,
},
{
id: 3,
date: "2021-11-19T21:00:00.000Z",
movieId: 19,
},
{
id: 4,
date: "2021-11-19T15:03:00.000Z",
movieId: 19,
},
{
id: 5,
date: "2021-11-19T23:04:00.000Z",
movieId: 20,
},
{
id: 6,
date: "2021-11-19T17:00:00.000Z",
movieId: 20,
},
{
id: 7,
date: "2021-11-25T20:00:00.000Z",
movieId: 20,
},
{
id: 8,
date: "2021-11-19T14:00:00.000Z",
movieId: 21,
},
{
id: 9,
date: "2021-11-19T20:00:00.000Z",
movieId: 21,
},
{
id: 10,
date: "2021-11-25T17:00:00.000Z",
movieId: 21,
},
{
id: 11,
date: "2021-11-19T21:00:00.000Z",
movieId: 22,
},
{
id: 12,
date: "2021-11-20T18:00:00.000Z",
movieId: 22,
},
{
id: 13,
date: "2021-11-19T16:00:00.000Z",
movieId: 23,
},
{
id: 14,
date: "2021-11-19T14:30:00.000Z",
movieId: 24,
},
{
id: 15,
date: "2021-11-19T23:30:00.000Z",
movieId: 24,
},
{
id: 16,
date: "2021-11-20T19:30:00.000Z",
movieId: 24,
},
{
id: 17,
date: "2021-11-20T14:30:00.000Z",
movieId: 25,
},
{
id: 18,
date: "2021-11-20T20:30:00.000Z",
movieId: 25,
},
{
id: 19,
date: "2021-11-21T22:30:00.000Z",
movieId: 25,
},
{
id: 20,
date: "2021-11-20T14:00:00.000Z",
movieId: 26,
},
{
id: 21,
date: "2021-11-20T20:00:00.000Z",
movieId: 26,
},
{
id: 22,
date: "2021-11-20T15:00:00.000Z",
movieId: 27,
},
{
id: 23,
date: "2021-11-20T21:00:00.000Z",
movieId: 27,
},
{
id: 24,
date: "2021-11-21T14:15:00.000Z",
movieId: 27,
},
{
id: 25,
date: "2021-11-20T18:00:00.000Z",
movieId: 28,
},
{
id: 26,
date: "2021-11-21T00:00:00.000Z",
movieId: 28,
},
{
id: 27,
date: "2021-11-21T17:15:00.000Z",
movieId: 28,
},
{
id: 28,
date: "2021-11-21T21:00:00.000Z",
movieId: 31,
},
{
id: 29,
date: "2021-11-20T21:00:00.000Z",
movieId: 31,
},
{
id: 30,
date: "2021-11-21T00:00:00.000Z",
movieId: 32,
},
{
id: 31,
date: "2021-11-29T00:00:00.000Z",
movieId: 32,
},
{
id: 32,
date: "2021-11-23T18:30:00.000Z",
movieId: 32,
},
{
id: 33,
date: "2021-11-21T14:00:00.000Z",
movieId: 33,
},
{
id: 34,
date: "2021-11-21T20:00:00.000Z",
movieId: 33,
},
{
id: 35,
date: "2021-11-22T22:30:00.000Z",
movieId: 33,
},
{
id: 36,
date: "2021-11-21T18:00:00.000Z",
movieId: 34,
},
{
id: 37,
date: "2021-11-22T23:15:00.000Z",
movieId: 34,
},
{
id: 38,
date: "2021-11-21T20:15:00.000Z",
movieId: 35,
},
{
id: 39,
date: "2021-11-27T21:00:00.000Z",
movieId: 35,
},
{
id: 40,
date: "2021-11-22T15:00:00.000Z",
movieId: 36,
},
{
id: 41,
date: "2021-11-23T00:00:00.000Z",
movieId: 36,
},
{
id: 42,
date: "2021-11-23T14:15:00.000Z",
movieId: 36,
},
{
id: 43,
date: "2021-11-22T13:45:00.000Z",
movieId: 37,
},
{
id: 44,
date: "2021-11-22T18:30:00.000Z",
movieId: 37,
},
{
id: 45,
date: "2021-11-22T21:30:00.000Z",
movieId: 37,
},
{
id: 46,
date: "2021-11-22T17:30:00.000Z",
movieId: 38,
},
{
id: 47,
date: "2021-11-22T23:30:00.000Z",
movieId: 38,
},
{
id: 48,
date: "2021-11-23T16:30:00.000Z",
movieId: 38,
},
{
id: 49,
date: "2021-11-22T21:00:00.000Z",
movieId: 39,
},
{
id: 50,
date: "2021-11-28T18:00:00.000Z",
movieId: 39,
},
{
id: 51,
date: "2021-11-23T18:00:00.000Z",
movieId: 40,
},
{
id: 52,
date: "2021-11-27T21:30:00.000Z",
movieId: 40,
},
{
id: 53,
date: "2021-11-24T18:00:00.000Z",
movieId: 41,
},
{
id: 54,
date: "2021-11-23T18:00:00.000Z",
movieId: 41,
},
{
id: 55,
date: "2021-11-25T18:00:00.000Z",
movieId: 41,
},
{
id: 58,
date: "2021-11-23T21:00:00.000Z",
movieId: 43,
},
{
id: 59,
date: "2021-11-24T21:00:00.000Z",
movieId: 43,
},
{
id: 60,
date: "2021-11-24T14:30:00.000Z",
movieId: 44,
},
{
id: 61,
date: "2021-11-24T20:30:00.000Z",
movieId: 44,
},
{
id: 62,
date: "2021-11-25T16:30:00.000Z",
movieId: 44,
},
{
id: 63,
date: "2021-11-25T21:00:00.000Z",
movieId: 45,
},
{
id: 64,
date: "2021-11-26T15:00:00.000Z",
movieId: 45,
},
{
id: 70,
date: "2021-11-24T15:00:00.000Z",
movieId: 48,
},
{
id: 71,
date: "2021-11-24T21:00:00.000Z",
movieId: 48,
},
{
id: 72,
date: "2021-11-26T00:00:00.000Z",
movieId: 48,
},
{
id: 76,
date: "2021-11-24T14:00:00.000Z",
movieId: 50,
},
{
id: 77,
date: "2021-11-24T20:00:00.000Z",
movieId: 50,
},
{
id: 78,
date: "2021-11-27T17:00:00.000Z",
movieId: 50,
},
];
let model = {
optimize: "movieSeen",
opType: "max",
constraints: {},
variables: {},
ints: {},
};
let constraintId = 1000;
for (const movie of movies) {
constraintId;
model.constraints[constraintId] = { max: 1 };
model.variables["m" movie.id] = { movieSeen: 1 };
model.variables["m" movie.id][constraintId] = 1;
constraintId;
model.constraints["sm" movie.id] = { min: 0 };
model.variables["m" movie.id]["sm" movie.id] = -1;
}
for (const screening of screenings) {
constraintId;
model.constraints[constraintId] = { min: 0 };
model.variables["s" screening.id] = { constraintId: 1 };
model.variables["s" screening.id]["sm" screening.movieId] = 1;
model.ints["s" screening.id] = 1;
}
let runtimes = {};
for (const movie of movies) {
runtimes[movie.id] = movie.runtime;
}
let events = [];
for (const screening of screenings) {
const start = Date.parse(screening.date);
events.push({ date: start, isStart: true, id: screening.id });
const finish = start runtimes[screening.movieId] * 60 * 1000;
events.push({ date: finish, isStart: false, id: screening.id });
}
events.sort(function (a, b) {
return a.date - b.date;
});
let previousIsStart = false;
let nowPlaying = {};
for (const event of events) {
if (event.isStart) {
nowPlaying[event.id] = true;
previousIsStart = true;
} else {
if (previousIsStart) {
constraintId;
model.constraints[constraintId] = { max: 1 };
for (const id of Object.keys(nowPlaying)) {
model.variables["s" id][constraintId] = 1;
}
}
delete nowPlaying[event.id];
previousIsStart = false;
}
}
let solver = require("javascript-lp-solver");
let results = solver.Solve(model);
console.log(results);
Output:
{
feasible: true,
result: 27,
bounded: true,
isIntegral: true,
s1: 1,
s64: 1,
s12: 1,
s15: 1,
s42: 1,
s20: 1,
s24: 1,
s29: 1,
s31: 1,
s37: 1,
s19: 1,
s46: 1,
s51: 1,
s53: 1,
s58: 1,
s71: 1,
s13: 1,
s3: 1,
s8: 1,
s34: 1,
s7: 1,
s26: 1,
s39: 1,
s43: 1,
s49: 1,
s76: 1,
s62: 1,
m18: 1,
m19: 1,
m20: 1,
m21: 1,
m22: 1,
m23: 1,
m24: 1,
m25: 1,
m26: 1,
m27: 1,
m28: 1,
m31: 1,
m32: 1,
m33: 1,
m34: 1,
m35: 1,
m36: 1,
m37: 1,
m38: 1,
m39: 1,
m40: 1,
m41: 1,
m43: 1,
m44: 1,
m45: 1,
m48: 1,
m50: 1
}