CSCI 4430/6430 Programming Languages Fall 2019
Programming Assignment 3
This assignment is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other groups code. Do not put your code in a public directory or otherwise make it public. However, you may get help from the mentors, TAs, or the instructor. You are encouraged to use the Submitty Discussion Forum to post problems so that other students can also answer/see the answers.
This assignment will strengthen your understanding of logical and constraint based programming through application in either Prolog or Oz. You will be tasked with solving systems that have constraints specified in a subset of natural language.
Please be honest with your submitted code. Any solution that simply prints out the correct answer without performing calculations that lead to the correct answer will result in a zero for the entire assignment.
Part 1: Curious Set of Integers
This section serves as a warm up to get you used to working with Prolog/Oz under a constraint based programming model. You will be presented with a simple puzzle (representing a constraint programming problem) that you must solve.
Puzzle Description
The original version of this puzzle was posed by Martin Gardner in February 1967.
The integers 1, 3, 8, and 120 form a set with a remarkable property: the product of any two integers is one less than a perfect square. Find another set containing four unique numbers between 0 and 10000 that also has this property and it contains no numbers from the original set of {1, 3, 8, 120}.
Code Requirements
Your code should print the results to the standard output as comma separated values.
Example Output
$ 1,3,8,120
1
Part 2: Parsing Constraints and Building Interesting Sets
One of the advantages of logical programming is that parsing languages comes naturally from the compu- tational model. In this section you will be tasked with creating a parser for a specified grammar and using the resulting parse tree to solve a simple constraint programming problem.
The grammar that you will be using accepts sentences that define the constraint programming problem of finding a set of integers with specific properties, called interesting sets. Some examples of sentences that the grammar accepts are: Find a set of 2 odd integers that sum to 16 and Find a set of 2 even and 3 odd integers that multiply to 120. Note that this grammar accepts sentences that correspond to a constraint programming problem with no solutions: Find a set of 2 even in- tegers that sum to 3. To help make your search space smaller you can assume that each element in the set has a value between 0 and 128 inclusive. Note that the values in a set must be unique and their order does not matter.
Interesting Sets Grammar
S Findasetof IthatOptoNumber
I Even integers | Odd integers | Both integers Even Number even
Odd Number odd
Both Even and Odd
Op sum | multiply
Number 1|2|3|
Code Requirements
Your code should accept as input a string that defines the constraints of a particular interesting set of inte- gers. There are three possible types of output for your program depending on if the string is invalid in the grammar, there is no solution to the problem, or at least one solution exists:
Invalid input: $ Invalid String
No solution to the problem: $ No Solution
At least one solution exists: Comma separated list of values (shown in section below)
Example Input/Output
Input:
Find a set of 3 odd integers that sum to 15
Output:
$ 3,5,7
2
General Code Requirements
Each part of this assignment should have its own source code file named part x.oz or part x.pl (x = 1, 2). Output for each file should go to standard output and more detailed specifications may be found in the corresponding sections above.
Sample code has been provided on the PA3 website. This starter code takes as input a single string and then prints that string to standard output. In order to run the starting code follow the same instructions provided below in the Running Code sections.
Setting Up Oz
The most up to date version of Oz/Mozart (2.0) does not allow for constraint programming. Consequently, you are required to use Mozart 1.4.0 which only runs on 32-bit operating systems. Since most modern systems are 64-bit, we have created a virtual machine in the VirtualBox 6.0 provided student.ova file. This will provide you with an environment that already has Oz/Mozart 1.4.0 fully installed and ready to go. To log into the VM the first time the password is student and will remain that way unless you change it.
Running Oz Code
Your code will be run in the following way on Submitty:
$ ozc -c part 1.oz
$ ozengine part 1.ozf > part 1.txt
$ ozc -c part 2.oz
$ ozengine part 2.ozf Example Input String > part 2.txt
Setting Up Prolog
If you plan to use Prolog for this assignment you are required to use SWI-Prolog which can be found here.
Running Prolog Code
$ swipl -q -f part 1.pl -t main > part 1.txt
$ swipl -q -f part 2.pl -t main Example Input String > part 2.txt
Grading
Submissions will be graded according to the following rubric:
Part 1
20%
Part 2
70%
Code Clarity/ Comments
10 %
3
Reviews
There are no reviews yet.