Heckroth Industries

Perl

Advent of Code 2020 - Day 1

So, it’s that time of year again when I spend a bit of time tackling some of the Advent Of Code challenges. As a bit of an exercise I’ve decided that for some of the days that I’ve completed I’ll write down a bit of an explanation of how I tackled it. So let’s start with Day 1.

Part 1

Each Day’s challenge consists of two parts and the simplified explanation for the first part for Day 1’s challenge is:

Given a list of numbers find two that numbers that add up to 2020. Take those two numbers and multiply them together to get your solution.

Multiplication is trivial, getting the two numbers that add up to 2020 is the part of the challenge that you have to think a little bit about. So let’s look at how I tackled that.

So we need a function that given a list finds the two entries that add up to 2020 - lets call it findTwoEntriesThatSumTo. The first parameter can be the number we want the two list entries to add up to, the rest of the parameters can be the list.

Now we know what our function is going to be called and what parameters it takes, we can write a test:

use Day_01 qw( findTwoEntriesThatSumTo );

my @testExpenses = ( 1721, 979, 366, 299, 675, 1456 );

subtest 'Part 1' => sub {
    cmp_deeply(
        [ findTwoEntriesThatSumTo(2020, @testExpenses ) ],
        bag( 1721, 299 ),
        "Should find the two entries that sum to 2020"
    );
};

We’re comparing against a bag as the order that the two entries are returned doesn’t matter.

Now that we have a failing test we can write the code to make it pass. There’s a lot of different ways to tackle the problem, but the one I ended up with is:

sub findTwoEntriesThatSumTo {
    my ( $value, @list ) = @_;

    while ( my $a = shift @list ) {
        foreach my $b ( @list ) {
            return ( $a, $b ) if $a + $b == $value;
        }
    }

    return;
}

The first line defines the function, and the second extracts the parameters into variables (Perl passes parameters into a function via the special @_ array).

In Perl shift removes the first item from an array and returns it. If the list is empty then it’ll return undef, if the condition in a while loop evaluates to undefined then the while loop is done.

Inside the while loop we have a foreach loop that loops through the entries left in our array.

Inside that foreach loop we’ll return the two values if they add add up to the value we’re looking for, otherwise the foreach loop will move onto the next value in the list.

If the foreach loop completes without finding a suitable value then control is returned to the while loop which takes the next value off the start of the list and runs through the foreach loop again to see if any other number in the list will add up with it to the value we’re looking for. (Note that each time round the while loop the list is getting shorter).

If there isn’t a pair of numbers in the list that add up to 2020 then eventually the list will be empty and the while loop will hand control to the next statement after it, which in this case is a simple return. That return at the end of the function makes sure that we’ll get an undef back from the function if it doesn’t find a suitable answer.

Once the that was written, the bugs fixed and the test passing I put together a simple script that used it to find the answer to the first part of the Day 1 challenge.

Part 2

Part 2’s challenge is almost identical to Part 1 except this time we’re looking for three numbers that add up to 2020. So lets create a new function called findThreeEntriesThatSumTo that takes the same parameters as our function that solves Part 1. As before we’ll create a test so that we know what we’re trying to achieve:

subtest 'Part 2' => sub {
    cmp_deeply(
        [ findThreeEntriesThatSumTo( 2020, @testExpenses ) ],
        bag( 979, 366, 675 ),
        "Should find the three entries that sum to 2020"
    );
};

With a failing test we’re in a position to write our function to solve the problem. There’s a lot of ways to view the new challenge, but there all going to involve looping through our list of numbers trying to find two others that when added to it gives us 2020. Luckily for us we already have a function that given a target value and a list of numbers will try to find two that add up to that target value. So lets use that in a similar while loop to that we used in Part 1:

sub findThreeEntriesThatSumTo {
    my ( $value, @list ) = @_;

    while ( my $a = shift @list ) {
        my ( $b, $c ) = findTwoEntriesThatSumTo( $value - $a, @list );
        return ( $a, $b, $c ) if defined $b;
    }

    return;
}

The while loop functions in exactly the same way as it does in our solution to Part 1, shifting the first entry out of the list on each time round.

Each iteration of the while loop starts by calling the findTwoEntriesThatSumTo function and storing the result in the variables $b and $c. The first parameter passed to findTwoEntriesThatSumTo is the result of subtracting the number we shifted off the start of our list ($a) from our target value ($value), the rest of the parameters we pass are what remains of our list.

If our findTwoEntriesThatSumTo function doesn’t find two values then it returns undef and $b an $c will both be undefined. We can use this as a check on the next line to see if we’ve found our answer or if we need to carry on to the next time round the loop. If $b is defined then it’s found an answer and can return the three values it has found ($a, $b and $c). However, if $b isn’t defined then the while loop will move on and try the next number in our list.

If by some chance it doesn’t find three numbers in the list that add up to our target value then the while loop will finish and the return at the end of the function will return undef to the caller.

Once the function was working I updated my script from Part 1 to also call our new function to solve Part 2.

Jason — 2020-12-04

Picking up DBD::Mock

A few months ago I started using the DBD::Mock Perl module as part of some unit tests for a project I was working on. It was pretty simple to pick up and use, but I found that there was a feature missing that would make it easier for me to use. As it’s open source I was able to dig into the module’s code and figure out how to add the new functionality. The internals of the module are logically structured so it only took about an hour to prepare a patch, but when I tried to submit the patches back to the source I discovered that the module was no longer being actively maintained. This discovery triggered a chain of events which resulted in me taking on a maintainer role for the module.

As the new maintainer, the first task I had to undertake was to get the codebase into a repository that I controlled. This involved cloning the old GitHub repository with git’s --bare option and then using the --mirror option to push it up to the new GitLab repository.

Once that was done I needed to build a development environment around it, starting with migrating the build process to be consistent with my other CPAN modules (i.e. get it set up with Minilla).

Migrating the build process to using Minilla left one last step to do before the development environment was ready, Continuous Integration (CI). In GitLab the CI logic is controlled by the .gitlab-ci.yml file, and I didn’t need anything complicated, so I first went with:

image: perl:latest

before_script:
  - cpanm Minilla

stages:
  - test

unitTests:
    stage: test
    script:
      - minil test

Quick explanation of this .gitlab-ci.yml file:

  • Image tells GitLab’s CI which Docker image to use (in this case the latest Perl image from Docker Hub

  • before_script sets a series of commands to prepend to each job’s script

  • stages list the stages in our CI pipeline (in this case just the test stage)

  • unitTests is a job with the following properties:

    • stage the stage this job is part of (this one’s part the test stage)
    • script the script that commands that get run to perform the job

Now I had a development environment ready, I could get started with figuring out what to tackle for my first release. Reviewing the module’s RT queue showed a number of issues that needed investigating and resolving. I decided to keep it simple for the my first release and targeted three easy issues:

  • Adding in details about the module’s Git repository

  • Fixing a spelling mistake in the POD

  • Adding in my patches

Once they were done I used Minilla to release a new version (v1.46). A few hours later and the new version was available on CPAN and could be installed in the usual way for CPAN modules.

The next day I got an email from CPAN Testers , a group of people who test CPAN modules against different versions of Perl on different operating systems. The new version was failing on versions of Perl below v5.10.0. Sure enough I’d used a defined-or (//) which isn’t available in Perl v5.8.

The first thing to do was to fix my CI pipeline to make sure that I tested against Perl v5.8 as well as the latest version, so I wouldn’t make this mistake again. After a bit of playing with the .gitlab-ci.yml file, it looked like the following:

stages:
  - test

before_script:
  - cpanm Module::Build::Tiny Test::Pod Test::Pod::Coverage
  - cpanm --installdeps .
  - perl Build.PL
  - perl Build

unitTestsLatest:
    image: perl:latest
    stage: test
    script:
      - perl Build test

unitTestsV5.8:
    image: perl:5.8-threaded
    stage: test
    script:
      - perl Build test

There were three key changes:

  • Removal of Minilla in the build and testing process, the before_script now consisted of 4 commands to install dependencies, optional modules, run Build.PL and use the Build file produced to build the module so it’s ready for testing

  • A new unitTestsV5.8 job for testing against Perl v5.8

  • The image property has moved into the jobs as each job needs to use a different Perl docker image depending on the version being tested

These changes made it a lot easier to extend the versions of Perl being tested against by simply adding a new job (hint: the latest version of DBD::Mock tests against 13 different versions of Perl).

Once the CI was testing against Perl v5.8 as well as the latest, I could actually get around to fixing the bug and preparing the next release (v1.47). As development of the module had progressed in the time up to the point that CPAN Testers reported the issue with Perl v5.8, the new release also contained the following changes:

  • Max Carey’s patch from rt86294

  • Addition of a new experimental Connection Callback feature

Over the next month, two additional release of DBD::Mock were made, which resolved the last of the open issues in it’s RT queue. I’m now holding off on development for a little while to give time for any bugs to be found and reported.

Jason — 2019-10-09

Augmenting LDAP

Recently I needed to augment an LDAP service so that we could authenticate users against an Active Directory or an another internal system. This initially looked like a very time consuming task which would get very messy, that was until I stumbled across the ability for OpenLDAP to use a Perl Module for processing LDAP requests.

The documentation for the actual Perl Module side of this is not very good, the best thing to do is to play with the example module to get an understanding of how it all fits together.

Any sticking points? yes, if you are using Red Hat Enterprise Linux (Version 5 in my case) then you have to get the stable version of OpenLDAP and manually compile and install it (remembering to specify –enable-perl when configuring). The version being used by Red Hat doesn’t include the perl backend part of OpenLDAP and even if you install their source and try to compile it as a module it fails.

If you require the option to accept a search filter with sAMAccountName in it then you will need to create a file with the other OpenLDAP schema containing

attributetype ( 1.2.840.113556.1.4.221
NAME 'sAMAccountName'
EQUALITY caseIgnoreMatch
SYNTAX '1.3.6.1.4.1.1466.115.121.1.15'
SINGLE-VALUE )

and in your slapd.conf add an include line to include the schema file.

The bind method wasn’t present in the Perl example module I started from and while some people say you shouldn’t do the bind in Perl but I couldn’t get it started without it. Here is an extract of the bind method I used.

sub bind {
    print {*STDERR} "==== bind start ====\n";
    my ($this, $dn, $pass)=@_;
    print {*STDERR} "DN=$dn\n";
    #print {*STDERR} "Pass=$pass\n";

    my $retval=1;

    # Code here to set $retval to 0 if the distinguised name and password are valid
    print {*STDERR} "==== bind end ====\n";
    return $retval;

If you don’t require a method then simply return the value 53, which is an “unwilling to perform” error.

UTF-8 and CSVs

Recently I have had to produce some CSVs using UTF-8 character encoding. The UTF-8 encoding is easy to do you just need to remember to set the header charset to be utf-8 when printing the CGI header.

use CGI;
my $CGI=new CGI;
print $CGI->header(-type=>'text/csv', -charset=>'utf-8', -attachment =>$filename);

Then you have to print the Byte Order Mark (BOM) which in hex is FEFF as the very first thing so that Excel will recorgnise the CSV as being in UTF-8 and not in its default character set.

print "\x{FEFF}";

Interestingly from what I can tell this BOM is actually for UTF-16, the BOM for UTF-8 should be 0xEFBBBF, but this didn’t seem to work with Excel.

Note: Usually the BOM is not recommended for UTF-8 as it can cause problems, but in the case of CSV’s that you want to open in Excel it is required.

Jason — 2011-04-13