Perl Weekly Challenge: I Shot The Subnet…

Posted on by

Perl Weekly Challenge 363‘s tasks are “String Lie Detector” and “Subnet Sheriff”.

I challenge anyone to not think of I Shot The Sheriff given those tasks.

Task 2: Subnet Sheriff

You are given an IPv4 address and an IPv4 network (in CIDR format).

Write a script to determine whether both are valid and the address falls within the network. For more information see the Wikipedia article.

Example 1

Input: $ip_addr = "192.168.1.45"
       $domain  = "192.168.1.0/24"
Output: true

Example 2

Input: $ip_addr = "10.0.0.256"
       $domain  = "10.0.0.0/24"
Output: false

Example 3

Input: $ip_addr = "172.16.8.9"
       $domain  = "172.16.8.9/32"
Output: true

Example 4

Input: $ip_addr = "172.16.4.5"
       $domain  = "172.16.0.0/14"
Output: true

Example 5

Input: $ip_addr = "192.0.2.0"
       $domain  = "192.0.2.0/25"
Output: true

Approach

I find this challenge task very ironic, because I just installed Net::CIDR at work to do this exact same thing. The library has subroutines to validate an IP address and test whether an address is within the range of a CIDR. So, using that library, the solution would be 

sub subnetSheriff($ip_addr, $domain) {
  return Net::CIDR::cidrvalidate($ip_addr)
      && Net::CIDR::cidrvalidate($domain)
      && Net::CIDR::cidrlookup($ip_addr, @{[ $domain ]})
}

But I’m not going to use that library. I didn’t need to consult the Wikipedia article to remember that IPv4 addresses are 32-bit integers, usually expressed as four 8-bit decimal octets. So for the IPv4 address 1.2.3.4, the 32-bit integer is 1 * 2**24 + 2 * 2**16 + 3 * 2**8 + 4, or 16909060. And CIDR notation contains two parts: the first specifying a network prefix, and the second a subnet mask.

I could write this more compactly, but I’m going for readability. I’m writing three functions, valid, octets2int, and in_range to handle the portions of the approach. The valid function will check to see if the provided IPv4 address or IPv4 CIDR is valid by checking that each of the octets (and the subnet mask, if provided) are in the acceptable range.

The octets2int function will convert a series of 4 octets into a 32-bit integer.

The in_range function will generate the 32-bit integer subnet mask, and then do a bitwise AND between that and the 32-bit integer IP address, and then compare the result with the 32-bit integer network prefix. If the numbers match, the IP address is in the range of the CIDR.

(2 ** 32 - 1) will get us 32 bits of 1s, and if $mask is the numeric portion of the subnet mask (say, /24), then (2 ** (32-$mask) - 1) will get us the appropriate 1 bits for the mask (for a /24 mask, that’s eight bits of 1s).

Raku

The new (to me) thing I used in the Raku solution was the .all routine, which returns a Junction that performs the operation against each item in the list. However, when I was doing say statements to check my results along the way, the junction was getting stringified as all(True, True, True, True), so I added the so operator to coerce the Junction into a Boolean.

The other thing that messed me up is because I primarily code in Perl, I couldn’t keep straight the bitwise operators. +^ is the numeric bitwise XOR operator and +& is the numeric bitwise AND operator.

sub valid($val) {
  my @octets = $val.split('.');
  if (@octets[3] ~~ /\//) {
    my ($octet, $mask) = @octets[3].split('/');
    return False if $mask > 32;
    @octets[3] = $octet;
  }
  return so @octets.all <= 255;
}

sub octets2int($ip_addr) {
  my $i = 3;
  return $ip_addr.split('.').map({ $_ * 2**(($i--)*8)}).sum;
}

sub in_range($ip_addr, $domain) {
  my ($prefix, $mask) = $domain.split('/');
  my $ip_int     = octets2int($ip_addr);
  my $prefix_int = octets2int($prefix);
  my $mask_int   = (2 ** 32 - 1) +^ (2 ** (32-$mask) - 1);
  return ($ip_int +& $mask_int) == $prefix_int;
}

sub subnetSheriff($ip_addr, $domain) {
  return so valid($ip_addr) && valid($domain) &&
         in_range($ip_addr, $domain);
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $ip_addr = "192.168.1.45"
       $domain  = "192.168.1.0/24"
Output: True

Example 2:
Input: $ip_addr = "10.0.0.256"
       $domain  = "10.0.0.0/24"
Output: False

Example 3:
Input: $ip_addr = "172.16.8.9"
       $domain  = "172.16.8.9/32"
Output: True

Example 4:
Input: $ip_addr = "172.16.4.5"
       $domain  = "172.16.0.0/14"
Output: True

Example 5:
Input: $ip_addr = "192.0.2.0"
       $domain  = "192.0.2.0/25"
Output: True

Perl

Because my brain is still steeping in about 30 years of writing in Perl, my Raku code is still very much like Perl code. I had to import all and sum from List::AllUtils, and ^ is bitwise XOR and & is bitwise AND.

use List::AllUtils qw( all sum );

sub valid($val) {
  my @octets = split /\./, $val;
  if ($octets[3] =~ /\//) {
    my ($octet, $mask) = split /\//, $octets[3];
    return false if $mask > 32;
    @octets[3] = $octet;
  }
  return all { $_ <= 255 } @octets;
}

sub octets2int($ip_addr) {
  my $i = 3;
  return sum map { $_ * 2**(($i--)*8) } split /\./, $ip_addr;
}

sub in_range($ip_addr, $domain) {
  my ($prefix, $mask) = split /\//, $domain;
  my $ip_int     = octets2int($ip_addr);
  my $prefix_int = octets2int($prefix);
  my $mask_int   = (2 ** 32 - 1) ^ (2 ** (32-$mask) - 1);
  return ($ip_int & $mask_int) == $prefix_int;
}

sub subnetSheriff($ip_addr, $domain) {
  return valid($ip_addr) && valid($domain) &&
         in_range($ip_addr, $domain);
}

View the entire Perl script for this task on GitHub.

Python

But because I write my Python like Perl, making the Python version was dead easy. The hardest part was decrementing i in the octets2int loop. I wound up using zip() to loop over both a range of i values and the octets, but instead of providing the range as range(3, -1, -1), I wrote it as [3, 2, 1, 0] instead because that’s only 13 characters instead of 17. At least all the bitwise operators are the same as Perl…

def valid(val):
  octets = val.split('.')
  if '/' in octets[3]:
    octet, mask = octets[3].split('/')
    if int(mask) > 32: return False
    octets[3] = octet
  return all([ int(o) <= 255 for o in octets ])

def octets2int(ip_addr):
  octets = ip_addr.split('.')
  return sum(
    [ int(o) * 2**(8*i) for i,o in zip([3, 2, 1, 0], octets) ]
  )

def in_range(ip_addr, domain):
  prefix, mask = domain.split('/')
  ip_int     = octets2int(ip_addr)
  prefix_int = octets2int(prefix)
  mask_int   = (2 ** 32 - 1) ^ (2 ** (32-int(mask)) - 1)
  return (ip_int & mask_int) == prefix_int

def subnet_sheriff(ip_addr, domain):
  return (
    valid(ip_addr) and valid(domain) and
    in_range(ip_addr, domain)
  )

View the entire Python script for this task on GitHub.

Elixir

Most of the extra lines in Elixir come from valid, which winds up being two functions, one to determine if there’s a mask and one to check the octets of the address. I’m doing a lot of importing so I don’t have to qualify a bunch of functions.

import Bitwise
import String

def valid(octets) when is_list(octets), do:
  Enum.all?(octets, fn o -> to_integer(o) <= 255 end)

def valid(octets) do
  if contains?(octets, "/") do
    [octets, mask] = split(octets, "/")
    to_integer(mask) <= 32 and octets |> split(".") |> valid
  else
    octets |> split(".") |> valid
  end
end

def octets2int(ip_addr) do
  ip_addr |> split(".") |> Enum.map_reduce(3, fn o, i ->
    { to_integer(o) * 2 ** (8*i), i - 1 }
  end) |> elem(0) |> Enum.sum
end

def in_range(ip_addr, domain) do
  [prefix, mask] = split(domain, "/")
  ip_int     = octets2int(ip_addr)
  prefix_int = octets2int(prefix)
  mask       = to_integer(mask)
  mask_int   = bxor(2 ** 32 - 1, 2 ** (32-mask) - 1)
  (ip_int &&& mask_int) == prefix_int
end

def subnet_sheriff(ip_addr, domain) do
  valid(ip_addr) and
  valid(domain)  and
  in_range(ip_addr, domain)
end

View the entire Elixir script for this task on GitHub.

Task 1: String Lie Detector

You are given a string.

Write a script that parses a self-referential string and determines whether its claims about itself are true. The string will make statements about its own composition, specifically the number of vowels and consonants it contains.

Example 1

Input: $str = "aa — two vowels and zero consonants"
Output: true

Example 2

Input: $str = "iv — one vowel and one consonant"
Output: true

Example 3

Input: $str = "hello - three vowels and two consonants"
Output: false

Example 4

Input: $str = "aeiou — five vowels and zero consonants"
Output: true

Example 5

Input: $str = "aei — three vowels and zero consonants"
Output: true

Approach

And now my brain is singing “String Lie Detector” to the tune of “I Shot The Sheriff”.

This is the flip side of last week’s task “Spellbound Sorting“, where we had to convert numeric values into human-language words; now we’re converting words into their numeric values.

I’m going to assume that all strings will match the following regular expression:

        /(\w+)\s+—\s+(.+)\s+vowels?\s+and\s+(.+)\s+consonants?/

This makes the problem much simpler: rather than having to parse out any sentence, I’m able to apply a regular expression and get back three string values: the string being referenced, how many vowels it claims to have, and how many consonants it claims to have.Then all I have to do is count the consonants and vowels in the string, and convert the string numbers to numerics to determine whether it’s true or not.

Raku

Like last week, I’m using  Lingua::NumericWordForms for my translation. This time, the function is from-numeric-word-form, and it takes a string that is a numeric word form and converts it to an Int.

I’m also using Raku’s regex’s named captures, and the version of .comb where you provide a regex of the characters to match (I’m usually providing no parameter to .comb, which returns a Seq of characters in the string, as if the matcher was rx/./).

use Lingua::NumericWordForms;

my $extract_regex = rx/
  $<string> = [ \w+ ] \s+ <[\-\—\―]> \s+
  $<vowels> = [ .+ ] \s+ vowels?
  \s+ and \s+
  $<consonants> = [ .+ ] \s+ consonants?
/;

sub lieDetector($str) {
  $str ~~ $extract_regex;
  my $vowel_count     = ~$<string>.comb(/<[aeiou]>/).elems;
  my $consonant_count = ~$<string>.comb(/<-[aeiou]>/).elems;
  my $vowel_claim     = from-numeric-word-form(~$<vowels>);
  my $consonant_claim = from-numeric-word-form(~$<consonants>);
  return $vowel_count     == $vowel_claim
      && $consonant_count == $consonant_claim;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $str = "aa — two vowels and zero consonants"
Output: True

Example 2:
Input: $str = "iv — one vowel and one consonant"
Output: True

Example 3:
Input: $str = "hello - three vowels and two consonants"
Output: False

Example 4:
Input: $str = "aeiou — five vowels and zero consonants"
Output: True

Example 5:
Input: $str = "aei — three vowels and zero consonants"
Output: True

Perl

For Perl, the module I’m using to translate words into numbers is Lingua::EN::Words2Nums. I’m also rolling my own comb function for brevity.

use Lingua::EN::Words2Nums;

my $extract_regex = qr/
  (?<string> \w+ ) \s+ [\-\—\―]+ \s+
  (?<vowels> .+  ) \s+ vowels?
  \s+ and \s+
  (?<consonants> .+ ) \s+ consonants?
/x;

sub comb($str, $regex) {
  map { /$regex/ } split //, $str;
}

sub lieDetector($str) {
  $str =~ /$extract_regex/;
  my $vowel_count     = scalar(comb($+{string}, qr/[aeiou]/));
  my $consonant_count = scalar(comb($+{string}, qr/[^aeiou]/));
  my $vowel_claim     = words2nums($+{vowels});
  my $consonant_claim = words2nums($+{consonants});
  return $vowel_count     == $vowel_claim
      && $consonant_count == $consonant_claim;
}

View the entire Perl script for this task on GitHub.

Python

For Python, the library appears to be word2number.

import re
from word2number import w2n

extract_regex = re.compile(
  r'(?P<string> \w+ ) \s+ [\-\—\―]+ \s+'
  r'(?P<vowels> .+  ) \s+ vowels?'
  r'\s+ and \s+'
  r'(?P<consonants> .+ ) \s+ consonants?', re.X)

vowels     = re.compile(r'[aeiou]')
consonants = re.compile(r'[^aeiou]')

def comb(string, regex):
  return [ c for c in string if regex.match(c) ]

def lie_detector(string):
  r = extract_regex.search(string)
  vowel_count     = len(comb(r.group('string'), vowels))
  consonant_count = len(comb(r.group('string'), consonants))
  vowel_claim     = w2n.word_to_num(r.group('vowels'))
  consonant_claim = w2n.word_to_num(r.group('consonants'))
  return(vowel_count     == vowel_claim
     and consonant_count == consonant_claim)

View the entire Python script for this task on GitHub.

Elixir

I wasn’t able to find a module that translated words into numbers for Elixir, so I used the code in Lingua::EN::Words2Nums as inspiration to whip up a small Elixir implementation. It assumes all the words are separated by either spaces or dashes, and then it loops through the words and adds up a value looked up from a map. It will handle vales up to ninety-nine.

The rest of the problem is pretty much exactly like the other implementations.

defp word_map(), do: %{
  "naught"   => 0,
  "nought"   => 0,
  "zero"     => 0,
  "one"      => 1,
  "two"      => 2,
  "three"    => 3,
  "four"     => 4,
  "five"     => 5,
  "six"      => 6,
  "seven"    => 7,
  "eight"    => 8,
  "nine"     => 9,
  "ten"      => 10,
  "eleven"   => 11,
  "twelve"   => 12,
  "thirteen" => 13,
  "fifteen"  => 15,
  "eighteen" => 18,
  "ninteen"  => 19,
  "twenty"   => 20,
  "thirty"   => 30,
  "forty"    => 40,
  "fourty"   => 40,
  "fifty"    => 50,
  "sixty"    => 60,
  "seventy"  => 70,
  "eighty"   => 80,
  "ninety"   => 90,
  "ninty"    => 90, # common mispelling
}

defp words2num([], num), do: num
defp words2num([word | words], num), do:
  words2num(words, num + Map.get(word_map(), word, 0))
defp words2num(words), do:
  words2num(
    words |> String.replace("-", " ") |> String.split, 0
  )

defp extract_regex() do
  "(?<string>\\w+)\\s+\\S+\\s+" <>
  "(?<vowels>.+)\\s+vowels?" <>
  "\\s+and\\s+" <>
  "(?<consonants>.+)\\s+consonants?" |> Regex.compile!("x")
end

defp vowels(str),     do: Regex.replace(~r/[^aeiou]/, str, "")
defp consonants(str), do: Regex.replace(~r/[aeiou]/, str, "")

def lie_detector(str) do
  parsed = Regex.named_captures(extract_regex(), str)
  string = Map.get(parsed, "string")
  vowel_count     = vowels(string)     |> String.length
  consonant_count = consonants(string) |> String.length
  vowel_claim     = words2num(Map.get(parsed, "vowels"))
  consonant_claim = words2num(Map.get(parsed, "consonants"))

  vowel_count == vowel_claim and
  consonant_count == consonant_claim
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-363/packy-anderson

Leave a Reply