1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
#!/usr/bin/env perl
use strict;
use warnings;
# CLI usage
sub usage {
print "$0 {-e ARABIC | -d ROMAN | --test}\n";
exit shift;
}
usage -1 unless @ARGV > 0;
if ($ARGV[0] eq "--test") {
test();
} else {
usage -1 unless @ARGV == 2;
if ($ARGV[0] eq "-d") {
print decode($ARGV[1]), "\n";
} elsif ($ARGV[0] eq "-e") {
print encode($ARGV[1]), "\n";
} else {
usage -1;
}
}
# roman -> arabic
sub decode {
my @roman = split //, shift;
# Decimal value of each roman symbol
my %dec = (
M => 1000,
D => 500,
C => 100,
L => 50,
X => 10,
V => 5,
I => 1,
);
my $arabic = 0; # Return value
# Iterate over roman symbols
for (my $i = 0; $i < @roman; $i++) {
# Get current and next symbols
my ($currsym, $nextsym) = @roman[$i .. $i+1];
my $val = $dec{$currsym};
# Sub current value if next symbol is bigger; add it otherwise
if (defined $nextsym && $val < $dec{$nextsym}) {
$arabic -= $val;
} else {
$arabic += $val;
}
}
return $arabic;
}
# arabic -> roman
sub encode {
die "ERROR: Unable to encode numbers bigger than 9999" if $_[0] > 9999;
my @arabic = split //, shift;
my @symbols = ("I", "V", "X", "L", "C", "D", "M");
my @roman; # Return value (roman symbols)
# Iterate arabic digits from right to left (upward units)
for (my $i = $#arabic; $i >= 0; $i--) {
my $digit = $arabic[$i];
# Roman symbols corresponding to (1-5-10) given the current base
my ($one, $five, $ten) = @symbols;
# Roman symbols to add at the beginning of the current result
my @to_add;
# 4 and 9 are (5-1) and (10-1) respectively
if ($one ne "M" && ($digit == 4 || $digit == 9)) {
push @to_add, $one;
$digit++;
}
# Add the roman equivalents to the current digit
if ($one eq "M") {
# For 4000-9999, just add as much M's as needed
push @to_add, (map $one, (1..$digit));
} elsif ($digit == 10) {
push @to_add, $ten;
} elsif ($digit > 4) {
push @to_add, ($five, map $one, (6..$digit));
} elsif ($digit > 0) {
push @to_add, (map $one, (1..$digit));
}
unshift @roman, @to_add;
# For the next decimal, discard two roman symbols (one + five)
shift @symbols foreach (1..2);
}
return join "", @roman;
}
# Property:
# forall (x : Arabic). x == decode(encode(x))
sub test {
foreach my $i (1..9999) {
my $roman = encode($i);
my $arabic = decode($roman);
die "ERROR: $i -> $roman -> $arabic" if $i != $arabic;
}
print "Test successful\n";
}
|
