PERL WEEKLY CHALLENGE – 061

This is my 31th week participating into the weekly challenge.


TASK #1 › Product SubArray

Reviewed by: Ryan Thompson

Given a list of 4 or more numbers, write a script to find the contiguous sublist that has the maximum product. The length of the sublist is irrelevant; your job is to maximize the product.

Example

Input: [ 2, 5, -1, 3 ]

Output: [ 2, 5 ] which gives maximum product 10.


For this challenge, I divide the initial list into smaller lists and iterated through the smaller sublist.

We store the max product and indices of the list which give us the max product. If the max product of the new sublist is greater, we store that instead.

So the algorithm works like this.
(I’ll use the list [ 2, 5, -1, 3, 4 ] as an example):

[ 2, 5, -1, 3, 4 ] => stores [2, 5] and 10 as the longest list chain

[ 5, -1, 3, 4] => doesn’t find a higher max product (the highest product found was 5)

[ -1, 3, 4] => doesn’t find a higher max product (the highest product found was -1)

[ 3, 4 ] => stores [3, 4] and 12

[ 4 ] => doesn’t find a higher max product (the highest product found was 4)

Perl 5 solution

#!/usr/bin/perl
# Test: ./ch-1.pl 30
use strict;
use warnings;
use feature qw /say/;

say max_product([ 2, 5, -1, 3 ]);

sub max_product {
	my $list = shift;

	# Index of the array that will return
	# the max product
	my $left  = 0;
	my $right = scalar(@$list);

	# Max product
	my $max_product = 1;

	# Loop through the list
	for (my $i = 0; $i < scalar(@$list); $i++ ) {
		my $j = $i;

		# Temp variable
		my $current_product = 1;

		# Loop through the list another time
		while ($j < scalar(@$list)) {
			$current_product =
				$current_product * $list->[$j];

			if ($current_product >= $max_product) {
				$max_product = $current_product;
				$left  = $i;
				$right = $j;
			}

			$j++;
		}
	}

	return '[' .
		(join ', ', @{$list}[$left .. $right]) .
		']' . ' which gives a maximum product of ' .
		$max_product;
}

Output: perl ./ch-1.pl

[2, 5] which gives a maximum product of 10

Raku solution

# Test: perl6 ch-1.p6
sub MAIN() {
	say max-product([ 2, 5, -1, 3 ]);
}

sub max-product(@list) {

	# Index of the array that will return
	# the max product
	my $left  = 0;
	my $right = @list.elems;

	# Max product
	my $max_product = 1;

	# Loop through the list
	for ^@list -> $i {
		my $j = $i;

		# Temp variable
		my $current_product = 1;

		# Loop through the list another time
		while ($j < @list.elems) {
			$current_product =
				$current_product * @list[$j];

			if ($current_product >= $max_product) {
				$max_product = $current_product;
				$left  = $i;
				$right = $j;
			}

			$j++;
		}
	}

	return '[' ~
		@list[$left .. $right].join(', ') ~
		']' ~ ' which gives a maximum product of ' ~
		$max_product;;
}

Output perl6 ch-1.p6

[2, 5] which gives a maximum product of 10

TASK #2 › IPv4 Partition

Reviewed by: Ryan Thompson

You are given a string containing only digits (0..9). The string should have between 4 and 12 digits.

Write a script to print every possible valid IPv4 address that can be made by partitioning the input string.

For the purpose of this challenge, a valid IPv4 address consists of four “octets” i.e. ABC and D, separated by dots (.).

Each octet must be between 0 and 255, and must not have any leading zeroes. (e.g., 0 is OK, but 01 is not.)

Example

Input: 25525511135,

Output:

255.255.11.135
255.255.111.35

For this challenge I brute forced the solution my finding all the possible locations of the . then checking the string if its a valid IP address.

so a string like: 12345

Will produce these combinations
1.2.3.45
1.2.34.5
1.23.4.5
12.3.4.5

Perl 5 solution

#!/usr/bin/perl
# Test: ./ch-2.pl
use strict;
use warnings;
use feature qw /say/;
use Algorithm::Combinatorics qw(combinations);

my $ip_address = $ARGV[0] || '25525511135';
partition_ip_string($ip_address);

# Partition the ip string
sub partition_ip_string {
	my $string = shift;
	my $length = length($string) - 2;

	# Validate string
	return undef if
		( length($string) < 4  ||
		  length($string) > 12 ||
		  !($string =~ /^\d+$/)
		);

	# Find all the combinations for the possible ips
	my @dot_positions = (0 .. $length);
	my $iter = combinations(\@dot_positions, 3);

	# Process the combinations
	while (my $combos = $iter->next) {
		my $to_test = $string;
		my $offset = 0;

		for my $dot_position (@$combos) {
			my $position =
				($dot_position + $offset) + 1;

			# Append to the test string;
			$to_test =
				(substr $to_test, 0, $position)
				. '.' .
				(substr $to_test, $position);

			# Offset the string
			$offset++;
		}

		say $to_test
			if (validate_ip_string($to_test));
	}
}

# Validate the IP String
sub validate_ip_string {
	for my $digit (split('\.', shift)) {
		return 0 if ($digit > 255);
		return 0 if ($digit =~ /^0\d+$/);
	}

	return 1;
}

Output ./ch-2.pl

255.255.11.135
255.255.111.35

Raku solution

# Test: perl6 ch-2.p6
multi MAIN() {
	MAIN('25525511135');
}

multi MAIN(Str $str) {
	partition-ip-string($str);
}

# Partition the ip string
sub partition-ip-string (Str $str) {
	my $length = $str.chars - 2;

	# Find all the combinations for the possible ips
	my @dot_positions = (0 .. $length);
	my @combos = @dot_positions.combinations: 3;

	# Process the combinations
	for @combos -> @combo {
		my $to_test = $str;
		my $offset = 0;

		for (@combo) -> $dot_position {
			my $position =
				($dot_position + $offset) + 1;

			# Append to the test string;
			$to_test =
				$to_test.substr(0, $position)
				~ '.' ~
				$to_test.substr($position);

			# Offset the string
			$offset++;
		}

		say $to_test
			if (validate-ip-string($to_test));
	}
}

# Validate the IP String
sub validate-ip-string(Str $str) {
	for $str.split('.') -> $digit {
		return False if ($digit > 255);
		return False if ($digit ~~ /^0\d+$/);
	}
	return True;
}

Output perl6 ch-2.p6

255.255.11.135
255.255.111.35

One thought on “PERL WEEKLY CHALLENGE – 061

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s