Gossamer Forum
(Advanced Search)
for
Home : General : Perl Programming :

Problem with cross checking multiple array values.

Jun 16, 2003, 4:19 AM
fafu
New User (2 posts)
Jun 16, 2003, 4:19 AM
Post #1 of 4
Views: 4040
Shortcut
Quote Reply
Problem with cross checking multiple array values.
Hi,

i have a little problem that i'm having trouble doing well, and with Perl i know that shouldn't be the case. Wink

I have 6 arrays with 6 entries in each. Each array entry is either a 1 or a 0. A single array can be made up of any combination of 1's and 0's. For example
Code:
@a = (1,0,0,1,0,1);
@b = (0,1,1,0,1,1);
@c = (1,0,0,0,0,1);
@d = (1,1,1,1,1,1);
@e = (0,0,0,1,0,0);
@f = (0,1,0,1,0,1);

Each array represents a school course, and each value in the array the blocks, 0-5, the course runs in. What i need to do is find out if there are any clashes between the courses. In other words can the student who has chosen this set of courses actually sit them all with out being double booked.

My way of doing it so far is to work down the arrays (@a - @f) and assign the blocks on a first come first served basis. Then where there are clashes, reassign the 2 clashing courses again to different available places, as allowed by the array pattern for that course, until they all fit. Any that really will not go will be flagged up for the user so they can try something different.

Normally the student will only actually choose 4, possibly 5, courses. Which will make assignment slightly more successful.

This seems like a long winded way of doing this, and i was wondering if anyone out there had a better solution to this problem. I've reached a plateau in my Perl and need a little helping hand into some new ways of thinking.

Thanks in advance to anyone who can help.
Fafu
http://www.fafu.co.uk
Jun 18, 2003, 4:35 PM
cornball
User (238 posts)
Jun 18, 2003, 4:35 PM
Post #2 of 4
Views: 3905
Shortcut
Quote Reply
Re: [fafu] Problem with cross checking multiple array values. In reply to
Hello fafu,

See attached idea.html .

Rather than allowing students to pick classes and time periods and then check

for clashes why don't you use radio groups from the start so they can not pick

2 classes for the same block.

I suppose it all depends on how you get the information in from the students.

Thanks

cornball

Attached Files:

Jun 18, 2003, 5:54 PM
cornball
User (238 posts)
Jun 18, 2003, 5:54 PM
Post #3 of 4
Views: 3904
Shortcut
Quote Reply
Re: [cornball] Problem with cross checking multiple array values. In reply to
See attached idea2.html for Version 2 as it was possible to pick one subject in all blocks.

Thanks

cornball

Attached Files:

Jun 20, 2003, 2:40 AM
fafu
New User (2 posts)
Jun 20, 2003, 2:40 AM
Post #4 of 4
Views: 3874
Shortcut
Quote Reply
Re: [cornball] Problem with cross checking multiple array values. In reply to
Cornball,

Top bit of Javascript squire, thank you for spending the time to look at this.

Unfortunatly it won't really work for what i need. The courses that the student gets to choose from are only available in certain blocks depending on tutor availability, demand and classroom space. So some courses will run in everyblock while some will only run in 1 out of the 6. This is all preset by the head teacher before hand. Also there are some 150 possible courses to choose from which is quite a lot. My page that the student picks their courses from uses HTML picklists (SELECT LISTS) to save on screen space.

There for i think the cross checking has to take place in Perl upon submission. Though i'm still open to other suggestions.

Here is a demo version of my long winded code that works for me at the moment, and i guess might be of use to someone somewhere. I just feel that there should be an easier way of doing everything. As you'll see, i've changed my way of thinking from what i described originally and use quite a few hashes to order and reorder the data into ways which fit my logic, which as it's been quite muggy here in London is lacking.

Code:

#
# fafu June 2003
#
open (FH, "file.txt") || die "no $!";

@v = ("A", "B", "C", "D", "E", "F");
@coursenames = ("one", "two", "three", "four", "five", "six"); ## as we won't have course names in this demo

$coursecount = 0;
while (<FH>) {
chomp;
$rows{$coursenames[$coursecount]} = $_;
print "Course '$coursenames[$coursecount]' have read in '$_'\n";
$coursecount++;
}

foreach $r (keys %rows) {

@t = $rows{$r};
@u = split(/\ /, $t[0]);
for ($i=0;$i<@v;$i++) {
if ($u[$i] == 1) {
$fit{$i}{$r} = "in";
$cscores{$r}++;
$clist{$r}{$i} = 1;
}
}
}

$excessrowcount = 0;
$havecoursestofit = 1;
while ($havecoursestofit == 1) { ## we will need a few passes of this as things will change as we go.
foreach $block (sort numerically keys %fit) {
$counter=0; ## used to count the number of courses in this block
foreach $c (sort numerically keys %{$fit{$block}}) {
$counter++;
$course = $c;
}

## now we have counted the number of courses in this block
if ($counter ==1) {
## found a block with only one courses in it,
## so it won't clash with anything else
if (!$courseplaced{$course}) {
$placed{$block} = $course; ## $placed{"blockcode"} = "coursename";
$courseplaced{$course} = $block; ## $courseplaced{"coursename"} = "block";
}

## now must remove this course from every other block to make
## sure we don't assign it again.
foreach $b2 (sort numerically keys %fit) {
if ($fit{$b2}{$course}) {
delete($fit{$b2}{$course});
}
}
}
}
if ($excessrowcount > 5) { ## if we've been through 5 times that's probably enough get out.
$havecoursestofit = 0;
}
$excessrowcount++;
} # end of while


## if there are any courses not as yet placed we need to get them to fit.
## get any courses which only appear in one block, for example their block string in the text file reads
## 0 0 0 0 0 1
foreach $c (sort numerically keys %cscores) {
foreach $b (sort numerically keys %{$clist{$c}}) {
if (($cscores{$c} ==1) && (!$placed{$b})) {
$placed{$b} = $c; ## this gets placed as it can't go anywhere else
delete($fit{$b}{$c}); ## take out of the hash
}
}
}

## now all the blocks left that haven't been taken have more than one course in them, and
## each of those courses have at least one more block where it could fit.
## so we take the courses with the lowest number of possible places and try sticking it in and
## seeing what happens!
foreach $b (sort numerically keys %fit) {
undef(%lowest);
foreach $c (sort keys %{$fit{$b}}) {
$lowest{$cscores{$c}} = $c;
}
foreach $sc (sort numerically keys %lowest) {
if (!$placed{$b}) {
$placed{$b} = $lowest{$sc};
foreach $b2 (sort numerically keys %fit) {
if ($fit{$b2}{$lowest{$sc}}) {
delete($fit{$b2}{$lowest{$sc}});
delete($cscores{$lowest{$sc}});
}
}
last;
}
}
}

print "\nPLACED\n";
foreach $pi (sort keys %placed) {
print "$placed{$pi} placed in block $v[$pi] \n";
}

## now any left must clash with other courses, show which they are and who they clash with
print "\nCLASHES\n";

foreach $block (sort keys %fit) {
foreach $course (sort keys %{$fit{$block}}) {
if ($course) {
print " $course clashes with $placed{$block} in block $v[$block]\n";
}
}
}


#
# subs
#

sub numerically {
$a <=> $b;
}

This opens and reads in text file called "file.txt" in the same directory, which i've used for this demo instead of reading in parameters passed from a url. Here's a sample for that file

Code:

1 0 1 1 0 0
0 1 0 0 0 0
1 1 1 1 1 1
0 1 0 0 0 0

This demo should place 3 out of the 4 and then tell you that one of the courses clashes with another. Changing the patterns in file.txt will produce different results obviously, the only rule is there has to be 6 marks per line and up to 6 lines max. Most students in my case will only pick 3 or 4 courses.

Again, big thanks Cornball for having a look. Plus thanks to anyone else who spots a better way of doing the above. I'm happy with my code i just need to learn a few more tricks from the masters out there...
Fafu
http://www.fafu.co.uk