ACOF Write a Program Activity

Prolog:Test files:
testall :test1,
\+ test2,
\+ test3,
\+ test4,
\+ test5,
\+ test6,
test7.
test1 :-
% OK
assignment_ok(
[[abby, ethan, connor, gabriel, zoe],
[sara, gabriel, jasmine, mia, tyler],
[abby, sara, jasmine, zoe, lucas]],
[[abby,
1,
0,
2],
[connor,
0,
1,
3],
[ethan,
1,
1,
1],
[gabriel,
1,
1,
2],
[jasmine,
0,
2,
3],
[lucas,
0,
0,
3],
[mia,
0,
1,
3],
[sara,
1,
1,
2],
[tyler,
0,
1,
2],
[zoe,
0,
2,
2]]
).
test2 :-
% sara works twice in shift 2
assignment_ok(
[[abby, ethan, connor, gabriel, zoe],
[sara, sara, jasmine, mia, tyler],
[abby, gabriel, jasmine, zoe, lucas]],
[[abby,
1,
0,
2],
[connor,
0,
1,
3],
[ethan,
1,
1,
1],
[gabriel,
1,
1,
2],
[jasmine,
0,
2,
3],
[lucas,
0,
0,
3],
[mia,
0,
1,
3],
[sara,
1,
1,
2],
[tyler,
0,
1,
2],
[zoe,
0,
2,
2]]
).
test3 :-
% zoe works twice in shift 1
assignment_ok(
% and zoe works too many shifts
[[abby, ethan, zoe, connor, zoe],
[sara, gabriel, jasmine, mia, tyler],
[abby, sara, jasmine, gabriel, zoe]],
[[abby,
1,
0,
2],
[connor,
0,
1,
3],
[ethan,
1,
1,
1],
[gabriel,
1,
1,
2],
[jasmine,
0,
2,
3],
[lucas,
0,
0,
3],
[mia,
0,
1,
3],
[sara,
1,
1,
2],
[tyler,
0,
1,
2],
[zoe,
0,
2,
2]]
).
test4 :-
% lucas can’t be a lifeguard
assignment_ok(
[[lucas, ethan, connor, gabriel, zoe],
[sara, gabriel, jasmine, mia, tyler],
[abby, sara, jasmine, zoe, lucas]],
[[abby,
1,
0,
2],
[connor,
0,
1,
3],
[ethan,
1,
1,
1],
[gabriel,
1,
1,
2],
[jasmine,
0,
2,
3],
[lucas,
0,
0,
3],
[mia,
0,
1,
3],
[sara,
1,
1,
2],
[tyler,
0,
1,
2],
[zoe,
0,
2,
2]]
).
test5 :-
% connor doesn’t have enough hours
assignment_ok(
[[abby, ethan, lucas, gabriel, zoe],
[sara, gabriel, jasmine, mia, tyler],
[abby, sara, jasmine, zoe, lucas]],
[[abby,
1,
0,
2],
[connor,
0,
1,
3],
[ethan,
1,
1,
1],
[gabriel,
1,
1,
2],
[jasmine,
0,
2,
3],
[lucas,
0,
0,
3],
[mia,
0,
1,
3],
[sara,
1,
1,
2],
[tyler,
0,
1,
2],
[zoe,
0,
2,
2]]
).
test6 :-
% abby has too many hours
assignment_ok(
[[abby, ethan, connor, gabriel, zoe],
[abby, gabriel, jasmine, mia, tyler],
[abby, sara, jasmine, zoe, lucas]],
[[abby,
1,
0,
2],
[connor,
0,
1,
3],
[ethan,
1,
1,
1],
[gabriel,
1,
1,
2],
[jasmine,
0,
2,
3],
[lucas,
0,
0,
3],
[mia,
0,
1,
3],
[sara,
1,
1,
2],
[tyler,
0,
1,
2],
[zoe,
0,
2,
2]]
).
test7 :-
% OK
assignment_ok(
[[jacob, alex, hannah, isabella, emma],
[alex, emma, hannah, isabella, jacob],
[jacob, emma, alex, isabella, hannah]],
[[alex,
1,
1,
3],
[emma,
1,
1,
3],
[hannah,
0,
1,
3],
[isabella,
0,
1,
3],
[jacob,
1,
1,
3]]
).
Haskell
Test files:
import Swim
test1 = — ok
assignment_ok [[“abby”, “ethan”, “connor”, “gabriel”, “zoe”],
[“sara”, “gabriel”, “jasmine”, “mia”, “tyler”],
[“abby”, “sara”, “jasmine”, “zoe”, “lucas”]]
[(“abby”, 1, 0, 2),
(“connor”, 0, 1, 3),
(“ethan”, 1, 1, 1),
(“gabriel”, 1, 1, 2),
(“jasmine”, 0, 2, 3),
(“lucas”, 0, 0, 3),
(“mia”, 0, 1, 3),
(“sara”, 1, 1, 2),
(“tyler”, 0, 1, 2),
(“zoe”, 0, 2, 2)]
test2 = — sara works twice in shift 2
assignment_ok [[“abby”, “ethan”, “connor”, “gabriel”, “zoe”],
[“sara”, “sara”, “jasmine”, “mia”, “tyler”],
[“abby”, “sara”, “jasmine”, “zoe”, “lucas”]]
[(“abby”, 1, 0, 2),
(“connor”, 0, 1, 3),
(“ethan”, 1, 1, 1),
(“gabriel”, 1, 1, 2),
(“jasmine”, 0, 2, 3),
(“lucas”, 0, 0, 3),
(“mia”, 0, 1, 3),
(“sara”, 1, 1, 2),
(“tyler”, 0, 1, 2),
(“zoe”, 0, 2, 2)]
test3 = — zoe works twice in shift 1
assignment_ok [[“abby”, “ethan”, “zoe”, “connor”, “zoe”],
[“sara”, “gabriel”, “jasmine”, “mia”, “tyler”],
[“abby”, “sara”, “jasmine”, “zoe”, “lucas”]]
[(“abby”, 1, 0, 2),
(“connor”, 0, 1, 3),
(“ethan”, 1, 1, 1),
(“gabriel”, 1, 1, 2),
(“jasmine”, 0, 2, 3),
(“lucas”, 0, 0, 3),
(“mia”, 0, 1, 3),
(“sara”, 1, 1, 2),
(“tyler”, 0, 1, 2),
(“zoe”, 0, 2, 2)]
test4 = — lucas can’t be a lifeguard
assignment_ok [[“lucas”, “ethan”, “connor”, “gabriel”, “zoe”],
[“sara”, “gabriel”, “jasmine”, “mia”, “tyler”],
[“abby”, “sara”, “jasmine”, “zoe”, “lucas”]]
[(“abby”, 1, 0, 2),
(“connor”, 0, 1, 3),
(“ethan”, 1, 1, 1),
(“gabriel”, 1, 1, 2),
(“jasmine”, 0, 2, 3),
(“lucas”, 0, 0, 3),
(“mia”, 0, 1, 3),
(“sara”, 1, 1, 2),
(“tyler”, 0, 1, 2),
(“zoe”, 0, 2, 2)]
test5 = — connor doesn’t have enough hours
assignment_ok [[“abby”, “ethan”, “lucas”, “gabriel”, “zoe”],
[“sara”, “gabriel”, “jasmine”, “mia”, “tyler”],
[“abby”, “sara”, “jasmine”, “zoe”, “lucas”]]
[(“abby”, 1, 0, 2),
(“connor”, 0, 1, 3),
(“ethan”, 1, 1, 1),
(“gabriel”, 1, 1, 2),
(“jasmine”, 0, 2, 3),
(“lucas”, 0, 0, 3),
(“mia”, 0, 1, 3),
(“sara”, 1, 1, 2),
(“tyler”, 0, 1, 2),
(“zoe”, 0, 2, 2)]
test6 = — abby has too many hours
assignment_ok [[“abby”, “ethan”, “connor”, “gabriel”, “zoe”],
[“abby”, “gabriel”, “jasmine”, “mia”, “tyler”],
[“abby”, “sara”, “jasmine”, “zoe”, “lucas”]]
[(“abby”, 1, 0, 2),
(“connor”, 0, 1, 3),
(“ethan”, 1, 1, 1),
(“gabriel”, 1, 1, 2),
(“jasmine”, 0, 2, 3),
(“lucas”, 0, 0, 3),
(“mia”, 0, 1, 3),
(“sara”, 1, 1, 2),
(“tyler”, 0, 1, 2),
(“zoe”, 0, 2, 2)]
test7 = — ok
assignment_ok
[[“jacob”, “alex”, “hannah”, “isabella”, “emma”],
[“alex”, “emma”, “hannah”, “isabella”, “jacob”],
[“jacob”, “emma”, “alex”, “isabella”, “hannah”]]
[(“alex”, 1, 1, 3),
(“emma”, 1, 1, 3),
(“hannah”, 0, 1, 3),
(“isabella”, 0, 1, 3),
(“jacob”, 1, 1, 3)]
General problem description
You will write a program which checks a work assignment against a collection of
constraints to see whether the work assignment is acceptable.
At the Seagull Swimming Pool, there are three work shifts during the day: 12:002:00, 2:00-4:00, and 4:00-6:00. During each shift, five workers are needed: two
lifeguards, two people to run the snack bar, and one person to sit at the front desk.
No worker can do more than one job during a single shift, though workers can
work multiple shifts during the day.
Some of the employees have the qualifications to be a lifeguard, and only qualified
lifeguards are allowed to work as lifeguards. Anyone can work at the snack bar or
front desk.
Each of the employees has a minimum and maximum number of shifts that they
should work during the day. These numbers are different for different employees.
The input to your program will be a proposed job assignment (the two lifeguards,
the two snack bar workers, and the front desk worker, for each of the three shifts),
followed by a list of employees and their work constraint information. The
employees and their information will be specified by an employee’s name, then a
number (1 or 0) indicating whether the person is qualified to be a lifeguard (1=yes,
0=no), then two nonnegative integers indicating the minimum and maximum
number of shifts the person can work. For example:
Olivia 1 0 2
indicates that Olivia is qualified to be a lifeguard and should work between 0 and 2
shifts — that is, she should work 0, 1, or 2 shifts.
Michael 0 2 3
indicates that Michael is not qualified to be a lifeguard and should work either 2 or
3 shifts.
Nick 1 2 2
indicates that Nick is qualified to be a lifeguard and should work exactly 2 shifts.
The output will be a message indicating whether the proposed job assignment is
acceptable.
Sample calculations
Example 1:
Input:
Abby Ethan Connor Gabriel Zoe
Sara Gabriel Jasmine Mia Tyler
Abby Sara Jasmine Zoe Lucas
10
Abby
1
Connor 0
Ethan
1
Gabriel 1
Jasmine 0
Lucas
0
Mia
0
Sara
1
Tyler
0
Zoe
0
0
1
1
1
2
0
1
1
1
2
2
3
1
2
3
3
3
2
2
2
Output:
Acceptable
Rationale:
The proposed work assignment says that
In shift 1, Abby and Ethan are lifeguards, Connor and Gabriel work the snack bar,
and Zoe sits at the front desk.
In shift 2, Sara and Gabriel are lifeguards, Jasmine and Mia work the snack bar,
and Tyler sits at the front desk.
In shift 3, Abby and Sara are lifeguards, Jasmine and Zoe work the snack bar, and
Lucas sits at the front desk.
The number 10 means that there are 10 employees in the list that follows.
Abby is qualified to be a lifeguard, and should work between 0 and 2 shifts,
inclusive.
Connor is not qualified to be a lifeguard, and should work between 1 and 3 shifts,
inclusive.
Ethan is qualified to be a lifeguard, and should work exactly 1 shift.
Everyone has been assigned to jobs that they can perform, and everyone has been
assigned the correct number of work shifts, so the assignment is acceptable.
Example 2:
Input:
Lucas Ethan Connor Gabriel Zoe
Sara Gabriel Jasmine Mia Tyler
Abby Sara Jasmine Zoe Lucas
10
Abby
1
0
2
Connor 0
1
3
Ethan
1
1
1
Gabriel 1
1
2
Jasmine 0
2
3
Lucas
Mia
Sara
Tyler
Zoe
0
0
1
0
0
0
1
1
1
2
3
3
2
2
2
Output:
Not Acceptable
Rationale:
This is the same input as in example 1, except that Lucas has been assigned to be a
lifeguard in shift 1 instead of Abby. The assignment is unacceptable because Lucas
is not qualified to be a lifeguard.
Example 3:
Input:
Abby Ethan Zoe Connor Zoe
Sara Gabriel Jasmine Mia Tyler
Abby Sara Jasmine Zoe Lucas
10
Abby
1
0
2
Connor 0
1
3
Ethan
1
1
1
Gabriel 1
1
2
Jasmine 0
2
3
Lucas
0
0
3
Mia
0
1
3
Sara
1
1
2
Tyler
0
1
2
Zoe
0
2
2
Output:
Not Acceptable
Rationale:
This is similar to example 1, but Zoe has been assigned two jobs in shift 1, so the
assignment is unacceptable.
Example 4:
Input:
Abby Ethan Lucas Gabriel Zoe
Sara Gabriel Jasmine Mia Tyler
Abby Sara Jasmine Zoe Lucas
10
Abby
1
0
2
Connor 0
Ethan
1
Gabriel 1
Jasmine 0
Lucas
0
Mia
0
Sara
1
Tyler
0
Zoe
0
1
1
1
2
0
1
1
1
2
3
1
2
3
3
3
2
2
2
Output:
Not Acceptable
Rationale:
This is similar to example 1, except that Connor has not been assigned enough
shifts. He should work between 1 and 3 shifts, but he has been assigned 0 shifts.
The assignment is unacceptable.
A note on I/O format
The exact format of the input and output will be slightly different for the four
different languages, to make the input and output as easy as possible in each
different language. The four input/output specifications for the four different
languages are given below.
In all versions of the problem, assume that the input will be correctly formatted,
and that all numbers will be in the ranges given in the problem specification; your
program does not need to check for formatting errors.
Grading
There are three different major tasks the program must perform, beyond the basics
of reading the input:
1. Determining whether everyone who has been assigned to be a lifeguard is
qualified to be a lifeguard. This is worth 15 points of the assignment.
2. Determining whether anyone has been assigned two jobs in the same shift.
This is worth 10 points of the assignment.
3. Determining whether everyone has been assigned a correct number of shifts.
This is worth 15 points of the assignment.
Note that each of these tasks is independent of the others. If you are able (for
example) to complete tasks #2 and #3 but not #1, and your program is otherwise
correct, with good style and comments, then the grade will be 85. If you get stuck
on one or two of the tasks, I encourage you to complete as many of the tasks as you
can and turn in the program you have created.
10 points of the assignment will be devoted to style and format issues, including
the following:
•
•
•
•
•
•
Have you used good variable names and indentation?
Have you added appropriate comments? In Scheme and Prolog, you should
have a comment for each function or predicate, in addition to any other
explanatory comments that you need. In Ada and Python, fewer comments
are necessary, but you should still comment anything that is unclear.
Did you include a comment with your name?
If you are working in a team, did you include a comment with all your
teammates’ names?
Did you follow the specified input format?
Did you follow the specified output format? For the Scheme, Prolog, and
Python assignments, did you return a value rather than merely printing a
value?
Even in languages that are new and unfamiliar, you should do your best to follow
good style conventions and to follow the I/O specifications in the problem
description.
The remaining 50 points of the assignment are devoted to the basics of writing
programs in the language: Does your program attempt to solve the assigned
problem? Are there syntax errors? Does the program run without crashing? and so
on.
Prolog problem
Write a Prolog program to solve the problem described above. Define a
predicate assignment_ok(+Assignment, +Employees). Assignment is a list of three
sub-lists, one for each shift. Each sub-list contains the work assignment for that
shift: two names for lifeguards, followed by two for the snack bar, followed by one
for the front desk. Employees is a list of sub-lists; each sub-list contains an
employee’s name, then a number (1 or 0) indicating whether the person is qualified
to be a lifeguard (1=yes, 0=no), then two nonnegative integers indicating the
minimum and maximum number of shifts the person can work.
Predicate assignment_ok should succeed if the work assignment is acceptable, and
fail if the work assignment is not acceptable.
You may assume that the Assignment and Employees lists will be in the correct
format when the function is called; you do not have to error-check for a non-list or
an incorrectly formed list. In your program, you may write and call any additional
predicates that are helpful in the computation.
Examples:
?- assignment_ok(
[[abby, ethan, connor, gabriel, zoe],
[sara, gabriel, jasmine, mia, tyler],
[abby, sara, jasmine, zoe, lucas]],
[[abby,
[connor,
[ethan,
[gabriel,
[jasmine,
[lucas,
[mia,
[sara,
[tyler,
[zoe,
1,
0,
1,
1,
0,
0,
0,
1,
0,
0,
0,
1,
1,
1,
2,
0,
1,
1,
1,
2,
2],
3],
1],
2],
3],
3],
3],
2],
2],
2]] ).
should succeed, and
?- assignment_ok(
[[lucas, ethan, connor, gabriel, zoe],
[sara, gabriel, jasmine, mia, tyler],
[abby, sara, jasmine, zoe, lucas]],
[[abby,
[connor,
[ethan,
[gabriel,
[jasmine,
[lucas,
[mia,
[sara,
[tyler,
[zoe,
1,
0,
1,
1,
0,
0,
0,
1,
0,
0,
0,
1,
1,
1,
2,
0,
1,
1,
1,
2,
2],
3],
1],
2],
3],
3],
3],
2],
2],
2]] ).
should fail.
Test suite for Prolog
The test suite for the Prolog program is on elvis at ~nlt/testprolog . This file
defines predicates test1, test2, test3, test4, test5, test6 and test7. It also defines
predicate testall, which calls all the other test functions. Load this file into the
Prolog interpreter along with your homework program file, run your homework
program on predicate testall, and capture this sample run with script.
Note that, as with Scheme, you may wish to call the individual predicates test1,
test2, etc., directly while developing and debugging the program.
Haskell
Write a Haskell program to solve the programming, Define a
function assignment_ok which takes two
parameters, Assignment and Employees. Assignment is a list of three sub-lists, one
for each shift. Each sub-list contains the work assignment for that shift: two names
for lifeguards, followed by two for the snack bar, followed by one for the front
desk. Employees is a list of tuples; each tuple contains an employee’s name, then a
number (1 or 0) indicating whether the person is qualified to be a lifeguard (1=yes,
0=no), then two nonnegative integers indicating the minimum and maximum
number of shifts the person can work.
You may assume that the Assignment and Employees lists will be in the correct
format when the function is called; you do not have to error-check for a non-list or
an incorrectly formed list. In your program, you may write and call any additional
functions that are helpful in the computation.
Examples:
assignment_ok [[“abby”, “ethan”, “connor”, “gabriel”, “zoe”],
[“sara”, “gabriel”, “jasmine”, “mia”, “tyler”],
[“abby”, “sara”, “jasmine”, “zoe”, “lucas”]]
[(“abby”, 1, 0, 2),
(“connor”, 0, 1, 3),
(“ethan”, 1, 1, 1),
(“gabriel”, 1, 1, 2),
(“jasmine”, 0, 2, 3),
(“lucas”, 0, 0, 3),
(“mia”, 0, 1, 3),
(“sara”, 1, 1, 2),
(“tyler”, 0, 1, 2),
(“zoe”, 0, 2, 2)]
should return True, and
assignment_ok [[“abby”, “ethan”, “connor”, “gabriel”, “zoe”],
[“sara”, “sara”, “jasmine”, “mia”, “tyler”],
[“abby”, “sara”, “jasmine”, “zoe”, “lucas”]]
[(“abby”, 1, 0, 2),
(“connor”, 0, 1, 3),
(“ethan”, 1, 1, 1),
(“gabriel”, 1, 1, 2),
(“jasmine”, 0, 2, 3),
(“lucas”, 0, 0, 3),
(“mia”, 0, 1, 3),
(“sara”, 1, 1, 2),
(“tyler”, 0, 1, 2),
(“zoe”, 0, 2, 2)]
should return False.
Test suite for Haskell:
Name your program file Swim.hs
Near the top of your program, before any other Haskell code, include the line
module Swim (assignment_ok) where
This line will allow your code to be called properly by the test file.
How to create a sample run: A test suite for this program is located on elvis
at ~nlt/testhaskell.hs . This file contains definitions of functions test1, test2, …
, test7, which call assignment_ok with seven different sample inputs. The
comments in the testhaskell.hs file give the correct return values for each of the
function calls, so you can check to see whether your program is correct.
Copy testhaskell.hs to the directory that contains your Haskell program Swim.hs .
Start script . Start the Haskell interpreter and load function testhaskell.hs . Call
functions test1, test2, … , test7. End script. You now have a typescript file
containing your test run.
Collect your program file and the typescript file into a directory called HaskellHW,
and turn in the HaskellHW directory using these directions.