# Prolog辅导 | CSCI 4430/6430 Programming Assignment 3

这个Assignment是使用prolog完成2个练习题

CSCI 4430/6430 Programming Languages

Fall 2019

Programming Assignment 3

Deadline: 7:00pm EST December 02, 2019

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 computational 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 integers 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 −→ Find a set of I that Op to Number

• 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 integers. 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