Compsoc Progcomp

The good people at ACME fundraisers are planning a fundraising ball, including dinner, and need a way to allocate people to tables. Since they are hoping for millions of people to attend they will be using a computer in order to organise the table layouts. Each table is a rectangle that seats people on either side. You should be given a list of people, the available tables and preferences, and you must calculate a seating plan. We will use the term 'close' in order to refer to five spaces around person, or three if one is seated at the end of a table. Seating preferences are in the form of likes, dislikes, loves and hates. If one person likes another, they must be sat at the same table, if one person hates another, they must be sat at different tables. If a person loves another they must be sat nearby, at the same table, if they dislike, they may be sat at the same table, but not nearby.

Input will be received on standard in. People will be specified by a line of input, here are some examples:

PERSON: Randy
PERSON: Donald Knuth
PERSON: Timmy Mallet

Table specifications can be of the following form:

TABLE: GREEN, 20
TABLE: 1, 6

Where the first identifier after TABLE is the name (eg "GREEN" or "1") and that is followed by the number of people seated at the table (eg 20 or ), which you may assume to always be even. Finally preferences are formatted as a triple of person name, preference, person name, for example:

Randy LOVES Donald Knuth
Donald Knuth HATES Randy
Timmy Mallet LIKES Randy
Donald Knuth DISLIKES Timmy Mallet

You will never be given the name of a person who isn't in the input list of names.

This is in the form of a list of people at a table, for example If the "GREEN" had one side of people called 'Randy' and 'Timmy Mallet', whilst opposite them on the other side 'Donald Knuth' and 'David Beckham', then it would be described in output by the name of the table, followed by a comma seperated list of square bracketed pairs, who are people sitting opposite each other on the table in order, for example:

GREEN [Randy,Donald Knuth],[Timmy Mallet,David Beckham]

If it is impossible to satisfy all the input constraints, then penalties are imposed, depending on how many constraints are broken. The following table specifies the penalties:

A HATES C on same table, penalty 1.
A HATES C nearby, penalty 2
A DISLIKES C nearby, penalty 1
A LOVES C not nearby, penalty 1
A LOVES C on different table, penalty 2
A LIKES C on different table, penalty 1

The value of penalty will be considered during testing. Penalties will also be imposed for not seating people.

Completed solutions should be emailed to progcomp@uwcs.co.uk before midday of the 8th April.

Half of the marks for a solution come from performance, and half from code quality. The former is to be judged on a range of inputs. The code quality is based on the opinion of the judges. Common standards are to be adhered to here - for example indentation, appropriate comments and appropriate abstractions/language idioms. Input should be expected on standard in, Output should be printed onto standard out.