The Bear's Den

Enter at your own risk

30 October 2026

Challenge 058

Ordered Versions

Task 1: Compare Version
Task 2: Ordered Lineup

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, and 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
------ ------ ------
1 < 1.1     -1
0 > 1.2      1
2 < 1.2_5   -1
2.1 > 1.2_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.

Solution

Here we need a kind of lexicographical comparison, where a string compare comes close the requested result. Splitting every version string into parts:

several decimal numbers, separated by dots
followed by any number of underscore / number pairs

Every number and every separator produces one part that is represented as.

a packed sequence of bytes in big-endian order for a number
a packed -1 for a dot
a packed -2 for an underscore

With this encoding:

two positive integers compare numerically the same as their packed representations as strings
a dot is larger than every positive integer and as an underscore
an underscore is larger than every positive integer but smaller than a dot.

The concatenation of all the parts from a version results in a (binary) string that can be compared to other version representations using a binary string compare.

use strict;
use warnings;
use experimental 'signatures';

sub compare_version ($v1, $v2) {
    state sub vstr ($v) {
        $v =~ m{^(?:\d++\.?+)++(?:_\d++)*+$} or die "version invalid: $v";
        pack "i>*",
            map /\./ ? -1 :
                /_/  ? -2 : $_,
            split /(\.|_)/, shift;
    }

    no locale;
    vstr($v1) cmp vstr($v2);
}

See the full solution to task 1.

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 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 a diagram of the input arrays @H and @T:

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

As per the last diagram, your script would then output the ordering (5, 1, 2, 6, 3, 4) in this case. (The leftmost element is the “front” of the array.)

Here’s a 64-person example, with answer provided:

# Heights
@H = (27, 21, 37,  4, 19, 52, 23, 64,  1,  7, 51, 17, 24, 50,  3,  2,
34, 40, 47, 20,  8, 56, 14, 16, 42, 38, 62, 53, 31, 41, 55, 59,
48, 12, 32, 61,  9, 60, 46, 26, 58, 25, 15, 36, 11, 44, 63, 28,
5, 54, 10, 49, 57, 30, 29, 22, 35, 39, 45, 43, 18,  6, 13, 33);

# Number taller people in front
@T = ( 6, 41,  1, 49, 38, 12,  1,  0, 58, 47,  4, 17, 26,  1, 61, 12,
29,  3,  4, 11, 45,  1, 32,  5,  9, 19,  1,  4, 28, 12,  2,  2,
13, 18, 19,  3,  4,  1, 10, 16,  4,  3, 29,  5, 49,  1,  1, 24,
2,  1, 38,  7,  7, 14, 35, 25,  0,  5,  4, 19, 10, 13,  4, 12);

# Expected answer
@A = (35, 23,  5, 64, 37,  9, 13, 25, 16, 44, 50, 40,  2, 27, 36,  6,
18, 54, 20, 39, 56, 45, 12, 47, 17, 33, 55, 30, 26, 51, 42, 53,
49, 41, 32, 15, 22, 60, 14, 46, 24, 59, 10, 28, 62, 38, 58, 63,
8, 48,  4,  7, 31, 19, 61, 43, 57, 11,  1, 34, 21, 52, 29,  3);

L You’re free to come up with your own inputs. Here is a 1000-person list, if you like!

Solution

Here is an extract from my solution dated 28 Jun 2020:

use strict;
use warnings;

use List::MoreUtils qw(pairwise firstidx reduce_1);

# exchange item at position $pos and next taller item.
# return position of found next item.
sub exchange {
	my ($items, $pos) = @_;
	my $pos_height = $items->[$pos]{height};
	my $next = $pos + firstidx {$_->{height} > $pos_height}
		@$items[$pos..$#$items];
	@$items[$pos, $next] = @$items[$next, $pos];
	return $next;
}

sub lineup {
	my ($heights, $talls) = @_;
	die "hights and talls have different sizes" if @$heights != @$talls;

	# collect hights and talls into single array.
	my @items = sort {$a->{height} <=> $b->{height}}
		pairwise { {height => $a, taller => $b} } @$heights, @$talls;

	# check solvability: the required number of taller predecessors must
	# not exceed the number of taller items.
	reduce_1 {$a && $b->{taller} <= $#items - $_} @items
			or die "no solution";

	# create an index to locate items in the array.
	my @index = (0 .. $#items);

	# process items by size.
	for (my $i = 0; $i < @index; $i++) {
		my $pos = $index[$i];
		my $item = $items[$pos];

		# move item to the right for the desired number of taller
		# predecessors.
		foreach my $offs (1 .. $item->{taller}) {
			# store new position of moved item
			$index[$i + $offs] = $pos;
			$pos = exchange \@items, $pos;
		}
	}
	return [map $_->{height}, @items];
}

See the full solution to task 2.