## Description

Computer Science 320SC

Programming Assignment 6

Requirements

This sixth assignment lets you get familiar with further algorithm design techniques covered in class

(e.g. network flow). There are two algorithms/programs required but three different submissions (two

data sets for one of them). It is worth 5% of your total course marks. Please try and test with your

own generated input cases before submitting to the automated marker.

Task 1: Peg Removal

We have a few pegs placed in a line of twelve holes. We want to remove pegs by jumping over other

pegs. Jumped over pegs disappear as a result of a move. A move is possible if there is a straight line

of three adjacent holes, where two adjecent holes contain a peg and the third is empty. The outside

peg may jump over the middle peg and be placed in the vacant hole on the other outside position. To

illustrate these moves consider the following figure (black nodes are pegged holes). Peg at position 8

jumps to the hole at position 6 then the peg at position 5 jumps past the peg at position 6 and ends

up at position 7.

Your goal is to find a sequence of moves such that as few pegs as possible are left.

The input consists of several cases. The first line is an integer denoting how many. The subsequent lines

are text strings of 12 characters in length consisting of ‘-’ (minus) and ‘o’ (little oh). An ’o’ represents an

peg and an ‘-’ represents an empty hole. Output an integer denoting the smallest number of remaining

pegs obtained by some sequence of moves.

Sample Input:

5

–ooo–oo—

ooooo—–oo

oooooooooooo

-o—–oo—

-oo-oo-oo—

Sample Output: for program named peg.ext

2

4

12

2

2

1

Task 2: UN Laptops

The United Nations (UN) is holding a computer convention and various delagates from around the world

come with laptops and want to plug them into outlets at the venue. Unfortunately, not all countries

use the same type of plugs. The UN venue supports a few popular types directly. Also they have an

unlimited supply of various types of adaptors. A delagate may need one or more adaptors to connect

and power his/her computer. Your task is to decide the minimum number of delagates that are left

without power, given a set of outlets (of the building), types of adaptors available, and the types of

plugs (of the laptops).

The input will consist of several cases as specified by an integer on the first line.

Each case is then given in three parts. The first line is an integer 1 ≤ n ≤ 500 indicating the number of

outlets in the building. The next n lines consist of a string indicating the type of each outlet. The next

line of the case consists of an integer 1 ≤ m ≤ 500 indicating the number of laptops. The next m lines

consist of a string indicating the type of the plug for each laptop. The next line of the case consists of

an integer 1 ≤ k ≤ 1000 indicating the number of adaptors types available. This is followed by k lines

of two strings separated by one space. These lines indicate the plug conversion for an adaptor (first

type to second type). All strings will be alphanumeric and of length at most 25.

For example in the following input the number of cases is 2. For the first case we have three outlets of

two types (one NZ and two British), then three laptops (two have NZ plugs and one has a British plug)

Finally we have two types of adapters: the first one converts NZ to American and the other one converts

American to British. All three laptops can be used, with one of the NZ plugs using both adaptors.

Sample Input:

2

3

NZ

British

British

3

NZ

British

NZ

2

NZ American

American British

4

A

B

C

D

5

B

C

B

B

X

3

B X

A X

X D

Sample Output:

0

2

Submit programs laptopsE.ext and laptopsH.ext to test easy and harder data sets.

Submission Procedure

For each of these submissions you may use the folling extensions for ext to indicate which language/compiler to use: { java, cpp, py, cs }, that indicates Java/C++/Python/C#(mono). The

automarker runs on a Debian linux box and uses the most recent compilers that are packaged by them.

Please use just one source file per problem.

For this assignment there is two marks awarded for Task 1 and and three marks awarded for Task 2.

2