The formulation of this problem is quite creative, but overall it is just describing a matrix where the rows are workers and the columns are tasks. Workers have numbers and tasks have names and the job completion time depend on whether the worker is odd or even, the number of vowels and consonants in the task name and even common factors between the task name length and the worker number. Contrived but trivial. On top of that one is called to solve an assignment problem or weighted bipartite matching in graph speak. One algorithm to do just that is the Hungarian Algorithm (I wish I could speak of the Italian Algorithm, but there are none I know of). To create the input matrix one can use the program below, but it doesn't really achieve the full generality called for by the Facebook people. I wrote it down just to convince myself there wasn't some obvious structure in the matrix. It is written in my latest loop-free style (what do you do if your company doesn't switch to a functional language? Simple, write functionally in any language to the extent that is possible).
use strict;
sub nconsonants {
my $a = shift;
$a=~s/[aeiouAEIOU]+//g;
return length($a);
}
sub factors {
my $a = shift;
my @factors = ([],[],[2],[3],[2,2], [5], [2,3], [7], [2,2,2], [3,3], [2,5]);
return $factors[length($a)];
}
sub name2info {
my $a = shift;
return {ncon=>nconsonants($a),
nvow=>length($a) - nconsonants ($a),
fact=>factors($a)
};
}
sub progtime {
my ($prog, $info) = @_;
my $sum = 0;
map({$sum+=(($prog % $_)?0:4)} @{$info->{fact}});
return ($prog % 2 ? 1.5 * $info->{nvow} : $info->{ncon}) + $sum + 1;
}
my @names = qw/ANDROMEDA BARBARA CAMERON DAGMAR EKATERINA FLANNERY GREGORY HAMILTON ISABELLA
JEBEDIAH KIMBERLEY LARISSA MEREDITH NORMAN OSWALD PENELOPE QUENTIN RANDALL SAVANNAH TABITHA
URSULA VIVIENNE WINONA XAVIER YVONNE ZENOBIA/;
my @res=
map ({my $info = $_;
[map({my $prog = $_;
progtime($prog, $info);
}
1..26)]
}
map({name2info $_
}
@names));
print join "\n", map({join " \t", @$_} @res);
Read More......
Posts
