#!/usr/bin/perl

# Greedy brute force solution to the Golf Foursomes Problem
# 11 Apr 2003 by Aneel Nazareth
# http://eye-of-newt.com/nazareth/golf.html

sub pick_best {
    my $playing = shift;
    my $candidates = shift;

    #warn "$playing $candidates\n";
    my %score;
    
    foreach $c (@$candidates) {
	foreach $p (@$playing) {
	    if ($played->[$c]->[$p]) {
		$score{$c}++;
	    }
	}
    }
    
    my $min = $score{$candidates->[0]};
    my $best = $candidates->[0];
    foreach $c (@$candidates) {
	if ($score{$c} < $min) {
	    $min = $score{$c};
	    $best = $c;
	}
    }
    #warn "best match is $best with score of $min\n";
    
    foreach $p (@$playing) {
	$played->[$p]->[$best]++;
	$played->[$best]->[$p]++;
	$played_round->[$p]->[$best]++;
	$played_round->[$best]->[$p]++;
    }
    return $best;
}


sub round {
    my %players;
    $played_round = [];
    
    print "New Round\n";
    
    for (my $i=0; $i<16; $i++) {
	$players{$i} = 1;
    }
    
    for (my $i=0; $i<4; $i++) {
	my @group;
	for (my $j=0; $j<4; $j++) {
	    my @players = sort {$a <=> $b} keys %players;
	    my $best = pick_best(\@group,\@players);
	    push(@group, $best);
	    delete $players{$best};
	}
	print "group $i: ";
	foreach (@group) {
	    printf("%2d ", $_);
	}
	print "\n";
    }
    
    print "\n";
    for (my $i=0; $i<16; $i++) {
	printf("%2d played this round: ", $i);
	for (my $j=0; $j<16; $j++) {
	    if ($played_round->[$i]->[$j]) {
		printf("%2d ", $j);
	    } else {
		print '   ';
	    }
	}
	print "\n";
    }
    
    print "\n";
    for (my $i=0; $i<16; $i++) {
	printf("%2d has played: ", $i);
	for (my $j=0; $j<16; $j++) {
	    if ($played->[$i]->[$j]) {
		printf("%2d ", $j);
     } else {
	 print '   ';
     }
	}
	print "\n";
    }
    
    print "\n";
}

round();
round();
round();
round();
round();