Download the raw code.
use v6;
use Test;
# p3 solution by colomon
grammar InclusionsAndExclusions {
regex integer { '-'? <digit>+ }
regex inclusion { '+[' <integer> '..' <integer> ']' }
regex exclusion { '-[' <integer> '..' <integer> ']' }
regex in_or_ex { <inclusion> | <exclusion> }
regex TOP { ^ <in_or_ex>* $ }
}
sub make-range($clusion) {
(+$clusion<integer>[0]) .. (+$clusion<integer>[1]);
}
sub test-inclusions-and-exclusions(Str $intervals, Int $integer) {
my $cleaned-intervals = $intervals.subst(/\h+/, "", :global);
my $match = InclusionsAndExclusions.parse($cleaned-intervals, :rule<TOP>);
return Bool unless $match;
my $result = Bool::False;
for @($match<in_or_ex>) -> $in-or-ex {
if $in-or-ex<inclusion> {
$result = Bool::True if $integer ~~ make-range($in-or-ex<inclusion>);
} else {
$result = Bool::False if $integer ~~ make-range($in-or-ex<exclusion>);
}
}
$result;
}
multi MAIN() {
my $intervals = $*IN.get;
my $integer = $*IN.get.Int;
my $result = test-inclusions-and-exclusions($intervals, $integer);
say $result.defined ?? $result ?? "yes" !! "no"
!! "invalid input";
}
multi MAIN("test") {
plan *;
{
my $match = InclusionsAndExclusions.parse("+[1..10]", :rule<inclusion>);
isa_ok $match, Match, "We matched";
is $match<integer>[0], 1, "Start is 1";
is $match<integer>[1], 10, "End is 10";
}
{
my $match = InclusionsAndExclusions.parse("-[1..10]", :rule<exclusion>);
isa_ok $match, Match, "We matched";
is $match<integer>[0], 1, "Start is 1";
is $match<integer>[1], 10, "End is 10";
}
{
my $match = InclusionsAndExclusions.parse("-[1..10]+[2..4]", :rule<TOP>);
isa_ok $match, Match, "We matched";
ok $match<in_or_ex>[0]<exclusion>, "First match is an exclusion";
nok $match<in_or_ex>[0]<inclusion>, "First match is not an inclusion";
ok $match<in_or_ex>[1]<inclusion>, "Second match is an inclusion";
nok $match<in_or_ex>[1]<exclusion>, "Second match is not an exclusion";
}
ok test-inclusions-and-exclusions("+[1..10]", 4), "4 is in 1..10";
nok test-inclusions-and-exclusions("+[1..10]-[2..4]", 4), "4 is not in +[1..10]-[2..4]";
nok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 41), "41 not in masak's example";
ok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 42), "42 in masak's example";
ok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 47), "47 in masak's example";
ok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 49), "49 in masak's example";
nok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 50), "50 not in masak's example";
nok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 55), "55 not in masak's example";
nok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 60), "60 not in masak's example";
ok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 61), "61 in masak's example";
ok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 80), "80 in masak's example";
ok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 100), "100 in masak's example";
nok test-inclusions-and-exclusions("+[ 42 .. 100 ] -[ 50 .. 60 ] -[ -10 .. 2 ]", 101), "101 not in masak's example";
nok test-inclusions-and-exclusions("+", 4).defined, "Recognized illegal input";
done;
}
Well-balanced and compartmentalized.
The neologism $clusion
(line 14) is brilliantly suitable as a short way to
say "inclusion or exclusion". Too bad it wasn't used all the way through,
like on line 10 or on line 18.
The subroutine test-inclusions-and-exclusions
does three-valued logic,
returning True
if the integer is in the rangeset, False
if it isn't,
and Bool
if the input string giving the rangeset didn't parse correctly.
As a consequence, any caller will have to juggle return values like in the
nested set of trinary operators on lines 39-40. Would have made
for a simpler, less error-prone API to do parsing outside of the sub.
Linear time complexity, as expected. Anything worse would have been surprising, and less-than-acceptable.
Reaching for a grammar for this problem is a Perl 6 instinct, I guess.
At line 41, we leave algorithmic code, and do tests for a bit more than half of the code. Not bad.