Task 1: "Compare Version

Compare two given version number strings v1 and v2 such that:

    If v1 > v2 return 1
    If v1 < v2 return -1
    Otherwise, return 0

The version numbers are non-empty strings containing only digits, the dot
('.') and underscore ('_') characters. ('_' denotes an alpha/development
version, and has a lower precedence than a dot, '.'). Here are some examples:

   v1   v2    Result
------ ------ ------
  0.1 < 1.1     -1
  2.0 > 1.2      1
  1.2 < 1.2_5   -1
1.2.1 > 1.2_1    1
1.2.1 = 1.2.1    0

Version numbers may also contain leading zeros. You may handle these
how you wish, as long as it's consistent.
"

My notes: I hate it already:-)  but it doesn't sound too hard.


Task 2: "Ordered Lineup

Write a script to arrange people in a lineup according to how many
taller people are in front of each person in line. You are given two
arrays. @H is a list of unique heights, in any order. @T is a list of
how many taller people are to be put in front of the corresponding
person in @H. The output is the final ordering of people's heights,
or an error if there is no solution.

Here is a small example:

    @H = (2, 6, 4, 5, 1, 3) # Heights
    @T = (1, 0, 2, 0, 1, 2) # Number of taller people wanted in front

The ordering of both arrays lines up, so H[i] and T[i] refer to the same
person. For example, there are 2 taller people in front of the person
with height 4, and there is 1 person in front of the person with height 1.

here is one possible solution that satisfies @H and @T:

(5, 1, 2, 6, 3, 4)

Note that the leftmost element is the 'front' of the array.)
"

My notes: an unfamiliar problem, sounds quite interesting.  No algorithm
immediately comes to mind..  Generate-and-test was my first thought - i.e.
have a function to test "is-this-combination-a-valid-answer" and invoke it
for every possible answer.  But the question also suggested that our
algorithm should be able to work at a scale of 1000 people, and the number
of combinations of 1000 people is insane (1000!).  so scratch that.

After trying a few examples manually, I realised that the first person in
the queue must be someone who wants 0 people taller than them in front of
them, and quickly generalised this into what I think it a valid and efficient
algorithm.  See function "solve".

However, it doesn't (yet) scale to the 64-person solution, much less the
1000-person one.  I've tried some Perl profiling on an intermediate scale
problem, and managed to make it run 4 times faster, but it still can't
scale up to 64-person scale, would need a fundamentally faster algorithm,
which I just can't see.