The Weekly Challenge 010

Roman Numerals and Jaro-Winkler Distance

Solutions on GitHub

Task 1: Roman Numerals

Write a script to encode decimal numbers into Roman numerals and decode Roman numerals back to decimal numbers.

Example Output

CCXLVI = 246 246 = CCXLVI 39 = XXXIX XXXIX = 39

Logic

We define a mapping list/dictionary of the core values (including combined subtractive pairs like `CM`, `IV`, `IX`). For encoding, we repeatedly subtract the largest possible values while prefixing their corresponding Roman characters. For decoding, we match Roman prefix patterns sequentially and add their corresponding numerical values.

Perl Solution

ch-1.pl

sub encode_roman { my $number = shift; my @roman_map = ( [ 'M', 1000 ], [ 'CM', 900 ], [ 'D', 500 ], [ 'CD', 400 ], [ 'C', 100 ], [ 'XC', 90 ], [ 'L', 50 ], [ 'XL', 40 ], [ 'X', 10 ], [ 'IX', 9 ], [ 'V', 5 ], [ 'IV', 4 ], [ 'I', 1 ] ); my $roman_numeral = ''; foreach my $pair (@roman_map) { my ( $numeral, $value ) = @$pair; while ( $number >= $value ) { $roman_numeral .= $numeral; $number -= $value; } } return $roman_numeral; } sub decode_roman { my $roman_numeral = shift; my @roman_map = ( [ 'M', 1000 ], [ 'CM', 900 ], [ 'D', 500 ], [ 'CD', 400 ], [ 'C', 100 ], [ 'XC', 90 ], [ 'L', 50 ], [ 'XL', 40 ], [ 'X', 10 ], [ 'IX', 9 ], [ 'V', 5 ], [ 'IV', 4 ], [ 'I', 1 ] ); my $number = 0; foreach my $pair (@roman_map) { my ( $numeral, $value ) = @$pair; while ( $roman_numeral =~ /^$numeral/ ) { $number += $value; $roman_numeral =~ s/^$numeral//; } } return $number; }

Python Solution

ch-1.py

roman_map = { "I": 1, "IV": 4, "V": 5, "IX": 9, "X": 10, "XL": 40, "L": 50, "XC": 90, "C": 100, "CD": 400, "D": 500, "CM": 900, "M": 1000, } def encode_to_roman(number): result = "" for roman, value in sorted(roman_map.items(), key=lambda x: -x[1]): while number >= value: result += roman number -= value return result def decode_to_decimal(roman): result = 0 index = 0 while index < len(roman): if index < len(roman) - 1 and roman[index : index + 2] in roman_map: result += roman_map[roman[index : index + 2]] index += 2 else: result += roman_map[roman[index]] index += 1 return result

Task 2: Jaro-Winkler Distance

Write a script to calculate the Jaro-Winkler distance between two strings.

Example Output

Jaro-Winkler distance between 'MARTHA' and 'MARHTA' is 0.961111111111111

Logic

The Jaro-Winkler distance is a measure of similarity between two strings:

  1. Jaro Distance ($d_j$): Calculate matching characters $m$ within a maximum match distance of $\lfloor \frac{\max(|s_1|, |s_2|)}{2} \rfloor - 1$. Calculate half-transpositions $t$ where matching characters appear in different orders. Formula: $d_j = \frac{1}{3} (\frac{m}{|s_1|} + \frac{m}{|s_2|} + \frac{m - t}{m})$.
  2. Jaro-Winkler Distance ($d_w$): We give more weight to strings that share a common prefix. We find the length of the matching prefix $l \le 4$ and apply the formula: $d_w = d_j + l \cdot p \cdot (1 - d_j)$, where $p = 0.1$ is the constant scaling factor.

Perl Solution

ch-2.pl

sub jaro_winkler_distance { my ( $s1, $s2, $p ) = @_; $p ||= 0.1; my $matches = 0; my $transpositions = 0; my $s1_len = length($s1); my $s2_len = length($s2); my $match_distance = int( max( $s1_len, $s2_len ) / 2 ) - 1; my %s2_matches = (); for ( my $i = 0 ; $i < $s1_len ; $i++ ) { my $c1 = substr( $s1, $i, 1 ); my $start = max( 0, $i - $match_distance ); my $end = min( $i + $match_distance + 1, $s2_len ); for ( my $j = $start ; $j < $end ; $j++ ) { if ( !$s2_matches{$j} && substr( $s2, $j, 1 ) eq $c1 ) { $matches++; $s2_matches{$j} = 1; last; } } } return 0 if ( $matches == 0 ); my $jaro_distance = ( $matches / $s1_len + $matches / $s2_len + ( $matches - $transpositions / 2 ) / $matches ) / 3; my $prefix_len = 0; for ( my $i = 0 ; $i < min( $s1_len, $s2_len ) ; $i++ ) { if ( substr( $s1, $i, 1 ) eq substr( $s2, $i, 1 ) ) { $prefix_len++; } else { last; } } my $jaro_winkler_distance = $jaro_distance + $prefix_len * $p * ( 1 - $jaro_distance ); return $jaro_winkler_distance; }

Python Solution

ch-2.py

def jaro_winkler_distance(s1, s2, p=0.1): m = 0 s1_len = len(s1) s2_len = len(s2) match_distance = max(s1_len, s2_len) // 2 - 1 s1_matches = [False] * s1_len s2_matches = [False] * s2_len for i in range(s1_len): start = max(0, i - match_distance) end = min(i + match_distance + 1, s2_len) for j in range(start, end): if s2_matches[j]: continue if s1[i] != s2[j]: continue s1_matches[i] = True s2_matches[j] = True m += 1 break if m == 0: return 0.0 transpositions = 0 j = 0 for i in range(s1_len): if not s1_matches[i]: continue while not s2_matches[j]: j += 1 if s1[i] != s2[j]: transpositions += 1 j += 1 jaro_distance = (m / s1_len + m / s2_len + (m - transpositions / 2) / m) / 3 l = 0 for i in range(min(s1_len, s2_len)): if s1[i] != s2[i]: break l += 1 jaro_winkler_distance = jaro_distance + l * p * (1 - jaro_distance) return jaro_winkler_distance