Hacker News Reader

Comment by johnisgood | Hacker News Reader

Does anyone know if Prolog is useful for creating a schedule for workers with many constraints? I have a comment somewhere where I included the constraints but I have forgotten most of it by now. Constraints like minimum of 2 workers for both morning and night shifts, all workers must have 2 days off at least in a week, so no consecutive 3 days work, etc. The number of workers would be defined with names as well, etc. The goal would be to create a monthly schedule. I tried to come up with one but I may have messed up the constraints because it took too long (it got stuck, actually), maybe the constraints were too tight, I don't remember. If not Prolog, then what would be the best way to do this? I am interested in FOSS.

I wish there was a way to search for my comments, it sucks that I would have to paginate. I left a lot of comments.

View on HN

Yes, you could do this and it's likely it'll turn out as rather nice and decently performant code. You would, however, most likely run into the problem of finding people to maintain it that are willing to learn. Most Prolog teaching material is quite abstract in the sense that it mainly teaches the language and its tricks, not so much applications, though there are of course a lot of FOSS and example applications to look at.

In practice you would have to write documentation that basically turns into a course on constraint solving in Prolog. There are footguns and somewhat advanced techniques involving control over the execution strategy that are going to trip up newcomers. You'll also have to figure out how to interface with a Prolog implementation.

A compromise might be to use bindings for Z3 or something like the Timefold solver, https://timefold.ai/open-source-solver. Either way it's a good idea to spend some time playing around with Scryer, https://www.scryer.pl/, and Markus Triska's crash course, https://www.metalevel.at/prolog. SWI-Prolog has more conveniences that might make it more suitable for practical applications, but being used to them might make it harder to adapt to e.g. Scryer, Tau or some other implementation.

There's also the Mercury language, it's weirder but also very interesting, https://mercurylang.org/.

Edit: Some people swear by Picat but I have very little experience with it, http://picat-lang.org/.

You could have a look at the potassco suite[0]. It is a grounder and solver for Answer Set Programming (ASP). ASP is a form of Logic Programming.

[0] https://potassco.org/

I will take a look at it. Are you familiar with it, an example or a snippet would come in handy, but I may just ask Claude (if it even knows about Potassco).

ASP is optimized for combinatorial problems. Basically, you list the parts that are variable, and the constraints, the answers are given by the solver. Have a look at the documentation[0]. Here is an example:

    % Each shift needs a nurse).
    1 { shift_nurse(Shift, Nurse): nurse(Nurse) } 1 :- shift(shift).

    % It cannot be that a nurse does two shifts in a row.
    :- nurse(Nurse), shift_nurse(Shift1,Nurse),shift_nurse(Shift2,Nurse), Shift1 + 1 = Shift2.

[0] https://potassco.org/doc/start/

Thanks.

Found the original comment: https://news.ycombinator.com/item?id=41756679

Would this still work with ASP?

Yes, but honestly if you can use specialized software instead of writing your own, do so. Scheduling problems become very hairy quite quickly. For ASP, there is also sCASP that is the current flagship application of SWI Prolog.

yes[1][2]. You can write Prolog schedulers with arbitrary constraints.

[1]: https://www.metalevel.at/prolog/timetabling/

[2]: https://github.com/mthom/scryer-prolog/discussions/2519

So something like this: https://news.ycombinator.com/item?id=41756679 can be created using this?

Prolog is definitely the tool for this. I created an entire year's schedule for teachers a decade ago without a sweat. Maybe remove some constraints and try to debug which one is causing the problem.

Is it open source? Is the code available anywhere?

Oh no, it is in an undergrad thesis probably rotting in some library.

Try Z3

Reply on news.ycombinator.com