The Weekly Challenge 058

Compare Version Numbers and Ordered Lineup

Solutions on GitHub

Task 1: Compare Version Numbers

Compare two given version number strings v1 and v2. Return 1 if v1 > v2, -1 if v1 < v2, and 0 if they are equal.

Example Output

compare_versions('0.1', '1.1') => -1 compare_versions('2.0', '1.2') => 1 compare_versions('1.2.1', '1.2_1') => 1

Logic

Parse numbers and separator characters (. vs _). Compare numeric parts component by component. If numbers match, a dot . has higher precedence than an underscore _.

Perl Solution

ch-1.pl

sub compare_versions { my ($ver1, $ver2) = @_; my ( $nums1, $seps1 ) = _parse_version($ver1); my ( $nums2, $seps2 ) = _parse_version($ver2); my $min = @$nums1 < @$nums2 ? scalar(@$nums1) : scalar(@$nums2); for my $i ( 0 .. $min - 1 ) { return -1 if $nums1->[$i] < $nums2->[$i]; return 1 if $nums1->[$i] > $nums2->[$i]; next if $i == 0; my $s1 = $seps1->[ $i - 1 ]; my $s2 = $seps2->[ $i - 1 ]; next if $s1 eq $s2; return 1 if $s1 eq '.'; return -1; } return -1 if @$nums1 < @$nums2; return 1 if @$nums1 > @$nums2; return 0; }

Python Solution

ch-1.py

def compare_versions(v1: str, v2: str) -> int: nums1, seps1 = _parse_version(v1) nums2, seps2 = _parse_version(v2) m = min(len(nums1), len(nums2)) for i in range(m): if nums1[i] != nums2[i]: return 1 if nums1[i] > nums2[i] else -1 if i > 0 and seps1[i - 1] != seps2[i - 1]: return 1 if seps1[i - 1] == "." else -1 if len(nums1) != len(nums2): return 1 if len(nums1) > len(nums2) else -1 return 0

Task 2: Ordered Lineup

Given arrays of unique heights @H and, for each height, the count @T of taller people in front of that person, reconstruct the lineup.

Example Output

Input: H = [2, 6, 4, 5, 1, 3], T = [1, 0, 2, 0, 1, 2] Output: [5, 1, 2, 6, 3, 4]

Logic

Greedy insertion algorithm: sort people by height descending. Insert each person into index T of the output array. Because taller people are inserted first, inserting at position T guarantees exactly T taller people precede them.

Perl Solution

ch-2.pl

sub ordered_lineup ( $heights, $taller_in_front ) { my @people; for my $i ( 0 .. $#$heights ) { push @people, { h => $heights->[$i], t => $taller_in_front->[$i] }; } @people = sort { $b->{h} <=> $a->{h} } @people; my @line; for my $p (@people) { my $idx = $p->{t}; splice @line, $idx, 0, $p->{h}; } return \@line; }

Python Solution

ch-2.py

def ordered_lineup(heights: Sequence[int], taller_in_front: Sequence[int]) -> List[int]: people = [Person(h, t) for h, t in zip(heights, taller_in_front)] people.sort(key=lambda p: p.height, reverse=True) line: List[int] = [] for p in people: line.insert(p.taller_in_front, p.height) return line