Glad, I was able to be helpful.
Sure, what is the other task, if i know how to do it and can talk you through it … why not.
We have to do staff planning for the next day only using prolog and all the data and predicates we alreadye have.
So we have to assign personal to the airplaines so the airplaines have the required amount of people in order to start.
Constraints:
1 crew member per airplain
crew members can not change airplanes during the day
every crew has two pilotes with the necessary licenses and the amount of cabin crew which is needed for the aircraft and atleast 1 pursuer
The amount of overtime is also required to take into consideration.
crew members 7 and 9 , 2 and 10 are allowed to fly together meaning they have to fly together or they have to stay at the airport together.
Aircrafts from the type 737-max aren’t allowed to fly.
we have to write following predicates:
generatecrew([List], flighttype):- Generate a permutation of the possible crew layout regarding the constraints. Keep in mind that every solution is to put out max once, i.e [1,2,3,4] and [1,3,2,4] are the same solutions.
checkworkinghours(crewNr, flighttype):- Checks if a Crew member has enough workinghours left, so he can work a list of routes. To simplyfy the problem only the time of the aircraft flying is needed. ( no need to subtract the 3 hours)
validcoworker([crewNr1,…,crewNrN]):- checks if the constraints of the crew members are holding.
noflightban(flighttype):- Checks if the aircraft is allowed to fly and has no ban.
generateStaffplan(List,[flighttype1,flighttypeN]):- Outputs an list of the staff assigned to the aircrafts. The list has to fulfill the constraints. The predicate should output every solution possible using backtracking, but every solution should put out only once.
Thanks @j4n_bur53. I knew that _17492 was the mistake but I didn’t know how to correct it. As far as I understand the mistake it had something to do with the recursion because I had no recursion baseline. So when I reached the end of the recursion it didn’t resolve with the baseline. Instead of resolving it with 0 it kept the anonymous variable which resultet in the offending variable in the call: (12).
Atleast thats my understanding ^^
What do you mean by rule?
If I run your code
I get this error again.
[trace] ?- travel_time([1,2],X).
Call: (10) travel_time([1, 2], _5258) ? creep
^ Call: (11) apply:maplist(fetch_time, [1, 2], 5742) ? creep
Call: (12) apply:maplist([1, 2], _5742, user:fetch_time) ? creep
Call: (13) fetch_time(1, _5848) ? creep
Call: (14) route(1, _5966, _5968, _5900, _5902, _5974) ? creep
Exit: (14) route(1, ‘FRA’, ‘LHR’, 15:10, 18:30, ‘DE-AAB’) ? creep
Call: (14) duration_time(15:10, 18:30, _6076) ? creep
Call: (15) 15<18 ? creep
Exit: (15) 15<18 ? creep
Call: (15) _6156 is 1560+10 ? creep
Exit: (15) 910 is 1560+10 ? creep
Call: (15) _6266 is 1860+30 ? creep
Exit: (15) 1110 is 1860+30 ? creep
Call: (15) _6376 is 1110-910 ? creep
Exit: (15) 200 is 1110-910 ? creep
Exit: (14) duration_time(15:10, 18:30, 200) ? creep
Exit: (13) fetch_time(1, 5848) ? creep
Call: (13) apply:maplist([2], _5850, user:fetch_time) ? creep
Call: (14) fetch_time(2, _6626) ? creep
Call: (15) route(2, _6744, _6746, _6678, _6680, _6752) ? creep
Exit: (15) route(2, ‘LHR’, ‘FRA’, 20:45, 23:50, ‘DE-AAB’) ? creep
Call: (15) duration_time(20:45, 23:50, _6854) ? creep
Call: (16) 20<23 ? creep
Exit: (16) 20<23 ? creep
Call: (16) _6934 is 2060+45 ? creep
Exit: (16) 1245 is 2060+45 ? creep
Call: (16) _7044 is 2360+50 ? creep
Exit: (16) 1430 is 2360+50 ? creep
Call: (16) 7154 is 1430-1245 ? creep
Exit: (16) 185 is 1430-1245 ? creep
Exit: (15) duration_time(20:45, 23:50, 185) ? creep
Exit: (14) fetch_time(2, 6626) ? creep
Call: (14) apply:maplist([], 6628, user:fetch_time) ? creep
Exit: (14) apply:maplist([], [], user:fetch_time) ? creep
Exit: (13) apply:maplist([2], [6626], user:fetch_time) ? creep
Exit: (12) apply:maplist([1, 2], [_5848, _6626], user:fetch_time) ? creep
^ Exit: (11) apply:maplist(user:fetch_time, [1, 2], [_5848, _6626]) ? creep
Call: (11) lists:sum_list([_5848, _6626], _5258) ? creep
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR: [13] _8346 is 0+_8354
ERROR: [12] lists:sum_list([_8392,_8398],0,_8388) at c:/program files/swipl/library/lists.pl:593
ERROR: [11] lists:sum_list([_8436,_8442],_8432) at c:/program files/swipl/library/lists.pl:588
ERROR: [10] travel_time([1,2],_8470) at c:/users/blabl/desktop/aufgabe1.pl:121
ERROR: [9] toplevel_call(user:user: …) at c:/program files/swipl/boot/toplevel.pl:1113
Exception: (11) lists:sum_list([_5848, _6626], _5258) ?
creep
Exception: (10) travel_time([1, 2], _5258) ?
creep
But just to clearify my understanding of the code you sent.
You are calling travel_time with a list and a variable for the total flighttime.
Maplist calls fetch_time upon every element in the list ‘HopList’ and stores it in FlighttimeList.
After that you sum it up in sum_list and output totalflighttime.
True, you can use meta predicates …
But I suspect that they are harder to explain and digest when first trying to get the head around analyzing a problem the relational (Prolog) way, and then translate these into correct syntax with all its subtleties that differ from conventional programming languages – such as Arguments can be input and output and the like.
So, to get introduced its better to keep things less meta, or at least so, goes my thinking …
Edit:
Also, to add – since this is a homework assignment, I didn’t feel comfortable just posting a solution, but wanted to walk through the thinking process – and with meta predicates its a bit harder to do – at least for me – but, perhaps its something worthwhile to work out – how to explain the thinking process underlying the creation of meta-predicate supported solutions.
Dan
The problem description does remind me of the initial “didactic” example I posted early on (repeated below).
Essentially, a_number(X) is a generator – it “generates” through backtracking all the numbers, while the condition X > N is a constraint, which failure, after a binding for X is selected, causes backtracking, and the binding of X to a different value (hence generator).
In SWI Prolog there is a predicate to generate permutations: permutation/2
So, i guess, I would start with predicates that describe the different possible resources assignable via predicates and their variables, whose bindings get permuted, upon backtracking (just like a_number above), and the writen predicates that represent the constraints that would be tested, and let backtracking find the right permutation that satisfy the constraints.
As an aside SWI-Prolog has a constraint solving library, but this exercise seems to call for a “native” Prolog solution.
a_number(1).
a_number(2).
a_number(3).
a_number(4).
a_number(5).
exists_greater_than_n(X, N) :-
a_number(X), % there exists a number X
X >N.
I think this is exactly the point: a seasoned programmer vs. someone learning the ropes of logic programming.
And, it seems that elegant meta predicate based solutions are then only the starting point, when it comes to writing performant code.
At least, according to what I read in O’Kefee, you can describe solutions elegantly using meta predicates, but then you unfold them to make them performant – eliminating meta predicates, creating direct calls, adding context predicates and accumulators as needed.
So, understanding both styles is important – and, it seems to me that getting introduced with the latter, involves significant less cognitive gap, when coming from traditional programming languages.
It wasn’t just natural language, but the use of natural language to describe the problem in a declarative / definitional way – a problem described by breaking it down into sub-problems, rather than a step by step procedure to solve it – as would have been the case if you would analyse this for imperative language.
My hope was that you can then translate the problem descriptions directly into a prolog formalization.
Dan
p.s. Btw, i don’t see in the meta-predicate based solution handing of the exception case – when the arrival of the prior hop is different to the departure of the next hop, how do you pass along the prior arrival during meta calls.
Could you add this …
I have another basic question.
If I have the following
number(1).
number(2).
number(3).
number(4).
number(5).
is there any predicate that adds all of them to a list?
I didn’t found any solution that worked.
I will try to do that to clarify what I have done^^ ( If I can recover the earlier stage of my doings )
Have a nice evening and many many thanks
Skonnky
Just as an aside,
In Prolog one can process lists explicity or implicitly.
Explicit list processing is something like the following:
number(1).
number(2).
number(3).
number(4).
number(5).
exists_greater_than_n(X, N) :-
findall(X, a_number(X), X_List),
find_is_greater(X_List, N).
find_is_greater([First | Rest], N) :-
First > N
;
find_is_greater(Rest, N).
or, one can retrieve the list via backtracking (as before)
exists_greater_than_n(X, N) :-
a_number(X), % retrieves each a_number through backtracking
X >N.
It depends on whether holding a list is needed as part of the solution.
Searching a cyclic graph is a classic example, where you do want to hold a list rather than rely on backtracking is when the list is built up during solution searching, rather than given as facts.
To ensure that the cycles in the graph don’t cause an infinite recursion, one approach is to pass around a visited list of nodes, as an accumulator.
(Btw, the tabling feature included in swi-prolog offers an alternative approach to dealing with cycling data, without the need for keeping a visited list around – whereby internally a table is generated of already computed / visited nodes, which are then retrieved without further processing, thereby eliminating the end-less recursive call with a table-based retrieval case).
Dan
Hello fellow mentors,
I have a question about using permutation/2 and solving constraints with permutation/2 .
What do I need to change in order to have only results without an ‘a’ ath the beginning?
dosth(X):-
permutation([a,b,c],X),
sally(X)
.
sally([Head|Tail]):- (Head == 'a',false).this,seems to have worked (on the command line):
permutation([a,b,c],X), [H|_]=X, \+H=a.
X = [b, a, c],
H = b ;
X = [b, c, a],
H = b ;
X = [c, a, b],
H = c ;
X = [c, b, a],
H = c ;
false.
The number of permutations increases very quickly with the size of the list, so a better approach is to have delayed tests, which cut off permutations more quickly (this becomes important when you have more than 3 items in the list). Notice the order of goals – the dif/2 goal is before the permutation/2 goal, so that as soon as H is sufficiently instantiated, the dif/2 test is done.
?- X=[H|_], dif(H,a), permutation([a,b,c],X).
X = [b, a, c],
H = b ;
X = [b, c, a],
H = b ;
X = [c, a, b],
H = c ;
X = [c, b, a],
H = c ;
false.
In this particular case, using delayed tests doesn’t help much (there’s overhead in delaying a goal); but in a situation where very few permutations meet the test, it can be a big winner (you can see this for yourself, by making the test more restrictive).
?- List=[a,b,c,d,e,f,g,h,i], time(findall(X, (X=[H|_], dif(H,a), permutation(List,X)), All)), length(All, AllLen).
% 2,630,693 inferences, 0.406 CPU in 0.407 seconds (100% CPU, 6475552 Lips)
List = [a, b, c, d, e, f, g, h, i],
All = [[b, a, c, d, e, f, g, h|...], [b, a, c, d, e, f, g|...], [b, a, c, d, e, f|...], [b, a, c, d, e|...], [b, a, c, d|...], [b, a, c|...], [b, a|...], [b|...], [...|...]|...],
AllLen = 322560.
?- List=[a,b,c,d,e,f,g,h,i], time(findall(X, (permutation(List,X), X=[H|_], H\=a), All)), length(All, AllLen).
% 3,644,685 inferences, 0.438 CPU in 0.444 seconds (99% CPU, 8330709 Lips)
List = [a, b, c, d, e, f, g, h, i],
All = [[b, a, c, d, e, f, g, h|...], [b, a, c, d, e, f, g|...], [b, a, c, d, e, f|...], [b, a, c, d, e|...], [b, a, c, d|...], [b, a, c|...], [b, a|...], [b|...], [...|...]|...],
AllLen = 322560.
1 Like
that’s great to know, thanks.
i am looking at this and i am wondering, where exactly the saving happens.
Can you elaborate a bit on this.
The permutation code (from library(lists)) is:
perm([], []).
perm(List, [First|Perm]) :-
select(First, List, Rest), % backtracks through all elements of List
perm(Rest, Perm).
and we run it with these goals:
dif(H, a), perm([a,b,c,d,e,f], [H|_])
(We actually do X=[H|_], dif(H,a), perm([a,b,c,d,e,f], X) because we want the entire permutation in X.)
If you do generate & test, then you have to generate all the possibilities, which is n! (n-factorial).
If you do delayed-test & generate, then the permutation backtracking can be “short circuited”. For example, when select(First,List,Rest) instantiates First, if that is the first element of the resulting permutation (which has been unified to H), then the test dif(H,a) wakes up and runs; if the selected item was a, then that causes the select/3 to fail and the following call to perm/2 isn’t done.
A better example of this is a logic puzzle, where there are a large number of tests, which can greatly prune the number of permutations that are generated. Another way of thinking about this is that you’re generating a proof tree – as soon as one of the constraints fails, there’s no point in generating any of the potential proofs below that point.
Or a sudoku solver can generate all possible digits for each square and then use an all_distinct/1 constraint to remove a potential solution (and all solutions that depend on it) if another item already has that value.
What does this do?
Do you have any tips on how to solve the following problem? I know that permutation is the right thing to do but I dont know how to instantiated the length of the list for the args of permutation
permutation([ amount of crew ], X
amount of crew differs in length from 4 to 5 and only holds integers
The task / problem with constraints and explanation ( I already wrote some predicates if you need the codes let me know)
So we have to assign personal to the airplaines so the airplaines have the required amount of people in order to start.
Constraints:
1 crew member per airplain
crew members can not change airplanes during the day
every crew has two pilotes with the necessary licenses and the amount of cabin crew which is needed for the aircraft and atleast 1 pursuer
The amount of overtime is also required to take into consideration.
crew members 7 and 9 , 2 and 10 are allowed to fly together meaning they have to fly together or they have to stay at the airport together.
Aircrafts from the type 737-max aren’t allowed to fly.
we have to write following predicates:
generatecrew([List], flighttype):- Generate a permutation of the possible crew layout regarding the constraints. Keep in mind that every solution is to put out max once, i.e [1,2,3,4] and [1,3,2,4] are the same solutions.
Skonnky
https://www.swi-prolog.org/pldoc/doc_for?object=(%3D)/2
X=a
means, that X unifies with the symbol a, if X is already bound, then X=a only succeeds if X is bound to a.
\+
is a negation operator,
So, \+ X=a
means that trying to unify X with a succeeded, and hence, \+ X=a should fail.
Do you have any thoughts on my problem?
So we have to assign personal to the airplaines so the airplaines have the required amount of people in order to start.
Constraints:
1 crew member per airplain
crew members can not change airplanes during the day
every crew has two pilotes with the necessary licenses and the amount of cabin crew which is needed for the aircraft and atleast 1 pursuer
The amount of overtime is also required to take into consideration.
crew members 7 and 9 , 2 and 10 are allowed to fly together meaning they have to fly together or they have to stay at the airport together.
Aircrafts from the type 737-max aren’t allowed to fly.
we have to write following predicates:
generatecrew([List], flighttype):- Generate a permutation of the possible crew layout regarding the constraints. Keep in mind that every solution is to put out max once, i.e [1,2,3,4] and [1,3,2,4] are the same solutions.
Hi,
I will try to review tomorrow, i haven’t solved a constraint problem before, so its new to me as well. here are just some initial thoughts:
The problem seems over specified – or there is some tables missing – i don’t see a table with an airplane of the max 373. Also, no information about whether pilots are licensed or not.
I can see two types of aircrafts in the fleet, which fly twice a day, but the crew per aircraft is not changed during the day – so each day assignments are made only once per aircraft type.
I wonder if this simplification is allowed to be part of the code.
Also, whether knowledge of two aircrafts can be part of the code, or whether this should work for N aircrafts in a fleet as well.
One thought, i has is that beside permutation there is also a kind of partitioning of the list of people into several subsets – first, based on their role, and second across aircrafts.
How would one describe a partitioning of a set into subsets – if partitioning is fixed across two aircrafts, then append/3 could do it,
?- append(A, B, [1,2,3]).
A = [],
B = [1, 2, 3] ;
A = [1],
B = [2, 3] ;
A = [1, 2],
B = [3] ;
A = [1, 2, 3],
B = [] ;
false.
So, a simplified solution (perhaps just to get going) is to use append as the generator, and have each sublist generated be tested for constraint.
A more generalized solution would see to generate N partitioned subsets, where N is the number of aircrafts of different type in a fleet that travel during one day.
Before i start my day, I did a bit more thinking … here are a few more shared thoughts:
- Group 1: One starts with a full list of 18 employees,
- Group 2.1, Group 2.2, Group 2.3: these are then grouped into 3 distinct groups: pilots, flight attendants (steward/stewardess), pursuers.
There are exactly three groups, per problem, so this is fixed and can be encoded in a fixed way (e.g. via distinct predicates) in the solution
- Group 3: Then each day has a group of aircraft types that fly that day identified via the schedule.
The group of aircrafts flying per day is not fixed, since its defined as tuples in a table, so this group has to be represented dynamically, as part of some count, somehow.
Furthermore,
Group 3 represents are essentially the number of “buckets” into which, elements of group2.1, 2.2. and 2.3. are allocated into:
- finally, an allocation is checked for constraints.
So, overall from a generate and test approach, we want to first generate different sized allocations from, group 2.1, 2.2 and 2.3 into N buckets.
Btw, for some reason i keep thinking about powersets as something potentially useful here – it can represents different selections taken from a set that also vary in size.
So, if you can solve this, you have an generate piece of the puzzle worked out …
Edit:
Here are algorithms in Java to generate N sublists :
https://www.techiedelight.com/partition-list-multiple-sublists-java/
Dan
Sorry I cannot be more specific, but for allocation/scheduling problems there are some well established building blocks in library(clpfd). See serialized/2, cumulative/2. Not that these are easy to use, specially if you have never seen them applied in concrete examples. Programming with constraints requires experience about modelling, often it’s convenient to introduce some redundancy and map the problem to geometric 2d relations. See this answer (not mine, alas) for an example of the intuition needed to apply finite domains constraints into a specific problem.